Constrained Serial Dictatorships can be Fair
This work addresses fairness in resource allocation mechanisms for agents, but it is incremental as it builds on a previous model with specific parameterizations.
The paper tackles the problem of balancing priority and item allocation in constrained serial dictatorships for indivisible goods, showing that optimal sequences can be computed exactly in polynomial time or approximated via sampling for various parameter settings, with experimental results illustrating parameter impacts.
When allocating indivisible items to agents, it is known that the only strategyproof mechanisms that satisfy a set of rather mild conditions are constrained serial dictatorships: given a fixed order over agents, at each step the designated agent chooses a given number of items (depending on her position in the sequence). Agents who come earlier in the sequence have a larger choice of items; however, this advantage can be compensated by a higher number of items received by those who come later. How to balance priority in the sequence and number of items received is a nontrivial question. We use a previous model, parameterized by a mapping from ranks to scores, a social welfare functional, and a distribution over preference profiles. For several meaningful choices of parameters, we show that the optimal sequence can be computed exactly in polynomial time or approximated using sampling. Our results hold for several probabilistic models on preference profiles, with an emphasis on the Plackett-Luce model. We conclude with experimental results showing how the optimal sequence is impacted by various parameters.