Conference proceeding
Getting More by Knowing Less: Bayesian Incentive Compatible Mechanisms for Fair Division
PROCEEDINGS OF THE THIRTY-THIRD INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, IJCAI 2024, pp.2807-2815
01 Jan 2024
Abstract
We study fair resource allocation with strategic agents. It is well-known that, across multiple fundamental problems in this domain, truthfulness and fairness are incompatible. For example, when allocating indivisible goods, no truthful and deterministic mechanism can guarantee envy-freeness up to one item (EF1), even for two agents with additive valuations. Or, in cake-cutting, no truthful and deterministic mechanism always outputs a proportional allocation, even for two agents with piecewise constant valuations. Our work stems from the observation that, in the context of fair division, truthfulness is used as a synonym for Dominant Strategy Incentive Compatibility (DSIC), requiring that an agent prefers reporting the truth, no matter what other agents report. In this paper, we instead focus on Bayesian Incentive Compatible (BIC) mechanisms, requiring that agents are better off reporting the truth in expectation over other agents' reports. We prove that, when agents know a bit less about each other, a lot more is possible: BIC mechanisms can guarantee fairness notions that are unattainable by DSIC mechanisms in both the fundamental problems of allocation of indivisible goods and cake-cutting. We prove that this is the case even for an arbitrary number of agents, as long as the agents' priors about each others' types satisfy a neutrality condition. Notably, for the case of indivisible goods, we significantly strengthen the state-of-the-art negative result for efficient DSIC mechanisms, while also highlighting the limitations of BIC mechanisms, by showing that a very general class of welfare objectives is incompatible with Bayesian Incentive Compatibility. Combined these results give a nearcomplete picture of the power and limitations of BIC and DSIC mechanisms for the problem of allocating indivisible goods.
Metrics
1 Record Views
Details
- Title
- Getting More by Knowing Less: Bayesian Incentive Compatible Mechanisms for Fair Division
- Creators
- Vasilis Gkatzelis - Drexel UniversityAlexandros Psomas - Purdue Univ, Dept Comp Sci, W Lafayette, IN USAXizhi Tan - Drexel UniversityParitosh Verma - Purdue Univ, Dept Comp Sci, W Lafayette, IN USA
- Contributors
- K Larson (Editor)
- Publication Details
- PROCEEDINGS OF THE THIRTY-THIRD INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, IJCAI 2024, pp.2807-2815
- Number of pages
- 9
- Grant note
- Google AI for Social Good award CCF-2144208; CCF-2047907 / NSF CAREER award; National Science Foundation (NSF); NSF - Office of the Director (OD) Google Research Scholar Award
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Computer Science (Computing)
- Identifiers
- 991022035264404721