DROPS

Document

Extended Abstract

DOI: 10.4230/LIPIcs.ITCS.2026.77

Discrepancy Beyond Additive Functions with Applications to Fair Division (Extended Abstract)

Authors: Alexandros Hollender, Pasin Manurangsi, Raghu Meka, and Warut Suksompong

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

We consider a setting where we have a ground set ℳ together with real-valued set functions f₁, … , f_n, and the goal is to partition ℳ into two sets S₁,S₂ such that |f_i(S₁) - f_i(S₂)| is small for every i. Many results in discrepancy theory can be stated in this form with the functions f_i being additive. In this work, we initiate the study of the unstructured case where f_i is not assumed to be additive. We show that even without the additivity assumption, the upper bound remains at most O(√{n log n}). Our result has implications on the fair allocation of indivisible goods. In particular, we show that a consensus halving up to O(√{n log n}) goods always exists for n agents with monotone utilities. Previously, only an O(n) bound was known for this setting.

Cite as

Alexandros Hollender, Pasin Manurangsi, Raghu Meka, and Warut Suksompong. Discrepancy Beyond Additive Functions with Applications to Fair Division (Extended Abstract). In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, p. 77:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hollender_et_al:LIPIcs.ITCS.2026.77,
  author =	{Hollender, Alexandros and Manurangsi, Pasin and Meka, Raghu and Suksompong, Warut},
  title =	{{Discrepancy Beyond Additive Functions with Applications to Fair Division}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{77:1--77:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.77},
  URN =		{urn:nbn:de:0030-drops-253641},
  doi =		{10.4230/LIPIcs.ITCS.2026.77},
  annote =	{Keywords: Discrepancy Theory, Fair Division}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2025.54

Reforming an Unfair Allocation by Exchanging Goods

Authors: Sheung Man Yuen, Ayumi Igarashi, Naoyuki Kamiyama, and Warut Suksompong

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract

Fairly allocating indivisible goods is a frequently occurring task in everyday life. Given an initial allocation of the goods, we consider the problem of reforming it via a sequence of exchanges to attain fairness in the form of envy-freeness up to one good (EF1). We present a vast array of results on the complexity of determining whether it is possible to reach an EF1 allocation from the initial allocation and, if so, the minimum number of exchanges required. In particular, we uncover several distinctions based on the number of agents involved and their utility functions. Furthermore, we derive essentially tight bounds on the worst-case number of exchanges needed to achieve EF1.

Cite as

Sheung Man Yuen, Ayumi Igarashi, Naoyuki Kamiyama, and Warut Suksompong. Reforming an Unfair Allocation by Exchanging Goods. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 54:1-54:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{yuen_et_al:LIPIcs.ISAAC.2025.54,
  author =	{Yuen, Sheung Man and Igarashi, Ayumi and Kamiyama, Naoyuki and Suksompong, Warut},
  title =	{{Reforming an Unfair Allocation by Exchanging Goods}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{54:1--54:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.54},
  URN =		{urn:nbn:de:0030-drops-249626},
  doi =		{10.4230/LIPIcs.ISAAC.2025.54},
  annote =	{Keywords: fair division, indivisible goods, envy-freeness, exchanges}
}

Search Results

Documents authored by Suksompong, Warut

Discrepancy Beyond Additive Functions with Applications to Fair Division (Extended Abstract)

Abstract

Cite as

Reforming an Unfair Allocation by Exchanging Goods

Abstract

Cite as

Thanks for your feedback!

Could not send message