5. Randomized strategyproof mechanisms with best of both worlds fairness and efficiency
Invited abstract in session FD-1: Fairness, stream Fairness.
Friday, 15:30 - 17:00Room: L226
Authors (first author is the speaker)
| 1. | Bo Chen
|
| Warwick Business School, University of Warwick | |
| 2. | Ankang Sun
|
| University of Warwick |
Abstract
We study the problem of mechanism design for allocating a set of indivisible items among agents with private preferences on items. We are interested in such a mechanism that is strategyproof (where agents’ best strategy is to report their true preferences) and is expected to ensure fairness and efficiency to a certain degree. We first present an impossibility result that a deterministic mechanism does not exist that is strategyproof, fair and efficient for allocating indivisible chores. We then utilize randomness to overcome the strong impossibility. For allocating indivisible chores, we propose a randomized mechanism that is strategyproof in expectation as well as ex-ante and ex-post (best of both worlds) fair and efficient. For allocating mixed items, where an item can be a good (i.e., with a positive utility) for one agent but a chore (i.e., a with negative utility) for another, we propose a randomized mechanism that is strategyproof in expectation with best of both worlds fairness and efficiency when there are two agents.
Keywords
- Combinatorial Optimization
- Algorithms
- Game theory
Status: accepted
Back to the list of papers