2025-11-17T18:43:12.758371

Fair and Efficient Allocation of Indivisible Mixed Manna

Barman, HV, Sethia et al.

We study fair division of indivisible mixed manna (items whose values may be positive, negative, or zero) among agents with additive valuations. Here, we establish that fairness -- in terms of a relaxation of envy-freeness -- and Pareto efficiency can always be achieved together. Specifically, our fairness guarantees are in terms of envy-freeness up to $k$ reallocations (EFR-$k$): An allocation $A$ of the indivisible items is said to be EFR-$k$ if there exists a subset $R$ of at most $k$ items such that, for each agent $i$, we can reassign items from within $R$ (in $A$) and obtain an allocation, $A^i$, which is envy-free for $i$. We establish that, when allocating mixed manna among $n$ agents with additive valuations, an EFR-$(n-1)$ and Pareto optimal (PO) allocation $A$ always exists. Further, the individual envy-free allocations $A^i$, induced by reassignments, are also PO. In addition, we prove that such fair and efficient allocations are efficiently computable when the number of agents, $n$, is fixed. We also obtain positive results focusing on EFR by itself (and without the PO desideratum). Specifically, we show that an EFR-$(n-1)$ allocation of mixed manna can be computed in polynomial time. In addition, we prove that when all the items are goods, an EFR-${\lfloor n/2 \rfloor}$ allocation exists and can be computed efficiently. Here, the $(n-1)$ bound is tight for chores and $\lfloor n/2 \rfloor$ is tight for goods. Our results advance the understanding of fair and efficient allocation of indivisible mixed manna and rely on a novel application of the Knaster-Kuratowski-Mazurkiewicz (KKM) Theorem in discrete fair division. We utilize weighted welfare maximization, with perturbed valuations, to achieve Pareto efficiency, and overall, our techniques are notably different from existing market-based approaches.

academic

অবিভাজ্য মিশ্র মান্নার ন্যায্য এবং দক্ষ বরাদ্দ

মৌলিক তথ্য

পেপার আইডি: 2507.03946
শিরোনাম: অবিভাজ্য মিশ্র মান্নার ন্যায্য এবং দক্ষ বরাদ্দ
লেখক: সিদ্ধার্থ বর্মন (ভারতীয় বিজ্ঞান প্রতিষ্ঠান), বিশ্ব প্রকাশ এইচভি (চেন্নাই গণিত প্রতিষ্ঠান), অদিতি সেঠিয়া (ভারতীয় বিজ্ঞান প্রতিষ্ঠান), মাশবাত সুজুকি (UNSW সিডনি)
শ্রেণীবিভাগ: cs.GT (কম্পিউটার বিজ্ঞান - গেম তত্ত্ব)
প্রকাশনার সময়: ২০২৫ সালের অক্টোবর ১৫ (arXiv প্রাক-প্রিন্ট দ্বিতীয় সংস্করণ)
পেপার লিঙ্ক: https://arxiv.org/abs/2507.03946v2

সারসংক্ষেপ

এই পেপারটি সংযোজনীয় মূল্যায়ন সহ বুদ্ধিমান এজেন্টদের মধ্যে অবিভাজ্য মিশ্র মান্নার (mixed manna) ন্যায্য বরাদ্দ সমস্যা অধ্যয়ন করে। মিশ্র মান্না হল এমন পণ্য যার মূল্য ইতিবাচক, নেতিবাচক বা শূন্য হতে পারে। পেপারটি ন্যায্যতা (ঈর্ষামুক্ততার শিথিলকরণের উপর ভিত্তি করে) এবং পারেটো দক্ষতা একযোগে অর্জনযোগ্য তা প্রমাণ করে। নির্দিষ্টভাবে, ন্যায্যতার নিশ্চয়তা "k-বার পুনর্বন্টনের ঈর্ষামুক্ততা" (EFR-k) ধারণার উপর ভিত্তি করে: যদি সর্বাধিক k টি পণ্যের একটি উপসেট R বিদ্যমান থাকে যাতে প্রতিটি এজেন্ট i এর জন্য, R-তে পণ্যগুলি পুনর্বন্টনের মাধ্যমে i এর জন্য ঈর্ষামুক্ত বরাদ্দ A^i প্রাপ্ত করা যায়, তবে বরাদ্দ A হল EFR-k।

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

সমস্যা সংজ্ঞা

ন্যায্য বরাদ্দ একটি সমস্যা যা সম্পত্তি বিভাজন, কাজ বরাদ্দ, সীমানা বিরোধ এবং ঋণ বরাদ্দের মতো বাস্তব পরিস্থিতিতে ঘন ঘন দেখা যায়। যখন অংশগ্রহণকারী এজেন্টদের ব্যক্তিগত পছন্দ থাকে, তখন "কে কী পায়" প্রশ্নটি ব্যবহারিক জরুরিতা এবং তাত্ত্বিক সমৃদ্ধি উভয়ই রাখে।

গবেষণা চ্যালেঞ্জ

মিশ্র মান্নার জটিলতা: বিশুদ্ধ পণ্য (goods) বা কাজ (chores) এর বিপরীতে, মিশ্র মান্নায় পণ্যের মূল্যের চিহ্ন এজেন্ট অনুযায়ী পরিবর্তিত হতে পারে, যা বরাদ্দকে আরও জটিল করে তোলে।
ন্যায্যতা এবং দক্ষতার মধ্যে ভারসাম্য: অবিভাজ্য পণ্যের সেটিংয়ে, ঐতিহ্যবাহী ঈর্ষামুক্ততা (envy-freeness) অস্তিত্ব নিশ্চিত করতে পারে না, উপযুক্ত শিথিলকরণ শর্ত খুঁজে বের করার প্রয়োজন।
বিদ্যমান পদ্ধতির সীমাবদ্ধতা:
- কাজ বরাদ্দের জন্য, এমনকি চারটি এজেন্টের ক্ষেত্রেও EF1 এবং পারেটো সর্বোত্তম বরাদ্দের অস্তিত্ব এখনও অমীমাংসিত
- মিশ্র মান্নার জন্য, এই সমস্যাটি এমনকি তিনটি এজেন্টের ক্ষেত্রেও খোলা রয়েছে
- বিদ্যমান বাজার-ভিত্তিক পদ্ধতিগুলি নেতিবাচক মূল্যায়নে সরাসরি সম্প্রসারিত হতে পারে না

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

পেপারটির লক্ষ্য EFR-k ধারণা প্রবর্তনের মাধ্যমে মিশ্র মান্নার ন্যায্য উচ্চ-দক্ষ বরাদ্দের জন্য তাত্ত্বিক নিশ্চয়তা প্রদান করা এবং কার্যকর গণনামূলক অ্যালগরিদম বিকাশ করা।

মূল অবদান

তাত্ত্বিক অস্তিত্ব নিশ্চয়তা: প্রমাণ করে যে সংযোজনীয় মূল্যায়ন সহ n এজেন্টের মিশ্র মান্না বরাদ্দের জন্য, সর্বদা EFR-(n-1) এবং পারেটো সর্বোত্তম বরাদ্দ বিদ্যমান।
অ্যালগরিদমিক গণনাযোগ্যতা: যখন এজেন্টের সংখ্যা n নির্দিষ্ট থাকে, বহুপদী সময়ে EFR-(n-1) এবং পারেটো সর্বোত্তম বরাদ্দ গণনা করা যায়।
স্বাধীন EFR ফলাফল:
- EFR-(n-1) মিশ্র মান্না বরাদ্দ বহুপদী সময়ে গণনা করা যায়
- যখন সমস্ত পণ্য পণ্য হয়, EFR-⌊n/2⌋ বরাদ্দ বিদ্যমান এবং দক্ষতার সাথে গণনা করা যায়
কঠোরতা ফলাফল:
- কাজের জন্য, (n-1) সীমা কঠোর
- পণ্যের জন্য, ⌊n/2⌋ সীমা কঠোর
প্রযুক্তিগত উদ্ভাবন: বিচ্ছিন্ন ন্যায্য বরাদ্দে Knaster-Kuratowski-Mazurkiewicz (KKM) উপপাদ্যের প্রথম প্রয়োগ।

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

কাজের সংজ্ঞা

ইনপুট:

n এজেন্ট, n = {1,...,n} হিসাবে চিহ্নিত
m অবিভাজ্য পণ্য, m = {1,...,m} হিসাবে চিহ্নিত
সংযোজনীয় মূল্যায়ন ফাংশন {vi}i∈n, যেখানে vi(t) ∈ ℝ এজেন্ট i এর পণ্য t এর মূল্যায়ন প্রতিনিধিত্ব করে

আউটপুট: বরাদ্দ A = (A1,...,An), যেখানে Ai ⊆ m এজেন্ট i এর বরাদ্দকৃত পণ্যের সেট

উদ্দেশ্য: একযোগে EFR-k এবং পারেটো সর্বোত্তম সন্তুষ্ট করে এমন বরাদ্দ খুঁজে পাওয়া

মূল ধারণা

EFR-k সংজ্ঞা

বরাদ্দ A হল EFR-k, যদি এবং শুধুমাত্র যদি সর্বাধিক k আকারের উপসেট R ⊆ m বিদ্যমান থাকে, যাতে প্রতিটি এজেন্ট i এর জন্য, R-তে পণ্যগুলি পুনর্বন্টনের মাধ্যমে i এর জন্য ঈর্ষামুক্ত বরাদ্দ A^i প্রাপ্ত করা যায়।

মূল প্রযুক্তিগত উপাদান

মূল্যায়ন বিঘ্ন: অ-অবক্ষয়ী শর্ত পেতে, প্রদত্ত মূল্যায়নে যথেষ্ট ছোট সংযোজনীয় বিঘ্ন যোগ করুন:
```
v̄i(t) = vi(t) - εi,t
```
যেখানে εi,t (0,ε) থেকে সমানভাবে র্যান্ডমভাবে নির্বাচিত।
ওজন অফসেট: প্রতিটি ওজন ভেক্টর w ∈ Δn-1 এর জন্য, প্রতিটি উপাদান অফসেট প্যারামিটার η > 0:
```
SWη(A,w) := Σi∈[n] (wi + η)v̄i(Ai)
```

KKM কভারেজ: প্রতিটি এজেন্ট i এর জন্য, সেট সংজ্ঞায়িত করুন

Ci := {w ∈ Δn-1 : বিদ্যমান বরাদ্দ Xi ∈ Oη(w) যাতে i Xi এর অধীনে ঈর্ষামুক্ত}

প্রধান অ্যালগরিদম কাঠামো

উপপাদ্য 3.1 এর প্রমাণ কৌশল

বিঘ্নিত মূল্যায়ন নির্মাণ: অ-অবক্ষয়ী বৈশিষ্ট্য নিশ্চিত করুন
KKM কভারেজ সংজ্ঞায়িত করুন: KKM শর্ত সন্তুষ্ট করে এমন বন্ধ সেট পরিবার {Ci} নির্মাণ করুন
KKM উপপাদ্য প্রয়োগ করুন: ছেদ w* ∈ ∩i Ci প্রাপ্ত করুন
গণনা যুক্তি: প্রমাণ করুন যে পুনর্বন্টন সেট R এর আকার সর্বাধিক n-1

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

বিশুদ্ধ পণ্যের ক্ষেত্রে, রাউন্ড-রবিন-ভিত্তিক অ্যালগরিদম ডিজাইন করা হয়েছে:

দ্বন্দ্ব সমাধান পর্যায়: একাধিক এজেন্টের সবচেয়ে পছন্দের একই পণ্য চিহ্নিত করুন, এটি পুনর্বন্টন সেট R-তে যোগ করুন
নির্বাচন পর্যায়: সক্রিয় এজেন্টরা শব্দকোষ ক্রমে সবচেয়ে পছন্দের পণ্য নির্বাচন করুন

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

KKM উপপাদ্যের নতুন প্রয়োগ: প্রথমবারের মতো ক্লাসিক্যাল KKM উপপাদ্য বিচ্ছিন্ন ন্যায্য বরাদ্দ সমস্যায় প্রয়োগ করা হয়েছে, বিদ্যমান বাজার-ভিত্তিক পদ্ধতি থেকে সম্পূর্ণ ভিন্ন প্রযুক্তিগত পথ প্রদান করে।
বিঘ্ন কৌশল: সাবধানে ডিজাইন করা মূল্যায়ন বিঘ্নের মাধ্যমে অ-অবক্ষয়ী নিশ্চিত করুন, যাতে ওজনযুক্ত সামাজিক কল্যাণ সর্বাধিকীকরণ সমস্যা ভাল বৈশিষ্ট্য রাখে।
গণনা যুক্তি: দ্বিপক্ষীয় গ্রাফের অ-চক্রীয় বৈশিষ্ট্য ব্যবহার করে পুনর্বন্টন সেটের আকার সীমা প্রমাণ করুন।

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

তাত্ত্বিক বিশ্লেষণ কাঠামো

যেহেতু এটি একটি তাত্ত্বিক পেপার, ফলাফলগুলি প্রধানত অভিজ্ঞতামূলক পরীক্ষার পরিবর্তে গাণিতিক প্রমাণের মাধ্যমে যাচাই করা হয়। পেপারটি নিম্নলিখিত বিশ্লেষণ কাঠামো গ্রহণ করে:

অস্তিত্ব প্রমাণ: KKM উপপাদ্য ব্যবহার করে EFR-(n-1) এবং PO বরাদ্দের অস্তিত্ব প্রমাণ করুন
কঠোরতা বিশ্লেষণ: প্রতিউদাহরণ নির্মাণ করে সীমার কঠোরতা প্রমাণ করুন
অ্যালগরিদম জটিলতা: অ্যালগরিদমের সময় জটিলতা বিশ্লেষণ করুন

জটিলতা বিশ্লেষণ

নির্দিষ্ট এজেন্ট: EFR-(n-1) এবং PO বরাদ্দ m^poly(n) সময়ে গণনা করা যায়
সাধারণ ক্ষেত্র: EFR-(n-1) বরাদ্দ বহুপদী সময়ে গণনা করা যায়
পণ্য ক্ষেত্র: EFR-⌊n/2⌋ বরাদ্দ বহুপদী সময়ে গণনা করা যায়

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

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

উপপাদ্য 3.1 (প্রধান অস্তিত্ব ফলাফল)

অবিভাজ্য মিশ্র মান্না এবং সংযোজনীয় মূল্যায়ন সহ প্রতিটি ন্যায্য বরাদ্দ উদাহরণে EFR-(n-1) এবং পারেটো সর্বোত্তম বরাদ্দ বিদ্যমান।

উপপাদ্য 4.1 (গণনাযোগ্যতা ফলাফল)

নির্দিষ্ট সংখ্যক এজেন্টের মিশ্র মান্না বরাদ্দ উদাহরণের জন্য, বহুপদী সময়ে EFR-(n-1) এবং পারেটো সর্বোত্তম বরাদ্দ গণনা করা যায়।

উপপাদ্য 5.1 (EFR স্বাধীন ফলাফল)

মিশ্র মান্না এবং সংযোজনীয় মূল্যায়ন সহ ন্যায্য বরাদ্দ উদাহরণের জন্য, সর্বদা EFR-(n-1) এবং EF1 উভয়ই এমন বরাদ্দ বিদ্যমান, এবং বহুপদী সময়ে গণনা করা যায়।

উপপাদ্য 5.4 (পণ্যের উন্নত সীমা)

বিশুদ্ধ পণ্যের ন্যায্য বরাদ্দ উদাহরণের জন্য, অ্যালগরিদম 1 বহুপদী সময়ে EFR-⌊n/2⌋ বরাদ্দ গণনা করে।

কঠোরতা ফলাফল

উপপাদ্য 5.2 (কাজের কঠোরতা)

কাজ বরাদ্দ উদাহরণ বিদ্যমান যা EFR-(n-2) বরাদ্দ নেই, প্রমাণ করে (n-1) সীমা কঠোর।

উপপাদ্য 5.5 (পণ্যের কঠোরতা)

পণ্য বরাদ্দ উদাহরণ বিদ্যমান যা EFR-(⌊n/2⌋-1) বরাদ্দ নেই, প্রমাণ করে ⌊n/2⌋ সীমা কঠোর।

গণনামূলক জটিলতা ফলাফল

উপপাদ্য A.1 (সিদ্ধান্ত সমস্যার জটিলতা)

প্রদত্ত বরাদ্দ A এবং ধনাত্মক পূর্ণসংখ্যা k < n-2, A হল EFR-k কিনা তা সিদ্ধান্ত করা NP-সম্পূর্ণ।

তাত্ত্বিক অগ্রগতি: সাধারণ মিশ্র মান্না সেটিংয়ের জন্য প্রথমবারের মতো ন্যায্যতা এবং দক্ষতার একযোগে নিশ্চয়তা প্রদান করে
প্রযুক্তিগত উদ্ভাবন: বিচ্ছিন্ন ন্যায্য বরাদ্দে KKM উপপাদ্যের নতুন প্রয়োগ নতুন গবেষণা দিকনির্দেশনা খুলে দেয়
ব্যবহারিক মূল্য: অ্যালগরিদম ফলাফল বাস্তব প্রয়োগের জন্য গণনামূলক ভিত্তি প্রদান করে

সীমাবদ্ধতা

সীমা: EFR-(n-1) এর সীমা তুলনামূলকভাবে বড়, গড়ে প্রতিটি এজেন্ট প্রায় 2টি পণ্য পুনর্বন্টন করতে হবে
নির্দিষ্ট এজেন্ট অনুমান: বহুপদী সময় অ্যালগরিদমের জন্য এজেন্টের সংখ্যা নির্দিষ্ট থাকা প্রয়োজন
সংযোজনীয় মূল্যায়ন সীমাবদ্ধতা: ফলাফল শুধুমাত্র সংযোজনীয় মূল্যায়ন ফাংশনের জন্য প্রযোজ্য

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

সীমা উন্নতি: ছোট পুনর্বন্টন সেট R খুঁজে পাওয়া
মূল্যায়ন প্রকার সম্প্রসারণ: অ-সংযোজনীয় মূল্যায়ন ফাংশন বিবেচনা করুন
ব্যবহারিক প্রয়োগ: তাত্ত্বিক ফলাফল নির্দিষ্ট বরাদ্দ পরিস্থিতিতে প্রয়োগ করুন

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

সুবিধা

উল্লেখযোগ্য তাত্ত্বিক অবদান: মিশ্র মান্নার ন্যায্য উচ্চ-দক্ষ বরাদ্দের মৌলিক সমস্যা সমাধান করে
উদ্ভাবনী প্রযুক্তিগত পদ্ধতি: KKM উপপাদ্যের প্রয়োগ গভীর গাণিতিক অন্তর্দৃষ্টি প্রদর্শন করে
ব্যাপক ফলাফল: অস্তিত্ব এবং অ্যালগরিদম উভয়ই, উপরের এবং নিচের সীমা উভয়ই রয়েছে
কঠোর প্রমাণ: সম্পূর্ণ গাণিতিক অনুমান, প্রযুক্তিগত বিবরণ যথাযথভাবে পরিচালিত

অপূর্ণতা

সীমিত ব্যবহারিকতা: EFR-(n-1) এর সীমা বাস্তব প্রয়োগে অত্যধিক হতে পারে
অভিজ্ঞতামূলক মূল্যায়ন অনুপস্থিত: তাত্ত্বিক পেপার হিসাবে, বাস্তব ডেটায় কর্মক্ষমতা মূল্যায়ন অনুপস্থিত
অ্যালগরিদম দক্ষতা: নির্দিষ্ট এজেন্টের সময় m^poly(n) জটিলতা ব্যবহারিকভাবে উচ্চ হতে পারে

প্রভাব

একাডেমিক প্রভাব: ন্যায্য বরাদ্দ তত্ত্বে গুরুত্বপূর্ণ অবদান, ব্যাপকভাবে উদ্ধৃত হওয়ার প্রত্যাশা
পদ্ধতিগত মূল্য: KKM উপপাদ্যের প্রয়োগ আরও সম্পর্কিত গবেষণা অনুপ্রাণিত করতে পারে
ব্যবহারিক সম্ভাবনা: বাস্তব বরাদ্দ সিস্টেম ডিজাইনের জন্য তাত্ত্বিক ভিত্তি প্রদান করে

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

উত্তরাধিকার বিভাজন: সম্পদ এবং ঋণ অন্তর্ভুক্ত জটিল বিভাজন পরিস্থিতি
কাজ বরাদ্দ: আকর্ষণীয় এবং অনাকর্ষণীয় কাজ উভয়ই অন্তর্ভুক্ত বরাদ্দ
সম্পদ ব্যবস্থাপনা: আয় এবং খরচ উভয়ই বিবেচনা করতে হয় এমন সম্পদ বরাদ্দ সমস্যা

তথ্যসূত্র

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

Budish (2011): EF1 ধারণার প্রবর্তন
Caragiannis et al. (2019): ন্যাশ সামাজিক কল্যাণ এবং EF1+PO এর সম্পর্ক
Aziz et al. (2022): মিশ্র মান্নার EF1 অস্তিত্ব
Sandomirskiy & Segal-Halevi (2022): ভগ্নাংশ বরাদ্দের সম্পর্কিত ফলাফল

সামগ্রিক মূল্যায়ন: এটি একটি উচ্চ-মানের তাত্ত্বিক পেপার যা EFR ধারণা প্রবর্তন এবং KKM উপপাদ্য প্রয়োগের মাধ্যমে মিশ্র মান্নার ন্যায্য উচ্চ-দক্ষ বরাদ্দের জন্য গুরুত্বপূর্ণ তাত্ত্বিক নিশ্চয়তা প্রদান করে। যদিও ব্যবহারিক দিক থেকে নির্দিষ্ট সীমাবদ্ধতা রয়েছে, তবে এর তাত্ত্বিক অবদান এবং প্রযুক্তিগত উদ্ভাবন এটিকে ন্যায্য বরাদ্দ ক্ষেত্রের একটি গুরুত্বপূর্ণ অগ্রগতি করে তোলে।