Round-robin item allocation

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 he 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 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:

  1. Number the people arbitrarily from 1 to ;
  2. While there are unassigned objects:
    • Let each person from 1 to pick an unassigned object.

It is assumed that each person in his turn picks an unassigned object with a highest value among the remaining objects.

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) time per agent) and then pick an object in time O(1).

The final allocation is EF1 - envy-free except one object. This means that, for every pair of agents i and j, if at most one object is removed from the bundle of j, then i does not envy j.

Proof:[1] For every agent , divide the selections made by the agents to sub-sequences: the first subsequence starts at agent 1 and ends at agent ; the latter subsequences start at and end at . In the latter subsequences, agent chooses first, so he can choose his best item, so he does not envy any other agent. Agent can envy only one of the agents , and the envy comes only from an item they selected in the first subsequence. If this item is removed, agent 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.

Additivity requirement

The round-robin protocol requires additivity, since it requires each agent to pick his "best item" without knowing what other items he is 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.

Extensions

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.[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 an 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.[3]

See also

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.

References

  1. Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016). The Unreasonable Fairness of Maximum Nash Welfare (PDF). Proceedings of the 2016 ACM Conference on Economics and Computation - EC '16. p. 305. doi:10.1145/2940716.2940726. ISBN 9781450339360.
  2. Haris Aziz, Ioannis Caragiannis, Ayumi Igarashi, Toby Walsh (2019). "Fair Allocation of Indivisible Goods and Chores" (PDF). IJCAI 2019 conference.CS1 maint: multiple names: authors list (link)
  3. Biswas, Arpita; Barman, Siddharth (2018-07-13). "Fair division under cardinality constraints". Proceedings of the 27th International Joint Conference on Artificial Intelligence. IJCAI'18. Stockholm, Sweden: AAAI Press: 91–97. arXiv:1804.09521. ISBN 978-0-9992411-2-7.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.