Fair and Efficient Completion of Indivisible Goods
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929647507210240 |
|---|---|
| author | HV, Vishwa Prakash Igarashi, Ayumi Vaish, Rohit |
| author_facet | HV, Vishwa Prakash Igarashi, Ayumi Vaish, Rohit |
| contents | We formulate the problem of fair and efficient completion of indivisible goods, defined as follows: Given a partial allocation of indivisible goods among agents, does there exist an allocation of the remaining goods (i.e., a completion) that satisfies fairness and economic efficiency guarantees of interest? We study the computational complexity of the completion problem for prominent fairness and efficiency notions such as envy-freeness up one good (EF1), proportionality up to one good (Prop1), maximin share (MMS), and Pareto optimality (PO), and focus on the class of additive valuations as well as its subclasses such as binary additive and lexicographic valuations. We find that while the completion problem is significantly harder than the standard fair division problem (wherein the initial partial allocation is empty), the consideration of restricted preferences facilitates positive algorithmic results for threshold-based fairness notions (Prop1 and MMS). On the other hand, the completion problem remains computationally intractable for envy-based notions such as EF1 and EF1+PO even under restricted preferences. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_09468 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fair and Efficient Completion of Indivisible Goods HV, Vishwa Prakash Igarashi, Ayumi Vaish, Rohit Computer Science and Game Theory We formulate the problem of fair and efficient completion of indivisible goods, defined as follows: Given a partial allocation of indivisible goods among agents, does there exist an allocation of the remaining goods (i.e., a completion) that satisfies fairness and economic efficiency guarantees of interest? We study the computational complexity of the completion problem for prominent fairness and efficiency notions such as envy-freeness up one good (EF1), proportionality up to one good (Prop1), maximin share (MMS), and Pareto optimality (PO), and focus on the class of additive valuations as well as its subclasses such as binary additive and lexicographic valuations. We find that while the completion problem is significantly harder than the standard fair division problem (wherein the initial partial allocation is empty), the consideration of restricted preferences facilitates positive algorithmic results for threshold-based fairness notions (Prop1 and MMS). On the other hand, the completion problem remains computationally intractable for envy-based notions such as EF1 and EF1+PO even under restricted preferences. |
| title | Fair and Efficient Completion of Indivisible Goods |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2406.09468 |