Possible and Necessary Allocations via Sequential Mechanisms
This work addresses allocation fairness in resource distribution for multi-agent systems, providing incremental extensions to existing characterizations.
The paper tackles the problem of characterizing and computing possible and necessary allocations in sequential mechanisms for indivisible resources, identifying specific conditions for various policy classes and analyzing their computational complexity.
A simple mechanism for allocating indivisible resources is sequential allocation in which agents take turns to pick items. We focus on possible and necessary allocation problems, checking whether allocations of a given form occur in some or all mechanisms for several commonly used classes of sequential allocation mechanisms. In particular, we consider whether a given agent receives a given item, a set of items, or a subset of items for five natural classes of sequential allocation mechanisms: balanced, recursively balanced, balanced alternating, strictly alternating and all policies. We identify characterizations of allocations produced balanced, recursively balanced, balanced alternating policies and strictly alternating policies respectively, which extend the well-known characterization by Brams and King [2005] for policies without restrictions. In addition, we examine the computational complexity of possible and necessary allocation problems for these classes.