# fair_and_efficient_allocations_under_lexicographic_preferences__f1eb6c67.pdf

Fair and Efﬁcient Allocations under Lexicographic Preferences

Hadi Hosseini,1 Sujoy Sikdar,2 Rohit Vaish,3 Lirong Xia4

1 Pennsylvania State University, University Park, Pennsylvania, USA 16802 2 Binghamton University, Binghamton, New York 13902-6000 3 Tata Institute of Fundamental Research, Mumbai, India 400005 4 Rensselaer Polytechnic Institute, Troy, New York 12180 hadi@psu.edu, ssikdar@binghamton.edu, rohit.vaish@tifr.res.in, xial@cs.rpi.edu

Envy-freeness up to any good (EFX) provides a strong and intuitive guarantee of fairness in the allocation of indivisible goods. But whether such allocations always exist or whether they can be efﬁciently computed remains an important open question. We study the existence and computation of EFX in conjunction with various other economic properties under lexicographic preferences a well-studied preference model in artiﬁcial intelligence and economics. In sharp contrast to the known results for additive valuations, we not only prove the existence of EFX and Pareto optimal allocations, but in fact provide an algorithmic characterization of these two properties. We also characterize the mechanisms that are, in addition, strategyproof, non-bossy, and neutral. When the efﬁciency notion is strengthened to rank-maximality, we obtain non-existence and computational hardness results, and show that tractability can be restored when EFX is relaxed to another well-studied fairness notion called maximin share guarantee (MMS).

Introduction Fair and efﬁcient allocation of scarce resources is a fundamental problem in economics and computer science. The quintessential fairness notion envy-freeness enjoys strong existential and computational guarantees for divisible resources (Varian 1974). However, in notable applications such as course allocation (Budish 2011) and property division (Pruhs and Woeginger 2012) that involve indivisible resources, (exact) envy-freeness could be too restrictive. In these settings, it is natural to consider notions of approximate fairness such as envy-freeness up to any good (EFX) wherein pairwise envy can be eliminated by the removal of any good in the envied bundle (Caragiannis et al. 2019). EFX is arguably the closest analog of envy-freeness in the indivisible setting, and, as a result, has been actively studied especially for the domain of additive valuations. However, it also suffers from a number of limitations: First, barring a few special cases, the existence and computation of EFX allocations remains an open problem. Second, for additive valuations, EFX can be incompatible with Pareto optimality (PO) a fundamental notion of economic efﬁciency (Plaut and Roughgarden 2020). Finally, EFX could also be at odds

Copyright 2021, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

with strategyproofness (Amanatidis et al. 2017), which is another desirable property in the economic analysis of allocation problems. The aforementioned limitations of EFX prompt us to explore the domain restriction approach in search of positive results (Elkind, Lackner, and Peters 2016). Speciﬁcally, we deviate from the framework of cardinal preferences for which EFX allocations have been most extensively studied, and instead focus on the purely ordinal domain of lexicographic preferences. Lexicographic preferences have been widely studied in psychology (Gigerenzer and Goldstein 1996), machine learning (Schmitt and Martignon 2006), and social choice (Taylor 1970) as a model of human decision-making. Several real-world settings such as evaluating job candidates and the desirability of a product involve lexicographic preferences over the set of features. In the context of fair division, too, lexicographic preferences can arise naturally. For example, when dividing an inheritance consisting of a house, a car, and some home appliances, a stakeholder might prefer any division in which she gets the house over one where she doesn t (possibly because of its sentimental value), subject to which she might prefer any outcome that includes the car over one that doesn t, and so on. On the computational side, lexicographic preferences provide a succinct language for representing preferences over combinatorial domains (Saban and Sethuraman 2014; Lang, Mengin, and Xia 2018), and have led to numerous positive results at the intersection of artiﬁcial intelligence and economics (Fujita et al. 2018; Hosseini and Larson 2019). Motivated by these considerations, our work examines the existence and computation of fair (i.e., EFX) and efﬁcient allocations from the lens of lexicographic preferences.

Our Contributions. Figure 1 summarizes our theoretical contributions. EFX+PO: Our ﬁrst result provides a family of polynomial-time algorithms for computing EFX+PO allocations under lexicographic preferences. Furthermore, we show that any EFX+PO allocation can be computed by some algorithm in this family, thus providing an algorithmic characterization of such allocations (Theorem 1). This result establishes a sharp contrast with the additive valuations domain where the two properties are incompatible in general.

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

EFX+PO EFX+ Rank-maximal

EFX+PO+Strategyproof+ non-bossy + neutral

Characterization (Theorem 1)

Non-existence and NP-hardness (Theorem 3)

Non-existence (Example 1) Characterization (Theorem 2)

Figure 1: Summary of our theoretical results.

EFX+PO+strategyproofness: The positive result for EFX+PO motivates us to investigate a more demanding property combination of EFX, PO, and strategyproofness. Once again, we obtain an algorithmic characterization (Theorem 2): Subject to some common axioms (non-bossiness and neutrality), any mechanism satisfying EFX, PO, and strategyproofness is characterized by a special class of quota-based serial dictatorship mechanisms (P apai 2000b; Hosseini and Larson 2019). EFX+rank-maximality: When the efﬁciency notion is strengthened to rank-maximality, we encounter incompatibility with strategyproofness (Example 1) as well as with EFX (Example 2). Furthermore, checking the existence of EFX and rank-maximal allocations turns out to be NPcomplete (Theorem 3), suggesting that our algorithmic results are, in a certain sense, maximal . The intractability persists even when EFX is relaxed to envy-freeness up to k goods (EFk) (Theorem 4), but efﬁcient computation is possible if EFX is relaxed to another well-studied fairness notion called maximin share guarantee or MMS (Theorem 5).

Related Work. Envy-free solutions may not always exist for indivisible goods. As a result, the literature has focused on notions of approximate fairness, most notably envy-freeness up to one good (EF1) and its strengthening called envy-freeness up to any good (EFX). The former enjoys strong existential and algorithmic support, as an EF1 allocation always exists for general monotone valuations and can be efﬁciently computed. However, achieving EF1 together with economic efﬁciency seems non-trivial: For additive valuations, EF1+PO allocations always exist (Caragiannis et al. 2019; Barman, Krishnamurthy, and Vaish 2018) but no polynomial-time algorithm is known for computing such allocations. The stronger notion of EFX has proven to be more challenging. As mentioned previously, the existence of EFX for additive valuations remains an open problem. Additionally, EFX and Pareto optimality are known to be incompatible for non-negative additive valuations (Plaut and Roughgarden 2020). The aforementioned limitations of EFX have motivated the study of further relaxations or special cases in search of positive results. Some recent results establish the existence of partial allocations that satisfy EFX after discarding a small number of goods while also fulﬁlling certain efﬁciency criteria (Caragiannis, Gravin, and Huang 2019; Chaudhury et al. 2020). Similarly, EFX allocations have been shown to exist for the special case of three agents with

additive valuations (Chaudhury, Garg, and Mehlhorn 2020), or when the agents can be partitioned into two types (Mahara 2020), or when agents have dichotomous preferences (Amanatidis et al. 2020). For cardinal utilities, various multiplicative approximations of EFX (and its variant that involves removing an average good) have been considered (Plaut and Roughgarden 2020; Amanatidis, Markakis, and Ntokos 2020; Chaudhury, Garg, and Mehta 2020; Farhadi et al. 2020). Another emerging line of work studies EFX for nonmonotone valuations, i.e., when the resources consist of both goods and chores (Chen and Liu 2020; B erczi et al. 2020). The interaction between fairness and efﬁciency is further complicated with the addition of strategyproofness due to several fundamental impossibility results both in deterministic (Zhou 1990) as well as randomized settings (Bogomolnaia and Moulin 2001; Kojima 2009). Indeed, while ordinal efﬁciency is compatible with envy-freeness, such outcomes cannot, in general, be achieved via (weakly) strategyproof mechanisms even under strict preferences (Kojima 2009). Moreover, sd-efﬁciency and sd-strategyproofness (here, sd stands for stochastic dominance) are incompatible even with a weak notion of stochastic fairness called equal treatment of equals (Aziz and Kasajima 2017). In a similar vein, for deterministic mechanisms, any strategyproof mechanism could fail to satisfy EF1 even for two agents under additive valuations (Amanatidis et al. 2017). Lexicographic preferences have also been successfully used as a domain restriction to circumvent impossibility results in mechanism design (Sikdar, Adali, and Xia 2017; Fujita et al. 2018). In fair division of indivisible goods, lexicographic (sub)additive utilities have facilitated constantfactor approximation algorithms for egalitarian and Nash social welfare objectives (Baumeister et al. 2017; Nguyen 2020). Hosseini and Larson (2019) showed that under lexicographic preferences, a mechanism is Pareto optimal, strategyproof, non-bossy, and neutral if and only if it is a serial dictatorship quota mechanism. In randomized settings, too, lexicographic preferences have led to the design of mechanisms that simultaneously satisfy stochastic efﬁciency, envy-freeness, and strategyproofness (Schulman and Vazirani 2015; Hosseini and Larson 2019).

Preliminaries

Model For any k N, deﬁne [k] := {1, . . . , k}. An instance of the allocation problem is a tuple N, M, , where N := [n] is a set of n agents, M is a set of m goods, and := ( 1 , . . . , n) is a preference proﬁle that speciﬁes the ordinal preference of each agent i N as a linear order i L over the set of goods; here, L denotes the set of all (strict and complete) linear orders over M. Allocation and bundles A bundle is any subset X M of the set of goods. An allocation A = (A1, . . . , An) is an n-partition of M, where Ai M is the bundle assigned to agent i. We will write Π to denote the set of all n-partitions of M. We say that allocation A is partial if S i N Ai M, and complete if S i N Ai = M. Lexicographic preferences We will assume that agents preferences over the bundles are given by the lexicographic

extension of their preferences over individual goods. Informally, this means that if an agent ranks the goods in the order a b c . . . , then it prefers a bundle containing a over any other bundle that doesn t, subject to that, it prefers a bundle containing b over any other bundle that doesn t, and so on. Formally, given any pair of bundles X, Y M and any linear order i L, we have X i Y if and only if there exists a good g X \ Y such that {g Y : g i g} X. Notice that since i is a linear order over M, the corresponding lexicographic extension is a linear order over 2M. For any agent i N and any pair of bundles X, Y M, we will write X i Y if either X i Y or X = Y . Envy-freeness Given a preference proﬁle , an allocation A is said to be (a) envy-free (EF) if for every pair of agents i, h N, we have Ai i Ah; (b) envy-free up to any good (EFX) if for every pair of agents i, h N such that Ah = and every good j Ah, we have Ai i Ah \ {j}, and (c) envy-free up to k goods (EFk) if for every pair of agents i, h N such that Ah = , there exists a set S Ah such that |S| k and Ai i Ah \ S. Clearly, EFX EF1 EF2 . . . . Maximin Share An agent s maximin share is its most preferred bundle that it can guarantee itself as a divider in an nperson cut-and-choose procedure against adversarial opponents (Budish 2011). Formally, the maximin share of agent i is given by MMSi := max A Π mini{A1, . . . , An}, where min{ } and max{ } denote the least-preferred and mostpreferred bundles with respect to i. An allocation A satisﬁes maximin share guarantee (MMS) if each agent receives a bundle that it weakly prefers to its maximin share. That is, the allocation A is MMS if for every i N, Ai i MMSi. It is easy to see that EF MMS. Additionally, for lexicographic preferences, we have that EFX MMS (the converse is not true) while EF1 and MMS can be incomparable (see the full version (Hosseini et al. 2020) for details). Pareto optimality Given a preference proﬁle , an allocation A is said to be Pareto optimal (PO) if there is no other allocation B such that Bi i Ai for every agent i N and Bk k Ak for some agent k N. Rank-maximality A rank-maximal (RM) allocation is one that maximizes the number of agents who receive their favorite good, subject to which it maximizes the number of agents who receive their second favorite good, and so on (Irving et al. 2006; Paluch 2013). Given an allocation A, its signature refers to a tuple (n1, n2, . . . , nm) where ni is the number of agents who receive their ith favorite good (note that an agent can contribute to multiple ni s). All rank-maximal allocations for a given instance have the same signature. Computing some rank-maximal allocation for a given instance is easy: Assign each good to an agent that ranks it the highest among all agents (tiebreak arbitrarily). This procedure provides a computationally efﬁcient way of computing the signature of a rank-maximal allocation as well as verifying whether a given allocation is rankmaximal. Notice that rank-maximality is a strictly stronger requirement than Pareto optimality. Mechanism A mechanism f : Ln Π is a mapping from preference proﬁles to allocations. For any preference proﬁle Ln, we use f( ) to denote the allocation returned by

f, and fi( ) to denote the bundle assigned to agent i. Properties of mechanisms A mechanism f : Ln Π is said to satisfy EF / EFX / EFk / PO / RM if for every preference proﬁle Ln, the allocation f( ) has that property. In addition, a mechanism f satisﬁes strategyproofness (SP) if no agent can improve by misreporting its preferences. That is, for every preference proﬁle Ln, every agent i N, and every (misreported) linear order i L, we have fi( ) i fi( ), where := ( 1, . . . , i 1, i, i+1, . . . , n). non-bossiness if no agent can modify the allocation of another agent by misreporting its preferences without changing its own allocation. That is, for every proﬁle Ln, every agent i N, and every (misreported) linear order i L, we have fi( ) = fi( ) f( ) = f( ), where := ( 1, . . . , i 1, i, i+1, . . . , n). neutrality if relabeling the goods results in a consistent change in the allocation. That is, for every preference proﬁle Ln and every relabeling of the goods π : M M, it holds that f(π( )) = π(f( )), where π( ) := (π( 1), . . . , π( n)) and π(A) := (π(A1), . . . , π(An)) for any allocation A = (A1, . . . , An).

EFX and Pareto Optimality Recall that for additive valuations, establishing the existence of EFX allocations remains an open problem, and there exist instances where no allocation is simultaneously EFX and PO (Plaut and Roughgarden 2020). Our ﬁrst result (Theorem 1) shows that there is no conﬂict between fairness and efﬁciency for lexicographic preferences: Not only does there exist a family of polynomial-time algorithms that always return EFX+PO allocations, but every EFX+PO allocation can be computed by some algorithm in this family. We will start with an easy observation concerning EFX allocations.

Proposition 1. An allocation A is EFX if and only if each envied agent in A gets exactly one good.

Description of algorithm Each algorithm in this family (Algorithm 1) is speciﬁed by an ordering σ over the agents, and consists of two phases. Phase 1 involves a single round of serial dictatorship according to σ. Phase 2 assigns the remaining goods among the unenvied agents according to a picking sequence τ. Note that the set of unenvied agents after Phase 1 must be nonempty; in particular, the last agent in σ belongs to this set since every other agent prefers its good picked in Phase 1 to any good in the last agent s bundle.

Theorem 1. For any ordering σ of the agents, the allocation computed by Algorithm 1 satisﬁes EFX and PO. Conversely, any EFX+PO allocation can be computed by Algorithm 1 for some choice of σ.

Proof. We will start by showing that the allocation A returned by Algorithm 1 satisﬁes EFX. From Proposition 1, it sufﬁces to show that any envied agent gets exactly one good in A. Notice that any agent that is envied at the end of Phase 1 does not receive any good in Phase 2. Furthermore, the pairwise envy relations remain unchanged during Phase 2 since each agent has already picked its favorite available

ALGORITHM 1: EFX+PO Input: An instance N, M, with lexicographic preferences Parameters: A permutation σ : N N of the agents Output: An allocation A A ( , . . . , ) Phase 1: Serial dictatorship for assigning n goods Agents arrive according to σ, and each picks a favorite good from the set of remaining goods. Update partial allocation A. Phase 2: Allocate leftover goods via picking sequence if the set of remaining goods is nonempty then

U {i N : i is not envied by any agent under A}. Fix any picking sequence τ of length m n consisting only of the agents in U (i.e., the unenvied agents). Assign remaining goods according to τ and update A. return A

good in Phase 1, and because of lexicographic preferences, any goods assigned in Phase 2 are strictly less preferred. Thus, A is EFX. To prove Pareto optimality (PO), suppose, for contradiction, that A is Pareto dominated by an allocation B. Then, there must exist some agent, say i, who receives a good under A that it does not receive under B (i.e., Ai \ Bi = ); we will call any such item a difference good. Observe that the execution of Algorithm 1 can be described in terms of a combined picking sequence σ, τ . Thus, without loss of generality, we can deﬁne i to be the ﬁrst agent according to σ, τ to receive a difference good. Let g denote the corresponding difference good picked by i, and note that g Ai \ Bi by assumption. Since B Pareto dominates A and Ai = Bi, we must have Bi i Ai. For lexicographic preferences, this means that there exists a good g Bi \ Ai such that g i g. Since all agents preceding i in σ, τ pick the goods that they also own under B, the good g must be available (along with g) when it is i s turn to pick. Thus, i would not pick g, which is a contradiction. Hence, A satisﬁes PO. To prove the converse, note that any PO allocation can be induced by a picking sequence.1 Given any EFX+PO allocation A, let S denote the corresponding picking sequence. We claim that without loss of generality, the ﬁrst n positions in S belong to n different agents. Indeed, if some agent i appears more than once in the n-preﬁx of S, then |Ai| > 1. By Proposition 1, i must not be envied by any other agent. Because of the no-envy condition, a modiﬁed sequence where the repeated appearances of unenvied agents are pushed behind the ﬁrst appearance of any other agent will also result in allocation A. We can now instantiate Algorithm 1 with σ as the n-preﬁx of S and τ as S \ σ to compute A.

Characterizing Strategyproof Mechanisms

In addition to fairness and efﬁciency, an important desideratum for allocation mechanisms is strategyproofness. For ad-

1Indeed, in any PO allocation, some agent must receive its favorite good (otherwise a cyclic exchange of the top-ranked goods gives a Pareto improvement). Add this agent to the picking sequence, and repeat the procedure for the remaining goods.

ALGORITHM 2: Input: An instance N, M, with lexicographic preferences Parameters: A permutation σ : N N of the agents Output: An allocation A A ( , . . . , ) Execute one round of serial dictatorship according to σ. Assign all remaining goods to the last agent in σ. return A

ditive valuations, strategyproofness is known to be incompatible even with EF1 (Amanatidis et al. 2017). By contrast, for lexicographic preferences, we will show that strategyproofness can be achieved in conjunction with a stronger fairness guarantee (EFX) as well as Pareto optimality, nonbossiness, and neutrality (Theorem 2). Indeed, Algorithm 2, a special case of Algorithm 1 where the last agent gets all the remaining goods characterizes these properties. Our characterization result builds upon an existing result of Hosseini and Larson (2019, Theorem 5.6) (see Proposition 2) that characterizes four out of the ﬁve properties mentioned above (excluding EFX) in terms of Serial Dictatorship Quota Mechanisms (SDQ), as deﬁned below. Deﬁnition 1. The Serial Dictatorship Quota (SDQ) mechanism is speciﬁed by a permutation σ : N N of the agents and a set of quotas (q1, . . . , qn) such that Pn i=1 qi = m. Given a lexicographic instance N, M, as input, the SDQ mechanism considers agents in the order σ, and assigns the ith agent its most preferred bundle of size qi from the remaining goods. The resulting allocation is returned as output.

Proposition 2 (Hosseini and Larson 2019). For lexicographic preferences, a mechanism is Pareto optimal, strategyproof, non-bossy, and neutral if and only if it is SDQ. The next result (Theorem 2) provides an algorithmic characterization of EFX, PO, strategyproofness, non-bossiness, and neutrality for lexicographic preferences. Theorem 2. For any ordering σ of the agents, Algorithm 2 is EFX, PO, strategyproof, non-bossy, and neutral. Conversely, any mechanism satisfying these properties can be implemented by Algorithm 2 for some σ.

Proof. Note that Algorithm 2 is a special case of SDQ for the quotas qi = 1 for all i [n 1] and qn = m (n 1). Therefore, from Proposition 2, it is PO, strategyproof, nonbossy, and neutral. Furthermore, Algorithm 2 is also a special case of Algorithm 1 and is therefore EFX (Theorem 1). To prove the converse, let f be an arbitrary mechanism satisfying the desired properties. From Proposition 2, f must be an SDQ mechanism for some ordering σ and some set of quotas (q1, . . . , qn) such that Pn i=1 qi = m. If m < n, the claim follows easily from Theorem 1, so we can assume, without loss of generality, that m n. Then, by Proposition 1, we must have that qi 1 for all i [n]. Therefore, it sufﬁces to show that qi = 1 for all i [n 1]. Assume, without loss of generality, that σ = (1, 2, . . . , n). Consider a preference proﬁle with identical preferences, i.e., i = k for all i, k [n]. Let g1 i g2 i i gm for any i [n]. Suppose, for

contradiction, that qi > 1 for some i [n 1], and let k [n 1] be the smallest index for which this happens. Since f is an SDQ mechanism, we have that gk fk( ) and |fk( )| = qk > 1. Then, for every ℓ> k, agent ℓ envies agent k. By Proposition 1, f violates EFX, which is a contradiction. Therefore, f must be identical to Algorithm 2 for the ordering σ, as desired.

We note that in this context any deterministic strategyproof and non-bossy mechanism is also groupstrategyproof (P apai 2000a). Therefore, Algorithm 2 also characterizes the set of EFX, PO, group-strategyproof, nonbossy, and neutral mechanisms under lexicographic preferences. In addition, we show that the set of properties considered in Theorem 2 is minimal. That is, dropping any property from the characterization necessarily allows for feasible mechanisms beyond those in Algorithm 2. Details and the proof are relegated to the full version (Hosseini et al. 2020). Proposition 3. The set {EFX, PO, strategyproofness, nonbossiness, neutrality} is a minimal set of properties for characterizing the family of mechanisms in Algorithm 2. The efﬁciency guarantee in Theorem 2 cannot be strengthened much further, as there exists an instance where any rank-maximal (RM) mechanism violates strategyproofness (Example 1). Example 1 (Strategyproofness and RM). Consider the instance with k + 2 goods g1, . . . , gk+2 and three agents:

a1 : g1 g2 g3 . . . gk+1 gk+2 a2 : g1 g2 g3 . . . gk+1 gk+2 a3 : g2 g3 g4 . . . gk+2 g1.

Each of the goods g2, . . . , gk+2 is ranked higher by a3 than by a1 or a2, and therefore must be assigned to a3 in any rank-maximal allocation. Suppose, under truthful reporting, g1 is assigned to a1, and a2 gets an empty bundle. Then, a2 could falsely report g3 as its favorite good. By rankmaximality, g3 is now assigned to a2, resulting in a strict improvement.

The non-existence result in Example 1 prompts us to forego strategyproofness (as well as non-bossiness and neutrality) and focus only on (approximate) envy-freeness and rank-maximality.

Envy-Freeness and Rank-Maximality For lexicographic preferences, it is easy to see that a complete allocation is envy-free if and only if each agent receives its favorite good. Checking the existence of an envy-free allocation therefore boils down to computing a (left-)perfect matching in a bipartite graph where the left and the right vertex sets correspond to the agents and the goods, respectively, and the edges denote the top-ranked good of each agent. If an envy-free partial allocation of the top-ranked goods exists, then it can be extended to a complete rank-maximal allocation by assigning each remaining good to an agent that has the highest rank for it (note that the assignment of the remaining goods does not introduce any envy). Thus, the existence of an envy-free and rank-maximal allocation can

be checked efﬁciently for lexicographic preferences (Proposition 4).

Proposition 4. There is a polynomial-time algorithm that, given a lexicographic instance as input, computes an envyfree and rank-maximal allocation, whenever one exists.

Since an envy-free allocation is not guaranteed to exist, one could ask whether rank-maximality can always be achieved alongside approximate envy-freeness; in particular, EFk and EFX. Example 2 shows that both of these notions could conﬂict with rank-maximality. Speciﬁcally, for any ﬁxed k N, an EFk+RM allocation could fail to exist. Since EFX implies EF1, a similar incompatibility holds for EFX+RM as well.

Example 2 (EFk and RM). Consider again the instance in Example 1. Any rank-maximal allocation assigns the goods g2, . . . , gk+2 to a3. If g1 is assigned to a1, then a2 gets an empty bundle and the pair {a2, a3} violates EFk.

Given the non-existence result in Example 2, a natural question is whether there exists an efﬁcient algorithm for checking the existence of an approximately envy-free and rank-maximal allocation. Unfortunately, the news here is also negative, as the problem turns out to be NP-complete (Theorem 3). Thus, while EFX can always be achieved in conjunction with Pareto optimality (Theorems 1 and 2), strengthening the efﬁciency notion to rank-maximality results in non-existence and computational hardness.

Theorem 3. Determining whether a given instance admits an EFX and rank-maximal allocation is NP-complete.

Proof. Membership in NP follows from the fact that both EFX and rank-maximality can be checked in polynomial time. To prove NP-hardness, we will show a reduction from a restricted version of 3-SAT called (2/2/3)-SAT, which is known to be NP-complete (Ahadi and Dehghan 2019). An instance of (2/2/3)-SAT consists of a collection of r variables X1, . . . , Xr and s clauses C1, . . . , Cs, where each clause is speciﬁed as a disjunction of three literals, and each variable occurs in exactly four clauses, twice negated and twice non-negated. The goal is to determine if there is a truth assignment that satisﬁes all clauses. Construction of the reduced instance: We will construct a fair division instance with n = 4r agents and m = 4r + s goods. The set of agents consists of 2r literal agents {xi, xi}i [r], and 2r dummy agents {di, di}i [r]. The set of goods consists of 2r signature goods {Si, Si}i [r], s clause goods {Cj}j [s], and 2r dummy goods {Ti, Bi}i [r]; here Ti and Bi denote the top and the bottom dummy goods associated with the variable Xi, respectively. Preferences: Table 1 shows the preferences of the agents. Let deﬁne a reference ordering on the set of goods. For every i [r], if Cj and Ck denote the two clauses containing the positive literal xi, then the literal agent xi ranks Si at the top, and the clause goods Cj and Ck at ranks j + 1 and k + 1, respectively. The missing positions consist of remaining goods ranked according to (we write ℓto denote the top ℓgoods in that have not been ranked so far). The symbol indicates rest of the goods ordered according to . The

: S1 S1 Sr Sr T1 Tr

C1 Cs B1 Br xi: Si (j 1) Cj (k j 1) Ck

xi: Si (p 1) Cp (q p 1) Cq

di: Ti Si Bi and di : Ti Si Bi .

Table 1: Preferences of agents in the proof of Theorem 3.

preferences of the (negative) literal agent xi and the dummy agents di, di are deﬁned similarly as shown in Table 1. This completes the construction of the reduced instance. Note that for any ﬁxed i [r], the signature good Si (or Si) is ranked at the top position by the literal agent xi (or xi), and at a lower position by all other agents. Therefore, any rank-maximal allocation must assign Si to xi and Si to xi. For a similar reason, a rank-maximal allocation must assign the clause good Cj to a literal agent corresponding to a literal contained in the clause Cj, and the dummy goods Ti, Bi to the dummy agents di, di. The aforementioned necessary conditions for rank-maximality are also sufﬁcient since each clause good Cj is ranked at the same position by all literal agents corresponding to the literals contained in clause Cj, and the goods Ti and Bi are ranked identically by di and di. We will now argue the equivalence of solutions. ( ) Given a satisfying truth assignment, the desired allocation, say A, can be constructed as follows: For every i [r], assign the signature goods Si and Si to the literal agents xi and xi, respectively. If xi = 1, then assign Ti to di and Bi to di, otherwise, if xi = 0, then assign Ti to di and Bi to di. For every j [s], the clause good Cj is assigned to a literal agent xi (or xi) if the literal xi (or xi) is contained in the clause Cj and the clause is satisﬁed by the literal, i.e., xi = 1 (or xi = 1). Note that under a satisfying assignment, each clause must have at least one such literal. Observe that allocation A satisﬁes the aforementioned sufﬁcient condition for rank-maximality. Furthermore, any envied agent in A receives exactly one good; in particular, if di receives a bottom dummy good Bi, then we have xi = 0 in which case the literal agent xi, who is envied by di, does not receive any clause goods. By Proposition 1, A is EFX. ( ) Now suppose there exists an EFX and rank-maximal allocation A. Then, A must satisfy the aforementioned necessary condition for rank-maximality. That is, for every i [r], the signature goods Si and Si are assigned to the literal agents xi and xi, respectively (i.e., Si Axi and Si Axi), and the dummy goods Ti and Bi are allocated between the dummy agents di and di (i.e., {Ti, Bi} Adi Adi). In addition, for every j [s], the clause good Cj is assigned to a literal agent xi (or xi) such that the literal xi (or xi) is contained in the clause Cj. Also, by Proposition 1, each dummy agent must get exactly one dummy good. We will construct a truth assignment for the (2/2/3)-SAT instance as follows: For every i [r], if Ti Adi, then set xi = 1, otherwise set xi = 0. Note that the assignment is feasible as no literal is assigned conﬂicting values. To see why this is a satisfying assignment, consider any clause Cj.

Suppose the clause good Cj is assigned to a literal agent xi (an analogous argument works when xi gets Cj). Then, due to rank-maximality, we know that the literal xi must be contained in the clause Cj. Furthermore, since agent xi gets more than one good (Si, Cj Axi), it cannot be envied under A (Proposition 1). Thus, the dummy agent di must get the top good Ti. Recall that in this case we set xi = 1. Since clause Cj contains xi, it must be satisﬁed, as desired.

The intractability in Theorem 3 persists even when we relax the fairness requirement from EFX to EFk. Theorem 4. For any ﬁxed k N, determining the existence of an EFk and rank-maximal allocation is NP-complete. We note that the proof of Theorem 4 (see the full version (Hosseini et al. 2020) for details) differs considerably from that of Theorem 3 as neither result is an immediate consequence of the other. Indeed, a YES instance of EFX+RM is also a YES instance of EFk+RM, but the same is not true for a NO instance. A corollary of Theorem 4 is that checking the existence of EF1+RM allocations for additive valuations is also NPcomplete.2 For this setting, Aziz et al. (2019) have shown NP-completeness even for three agents. By contrast, we will show that for lexicographic preferences, the problem is efﬁciently solvable when n = 3 (Proposition 5). The proof of this result is deferred to the full version of the paper (Hosseini et al. 2020). Proposition 5. There is a polynomial-time algorithm that, given as input a lexicographic instance with three agents, computes an EF1 and rank-maximal allocation, whenever one exists. Another avenue for circumventing the intractability in Theorem 3 is provided by maximin share guarantee (MMS). For additive valuations, EFX and MMS are incomparable notions (Amanatidis, Birmpas, and Markakis 2018). However, for lexicographic preferences, MMS is strictly weaker than EFX (see the full version (Hosseini et al. 2020) for details). This relaxation of EFX turns out to be computationally useful, as the existence of an MMS and RM allocations can be checked in polynomial time. Theorem 5. There is a polynomial-time algorithm that, given as input a lexicographic instance, computes an MMS and rank-maximal allocation, whenever one exists. We defer the proof of Theorem 5 to the full version (Hosseini et al. 2020), and brieﬂy outline the algorithm below. Fix any agent i N, and suppose its preference is given by i := g1 g2 . . . gm. Under lexicographic preferences, the MMS partition of agent i N is uniquely deﬁned as {{g1}, {g2}, . . . , {gn 1}, {gn, gn+1, . . . , gm}}. This observation gives a characterization of MMS allocations: An allocation is MMS if and only if each agent either receives one or more of its top-(n 1) goods, or it receives all of its bottom-(m n + 1) goods. Construct a bipartite graph G = (N M, E) between agents and goods where an edge (i, j) E exists if agent i

2An additive valuations instance in which agent i values its jth

favorite good at 2m j+1 is equivalent to the lexicographic instance.

Figure 2: The plots show how the fraction of instances that admit {EF, EFX, EF1, MMS} + RM allocations varies with the number of goods. The number of agents is ﬁxed (n = 5). Preferences follow the Mallows model with dispersion parameter φ.

ranks good j within its top-(n 1) goods, and good j can be rank-maximally assigned to agent i. In other words, agent i ranks good j at least as high as any other agent. If G admits a perfect matching (this can be checked in polynomial time), then, by the above characterization, we have a partial allocation that is MMS and rank-maximal. By assigning the unmatched goods in a rank-maximal manner (which can be done in polynomial time), we obtain a desired complete allocation.

Experiments We now revisit the non-existence result in Example 2 by examining how frequently {EF, EFX, EF1, MMS} + RM allocations exist in synthetically generated data. To that end, we consider a ﬁxed number of agents (n = 5) whose preferences over a set of m goods (where m {5, . . . , 15}) are generated using the Mallows model (Mallows 1957). Given a reference ranking L and a dispersion parameter φ [0, 1], the probability of generating a ranking i L under the Mallows model is given by 1

Z φd( , i), where Z is a normalization constant and d( ) is the Kendall s Tau distance. Thus, φ = 0 induces identical preferences (i.e., i = ) while φ = 1 is the uniform distribution. For each combination of m, n, and φ {0, 0.25, 0.5, 0.75, 1}, we sample 1000 preference proﬁles, and use an integer linear program to check the existence of {EF, EFX, EF1, MMS}+ RM allocations. Code and data for all our experiments is available at https://github.com/sujoyksikdar/Envy-Freeness With-Lexicographic-Preferences. Figure 2 presents our experimental results. For identical preferences (φ = 0), every complete allocation is Pareto optimal as well as rank-maximal. Therefore, an EFX+RM (and hence {EF1, MMS}+RM) allocation always exists in this case, validating our theoretical result in Theorem 1. On the other hand, an EF+RM allocation fails to exist because of the conﬂict in top-ranked goods. At the other extreme for φ = 1 (i.e., the uniform distribution), we note that the probability of existence of EF+RM outcomes grows steadily with m. This is because for (exact) envy-freeness, all ﬁve rankings should have distinct top goods, the probability of which is (1 1

m). For m = 100, this value is roughly 0.9, suggesting that in the asymptotic regime, envy-free (and, by extension, EF+RM) allocations are increasingly likely to exist, and our algorithm in Proposition 4 will return EF+RM outcomes with high probability.

We observe that the gap between the fractions of instances that admit EFX+RM allocations and EF+RM allocations decreases with the number of goods. We conjecture that as the number of goods increases, the likelihood that every agent must be allocated more than one good in any RM allocation increases. Therefore, it is likely that envied agents receive more than one good, which is in direct conﬂict with EFX. In the full version (Hosseini et al. 2020), we test this conjecture through experiments for larger values of m, and observe an increasing trend in the fractions of instances that admit EF+RM allocations as well as those that admit EFX+RM allocations, while the gap between the two shrinks rapidly, and becomes negligible for larger number of goods. We also observe the general trend in our plots that {EF1, MMS} + RM allocations tend to exist more frequently as the number of goods increases. Together, these observations suggest that the distributional approach could be a promising avenue for addressing the non-existence result in Example 2.

Concluding Remarks

We studied the interplay of fairness and efﬁciency under lexicographic preferences, obtaining strong algorithmic characterizations for EFX and Pareto optimality that addressed notable gaps in the additive valuations model, and outlining the computational limits of our approach for the stronger efﬁciency notion of rank-maximality. Going forward, it would be interesting to develop distribution-speciﬁc algorithms that can compute EFX+RM (or EF1+RM) allocations with, say, a constant probability. Extending our algorithmic characterization results to other fairness notions, speciﬁcally EF1 and MMS, will also be of interest.

Acknowledgments

HH acknowledges support from NSF grant #1850076. RV acknowledges support from ONR#N00014-171-2621 while he was afﬁliated with Rensselaer Polytechnic Institute, and is currently supported by project no. RTI4001 of the Department of Atomic Energy, Government of India. Part of this work was done while RV was supported by the Prof. R Narasimhan postdoctoral award. LX acknowledges support from NSF #1453542 and #1716333, ONR #N00014-1712621, and a gift fund from Google. We thank the anonymous reviewers for their very helpful comments and suggestions.

References Ahadi, A.; and Dehghan, A. 2019. (2/2/3)-SAT Problem and its Applications in Dominating Set Problems. Discrete Mathematics & Theoretical Computer Science 21(4).

Amanatidis, G.; Birmpas, G.; Christodoulou, G.; and Markakis, E. 2017. Truthful Allocation Mechanisms without Payments: Characterization and Implications on Fairness. In Proceedings of the 2017 ACM Conference on Economics and Computation, 545 562.

Amanatidis, G.; Birmpas, G.; Filos-Ratsikas, A.; Hollender, A.; and Voudouris, A. A. 2020. Maximum Nash Welfare and Other Stories about EFX. In In Proceedings of the 29th International Joint Conference on Artiﬁcial Intelligence, 24 30.

Amanatidis, G.; Birmpas, G.; and Markakis, E. 2018. Comparing Approximate Relaxations of Envy-Freeness. In Proceedings of the 27th International Joint Conference on Artiﬁcial Intelligence, 42 48.

Amanatidis, G.; Markakis, E.; and Ntokos, A. 2020. Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination. Theoretical Computer Science 841: 94 109.

Aziz, H.; Huang, X.; Mattei, N.; and Segal-Halevi, E. 2019. The Constrained Round Robin Algorithm for Fair and Efﬁcient Allocation. ar Xiv preprint ar Xiv:1908.00161 .

Aziz, H.; and Kasajima, Y. 2017. Impossibilities for Probabilistic Assignment. Social Choice and Welfare 49(2): 255 275.

Barman, S.; Krishnamurthy, S. K.; and Vaish, R. 2018. Finding Fair and Efﬁcient Allocations. In Proceedings of the 2018 ACM Conference on Economics and Computation, 557 574.

Baumeister, D.; Bouveret, S.; Lang, J.; Nguyen, N.-T.; Nguyen, T. T.; Rothe, J.; and Safﬁdine, A. 2017. Positional Scoring-Based Allocation of Indivisible Goods. Autonomous Agents and Multi-Agent Systems 31(3): 628 655.

B erczi, K.; B erczi-Kov acs, E. R.; Boros, E.; Gedefa, F. T.; Kamiyama, N.; Kavitha, T.; Kobayashi, Y.; and Makino, K. 2020. Envy-free Relaxations for Goods, Chores, and Mixed Items. ar Xiv preprint ar Xiv:2006.04428 .

Bogomolnaia, A.; and Moulin, H. 2001. A New Solution to the Random Assignment Problem. Journal of Economic Theory 100(2): 295 328.

Budish, E. 2011. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy 119(6): 1061 1103.

Caragiannis, I.; Gravin, N.; and Huang, X. 2019. Envy Freeness Up to Any Item with High Nash Welfare: The Virtue of Donating Items. In Proceedings of the 2019 ACM Conference on Economics and Computation, 527 545.

Caragiannis, I.; Kurokawa, D.; Moulin, H.; Procaccia, A. D.; Shah, N.; and Wang, J. 2019. The Unreasonable Fairness of Maximum Nash Welfare. ACM Transactions on Economics and Computation 7(3): 12.

Chaudhury, B. R.; Garg, J.; and Mehlhorn, K. 2020. EFX Exists for Three Agents. In Proceedings of the Twenty-First ACM Conference on Economics and Computation, 1 19. Chaudhury, B. R.; Garg, J.; and Mehta, R. 2020. Fair and Efﬁcient Allocations under Subadditive Valuations. ar Xiv preprint ar Xiv:2005.06511 . Chaudhury, B. R.; Kavitha, T.; Mehlhorn, K.; and Sgouritsa, A. 2020. A Little Charity Guarantees Almost Envy Freeness. In Proceedings of the Fourteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2658 2672. Chen, X.; and Liu, Z. 2020. The Fairness of Leximin in Allocation of Indivisible Chores. ar Xiv preprint ar Xiv:2005.04864 . Elkind, E.; Lackner, M.; and Peters, D. 2016. Preference Restrictions in Computational Social Choice: Recent Progress. In Proceedings of the Twenty-Fifth International Joint Conference on Artiﬁcial Intelligence, 4062 4065. Farhadi, A.; Hajiaghayi, M.; Latiﬁan, M.; Seddighin, M.; and Yami, H. 2020. Almost Envy-Freeness, Envy-Rank, and Nash Social Welfare Matchings. ar Xiv preprint ar Xiv:2007.07027 . Fujita, E.; Lesca, J.; Sonoda, A.; Todo, T.; and Yokoo, M. 2018. A Complexity Approach for Core-Selecting Exchange under Conditionally Lexicographic Preferences. Journal of Artiﬁcial Intelligence Research 63: 515 555. Gigerenzer, G.; and Goldstein, D. G. 1996. Reasoning the Fast and Frugal Way: Models of Bounded Rationality. Psychological Review 103(4): 650. Hosseini, H.; and Larson, K. 2019. Multiple Assignment Problems under Lexicographic Preferences. In Proceedings of the 18th International Conference on Autonomous Agents and Multi Agent Systems, 837 845. Hosseini, H.; Sikdar, S.; Vaish, R.; and Xia, L. 2020. Fair and Efﬁcient Allocations under Lexicographic Preferences. ar Xiv preprint ar Xiv:2012.07680 . Irving, R. W.; Kavitha, T.; Mehlhorn, K.; Michail, D.; and Paluch, K. 2006. Rank-Maximal Matchings. ACM Transactions on Algorithms 2: 602 610. Kojima, F. 2009. Random Assignment of Multiple Indivisible Objects. Mathematical Social Sciences 57(1): 134 142. Lang, J.; Mengin, J.; and Xia, L. 2018. Voting on Multi Issue Domains with Conditionally Lexicographic Preferences. Artiﬁcial Intelligence 265: 18 44. Mahara, R. 2020. Existence of EFX for Two Additive Valuations. ar Xiv preprint ar Xiv:2008.08798 . Mallows, C. L. 1957. Non-Null Ranking Models. Biometrika 44(1/2): 114 130. Nguyen, T. T. 2020. How to Fairly Allocate Indivisible Resources Among Agents Having Lexicographic Subadditive Utilities. In Frontiers in Intelligent Computing: Theory and Applications, 156 166. Paluch, K. 2013. Capacitated Rank-Maximal Matchings. In International Conference on Algorithms and Complexity, 324 335. Springer.

P apai, S. 2000a. Strategyproof Assignment by Hierarchical Exchange. Econometrica 68(6): 1403 1433. P apai, S. 2000b. Strategyproof Multiple Assignment Using Quotas. Review of Economic Design 5: 91 105. Plaut, B.; and Roughgarden, T. 2020. Almost Envy-Freeness with General Valuations. SIAM Journal on Discrete Mathematics 34(2): 1039 1068. Pruhs, K.; and Woeginger, G. J. 2012. Divorcing Made Easy. In International Conference on Fun with Algorithms, 305 314. Saban, D.; and Sethuraman, J. 2014. A Note on Object Allocation under Lexicographic Preferences. Journal of Mathematical Economics 50: 283 289. Schmitt, M.; and Martignon, L. 2006. On the Complexity of Learning Lexicographic Strategies. Journal of Machine Learning Research 7(Jan): 55 83. Schulman, L. J.; and Vazirani, V. V. 2015. Allocation of Divisible Goods Under Lexicographic Preferences. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 543. Sikdar, S.; Adali, S.; and Xia, L. 2017. Mechanism Design for Multi-Type Housing Markets. In Thirty-First AAAI Conference on Artiﬁcial Intelligence, 684 690. Taylor, M. 1970. The Problem of Salience in the Theory of Collective Decision-Making. Behavioral Science 15(5): 415 430. Varian, H. R. 1974. Equity, Envy, and Efﬁciency. Journal of Economic Theory 9(1): 63 91. Zhou, L. 1990. On a Conjecture by Gale about One-Sided Matching Problems. Journal of Economic Theory 52(1): 123 135.