PROPm Allocations of Indivisible Goods to Multiple Agents

A. Baklanov; Garimidi P.; Gkatzelis V.; Schoepflin D.

doi:10.24963/ijcai.2021/4

Publications

?

PROPm Allocations of Indivisible Goods to Multiple Agents

P. 24–30.

Baklanov A., Garimidi P., Gkatzelis V., Schoepflin D.

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 allocation that satisfies this notion of fairness for instances involving up to five agents, but fell short of proving that this is true in general. We extend this result to show that a PROPm allocation is guaranteed to exist for all instances, independent of the number of agents or goods. Our proof is constructive, providing an algorithm that computes such an allocation and, unlike prior work, the running time of this algorithm is polynomial in both the number of agents and the number of goods.

Language: English

DOI

Text on another site

Keywords: fair division of goods

Publication based on the results of:

New game-theoretic methods to resource allocation problems (2022)

In book

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)

International Joint Conferences on Artificial Intelligence, 2021.

Achieving Proportionality up to the Maximin Item with Indivisible Goods

Baklanov A., Garimidi P., Gkatzelis V. et al., , in: The Thirty-Fifth AAAI Conference on Artificial Intelligence. Technical Tracks 6Vol. 35. Issue 6.: AAAI Press, 2021. P. 5143–5150.

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 fairness, and a very vibrant line of research has aimed to circumvent them using appropriate notions of approximate fairness. Recent work has ...

Added: August 23, 2021

Competitive division of a mixed manna

Bogomolnaia A., Moulin H., Sandomirskiy F. et al., Econometrica 2017 Vol. 85 No. 6 P. 1847–1871

A mixed manna contains goods (that everyone likes), bads (that everyone dislikes), as well as items that are goods to some agents, but bads or satiated to others. If all items are goods and utility functions are homothetic, concave (and monotone), the Competitive Equilibrium with Equal Incomes maximizes the Nash product of utilities: hence it is ...

Added: October 14, 2016

Dividing goods or bads under additive utilities

Bogomolnaia A., Moulin H., Sandomirskiy F. et al., / Series arXiv:1608.01540 "Computer Science". 2016.

The Competitive Equilibrium with Equal Incomes is an especially appealing efficient and envy-free division of private goods when utilities are additive: it maximizes the Nash product of utilities and is single-valued and continuous in the marginal rates of substitution. The CEEI to divide bads captures similarly the critical points of the Nash product in the ...

Added: October 14, 2016

Dividing goods and bads under additive utilities

Bogomolnaia A., Moulin H., Sandomirskiy F. et al., / Series arXiv:1610.03745 [cs.GT] "Computer Science". 2016.

When utilities are additive, we uncovered in our previous paper (Bogomolnaia et al. "Dividing Goods or Bads under Additive Utilities") many similarities but also surprising differences in the behavior of the familiar Competitive rule (with equal incomes), when we divide (private) goods or bads. The rule picks in both cases the critical points of the ...

Added: October 13, 2016

Dividing Goods or Bads Under Additive Utilities

Bogomolnaia A., Moulin H., Sandomirskiy F. et al., / NRU Higher School of Economics. Series EC "Economics". 2016. No. 147.

Added: August 19, 2016