Envy-Free Mechanisms with Minimum Number of Cuts

Authors

  • Reza Alijani Duke University
  • Majid Farhadi Sharif University of Technology
  • Mohammad Ghodsi Sharif University of Technology
  • Masoud Seddighin Sharif University of Technology
  • Ahmad Tajik University of Michigan, Ann Arbor

DOI:

https://doi.org/10.1609/aaai.v31i1.10584

Keywords:

envy-free, mechanism design, truthful, cake cutting, fair division

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.

Downloads

Published

2017-02-10

How to Cite

Alijani, R., Farhadi, M., Ghodsi, M., Seddighin, M., & Tajik, A. (2017). Envy-Free Mechanisms with Minimum Number of Cuts. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1). https://doi.org/10.1609/aaai.v31i1.10584

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms