2025-11-16T13:10:12.550115

Online MMS Allocation for Chores

Song, Tao, Wang et al.
We study the problem of fair division of indivisible chores among $n$ agents in an online setting, where items arrive sequentially and must be allocated irrevocably upon arrival. The goal is to produce an $α$-MMS allocation at the end. Several recent works have investigated this model, but have only succeeded in obtaining non-trivial algorithms under restrictive assumptions, such as the two-agent bi-valued special case (Wang and Wei, 2025), or by assuming knowledge of the total disutility of each agent (Zhou, Bai, and Wu, 2023). For the general case, the trivial $n$-MMS guarantee remains the best known, while the strongest lower bound is still only $2$. We close this gap on the negative side by proving that for any fixed $n$ and $\varepsilon$, no algorithm can guarantee an $(n - \varepsilon)$-MMS allocation. Notably, this lower bound holds precisely for every $n$, without hiding constants in big-$O$ notation, thereby exactly matching the trivial upper bound. Despite this strong impossibility result, we also present positive results. We provide an online algorithm that applies in the general case, guaranteeing a $\min\{n, O(k), O(\log D)\}$-MMS allocation, where $k$ is the maximum number of distinct disutilities across all agents and $D$ is the maximum ratio between the largest and smallest disutilities for any agent. This bound is reasonable across a broad range of scenarios and, for example, implies that we can achieve an $O(1)$-MMS allocation whenever $k$ is constant. Moreover, to optimize the constant in the important personalized bi-valued case, we show that if each agent has at most two distinct disutilities, our algorithm guarantees a $(2 + \sqrt{3}) \approx 3.7$-MMS allocation.
academic

অনলাইন MMS বরাদ্দ গৃহস্থালী কাজের জন্য

মৌলিক তথ্য

  • পেপার আইডি: 2507.14039
  • শিরোনাম: Online MMS Allocation for Chores
  • লেখক: Jiaxin Song (University of Illinois Urbana-Champaign), Biaoshuai Tao (Shanghai Jiao Tong University), Wenqian Wang (Shanghai Jiao Tong University), Yuhao Zhang (Shanghai Jiao Tong University)
  • শ্রেণীবিভাগ: cs.GT (কম্পিউটার বিজ্ঞান - গেম তত্ত্ব)
  • প্রকাশনার সময়: ২০২৫ সালের অক্টোবর ১১ (arXiv v2)
  • পেপার লিংক: https://arxiv.org/abs/2507.14039

সারসংক্ষেপ

এই পেপারটি অনলাইন পরিবেশে n সংখ্যক বুদ্ধিমান এজেন্টদের মধ্যে অবিভাজ্য গৃহস্থালী কাজের ন্যায্য বরাদ্দ সমস্যা অধ্যয়ন করে। এই সেটিংয়ে, কাজগুলি ক্রমানুসারে আসে এবং আগমনের সময় কোনো এজেন্টের কাছে অপরিবর্তনীয়ভাবে বরাদ্দ করা আবশ্যক, লক্ষ্য হল চূড়ান্তভাবে α-MMS বরাদ্দ তৈরি করা। সাম্প্রতিক কাজ সীমাবদ্ধ অনুমানের অধীনে অগ্রগতি অর্জন করেছে, তবে সাধারণ ক্ষেত্রে, পরিচিত সর্বোত্তম গ্যারান্টি এখনও তুচ্ছ n-MMS, এবং সবচেয়ে শক্তিশালী নিম্ন সীমা মাত্র ২। এই পেপারটি প্রমাণ করে যে যেকোনো স্থির n এবং ε এর জন্য, কোনো অ্যালগরিদম (n-ε)-MMS বরাদ্দ গ্যারান্টি দিতে পারে না, এভাবে নেতিবাচক ফলাফলের ব্যবধান বন্ধ করে। একই সাথে, এই পেপারটি একটি অনলাইন অ্যালগরিদম উপস্থাপন করে যা min{n, O(k), O(log D)}-MMS বরাদ্দ গ্যারান্টি দেয়, যেখানে k সকল এজেন্টের মধ্যে স্বতন্ত্র নেতিবাচক উপযোগিতা মানের সর্বোচ্চ সংখ্যা, এবং D যেকোনো এজেন্টের সর্বোচ্চ এবং সর্বনিম্ন নেতিবাচক উপযোগিতার মধ্যে সর্বোচ্চ অনুপাত।

গবেষণা পটভূমি এবং প্রেরণা

১. সমস্যার সংজ্ঞা

এই পেপারটি অবিভাজ্য গৃহস্থালী কাজের অনলাইন ন্যায্য বরাদ্দ সমস্যা অধ্যয়ন করে। ঐতিহ্যবাহী পণ্য বরাদ্দের বিপরীতে, গৃহস্থালী কাজের নেতিবাচক উপযোগিতা রয়েছে, এবং এজেন্টরা যতটা সম্ভব কম কাজ গ্রহণ করতে চায়। অনলাইন সেটিংয়ে, কাজগুলি ক্রমানুসারে আসে, এবং অ্যালগরিদমকে প্রতিটি কাজ আগমনের সময় অবিলম্বে এটি কোনো এজেন্টের কাছে বরাদ্দ করতে হয়, এবং বরাদ্দ সিদ্ধান্ত অপরিবর্তনীয়।

২. গবেষণার গুরুত্ব

এই সমস্যাটি বাস্তবে ব্যাপক প্রয়োগ রয়েছে, যেমন:

  • অনলাইন সেবা প্ল্যাটফর্মে কর্মচারীদের কাজের কাজ বরাদ্দ করা
  • সিস্টেম লোড ব্যালেন্সিং সমস্যা
  • সম্পদ সময়সূচীতে ন্যায্যতার গ্যারান্টি

৩. বিদ্যমান পদ্ধতির সীমাবদ্ধতা

বিদ্যমান গবেষণা নিম্নলিখিত সীমাবদ্ধতা রয়েছে:

  • অত্যন্ত সীমাবদ্ধ অনুমানের অধীনে অ-তুচ্ছ ফলাফল অর্জন করা (যেমন দুই এজেন্ট দ্বি-মূল্য ক্ষেত্রে)
  • প্রতিটি এজেন্টের মোট নেতিবাচক উপযোগিতা পূর্বজ্ঞান প্রয়োজন
  • সাধারণ ক্ষেত্রে, সর্বোত্তম পরিচিত অ্যালগরিদম শুধুমাত্র তুচ্ছ n-MMS গ্যারান্টি দিতে পারে

৪. গবেষণা প্রেরণা

এই পেপারটির লক্ষ্য:

  • অনলাইন MMS বরাদ্দ সমস্যার তাত্ত্বিক সীমা নির্ধারণ করা
  • সাধারণ ক্ষেত্রে প্রযোজ্য ব্যবহারিক অ্যালগরিদম ডিজাইন করা
  • বাস্তব পরামিতি সীমাবদ্ধতার অধীনে উন্নত কর্মক্ষমতা গ্যারান্টি প্রদান করা

মূল অবদান

১. তাত্ত্বিক নিম্ন সীমার নির্ভুল চিত্রায়ন: প্রমাণ করে যে যেকোনো স্থির n এবং ε > ০ এর জন্য, কোনো অ্যালগরিদম (n-ε)-MMS বরাদ্দ গ্যারান্টি দিতে পারে না, সম্পূর্ণভাবে তাত্ত্বিক ব্যবধান বন্ধ করে

२. সর্বজনীন অনলাইন অ্যালগরিদম: সাধারণ ক্ষেত্রে প্রযোজ্য একটি অ্যালগরিদম প্রস্তাব করে যা min{n, O(k), O(log D)}-MMS বরাদ্দ গ্যারান্টি দেয়

३. পরামিতিযুক্ত বিশ্লেষণ: যখন k (স্বতন্ত্র নেতিবাচক উপযোগিতা মানের সংখ্যা) ধ্রুবক হয়, অ্যালগরিদম O(1)-MMS গ্যারান্টি অর্জন করতে পারে

४. অপ্টিমাইজড দ্বি-মূল্য ক্ষেত্র: ব্যক্তিগতকৃত দ্বি-মূল্য ক্ষেত্রের জন্য, (2+√3) ≈ 3.7-MMS এর উন্নত গ্যারান্টি প্রদান করে

५. নতুন বিশ্লেষণ কৌশল: "স্ট্যাকিং গেম" কাঠামো প্রবর্তন করে, সমস্যাটিকে বিশেষ পার্থক্য ন্যূনতমকরণ সমস্যায় রূপান্তরিত করে

পদ্ধতির বিস্তারিত বর্ণনা

কাজের সংজ্ঞা

  • ইনপুট: n সংখ্যক এজেন্ট, m সংখ্যক ক্রমানুসারে আসা গৃহস্থালী কাজ
  • সীমাবদ্ধতা: প্রতিটি কাজ j এর জন্য এজেন্ট i এর ব্যক্তিগতকৃত নেতিবাচক উপযোগিতা di(j) রয়েছে, নেতিবাচক উপযোগিতা ফাংশন যোজক
  • আউটপুট: বরাদ্দ A = (A1, ..., An), যেখানে Ai এজেন্ট i এর কাছে বরাদ্দকৃত কাজের সেট
  • লক্ষ্য: α-MMS বরাদ্দ অর্জন করা, অর্থাৎ সকল i এর জন্য, di(Ai) ≤ α · MMSi

মডেল স্থাপত্য

১. সাধারণীকৃত রাউন্ড-রবিন অ্যালগরিদম কাঠামো

অ্যালগরিদম রাউন্ড-রবিন চিন্তার সম্প্রসারণের উপর ভিত্তি করে:

  • প্রতিটি এজেন্ট i এর প্রতিটি নেতিবাচক উপযোগিতা প্রকার θ এর জন্য চাপ পরামিতি Hθi বজায় রাখে
  • চাপ পরামিতি আদর্শ বরাদ্দের সাপেক্ষে এজেন্টের "অতিরিক্ত লোড" পরিমাপ করে
  • লোভী কৌশল: নতুন আগমনকারী কাজটি সংশ্লিষ্ট প্রকারের সর্বনিম্ন চাপ সহ এজেন্টের কাছে বরাদ্দ করে

२. মূল্য রাউন্ডিং কৌশল

  • প্রতিটি আগমনকারী কাজের নেতিবাচক উপযোগিতা ২ এর নিকটতম শক্তিতে রাউন্ড করে
  • স্বতন্ত্র নেতিবাচক উপযোগিতা প্রকারের সংখ্যা হ্রাস করে
  • প্রতিযোগিতামূলক অনুপাত O(k²) থেকে O(k) এ উন্নত করে

३. চাপ আপডেট প্রক্রিয়া

যখন কাজ j আসে:

  • যদি এজেন্ট i কাজ j (প্রকার θ) গ্রহণ করে, তাহলে Hθi ১ দ্বারা বৃদ্ধি পায়
  • অন্যান্য এজেন্ট i' এর সংশ্লিষ্ট চাপ Hθi' ১/(n-१) দ্বারা হ্রাস পায়

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

१. স্ট্যাকিং গেম বিমূর্তকরণ

অনলাইন বরাদ্দ সমস্যাটিকে ক্রমাগত প্রতিসম "স্ট্যাকিং গেম" এ বিমূর্ত করে:

  • ব্যবধান (-१/२, १/२] এ অ-হ্রাসমান ফাংশন f বজায় রাখে
  • প্রতিদ্বন্দ্বী মোট পরিমাপ १/k এর ব্যবধান সংযোগ নির্বাচন করে
  • অ্যালগরিদম লোভীভাবে নিম্ন অংশ উন্নীত করে, উচ্চ অংশ হ্রাস করে
  • প্রমাণ করে যে প্রতিদ্বন্দ্বী ফাংশন মূল্য O(k) অতিক্রম করতে পারে না

२. পুনরাবৃত্তিমূলক নির্মাণের নিম্ন সীমা প্রমাণ

পুনরাবৃত্তিমূলক কঠিন উদাহরণ নির্মাণ ডিজাইন করে:

  • T(n', ε) কে n' এজেন্টদের (n-ε)-MMS অর্জনের জন্য প্রয়োজনীয় রাউন্ড সংখ্যা হিসাবে সংজ্ঞায়িত করে
  • T(n') ব্যবহার করে T(n'+१) এর কঠিন উদাহরণ নির্মাণ করে
  • চতুর "পরিষ্কার" প্রক্রিয়া যা পূর্ববর্তী বরাদ্দকে উপেক্ষণীয় করে তোলে

পরীক্ষামূলক সেটআপ

এই পেপারটি প্রধানত একটি তাত্ত্বিক কাজ, ঐতিহ্যবাহী অর্থে পরীক্ষামূলক মূল্যায়ন নেই, বরং গাণিতিক প্রমাণের মাধ্যমে তাত্ত্বিক ফলাফল যাচাই করে।

তাত্ত্বিক যাচাইকরণ পদ্ধতি

१. গঠনমূলক প্রমাণ: নিম্ন সীমা প্রমাণের জন্য নির্দিষ্ট কঠিন উদাহরণ নির্মাণের মাধ্যমে २. আবেগপ্রবণ প্রমাণ: অ্যালগরিদমের কর্মক্ষমতা গ্যারান্টি প্রমাণের জন্য গাণিতিক আবেগ ব্যবহার করে ३. দ্বৈত বিশ্লেষণ: স্ট্যাকিং গেমের দ্বৈত সমস্যার মাধ্যমে অ্যালগরিদম কর্মক্ষমতা বিশ্লেষণ করে

পরীক্ষামূলক ফলাফল

প্রধান তাত্ত্বিক ফলাফল

१. নির্ভুল অসম্ভবতা ফলাফল

উপপাদ্য ५: যেকোনো n এবং ε > ० এর জন্য, কোনো অনলাইন অ্যালগরিদম (n-ε)-MMS বরাদ্দ গ্যারান্টি দিতে পারে না।

এই ফলাফল নির্ভুল, বড় O চিহ্নে লুকানো কোনো ধ্রুবক নেই, সম্পূর্ণভাবে তুচ্ছ উপরের সীমার সাথে মেলে।

२. সর্বজনীন অ্যালগরিদম কর্মক্ষমতা

উপপাদ্য १: অ্যালগরিদম १ min{n, O(k), O(log D)}-MMS বরাদ্দ গ্যারান্টি দেয়, যেখানে:

  • k সকল এজেন্টের মধ্যে স্বতন্ত্র নেতিবাচক উপযোগিতা মানের সর্বোচ্চ সংখ্যা
  • D যেকোনো এজেন্টের সর্বোচ্চ এবং সর্বনিম্ন নেতিবাচক উপযোগিতার সর্বোচ্চ অনুপাত

३. দ্বি-মূল্য ক্ষেত্রের অপ্টিমাইজেশন

উপপাদ্য ६: ব্যক্তিগতকৃত দ্বি-মূল্য ক্ষেত্রের জন্য, একটি অ্যালগরিদম বিদ্যমান যা min{n, २+√३}-MMS বরাদ্দ গ্যারান্টি দেয়, যেখানে २+√३ ≈ ३.७।

প্রযুক্তিগত বিশ্লেষণ ফলাফল

१. স্ট্যাকিং গেমের সীমানা

উপপাদ্য ३: স্ট্যাকিং গেমে, প্রতিদ্বন্দ্বী २k এর বেশি লাভ অর্জন করতে পারে না।

এই ফলাফল অ্যালগরিদম বিশ্লেষণের মূল, সরাসরি O(k) প্রতিযোগিতামূলক অনুপাত নিয়ে আসে।

२. চাপ পরামিতির নিয়ন্ত্রণ

স্ট্যাকিং গেম বিশ্লেষণের মাধ্যমে, প্রমাণ করে যে সকল চাপ পরামিতি Hθi O(k) পরিসরে বজায় রাখা যায়, এভাবে অ্যালগরিদমের কর্মক্ষমতা নিশ্চিত করে।

সম্পর্কিত কাজ

१. অনলাইন লোড ব্যালেন্সিং

অনলাইন MMS বরাদ্দ সমস্যা ক্লাসিক অনলাইন লোড ব্যালেন্সিং সমস্যার সাথে ঘনিষ্ঠভাবে সম্পর্কিত:

  • গ্রাহাম (१९६९) এর যুগান্তকারী কাজ
  • বর্তমান সর্বোত্তম প্রতিযোগিতামূলক অনুপাত १.८८, १.९२ এর মধ্যে

२. অফলাইন MMS বরাদ্দ

অফলাইন ক্ষেত্রে MMS বরাদ্দ গবেষণা:

  • সর্বোত্তম উপরের সীমা: १५/१३ (Garg et al., २०२५)
  • সর্বোত্তম নিম্ন সীমা: ४४/४३ (Feige et al., २०२१)

३. অনলাইন ন্যায্য বরাদ্দ

অন্যান্য অনলাইন ন্যায্য বরাদ্দ কাজ:

  • ঈর্ষা-ভিত্তিক ন্যায্যতা ধারণা
  • এজেন্ট অনলাইন আগমন মডেল
  • পণ্যের অনলাইন বরাদ্দ

সিদ্ধান্ত এবং আলোচনা

প্রধান সিদ্ধান্ত

१. তাত্ত্বিক সীমার সম্পূর্ণ চিত্রায়ন: প্রমাণ করে যে n-MMS অনলাইন গৃহস্থালী কাজ বরাদ্দ সমস্যার নির্ভুল তাত্ত্বিক সীমা २. ব্যবহারিক অ্যালগরিদম ডিজাইন: পরামিতি সীমাবদ্ধতার অধীনে ভাল কর্মক্ষমতা সহ সর্বজনীন অ্যালগরিদম প্রদান করে ३. প্রযুক্তিগত পদ্ধতি অবদান: স্ট্যাকিং গেম কাঠামো এই ধরনের সমস্যার জন্য নতুন বিশ্লেষণ সরঞ্জাম প্রদান করে

সীমাবদ্ধতা

१. কঠিন উদাহরণের ব্যবহারিকতা: তাত্ত্বিক নিম্ন সীমা নির্মাণ চরম নেতিবাচক উপযোগিতা অনুপাত এবং বিভিন্ন নেতিবাচক উপযোগিতা মানের বিশাল সংখ্যা প্রয়োজন २. অ্যালগরিদমের পূর্ব জ্ঞান: দ্বি-মূল্য অপ্টিমাইজেশন অ্যালগরিদম প্রতিটি এজেন্টের সর্বোচ্চ দুটি নেতিবাচক উপযোগিতা মূল্য রয়েছে তা পূর্বজ্ঞান প্রয়োজন ३. ধ্রুবক ফ্যাক্টর: যদিও অ্যাসিম্পটোটিকভাবে সর্বোত্তম, ধ্রুবক ফ্যাক্টর এখনও উন্নতির জায়গা রয়েছে

ভবিষ্যত দিকনির্দেশনা

१. ধ্রুবক ফ্যাক্টর উন্নতি: বিশেষ ক্ষেত্রে প্রতিযোগিতামূলক অনুপাতের ধ্রুবক আরও অপ্টিমাইজ করা २. অন্যান্য ন্যায্যতা ধারণা: অন্যান্য ন্যায্যতা ধারণা যেমন ঈর্ষা-মুক্ততায় সম্প্রসারণ ३. বাস্তব প্রয়োগ: তাত্ত্বিক ফলাফল নির্দিষ্ট লোড ব্যালেন্সিং এবং কাজ সময়সূচী দৃশ্যে প্রয়োগ করা

গভীর মূল্যায়ন

সুবিধা

१. তাত্ত্বিক সম্পূর্ণতা: একটি গুরুত্বপূর্ণ খোলা সমস্যা সম্পূর্ণভাবে সমাধান করে, নির্ভুল তাত্ত্বিক সীমানা প্রদান করে २. প্রযুক্তিগত উদ্ভাবনী: স্ট্যাকিং গেম বিমূর্তকরণ বিভিন্ন পরামিতির অধীনে বিশ্লেষণকে মার্জিতভাবে একীভূত করে ३. ব্যবহারিক মূল্য: যুক্তিসঙ্গত পরামিতি পরিসরে তুচ্ছ অ্যালগরিদমের চেয়ে উল্লেখযোগ্যভাবে ভাল কর্মক্ষমতা প্রদান করে ४. বিশ্লেষণ গভীরতা: পুনরাবৃত্তিমূলক নির্মাণের নিম্ন সীমা প্রমাণ উচ্চ প্রযুক্তিগত স্তর প্রদর্শন করে

অসুবিধা

१. পরীক্ষামূলক যাচাইকরণ অনুপস্থিত: খাঁটি তাত্ত্বিক কাজ হিসাবে, বাস্তব ডেটায় যাচাইকরণ অনুপস্থিত २. পরামিতি নির্ভরশীলতা: অ্যালগরিদম কর্মক্ষমতা k এবং D এর মানের উপর গুরুতরভাবে নির্ভর করে ३. জটিলতা বিশ্লেষণ: অ্যালগরিদমের সময় এবং স্থান জটিলতার বিস্তারিত বিশ্লেষণ নেই

প্রভাব

१. তাত্ত্বিক অবদান: অনলাইন ন্যায্য বরাদ্দ তত্ত্বের জন্য গুরুত্বপূর্ণ তাত্ত্বিক ভিত্তি প্রদান করে २. পদ্ধতি মূল্য: স্ট্যাকিং গেম কৌশল অন্যান্য সম্পর্কিত সমস্যায় প্রযোজ্য হতে পারে ३. ব্যবহারিক নির্দেশনা: বাস্তব সিস্টেম ডিজাইনের জন্য তাত্ত্বিক নির্দেশনা প্রদান করে

প্রযোজ্য দৃশ্য

१. অনলাইন কাজ সময়সূচী: ন্যায্যতা গ্যারান্টি প্রয়োজন এমন কাজ বরাদ্দ সিস্টেমে প্রযোজ্য २. লোড ব্যালেন্সিং: বহু-সার্ভার লোড ব্যালেন্সিং দৃশ্যে প্রয়োগ করা যায় ३. সম্পদ বরাদ্দ: বিভিন্ন অনলাইন সম্পদ বরাদ্দ সমস্যায় প্রযোজ্য

সংদর্ভ

পেপারটি সমৃদ্ধ সম্পর্কিত কাজ উদ্ধৃত করে, যার মধ্যে রয়েছে:

  • Budish (२०१०): MMS ধারণার প্রস্তাব
  • Zhou et al. (२०२३): অনলাইন MMS বরাদ্দের প্রাথমিক কাজ
  • Wang and Wei (२०२५): দ্বি-এজেন্ট দ্বি-মূল্য ক্ষেত্রের ফলাফল
  • Garg et al. (२०२५): অফলাইন MMS বরাদ্দের সর্বশেষ অগ্রগতি

এই পেপারটি তাত্ত্বিক কম্পিউটার বিজ্ঞান এবং অ্যালগরিদম গেম তত্ত্ব ক্ষেত্রে গুরুত্বপূর্ণ অবদান রাখে, শুধুমাত্র একটি গুরুত্বপূর্ণ খোলা সমস্যা সম্পূর্ণভাবে সমাধান করে না, বরং ব্যবহারিক অ্যালগরিদম ডিজাইন এবং উদ্ভাবনী বিশ্লেষণ কৌশলও প্রদান করে। যদিও প্রধানত তাত্ত্বিক কাজ, তার ফলাফল বাস্তব প্রয়োগের জন্য গুরুত্বপূর্ণ নির্দেশনা মূল্য রয়েছে।