Distribution of Chores with Information Asymmetry
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908364858982400 |
|---|---|
| author | Hosseini, Hadi Kavner, Joshua Wąs, Tomasz Xia, Lirong |
| author_facet | Hosseini, Hadi Kavner, Joshua Wąs, Tomasz Xia, Lirong |
| contents | A well-regarded fairness notion when dividing indivisible chores is envy-freeness up to one item (EF1), which requires that pairwise envy can be eliminated by the removal of a single item. While an EF1 and Pareto optimal (PO) allocation of goods can always be found via well-known algorithms, even the existence of such solutions for chores remains open, to date. We take an epistemic approach utilizing information asymmetry by introducing dubious chores--items that inflict no cost on receiving agents but are perceived costly by others. On a technical level, dubious chores provide a more fine-grained approximation of envy-freeness than EF1. We show that finding allocations with minimal number of dubious chores is computationally hard. Nonetheless, we prove the existence of envy-free and fractional PO allocations for $n$ agents with only $2n-2$ dubious chores and strengthen it to $n-1$ dubious chores in four special classes of valuations. Our experimental analysis demonstrates that often only a few dubious chores are needed to achieve envy-freeness. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_02986 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Distribution of Chores with Information Asymmetry Hosseini, Hadi Kavner, Joshua Wąs, Tomasz Xia, Lirong Computer Science and Game Theory A well-regarded fairness notion when dividing indivisible chores is envy-freeness up to one item (EF1), which requires that pairwise envy can be eliminated by the removal of a single item. While an EF1 and Pareto optimal (PO) allocation of goods can always be found via well-known algorithms, even the existence of such solutions for chores remains open, to date. We take an epistemic approach utilizing information asymmetry by introducing dubious chores--items that inflict no cost on receiving agents but are perceived costly by others. On a technical level, dubious chores provide a more fine-grained approximation of envy-freeness than EF1. We show that finding allocations with minimal number of dubious chores is computationally hard. Nonetheless, we prove the existence of envy-free and fractional PO allocations for $n$ agents with only $2n-2$ dubious chores and strengthen it to $n-1$ dubious chores in four special classes of valuations. Our experimental analysis demonstrates that often only a few dubious chores are needed to achieve envy-freeness. |
| title | Distribution of Chores with Information Asymmetry |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2305.02986 |