2025-11-18T20:31:13.847843

Fair Assignment of Indivisible Chores to Asymmetric Agents

Seddighin, Seddighin
We consider the problem of assigning indivisible chores to agents with different entitlements in the maximin share value (\MMS) context. While constant-\MMS\ allocations/assignments are guaranteed to exist for both goods and chores in the symmetric setting, the situation becomes much more complex when agents have different entitlements. For the allocation of indivisible goods, it has been proven that an $n$-\WMMS\ (weighted \MMS) guarantee is the best one can hope for. For indivisible chores, however, it was recently discovered that an $O(\log n)$-\WMMS\ assignment is guaranteed to exist. In this work, we improve this upper bound to a constant-\WMMS\ guarantee.\footnote{We prove the existence of a 20-\WMMS\ assignment, but we did not attempt to optimize the constant factor. We believe our methods already yield a slightly better bound with a tighter analysis.}
academic

অপ্রতিসম এজেন্টদের কাছে অবিভাজ্য কাজের ন্যায্য বরাদ্দ

মৌলিক তথ্য

  • পেপার আইডি: 2510.10698
  • শিরোনাম: অপ্রতিসম এজেন্টদের কাছে অবিভাজ্য কাজের ন্যায্য বরাদ্দ
  • লেখক: মাসউদ সেদ্দিঘিন, সাঈদ সেদ্দিঘিন
  • শ্রেণীবিভাগ: cs.GT (কম্পিউটার বিজ্ঞান - গেম তত্ত্ব)
  • প্রকাশনার সময়: ২০২৫ সালের ১২ অক্টোবর (arXiv প্রাক-প্রকাশনা)
  • পেপার লিঙ্ক: https://arxiv.org/abs/2510.10698v1

সারসংক্ষেপ

এই পেপারটি সর্বোচ্চ-ন্যূনতম শেয়ার মূল্য (MMS) কাঠামোর অধীনে বিভিন্ন অধিকার সম্পন্ন এজেন্টদের কাছে অবিভাজ্য কাজ বরাদ্দের ন্যায্য বিতরণ সমস্যা অধ্যয়ন করে। যদিও প্রতিসম সেটিংয়ে পণ্য এবং কাজের ধ্রুবক-MMS বরাদ্দ/বিতরণ নিশ্চিত করা হয়, তবে যখন এজেন্টদের বিভিন্ন অধিকার থাকে তখন পরিস্থিতি আরও জটিল হয়ে ওঠে। অবিভাজ্য পণ্যের বরাদ্দের জন্য, n-WMMS (ভারিত MMS) নিশ্চয়তা সর্বোত্তম হিসাবে প্রমাণিত হয়েছে। তবে অবিভাজ্য কাজের জন্য, সম্প্রতি O(log n)-WMMS বিতরণ নিশ্চয়তা পাওয়া গেছে। এই পেপারটি এই উপরের সীমাটি ধ্রুবক-WMMS নিশ্চয়তায় উন্নত করে, বিশেষভাবে 20-WMMS বিতরণের অস্তিত্ব প্রমাণ করে।

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

  1. মূল সমস্যা: এই পেপারটি অপ্রতিসম এজেন্টদের মধ্যে অবিভাজ্য কাজের ন্যায্য বরাদ্দ সমস্যা অধ্যয়ন করে। ক্লাসিক্যাল "কেক ভাগাভাগি" সমস্যার বিপরীতে, এখানে বিচ্ছিন্ন, অবিভাজ্য কাজ (chores) এবং বিভিন্ন অধিকার সম্পন্ন এজেন্টদের সাথে কাজ করা হয়।
  2. সমস্যার গুরুত্ব:
    • বাস্তব বিশ্বে অসমান অধিকারের পরিস্থিতি ঘন ঘন ঘটে, যেমন বিভিন্ন সংস্কৃতি এবং ধর্মে উত্তরাধিকার আইন সাধারণত অসমান বিতরণ নির্দিষ্ট করে
    • প্রাকৃতিক সম্পদ (যেমন তেল, মৎস্য) বরাদ্দ সাধারণত ভৌগোলিক, অর্থনৈতিক বা রাজনৈতিক বিবেচনার উপর ভিত্তি করে
    • এই বাস্তব চাহিদা অসমান অধিকারের অধীনে ন্যায্য বিতরণ অধ্যয়নের গুরুত্ব তুলে ধরে
  3. বিদ্যমান পদ্ধতির সীমাবদ্ধতা:
    • প্রতিসম সেটিংয়ের ধ্রুবক আনুমানিক নিশ্চয়তা সরাসরি প্রযোজ্য নয়, তবে অপ্রতিসম ক্ষেত্রে আরও চ্যালেঞ্জিং
    • পণ্য বরাদ্দের জন্য, n-WMMS সর্বোত্তম নিশ্চয়তা হিসাবে প্রমাণিত
    • কাজ বরাদ্দের জন্য, পূর্ববর্তী সেরা ফলাফল O(log n)-WMMS নিশ্চয়তা
  4. গবেষণা প্রেরণা: কাজ বরাদ্দের আনুমানিক অনুপাত লগারিদমিক স্তর থেকে ধ্রুবক স্তরে উন্নত করা, যা তাত্ত্বিকভাবে একটি প্রধান অগ্রগতি।

মূল অবদান

  1. প্রধান তাত্ত্বিক অবদান: অপ্রতিসম কাজ বরাদ্দ সমস্যায় 20-WMMS বিতরণের অস্তিত্ব প্রমাণ করা, যা প্রথম ধ্রুবক-WMMS নিশ্চয়তা
  2. অ্যালগরিদম উদ্ভাবন: স্তরযুক্ত চলমান ছুরি অ্যালগরিদম (Layered Moving Knife Algorithm) প্রস্তাব করা, যা চলমান ছুরি পদ্ধতিকে অপ্রতিসম সেটিংয়ে প্রসারিত করে
  3. ছোট আকারের ক্ষেত্রে অপ্টিমাইজেশন: n=3 এবং n=4 ক্ষেত্রে, log n+1 এর চেয়ে ভাল উপরের সীমা প্রদান করা
  4. কাজ-স্বাধীন বিশ্লেষণ: কাজ-স্বাধীন বিশ্লেষণ কৌশল উন্নয়ন, ছোট আকারের এজেন্ট সংখ্যার অধীনে সীমানা উন্নত করা

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

কাজের সংজ্ঞা

ইনপুট:

  • N = {a₁, a₂, ..., aₙ}: n সংখ্যক এজেন্ট
  • M = {b₁, b₂, ..., bₘ}: m সংখ্যক কাজ
  • Vᵢ: এজেন্ট aᵢ এর যোজক খরচ ফাংশন
  • wᵢ: এজেন্ট aᵢ এর অধিকার, যেখানে ∑wᵢ = 1

আউটপুট: কাজ থেকে এজেন্টে বরাদ্দ, যাতে প্রতিটি এজেন্ট aᵢ যে কাজের প্যাকেজ Sᵢ পায় তা Vᵢ(Sᵢ) ≤ α·WMMSᵢ সন্তুষ্ট করে

মূল সংজ্ঞা:

  • ভারিত সর্বোচ্চ-ন্যূনতম শেয়ার মূল্য: WMMSᵢ = min⟨A₁,...,Aₙ⟩∈Π(M) maxⱼ∈N Vᵢ(Aⱼ)·(wᵢ/wⱼ)
  • α-WMMS বিতরণ: সমস্ত এজেন্টের খরচ তাদের WMMS মূল্যের α গুণ অতিক্রম করে না

মডেল আর্কিটেকচার

1. প্রাক-প্রক্রিয়াকরণ পর্যায়

লেমা 4.1 (সাজানো কাজ সেটিং হ্রাস): যদি সাজানো কাজ সেটিংয়ে α-WMMS বিতরণের অস্তিত্ব নিশ্চিত করা যায়, তবে সাধারণ ক্ষেত্রেও α-WMMS বিতরণ বিদ্যমান।

লেমা 4.2 (অধিকার বিভাজ্যতা হ্রাস): যদি অধিকার বিভাজ্য সেটিংয়ে α-WMMS বিতরণের অস্তিত্ব নিশ্চিত করা যায়, তবে সাধারণ ক্ষেত্রে 2α-WMMS বিতরণ বিদ্যমান।

2. স্তরযুক্ত চলমান ছুরি অ্যালগরিদম

অ্যালগরিদম তিনটি এজেন্ট সেট বজায় রাখে:

  • মৃত এজেন্ট (D): ইতিমধ্যে বরাদ্দ সম্পন্ন এজেন্ট
  • চলমান এজেন্ট (P): বর্তমান রাউন্ডে অংশগ্রহণকারী এজেন্ট
  • সারি এজেন্ট (Q): বরাদ্দের জন্য অপেক্ষমান এজেন্ট

নিরাপত্তা ব্যবস্থা:

  • ∑aᵢ∈P wᵢ ≥ ∑aᵢ∈D wᵢ
  • m - s ≥ ∑ᵢ>minp wᵢ/wminp (যেখানে minp হল P-তে সর্বনিম্ন সূচক এজেন্ট)

মূল প্রক্রিয়া:

  1. bₘ থেকে b₁ পর্যন্ত ক্রমান্বয়ে কাজ বরাদ্দ করা
  2. P-তে প্রতিটি এজেন্ট aᵢ এর জন্য 2wᵢ/wminp সংখ্যক অনুলিপি তৈরি করে P' গঠন করা
  3. ছুরি ব্যবধান (ℓ,r) ব্যবহার করে, কোনো এজেন্টের খরচ ≤ 5wminp না হওয়া পর্যন্ত ব্যবধান সর্বাধিক প্রসারিত করা
  4. ব্যবধানের মধ্যে সমস্ত কাজ একটি শর্ত পূরণকারী এজেন্ট অনুলিপিতে বরাদ্দ করা
  5. P' খালি হলে, D, P, Q সেট আপডেট করা

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

  1. স্তরযুক্ত কাঠামো: তিন-স্তরীয় এজেন্ট কাঠামো বজায় রেখে অ্যালগরিদমের নিরাপত্তা এবং কার্যকারিতা নিশ্চিত করা
  2. অনুলিপি প্রক্রিয়া: প্রতিটি এজেন্টের জন্য একাধিক অনুলিপি তৈরি করে বিভিন্ন অধিকারের অধীনে বিতরণ ভারসাম্য রাখা
  3. চলমান ছুরি সম্প্রসারণ: ক্লাসিক্যাল চলমান ছুরি পদ্ধতিকে প্রতিসম থেকে অপ্রতিসম সেটিংয়ে প্রসারিত করা
  4. ক্রমবর্ধমান বরাদ্দ: একাধিক রাউন্ডের মাধ্যমে ক্রমান্বয়ে সমস্ত এজেন্ট প্রক্রিয়া করা

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

তাত্ত্বিক বিশ্লেষণ সেটআপ

এই পেপারটি প্রধানত তাত্ত্বিক বিশ্লেষণ পরিচালনা করে, পরীক্ষামূলক অংশ নিম্নলিখিতে কেন্দ্রীভূত:

  1. ছোট আকারের ক্ষেত্র বিশ্লেষণ: n=3,4 এর জন্য নির্ভুল সীমানা বিশ্লেষণ
  2. অভিজ্ঞতামূলক যাচাইকরণ: 3≤n≤10 এর ক্ষেত্রে, অধিকার সেটিংসের ১০ বিলিয়ন গ্রুপ র‍্যান্ডম নমুনা করে যাচাইকরণ
  3. তুলনামূলক মানদণ্ড: পূর্ববর্তী log n+1 উপরের সীমার সাথে তুলনা

মূল্যায়ন মেট্রিক্স

  • আনুমানিক অনুপাত: WMMS নিশ্চয়তার গুণক ফ্যাক্টর
  • প্রযোজ্য পরিসীমা: অ্যালগরিদম প্রযোজ্য এজেন্ট সংখ্যার পরিসীমা
  • তাত্ত্বিক নিশ্চয়তা: সর্বোচ্চ ক্ষেত্রে কর্মক্ষমতা নিশ্চয়তা

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

প্রধান ফলাফল

সেটিংপূর্ববর্তী কাজএই পেপারের ফলাফল
সাধারণ nlog n+120
n=2(√3+1)/2-
n=3-≈2.1122
n=4-≈2.5404

মূল উপপাদ্য

উপপাদ্য 4.5: অপ্রতিসম কাজ বরাদ্দ সমস্যায় 20-WMMS বিতরণ বিদ্যমান।

উপপাদ্য 5.4: তিনটি এজেন্টের জন্য, সর্বদা প্রায় 2.1122-WMMS বিতরণ বিদ্যমান।

উপপাদ্য 5.5: চারটি এজেন্টের জন্য, সর্বদা প্রায় 2.5404-WMMS বিতরণ বিদ্যমান।

পরীক্ষামূলক আবিষ্কার

  1. তাত্ত্বিক অগ্রগতি: প্রথমবারের মতো উপরের সীমা O(log n) থেকে ধ্রুবকে উন্নত করা
  2. ছোট আকারের অপ্টিমাইজেশন: n≤10 এর ক্ষেত্রে, কাজ-স্বাধীন কৌশল আরও ভাল সীমানা প্রদান করে
  3. বাস্তব থ্রেশহোল্ড: ধ্রুবক সীমা শুধুমাত্র n>2¹⁹=524288 এর সময় লগারিদমিক সীমার চেয়ে ভাল

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

প্রধান গবেষণা দিকনির্দেশনা

  1. ক্লাসিক্যাল ন্যায্য বিভাজন: 1948 সালে স্টেইনহাউসের কেক ভাগাভাগি সমস্যা থেকে শুরু
  2. অবিভাজ্য পণ্য বরাদ্দ: ক্রমাগত সম্পদ থেকে বিচ্ছিন্ন পণ্যের বরাদ্দে রূপান্তর
  3. MMS ধারণা: বুডিশ দ্বারা প্রস্তাবিত সর্বোচ্চ-ন্যূনতম শেয়ার ন্যায্যতার পরিমাপ হিসাবে

এই পেপারের সম্পর্কিত কাজের সাথে সম্পর্ক

  • আজিজ এবং অন্যরা 4: অসমান অধিকারের অধীনে কাজ বরাদ্দ প্রথম অধ্যয়ন করেছেন
  • ওয়াং এবং অন্যরা 27: O(log n)-WMMS উপরের সীমা স্থাপন করেছেন
  • হুয়াং এবং অন্যরা 23: ছোট আকারের ক্ষেত্রে নির্দিষ্ট সীমানা প্রদান করেছেন

প্রযুক্তিগত সুবিধা

বিদ্যমান কাজের তুলনায়, এই পেপারের সুবিধা হল:

  1. প্রথমবারের মতো ধ্রুবক আনুমানিক অনুপাত অর্জন করা
  2. একীভূত অ্যালগরিদম কাঠামো প্রদান করা
  3. ছোট আকারের ক্ষেত্রে আরও নির্ভুল বিশ্লেষণ প্রদান করা

উপসংহার এবং আলোচনা

প্রধান উপসংহার

  1. তাত্ত্বিক অবদান: অপ্রতিসম কাজ বরাদ্দে ধ্রুবক-WMMS নিশ্চয়তা বিদ্যমান প্রমাণ করা
  2. অ্যালগরিদম উদ্ভাবন: স্তরযুক্ত চলমান ছুরি অ্যালগরিদম অপ্রতিসম সেটিংয়ের প্রযুক্তিগত চ্যালেঞ্জ কার্যকরভাবে সমাধান করে
  3. ব্যবহারিক মূল্য: বাস্তব বিশ্বের অসমান অধিকার বরাদ্দ সমস্যার জন্য তাত্ত্বিক ভিত্তি প্রদান করে

সীমাবদ্ধতা

  1. ধ্রুবক ফ্যাক্টর: 20 এই ধ্রুবক তুলনামূলকভাবে বড়, বাস্তব প্রয়োগে যথেষ্ট নাও হতে পারে
  2. প্রযোজ্য থ্রেশহোল্ড: শুধুমাত্র এজেন্ট সংখ্যা অত্যন্ত বড় হলে পূর্ববর্তী লগারিদমিক সীমার চেয়ে ভাল
  3. অ্যালগরিদম জটিলতা: স্তরযুক্ত কাঠামো বাস্তবায়ন জটিলতা বৃদ্ধি করে, যা বাস্তব প্রয়োগকে প্রভাবিত করতে পারে

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

  1. ধ্রুবক অপ্টিমাইজেশন: আরও সূক্ষ্ম বিশ্লেষণের মাধ্যমে ধ্রুবক ফ্যাক্টর উন্নত করা
  2. নিম্ন সীমা গবেষণা: সমস্যার তাত্ত্বিক নিম্ন সীমা অন্বেষণ করা
  3. অ্যালগরিদম সরলীকরণ: ধ্রুবক নিশ্চয়তা অর্জনের জন্য আরও সহজ পদ্ধতি খোঁজা

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

শক্তি

  1. তাত্ত্বিক অগ্রগতি: লগারিদমিক থেকে ধ্রুবকে উন্নতি একটি প্রধান তাত্ত্বিক অগ্রগতি
  2. পদ্ধতি উদ্ভাবন: স্তরযুক্ত চলমান ছুরি অ্যালগরিদম সুচিন্তিত ডিজাইন, তাত্ত্বিক বিশ্লেষণ কঠোর
  3. সম্পূর্ণতা: সাধারণ ক্ষেত্র এবং ছোট আকারের বিশেষ ক্ষেত্র উভয়ই পরিচালনা করা
  4. লেখার স্পষ্টতা: পেপার কাঠামো স্পষ্ট, প্রমাণ বিস্তারিত এবং সম্পূর্ণ

দুর্বলতা

  1. ব্যবহারিক সীমাবদ্ধতা: ধ্রুবক 20 তুলনামূলকভাবে বড়, বাস্তব উন্নতি সীমিত
  2. প্রযোজ্য পরিসীমা: শুধুমাত্র অত্যন্ত বড় আকারে সুবিধা রয়েছে
  3. অ্যালগরিদম জটিলতা: বাস্তবায়ন তুলনামূলকভাবে জটিল, বাস্তব প্রয়োগকে প্রভাবিত করতে পারে

প্রভাব

  1. তাত্ত্বিক তাৎপর্য: ন্যায্য বরাদ্দ তত্ত্বে গুরুত্বপূর্ণ অবদান
  2. পদ্ধতি মূল্য: স্তরযুক্ত চলমান ছুরি কৌশল অন্যান্য সমস্যায় প্রযোজ্য হতে পারে
  3. গবেষণা প্রচার: পরবর্তী গবেষণার জন্য নতুন প্রযুক্তিগত সরঞ্জাম প্রদান করে

প্রযোজ্য পরিস্থিতি

  1. বড় আকারের সম্পদ বরাদ্দ: অত্যন্ত বড় সংখ্যক এজেন্টের পরিস্থিতিতে প্রযোজ্য
  2. তাত্ত্বিক গবেষণা: সম্পর্কিত তাত্ত্বিক গবেষণার জন্য ভিত্তি প্রদান করে
  3. অ্যালগরিদম ডিজাইন: স্তরযুক্ত কৌশল অন্যান্য বরাদ্দ সমস্যায় সাধারণীকৃত হতে পারে

সংদর্ভ

পেপারটি এই ক্ষেত্রের গুরুত্বপূর্ণ কাজ উদ্ধৃত করে, যার মধ্যে রয়েছে:

  1. বুডিশ (2011): MMS ধারণার প্রস্তাব
  2. আজিজ এবং অন্যরা (2019): অসমান অধিকার কাজ বরাদ্দের যুগান্তকারী কাজ
  3. ওয়াং এবং অন্যরা (2024): পূর্ববর্তী সেরা O(log n) ফলাফল
  4. হুয়াং এবং অন্যরা (2023): ছোট আকারের ক্ষেত্রে সীমানা বিশ্লেষণ

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