Envy-Free Mechanisms with Minimum Number of Cuts

Reza Alijani, Majid Farhadi, Mohammad Ghodsi, Masoud Seddighin, Ahmad S. Tajik

AAAI 2017 pp. 312-318

doi:10.1609/AAAI.V31I1.10584 /aaai/2017/alijani2017aaai-envy/

Abstract

We study the problem of fair division of a heterogeneous resource among strategic players. Given a divisible heterogeneous cake, we wish to divide the cake among n players in a way that meets the following criteria: (I) every player(weakly) prefers his allocated cake to any other player’s share (such notion is known as envy-freeness), (II) the mechanism is strategy-proof (truthful), and (III) the number of cuts made on the cake is minimal. We provide methods, namely expansion process and expansion process with unlocking, for dividing the cake under different assumptions on the valuation functions of the players.

PDF AAAI Semantic Scholar

Cite

Text

Alijani et al. "Envy-Free Mechanisms with Minimum Number of Cuts." AAAI Conference on Artificial Intelligence, 2017. doi:10.1609/AAAI.V31I1.10584

Markdown

[Alijani et al. "Envy-Free Mechanisms with Minimum Number of Cuts." AAAI Conference on Artificial Intelligence, 2017.](https://mlanthology.org/aaai/2017/alijani2017aaai-envy/) doi:10.1609/AAAI.V31I1.10584

BibTeX

@inproceedings{alijani2017aaai-envy,
  title     = {{Envy-Free Mechanisms with Minimum Number of Cuts}},
  author    = {Alijani, Reza and Farhadi, Majid and Ghodsi, Mohammad and Seddighin, Masoud and Tajik, Ahmad S.},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2017},
  pages     = {312-318},
  doi       = {10.1609/AAAI.V31I1.10584},
  url       = {https://mlanthology.org/aaai/2017/alijani2017aaai-envy/}
}