Help
Cart
Skip main navigation

Available Issues

April 10, 2013 - May 8, 2026

Available Issues

April 10, 2013 - May 8, 2026

Consensus Halving for Sets of Items

Published Online:10 Feb 2022https://doi.org/10.1287/moor.2021.1249

References

  • [1] Alon N (1987) Splitting necklaces. Adv. Math. 63(3):247–253.Crossref, Google Scholar
  • [2] Alon N, Graur A (2021) Efficient splitting of necklaces. Proc. 48th Internat. Colloquium Automata, Languages, Programming, 1–17.Google Scholar
  • [3] Alon N, West DB (1986) The Borsuk-Ulam theorem and bisection of necklaces. Proc. Amer. Math. Soc. 98(4):623–628.Crossref, Google Scholar
  • [4] Austin AK (1982) Sharing a cake. Math. Gazette 66(437):212–215.Crossref, Google Scholar
  • [5] Aziz H, Caragiannis I, Igarashi A, Walsh T (2019) Fair allocation of indivisible goods and chores. Proc. 28th Internat. Joint Conf. Artificial Intelligence, 53–59.Google Scholar
  • [6] Batziou E, Hansen KA, Høgh K (2021) Strong approximate consensus halving and the Borsuk-Ulam theorem. Proc. 48th Internat. Colloquium Automata, Languages, Programming, 1–20.Google Scholar
  • [7] Bilò V, Caragiannis I, Flammini M, Igarashi A, Monaco G, Peters D, Vinci C, Zwicker WS (2019) Almost envy-free allocations with connected bundles. Proc. 10th Innovations Theoretical Comput. Sci. Conf., 1–21.Google Scholar
  • [8] Bogomolnaia A, Moulin H, Sandomirskiy F, Yanovskaya E (2017) Competitive division of a mixed manna. Econometrica 85(6):1847–1871.Crossref, Google Scholar
  • [9] Brams SJ, Taylor AD (1996) Fair Division: From Cake-Cutting to Dispute Resolution (Cambridge University Press).Crossref, Google Scholar
  • [10] Brams SJ, Taylor AD (1999) The Win-Win Solution: Guaranteeing Fair Shares to Everybody (W. W. Norton & Company).Google Scholar
  • [11] Caragiannis I, Kurokawa D, Moulin H, Procaccia AD, Shah N, Wang J (2019) The unreasonable fairness of maximum Nash welfare. ACM Trans. Econom. Comput. 7(3):1–32.Crossref, Google Scholar
  • [12] Chaudhury BR, Garg J, McGlaughlin P, Mehta R (2021) Competitive allocation of a mixed manna. Proc. 32nd ACM-SIAM Sympos. Discrete Algorithms, 1405–1424.Google Scholar
  • [13] Chen X, Deng X, Teng SH (2009) Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3):1–57.Crossref, Google Scholar
  • [14] Daskalakis C, Goldberg PW, Papadimitriou CH (2009) The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1):195–259.Crossref, Google Scholar
  • [15] Deligkas A, Filos-Ratsikas A, Hollender A (2021) Two’s company, three’s a crowd: Consensus-halving for a constant number of agents. Proc. 22nd ACM Conf. Econom. Comput., 347–368.Google Scholar
  • [16] Deligkas A, Fearnley J, Melissourgos T, Spirakis PG (2021) Computing exact solutions of consensus halving and the Borsuk-Ulam theorem. J. Comput. System Sci. 117:75–98.Crossref, Google Scholar
  • [17] Deng X, Qi Q, Saberi A (2012) Algorithmic solutions for envy-free cake cutting. Oper. Res. 60(6):1461–1476.Link, Google Scholar
  • [18] Etessami K, Yannakakis M (2010) On the complexity of Nash equilibria and other fixed points. SIAM J. Comput. 39(6):2531–2597.Crossref, Google Scholar
  • [19] Filos-Ratsikas A, Goldberg PW (2018) Consensus halving is PPA-complete. Proc. 50th Annual ACM SIGACT Sympos. Theory Comput., 51–64.Google Scholar
  • [20] Filos-Ratsikas A, Goldberg PW (2019) The complexity of splitting necklaces and bisecting ham sandwiches. Proc. 51st Annual ACM SIGACT Sympos. Theory Comput., 638–649.Google Scholar
  • [21] Filos-Ratsikas A, Frederiksen SKS, Goldberg PW, Zhang J (2018) Hardness results for consensus-halving. Proc. 43rd Internat. Sympos. Math. Foundations Comput. Sci., 1–16.Google Scholar
  • [22] Filos-Ratsikas A, Hollender A, Sotiraki K, Zampetakis M (2020) Consensus-halving: Does it ever get easier? Proc. 21st ACM Conf. Econom. Comput., 381–399.Google Scholar
  • [23] Filos-Ratsikas A, Hollender A, Sotiraki K, Zampetakis M (2021) A topological characterization of modulo-p arguments and implications for necklace splitting. Proc. 32nd ACM-SIAM Sympos. Discrete Algorithms, 2615–2634.Google Scholar
  • [24] Filos-Ratsikas A, Giannakopoulos Y, Hollender A, Lazos P, Poças D (2021) On the complexity of equilibrium computation in first-price auctions. Proc. 22nd ACM Conf. Econom. Comput., 454–476.Google Scholar
  • [25] Garg J, Mehta R, Vazirani VV (2018) Substitution with satiation: A new class of utility functions and a complementary pivot algorithm. Math. Oper. Res. 43(3):996–1024.Link, Google Scholar
  • [26] Goldberg CH, West DB (1985) Bisection of circle colorings. SIAM J. Algebraic Discrete Methods 6(1):93–106.Crossref, Google Scholar
  • [27] Göös M, Kamath P, Sotiraki K, Zampetakis M (2020) On the complexity of modulo-q arguments and the Chevalley-Warning theorem. Proc. 35th Comput. Complexity Conf., 1–42.Google Scholar
  • [28] Gourvès L (2019) Agreeable sets with matroidal constraints. J. Combin. Optim. 37(3):866–888.Crossref, Google Scholar
  • [29] Hobby CR, Rice JR (1965) A moment problem in L1 approximation. Proc. Amer. Math. Soc. 16(4):665–670.Google Scholar
  • [30] Hollender A (2021) The classes PPA-k: Existence from arguments modulo k. Theoretical Comput. Sci. 885:15–29.Crossref, Google Scholar
  • [31] Kyropoulou M, Suksompong W, Voudouris AA (2020) Almost envy-freeness in group resource allocation. Theoretical Comput. Sci. 841:110–123.Crossref, Google Scholar
  • [32] Manurangsi P, Suksompong W (2017) Asymptotic existence of fair divisions for groups. Math. Social Sci. 89:100–108.Crossref, Google Scholar
  • [33] Manurangsi P, Suksompong W (2019) Computing a small agreeable set of indivisible items. Artificial Intelligence 268:96–114.Crossref, Google Scholar
  • [34] Manurangsi P, Suksompong W (2021) Almost envy-freeness for groups: Improved bounds via discrepancy theory. Proc. 30th Internat. Joint Conf. Artificial Intelligence, 335–341.Google Scholar
  • [35] Moulin H (2003) Fair Division and Collective Welfare (MIT Press).Crossref, Google Scholar
  • [36] Moulin H (2007) Minimizing the worst slowdown: Offline, online. Oper. Res. 55(5):876–889.Link, Google Scholar
  • [37] Neyman J (1946) Un théorème d’existence. Comptes Rendus de l’Académie des sciences 222:843–845.Google Scholar
  • [38] Oh H, Procaccia AD, Suksompong W (2021) Fairly allocating many goods with few queries. SIAM J. Discrete Math. 35(2):788–813.Crossref, Google Scholar
  • [39] Papadimitriou CH (1994) On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. System Sci. 48(3):498–532.Crossref, Google Scholar
  • [40] Plaut B, Roughgarden T (2020) Almost envy-freeness with general valuations. SIAM J. Discrete Math. 34(2):1039–1068.Crossref, Google Scholar
  • [41] Roughgarden T (2016) Twenty Lectures on Algorithmic Game Theory (Cambridge University Press).Crossref, Google Scholar
  • [42] Rubinstein A (2018) Inapproximability of Nash equilibrium. SIAM J. Comput. 47(3):917–959.Crossref, Google Scholar
  • [43] Sandomirskiy F, Segal-Halevi E (2019) Fair division with minimal sharing. Preprint, submitted August 5, https://arxiv.org/abs/1908.01669.Google Scholar
  • [44] Schuldenzucker S, Seuken S (2019) Monotonic and non-monotonic solution concepts for generalized circuits. Preprint, submitted July 30, https://arxiv.org/abs/1907.12854.Google Scholar
  • [45] Segal-Halevi E (2018) Fairly dividing a cake after some parts were burnt in the oven. Proc. 17th Internat. Conf. Autonomous Agents Multiagent Systems, 1276–1284.Google Scholar
  • [46] Segal-Halevi E, Nitzan S (2019) Fair cake-cutting among families. Soc. Choice Welfare 53(4):709–740.Crossref, Google Scholar
  • [47] Segal-Halevi E, Suksompong W (2019) Democratic fair allocation of indivisible goods. Artificial Intelligence 277:103167.Crossref, Google Scholar
  • [48] Segal-Halevi E, Suksompong W (2021) How to cut a cake fairly: A generalization to groups. Amer. Math. Monthly 128(1):79–83.Crossref, Google Scholar
  • [49] Segal-Halevi E, Hassidim A, Aumann Y (2020) Envy-free division of land. Math. Oper. Res. 45(3):896–922.Link, Google Scholar
  • [50] Simmons FW, Su FE (2003) Consensus-halving via theorems of Borsuk-Ulam and Tucker. Math. Social Sci. 45(1):15–25.Crossref, Google Scholar
  • [51] Stromquist W, Woodall DR (1985) Sets on which several measures agree. J. Math. Anal. Appl. 108(1):241–248.Crossref, Google Scholar
  • [52] Suksompong W (2016) Assigning a small agreeable set of indivisible items to multiple players. Proc. 25th Internat. Joint Conf. Artificial Intelligence, 489–495.Google Scholar
  • [53] Suksompong W (2018) Approximate maximin shares for groups of agents. Math. Social Sci. 92:40–47.Crossref, Google Scholar
  • [54] Vondrák J (2010) CS 369P: Polyhedral techniques in combinatorial optimization, Lecture 17. Accessed February 5, 2022, http://theory.stanford.edu/˜jvondrak/CS369P/lec17.pdf.Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree