Randomized Strategyproof Mechanisms with Best of Both Worlds Fairness and Efficiency
<|reference_start|>Randomized Strategyproof Mechanisms with Best of Both Worlds Fairness and Efficiency: 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.<|reference_end|>
@article{sun2024randomized,
    title={Randomized Strategyproof Mechanisms with Best of Both Worlds Fairness
  and Efficiency},
    author={Ankang Sun and Bo Chen},
    journal={arXiv preprint arXiv:2408.01027},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.01027},
    primaryClass={cs.GT}
}