Picking sequence

Last updated October 26, 2023

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 agent-names, where each name determines what agent is the next to pick an item.

AABB - Alice picks two items, then Bob picks the two remaining items.
ABAB - Alice picks one item, then Bob picks one item, then Alice again, then Bob again. This is more "fair" than AABB since it lets Bob more chance to get a better item.
ABBA - Alice picks one item, then Bob picks two items, then Alice receives the remaining item. This is intuitively even more "fair" than ABAB, since, in ABAB, Bob is always behind of Alice, while ABBA 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 $\Theta (m\log {m})$ .

Welfare maximization

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, the "round robin" sequence (ABABAB...) attains the maximal expected sum-of-utilities.^[2]^: 308

Fairness with different entitlements

Brams and Kaplan^[5] study the problem of allocating cabinet ministries among parties. There is a coalition of parties; each party has a different number of seats in the parliament; larger parties should be allocated more ministries or more prestigious ministries. This is a special case of fair item assignment with different entitlements. A possible solution to this problem is to determine a picking sequence, based on the different entitlements, and let each party pick a ministry in turn. Such a solution is used in Northern Ireland, Denmark and the European parliament.^[6]

Brams assumes that each agent has a strict ordering on the items, and has responsive preferences on bundles of items. This means that, at each point in the picking sequence, there is a single remaining item which is the "best item" for the agent. An agent is called sincere (truthful) if, at each point, he picks his best item. If agents have complete information on each other's preferences (as is common among parties), it may not be rational for them to choose truthfully; it may be better for them to make sophisticated (strategic) choices. Thus, the picking sequence induces a sequential game and it is interesting to analyze its subgame-perfect equilibrium. Several results are proved:

With two agents, both truthful and strategic choices lead to Pareto efficient allocations. Moreover, the game is monotonic in the following sense: an agent is always better-off if one or more of his positions in the sequence are improved (e.g, Alice is better-off in the sequence ABBA than in BABA). Both properties are still true with three or more agents, as long as they make truthful choices.
With three or more agents who make strategic choices, a picking-sequence might lead to inefficient allocations (i.e, the subgame-perfect equilibrium might not be Pareto-efficient).
With three or more agents who make strategic choices, the game might be non-monotonic, i.e, an agent might do worse by picking earlier in the sequence.^[5]^{: 210–212}
For two agents, there exists a simple modification of the picking-sequence which is a truthful mechanism - picking items truthfully is a dominant strategy. Therefore, there exists a subgame-perfect equilibrium which is Pareto optimal, and the game is monotonic.

Determining the picking-sequence

Given the agents' different rights, what would be a fair picking sequence? Brams^[5]^{: 202–206} suggests to use divisor methods, similar to the ones used for apportionment of congress seats among states. The two most commonly used methods are the ones proposed by Daniel Webster and Thomas Jefferson. Both methods start in the same way:

Calculate the divisor - the sum of the entitlements divided by the number of items (e.g, if the sum of all entitlements is 201, and there are 15 items to share, then the divisor is 201/15).
Calculate the quota - the fractional number of items each agent is entitled to. This is the entitlement divided by the divisor (e.g, for an agent with an entitlement of 10 out of 201, the quota is 10*15/201 ~ 0.75 items).

Competitive equilibrium

Picking sequences can be used to find allocations that satisfy a strong fairness and efficiency condition called competitive equilibrium.^[7]

Related Research Articles

Fair division is the problem in game theory of dividing a set of resources among several people who have an entitlement to them so that each person receives their due share. That problem arises in various real-world settings such as division of inheritance, partnership dissolutions, divorce settlements, electronic frequency allocation, airport traffic management, and exploitation of Earth observation satellites. It is an active research area in mathematics, economics, dispute resolution, etc. The central tenet of fair division is that such a division should be performed by the players themselves, maybe using a mediator but certainly not an arbiter as only the players really know how they value the goods.

Adjusted Winner (AW) is a procedure for envy-free item allocation. Given two agents and some goods, it returns a partition of the goods between the two agents with the following properties:

Envy-freeness: Each agent believes that his share of the goods is at least as good as the other share;
Equitability: The "relative happiness levels" of both agents from their shares are equal;
Pareto-optimality: no other allocation is better for one agent and at least as good for the other agent;
At most one good has to be shared between the agents.

Entitlement in fair division describes that proportion of the resources or goods to be divided that a player can expect to receive. In many fair division settings, all agents have equal entitlements, which means that each agent is entitled to 1/n of the resource. But there are practical settings in which agents have different entitlements. Some examples are:

Fair cake-cutting is a kind of fair division problem. The problem involves a heterogeneous resource, such as a cake with different toppings, that is assumed to be divisible – it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible. The division should be unanimously fair – each person should receive a piece believed to be a fair share.

Fair item allocation is a kind of the fair division problem in which the items to divide are discrete rather than continuous. The items have to be divided among several partners who potentially value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:

Utilitarian cake-cutting is a rule for dividing a heterogeneous resource, such as a cake or a land-estate, among several partners with different cardinal utility functions, such that the sum of the utilities of the partners is as large as possible. It is a special case of the utilitarian social choice rule. Utilitarian cake-cutting is often not "fair"; hence, utilitarianism is often in conflict with fair cake-cutting.

Resource monotonicity is a principle of fair division. It says that, if there are more resources to share, then all agents should be weakly better off; no agent should lose from the increase in resources. The RM principle has been studied in various division problems.

Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent.

The undercut procedure is a procedure for fair item assignment between two people. It provably finds a complete envy-free item assignment whenever such assignment exists. It was presented by Brams and Kilgour and Klamler and simplified and extended by Aziz.

The AL procedure is a procedure for fair item assignment between two people. It finds an envy-free item assignment of a subset of the items. Moreover, the resulting allocation is Pareto efficient in the following sense: there is no other envy-free allocation which is better for one person and not worse for the other person.

Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is a procedure for fair item assignment. It was developed by Eric Budish.

The Decreasing Demand procedure is a procedure for fair item allocation. It yields a Pareto-efficient division that maximizes the rank of the agent with the lowest rank. This corresponds to the Rawlsian justice criterion of taking care of the worst-off agent.

Random priority (RP), also called Random serial dictatorship (RSD), is a procedure for fair random assignment - dividing indivisible items fairly among people.

A simultaneous eating algorithm(SE) is an algorithm for allocating divisible objects among agents with ordinal preferences. "Ordinal preferences" means that each agent can rank the items from best to worst, but cannot (or does not want to) specify a numeric value for each item. The SE allocation satisfies SD-efficiency - a weak ordinal variant of Pareto-efficiency (it means that the allocation is Pareto-efficient for at least one vector of additive utility functions consistent with the agents' item rankings).

Strategic fair division is the branch of fair division in which the participants are assumed to hide their preferences and act strategically in order to maximize their own utility, rather than playing sincerely according to their true preferences.

Truthful cake-cutting is the study of algorithms for fair cake-cutting that are also truthful mechanisms, i.e., they incentivize the participants to reveal their true valuations to the various parts of the cake.

Population monotonicity (PM) is a principle of consistency in allocation problems. It says that, when the set of agents participating in the allocation changes, the utility of all agents should change in the same direction. For example, if the resource is good, and an agent leaves, then all remaining agents should receive at least as much utility as in the original allocation.

Fair allocation of items and money is a class of fair item allocation problems in which, during the allocation process, it is possible to give or take money from some of the participants. Without money, it may be impossible to allocate indivisible items fairly. For example, if there is one item and two people, and the item must be given entirely to one of them, the allocation will be unfair towards the other one. Monetary payments make it possible to attain fairness, as explained below.

Ordinal Pareto efficiency refers to several adaptations of the concept of Pareto-efficiency to settings in which the agents only express ordinal utilities over items, but not over bundles. That is, agents rank the items from best to worst, but they do not rank the subsets of items. In particular, they do not specify a numeric value for each item. This may cause an ambiguity regarding whether certain allocations are Pareto-efficient or not. As an example, consider an economy with three items and two agents, with the following rankings:

References

↑ Steven Brams and Alan D. Taylor (1999–2000). ' The Win-Win Solution: Guaranteeing Fair Shares to Everybody. New York: W. W. Norton.
1 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 )
↑ A general elicitation-free protocol for allocating indivisible goods. doi:10.5591/978-1-57735-516-8/ijcai11-024.
↑ A social welfare optimal sequential allocation procedure. AAAI-13. 2013.
1 2 3 Chapter 9 in Steven J. Brams (2008). Mathematics and Democracy: Designing Better Voting and Fair-Division Procedures. Princeton, NJ: Princeton University Press. ISBN 9780691133218.. Adapted from Brams, Steven J.; Kaplan, Todd R. (2004). "Dividing the Indivisible". Journal of Theoretical Politics. 16 (2): 143. doi:10.1177/0951629804041118. hdl:10036/26974. S2CID 154854134.
↑ O'Leary, Brendan; Grofman, Bernard; Elklit, Jorgen (2005). "Divisor Methods for Sequential Portfolio Allocation in Multi-Party Executive Bodies: Evidence from Northern Ireland and Denmark". American Journal of Political Science. 49: 198–211. doi:10.1111/j.0092-5853.2005.00118.x. S2CID 547519.
↑ Segal-Halevi, Erel (2020-02-20). "Competitive equilibrium for almost all incomes: existence and fairness". Autonomous Agents and Multi-Agent Systems. 34 (1): 26. arXiv: 1705.04212 . doi:10.1007/s10458-020-09444-z. ISSN 1573-7454. S2CID 254232282.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Steven Brams and Alan D. Taylor (1999–2000). ' The Win-Win Solution: Guaranteeing Fair Shares to Everybody. New York: W. W. Norton.

[handbook-2] 1 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 )

[bl11-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.

[b08-5] 1 2 3 Chapter 9 in Steven J. Brams (2008). Mathematics and Democracy: Designing Better Voting and Fair-Division Procedures. Princeton, NJ: Princeton University Press. ISBN 9780691133218.. Adapted from Brams, Steven J.; Kaplan, Todd R. (2004). "Dividing the Indivisible". Journal of Theoretical Politics. 16 (2): 143. doi:10.1177/0951629804041118. hdl:10036/26974. S2CID 154854134.

[6] O'Leary, Brendan; Grofman, Bernard; Elklit, Jorgen (2005). "Divisor Methods for Sequential Portfolio Allocation in Multi-Party Executive Bodies: Evidence from Northern Ireland and Denmark". American Journal of Political Science. 49: 198–211. doi:10.1111/j.0092-5853.2005.00118.x. S2CID 547519.

[7] Segal-Halevi, Erel (2020-02-20). "Competitive equilibrium for almost all incomes: existence and fairness". Autonomous Agents and Multi-Agent Systems. 34 (1): 26. arXiv: 1705.04212 . doi:10.1007/s10458-020-09444-z. ISSN 1573-7454. S2CID 254232282.

[1]

[2]

[3]

[4]

[5]

[6]

[7]