Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Constraints in fair division

Constraints in fair division The fair allocation of resources to interested agents is a fundamental problem in society. While the majority of the fair division literature assumes that all allocations are feasible, in practice there are often constraints on the allocation that can be chosen. In this survey, we discuss fairness guarantees for both divisible (cake cutting) and indivisible resources under several common types of constraints, including connectivity, cardinality, matroid, geometric, separation, budget, and conflict constraints. We also outline a number of open questions and directions. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM SIGecom Exchanges Association for Computing Machinery

Constraints in fair division

Suksompong, Warut
ACM SIGecom Exchanges , Volume 19 (2): 16 – Dec 6, 2021
Download PDF
16 pages

Loading next page...
 
/lp/association-for-computing-machinery/constraints-in-fair-division-j4pgS52RP0
Publisher
Association for Computing Machinery
Copyright
Copyright © 2021 Copyright is held by the owner/author(s)
ISSN
1551-9031
eISSN
1551-9031
DOI
10.1145/3505156.3505162
Publisher site
See Article on Publisher Site

Abstract

The fair allocation of resources to interested agents is a fundamental problem in society. While the majority of the fair division literature assumes that all allocations are feasible, in practice there are often constraints on the allocation that can be chosen. In this survey, we discuss fairness guarantees for both divisible (cake cutting) and indivisible resources under several common types of constraints, including connectivity, cardinality, matroid, geometric, separation, budget, and conflict constraints. We also outline a number of open questions and directions.

Journal

ACM SIGecom Exchanges – Association for Computing Machinery

Published: Dec 6, 2021

Keywords: constraints

References

  • Fair and efficient cake division with connected pieces
    Arunachaleswaran, ; R., E.; Barman, ; S., ; Kumar, ; R., ; Rathi, ; N.,
  • The price of indivisibility in cake cutting
    Arunachaleswaran, ; R., E.; Gopalakrishnan, ; R.,
  • Fair allocation of indivisible goods and chores
    Aziz, ; H., ; Caragiannis, ; I., ; Igarashi, ; A., ; Walsh, ; T.,
  • A discrete and bounded envy-free cake cutting protocol for any number of agents
    Aziz, ; H., ; Mackenzie, ; S.,
  • Competitive equilibrium with indivisible goods and generic budgets
    Babaioff, ; M., ; Nisan, ; N., ; Talgam-Cohen, ; I.,
  • The price of connectivity in fair division
    Bei, ; X., ; Igarashi, ; A., ; Lu, ; X., ; Suksompong, ; W.,
  • Fair division of mixed divisible and indivisible goods
    Bei, ; X., ; Li, ; Z., ; Liu, ; J., ; Liu, ; S., ; Lu, ; X.,
  • Dividing a graphical cake
    Bei, ; X., ; Suksompong, ; W.,
  • Almost envy-free allocations with connected bundles
    Bilò, ; V., ; Caragiannis, ; I., ; Flammini, ; M., ; Igarashi, ; A., ; Monaco, ; G., ; Peters, ; D., ; Vinci, ; C., ; Zwicker, ; S., W.
  • Fair division under cardinality constraints
    Biswas, ; A., ; Barman, ; S.,
  • Competitive division of a mixed manna
    Bogomolnaia, ; A., ; Moulin, ; H., ; Sandomirskiy, ; F., ; Yanovskaya, ; E.,
  • Fair division of a graph
    Bouveret, ; S., ; Cechlárová, ; K., ; Elkind, ; E., ; Igarashi, ; A., ; Peters, ; D.,
  • Chore division on a graph
    Bouveret, ; S., ; Cechlárová, ; K., ; Lesca, ; J.,
  • Fair allocation of indivisible goods
    Bouveret, ; S., ; Chevaleyre, ; Y., ; Maudet, ; N.,
  • Fair Division: From Cake-Cutting to Dispute Resolution
    Brams, ; J., S.; Taylor, ; D., A.
  • The query complexity of cake cutting
    Brânzei, ; S., ; Nisan, ; N.,
  • The unreasonable fairness of maximum Nash welfare
    Caragiannis, ; I., ; Kurokawa, ; D., ; Moulin, ; H., ; Procaccia, ; D., A.; Shah, ; N., ; Wang, ; J.,
  • Weighted envy-freeness in indivisible item allocation
    Chakraborty, ; M., ; Igarashi, ; A., ; Suksompong, ; W., ; Zick, ; Y.,
  • Fair packing of independent sets
    Chiarelli, ; N., ; Krnc, ; M., ; Milanič, ; M., ; Pferschy, ; U., ; Pivač, ; N., ; Schauer, ; J.,
  • The complexity of cake cutting with unequal shares
    Cseh, ; A., ; Fleiner, ; T.,
  • Algorithmic solutions for envy-free cake cutting
    Deng, ; X., ; Qi, ; Q., ; Saberi, ; A.,
  • On fair division under heterogeneous matroid constraints
    Dror, ; A., ; Feldman, ; M., ; Segal-Halevi, ; E.,
  • How to cut a cake fairly
    Dubins, ; E., L.; Spanier, ; H., E.
  • Cake cutting really is not a piece of cake
    Edmonds, ; J., ; Pruhs, ; K.,
  • Graphical cake cutting via maximin share
    Elkind, ; E., ; Segal-Halevi, ; E., ; Suksompong, ; W.,
  • Keep your distance: Land division with separation
    Elkind, ; E., ; Segal-Halevi, ; E., ; Suksompong, ; W.,
  • Mind the gap: Cake cutting with separation
    Elkind, ; E., ; Segal-Halevi, ; E., ; Suksompong, ; W.,
  • A note on cake cutting
    Even, ; S., ; Paz, ; A.,
  • Fair allocation of indivisible goods to asymmetric agents
    Farhadi, ; A., ; Ghodsi, ; M., ; Hajiaghayi, ; M., ; Lahaie, ; S., ; Pennock, ; D., ; Seddighin, ; M., ; Seddighin, ; S., ; Yami, ; H.,
  • Approximately envy-free budget-feasible allocation
    Gan, ; J., ; Li, ; B., ; Wu, ; X.,
  • Assigning papers to referees
    Garg, ; N., ; Kavitha, ; T., ; Kumar, ; A., ; Mehlhorn, ; K., ; Mestre, ; J.,
  • Contiguous cake cutting: Hardness results and approximation algorithms
    Goldberg, ; W., P.; Hollender, ; A., ; Suksompong, ; W.,
  • Spliddit: Unleashing fair division algorithms
    Goldman, ; J., ; Procaccia, ; D., A.
  • On maximin share allocations in matroids
    Gourvès, ; L., ; Monnot, ; J.,
  • Near fairness in matroids
    Gourvès, ; L., ; Monnot, ; J., ; Tlilane, ; L.,
  • Fair division of time: Multi-layered cake cutting
    Hosseini, ; H., ; Igarashi, ; A., ; Searns, ; A.,
  • Fair allocation of conflicting items
    Hummel, ; H., ; Hetland, ; L., M.
  • Guaranteeing half-maximin shares under cardinality constraints
    Hummel, ; H., ; Hetland, ; L., M.
  • Envy-free division of multi-layered cakes
    Igarashi, ; A., ; Meunier, ; F.,
  • Pareto-optimal allocation of indivisible goods with connectivity constraints
    Igarashi, ; A., ; Peters, ; D.,
  • Fair division of graphs and of tangled cakes
    Igarashi, ; A., ; Zwicker, ; S., W.
  • Splitting necklaces, with constraints
    Jojić, ; D., ; Panina, ; G., ; Živaljević, ; R.,
  • Almost envy-freeness in group resource allocation
    Kyropoulou, ; M., ; Suksompong, ; W., ; Voudouris, ; A., A.
  • The fair division of hereditary set systems
    Li, ; Z., ; Vetta, ; A.,
  • On approximately fair allocations of indivisible goods
    Lipton, ; J., R.; Markakis, ; E., ; Mossel, ; E., ; Saberi, ; A.,
  • Maximin share allocations on cycles
    Lonc, ; Z., ; Truszczynski, ; M.,
  • Asymptotic existence of fair divisions for groups
    Manurangsi, ; P., ; Suksompong, ; W.,
  • Approximation algorithms and hardness results for fair division
    Markakis, ; E.,
  • Equitable division of a path
    Misra, ; N., ; Sonar, ; C., ; Vaidyanathan, ; R., P.; Vaish, ; R.,
  • Fair Division and Collective Welfare
    Moulin, ; H.,
  • Cake cutting algorithms
    Procaccia, ; D., A.
  • Cake-Cutting Algorithms: Be Fair if You Can
    Robertson, ; J., ; Webb, ; W.,
  • Fairly dividing a cake after some parts were burnt in the oven
    Segal-Halevi, ; E.,
  • Fair multi-cake cutting
    Segal-Halevi, ; E.,
  • Envy-free division of land
    Segal-Halevi, ; E., ; Hassidim, ; A., ; Aumann, ; Y.,
  • Envy-free cake-cutting among families
    Segal-Halevi, ; E., ; Nitzan, ; S.,
  • Fair and square: Cake-cutting in two dimensions
    Segal-Halevi, ; E., ; Nitzan, ; S., ; Hassidim, ; A., ; Aumann, ; Y.,
  • Spliddit: Two years of making the world fairer
    Shah, ; N.,
  • How to cut a cake fairly
    Stromquist, ; W.,
  • Envy-free cake divisions cannot be found by finite protocols
    Stromquist, ; W.,
  • Rental harmony: Sperner's lemma in fair division
    Su, ; E., F.
  • Approximate maximin shares for groups of agents
    Suksompong, ; W.,
  • Fairly allocating contiguous blocks of indivisible items
    Suksompong, ; W.,
  • Introduction to the theory of fair allocation
    Thomson, ; W.,
  • Fair division: the computer scientist's perspective
    Walsh, ; T.,
  • Budget-feasible maximum Nash social welfare allocation is almost envy-free
    Wu, ; X., ; Li, ; B., ; Gan, ; J.,