Towards More Expressive Cake Cutting

Caragiannis, Ioannis; Lai, John K.; Procaccia, Ariel D.

doi:10.5591/978-1-57735-516-8/IJCAI11-033

Towards More Expressive Cake Cutting

Ioannis Caragiannis, John K. Lai, Ariel D. Procaccia

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 127-131.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-033

Abstract

Cake cutting is a playful name for the problem of fairly dividing a heterogeneous divisible good among a set of agents. The agent valuations for different pieces of cake are typically assumed to be additive. However, in certain practical settings this assumption is invalid because agents may not have positive value for arbitrarily small crumbs of cake. In this paper, we propose a new, more expressive model of agent valuations that captures this feature. We present an approximately proportional algorithm for any number of agents that have such expressive valuations. The algorithm is optimal in the sense that no other algorithm can guarantee a greater worst-case degree of proportionality. We also design an optimal approximately proportional and fully envy-free algorithm for two agents.

Ioannis Caragiannis, John K. Lai, and Ariel D. Procaccia. 2011. Towards More Expressive Cake Cutting. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 127–131. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-033

@inproceedings{ijcai2011p33,
  title     = {Towards More Expressive Cake Cutting},
  author    = {Caragiannis, Ioannis and Lai, John K. and Procaccia, Ariel D.},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {127--131},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-033},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-033},
}

TY  - CPAPER
TI  - Towards More Expressive Cake Cutting
AU  - Caragiannis, Ioannis
AU  - Lai, John K.
AU  - Procaccia, Ariel D.
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 127
EP  - 131
DO  - 10.5591/978-1-57735-516-8/IJCAI11-033
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-033
ER  -