Fair and Almost Truthful Mechanisms for Additive Valuations and Beyond
摘要
We study the problem of fairly allocating indivisible goods among n strategic agents. It is well-known that truthfulness is incompatible with any meaningful fairness notions. We bypass the strong negative result by considering the concept of incentive ratio, a relaxation of truthfulness quantifying agents’ incentive to misreport. Previous studies show that Round-Robin, which satisfies envy-freeness up to one good (EF1), achieves an incentive ratio of 2 for additive valuations. In this paper, we explore the incentive ratio achievable by fair mechanisms for various classes of valuations besides additive ones. We first show that, for arbitrary \(\epsilon > 0\) , every \((\frac{1}{2} + \epsilon )\) -EF1 mechanism for additive valuations admits an incentive ratio of at least 1.5. Then, using the above lower bound for additive valuations in a black-box manner, we show that for arbitrary \(\epsilon > 0\) , every \(\epsilon \) -EF1 mechanism for cancelable valuations admits an infinite incentive ratio. Moreover, for subadditive cancelable valuations, we show that Round-Robin, which satisfies EF1, achieves an incentive ratio of 2, and every \((\varphi - 1)\) -EF1 mechanism admits an incentive ratio of at least \(\varphi \) with \(\varphi = (1 + \sqrt{5}) / 2 \approx 1.618\) . Finally, for submodular valuations, we show that Round-Robin, which satisfies \(\frac{1}{2}\) -EF1, admits an incentive ratio of n.