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.
Setting 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).
Description The protocol proceeds as follows:
Number the people arbitrarily from 1 to n {\displaystyle n} ; While there are unassigned objects: Let each person from 1 to n {\displaystyle n} pick an unassigned object. It is assumed that each person in their turn picks an unassigned object with a highest value among the remaining objects.
Additivity requirement 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.
Properties 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 ( m log m ) {\displaystyle O(m{\text{log}}m)} time per agent) and then pick an object in time O ( 1 ) {\displaystyle O(1)} . The final allocation is EF1 - envy-free up to one object. This means that, for every pair of agents i {\displaystyle i} and j {\displaystyle j} , if at most one object is removed from the bundle of j {\displaystyle j} , then i {\displaystyle i} does not envy j {\displaystyle j} .
Proof: For every agent i {\displaystyle i} , divide the selections made by the agents to sub-sequences: the first subsequence starts at agent 1 and ends at agent i − 1 {\displaystyle i-1} ; the latter subsequences start at i {\displaystyle i} and end at i − 1 {\displaystyle i-1} . In the latter subsequences, agent i {\displaystyle i} chooses first, so they can choose their best item, so they do not envy any other agent. Agent i {\displaystyle i} can envy only one of the agents 1 , . . . , i − 1 {\displaystyle 1,...,i-1} , and the envy comes only from an item they selected in the first subsequence. If this item is removed, agent i {\displaystyle i} does not envy. Additionally, round-robin guarantees that each agent receives the same number of items (m/n, if m is divisible by n), or almost the same number of items (if m is not divisible by n). Thus, it is useful in situations with simple cardinality constraints, such as: assigning course-seats to students where each student must receive the same number of courses.
Efficiency considerations 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 ( z x v , y w u ) {\displaystyle (zxv,ywu)} with utilities (24,23) and social welfare 47. It is not Pareto efficient, since it is dominated e.g. y the allocation ( y x w , z v u ) {\displaystyle (yxw,zvu)} , with utilities (25,25). An alternative algorithm, which may attain a higher social welfare, is the Iterated maximum-weight matching algorithm. 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 ) {\displaystyle (y,z)} , the second is ( w , x ) {\displaystyle (w,x)} , and the third is ( u , v ) {\displaystyle (u,v)} . The total allocation is ( y w u , z x v ) {\displaystyle (ywu,zxv)} with utilities (18,32); the social welfare (- the sum of utilities) is 50, which is higher than in the round-robin allocation. 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).
… excerpt ends here. Continue reading the full article.
