7 Search Results for "Brams, Steven J."

Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.41
Simultaneously Fair Allocation of Indivisible Items Across Multiple Dimensions

Authors: Yasushi Kawase, Bodhayan Roy, and Mohammad Azharuddin Sanpui

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
This paper explores the fair allocation of indivisible items in a multidimensional setting, motivated by the need to address fairness in complex environments where agents assess bundles according to multiple criteria. Such multidimensional settings are not merely of theoretical interest but are central to many real-world applications. For example, cloud computing resources are evaluated based on multiple criteria such as CPU cores, memory, and network bandwidth. In such cases, traditional one-dimensional fairness notions fail to capture fairness across multiple attributes. To address these challenges, we study two relaxed variants of envy-freeness: weak simultaneously envy-free up to c goods (weak sEFc) and strong simultaneously envy-free up to c goods (strong sEFc), which accommodate the multidimensionality of agents’ preferences. Under the weak notion, for every pair of agents and for each dimension, any perceived envy can be eliminated by removing, if necessary, a different set of goods from the envied agent’s allocation. In contrast, the strong version requires selecting a single set of goods whose removal from the envied bundle simultaneously eliminates envy in every dimension. We provide upper and lower bounds on the relaxation parameter c that guarantee the existence of weak or strong sEFc allocations, where these bounds are independent of the total number of items. In addition, we present algorithms for checking whether a weak or strong sEFc allocation exists. Moreover, we establish NP-hardness results for checking the existence of weak sEF1 and strong sEF1 allocations.
Cite as

Yasushi Kawase, Bodhayan Roy, and Mohammad Azharuddin Sanpui. Simultaneously Fair Allocation of Indivisible Items Across Multiple Dimensions. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 41:1-41:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kawase_et_al:LIPIcs.FSTTCS.2025.41,
  author =	{Kawase, Yasushi and Roy, Bodhayan and Sanpui, Mohammad Azharuddin},
  title =	{{Simultaneously Fair Allocation of Indivisible Items Across Multiple Dimensions}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{41:1--41:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.41},
  URN =		{urn:nbn:de:0030-drops-251210},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.41},
  annote =	{Keywords: Fair allocation, Envy-free up to one good, Multi-dimensional criteria, Linear programming, NP-hardness}
}
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}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.71
Unfairly Splitting Separable Necklaces

Authors: Patrick Schnider, Linus Stalder, and Simon Weber

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
The Necklace Splitting problem is a classical problem in combinatorics that has been intensively studied both from a combinatorial and a computational point of view. It is well-known that the Necklace Splitting problem reduces to the discrete Ham Sandwich problem. This reduction was crucial in the proof of PPA-completeness of the Ham Sandwich problem. Recently, Borzechowski, Schnider and Weber [ISAAC'23] introduced a variant of Necklace Splitting that similarly reduces to the α-Ham Sandwich problem, which lies in the complexity class UEOPL but is not known to be complete. To make this reduction work, the input necklace is guaranteed to be n-separable. They showed that these necklaces can be fairly split in polynomial time and thus this subproblem cannot be used to prove UEOPL-hardness for α-Ham Sandwich. We consider the more general unfair necklace splitting problem on n-separable necklaces, i.e., the problem of splitting these necklaces such that each thief gets a desired fraction of each type of jewels. This more general problem is the natural necklace-splitting-type version of α-Ham Sandwich, and its complexity status is one of the main open questions posed by Borzechowski, Schnider and Weber. We show that the unfair splitting problem is also polynomial-time solvable, and can thus also not be used to show UEOPL-hardness for α-Ham Sandwich.
Cite as

Patrick Schnider, Linus Stalder, and Simon Weber. Unfairly Splitting Separable Necklaces. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 71:1-71:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schnider_et_al:LIPIcs.STACS.2025.71,
  author =	{Schnider, Patrick and Stalder, Linus and Weber, Simon},
  title =	{{Unfairly Splitting Separable Necklaces}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{71:1--71:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.71},
  URN =		{urn:nbn:de:0030-drops-228963},
  doi =		{10.4230/LIPIcs.STACS.2025.71},
  annote =	{Keywords: Necklace splitting, n-separability, well-separation, Ham Sandwich, alpha-Ham Sandwich, unfair splitting, fair division}
}
Document
DOI: 10.4230/DagSemProc.07261.1
07261 Abstracts Collection – Fair Division

Authors: Steven J. Brams and Kirk Pruhs

Published in: Dagstuhl Seminar Proceedings, Volume 7261, Fair Division (2007)

Abstract
From 24.06. to 29.06.2007, the Dagstuhl Seminar 07261 % generate automatically ``Fair Division'' % generate automatically was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Steven J. Brams and Kirk Pruhs. 07261 Abstracts Collection – Fair Division. In Fair Division. Dagstuhl Seminar Proceedings, Volume 7261, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{brams_et_al:DagSemProc.07261.1,
  author =	{Brams, Steven J. and Pruhs, Kirk},
  title =	{{07261 Abstracts Collection – Fair Division}},
  booktitle =	{Fair Division},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7261},
  editor =	{Steven Brams and Kirk Pruhs and Gerhard Woeginger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07261.1},
  URN =		{urn:nbn:de:0030-drops-12444},
  doi =		{10.4230/DagSemProc.07261.1},
  annote =	{Keywords: Economics, Fairness, Allocation, Political Science}
}
Document
DOI: 10.4230/DagSemProc.07261.2
07261 Summary – Fair Division

Authors: Steven J. Brams and Kirk Pruhs

Published in: Dagstuhl Seminar Proceedings, Volume 7261, Fair Division (2007)

Abstract
The problem of fair division – dividing goods or "bads" (e.g., costs) among entities in an impartial and equitable way – is one of the most important problems that society faces. A Google search on the phrase "fair allocation" returns over 100K links, referring to the division of sports tickets, health resources, computer networking resources, voting power, intellectual property licenses, costs of environmental improvements, etc.
Cite as

Steven J. Brams and Kirk Pruhs. 07261 Summary – Fair Division. In Fair Division. Dagstuhl Seminar Proceedings, Volume 7261, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{brams_et_al:DagSemProc.07261.2,
  author =	{Brams, Steven J. and Pruhs, Kirk},
  title =	{{07261 Summary  – Fair Division}},
  booktitle =	{Fair Division},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7261},
  editor =	{Steven Brams and Kirk Pruhs and Gerhard Woeginger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07261.2},
  URN =		{urn:nbn:de:0030-drops-12434},
  doi =		{10.4230/DagSemProc.07261.2},
  annote =	{Keywords: Economics, Fairness, Allocation, Political Science}
}
Document
DOI: 10.4230/DagSemProc.07261.5
Better Ways to Cut a Cake - Revisited

Authors: Steven J. Brams, Michael A. Jones, and Christian Klamler

Published in: Dagstuhl Seminar Proceedings, Volume 7261, Fair Division (2007)

Abstract
Procedures to divide a cake among n people with n-1 cuts (the minimum number) are analyzed and compared. For 2 persons, cut-and-choose, while envy-free and efficient, limits the cutter to exactly 50% if he or she is ignorant of the chooser's preferences, whereas the chooser can generally obtain more. By comparison, a new 2-person surplus procedure (SP'), which induces the players to be truthful in order to maximize their minimum allocations, leads to a proportionally equitable division of the surplus - the part that remains after each player receives 50% - by giving each person a certain proportion of the surplus as he or she values it. For n geq 3 persons, a new equitable procedure (EP) yields a maximally equitable division of a cake. This division gives all players the highest common value that they can achieve and induces truthfulness, but it may not be envy-free. The applicability of SP' and EP to the fair division of a heterogeneous, divisible good, like land, is briefly discussed.
Cite as

Steven J. Brams, Michael A. Jones, and Christian Klamler. Better Ways to Cut a Cake - Revisited. In Fair Division. Dagstuhl Seminar Proceedings, Volume 7261, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{brams_et_al:DagSemProc.07261.5,
  author =	{Brams, Steven J. and Jones, Michael A. and Klamler, Christian},
  title =	{{Better Ways to Cut a Cake - Revisited}},
  booktitle =	{Fair Division},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7261},
  editor =	{Steven Brams and Kirk Pruhs and Gerhard Woeginger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07261.5},
  URN =		{urn:nbn:de:0030-drops-12278},
  doi =		{10.4230/DagSemProc.07261.5},
  annote =	{Keywords: Fair division, cake-cutting, envy-freeness, strategy-proofness}
}
Document
DOI: 10.4230/DagSemProc.07261.6
Divide-and-Conquer: A Proportional, Minimal-Envy Cake-Cutting Procedure

Authors: Steven J. Brams, Michael A. Jones, and Christian Klamler

Published in: Dagstuhl Seminar Proceedings, Volume 7261, Fair Division (2007)

Abstract
Properties of discrete cake-cutting procedures that use a minimal number of cuts (n-1 if there are n players) are analyzed. None is always envy-free or efficient, but divide-and-conquer (D&C) minimizes the maximum number of players that any single player may envy. It works by asking n ≥ 2 players successively to place marks on a cake that divide it into equal or approximately equal halves, then halves of these halves, and so on. Among other properties, D&C (i) ensures players of more than 1/n shares if their marks are different and (ii) is strategyproof for risk-averse players. However, D&C may not allow players to obtain proportional, connected pieces if they have unequal entitlements. Possible applications of D&C to land division are briefly discussed.
Cite as

Steven J. Brams, Michael A. Jones, and Christian Klamler. Divide-and-Conquer: A Proportional, Minimal-Envy Cake-Cutting Procedure. In Fair Division. Dagstuhl Seminar Proceedings, Volume 7261, pp. 1-31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{brams_et_al:DagSemProc.07261.6,
  author =	{Brams, Steven J. and Jones, Michael A. and Klamler, Christian},
  title =	{{Divide-and-Conquer: A Proportional, Minimal-Envy Cake-Cutting Procedure}},
  booktitle =	{Fair Division},
  pages =	{1--31},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7261},
  editor =	{Steven Brams and Kirk Pruhs and Gerhard Woeginger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07261.6},
  URN =		{urn:nbn:de:0030-drops-12211},
  doi =		{10.4230/DagSemProc.07261.6},
  annote =	{Keywords: Cake-cutting, proportionality, envy-freeness, efficiency, strategy-proofness}
}
  • Refine by Type
  • 7 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 4 2007

  • Refine by Author
  • 4 Brams, Steven J.
  • 2 Jones, Michael A.
  • 2 Klamler, Christian
  • 2 Pruhs, Kirk
  • 1 Igarashi, Ayumi
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs
  • 4 DagSemProc

  • Refine by Classification
  • 2 Theory of computation → Algorithmic game theory
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Problems, reductions and completeness
  • Show More...

  • Refine by Keyword
  • 3 envy-freeness
  • 2 Allocation
  • 2 Economics
  • 2 Fairness
  • 2 Political Science
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact