Picking Sequences and Monotonicity in Weighted Fair Division

Chakraborty, Mithun; Schmidt-Kraepelin, Ulrike; Suksompong, Warut

doi:10.24963/ijcai.2021/12

Picking Sequences and Monotonicity in Weighted Fair Division

Mithun Chakraborty, Ulrike Schmidt-Kraepelin, Warut Suksompong

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 82-88.

https://doi.org/10.24963/ijcai.2021/12

Keywords

Agent-based and Multi-agent Systems: Resource Allocation
Agent-based and Multi-agent Systems: Computational Social Choice

Abstract

We study the problem of fairly allocating indivisible items to agents with different entitlements, which captures, for example, the distribution of ministries among political parties in a coalition government. Our focus is on picking sequences derived from common apportionment methods, including five traditional divisor methods and the quota method. We paint a complete picture of these methods in relation to known envy-freeness and proportionality relaxations for indivisible items as well as monotonicity properties with respect to the resource, population, and weights. In addition, we provide characterizations of picking sequences satisfying each of the fairness notions, and show that the well-studied maximum Nash welfare solution fails resource- and population-monotonicity even in the unweighted setting. Our results serve as an argument in favor of using picking sequences in weighted fair division problems.

Mithun Chakraborty, Ulrike Schmidt-Kraepelin, and Warut Suksompong. 2021. Picking Sequences and Monotonicity in Weighted Fair Division. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 82–88. https://doi.org/10.24963/ijcai.2021/12

@inproceedings{ijcai2021p12,
  title     = {Picking Sequences and Monotonicity in Weighted Fair Division},
  author    = {Chakraborty, Mithun and Schmidt-Kraepelin, Ulrike and Suksompong, Warut},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {82--88},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/12},
  url       = {https://doi.org/10.24963/ijcai.2021/12},
}

TY  - CPAPER
TI  - Picking Sequences and Monotonicity in Weighted Fair Division
AU  - Chakraborty, Mithun
AU  - Schmidt-Kraepelin, Ulrike
AU  - Suksompong, Warut
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 82
EP  - 88
DO  - 10.24963/ijcai.2021/12
UR  - https://doi.org/10.24963/ijcai.2021/12
ER  -