# envyfree_house_allocation_under_uncertain_preferences__613572c3.pdf

Envy-Free House Allocation under Uncertain Preferences

Haris Aziz1, Isaiah Iliffe1, Bo Li2, Angus Ritossa1, Ankang Sun2, Mashbat Suzuki1

1UNSW Sydney 2Hong Kong Polytechnic University haris.aziz@unsw.edu.au, i.iliffe@student.unsw.edu.au, bo.li@polyu.edu.hk, a.ritossa@student.unsw.edu.au, ankang.sun@polyu.edu.hk, mashbat.suzuki@unsw.edu.au

Envy-freeness is one of the most important fairness concerns when allocating resources. We study the envy-free house allocation problem when agents have uncertain preferences over items and consider several well-studied preference uncertainty models. The central problem that we focus on is computing an allocation that has the highest probability of being envy-free. We show that each model leads to a distinct set of algorithmic and complexity results, including detailed results on (in-)approximability. En route, we consider two related problems of checking whether there exists an allocation that is possibly or necessarily envy-free. We give a complete picture of the computational complexity of these two problems for all the uncertainty models we consider.

1 Introduction Multi-agent resource allocation is one of the fundamental issues at the intersection of computer science and economics. We consider a fundamental allocation problem in which agents have preferences over items or houses and each agent is allocated one house while taking into account their preferences. The problem has been referred to as the house allocation or assignment problem. When agents have deterministic preferences over items, the problem is very well-understood. For example, there are characterizations of Pareto optimal allocations (see, e.g. (Abdulkadiro glu and S onmez 1998)) and polynomial-time algorithms for computing envy-free allocations (see, e.g. (Gan, Suksompong, and Voudouris 2019)). In this paper, we focus on fairly allocating items in the house allocation problem. The central fairness concept we consider is envy-freeness (EF) which is considered one of the gold-standard for capturing fairness. An allocation is EF if every agent gets her favorite house among all the houses assigned to the agents. While the structure of EF allocations under deterministic preferences is well-understood, there is little prior work on the complexity of computing EF house allocations under uncertain preferences. Uncertain preferences are important to model when agents preferences may not be completely known, and the central planner may have to make decisions based on limited information. The uncertainty model can also capture the situation when the agents

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

represent a group of agents with a composition of preferences. Various types of uncertain preferences have been examined in the literature (see, e.g, (Hazon et al. 2012; Aziz et al. 2019, 2020, 2022)), including the lottery Model, the joint probability model, and the compact indifference model. All the models are well motivated and some real-world applications can be found in, for example, (Aziz et al. 2020). Given an instance in which agents uncertain preferences are given as input, the central problem that we consider is MAX-PROBEF which concerns computing an allocation with the highest probability of being EF. Such an allocation can be viewed as being robustly fair under uncertain information. En route, we consider two related problems: EXISTSPOSSIBLYEF (i.e., does there exist an allocation that is EF with non-zero probability?) and EXISTSCERTAINLYEF (i.e., does there exist an allocation that is EF with probability one?). Our work aims to present a comprehensive study of the computation complexity for all these problems under various uncertainty models.

Problems Lottery Compact Joint indifference Prob

EXISTSPOSSIBLYEF NP-c in P in P

EXISTSCERTAINLYEF NP-c in P NP-c

MAX-PROBEF NP-h NP-h NP-h

Table 1: Summary of the main results. The symbol indicates that the problem admits no bounded multiplicative approximation, assuming P =NP. The symbol indicates that the problem admits no polynomially-bounded multiplicative approximation, assuming P =NP. The symbol indicates that there is no polynomial-time algorithm with better than 6 5-approximation ratio, assuming P =NP. The symbol indicates the problem admits a polynomial-time algorithm that either solves MAX-PROBEF exactly or certiﬁes that every allocation has a small probability of being EF.

Contributions In this work, we consider three natural and well-motivated uncertain preference models, namely, the lottery model, the compact indifference model, and the joint probability model. In the lottery model, each agent has

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

an independent probability distribution over linear preferences. In the joint probability model, the input is a probability distribution over preference proﬁles. The compact indifference model is a special type of lottery model in which the input is each agent having a corresponding weak order of the items and each complete linear order extension of this weak order is assumed to be equally likely. For each model, we ﬁrst present the computational complexity results of checking whether there exists an allocation that is possibly envy-free (EXISTSPOSSIBLYEF) or necessarily envyfree (EXISTSCERTAINLYEF). Then we undertake a detailed complexity analysis of the central problem MAX-PROBEF of computing an allocation that has the highest probability of being envy-free. Our results are summarized in Table 1.

Lottery Model We start with the lottery model. We prove that both EXISTSPOSSIBLYEF and EXISTSCERTAINLYEF are NP-complete. The intractability of EXISTSPOSSIBLYEF also implies that there is no polynomial-time algorithm with bounded multiplicative approximation ratio for MAXPROBEF, assuming P =NP.

Compact Indifference Model In sharp contrast to the lottery model, we show that there exist polynomial-time algorithms for EXISTSPOSSIBLYEF and EXISTSCERTAINLYEF. However, the main problem MAX-PROBEF continues to be intractable: we actually prove that ﬁnding an f(n, m)- approximation of MAX-PROBEF under the compact indifference model is NP-hard where f(n, m) is an arbitrary polynomial in the numbers of agents n and houses m. We complement this result by presenting a central algorithmic result: for any ﬁxed ϵ > 0, there exists a polynomial-time algorithm that either computes the optimal solution for MAXPROBEF exactly, or returns a certiﬁcate that every allocation has EF probability less than ϵ. We regard this part as the main contribution of this work.

Joint Probability Model Finally, we study the joint probability model. We ﬁrst show that EXISTSPOSSIBLYEF can be solved in polynomial time, while EXISTSCERTAINLYEF is NP-complete. Then we prove that there is no polynomialtime algorithm with a ( 6

5 ϵ)-approximation ratio for MAXPROBEF for any constant ϵ > 0, assuming P =NP.

2 Related Work Our work combines aspects of envy-free allocation and uncertainty in preferences that have been explored in the context of stable marriage, voting, and Pareto optimal allocation. The house allocation problem is one of the most fundamental and well-studied problems in economics and computer science (Abdulkadiro glu and S onmez 1999; Abraham et al. 2005; Aziz et al. 2016; Bogomolnaia and Moulin 2001; G ardenfors 1973; Svensson 1994, 1999). Typically, the problem has an equal number of agents and houses and the goal is to allocate one house to each agent. In our setup, we allow the number of houses to be more than the number of agents. Gan, Suksompong, and Voudouris (2019) presented an elegant polynomial-time algorithm to check whether an envy-free allocation exists or not in which each

agent gets one item. Aigner-Horev and Segal-Halevi (2022) also presented similar arguments for envy-free outcomes for bipartite graphs. Uncertainty in preferences has already been studied in voting (Hazon et al. 2012). They examine the computation of the probability of a particular candidate winning an election under uncertain preferences for various voting rules such as Plurality, k-approval, Borda, Copeland, and Bucklin etc. Aziz et al. (2019) explore the Pareto optimal allocation under uncertain preferences. We consider the same problem setup and preference uncertainty models as them but instead of focusing on Pareto optimality, our central property is envy-freeness. Aziz et al. (2020, 2022) examined uncertain preferences in the context of two-sided matching. The central property they examine is stability and they compute matchings that have the highest probability of being stable. In a related line of work, Dickerson et al. (2014) initiated the study of existence of envy-free allocations when agent valuations for items are drawn from a probability distribution. In follow up work, Manurangsi and Suksompong (2019, 2021) further reﬁned the parameter ranges for which envy-free allocations exist with high probability. There has been several other works (Farhadi et al. 2019; Bai et al. 2022; Bai and G olz 2022) on studying fair division under distributional models. In these models, where agent values are drawn from a distribution, allocations can change after the realization of the coin toss, whereas in our setting, we study a ﬁxed allocation that is robust under uncertainty.

3 Preliminaries An instance of the (deterministic) house allocation problem is a triple (N, H, ) where N = {1, . . . , n} is the set of n agents, H = {h1, . . . , hm} is the set of m items (also referred to as houses), and the preference proﬁle = ( 1 , . . . , n) speciﬁes complete and asymmetric preferences i of each agent i over H. Note that in the classical allocation problem, agents preferences are also assumed to be transitive, hence resulting in linearly ordered preferences. In some examples, we will represent the preferences as an ordered list in decreasing order of preferences from left to right. Let R(H) denote the set of all complete and asymmetric relations over the set of items H. An allocation is an assignment of items to agents such that each agent is allocated a unique item, and each item is allocated to at most one agent. Throughout the paper we assume m n as the only envy-free allocation in the case of m < n is one in which no agent gets any item. For a given allocation ω, let ω(i) denote the item allocated to agent i. We denote the set of all allocations by A . An allocation ω is envy-free (EF) if ω(i) i ω(j) for i N and j N \ {i}. In this work, we allow agents to express uncertainty in their preferences and consider various uncertainty models.

Lottery Model: For each agent i N, we are given a probability distribution i(R(H)) over linear preferences. We assume that the probability distributions are independent. Compact Indifference Model: Each agent reports a single weak preference list that allows for ties. Each com-

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

plete linear order extension of this weak order is assumed to be equally likely. We use a i b to represent that a is weakly preferred by i over b. We use a i b to represent that agent i is indifferent between a and b in the weak preference order. 1

Joint Probability Model: A probability distribution (R(H)n) over linear preference proﬁles is speciﬁed where a preference proﬁle speciﬁes (deterministic) preferences of each agent over items.

An uncertain preference model is independent if any uncertain preference proﬁle L under the model can be written as a product of uncertain preferences Li for all agents i, where all Li s are independent. Note that the joint probability model is not independent in general, but all the other problems that we study are independent. For the uncertainty models, we consider the following corresponding problems:

MAX-PROBEF: Given an instance of the problem, compute an allocation that maximizes the probability of being envy-free (EF). Formally,

arg max w A Pr D (R(H)n)[w is EF under proﬁle D].

EXISTSCERTAINLYEF: Determine whether there exists an allocation that is EF with probability one. EXISTSPOSSIBLYEF: Determine whether there exists an allocation that is EF with non-zero probability.

Note the answer to MAX-PROBEF also gives an answer to EXISTSCERTAINLYEF and EXISTSPOSSIBLYEF.

4 Initial Structural & Algorithmic Results In this section, we present some initial structural and algorithmic results. First we show that given an allocation, the probability that it is EF can be computed efﬁciently.

Proposition 4.1. Given allocation w, the probability that w is EF can be computed in polynomial time for the (i) joint probability model, (ii) lottery model, and (iii) compact indifference model.

The argument for the joint probability model is trivial. For the other models, for each agent i N, we ﬁnd the probability qi that the agent is not envious. The probability that w is envy-free is equal to the probability that all agents are envy-free which is computed as Q i N qi. The details are in the full paper (Aziz et al. 2023). Next, we present some structural results that suggest that the main challenge of Max-Prob EF lies in determining which houses are included in the matching. We say that an uncertain preference model is reasonable if for any set M M with |M | = n of houses, and any i N and

1The assignment problem is also known as the House Allocation problem. The compact indifference model can be viewed as the assignment problem with ties, or as it is widely known in the literature as the House Allocation problem with Ties (HRT) (Manlove 2013), where any preference list obtained by breaking ties arbitrarily is possible, and all possible preferences have the same likelihood of being realized.

j M , the probability pij that j is the most preferred house for agent i among houses in M can be computed in polynomial time. Note that all the models we consider are reasonable. For example, we argue why the lottery model is reasonable. Let i = (λr, r i )r S be the uncertain preferences of agent i, observe that pij can be computed efﬁciently since pij = P

{r S |j r i ℓ, ℓ M \j} λr.

Proposition 4.2. For any reasonable uncertainty model that is independent, given a set M M with |M | = n of houses, an allocation of M to N which maximizes the probability of EF can be computed in polynomial time.

Proof. Construct a complete weighted bipartite graph G = (N M , E) with edge weights wij = log(pij) for each i N, j M . Here pij denotes the probability that the house j is agent i s favourite when the houses are restricted to M . Observe now that the maximum weight matching in G gives an allocation that maximizes the probability of EF when the houses are restricted to M . This holds since pij is the probability that i does not envy any other agent when assigned j, and thus the probability that an allocation w is envy free is Q i N pi,w(i). Furthermore, the allocation that maximizes Q i N pi,w(i) also maximizes P i N log(pi,w(i)).

Proposition 4.2 implies that in order to ﬁnd the optimal solution to Max-Prob EF it sufﬁces to ﬁnd the houses that are assigned in the optimal solution rather than the allocation itself. Hence we may focus our attention on ﬁnding a set of houses M with |M | = n such that G = (N M , E) has the highest max weight matching. Our insights give the following algorithmic result.

Proposition 4.3. For any independent reasonable uncertainty model, Max-Prob EF problem with m = n+k houses can be solved in polynomial time, for any constant k N.

Proof. We iterate through each of the m n house restrictions and run the polynomial-time algorithm proposed in Proposition 4.2. Return the allocation with the highest max weight matching among the m n bipartite graphs. This procedure is polynomial-time since the algorithm in Proposition 4.2 is called at most m n = n+k n = n+k k = O(nk) times. Note that aforementioned procedure outputs an optimal solution since it outputs an allocation that maximizes the probability of EF under the each possible house restriction.

5 Lottery Model In this section, we study the lottery model.

Theorem 5.1. For the lottery model, EXISTSCERTAINLYEF is NP-complete.

Proof Sketch. The problem EXISTSCERTAINLYEF is in NP because it can be checked in polynomial time whether a given allocation is certainly EF or not. To prove NP-hardness, we reduce from Restricted 3-Exact Cover: given a family F = {S1, . . . , Sn} of n subsets of S = {u1, . . . , u3m}, where each subset of F has cardinality three, and moreover each element in S appears in exactly

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

three subsets of F (hence n = 3m). The problems asks if there is a subfamily of m subsets that covers S. We now construct a house allocation instance under the lottery model with a set {1, . . . , 3m} of 3m agents and a set H = {h1 1, h2 1, h3 1, h1 2, h2 2, h3 2, . . . , h1 n, h2 n, h3 n} of 3n houses. Intuitively, every agent i corresponds to the element ui of Restricted 3-Exact Cover problem. For every subset Sj, we construct three houses h1 j, h2 j, h3 j. If an agent i is allocated one of these houses, this corresponds to the element ui being covered by the subset Sj. Preference lists of the agents are as follows. Fix an agent i, and let Si1, Si2, Si3 be the three subsets including element ui in the Restricted 3-Exact Cover instance. Then, for each Sij, we construct two preference lists for agent i, and hence in total six preference lists for each agent. In each linear preference, agent i prefers the nine houses corresponding to Si1, Si2, and Si3 more than the other houses. The order of the other houses is arbitrary, and so we only provide partial preference lists. For j = 1, 2, 3, suppose that element ui is the one with l(j)-th smallest index in Sij, and let {p(j), q(j)} = {1, 2, 3} \ {l(j)} be the set of other two indices. We say that the house hl(j) ij corresponds to element ui in the subset Sij. Agent i s two preferences for Si1 are

1. hl(1) i1 hp(1) i1 hq(1) i1 hl(2) i2 hp(2) i2 hq(2) i2

hl(3) i3 hp(3) i3 hq(3) i3 other houses;

2. hl(1) i1 hq(1) i1 hp(1) i1 hl(2) i2 hp(2) i2 hq(2) i2

hl(3) i3 hp(3) i3 hq(3) i3 other houses;

In particular, agent i prefers the three houses representing elements from Si1. Then, among the three houses from Sid (d = 1), she likes the one corresponding to ui the most. We construct similar lists for Si2 and Si3. In the full version of the paper (Aziz et al. 2023), we complete the reduction by showing there exists Restricted 3-Exact Cover if and only if there is a certainly EF allocation.

Theorem 5.2. For the lottery model, EXISTSPOSSIBLYEF is NP-complete.

We prove Theorem 5.2 via a sequence of reductions starting from MINIMUM COVERAGE, which is known to be NPhard (Vinterbo 2002). For this purpose, we introduce two new problems:

EXISTSPARTIALEF under binary preferences. In this problem, there is a set [n] of agents and a set H of m houses. Each agent has deterministic binary preferences over the houses: in particular, each agent i partitions the houses into two sets Ai, Bi where houses in the same set are valued equally, and ha i hb for all ha Ai and hb Bi. Additionally, an integer k is supplied (with k n). The goal is to determine whether there exists an allocation of houses to k agents such that these k agents are envy-free. The n k agents without a house do not experience envy. EXISTSPARTIALPOSSIBLYEF under the lottery model. This problem is similar to EXISTSPOSSIBLYEF, however an additional integer k is supplied (with k n). The

goal is to determine whether there exists an allocation of houses to k agents such the probability of envy-freeness is nonzero. The n k agents without a house do not experience envy.

We show that MINIMUM COVERAGE reduces to EXISTSPARTIALEF, which in turn reduces to EXISTSPARTIALPOSSIBLYEF which ﬁnally reduces to EXISTSPOSSIBLYEF. To prove the next lemma, we use a modiﬁcation of the proof from Theorem 3.5 of Kamiyama, Manurangsi, and Suksompong (2021). They prove hardness for a similar problem, where all n agents must be allocated houses with the requirement that at least k agents are envy-free. This is detailed in the full paper (Aziz et al. 2023).

Lemma 5.3. With binary preferences, EXISTSPARTIALEF is NP-hard.

For the next lemma, we reduce from EXISTSPARTIALEF under binary preferences, which is NP-hard from Lemma 5.3.

Lemma 5.4. For the lottery model, EXISTSPARTIALPOSSIBLYEF is NP-hard.

We are now ready to prove Theorem 5.2.

Proof of Theorem 5.2. The problem EXISTSPOSSIBLYEF is in NP because it can be checked in polynomial time whether an allocation is possibly EF or not. To prove NP-hardness, we reduce from EXISTSPARTIALPOSSIBLYEF under the lottery model, which is NP-hard from Lemma 5.4. Consider an instance I of EXISTSPARTIALPOSSIBLYEF under the lottery model with n agents and m houses {h1, . . . , hm} and parameter k. We construct an instance I of EXISTSPOSSIBLYEF under the lottery model with n agents and m + n k houses, where the agents in I correspond to agents in I. The houses are {h1, . . . , hm} {e1, . . . , en k}. Consider some agent i. Assume that this agent has ℓpreference lists in I, and that the j-th such preference list is aj,1 . . . aj,m. In the instance I , agent i has ℓ+ n k preference lists, each with equal probability:

For each j [ℓ], we have the list aj,1 . . . aj,m e1 . . . en k. For each j [n k], we have the list ej e1 . . . ej 1 ej+1 . . . en k a1,1 . . . a1,m. Note that the e1 . . . ej 1 segment is empty if j = 1, and the ej+1 . . . en k segment is empty if j = n k.

We now prove the answer to I is yes if and only if the answer to I is yes . Assume the answer to I is yes and we have an allocation where agents u1, . . . , uk are each allocated house ω(ui) in a possibly envy-free way. Let uk+1, . . . , un be the agents that were not allocated a house. We create an allocation ω for I as follows:

For each i [k], ω (ui) = ω(ui), For each i [k + 1, n], ω (ui) = ei k.

Consider some agent i [k], where ω (ui) = ω(ui). Since agent i is possibly envy-free in I, there exists some preference list in I where ω(ui) is preferred over every other

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

allocated house. However, this corresponds to a preference list in I where ω (ui) is preferred to all the other houses allocated in ω . Hence, agent ui is possibly envy-free in I . Now, consider some i [k +1, n]. There exists a preference list in I where ω (ui) = ei k is the most preferred house, and so agent ui is possibly envy-free in I . For the other direction, suppose we have a possibly envyfree allocation in I . At most n k agents were allocated houses in {e1, . . . , en k} and so at least k agents were allocated houses in {h1, . . . , hm}. These agents remain possibly envy-free if they are allocated the same house in I.

As a corollary, we get the following result.

Corollary 5.5. For the lottery model, there is no polynomial-time algorithm with bounded multiplicative approximation ratio for MAX-PROBEF, assuming P =NP.

6 Compact Indifference Model In this section, we show that, in contrast to the lottery model, EXISTSPOSSIBLYEF and EXISTSCERTAINLYEF are polynomial-time solvable. However, perhaps surprisingly, multiplicative approximation to MAX-PROBEF still remains hard. On the positive side, we give a polynomialtime algorithm that either solves MAX-PROBEF exactly or certiﬁes that every allocation has a small probability of being EF. Due to space constraints, we defer the missing proofs in this section to the full version of the paper (Aziz et al. 2023).

6.1 Complexity Results Our ﬁrst complexity result is a strong inapproximability one.

Theorem 6.1. Let f(n, m) be a polynomial in the number of agents and houses. Then, ﬁnding an f(n, m)-approximation of MAX-PROBEF under the compact indifference model is NP-hard.

Proof. We begin by describing how to ﬁnd the probability that a given allocation is EF. In particular, consider some allocation ω where agent i is allocated house ω(i). Firstly, if ω(j) i ω(i) for any i, j N then the allocation is envy-free with probability 0. Otherwise, for each agent i, let Xi = {j N : ω(i) i ω(j)}. Then, the probability of agent i being envy-free is 1 |Xi|, and, by independence, the probability that the allocation is envy-free is Πi N 1 |Xi|. We prove NP-hardness via a reduction from INDEPENDENT SET. Firstly, for convenience, we only provide partial preference lists in the proof. In particular, for each agent i, we provide a subset of houses H H and a weak preference list over these houses. For all other houses in H \ H , we assume that agent i values these strictly worse than all houses in H , and that agent i cannot be allocated any house in H \ H in a possibly-EF allocation. To do this, we introduce two new agents a1, a2 and two new houses e1, e2. Agents a1 and a2 have the following preferences:

a1: e1 a1 e2 a1 all houses in H, in some arbitrary strict ordering. a2: e2 a2 e1 a2 all houses in H, in the same arbitrary strict ordering.

Then, any possibly-EF allocation ω has ω(a1) = e1 and ω(a2) = e2. Now, reconsider agent i and the subset H H of houses that they have a preference list over. We can extend this preference list into a complete preference list over all houses in H {e1, e2}. In particular, assume that agent i s preference list over H is h1 i . . . i h|H | (note that this list could include weak preferences). Then, agent i s preference list over H {e1, e2} is: h1 i . . . i h|H | i e1 i e2 i all houses in H \ H , in any arbitrary order. Then, agent i cannot be allocated any house in H \ H (otherwise, agent i would envy agents a1 and a2), and so for convenience we omit these houses from the preference list. We now describe the reduction. First, note that any polynomial f(n, m) can be upper bounded by a function of the form a(n + m)r for some positive integers a and r. So, we assume that f(n, m) is of this form. Now, consider an instance I of INDEPENDENT SET with a graph G = (V, E), and a target k. The goal is to determine if there exists an independent set in G of size k. We construct an instance I of MAX-PROBEF as follows. For each vertex v V , we introduce two houses tv and fv, and an agent av. We will design our instance so that house tv will be allocated to agent av if v is in the independent set, and fv will be allocated to agent av otherwise. We will show later that no other agent can be allocated tv or fv. In particular, agent av s preference list is tv av fv. Our goal is to ﬁnd a large independent set, and so we would rather house tv be allocated. We do this using a single penalty gadget, where we apply a penalty for allocating house fv. In a single penalty gadget, we add two new agents a1, a2 and four new houses e1, e2, e3, e4:

a1 s preference list: e1 a1 e2 a1 fv a1 e3. a2 s preference list: e1 a2 e2 a2 fv a2 e4.

First, note that house fv cannot be allocated to agent a1 nor a2, because doing so is impossible without one of the agents being envious. Now, if fv is unallocated, then a1 can be allocated house e3 and a2 can be allocated house e4, so that both agents are certainly EF. Otherwise, if fv is allocated, then agents a1 and a2 must be allocated houses e1 and e2, giving each agent a 1

2 probability of EF. Hence, this gadget multiplies the probability of EF by 1

4 if house fv is allocated. Let α = 49ar2|V ||E|. We create α copies of the single penalty gadget for each house fv. Hence, if fv is allocated (and hence, vertex v is not in the independent set), then the probability of EF is multiplied by 1 4α . Now, for each edge uv E, either vertex u or v must not be in the independent set. Thus, at least one of tu and tv must be unallocated. We use double penalty gadgets for this purpose. A double penalty gadget is built for two houses h1, h2 and adds four new agents a1, a2, a3, a4 and eight new houses e1, e2, e3, e4, e5, e6, e7, e8:

a1 s preference list: e1 a1 e2 a1 e3 a1 e4 a1 h1 a1 e5. a2 s preference list: e1 a2 e2 a2 e3 a2 e4 a2 h1 a2 e6. a3 s preference list: e1 a3 e2 a3 e3 a3 e4 a3 h2 a3 e7.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

a4 s preference list: e1 a4 e2 a4 e3 a4 e4 a4 h2 a4 e8.

First, note that neither h1 nor h2 can be allocated to any of these agents. In particular, without loss of generality, if h1 is allocated to agents a1 or a2, then at least one of agent a1 and a2 will always be envious of the other. Now, if either h1 or h2 is allocated to some other agent, then one of the houses e1, e2, e3, e4 will be allocated to a1, a2, a3 or a4. Then, to avoid envy, all the agents a1, a2, a3, a4 will be allocated houses e1, e2, e3, e4 in some permutation. Therefore each agent will be EF with probability 1

4, and so all the agents are EF with probability 1 256. However, if both h1 and h2 are unallocated, then agents a1, a2, a3, a4 can be allocated houses e5, e6, e7, e8 respectively, and will all be EF with probability 1. Hence, this gadget multiplies the EF-probability by 1 256 if either of h1 or h2 are allocated. For each edge uv E, we add |V |α copies of this gadget for the following pairs of houses: (tu, tv), (tu, fv), (fu, tv). We claim that these gadgets together provide a penalty if both houses tu, tv are allocated:

If both tu and tv are allocated, then all 3|V |α gadgets provide penalty. Hence, the EF-probability is multiplied by 1 2563|V |α . If at most one of tu and tv are allocated, then exactly 2|V |α of the gadgets provide penalty. In particular, if neither tu and tv are allocated, then both fu and fv will be allocated, and so the (tu, fv) and (fu, tv) gadgets provide penalty, but the (tu, tv) gadgets do not. On the other hand, if tu is allocated but tv is unallocated, then fv is allocated and so the (tu, tv) and (tu, fv) gadgets provide penalty but the (fu, tv) gadgets do not. Finally, the case when tu is unallocated but tv is allocated is symmetric. Thus, the EF-probability is multiplied by 1 2562|V |α .

Therefore, if both tu and tv are allocated, then the EFprobability is multiplied by an additional 1 256|V |α , compared to the case where this does not happen. This completes the description of the instance I . It can be shown that the MAX-PROBEF instance I is polynomial in size, and has the same answer as the INDEPENDENT SET instance I. For further details, please refer to the full paper (Aziz et al. 2023).

Next, we complement the above result by showing that additive approximations for MAX-PROBEF are computationally tractable.

6.2 Algorithm for MAX-PROBEF

Let OPT be EF probability of the optimal solution to MAXPROBEF.

Theorem 6.2. For any ﬁxed ϵ > 0, there is a polynomial time algorithm such that it either

computes OPT exactly, or returns a certiﬁcate that OPT < ϵ i.e., every allocation has probability of EF less than ϵ

To prove the theorem, we show that there is a polynomialtime algorithm (Algorithm 1) with the above properties. Next, we specify some terminology and machinery for the algorithm and the corresponding proof. Consider some instance I under the compact indifference model, and assume that there exists an allocation ω with a non-zero EFprobability. Then, this allocation ω must be envy-free with respect to the underlying weak deterministic preferences, that is, ω(i) i ω(j) for all agents i, j. We deﬁne an n n binary matrix A, which we call the envy-matrix of ω, as follows:

Ai,j = 0, if ω(i) i ω(j) 1, otherwise (i.e. ω(i) i ω(j))

Lemma 6.3. Let ϵ be a constant satisfying 0 < ϵ 1. Consider an instance under the compact indifference model that admits an allocation ω with EF-probability at least ϵ. Let A be the envy-matrix of ω. Then: 1. The EF-probability of ω is Qn i=1 1 Pn j=1 Ai,j , and 2. Excluding the main diagonal, the number of 1s in the envy-matrix is at most 1

ϵ . For the ﬁrst condition, a single agent is envy-free with probability 1 Pn j=1 Ai,j , which is equivalent to the formula described in the proof of Proposition 4.1. Due to independence, we multiply these values for each agent. The second condition can be derived from the ﬁrst condition and the assumption that the EF-probability is at least ϵ. We utilise envy-matrices to prove Theorem 6.2. To this end, we introduce the ALLOCSATISFYINGENVYMATRIX problem. In this problem, each agent has weak deterministic preferences over the houses. Additionally, an n n matrix A is supplied. The goal is to ﬁnd an allocation ω satisfying the following condition, or determine that such an allocation does not exist. For all agents i, j: If Ai,j = 1, then ω(i) i ω(j). Otherwise, if Ai,j = 0, then ω(i) i ω(j). Informally, the goal is to ﬁnd an allocation that is at least as good as the envy matrix. Lemma 6.4. ALLOCSATISFYINGENVYMATRIX can be solved in polynomial time. We prove Lemma 6.4 by extending the algorithm of Gan, Suksompong, and Voudouris (2019). As an overview, our algorithm either (i) ﬁnds an allocation, or (ii) identiﬁes a set of houses, such that none of these houses can appear in any allocation satisfying the envy-matrix. In the case of (ii), these houses are deleted and the procedure repeats. This terminates when either an allocation is found, or less than n houses remain, and so no allocation exists.

Proof of Theorem 6.2. We introduce Algorithm 1 and prove its correctness. Consider an instance I. Let ω be an allocation with maximum EF-probability in I, and let this EFprobability be p. We ﬁrst consider the case where p ϵ. Let A be the envy-matrix of ω. From Lemma 6.3, we know that Qn i=1 1 Pn j=1 Ai,j = p ϵ and A has at most 1

ϵ 1s (excluding the main diagonal). Hence, line 4 will be run with this

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Algorithm 1: Additive Approximation for MAX-PROBEF Input: A compact indifference instance I and constant ϵ satisfying 0 < ϵ 1. Output: An allocation with maximum EF-Prob, if there is one with EF-Prob at least ϵ; otherwise, returns null. 1: allocs empty array 2: for each n n binary matrix A where Ai,i = 1 for all i N and there are at most 1

ϵ 1s outside the main diagonal do 3: if 1 Pn i=1 Pn j=1 Ai,j ϵ then

4: Create an ALLOCSATISFYINGENVYMATRIX instance with envy-matrix A and the same weak preferences as I. Solve this using Lemma 6.4 and let the result be ω. 5: if ω = null then 6: Append ω to allocs 7: end if 8: end if 9: end for 10: if allocs is non-empty then 11: return an allocation in allocs with maximum EF-Prob 12: else 13: return no solution 14: end if

envy-matrix and so an allocation ω will be found with EFprobability p. It follows that Algorithm 1 ﬁnds an allocation with maximum EF-probability in this case. Now, assume that p < ϵ. Then, every instance of ALLOCSATISFYINGENVYMATRIX will report no solution, and so Algorithm 1 will correctly determine that no allocation exists with EF-probability at least ϵ. We now analyse the time complexity. The for loop on

line 2 iterates over P 1

i = O(n 2 ϵ ) matrices, and this can be done with only polynomial overhead. Since the algorithm of Lemma 6.4 runs in polynomial time, the overall running time is O(n 2 ϵ poly(n, m)).

Next, we remark that EXISTSCERTAINLYEF can be solved in polynomial time for the compact indifference model, which is implied by Theorem 6.2 (with ϵ = 1).

Corollary 6.5. EXISTSCERTAINLYEF can be solved in polynomial time for the compact indifference model.

Additionally, by using the algorithm of Gan, Suksompong, and Voudouris (2019), we have the following:

Proposition 6.6. EXISTSPOSSIBLYEF can be solved in polynomial time for the compact indifference model.

7 Joint Probability Model We next show that even for an expansive uncertainty model such as joint probability, EXISTSCERTAINLYEF is NPcomplete.

Theorem 7.1. For the joint probability model, EXISTSCERTAINLYEF is NP-complete, even with a constant number of proﬁles.

The NP-hardness is proved via a reduction from EXISTSCERTAINLYEF under a restricted case of lottery model where each agent has at most six linear preferences. One

can verify that the proof of Theorem 5.1 shows that EXISTSCERTAINLYEF is NP-complete even in the restricted case of lottery model where each agent has six preferences. Consider an instance I of the restricted lottery model, in which there are n agents and m houses, and moreover each agent has six linear preferences. Denote by Pi = { i,1 , . . . , i,6} the set of ordinal preferences for agent i under I. We now construct an instance I of the joint probability model. Instance I has the same number n of agents and m of houses. There are six preference proﬁles, each with equal probability 1

6. For t [6], the t-th preference proﬁle is ( 1,t, 2,t, . . . , n,t). The detailed proofs are in included the full paper (Aziz et al. 2023). Recall that the probability of an assignment ω being EF is the summation of probability of preference proﬁle Pi, under which ω is EF. The reduction in the proof of Theorem 7.1 indeed implies the following; (i) there exists an assignment with EF-probability one in the restricted lottery model if and only if there exists an assignment with EF-probability one in the joint probability model; (ii) there does not exist an assignment with EF-probability one in the restricted lottery model if and only if there does not exist an assignment with EF-probability strictly greater than 5

6 in the joint probability model. Then we have the following theorem.

Theorem 7.2. For any constant ϵ > 0, there is no polynomial-time algorithm with a ( 6

5 ϵ)-approximation ratio for MAX-PROBEF under the joint probability model, assuming P =NP.

In contrast, EXISTSPOSSIBLYEF can be solved in polynomial time by running the algorithm of Gan, Suksompong, and Voudouris (2019) on each realizable preference proﬁle.

Proposition 7.3. EXISTSPOSSIBLYEF can be solved in polynomial time for the joint probability model.

8 Conclusion

In this paper, we study a fundamental problem of envy-free house allocation under uncertainty. For each of the uncertain preference models considered, we provide a complete set of complexity results. We ﬁnd that, surprisingly, each model gives rise to a different set of complexity results. Although we mainly focus on uncertainty models that assume underlying linear preferences, we also study uncertainty models that go beyond this assumption. For example, in the pairwise probability model, where each agent has pairwise independent preferences over items, we show (in the full paper (Aziz et al. 2023)) that all the problems we consider are NP-hard. One of our central results is a polynomial-time algorithm that either solves MAX-PROBEF exactly or certiﬁes that every allocation has a small probability of being EF in the compact indifference model. It is interesting to see if similar results can be achieved for other uncertain preference models. Another possible future direction is to ﬁnd the best multiplicative approximation ratio achievable for the joint probability model. Finally, it is intriguing to investigate similar problems for general resource allocation settings.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Acknowledgments This work was supported by NSF-CSIRO grant on Fair Sequential Collective Decision-Making . Bo Li is funded by NSFC under Grant No. 62102333 and HKSAR RGC under Grant No. Poly U 15224823. Mashbat Suzuki is partially supported by the ARC Laureate Project FL200100204 on Trustworthy AI .

References Abdulkadiro glu, A.; and S onmez, T. 1998. Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems. Econometrica, 66(3): 689 701. Abdulkadiro glu, A.; and S onmez, T. 1999. House Allocation with Existing Tenants. Journal of Economic Theory, 88(2): 233 260. Abraham, D. J.; Cechl arov a, K.; Manlove, D. F.; and Mehlhorn, K. 2005. Pareto Optimality in House Allocation Problems. In Proceedings of the 16th International Symposium on Algorithms and Computation (ISAAC), volume 3341 of Lecture Notes in Computer Science (LNCS), 1163 1175. Aigner-Horev, E.; and Segal-Halevi, E. 2022. Envy-free matchings in bipartite graphs and their applications to fair division. Inf. Sci., 587: 164 187. Aziz, H.; Bir o, P.; de Haan, R.; and Rastegari, B. 2019. Pareto optimal allocation under uncertain preferences: uncertainty models, algorithms, and complexity. Artiﬁcial Intelligence, 276: 57 78. Aziz, H.; Bir o, P.; Fleiner, T.; Gaspers, S.; de Haan, R.; Mattei, N.; and Rastegari, B. 2022. Stable matching with uncertain pairwise preferences. Theor. Comput. Sci., 909: 1 11. Aziz, H.; Bir o, P.; Gaspers, S.; de Haan, R.; Mattei, N.; and Rastegari, B. 2020. Stable Matching with Uncertain Linear Preferences. Algorithmica, 82(5): 1410 1433. Aziz, H.; Biro, P.; Lang, J.; Lesca, J.; and Monnot., J. 2016. Optimal Reallocation under Additive and Ordinal Preferences. In Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). Aziz, H.; Iliffe, I.; Li, B.; Ritossa, A.; Sun, A.; and Suzuki, M. 2023. Envy-free House Allocation under Uncertain Preferences. https://arxiv.org/abs/2312.11286. Bai, Y.; Feige, U.; G olz, P.; and Procaccia, A. D. 2022. Fair Allocations for Smoothed Utilities. In Pennock, D. M.; Segal, I.; and Seuken, S., eds., EC 22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 - 15, 2022, 436 465. ACM. Bai, Y.; and G olz, P. 2022. Envy-Free and Pareto-Optimal Allocations for Agents with Asymmetric Random Valuations. In Raedt, L. D., ed., Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, 53 59. ijcai.org. Bogomolnaia, A.; and Moulin, H. 2001. A New Solution to the Random Assignment Problem. Journal of Economic Theory, 100(2): 295 328.

Dickerson, J. P.; Goldman, J. R.; Karp, J.; Procaccia, A. D.; and Sandholm, T. 2014. The Computational Rise and Fall of Fairness. In Brodley, C. E.; and Stone, P., eds., Proceedings of the Twenty-Eighth AAAI Conference on Artiﬁcial Intelligence, July 27 -31, 2014, Qu ebec City, Qu ebec, Canada, 1405 1411. AAAI Press. Farhadi, A.; Ghodsi, M.; Hajiaghayi, M. T.; Lahaie, S.; Pennock, D. M.; Seddighin, M.; Seddighin, S.; and Yami, H. 2019. Fair Allocation of Indivisible Goods to Asymmetric Agents. J. Artif. Intell. Res., 64: 1 20. Gan, J.; Suksompong, W.; and Voudouris, A. A. 2019. Envyfreeness in house allocation problems. Math. Soc. Sci., 101: 104 106. G ardenfors, P. 1973. Assignment problem based on ordinal preferences. Management Science, 20: 331 340. Hazon, N.; Aumann, Y.; Kraus, S.; and Wooldridge, M. 2012. On the evaluation of election outcomes under uncertainty. Artiﬁcial Intelligence, 189: 1 18. Kamiyama, N.; Manurangsi, P.; and Suksompong, W. 2021. On the complexity of fair house allocation. Operations Research Letters, 49(4): 572 577. Manlove, D. F. 2013. Algorithmics of Matching Under Preferences. World Scientiﬁc Publishing Company. Manurangsi, P.; and Suksompong, W. 2019. When Do Envy Free Allocations Exist? In The Thirty-Third AAAI Conference on Artiﬁcial Intelligence, AAAI 2019, The Thirty First Innovative Applications of Artiﬁcial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artiﬁcial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019, 2109 2116. AAAI Press. Manurangsi, P.; and Suksompong, W. 2021. Closing Gaps in Asymptotic Fair Division. SIAM J. Discret. Math., 35(2): 668 706. Svensson, L.-G. 1994. Queue allocation of indivisible goods. Social Choice and Welfare, 11: 323 330. Svensson, L.-G. 1999. Strategy-proof allocation of indivisible goods. Social Choice and Welfare, 16(4): 557 567. Vinterbo, S. A. 2002. A note on the hardness of the kambiguity problem. Harvard Med. School, Boston, MA, USA, Tech. Rep. DSG.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)