Fair and efficient allocation of indivisible items under category constraints
成果类型：
Article
署名作者：
Igarashi, Ayumi; Meunier, Frederic
署名单位：
University of Tokyo; Institut Polytechnique de Paris; Ecole Nationale des Ponts et Chaussees
刊物名称：
GAMES AND ECONOMIC BEHAVIOR
ISSN/ISSBN：
0899-8256
DOI：
10.1016/j.geb.2026.06.013
发表日期：
2026
关键词：
摘要：
We study the problem of fairly allocating indivisible good and chores under category constraints. There are agents and items, partitioned into categories with capacity limits, and an allocation is feasible ilevary bundle respects thus limits ontwe agents, Shoshan et al. (2023) gave a polynomial-time algorithm for finding a Pareto-optimal allocation satisfying EF[1, 1], a relaxed form of envy-freeness. Extending this beyond two agents was open. We show that for any number of agents and any number k of categories, there exists a Pareto-optimal allocation such that each agent can be made envy-free by reallocating at most mink+1,n)(n-1) items. We also give a polynomial-time algorithm for computing such an al-location when a is a constant. Our approach uses a new application of the Knaster-Kuratowski-Mazurkiewicz (KKM) lemma on a simplex of agent weights, which may be of independent interest.