Truthful Fair Division with Stochastic Valuations
Abstract
We study no-money mechanisms for allocating indivisible items to strategic agents with additive preferences under a stochastic model: items' values are drawn from an underlying distribution and mechanisms are evaluated with respect to this draw (e.g., in expectation, or with high probability). Motivated by worst-case impossibilities, showing that truthfulness severely restricts fairness and efficiency, we ask whether truthful mechanisms continue to perform poorly on random instances.
We first focus on dominant-strategy incentive compatible (DSIC) mechanisms. For two agents, we obtain a tight picture: there exists a distribution under which no DSIC mechanism achieves an expected welfare approximation better than $\frac{2+\sqrt{2}}{4}\approx 0.854$, and give a DSIC mechanism that matches this bound for all distributions simultaneously. We further show that, for every distribution, there exists a DSIC mechanism that is envy-free with high probability and obtains the same welfare. A key ingredient is a new, tight connection between welfare guarantees of a family of DSIC, no-money mechanisms and i.i.d.\ prophet inequalities. This connection allows us to generalize to $n$ agents; in particular, we obtain a DSIC mechanism that achieves a $\approx 0.745$ approximation to welfare and another DSIC mechanism achieving a $1/2$-approximation welfare, that is envy-free with high probability.
We then turn to Bayesian incentive compatibility (BIC). Under i.i.d.\ valuations, we show that BIC comes at essentially no cost: we design a prior-independent BIC mechanism that achieves a $(1-\varepsilon)$-approximation to the optimal welfare, while being envy-free with high probability. Under independent but non-identical priors, we further obtain BIC mechanisms that are $(1-\varepsilon)$-approximately Pareto efficient and envy-free with high probability.
We first focus on dominant-strategy incentive compatible (DSIC) mechanisms. For two agents, we obtain a tight picture: there exists a distribution under which no DSIC mechanism achieves an expected welfare approximation better than $\frac{2+\sqrt{2}}{4}\approx 0.854$, and give a DSIC mechanism that matches this bound for all distributions simultaneously. We further show that, for every distribution, there exists a DSIC mechanism that is envy-free with high probability and obtains the same welfare. A key ingredient is a new, tight connection between welfare guarantees of a family of DSIC, no-money mechanisms and i.i.d.\ prophet inequalities. This connection allows us to generalize to $n$ agents; in particular, we obtain a DSIC mechanism that achieves a $\approx 0.745$ approximation to welfare and another DSIC mechanism achieving a $1/2$-approximation welfare, that is envy-free with high probability.
We then turn to Bayesian incentive compatibility (BIC). Under i.i.d.\ valuations, we show that BIC comes at essentially no cost: we design a prior-independent BIC mechanism that achieves a $(1-\varepsilon)$-approximation to the optimal welfare, while being envy-free with high probability. Under independent but non-identical priors, we further obtain BIC mechanisms that are $(1-\varepsilon)$-approximately Pareto efficient and envy-free with high probability.
