Truthful and Almost Envy-Free Mechanism of Allocating Indivisible Goods: the Power of Randomness
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915654788972544 |
|---|---|
| author | Bu, Xiaolin Tao, Biaoshuai |
| author_facet | Bu, Xiaolin Tao, Biaoshuai |
| contents | We study the problem of fairly and truthfully allocating $m$ indivisible items to $n$ agents with additive preferences. Specifically, we consider truthful mechanisms outputting allocations that satisfy EF$^{+u}_{-v}$, where, in an EF$^{+u}_{-v}$ allocation, for any pair of agents $i$ and $j$, agent $i$ will not envy agent $j$ if $u$ items were added to $i$'s bundle and $v$ items were removed from $j$'s bundle. Previous work easily indicates that, when restricted to deterministic mechanisms, truthfulness will lead to a poor guarantee of fairness: even with two agents, for any $u$ and $v$, EF$^{+u}_{-v}$ cannot be guaranteed by truthful mechanisms when the number of items is large enough. In this work, we focus on randomized mechanisms, where we consider ex-ante truthfulness and ex-post fairness. For two agents, we present a truthful mechanism that achieves EF$^{+0}_{-1}$ (i.e., the well-studied fairness notion EF$1$). For three agents, we present a truthful mechanism that achieves EF$^{+1}_{-1}$. For $n$ agents in general, we show that there exists a truthful mechanism that achieves EF$^{+0}_{-O(\sqrt{n})}$. On the negative side, when considering the stronger notion EF$_{-v}^{+u}$X, we show that it cannot be achieved by any randomized truthful mechanism for any $u, v$, and any fixed number of agents.
We further consider fair and truthful mechanisms that also satisfy the standard efficiency guarantee: Pareto-optimality. We provide a mechanism that simultaneously achieves truthfulness, EF$1$, and Pareto-optimality for bi-valued utilities (where agents' valuation on each item is either $p$ or $q$ for some $p>q\geq0$). For tri-valued utilities (where agents' valuations on each item belong to $\{p,q,r\}$ for some $p>q>r\geq0$) and any $u,v$, we show that truthfulness is incompatible with EF$^{+u}_{-v}$ and Pareto-optimality even for two agents. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_13634 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Truthful and Almost Envy-Free Mechanism of Allocating Indivisible Goods: the Power of Randomness Bu, Xiaolin Tao, Biaoshuai Computer Science and Game Theory We study the problem of fairly and truthfully allocating $m$ indivisible items to $n$ agents with additive preferences. Specifically, we consider truthful mechanisms outputting allocations that satisfy EF$^{+u}_{-v}$, where, in an EF$^{+u}_{-v}$ allocation, for any pair of agents $i$ and $j$, agent $i$ will not envy agent $j$ if $u$ items were added to $i$'s bundle and $v$ items were removed from $j$'s bundle. Previous work easily indicates that, when restricted to deterministic mechanisms, truthfulness will lead to a poor guarantee of fairness: even with two agents, for any $u$ and $v$, EF$^{+u}_{-v}$ cannot be guaranteed by truthful mechanisms when the number of items is large enough. In this work, we focus on randomized mechanisms, where we consider ex-ante truthfulness and ex-post fairness. For two agents, we present a truthful mechanism that achieves EF$^{+0}_{-1}$ (i.e., the well-studied fairness notion EF$1$). For three agents, we present a truthful mechanism that achieves EF$^{+1}_{-1}$. For $n$ agents in general, we show that there exists a truthful mechanism that achieves EF$^{+0}_{-O(\sqrt{n})}$. On the negative side, when considering the stronger notion EF$_{-v}^{+u}$X, we show that it cannot be achieved by any randomized truthful mechanism for any $u, v$, and any fixed number of agents. We further consider fair and truthful mechanisms that also satisfy the standard efficiency guarantee: Pareto-optimality. We provide a mechanism that simultaneously achieves truthfulness, EF$1$, and Pareto-optimality for bi-valued utilities (where agents' valuation on each item is either $p$ or $q$ for some $p>q\geq0$). For tri-valued utilities (where agents' valuations on each item belong to $\{p,q,r\}$ for some $p>q>r\geq0$) and any $u,v$, we show that truthfulness is incompatible with EF$^{+u}_{-v}$ and Pareto-optimality even for two agents. |
| title | Truthful and Almost Envy-Free Mechanism of Allocating Indivisible Goods: the Power of Randomness |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2407.13634 |