## The Constrained Round Robin Algorithm for Fair and E GLYPH&lt;14&gt; cient Allocation

## Haris Aziz

## Xin Huang

UNSW Sydney and Data61 CSIRO haris.aziz@unsw.edu.au

## Nicholas Mattei

Tulane University nsmattei@tulane.edu

## Abstract

We consider a multi-agent resource allocation setting that models the assignment of papers to reviewers. A recurring issue in allocation problems is the compatibility of welfare e / GLYPH&lt;14&gt; ciency and fairness. Given an oracle to find a welfareachieving allocation, we embed such an oracle into a flexible algorithm called the Constrained Round Robin (CRR) algorithm, that achieves the required welfare level. Our algorithm also allows the system designer to lower the welfare requirements in order to achieve a higher degree of fairness. If the welfare requirement is lowered enough, a strengthening of envy-freeness up to one item is guaranteed. Hence, our algorithm can be viewed as a computationally e GLYPH&lt;14&gt; cient way to interpolate between welfare and approximate envy-freeness in allocation problems.

## Introduction

In multi-agent resource allocation, two orthogonal concerns are e GLYPH&lt;14&gt; ciency , e.g., Pareto optimality or maximizing the sum of utilities, and fairness , e.g., envy-freeness. In certain deployed applications, such as assigning papers to reviewers, the primary focus is on e GLYPH&lt;14&gt; ciency. But when the agents' preferences are highly correlated, there may be many di GLYPH&lt;11&gt; erent e GLYPH&lt;14&gt; cient allocations, most of which are not fair. Indeed, fairness concerns pose their own challenges. In several settings concerning indivisible resources, a fair allocation may not exist, and if it does exist - it might be hard to compute and might fail to satisfy e GLYPH&lt;14&gt; ciency requirements.

Several recent works focus on a particular combination of e GLYPH&lt;14&gt; ciency and fairness - finding an allocation that is both Pareto-optimal (PO) and envy-free except one item (EF1) . Caragiannis et al. (2016) prove that any allocation maximizing the Nash welfare (the product of utilities) is both PO and EF1, and Barman, Murthy, and Vaish (2018) present a pseudo-polynomial-time algorithm for finding a PO and EF1 allocation. These fascinating results are still limited in two ways: (1) They do not provide any guarantee for more popular welfare goals such as utilitarian maximality (maximizing the sum of utilities) or rank-maximality . (2) They work only for the basic setting in which all utilities are weakly-positive (i.e., all items are goods), there is a single copy of each item, and there are no constraints on the number of items given

Copyright c GLYPH&lt;13&gt; 2020, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

The Chinese University of Hong Kong xhuang@cse.cuhk.edu.hk

## Erel Segal-Halevi

Ariel University erelsgl@gmail.com to each agent. Thus they do not apply to practical problems such as assigning conference-papers to reviewers in which there are capacity constraints on both reviewers and papers and where agents may have negative utilities for the tasks.

The central research question we examine is the following one: 'how can we find fair allocations that guarantee a specified level of welfare e / GLYPH&lt;14&gt; ciency?'

Our Contribution. We consider a general allocation problem in which the utility of each item for each agent can be any real number (positive, negative, or zero), and there may be capacity constraints on both agents and items. We focus on EF1 as the predominant fairness notion. We consider utilitarian-maximality (UM) and rank-maximality (RM) as the predominant e GLYPH&lt;14&gt; ciency notions, though our approach can handle other e GLYPH&lt;14&gt; ciency notions.

Ideally, given a fairness and an e GLYPH&lt;14&gt; ciency requirement, we would like to first decide whether there exists an allocation that satisfies both requirements. If no such allocation exists, we would like to find a fair allocation that is as e GLYPH&lt;14&gt; cient as possible. However, we show that both these goals are computationally hard even for three agents: (1) deciding whether there exists an allocation that is both EF1 and UM, or both EF1 and RM, is NP-complete; (2) computing an allocation that is UM or RM within the set of EF1 allocations is NPhard.

In view of these issues, we present a general algorithm that finds an e GLYPH&lt;14&gt; cient allocation in a way that is provably fair for important classes of utility functions such as identical utilities. It is inspired by the round robin (RR) protocol for item allocation: In the RR protocol, each agent gets turns in a round-robin manner and in turn picks an item. Our algorithm is called Constrained Round Robin (CRR) : it tries to find an allocation in a round-robin manner, under the constraint that the final allocation must satisfy a given e GLYPH&lt;14&gt; ciency goal. For a given e GLYPH&lt;14&gt; ciency goal W, W-CRR is the corresponding CRR algorithm specified with respect to W and it returns an allocation satisfying W. In the special case in which W is null (i.e, no welfare goal is imposed), we show that W-CRR finds an EF1 allocation for all utilities consistent with the ordinal preferences. We call this novel strengthening of EF1 necessary EF1 (NEF1) .

The generality of CRR allows the system designer to gradually increase the welfare requirements by modifying

W, as long as the resulting allocation is su GLYPH&lt;14&gt; ciently fair for his her needs. W-CRR can be considered a practical engi-/ neering approach for interpolating between welfare and fairness, re-using existing algorithms and implementations for finding allocations that achieve a target welfare level. Using extensive simulation experiments on both real-world and synthetic data, we examine W-CRR where W is utilitarianmaximality or rank-maximality, and show that in many settings W-CRR produces fairer allocations than several existing algorithms for maximum Nash welfare or maximum Egalitarian welfare.

## Related Work

Bouveret, Chevaleyre, and Maudet (2016) survey the main algorithms and considerations in fair item allocation, including fairness and welfare considerations.

A flexible approach to achieve varying levels of utilitarian and egalitarian welfare is applying ordered weighted averages over the agents' total utilities (Yager 1988). The approach smoothly interpolates between utilitarian welfare and egalitarian welfare but it is computationally intractable. There is also no known connection with EF1.

Nash welfare based approaches have been proposed to achieve both Pareto optimality and EF1 (Caragiannis et al. 2016), but computing it is NP-hard. When there are additional side constraints such as agents getting an equal number of items, then EF1 is not implied by an allocation maximizing Nash welfare. Lian et al. (2018) proposed the SumOWA Maximizing rule that uses ordered weighted averaging over the agent's individual utilities for items . They experimentally showed that the approach can reduce certain measures of inequality. They did not establish whether the approach achieves some formal notion of fairness for any of the ordered vectors. The papers discussed assume that the agents' utilities are positive. On the other hand, W-CRR, in general, can cater for positive or negative utilities.

Garg et al. (2010) considered the problem of assigning papers to referees and focused on maximizing the utility of the worst o GLYPH&lt;11&gt; agent. They also considered rank maximal allocations when considering reviewer assignments. Rank maximality has been considered as a criterion when computing desirable allocations (Paluch 2013).

Biswas and Barman (2018) considered fairness issues when there are upper cardinality constraints on the categories of items in agents' allocations. They did not consider welfare measures.

Segal-halevi, Aziz, and Hassidim (2017) considered a sub-class of additive valuations and characterized the conditions under which allocations are necessarily envy-free for all valuations in the sub-class. Segal-Halevi (2018) considered fairness-welfare interpolation in the division of a heterogeneous resource ('cake-cutting'). The results crucially depend on the divisibility of the cake. Caragiannis et al. (2012) studied the fairness-welfare tradeo GLYPH&lt;11&gt; through the lens of the price of fairness -the ratio between the maximum welfare of an arbitrary allocation and the maximum welfare of a fair allocation.

The complexity of computing a Pareto optimal and EF1 allocation is an open question in the literature (Caragiannis et al. 2016; Barman, Murthy, and Vaish 2018). We show that strengthening PO to maximum welfare immediately leads to computational hardness.

## Setting

## Agents and Utilities

An allocation problem is a tuple ( N O ; ; % ; u c ; ) such that N = f 1 ; : : : ; n g is a set of agents, O = f o 1 ; : : : ; om g is a set of items and the preference profile % = ( % 1 ; : : : ; % n ) specifies for each agent i his complete and transitive preference % i over O . Agents may be indi GLYPH&lt;11&gt; erent among items, i.e., they provide weak rankings of the items. Hence, we denote % i : E i 1 ; : : : ; E ki i for each agent i with equivalence classes in decreasing order of preferences. We assume that each % i is induced by a utility function ui : O ! R . In general the utility of an item can be positive, negative or zero. Some of our results apply only when all utilities have the same sign (all positive or all negative). Agents are assumed to have additive utility so that ui ( O 0 ) = P o 2 O 0 ui ( o ).

When ui is not known to the algorithm (for example, when the user interface does not allow the agents to submit their cardinal utilities), we can still take a cardinal approach by assuming that agent's utility functions are derived by some scoring rule , that ascribes a utility for an item being in a given rank in the preference list. For example, in Borda scoring , an agent with strict preferences over m items gives utility m GLYPH&lt;0&gt; i + 1 for the i -th ranked item (see e.g., (Baumeister et al. 2017)).

An allocation p is a function p : N ! 2 O assigning each agent a bundle of items. Typically it is assumed that each item is allocated exactly once. However, we do not impose such a restriction, since we want to capture scenarios such as reviewer assignment, in which a paper is reviewed by multiple agents.

There is a capacity function c , which specifies for each agent i , the values c i and ci , which are the minimum and maximum number of items that should be allocated to i . Similarly, c specifies for each item o , the values c o and co , which are the minimum and maximum number of agents it may be allocated to. Some of our results focus on the special case where for all o o ; 0 2 O co , = c o = co 0 = c o 0 , and for all i ; i 0 2 N ci , = ci 0 and c i = c i 0 and ci GLYPH&lt;0&gt; c i = 1. The assumptions are motivated by the conference reviewer assignment problem in which each paper is reviewed by the same number of agents and all reviewers review almost the same number of papers.

We denote the set of all feasible allocations (all allocations consistent with the capacity constraints) by A . An allocation p 2 A is called balanced if j ( j p i ( ) j GLYPH&lt;0&gt; j p j ( ) ) j j GLYPH&lt;20&gt; 1 for all i ; j 2 N .

The set of all utility functions consistent with % i is denoted by U ( % i ). In this paper we do not consider strategic manipulations - we assume that all agents truthfully report their valuations.

## Fairness

An allocation p is envy-free (EF) if ui ( p i ( )) GLYPH&lt;21&gt; ui ( p j ( )) for all i ; j 2 N . Although EF is often viewed as the gold-standard for fairness, there may not exist an allocation that is EF. Furthermore, checking whether such an allocation exists is NPcomplete (see e.g., (Bouveret and Lemaˆ ıtre 2015)).

An allocation p is envy-free up to one item (EF1) if for all i ; j 2 N , there exists a subset O 0 GLYPH&lt;18&gt; O of cardinality at most 1, such that either ui ( p i ( ) n O 0 ) GLYPH&lt;21&gt; ui ( p j ( )) or ui ( p i ( )) GLYPH&lt;21&gt; ui ( p j ( ) n O 0 ). Note that this definition makes sense for both positive and negative utilities.

An allocation p satisfies necessary envy-freeness up to one item (NEF1) if for all i ; j 2 N , there exists a subset O 0 GLYPH&lt;18&gt; O of cardinality at most 1, such that for all ui 2 U ( % i ), either ui ( p i ( ) n O 0 ) GLYPH&lt;21&gt; ui ( p j ( )) or ui ( p i ( )) GLYPH&lt;21&gt; ui ( p j ( ) n O 0 ).

There is an equivalent way to write the definition of NEF1. In the responsive set extension , preferences over items are extended to preferences over sets of items in such a way that a set in which an item is replaced by a more preferred item is more preferred. For two allocations p i ( ) and q i ( ) of equal size, we write p i ( ) % RS i q i ( ) if there is a bijection f from q i ( ) to p i ( ) such that for each o 2 q i ( ), f ( o ) % i o . We can then say that an allocation p is NEF1 if for all i ; j 2 N , there exists a subset O 0 GLYPH&lt;18&gt; O of cardinality at most 1, such that either p i ( ) n O 0 % RS i p j ( ) or p i ( ) % RS i p j ( ) n O 0 . The equivalence of definitions is based on results by Aziz et al. (2015). NEF1 is a relaxation of the NEF concept as considered in a series of papers on fair allocation of indivisible items (Aziz et al. 2015; Bouveret, Endriss, and Lang 2010; Brams, Edelman, and Fishburn 2003).

## Welfare

There are many notions of welfare. We particularly focus on the following two. An allocation p is utilitarianmaximal (UM) if it maximizes the sum of utilities: p 2 arg max q 2A P i 2 N P o 2 q i ( ) ui ( o ). An allocation p is rankmaximal (RM) if it maximizes the number of agents assigned their 1st-best item, subject to that - it maximizes the number of agents assigned their 2nd-best item, and so on (see e.g., (Irving et al. 2006; Manlove 2013)). Formally, for any item o 2 O , its rank in agent i 's preference list % i is j if o 2 E j i i.e., it is in i 's j -th equivalence class. For an allocation p , its corresponding rank vector is r ( p ) = ( r 1 ( p ) ; : : : ; rm ( p )) where r j ( p ) is the total number of times an item o is assigned to an agent for whom o has a rank of j . Formally: r j ( p ) : = P i 2 N j E j i \ p i ( ) j : We compare rank vectors lexicographically. A rank-vector r = ( r 1 ; : : : ; rm ) is better than another rank-vector r 0 = ( r 0 1 ; : : : ; r 0 m ) if, for the smallest i such that ri , r 0 i , it must hold that ri &gt; r 0 i . An allocation p is rank-maximal if: p 2 arg max q 2A r q ( ) :

We note that rank maximality can be captured by imposing specific cardinal utilities for agents and then maximizing utility (Michail 2007). The specific cardinal utilities are lexicographic: For an agent i getting an item o from the j -th equivalence class, she gets utility ( xm m ) GLYPH&lt;0&gt; j where x = max f co : o 2 O g .

## Combining Welfare and Fairness

Before presenting our W-CRR algorithm, we explain the rationale behind it. Our starting point is the observation that there is a simple class of algorithms that always return NEF1 allocations - the recursively balanced sequential allocation . These sequential allocation algorithms are parametrized by a pre-specified sequence of agent-turns. In sequential allocation, when an agent gets a turn, she picks a most preferred item that is not yet allocated (see e.g., (Aziz, Walsh, and Xia 2015; Bouveret and Lang 2011; Beynier et al. 2018)). In case of our general setting with capacity constraints, an agent picks a most preferred item that she can pick without violating the item capacity constraint. A sequence of turns is called recursively balanced (RB) if at no point an agent has taken more than one turn than another agent (see e.g., (Aziz, Walsh, and Xia 2015)). For example for two agents and 4 items, the RB sequences are 1212, 1221, 2121 and 2112. We are also interested in the following subset of RB sequences. A sequence of turns is called round-robin (RR) if, for some permutation GLYPH&lt;25&gt; of the agents, the sequence is GLYPH&lt;25&gt; 1 ; GLYPH&lt;25&gt; 2 ; : : : ; GLYPH&lt;25&gt; n ; GLYPH&lt;25&gt; 1 ; GLYPH&lt;25&gt; 2 ; : : : ; GLYPH&lt;25&gt; n ; : : : For example, for two agents and 4 items the RR sequences are 1212 and 2121. All sequential allocation algorithms are ordinal in nature because they ignore the cardinal information in the utility function of the agents.

Note that an RB picking-sequence always returns a balanced allocation. Therefore, if the capacity constraints rule out some balanced allocations (e.g. one agent must get exactly 3 items while another agent must get exactly 5 items), then RB may not return a feasible allocation. However, it always returns an approximately-fair allocation:

Proposition 1 (a) If all utilities are positive, then the outcome of sequential allocation for any RB sequence is NEF1. (b) If all utilities are negative, then the outcome of sequential allocation for any RR sequence is NEF1.

Proof: (a) Let agent i 's allocation be s 1 ; : : : ; sk and agent j 's allocation be t 1 ; : : : ; t k 0 . Since the picking sequence is recursively balanced, the allocation is balanced, which implies that k 0 2 f k GLYPH&lt;0&gt; 1 ; k k ; + 1 . Without loss of generality we let g k 0 = k + 1 by letting j get dummy items after her actual turns have finished. Now let us look at the sequence of turns in which the items are picked: f s 1 ; t 1 g ; : : : ; f sk ; t k g ; f t k + 1 g : When two items are paired in curly brackets, we do not distinguish which one is picked first. Note that for each j 2 f 2 ; : : : ; k 0 g , s j GLYPH&lt;0&gt; 1 % i t j because i picks s j GLYPH&lt;0&gt; 1 when t j is still available. Consider the function f from p j ( ) n f t 1 g to p i ( ) such that for each t j 2 p j ( ) n f t 1 g , f ( o ) = s j GLYPH&lt;0&gt; 1 . Hence p i ( ) % RS i p j ( ) n f t 1 g and therefore, p satisfies NEF1.

(b) The argument is similar. It works by removing the most undesirable item allocated to the envious agent, instead of the most desirable item allocated to the envied agent. GLYPH&lt;3&gt;

Note that if all utilities are negative, the outcome of an RB sequence that is not RR might not even be EF1 (consider the sequence A,B,B). If utilities are mixed, then even the outcome of an RR sequence might not be EF1 (Aziz et al. 2019).

Sequential allocation with respect to a round-robin sequence does not necessarily maximize any social welfare function. Moreover, even EF1, which is weaker than NEF1, might be incompatible with welfare-maximization requirements. It is well-known that EF1 is incompatible with UM when there are no capacity constraints (for example, if Alice's utility for every item is higher than Bob's utility, the only UM allocation gives all items to Alice, which is obviously not EF1 for Bob). The following example shows that this incompatibility also holds when all agents have an identical capacity constraint and when all utilities are based on Borda scores, and it also holds for RM.

Example 1 There are 3 agents and 9 items, with a single copy per item. The following table shows the utility of each item to each agent:

| Item :       |   o 1 |   o 2 |   o 3 |   o 4 |   o 5 |   o 6 |   o 7 |   o 8 |   o 9 |
|--------------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| Agents 1,2 : |     9 |     8 |     7 |     6 |     5 |     4 |     3 |     2 |     1 |
| Agent 3 :    |     6 |     9 |     8 |     7 |     5 |     4 |     3 |     2 |     1 |

We first consider the case in which each agent's capacity is unbounded. In any utilitarian-maximal or rank-maximal allocation, each item must be given to an agent who assigns to it a highest utility. Therefore, Agent 3 must get (at least) the set f o 2 ; o 3 ; o 4 g . This leaves the other two agents a total utility of at most 24 . So one of these agents gets a utility of at most 12 . This agent EF1-envies Agent 3.

Next, we consider the case in which each agent must get exactly 3 items (i.e., the allocation must be balanced). Under this constraint, utilitarian-maximal or rank-maximal imply Agent 3 must get exactly f o 2 ; o 3 ; o 4 g . By the same argument, no utilitarian-maximal or rank-maximal allocation is EF1.

Given this incompatibility, we would like to decide whether there exists, among all welfare-maximizing allocations, one that is also fair. However, this can be computationally challenging. Below we show that, checking whether a UM / RM and EF1 allocation exists is NP-complete when there are at least three agents.

Proposition 2 For three agents, checking whether there exists an allocation that is both rank-maximal and EF1, or both utilitarian-maximal and EF1, is NP-complete.

Proof: We reduce from P artition , which is the following decision problem: given m numbers a 1 ; : : : ; am summing up to 2 S , is there a partition of the numbers into two sets with each set of integers summing up to S ? Given an instance of P artition , define an item-allocation instance with m + 6 items: m number-items and 6 extra-items, denoted e 1 ; e 2 ; e 3 ; e 4 ; e 5 ; e 6 . Each item should be allocated once. There are 3 agents with unbounded capacities and the following valuations:

| Items:     | m number-items    | e 1 ; e 2 ; e 3 ; e 4 ; e 5 ; e 6   |
|------------|-------------------|-------------------------------------|
| Alice:     | 0                 | 5 S ; 4 S ; 3 S ; 2 S ; S ; 0       |
| Bob, Carl: | u j ( o j ) = a j | 4 S ; 3 S ; 2 S ; S ; 5 S ; 5 S     |

It is possible to give all agents their best item, so any RM allocation must do so and give e 1 ; e 5 ; e 6 to Alice, Bob and Carl respectively. Subject to this, it is possible to give one agent her 2nd-best item - this must be Alice, so she must be given e 2 . Similarly, Alice must be given e 3 and e 4 . The same is true for any UM allocation.

Now, Bob and Carl have utility 5 S , and they value Alice's bundle as 10 S . Since the highest item-value for both Bob and Carl is 4 S , the allocation becomes EF1 i GLYPH&lt;11&gt; each of them gets a utility of exactly 6 S , i GLYPH&lt;11&gt; each of them gets a utility of exactly S from the number-items, i GLYPH&lt;11&gt; the allocation of these items corresponds to an equal partition of the numbers. GLYPH&lt;3&gt;

Remark 2 When there are two agents, checking whether there exists an allocation that is both UM and EF1 is polynomial-time solvable.

Proposition 3 For three agents, computing an allocation that is utilitarian-maximal or rank-maximal within the set of EF1 allocations is NP-hard.

Proof: Suppose there exists a polynomial-time algorithm that computes an allocation maximizing the utilitarian welfare within the set of EF1 allocations. Then we can compute the outcome of the algorithm and check whether its total utilitarian welfare is equal to the maximum possible welfare (which is well-known to be polynomial-time computable). The two values are equal if and only if there exists an allocation that is both UM and EF1. An analogous argument holds for RM and EF1, where instead of the maximum utility we consider the maximum rank-vector. GLYPH&lt;3&gt;

The NP-hardness of computing an allocation that maximizes the utilitarian welfare within the set of EF1 allocations was proven independently and recently by Barman et al. (2019). Proposition 3 is stronger in one respect that it even holds for rank maximality.

We proved that deciding whether there exists a UM + EF1 allocation for 3 or more agent is NP-hard. The same is true if we replace EF1 with the more 'friendly' concept of PROP1 -proportionality up to at most a single item. An allocation GLYPH&lt;25&gt; satisfies proportionality up to one item (PROP1) if for each agent i 2 N ,

- GLYPH&lt;15&gt; ui ( GLYPH&lt;25&gt; ( )) i GLYPH&lt;21&gt; ui ( O ) = n ; or
- GLYPH&lt;15&gt; ui ( GLYPH&lt;25&gt; ( )) i + ui ( o ) GLYPH&lt;21&gt; ui ( O ) = n for some o 2 O n GLYPH&lt;25&gt; ( ); or i
- GLYPH&lt;15&gt; ui ( GLYPH&lt;25&gt; ( )) i GLYPH&lt;0&gt; ui ( o ) GLYPH&lt;21&gt; ui ( O ) = n for some o 2 GLYPH&lt;25&gt; ( ). i

Proposition 4 When there are at least three agents, checking whether there exists an allocation that is both UM and PROP1 is NP-complete.

Proof: Similarly to the proof for UM + EF1, we reduce from P artition . Given an instance of P artition with m numbers, define an item-allocation instance with m + 4 items: m number-items plus 4 extra-items. The agents' valuations are:

| Items:     | m number-items   | e 1 ; e 2 ; e 3 ; e 4                 |
|------------|------------------|---------------------------------------|
| Alice:     | 0                | 3 S = 2 ; 3 S = 2 ; 3 S = 2 ; 3 S = 2 |
| Bob, Carl: | v ( o i ) = a i  | S ; S ; S ; S                         |

All agents value the set of all items as 6 S , so the proportional share per agent is 2 S . Since the largest item-value for both Bob and Carl is S , the allocation is PROP1 i GLYPH&lt;11&gt; both Bob and Carl get at least S from the number-items, i GLYPH&lt;11&gt; the i GLYPH&lt;11&gt; the allocation of these items corresponds to an equal partition of the numbers. GLYPH&lt;3&gt;

## The W-CRR Algorithm

In this section, we present the W-Constrained Round Robin (W-CRR) Algorithm. It is parametrized by a target welfare measure W.

While we are particularly interested in the case in which Wis UM or RM, we note that W can be any other welfare notion, for example: maximum egalitarian welfare (Egal), maximum Nash welfare (Nash), utilitarian welfare that is at least some given threshold, Pareto optimality, etc. The idea of W-CRR is to combine the required welfare guarantee with a round-robin sequential allocation.

The algorithm tries to find an allocation as a result of some recursively-balanced and if possible a round-robin policy. The policy is left unspecified at the start of the algorithm and is searched for dynamically. While trying to obtain an allocation as a result of an RB sequence, the algorithm makes regular checks on whether the partial allocation obtained so far can be completed so as to satisfy W. If this is not possible, then the algorithm carefully relaxes the requirement of a recursively-balanced picking sequence. In this relaxation, the algorithm prioritizes agents with smaller allocations to make a pick.

The algorithm uses an oracle called W-Completion that takes as input a partial allocation p and finds a feasible complete allocation that extends p and satisfies W, or reports that no such extension exists. The oracle solves the following computational problem, which we also refer to as WCompletion.

## W-Completion

Input: Question:

( N O ; ; % ; u c ; ) and a partial allocation p Does there exist a complete and feasible alloca-

tion p 0 that extends p and satisfies W? (yes no) /

For several e GLYPH&lt;14&gt; ciency measures such as rank-maximality and utilitarian-maximality, W-Completion can be reduced to simply finding an allocation which satisfies W; see Lemma 1. If W is null, that is we do not impose any e GLYPH&lt;14&gt; ciency constraints, then W-CRR reduces to round-robin sequential allocation. The W-CRR algorithm is specified as Algorithm 1.

Note that during the running of the algorithm W-CRR, as we grow allocation p , we always ensure that there exists an extension of p that also satisfies W. W-CRR needs to call the W-Completion oracle once for each agent-item pair, for a total of mn times. Hence the following properties are obvious:

Proposition 5 For any welfare measure W and instance I = ( N O ; ; % ; u c : (1) If I ; ) has at least one allocation that satisfies W, then W-CRR returns an outcome that satisfies W. (2) If W-Completion can be solved in time T ( I ) , then W-CRR takes time mn GLYPH&lt;1&gt; T I . ( )

W-CRR is inspired by the sequential allocation mechanism that uses a round-robin picking sequence. Among the agents who have the least number of items, it tries to give an item to the agent with the lowest index.

Given an instance I , we denote by W I ( ) the set of allocations that satisfy target W .

Proposition 6 If W ( I ) contains the set of all balanced allocations, then W-CRR is equivalent to a round-robin sequential allocation rule.

Combining Propositions 6 and 1 implies that, if W I ( ) contains all balanced allocations, and if all utilities are positive or all are negative, then W-CRR returns an allocation that is not just EF1 but also NEF1.

## Algorithm 1 W-CRR

Input: I = ( N O ; ; % ; u c ; ) and a target welfare measure W that can be achieved by at least one feasible allocation. Output: Allocation p

- 1 Initialize p to empty allocation f p will be gradually extended. g
- 2 j GLYPH&lt;0&gt; 1
- 3 O 0 GLYPH&lt;0&gt; O .
- 5 N active GLYPH&lt;0&gt; N N active f is the set of agents with non-empty preferences lists L i 0 s g
- 4 For each i 2 N , initialize L i 0 = ( E i 1 0 ; E i 2 0 ; ::: ) to Li = ( E i 1 ; E i 2 ; ::: )
- 6 while N active , ; and there exists a feasible extension of p by giving a new item to some agent do
- 7 N Min GLYPH&lt;0&gt; f i 2 N active : @ j 2 N active s.t. j p i ( ) j &gt; j p j ( ) jg f N Min is the set of agents among N active who have least number of items g
- 8 if there exists an i 2 N Min and o 2 E i 1 0 such that W-Completion( p [ f ( i ; o ) ) g is yes f W-Completion takes into account capacity constraints c g then
- 9 Choose such an i with the lowest index.
- Extend the current alloca-
- 10 p GLYPH&lt;0&gt; p [ f ( i ; o ) g f tion by assigning item o to agent i g
- 11 else

12

For each i 2 N Min , remove E i 1 0 from L i 0 and rename the equivalence classes of L i 0 f rename so that the next equivalence class is now named E i 1 0 and so on. g

13

- 14 return p .

N active GLYPH&lt;0&gt; f i 2 N active : L i 0 , empty g

Example 3 (Example illustrating W-CRR) Consider an instance with 4 agents and 6 items, where each item should be assigned to two di GLYPH&lt;11&gt; erent agents and each agent gets three items. The following table shows the utility of each item to each agent:

| Item :         |   o 1 |   o 2 |   o 3 |   o 4 |   o 5 |   o 6 |
|----------------|-------|-------|-------|-------|-------|-------|
| Agents 1,2,3 : |     6 |     5 |     4 |     3 |     2 |     1 |
| Agent 4 :      |     2 |     6 |     5 |     4 |     3 |     1 |

Let the algorithm target at maximum utility i.e. W is maximum total utility. For simplicity, we assume that the roundrobin order is from agent 1 to 4 if there is a tie. Then the flow of algorithm is as following:

- GLYPH&lt;15&gt; Agent 1 gets o , Agent 2 gets o 1 1 , Agent 3 gets o , Agent 4 2 gets o 2 .
- GLYPH&lt;15&gt; Agent 1 gets o , Agent 2 gets o 3 3 , Agent 3 gets o , Agent 4 4 gets o 4 .
- GLYPH&lt;15&gt; Agent 1 gets o 5 , Agent 4 gets o 5 (at this time, Agents 2 and 3 cannot get their first choice o 5 , otherwise the maximum utility constraint would be broken), Agent 2 gets o 6 , Agent 3 gets o 6 .

The final allocation is EF1, while maximizing total utility.

## RM-CRR and UM-CRR

Since the W-CRR algorithm depends on a W-Completion oracle, it is interesting to know for what W such WCompletion oracles can be implemented e GLYPH&lt;14&gt; ciently. We now show two cases in which W-Completion can be reduced to just computing a single allocation that satisfies W: they are rank-maximality and utilitarian-maximality. Rank-maximal allocations with arbitrary upper capacities can be computed e GLYPH&lt;14&gt; ciently by polynomial-time combinatorial algorithms (Paluch 2013). Similarly, it is well-known that utilitarian maximal allocations can be computed in polynomial time even with capacity constraints (see e.g., (Korte and Vygen 2012)).

Lemma 1 There exists a linear-time reduction - (a) from UM-Completion to computing a utilitarian-maximal allocation; (b) from RM-Completion to computing a rank-maximal allocation.

Proof: For part (a) , consider a partial allocation p that respects the upper capacities. Based on p , decrease the upper and lower capacities, and find a utilitarian-maximal allocation q for the decreased capacities. Let r be the allocation that combines p and q . Let wp ; wq ; wr be the utilitarian welfare of p q r ; ; respectively, so that wr = wp + wq . Let w GLYPH&lt;3&gt; be a maximal utilitarian welfare in the entire instance (note that w GLYPH&lt;3&gt; can be calculated once per instance - it need not be calculated in each call to UM-Completion).

If wr GLYPH&lt;21&gt; w GLYPH&lt;3&gt; . then UM-Completion returns 'yes', since r satisfies the (original) capacity constraints and attains the maximum utilitarian welfare. If wr &lt; w GLYPH&lt;3&gt; then UMCompletion returns 'no', since if there were a completion q 0 of p such that the completed allocation is utilitarianmaximal, then we would have wp + wq 0 GLYPH&lt;21&gt; w GLYPH&lt;3&gt; &gt; wr = wp + wq , which would imply wq 0 &gt; wq , contradicting the maximality of q with the decreased capacities.

For part (b) , note that a rank-maximal allocation is just like a utilitarian-maximal allocation with a vector-valued welfare-function. GLYPH&lt;3&gt;

From the lemma above, we get the following propositions.

Proposition 7 W-Completion can be solved in polynomial time when W is (a) utilitarian-maximality, or (b) rank-maximality. W-CRR can be computed in polynomial time when W is (a) utilitarian-maximality, or (b) rankmaximality.

We note that CRR aligns well with Borda welfare.

Proposition 8 Under strict preferences, positive Borda utilities and items having identical capacities, if the set of feasible allocations contains all balanced allocations, then W-CRR for any target social welfare W gives a 2approximation of maximum total Borda welfare.

Proof: We first prove that under strict preferences, the output of any RB sequential allocation gives a 2-approximation of maximum total Borda welfare. Let c be a positive integer. Suppose there are c copies of each item. We prove that, in round-robin, the welfare in the k -th round increases by at least m GLYPH&lt;0&gt; b ( k GLYPH&lt;0&gt; 1) = c c . Then the total utility is at least c m ( + 1) m = 2. To prove this, let us consider the worst case for the k -th round. Suppose in the k -th round, agent i is the one to choose his best item. Then in agent i 's perspective, the worst case is that in each of the previous rounds, one of his highest-utility item were taken. In such situation, agent i gets utility m GLYPH&lt;0&gt; b ( k GLYPH&lt;0&gt; 1) = c c . Obviously, the maximum welfare is at most cm 2 , which is attained when in each round the utility increases by m . Combining these, we conclude that RB sequential allocation gives a 2-approximation of Borda welfare.

Now consider W-CRR for any target social welfare welfare W If W is less than half the maximum total Borda welfare, then CRR degenerates to any RB sequential allocation. If the target welfare is more than half the maximum total Borda welfare, then this target welfare is indeed achieved by CRR. GLYPH&lt;3&gt;

## Empirical Evaluation

In order to evaluate the performance of W-CRR, we have implemented it along with objectives UM, RM, Egal, Nash, and P -OWA Maximizing. In order to easily switch between the various objective functions all models were implemented in Gurobi 8.1 using the Python interface. All code from this project will be released on GitHub. We have run experiments on both real-world data from PrefLib (Mattei and Walsh 2017; Mattei and Walsh 2013) and data generated according to a Mallows model.

In all of our experiments, we assume that agents have Borda utilities and these are assigned at the level of the equivalence class in the case of weak rankings from the realworld data; this is common in much of the literature on resource allocation and conference paper assignment (Lian et al. 2018). In all of our experiments we enforce that all agents and all items, respectively, have the same maximum and minimum capacities. We also enforce that all agents may receive only one copy of any particular item. For each of the datasets, we report the fraction of the n n ( GLYPH&lt;0&gt; 1) relations between agents that satisfy EF, EF1, NEF, and NEF1.

## Synthetic Data

We generate synthetic data using a Mallows model which gives each agent a strict preference over the items and allows us to measure the e GLYPH&lt;11&gt; ect that correlation between the agent preferences has on the overall results. For each setting of the GLYPH&lt;30&gt; 2 [0 ; 1] parameter, we generate 25 test instances and report the mean and standard deviation of the proportion of allocations satisfying the various evaluation criteria. We tested for correlation GLYPH&lt;30&gt; 2 f 0 0 : ; 0 25 0 50 0 75 0 95 . : ; : ; : ; : g The value of 1 GLYPH&lt;0&gt; GLYPH&lt;30&gt; indicates the level of correlation. For each GLYPH&lt;30&gt; , we generated instances with 10 agents and 20 items. We set

Figure 1: Mean performance of the seven objective functions as we sweep GLYPH&lt;30&gt; for NEF1.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00161v1-figure-144cef2b-b589-4424-be3c-1ecba566cc7f.jpg)

the agent minimum to 3 and maximum to 6, while for the objects we set a minimum of 3 and maximum of 4.

Figure 1 shows the mean proportion of NEF1 relations that are satisfied for each setting of GLYPH&lt;30&gt; and provides a good visualization of the e GLYPH&lt;11&gt; ect of correlation on the various algorithms. We see here that UM-CRR and RM-CRR are able to handle perfectly correlated preferences and provide a solution that has less NEF1 relations than the Egal objective, which is NP-hard to compute. We also see that the CRRrefinement outperforms the UM or RM objective alone for all settings to GLYPH&lt;30&gt; . Interesting in this graph is the good performance of the P -OWA objective with a linear OWA (LSOWA). Similar trends exists for other measures NEF and EF.

Table 1: Results of our CRR algorithms compared to various baseline algorithms for the PrefLib datasets.

|         | EF Relations   | EF Relations   | EF Relations   | EF Relations   | EF Relations   | EF Relations   | EF Relations   |
|---------|----------------|----------------|----------------|----------------|----------------|----------------|----------------|
|         | UM             | UM-CRR         | RM             | RM-CRR         | Nash           | Linear- P OWA  | Egal           |
| MD-2-01 | 0.955          | 0.975          | 0.965          | 0.975          | 0.922          | 0.657          | 0.934          |
|         | EF1 Relations  | EF1 Relations  | EF1 Relations  | EF1 Relations  | EF1 Relations  | EF1 Relations  | EF1 Relations  |
|         | UM             | UM-CRR         | RM             | RM-CRR         | Nash           | Linear- P OWA  | Egal           |
| MD-2-01 | 1.0            | 1.0            | 1.0            | 1.0            | 1.0            | 0.823          | 1.0            |
| MD-2-02 | 1.0            | 1.0            | 1.0            | 1.0            | 1.0            | 0.944          | 1.0            |
| MD-2-03 |                |                |                |                |                | 0.97           |                |
|         | 0.815          | 0.919          | 0.812          | 0.919          | 0.813          |                | 1.0            |
|         | NEF Relations  | NEF Relations  | NEF Relations  | NEF Relations  | NEF Relations  | NEF Relations  | NEF Relations  |
|         | UM             | UM-CRR         | RM             | RM-CRR         | Nash           | Linear- P OWA  | Egal           |
| MD-2-01 | 0.951          | 0.966          | 0.961          | 0.965          | 0.902          | 0.615          | 0.927          |
| MD-2-02 | 1.0            | 1.0            | 1.0            | 1.0            | 1.0            | 0.723          | 0.998          |
| MD-2-03 | 0.723          | 0.702          | 0.716          | 0.702          | 0.721          | 0.849          | 0.816          |
|         | NEF1 Relations | NEF1 Relations | NEF1 Relations | NEF1 Relations | NEF1 Relations | NEF1 Relations | NEF1 Relations |
|         | UM             | UM-CRR         | RM             | RM-CRR         | Nash           | Linear- P OWA  | Egal           |
| MD-2-01 | 0.995          | 1.0            | 0.998          | 1.0            | 0.961          | 0.806          | 0.989          |
| MD-2-02 | 1.0            | 1.0            | 1.0            | 1.0            | 1.0            | 0.918          | 1.0            |
| MD-2-03 | 0.814          | 0.918          | 0.81           | 0.918          | 0.811          | 0.97           | 1.0            |

## Real World Data

To measure the e GLYPH&lt;11&gt; ectiveness of our algorithms on real-world data we use three datasets from PrefLib: MD-2-01 - 03 are from small computer science conferences with between 50175 papers and bids from 25-150 participants. For all of these datasets, we set the capacity constraints so that each item (paper) is assigned to at least 3 and at most 4 agents. Each agent gets between 4 and 7 papers.

The results of CRR compared to other objectives are shown in Table 1. The results are mixed and suggest that there is a rich interplay between the exact bids received and the outcomes of the various algorithms. Looking first at the EF and EF1 relationships we see that the results are mixed, for some settings, envy goes up when we run the CRR algorithm while in others it actually decreases. However, for the EF1 relations the CRR refinement is always better and significantly so. Looking at the NEF and NEF1 relations we see that the CRR algorithm delivers strictly better results in terms of envy than the UM and RM objectives. It is interesting to note that in some cases even using the Egalitarian objective does worse than the corresponding CRR algorithm. However, in general, we see that using an Egalitarian objective, though it is NP-hard to optimize for, is a good way to reduce envy on average.

## Conclusions

We have presented a flexible algorithm called CRR that can be parametrized with respect to the target welfare and it can be used in conjunction with any feasibility constraints. Since each system designer may have a di GLYPH&lt;11&gt; erent sweet spot between welfare and fairness concerns, the CRR algorithm can cater to di GLYPH&lt;11&gt; erent 'tastes.' For any given welfare requirement, our approach can be seen as providing a fairness serum to the allocation process. We note that if agents have unequal shares or di GLYPH&lt;11&gt; erent capacities, this can handled by the algorithm by modifying N Min from N Min = f i 2 N j @ j 2 N Active s.t. j p i ( ) j &gt; j p j ( ) jg to N Min = f i 2 N : j p i ( ) j &lt; si P j 2 N s j j [ 2 j N p j ( ) jg : We conclude by noting that revisiting standard settings with the goal to incorporate real-life distribution constraints is an important research direction in multi-agent resource allocation.

## References

[Aziz et al. 2015] Aziz, H.; Gaspers, S.; Mackenzie, S.; and Walsh, T. 2015. Fair assignment of indivisible objects under ordinal preferences. Artificial Intelligence 227:71-92.

[Aziz et al. 2019] Aziz, H.; Caragiannis, I.; Igarashi, A.; and Walsh, T. 2019. Fair allocation of indivisible goods and chores. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI) , Forthcoming.

[Aziz, Walsh, and Xia 2015] Aziz, H.; Walsh, T.; and Xia, L. 2015. Possible and necessary allocations via sequential mechanisms. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI) , 468-474.

[Barman et al. 2019] Barman, S.; Ghalme, G.; Jain, S.; Kulkarni, P.; and Narang, S. 2019. Fair division of indivisible goods among strategic agents. CoRR abs 1901.09427. /

[Barman, Murthy, and Vaish 2018] Barman, S.; Murthy, S. K. K.; and Vaish, R. 2018. Finding fair and e GLYPH&lt;14&gt; cient allocations. In Proceedings of the 19th ACM Conference on Economics and Computation (ACM-EC) . ACM Press.

[Baumeister et al. 2017]

- J.; Nguyen, N.; Nguyen, T. T.; Rothe, J.; and Sa GLYPH&lt;14&gt;

Baumeister, D.; Bouveret, S.; Lang, dine,

- A. 2017. Positional scoring-based allocation of indivis-

ible goods. Autonomous Agents and Multi-Agent Systems 31(3):628-655.

[Beynier et al. 2018] Beynier, A.; Bouveret, S.; Lemaˆ ıtre, M.; Maudet, N.; and Rey, S. 2018. E GLYPH&lt;14&gt; ciency, sequenceability and deal-optimality in fair division of indivisible goods. CoRR abs 1807.11919. /

[Biswas and Barman 2018] Biswas, A., and Barman, S. 2018. Fair division under cardinality constraints. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI) , 91-97.

[Bouveret and Lang 2011] Bouveret, S., and Lang, J. 2011. A general elicitation-free protocol for allocating indivisible goods. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI) , 73-78. AAAI Press.

[Bouveret and Lemaˆ ıtre 2015] Bouveret, S., and Lemaˆ ıtre, M. 2015. Characterizing conflicts in fair division of indivisible goods using a scale of criteria. Autonomous Agents and Multi-Agent Systems .

[Bouveret, Chevaleyre, and Maudet 2016] Bouveret, S.; Chevaleyre, Y.; and Maudet, N. 2016. Fair allocation of indivisible goods. In Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D., eds., Handbook of Computational Social Choice . Cambridge University Press. chapter 12.

[Bouveret, Endriss, and Lang 2010] Bouveret, S.; Endriss, U.; and Lang, J. 2010. Fair division under ordinal preferences: Computing envy-free allocations of indivisible goods. In Proceedings of the 19th European Conference on Artificial Intelligence (ECAI) , 387-392.

[Brams, Edelman, and Fishburn 2003] Brams, S. J.; Edelman, P.; and Fishburn, P. C. 2003. Fair division of indivisible items. Theory and Decision 55:147-180.

[Caragiannis et al. 2012] Caragiannis, I.; Kaklamanisa, C.; Kanellopoulos, P.; and Kyropoulou, M. 2012. The e GLYPH&lt;14&gt; ciency of fair division. Theory of Computing Systems 50(4):589610.

[Caragiannis et al. 2016] Caragiannis, I.; Kurokawa, D.; Moulin, H.; Procaccia, A. D.; Shah, N.; and Wang, J. 2016. The Unreasonable Fairness of Maximum Nash Welfare. In Proceedings of the 17th ACM Conference on Economics and Computation (ACM-EC) , 305-322. ACM Press.

[Garg et al. 2010] Garg, N.; Kavitha, T.; Kumar, A.; Mehlhorn, K.; and Mestre, J. 2010. Assigning papers to referees. Algorithmica 58(1):119-136.

[Irving et al. 2006] Irving, R. W.; Kavitha, T.; Mehlhorn, K.; Michail, D.; and Paluch, K. E. 2006. Rank-maximal matchings. ACM Transactions on Algorithms (TALG) 2(4):602610.

[Korte and Vygen 2012] Korte, B., and Vygen, J. 2012. Combinatorial Optimization . Springer-Verlag, 5th edition.

[Lian et al. 2018] Lian, J. W.; Mattei, N.; Noble, R.; and Walsh, T. 2018. The conference paper assignment problem: Using order weighted averages to assign indivisible goods. In Proceedings of the Thirty-Second AAAI Conference on

Artificial Intelligence, New Orleans, Louisiana, USA, February 2-7, 2018 .

[Manlove 2013] Manlove, D. F. 2013. Algorithmics of Matching Under Preferences . World Scientific Publishing Company.

[Mattei and Walsh 2013] Mattei, N., and Walsh, T. 2013. PrefLib: A library for preferences, http //www preflib org : . . . In Proceedings of the 3rd International Conference on Algorithmic Decision Theory (ADT) .

[Mattei and Walsh 2017] Mattei, N., and Walsh, T. 2017. A P ref L ib .O rg Retrospective: Lessons Learned and New Directions. In Endriss, U., ed., Trends in Computational Social Choice . AI Access Foundation. chapter 15, 289-309.

- [Michail 2007] Michail, D. 2007. Reducing rank-maximal to maximum weight matching. Theoretical Computer Science 389(1-2):125-132.
- [Paluch 2013] Paluch, K. E. 2013. Capacitated rankmaximal matchings. In Algorithms and Complexity, 8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013. Proceedings , 324-335.
- [Segal-halevi, Aziz, and Hassidim 2017] Segal-halevi, E.; Aziz, H.; and Hassidim, A. 2017. Fair allocation based on diminishing di GLYPH&lt;11&gt; erences. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI) .

[Segal-Halevi 2018] Segal-Halevi, E. 2018. Redividing the cake. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI) , 498-504.

[Yager 1988] Yager, R. 1988. On ordered weighted averaging aggregation operators in multicriteria decisionmaking. IEEE Transactions on Systems, Man and Cybernetics 18(1):183-190.

## A. Maximum Nash Welfare Does Not Imply EF1 for Balanced Allocations: Example

There are 4 items, 2 agents, and each agent must get 2 items. The valuations are:

- GLYPH&lt;15&gt; Alice: 5, 5, 2, 2
- GLYPH&lt;15&gt; Bob: 7, 7, 0, 0

There are three possible allocations:

- GLYPH&lt;15&gt; Alice gets 5,5 and Bob gets 0,0 - the Nash welfare is 0.
- GLYPH&lt;15&gt; Alice gets 5,2 and Bob gets 7,0 - the Nash welfare is 7*7 = 49.
- GLYPH&lt;15&gt; Alice gets 2,2 and Bob gets 7,7 - the Nash welfare is 4*14 = 56.

So the Nash-optimal allocation gives Alice a value of 2 + = 2 4, but it is not EF1 for Alice. Note that without the capacity constraints, the Nash-optimal allocation gives Alice 5 + + = 2 2 9 and Bob 7, the Nash welfare is 63 and it is indeed EF1.

Figure 2: Graphs of the performance of the seven objective functions as we sweep GLYPH&lt;30&gt; for each of our evaluation metrics.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00161v1-figure-d2f85028-e2ed-4cd8-9921-b0f695cbb45e.jpg)

## B. Stepping Graphs

Figure 2 captures the proportions of the various relations as we sweep GLYPH&lt;30&gt; for each of the evaluation criteria. These plots can be thought of as an aggregate view of the individual boxplots found in the next section. Looking at this set of graphs we see that the CRR refinements are outperforming the UM and RM algorithms across the sweep of correlated preferences. This di GLYPH&lt;11&gt; erence is particularly noteworthy for the NEF1 and NEF plots.

## C. Individual Boxplots

Figures 3 through Figure 7 show the distribution of the results for each of the 25 trials for each of the settings to GLYPH&lt;30&gt; 2 f 0 0 0 25 0 50 0 75 0 95 . These figures give a more : ; : ; : ; : ; : g nuanced view of what is happening in the interplay between preference correlation and the fairness of the assignments that are found. Most interestingly is that, as seen in Figure 2 we see the CRR refinements beating out the underling UM and RM allocations at each of the steps. Another interesting aspect is that when preferences are random ( GLYPH&lt;30&gt; 2 0 95) all : algorithms are particularly good at finding fair allocations. The real interesting areas to focus on are when preferences are correlated but not perfectly so. In these cases, e.g., Figure 3 that NEF is indeed a very stringent requirement and none of the algorithms can guarantee more than 50% of the relations satisfy the measure. However, NEF1 is interesting in that many of the algorithms, and especially the CRR algorithms, are able to find an allocation satisfying NEF1 for over 80% of the pairs.

Figure 3: Boxplots for GLYPH&lt;30&gt; = 0.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00161v1-figure-6954949e-be09-42c2-b574-2b6105e037c6.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00161v1-figure-ac03cb7b-2794-4b66-a45f-3cd144227248.jpg)

Mallows Model -

=25

Proportion of NEF Relations

1.0

0.8

0.6

0.4

0.2

0.0

UM

UM-CRR

RM

RM-CRR Nash

LSOWA

Objective

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00161v1-figure-2cc48a66-8a23-4f1b-b160-f58853b36643.jpg)

Figure 4: Boxplots for GLYPH&lt;30&gt; = 25.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00161v1-figure-aaa02955-c3b2-4e7f-8296-99566480c3dc.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00161v1-figure-842c73c4-94fc-45bb-810a-7c88b18c70bc.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00161v1-figure-60483015-3a5b-47bd-ad9b-dd715692a177.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00161v1-figure-20491a8b-39ae-4325-89d9-06164a68b407.jpg)

=50

Figure 5: Boxplots for GLYPH&lt;30&gt; = 50.

Egal

Figure 6: Boxplots for GLYPH&lt;30&gt; = 75.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00161v1-figure-fcda4aa8-c9e8-44fd-9923-59d3072b7b5e.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00161v1-figure-98a584a4-4c12-4566-9385-011d08870cea.jpg)

Figure 7: Boxplots for GLYPH&lt;30&gt; = 0 95. :

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00161v1-figure-52b660e0-5a0e-4613-ac9b-d99f4236d8fa.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00161v1-figure-dbcb85c6-5459-4954-a620-9e6e45c61aed.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00161v1-figure-aefef4fd-925a-4a55-94fa-59690ac150ae.jpg)
Haris Aziz Xin Huang Nicholas Mattei Erel Segal-Halevi
The Constrained Round Robin Algorithm for Fair and Efficient Allocation
We consider a multi-agent resource allocation setting that models the
assignment of papers to reviewers. A recurring issue in allocation problems is
the compatibility of welfare/efficiency and fairness. Given an oracle to find a
welfare-achieving allocation, we embed such an oracle into a flexible algorithm
called the Constrained Round Robin (CRR) algorithm, that achieves the required
welfare level. Our algorithm also allows the system designer to lower the
welfare requirements in order to achieve a higher degree of fairness. If the
welfare requirement is lowered enough, a strengthening of envy-freeness up to
one item is guaranteed. Hence, our algorithm can be viewed as a computationally
efficient way to interpolate between welfare and approximate envy-freeness in
allocation problems.