Picking sequence

A picking sequence is a protocol for fair item assignment. Suppose m items have to be divided among n agents. One way to allocate the items is to let one agent select a single item, then let another agent select a single item, and so on. A picking-sequence is a sequence of m numbers between 1 and n, where each number determines what agent is the next to pick an item.

As an example, suppose 4 items have to be divided between 2 agents. Some possible picking sequences are:

• 1122 - agent #1 picks two items, then agent #2 picks the two remaining items.
• 1212 - agent #1 picks one item, then agent #2 picks one item, then agent #1 again, then agent #2 again. This is obviously more "fair" than 1122, since it lets agent #2 more chance to get a better item.
• 1221 - agent #1 picks one item, then agent #2 picks two items, then agent #1 receives the remaining item. This is intuitively even more "fair" than 1212, since in 1212, agent #2 is always behind of agent #1, while 1221 is more balanced.^[1]

Advantages

A picking-sequence has several merits as a fair division protocol:^[2]:307

• Simplicity: it is very easy for the agents to understand how the protocol works and what they should do in each step - just pick the best item.
• Privacy: the agents do not have to reveal their entire valuation function, or even their entire ranking. They only have to reveal what item is the best for them in each step.
• Low communication complexity: it requires only m reports, each of which includes a number between 1 and m, so that the total complexity is ${\displaystyle \Theta (m\log {m})}$.

Challenges

How should the picking sequence be selected? Bouveret and Lang^[3] study this question under the following assumptions:

• Each agent has an additive utility function (this implies that the items are independent goods).
• The agents may have different rankings on the items, but there is a common scoring function that maps the rankings to monetary values (e.g, for each agent, his best item is worth for him x dollars, his second-best item is worth for him y dollars, etc).
• The allocator does not know the rankings of the agents, but he knows that all rankings are random draws from a given probability distribution.
• The goal of the allocator is to maximize the expected value of some social welfare function.

They show picking-sequences that maximize the expected utilitarian welfare (sum of utilities) or the expected egalitarian welfare (minimum utility) in various settings.

Kalinowski et al^[4] show that, when there are two agents with a Borda scoring function, and each ranking is equally probable, then the "round robin" sequence (121212...) attains the maximal expected sum-of-utilities.^[2]:308

References

1. Steven Brams and Alan D. Taylor (1999–2000). 'The Win-Win Solution: Guaranteeing Fair Shares to Everybody. New York: W. W. Norton.
2. Sylvain Bouveret and Yann Chevaleyre and Nicolas Maudet, "Fair Allocation of Indivisible Goods". Chapter 12 in: Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Handbook of Computational Social Choice. Cambridge University Press. ISBN 9781107060432. (free online version)
3. A general elicitation-free protocol for allocating indivisible goods. doi:10.5591/978-1-57735-516-8/ijcai11-024.
4. A social welfare optimal sequential allocation procedure. AAAI-13. 2013.