Round robin is a procedure for fair item allocation. It can be used to allocate several indivisible items among several people, such that the allocation is "almost" envy-free: each agent believes that the bundle they received is at least as good as the bundle of any other agent, when at most one item is removed from the other bundle. In sports, the round-robin procedure is called a draft.
There are m objects to allocate, and n people ("agents") with equal rights to these objects. Each person has different preferences over the objects. The preferences of an agent are given by a vector of values - a value for each object. It is assumed that the value of a bundle for an agent is the sum of the values of the objects in the bundle (in other words, the agents' valuations are an additive set function on the set of objects).
The protocol proceeds as follows:
n
n
It is assumed that each person in their turn picks an unassigned object with a highest value among the remaining objects.
The round-robin protocol requires additivity, since it requires each agent to pick their "best item" without knowing what other items they are going to get; additivity of valuations guarantees that there is always a "best item" (an item with a highest value). In other words, it assumes that the items are independent goods. The additivity requirement can be relaxed to weak additivity.
The round-robin protocol is very simple to execute: it requires only m steps. Each agent can order the objects in advance by descending value (this takes
O(mlogm)
O(1)
The final allocation is EF1 - envy-free up to one object. This means that, for every pair of agents
i
j
j
i
j
Proof:[1] For every agent
i
i-1
i
i-1
i
i
1,...,i-1
i
Round-robin guarantees approximate fairness, but the outcome might be inefficient. As a simple example, suppose the valuations are:
| z | y | x | w | v | u | ||
|---|---|---|---|---|---|---|---|
| Alice's value: | 12 | 10 | 8 | 7 | 4 | 1 | |
| George's value: | 19 | 16 | 8 | 6 | 5 | 1 |
(zxv,ywu)
(yxw,zvu)
An alternative algorithm, which may attain a higher social welfare, is the Iterated maximum-weight matching algorithm.[2] In each iteration, it finds a maximum-weight matching in the bipartite graph in which the nodes are the agents and the items, and the edge weights are the agents' values to the items. In the above example, the first matching is
(y,z)
(w,x)
(u,v)
(ywu,zxv)
Note that even iterated maximum-weight matching does not guarantee Pareto efficiency, as the above allocation is dominated by (xwv, zyu) with utilities (19,36).
The round-robin algorithm can be used to fairly allocate items among groups. In this setting, all members in each group consume the same bundle, but different members in each group may have different preferences over the items. This raises the question of how each group should decide which item to choose in its turn. Suppose that the goal of each group is to maximize the fraction of its members that are "happy", that is, feel that the allocation is fair (according to their personal preferences). Suppose also that the agents have binary additive valuations, that is, each agent values each item at either 1 ("approve") or 0 ("disapprove"). Then, each group can decide what item to pick using weighted approval voting:[3]
The resulting algorithm is called RWAV (round-robin with weighted approval voting). The weight function w(r,s) is determined based on an auxiliary function B(r,s), defined by the following recurrence relation:
B(r,s):=1~~if~~s\leq0;
B(r,s):=0~~if~~0<s~and~r<s;
B(r,s):=min[
| 1 | |
| 2 |
[B(r-1,s)+B(r-1,s-1)] , B(r-2,s-1) ]~~otherwise
Intuitively, B(r,s) of an agent represents the probability that the agent is happy with the final allocation. If s ≤ 0, then by definition this probability is 1: the agent needs no more goods to be happy. If 0<s and r<s, then this probability is 0: the agent cannot be happy, since they need more goods than are available. Otherwise, B(r,s) is the average between B(r-1,s) - when the other group takes a good wanted by the agent, and B(r-1,s-1) - when the agent's group takes a good wanted by the agent. The term B(r-2,s-1) represents the situation when both groups take a good wanted by the agent. Once B(r,s) is computed, the weight function w is defined as follows:
When using this weight function and running RWAV with two groups, the fraction of happy members in group 1 is at least B(r, s(r)), and the fraction of happy members in group 2 is at least B(r-1, s(r)). The function s(r) is determined by the fairness criterion. For example, for 1-out-of-3 maximin-share fairness, s(r) = floor(r/3). The following table shows some values of the function B, with the values of B(r-1, floor(r/3)) boldfaced:w(r,s):=B(r,s)-B(r-1,s)
| -1 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | ||
| 0 | 1 | 0.500 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | |
| 1 | 1 | 0.750 | 0.375 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | |
| 2 | 1 | 0.875 | 0.625 | 0.313 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | |
| 3 | 1 | 0.938 | 0.781 | 0.547 | 0.273 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | |
| 4 | 1 | 0.969 | 0.875 | 0.711 | 0.492 | 0.246 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | |
| 5 | 1 | 0.984 | 0.930 | 0.820 | 0.656 | 0.451 | 0.226 | 0.000 | 0.000 | 0.000 | 0.000 | |
| 6 | 1 | 0.992 | 0.961 | 0.891 | 0.773 | 0.612 | 0.419 | 0.209 | 0.000 | 0.000 | 0.000 | |
| 7 | 1 | 0.996 | 0.979 | 0.935 | 0.854 | 0.733 | 0.576 | 0.393 | 0.196 | 0.000 | 0.000 | |
| 8 | 1 | 0.998 | 0.988 | 0.961 | 0.908 | 0.820 | 0.698 | 0.546 | 0.371 | 0.185 | 0.000 | |
| 9 | 1 | 0.999 | 0.994 | 0.978 | 0.943 | 0.882 | 0.790 | 0.668 | 0.519 | 0.352 | 0.176 | |
| 10 | 1 | 1.000 | 0.997 | 0.987 | 0.965 | 0.923 | 0.857 | 0.762 | 0.641 | 0.497 | 0.336 |
From this one can conclude that the RWAV algorithm guarantees that, in both groups, at least 75% of the members feel that the allocation is 1-out-of-3 MMS fair.
1. The round-robin protocol guarantees EF1 when the items are goods (- valued positively by all agents) and when they are chores (- valued negatively by all agents). However, when there are both goods and chores, it does not guarantee EF1. An adaptation of round-robin called double round-robin guarantees EF1 even with a mixture of goods and chores.[4]
2. When agents have more complex cardinality constraints (i.e., the items are divided into categories, and for each category of items, there is an upper bound on the number of items each agent can get from this category), round-robin might fail. However, combining round-robin with the envy-graph procedure gives an algorithm that finds allocations that are both EF1 and satisfy the cardinality constraints.[5]
3. When agents have different weights (i.e., agents have different entitlement for the total items), a generalized round-robin protocol called weighted round-robin guarantees EF1 when the items are goods (- valued positively by all agents)[6] and the reversed weighted round-robin guarantees EF1 when the items are chores (-valued negatively by all agents).[7]
Round-robin is a special case of a picking sequence.
Round-robin protocols are used in other areas besides fair item allocation. For example, see round-robin scheduling and round-robin tournament.