Fairly Allocating Many Goods with Few Queries

2018-07-30 · Hoon Oh, Ariel D. Procaccia, Warut Suksompong

We investigate the query complexity of the fair allocation of indivisible goods. For two agents with arbitrary monotonic utilities, we design an algorithm that computes an allocation satisfying envy-freeness up to one good (EF1), a relaxation of envy-freeness, using a logarithmic number of queries. We show that the logarithmic query complexity bound also holds for three agents with additive utilities, and that a polylogarithmic bound holds for three agents with monotonic utilities. These results suggest that it is possible to fairly allocate goods in practice even when the number of goods is extremely large. By contrast, we prove that computing an allocation satisfying envy-freeness and another of its relaxations, envy-freeness up to any good (EFX), requires a linear number of queries even when there are only two agents with identical additive utilities.

📄 PDF Abstract BibTeX arXiv:1807.11367

Code (0)

등록된 구현이 없습니다.

Envy-Free Allocation of Indivisible Goods via Noisy Queries

2026-02-06 · Zihan Li, Yan Hao Ling, Jonathan Scarlett, Warut Suksompong arxiv

We introduce a problem of fairly allocating indivisible goods (items) in which the agents' valuations cannot be observed directly, but instead can only be accessed via noisy queries. In the two-agent setting with Gaussia…

PROPm Allocations of Indivisible Goods to Multiple Agents

2021-05-24 · Artem Baklanov, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin

We study the classic problem of fairly allocating a set of indivisible goods among a group of agents, and focus on the notion of approximate proportionality known as PROPm. Prior work showed that there exists an allocati…

Fairness

On Maximum Weighted Nash Welfare for Binary Valuations

2022-04-08 · Warut Suksompong, Nicholas Teh

We consider the problem of fairly allocating indivisible goods to agents with weights representing their entitlements. A natural rule in this setting is the maximum weighted Nash welfare (MWNW) rule, which selects an all…

Fairly Allocating Utility in Constrained Multiwinner Elections

2022-11-23 · Kunal Relia

Fairness in multiwinner elections is studied in varying contexts. For instance, diversity of candidates and representation of voters are both separately termed as being fair. A common denominator to ensure fairness acros…

Diversity Fairness

Achieving Proportionality up to the Maximin Item with Indivisible Goods

2020-09-20 · Artem Baklanov, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin

We study the problem of fairly allocating indivisible goods and focus on the classic fairness notion of proportionality. The indivisibility of the goods is long known to pose highly non-trivial obstacles to achieving fai…