The price of connectivity in fair division

• Main Authors: Bei, Xiaohui, Igarashi, Ayumi, Lu, Xinhang, Suksompong, Warut
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2022
• Subjects: Science::Mathematics; Fair Division; Envy-Freeness
• Online Access: https://hdl.handle.net/10356/161276
• Institution: Nanyang Technological University

We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected subgraph. Our focus is on well-studied fairness notions including envy-freeness and maximin share fairness. We introduc...