Home Round-Robin Beyond Additive Agents: Existence and Fairness of Approximate Equilibria
Post
Cancel

Round-Robin Beyond Additive Agents: Existence and Fairness of Approximate Equilibria

(or how to be fair to deceptive egoists.)

When allocating indivisible goods to a number of selfish agents, both fairness and truthfulness are main concerns: the allocation should guarantee everyone a sense of fair treatment, while also incentivizing people to report their true, private preferences. Both are challenging goals, and together, there are strong results showing that achieving them is usually impossible.

Following previous work for agents with additive valuation functions, we demonstrate how to use variants of a very simple round-robin routine to get close to the above, impossible ideal: surprisingly, we show the existence of (approximate) equilibria for agents with complex, (up to) submodular valuation functions that exhibit fairness guarantees with respect to the true valuations of agents, although they might misreport those to the mechanism.

This post is licensed under CC BY 4.0 by the author.