Round robin is a procedure for fair item allocation.
In sports, the round-robin procedure is called a draft.
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 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
Round-robin guarantees approximate fairness, but the outcome might be inefficient.
As a simple example, suppose the valuations are: Round-robin, when Alice chooses first, yields the allocation
[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.
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.
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).
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 term B(r-2,s-1) represents the situation when both groups take a good wanted by the agent.
The following table shows some values of the function B, with the values of B(r-1, floor(r/3)) boldfaced: 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.
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, combining round-robin with the envy-graph procedure gives an algorithm that finds allocations that are both EF1 and satisfy the cardinality constraints.
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).
Round-robin protocols are used in other areas besides fair item allocation.