Random Assignment of Indivisible Goods under Constraints

Random Assignment of Indivisible Goods under Constraints

Yasushi Kawase, Hanna Sumita, Yu Yokoi

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Main Track. Pages 2792-2799. https://doi.org/10.24963/ijcai.2023/311

We investigate the problem of random assignment of indivisible goods, in which each agent has an ordinal preference and a constraint. Our goal is to characterize the conditions under which there always exists a random assignment that simultaneously satisfies efficiency and envy-freeness. The probabilistic serial mechanism ensures the existence of such an assignment for the unconstrained setting. In this paper, we consider a more general setting in which each agent can consume a set of items only if the set satisfies her feasibility constraint. Such constraints must be taken into account in student course placements, employee shift assignments, and so on. We demonstrate that an efficient and envy-free assignment may not exist even for the simple case of partition matroid constraints, where the items are categorized, and each agent demands one item from each category. We then identify special cases in which an efficient and envy-free assignment always exists. For these cases, the probabilistic serial cannot be naturally extended; therefore, we provide mechanisms to find the desired assignment using various approaches.
Keywords:
Game Theory and Economic Paradigms: GTEP: Fair division
Game Theory and Economic Paradigms: GTEP: Auctions and market-based systems
Game Theory and Economic Paradigms: GTEP: Mechanism design