Proceedings Abstracts of the Twenty-Fifth International Joint Conference on Artificial Intelligence

Allocating Indivisible Items in Categorized Domains / 359
Erika Mackin, Lirong Xia

We initiate a research agenda of mechanism design for categorized domain allocation problems (CDAPs), where indivisible items from multiple categories are allocated to agents without monetary transfer and each agent gets at least one item per category. We focus on basic CDAPs, where each agent gets exactly one item per category. We first characterize serial dictatorships by a minimal set of three axiomatic properties: strategy-proofness, non-bossiness, and category-wise neutrality. Then, we propose a natural extension of serial dictatorships called categorial sequential allocation mechanisms (CSAMs), which allocate the items in multiple rounds: in each round, the designated agent chooses an item from a designated category. We fully characterize the worst-case rank efficiency of CSAMs for optimistic and pessimistic agents.