Paper ID: 2301.06086

Thou Shalt not Pick all Items if Thou are First: of Strategyproof and Fair Picking Sequences

Sylvain Bouveret, Hugo Gilbert, Jérôme Lang, Guillaume Méroué

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). With these rules, also known as non-interleaving picking sequences, 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 in polynomial time. Last, we give a simple procedure for eliciting scoring vectors and we study the impact of the assignment from agents to positions on the ex-post social welfare.

Submitted: Jan 11, 2023