Round-robin item allocation

Last updated

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.

Contents

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

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

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 they can choose their best item, so they do 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.

Efficiency considerations

Round-robin guarantees approximate fairness, but the outcome might be inefficient. As a simple example, suppose the valuations are:

zyxwvu
Alice's value:12108741
George's value:19168651

Round-robin, when Alice chooses first, yields the allocation with utilities (24,23) and social welfare 47. It is not Pareto efficient, since it is dominated e.g. y the allocation , with utilities (25,25).

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 , the second is , and the third is . The total allocation is 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).

Round-robin for groups

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:

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)). [3] :Lemma 3.6 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:

r-s ↓ s →012345678910
-10.0000.0000.0000.0000.0000.0000.0000.0000.0000.000
010.5000.0000.0000.0000.0000.0000.0000.0000.0000.000
110.7500.3750.0000.0000.0000.0000.0000.0000.0000.000
210.8750.6250.3130.0000.0000.0000.0000.0000.0000.000
310.9380.7810.5470.2730.0000.0000.0000.0000.0000.000
410.9690.8750.7110.4920.2460.0000.0000.0000.0000.000
510.9840.9300.8200.6560.4510.2260.0000.0000.0000.000
610.9920.9610.8910.7730.6120.4190.2090.0000.0000.000
710.9960.9790.9350.8540.7330.5760.3930.1960.0000.000
810.9980.9880.9610.9080.8200.6980.5460.3710.1850.000
910.9990.9940.9780.9430.8820.7900.6680.5190.3520.176
1011.0000.9970.9870.9650.9230.8570.7620.6410.4970.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.

Extensions

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]

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.

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, and dispute resolution. The central tenet of fair division is that such a division should be performed by the players themselves, without the need for external arbitration, as only the players themselves really know how they value the goods.

<span class="mw-page-title-main">Adjusted winner procedure</span> Method of fairly dividing property

Adjusted Winner (AW) is an algorithm for envy-free item allocation. Given two parties and some discrete goods, it returns a partition of the goods between the two parties that is:

  1. Envy-free: Each party believes their share of the goods is as good as or better than their opponent's;
  2. Equitable: The "relative happiness levels" of both parties from their shares are equal;
  3. Pareto-optimal: no other allocation is better for one party and still at least as good for the other party; and
  4. Involves splitting at most one good between the parties.

In economics, philosophy, and social choice theory, a person's entitlement refers to the value of goods they are owed or deserve, i.e. the total value of the goods or resources that a player would ideally receive. For example, in party-list proportional representation, a party's seat entitlement is equal to its share of the vote, times the number of seats in the legislature.

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:

Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by any other agent. In other words, no person should feel envy.

Rental harmony is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem and room-assignment-rent-division are alternative names to the same problem.

Fisher market is an economic model attributed to Irving Fisher. It has the following ingredients:

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 envy-graph procedure is a procedure for fair item allocation. It can be used by several people who want to divide among them several discrete items, such as heirlooms, sweets, or seats in a class.

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).

Maximin share (MMS) is a criterion of fair item allocation. Given a set of items with different values, the 1-out-of-n maximin-share is the maximum value that can be gained by partitioning the items into parts and taking the part with the minimum value. An allocation of items among agents with different valuations is called MMS-fair if each agent gets a bundle that is at least as good as his/her 1-out-of-n maximin-share. MMS fairness is a relaxation of the criterion of proportionality - each agent gets a bundle that is at least as good as the equal split ( of every resource). Proportionality can be guaranteed when the items are divisible, but not when they are indivisible, even if all agents have identical valuations. In contrast, MMS fairness can always be guaranteed to identical agents, so it is a natural alternative to proportionality even when the agents are different.

When allocating objects among people with different preferences, two major goals are Pareto efficiency and fairness. Since the objects are indivisible, there may not exist any fair allocation. For example, when there is a single house and two people, every allocation of the house will be unfair to one person. Therefore, several common approximations have been studied, such as maximin-share fairness (MMS), envy-freeness up to one item (EF1), proportionality up to one item (PROP1), and equitability up to one item (EQ1). The problem of efficient approximately fair item allocation is to find an allocation that is both Pareto-efficient (PE) and satisfies one of these fairness notions. The problem was first presented at 2016 and has attracted considerable attention since then.

Egalitarian item allocation, also called max-min item allocation is a fair item allocation problem, in which the fairness criterion follows the egalitarian rule. The goal is to maximize the minimum value of an agent. That is, among all possible allocations, the goal is to find an allocation in which the smallest value of an agent is as large as possible. In case there are two or more allocations with the same smallest value, then the goal is to select, from among these allocations, the one in which the second-smallest value is as large as possible, and so on. Therefore, an egalitarian item allocation is sometimes called a leximin item allocation.

Proportional item allocation is a fair item allocation problem, in which the fairness criterion is proportionality - each agent should receive a bundle that they value at least as much as 1/n of the entire allocation, where n is the number of agents.

In economics and computer science, Fractional Pareto efficiency or Fractional Pareto optimality (fPO) is a variant of Pareto efficiency used in the setting of fair allocation of discrete objects. An allocation of objects is called discrete if each item is wholly allocated to a single agent; it is called fractional if some objects are split among two or more agents. A discrete allocation is called Pareto-efficient (PO) if it is not Pareto-dominated by any discrete allocation; it is called fractionally Pareto-efficient (fPO) if it is not Pareto-dominated by any discrete or fractional allocation. So fPO is a stronger requirement than PO: every fPO allocation is PO, but not every PO allocation is fPO.

Online fair division is a class of fair division problems in which the resources, or the people to whom they should be allocated, or both, are not all available when the allocation decision is made. Some situations in which not all resources are available include:

In computer science and operations research, the envy minimization problem is the problem of allocating discrete items among agents with different valuations over the items, such that the amount of envy is as small as possible.

Fair division among groups is a class of fair division problems, in which the resources are allocated among groups of agents, rather than among individual agents. After the division, all members in each group consume the same share, but they may have different preferences; therefore, different members in the same group might disagree on whether the allocation is fair or not. Some examples of group fair division settings are:

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.

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. Brustle, Johannes; Dippel, Jack; Narayan, Vishnu V.; Suzuki, Mashbat; Vetta, Adrian (2020-07-13). "One Dollar Each Eliminates Envy". Proceedings of the 21st ACM Conference on Economics and Computation. EC '20. Virtual Event, Hungary: Association for Computing Machinery. pp. 23–39. arXiv: 1912.02797 . doi:10.1145/3391403.3399447. ISBN   978-1-4503-7975-5. S2CID   208637311.
  3. 1 2 Segal-Halevi, Erel; Suksompong, Warut (2019-12-01). "Democratic fair allocation of indivisible goods". Artificial Intelligence. 277: 103167. arXiv: 1709.02564 . doi:10.1016/j.artint.2019.103167. ISSN   0004-3702. S2CID   203034477.
  4. Haris Aziz, Ioannis Caragiannis, Ayumi Igarashi, Toby Walsh (2019). "Fair Allocation of Indivisible Goods and Chores" (PDF). IJCAI 2019 conference.{{cite web}}: CS1 maint: multiple names: authors list (link)
  5. 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.
  6. Chakraborty, Mithun; Igarashi, Ayumi; Suksompong, Warut; Zick, Yair (2021-08-16). "Weighted Envy-freeness in Indivisible Item Allocation". ACM Transactions on Economics and Computation. ACm: 1–39.
  7. Xiaowei Wu, Cong Zhang, Shengwei Zhou (2023). "Weighted EF1 Allocations for Indivisible Chores". EC 2023conference.{{cite web}}: CS1 maint: multiple names: authors list (link)