# firstchoice_maximality_meets_exante_and_expost_fairness__2f1653a1.pdf

First-Choice Maximality Meets Ex-ante and Ex-post Fairness

Xiaoxi Guo1 , Sujoy Sikdar2 , Lirong Xia3 , Yongzhi Cao1 and Hanpin Wang4,1

1Key Laboratory of High Confidence Software Technologies (MOE), School of Computer Science, Peking University 2Department of Computer Science, Binghamton University 3Department of Computer Science, Rensselaer Polytechnic Institute 4School of Computer Science and Cyber Engineering, Guangzhou University guoxiaoxi@pku.edu.cn, ssikdar@binghamton.edu, xialirong@gmail.com, {caoyz, whpxhy}@pku.edu.cn

For the assignment problem where multiple indivisible items are allocated to a group of agents given their ordinal preferences, we design randomized mechanisms that satisfy first-choice maximality (FCM), i.e., maximizing the number of agents assigned their first choices, together with Paretoefficiency (PE). Our mechanisms also provide guarantees of ex-ante and ex-post fairness. The generalized eager Boston mechanism is ex-ante envy-free, and ex-post envy-free up to one item (EF1). The generalized probabilistic Boston mechanism is also ex-post EF1, and satisfies ex-ante efficiency instead of fairness. We also show that no strategyproof mechanism satisfies ex-post PE, EF1, and FCM simultaneously. In doing so, we expand the frontiers of simultaneously providing efficiency and both ex-ante and ex-post fairness guarantees for the assignment problem.

1 Introduction

How should m indivisible items be assigned to n agents efficiently and fairly when the agents have heterogeneous preferences over the items? This assignment problem is fundamental to economics, and increasingly, computer science, due to its versatility in modeling a wide variety of real-world problems such as assigning computing resources in cloud computing [Ghodsi et al., 2011; Grandl et al., 2014], courses to students in colleges [Budish, 2011], papers to referees [Garg et al., 2010], and medical resources in healthcare [Kirkpatrick et al., 2020; Pathak et al., 2021; Aziz and Brandl, 2021] where agents may obtain multiple items. In these problems, efficiency and fairness are the common desiderata, and also the goal of mechanism design. Efficiency reflects the degree of agents satisfaction and the room of improvement for the given assignment. The number of agents who are allocated their first choices or one of their top k choices is often highlighted as a measure of efficiency in practice [Chen and S onmez, 2006; Li, 2020; Irving et al., 2006]. First-choice maximality (FCM), i.e., maximizing the number of agents allocated their first choices [Dur et al., 2018], is considered to be either highly desirable or

indispensable in problems like job markets [Kawase et al., 2020], refugee reallocation [Sayedahmed and others, 2022], and school choice [Friedman, 1955; Friedman, 1962]. In addition, Pareto efficiency (PE) is often considered a basic efficiency property, which requires that the items cannot be redistributed in a manner strictly preferred by some agents and no worse for every other agent. In other words, it urges that all the improvements without undermining agents benefits should be made. Guaranteeing the fairness of assignments is also an important consideration, and envy-freeness (EF) [Gamow and Stern, 1958; Foley, 1966], which requires that no agent prefers the allocation of another agent to her own, is an exemplar of fairness requirements. However, an envy-free assignment may not exist for indivisible items, for example, when agents have identical preferences. Exact envy-freeness can only be guaranteed by randomization over assignments. This allows an ex-ante guarantee that every agent values its expected allocation, interpreted as probabilistic shares of items, at least as much as that of any other agent when using the notion of stochastic dominance (sd) [Bogomolnaia and Moulin, 2001] as the method of comparison. Such a random assignment describes a probability distribution over all the assignments. Envy-freeness can also be achieved approximately ex-post. Envy-freeness up to one item (EF1), which guarantees that any pairwise envy among agents is eliminated by removing one item from the envied agent s allocation [Budish, 2011], is popular among such approximations for its compatibility with efficiency [Caragiannis et al., 2019]. The Boston mechanism (BM) is widely used in the special case of the assignment problem where each agent is required to be matched with at most one item. The output of BM satisfies both FCM and PE [Abdulkadiro glu and S onmez, 2003; Kojima and Unver, 2014]. Although BM does not provide an ex-ante guarantee of envy-freeness, a variant of BM named the eager Boston mechanism provided in our previous work [Guo et al., 2023] guarantees sd-weak-envy-freeness (sd-WEF), a mildly weaker notion of ex-ante envy-freeness, while retaining FCM and PE. However, since each agent is matched with only one item, concerns over ex-post approximations of envy-freeness such as EF1 do not arise. For the general case of the assignment problem where agents may be assigned more than one item, recent work aims

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)

Efficiency Fairness Strategyproofness ex-post ex-ante ex-post ex-ante FCM PE sd-E EF1 sd-WEF sd-EF sd-WSP RSDQ Na Yb Nc NP 2 Yb Nc Yb PS-Lottery Na Yd Yd Yd Yd Yd Ne

GEBM YT 1 YT 1 Na YT 1 YT 1 Na NP 1

GPBM YT 2 YT 2 YT 2 YT 2 NR3 NR3 NP 1

Table 1: Comparison of the properties guaranteed by RSDQ, PS-Lottery, GPBM and GEBM. A Y indicates that the mechanism at that row satisfies the property at that column, and an N indicates that it does not. Results annotated with a follow from [Guo et al., 2023], b from [Hosseini and Larson, 2019], c from [Bogomolnaia and Moulin, 2001], d from [Aziz, 2020], and e from [Kojima, 2009] respectively. A result annotated with T, P, R refers to a Theorem, Proposition, or Remark in this paper, respectively (Proposition 2 is presented in the full version).

to achieve the best of both worlds (Bo BW), i.e., both exante and ex-post fairness. Freeman et al. [2020] showed that a form of ex-ante envy-freeness, sd-envy-freeness (sd-EF), and ex-post EF1 can be achieved simultaneously. Aziz [2020] showed that these fairness guarantees can also be achieved together with sd-efficiency (sd-E), an ex-ante variant of PE. However, the mechanisms developed in these works do not guarantee FCM. The pursuits for efficiency and simultaneous ex-ante and ex-post fairness outlined above inevitably raise the following natural open question that we investigate in this paper: How to design mechanisms that allocate m items to n agents and guarantee both efficiency (FCM and PE) and fairness (envyfreeness), both ex-ante and ex-post?

Our contributions. We provide two novel randomized mechanisms, the generalized eager Boston mechanism (GEBM) and the generalized probabilistic Boston mechanism (GPBM), both of which satisfy ex-post FCM and PE together with different combinations of desirable efficiency and fairness properties as we summarize in Table 1. In particular:

GEBM provides both ex-post and ex-ante fairness guarantees, satisfying satisfies sd-WEF and ex-post EF1 (Theorem 1).

GPBM also satisfies ex-post EF1, and provides a stronger ex-ante efficiency guarantee (sd-E) instead of ex-ante fairness (Theorem 2).

We provide the full version of the paper for more details1.

1.1 Related Work and Discussions The assignment problem is a generalization of the matching problem with one-sided preferences [Moulin, 2004; Manlove, 2013], where each agent must be assigned at most one item given agents preferences over the items. In matching problems, BM [Abdulkadiro glu and S onmez, 2003] and EBM [Guo et al., 2023] proceed in multiple rounds as follows. In each round r of BM, each agent that has not been allocated an item yet applies to receive its r-th ranked item. Each item, if it has applicants, is allocated to the one with the highest priority. Randomization over priority orders yields a mechanism whose expected output is a random assignment.

1https://arxiv.org/abs/2305.04589

In the round of EBM, each remaining agent applies for its most preferred remaining item, and each item is allocated to one of the applicants through a lottery. This subtle change results in the ex-ante fairness guarantee of EBM. The trade-off of efficiency and fairness in the assignment problem has been a long-standing topic, and guaranteeing FCM with other properties has been the focus of several recent research efforts. Notice that both BM and EBM guarantee FCM since every item ranked on top by some agent is allocated to one such agent in the first round during the execution of both mechanisms. For the matching problems, Ramezanian and Feizi [2021] showed that the efficiency notion favoring-higher-ranks (FHR), which characterizes BM and implies FCM. Our previous work showed that FHR is not compatible with sd-WEF, and provided favoring-eagernessfor-remaining-items as an alternative that also implies FCM [Guo et al., 2023]. For the general case of the assignment problem, Hosseini et al. [2021] showed an assignment that satisfies both rank-maximality (a stronger efficiency property that also implies FCM [Irving et al., 2006]) and envy-free up to any item (a stronger approximation of envy-freeness that implies EF1 [Caragiannis et al., 2019]) does not always exist. Designing randomized mechanisms that provide ex-ante guarantees of efficiency and fairness has been a long standing concern in the literature. Bogomolnaia and Moulin [2001] proposed the probabilistic serial (PS) mechanism that satisfies sd-E and sd-EF for the matching problem. Similar efforts have been made for housing markets [Athanassoglou and Sethuraman, 2011; Altuntas and Phan, 2022; Yılmaz, 2010] and assignment problems with quotas [Budish et al., 2013; Kojima, 2009]. The ex-post approximation of envy-freeness also raised concern in the previous work. However, the endeavors to provide both ex-ante and ex-post guarantees of fairness simultaneously are more recent [Babaioff et al., 2022; Freeman et al., 2020; Aziz, 2020; Hoefer et al., 2022]. Table 1 compares our GEBM and GPBM with existing mechanisms. The random serial dictatorship quota mechanism (RSDQ) [Hosseini and Larson, 2019] satisfies strategyproofness, meaning no agent can benefit by misreporting its preferences, but does not provide either ex-ante efficiency or ex-post fairness guarantees. Aziz [2020] proposed the PSLottery mechanism as an extension of PS which provides strong ex-ante efficiency and fairness guarantees. However,

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)

neither RSDQ nor PS-Lottery takes the ranks of items into consideration, and therefore they do not satisfy FCM.

2 Preliminaries

An instance of the assignment problem is given by a tuple (N, M), where N = {1, 2, . . . , n} is a set of n agents and M = {o1, o2, . . . , om} is a set of m distinct indivisible items; and a preference profile R = ( j)j N, where for each agent j N, j is a strict linear order representing j s preferences over M. Let R be the set of all possible preference profiles. For each agent j N and for any set of items S M, we define rk( j, o, S) {1, . . . , |S|} to denote the rank of item o S among the items in S M according to j, and top( j, S) S to denote the item ranked highest in S. When S = M, we use rk( j, o) for short; and when agent j s preference relation is clear from context, we use rk(j, o, S) and top(j, S) instead. We use j to denote the collection of preferences of agents in N \ {j}. For any linear order over M and item o, U( , o) = {o M|o o} {o} represents the items weakly preferred to o.

Allocations, assignments, and mechanisms. The subset of items that an agent receives, which we call an allocation, is a binary m-vector a = [a(o)]o M. The value a(o) = 1 indicates that item o is in the subset represented by a, and we also use o a for that. A random allocation is a m-vector p = [p(o)]o M with 0 p(o) 1, describing the probabilistic share of each item. Let Π be the set of all possible random allocations, and any allocation belongs to Π trivially. An assignment A : N 2M is a mapping from agents to allocations, represented by an n m matrix. For each agent j N, we use A(j) to denote the allocation for j. Let A denote the set of all the assignments. A random assignment is an n m matrix P = [P(j, o)]j N,o M. For each agent j N, the j-th row of P, denoted P(j), is agent j s random allocation, and for each item o M, P(j, o) is j s probabilistic share of o. We use P to denote the set of all possible random assignments, and we note that A P, i.e., an assignment can be regarded as a random assignment. A mechanism f : R P is a mapping from preference profiles to random assignments. For any profile R R, we use f(R) to refer to the random assignment output by f.

2.1 Desirable Properties Before giving the specific definitions of desirable properties, we introduce two methods for random allocation comparison.

Definition 1. [Bogomolnaia and Moulin, 2001] Given a preference relation over M, the stochastic dominance relation associated with , denoted by sd, is a partial ordering over Π such that for any pair of random allocations p, q Π, p (weakly) stochastically dominates q, denoted by p sd q, if for any o M, P o U( ,o) p(o ) P o U( ,o) q(o ).

Definition 2. Given a preference relation over M, the lexicographic dominance relation associated with , denoted by lexi, is a strict linear ordering over Π such that for any pair of random allocations p, q Π, p lexicographically dominates q, denoted by p lexi q, if there exists an item o such that p(o) > q(o) and p(o ) = q(o ) for any o o.

Given a preference profile R, an assignment A satisfies: (i) Pareto-efficiency (PE) if there does not exist another A such that A (j) lexi A(j) for j N = and A (k) = A(k) for k N \ N , (ii) envy-free up to one item (EF1) if for any agents j and k, there exists an item o such that A(j) sd j A(k) \ {o}, and (iii) first-choice maximality (FCM) if there does not exist another A such that |{j N | rk(j, o) = 1 and o A (j)}| > |{j N | rk(j, o) = 1 and o A(j)}|. In general, given a property X for assignments, a random assignment satisfies ex-post X if it is a convex combination of assignments satisfying property X, and a mechanism f satisfies a property Y if f(R) satisfies Y for every profile R R. Given a preference profile R, a random assignment P satisfies: (i) sd-efficiency (sd-E) if there is no random assignment Q = P such that Q(j) sd j P(j) for any j N, and

(ii) sd-weak-envy-freeness (sd-WEF) if P(k) sd j P(j) = P(j) = P(k). A mechanism f satisfies: (i) sd-weak-strategyproofness (sd-WSP) if for every R R, any j N, and any R = ( j, j), it holds that f(R )(j) sd j f(R)(j) = f(R )(j) = f(R)(j), (ii) neutrality if given any permutation π over the items, f(π(R)) = π(f(R)) for any preference profile R. The permutation π is given as {(o1, o2), (o2, o3), . . . }, and π(R) (respectively, π(f(R))) is obtained by replacing oi with oj in R (respectively, f(R)) for each ordered pair (oi, oj) π.

Lemma 1. [Folklore] An assignment A satisfies Paretoefficiency if and only if the relation {(o, o ) M M | there exists j N with o j o and o A(j)} is acyclic.

Lemma 2. [Bogomolnaia and Moulin, 2001] A random assignment P satisfies sd-efficiency if and only if the relation {(o, o ) M M | there exists an agent j N where o j o and P(j, o) > 0} is acyclic.

Due to Lemmas 1 and 2, sd-E implies ex-post PE for the assignment problem.

Remark 1 (ex-post FCM ex-ante FCM). A random assignment P is ex-post FCM if and only if it is ex-ante FCM, i.e., the probabilistic shares of each item o that is ranked first by some agent are allocated only to those agents who rank it first among all items. This is because in any assignment A drawn from the probability distribution represented by P, each o is assigned to one of the agents who rank it first if such an agent exists.

2.2 The Special Case of Matching The matching problem is a useful and important special case of the assignment problem where each agent must be matched with at most one item. To distinguish from the allocation in general cases, we call the assignment A in the matching problem as a (one-to-one) matching where each agent j s allocation A(j) either consists of a single item or is the empty set. We introduce two efficiency notions that imply FCM and PE. Favoring-higher-ranks (FHR) requires that each item is allocated to an agent that ranks it as high as possible among

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)

all the items [Ramezanian and Feizi, 2021], while favoringeagerness-for-remaining-items (FERI) requires that each remaining item is allocated to a remaining agent who prefers it to any other remaining items if such an agent exists [Guo et al., 2023]. Formally, given a preference profile R, a matching A satisfies (i) favoring-higher-ranks (FHR) if for any agents j, k N, rk(j, A(j)) rk(k, A(j)) or rk(k, A(k)) < rk(k, A(j)), and (ii) favoring-eagerness-for-remaining-items (FERI) if it holds that o = top(A 1(o), M \ S r <r TA,r ) for every item o TA,r with integer r 1, where we define TA,r = {o M | o = top(j, M \ S r <r TA,r ), A(j) / S r <r TA,r }.

3 Generalized Eager Boston Mechanism To achieve FCM accompanied with the ex-ante and expost fairness in the assignment problem, we propose the generalized eager Boston mechanism mechanism (GEBM) which is an extension of EBM. We show in Theorem 1 that GEBM satisfies the efficiency requirements of PE and FCM ex-post while also providing fairness guarantees both ex-ante (sd-WEF) and ex-post (EF1). For any preference profile R of n agents preferences over m items, GEBM (Algorithm 1) proceeds in m/n rounds. At each round c, a matching is computed on the instance of the matching problem involving all n agents and the remaining items using the EBM mechanism. The final output A of GEBM(N, M, R) is the composition of these matchings. For convenience, at each round c of GEBM, we use - M c to refer to the items remaining at the beginning, and - Ac = EBM(N, M c, R) to refer to the matching output by EBM for the instance (N, M c) of the matching problem. We note that in the notation EBM(N, M c, R), the preferences in R are over M, so we have to specify the item set to be allocated M c. The final output of GEBM is A = P m/n c=1 Ac.

Algorithm 1 Generalized Eager Boston Mechanism (GEBM)

1: Input: An assignment problem (N, M) and a strict linear preference profile R. 2: A 0n m. c 1. 3: for c = 1 to m/n do // Round c of GEBM 4: M c {o M | Ac (j, o) = 0 for all j N, c < c}. // Compute Ac = EBM(N, M c) 5: N N, Ac 0n m. 6: while N = and M c = do // Round of EBM 7: for each o M c do 8: No {j N | rk(j, o) = top(j, N )}. 9: Pick jo from No = uniformly at random. 10: Ac(jo, o) 1. 11: M c M c \ {o M c | No = }. 12: N N \ o M c{jo}. 13: A A + Ac. 14: return A

Example 1. We illustrate the execution of GEBM (Algorithm 1) using an instance with four items and two agents

with preferences:

1 : a 1 b 1 c 1 d, 2 : a 2 c 2 b 2 d.

The table below illustrates the execution of Algorithm 1. Each entry in the table refers to the item the row agent applied for in a round of execution of EBM within a round of GEBM indicated by the column. Circled entries indicate allocations, and a / entry indicates the agent was allocated an item in a previous round of EBM and does not apply for any item.

Round of GEBM 1 2 Round of EBM 1 2 1 2 Agent 1 a / b / Agent 2 a c b d

Table 2: An example of the execution of GEBM.

At Round 1 of GEBM(N, M, R), the EBM mechanism is executed on the matching instance (N = {1, 2}, M 1 = {a, b, c, d}) involving all items and both agents and outputs the assignment A1 : 1 (a), 2 (c) as follows. - At round 1 of EBM(N, M 1, R), both agents 1 and 2 apply for their top-ranked item a among items in M 1 and are in the applicant set Na. Suppose that agent 1 is chosen to receive a and therefore removed from the current round of GEBM. - At round 2 of EBM(N, M 1, R), agent 2 applies for her top item c among the remaining items {b, c, d} and gets it. At Round 2 of GEBM(N, M, R), EBM is executed on the matching instance (N = {1, 2}, M 2 = {b, d}) and outputs A2 : 1 (b), 2 (d). - At round 1 of EBM(N, M 2, R), agents 1 and 2 both prefer b over d and apply for b. Now suppose agent 1 gets b. - At round 2 of EBM(N, M 2, R), agent 2 applies for and is allocated the only remaining item d. Together the execution above outputs the assignment A : 1 (a, b), 2 (c, d). Notice that each of the matchings Ac = EBM(N, M c, R) satisfy FERI according to Theorem 1 in our previous work [Guo et al., 2023]. The first-choice maximality of A follows due to the matching A1. Corollary 1. Given any preference profile R and assignment GEBM(R) = P m/n c=1 Ac, for each c {1, . . . , m/n }, Ac satisfies FERI for the matching problem (N, M c). Lemma 3 shows that given a round of GEBM , every agent prefers the item they are allocated in that round to all the items allocated in any subsequent round. EF1 follows from this construction. Lemma 3. Given any preference profile R and assignment GEBM(R) = P m/n c=1 Ac, for any pair of agents j, k and integer c {1, . . . , m/n 1}, Ac(j) j Ac+1(k). With Corollary 1 and Lemma 3, we present the following theorem to show the properties of GEBM. Theorem 1. The generalized eager Boston mechanism satisfies ex-post PE, ex-post EF1, ex-post FCM, and sd-WEF.

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)

Proof. Given any preference profile R, let A = GEBM(R). (PE) We prove by mathematical induction that for any c {1, . . . , m/n }, assignment P c c Ac satisfies PE. Base case: For c = 1, A1 satisfies FERI by Corollary 1. Since FERI implies PE (Proposition 2 of Guo et al. [2023]), we have that A1 trivially satisfies PE. Inductive step: For any c > 1, given that A = P c <c Ac

satisfies PE, we prove that A = P c c Ac also satisfies PE. Suppose for the sake of contradiction that there exists a cycle in A by Lemma 1. By the given condition and Corollary 1, we know that A and Ac satisfies PE and therefore there is no cycle in any one of them, which means that the cycle in A must involve both A and Ac. Therefore there must exist a pair of items o = Ac (j) and o = A(k)c such that o j o for some agents j, k and c < c, which contradicts Lemma 3 which implies that Ac (j) j Ac(k). (EF1) By Lemma 3, Ac(j) j Ac+1(k) for any agents j and k. In this way, A(j) sd j A(k) \ {A1(k)}. (FCM) By Corollary 1, we know A1 satisfies FERI for the assignment problem (N, M, R). For any item o M, o is ranked top by some agent if and only if o TA1,1. Then for any such item o and for agent j with A(j) = o, we have o = top(j, M) by the definition of FERI, which implies A satisfies FCM. (sd-WEF) Let P = E(GEBM(R)). Recall that Ac is defined to be the outcome of EBM(N, M c) in round c in the execution of GEBM. Let A<c be the set of all the possible intermediate outcomes of first c 1 rounds of GEBM. For each A<c A<c, let α(A<c) be the probability that A<c is output after the first c 1 rounds. We define α(Ac | A<c) to be the probability that EBM(N, M c) = Ac is the matching output by EBM in round c of GEBM given A<c as the intermediate outcome of the first c 1 rounds of GEBM. Let Ac |A<c be the set of all possible matchings given the instance (N, M c). Let P c be the expected assignment computed at the end of round c of GEBM. Then, we have P = P m/n c=1 P c and:

Ac Ac |A<c α(Ac) α(Ac|A<c) Ac. (1)

We show that for each c {1, . . . , m/n }, it holds for any pair of agents j, k N that if P c(j) = P c(k) then P c(j) lexi j P c(k). By Eq (1), in an arbitrary round c of GEBM, for any assignment A<c computed in the first c 1 rounds of GEBM, let Qc |A<c = P Ac Ac |A<c α(Ac | A<c) Ac denote the expected

output of EBM(N, M c) given A<c, where M c = {o M | P j N A<c(j, o) = 0}. We first show that:

Qc |A<c(j) lexi j Qc |A<c(k) if Qc |A<c(j) = Qc |A<c(k). (2)

At any round r of EBM within round c of GEBM, let o be the item that agent j applies for. There are two cases according to the item agent k applies for: (Case 1) Suppose agent k applies for the same item as j. Then they have the same probability to get item o, i.e. Qc |A<c(j, o) = Qc |A<c(k, o) according to

line 9 of Algorithm 1. (Case 2) Suppose agent k applies for a different item o . Then o j o and agent k has no chance of receiving item o, since item o must be allocated to one of the agents that applied for o in round r of EBM, and it follows that Qc |A<c(j, o) > Qc |A<c(k, o) = 0. Together, both cases leads to Eq (2). By Eq (1), we have that P c = P A<c A<c α(A<c) Qc |A<c. Together with Claim 1 below, we have by Eq (2) that P c(j) lexi j P c(k) if P c(j) = P c(k).

Claim 1. Given random allocations p1, . . . , ps and q1, . . . , qs with pi lexi qi or pi = qi for any integer i [1, s]. If Ps i=1 pi = Ps i=1 qi, then Ps i=1 pi lexi Ps i=1 qi .

By P = P m/n c=1 P c and Claim 1, we have that P(j) lexi j P(k) when P(j) = P(k). It follows that if P(k) sd j P(j), then P(j) lexi j P(k) does not hold and therefore P(j) = P(k), which means that P satisfies sd-WEF.

Remark 2. GEBM does not satisfy sd-E and sd-EF. For the matching problem, GEBM executes lines 3-13 once and therefore it is equivalent to EBM. According to Proposition 15 of Guo et al. [2023], EBM does not satisfy sd-E and sd-EF, and therefore neither does GEBM.

4 Generalized Probabilistic Boston Mechanism

In this section, we propose generalized probabilistic Boston mechanism (GPBM) mechanism. GPBM also satisfies FCM and EF1 ex-post, and additionally provides an ex-ante efficiency guarantee of sd-E as we show in Theorem 2 later, but it does not provide an ex-ante fairness guarantee (Remark 3). In comparison, GEBM satisfies sd-WEF but not sd-E. GPBM, defined in Algorithm 2, proceeds by assigning the m distinct indivisible items in m/n rounds. Each item o initially has s(o) = 1 unit of supply to be consumed. In each round c (lines 3-10 of Algorithm 2), each agent is allowed to consume, i.e., be allocated, at most one unit of items cumulatively over multiple consumption rounds as follows. In each consumption round r (lines 5-10), for each item o, all of the agents who rank item o in position r over all items, represented by the set No in line 7, consume item o at an equal rate. An agent j No quits consuming o when either the supply of item o is exhausted, or j has cumulatively consumed one unit of items in round c of GPBM. GPBM terminates when all the items are consumed to exhaustion of their supply and returns the probability shares of items that agents consume during execution. We use P c to refer to the random assignment computed at the end of each round c {1, . . . , m/n } of GPBM.

Example 2. We use the instance in Example 1 to illustrate the execution of GPBM in Figure 1. For Round 1 of GPBM, P 1 is generated as follows. - At consumption round 1, agents 1 and 2 both consume item a at an equal rate, and therefore P 1(1, a) = P 1(2, a) = 1/2.

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)

Algorithm 2 Generalized Probabilistic Boston Mechanism (GPBM)

1: Input: An assignment problem (N, M) and a strict linear preference profile R. 2: For each o M, s(o) 1. M M. c 0. 3: while M = do // Round c of GPBM 4: c c + 1. P c 0n m. N N. r 1. 5: while M = and N = do // Consumption round r 6: for each o M do 7: No {j N | rk(j, o) = r}. 8: Each agent j No consumes o at an equal rate. Let δj be the amount of item o consumed by j. 8.1: Agent j stops consumption when either - P o U(j,o) P c(j, o ) + δj = 1, or - S k No δk = s(o).

8.2: P c(j, o) δj, and s(o) s(o) S k No δk.

9: M M \{o M | s(o) = 0}. N N \{j N | P o U(j,o) P c(j, o ) = 1}.

10: r r + 1.

11: return m/n P

- At consumption round 2, agent 1 consumes item b while agent 2 consumes c, which results in P 1(1, b) = P 1(2, c) = 1/2. Notice that b and c are not exhausted, but consumption stops since agents 1 and 2 have each cumulatively consumed one unit. For Round 2 of GPBM, we omit the consumption rounds that do not allocate any items in generating P 2. - At consumption round 2, agent 1 consumes item b while agent 2 consumes c, which results in P 2(1, b) = P 2(2, c) = 1/2. - At consumption round 4, agents 1 and 2 both consume item d and split it equally, i.e., P 2(1, d) = P 2(2, d) = 1/2. Then we obtain P 1 and P 2 in the following: Assignment P 1

a b c d 1 1/2 1/2 0 0 2 1/2 0 1/2 0

Assignment P 2 a b c d 1 0 1/2 0 1/2 2 0 0 1/2 1/2

We show in Lemma 4 that the random assignment P c obtained at the end of each round c of GPBM satisfies sd E, which will be instrumental in proving that the output of GPBM always satisfies sd-E in Theorem 2.

Lemma 4. Given any preference profile R, for every c {1, . . . , m/n }, the assignment P c computed at the end of round c of GPBM satisfies sd-E.

An assignment can be generated from the output P of GPBM using an algorithm suggested by Aziz [2020]. In the following discussion, we use Algorithm 3 to refer to it. The algorithm proceeds by first creating for each agent j the subagents j1, . . . , j m/n who have the random allocations P 1(j), . . . , P m/n (j) respectively. The n m/n subagents thus created then participate in a lottery, and each agent is allocated the items won by all of its subagents, e.g.,

Figure 1: An example of the execution of GPBM.

the assignment A in Example 1 is a possible result drawn from {P 1, P 2}. Since P o M P c(j, o) 1, each subagent does not obtain more than one item. For any A drawn from P, we define for c = 1, . . . , m/n that - Ac to refer to the one-to-one matching over all the subagents jc in A, and

- M c = {o M | o = Ac (j) for some c < c and j N} to be the set of items that are not allocated in the matching Ac with any c < c. In the following Lemma 5, we prove that each Ac satisfies FHR and that each agent prefers the items with positive shares in her allocation in the current round to any item to be allocated in later rounds.

Lemma 5. Given any preference profile R and {A1, . . . , A m/n } drawn from GPBM(R) = P m/n c=1 P c by Algorithm 3, (i) Ac satisfies FHR for the assignment problem (N, M c) for c = 1, . . . , m/n ; (ii) Ac(j) j Ac+1(k) for c = 1, . . . , m/n 1.

Theorem 2. The generalized probabilistic Boston mechanism satisfies ex-post FCM, ex-post EF1, and sd-E.

Proof. Let A be an assignment drawn from the distribution represented by {P 1, . . . , P m/n }. (FCM) Assume that A does not satisfy FCM. Then there exists an item o such that a set of agents N N prefer o most, but o is allocated to an agent k N , i.e., o A(k). Consider any agent j N and let o = A1(j) and o = Ac(k) for some c. Since o j o , it must hold that c = rk(k, o, A(k)) = 1. Otherwise, if c > 1, then it means that o = Ac(k) j A1(k), a contradiction to Lemma 5 (ii). However, we have that rk(k, o) > 1 = rk(j, o) by the selection of j and k, which contradicts the fact that A1 satisfies FHR by Lemma 5 (i). (EF1) By Lemma 5 (ii), Ac(j) j Ac+1(k) for any agents j and k. It follows that A(j) sd j A(k) \ {A1(k)}. (sd-E) Let P = E(GPBM(R)) = P c m/n P c. We prove by mathematical induction that for any c

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)

{1, . . . , m/n }, it holds that P c = P c c P c satisfies sd E. Base case: For c = 1, P c = P 1 and therefore it satisfies sd-E trivially by Lemma 4. Inductive step: Suppose that P c = P c c P c satisfies sd-E. Now, assume for the sake of contradiction that for P c+1, there exists a cycle in the relation in Lemma 2. Notice that by Lemma 4, P c+1 satisfies sd-E. Together with the assumption that P c satisfies sd-E, this means the cycle must involve items with positive shares in both P c and P c+1, i.e., there exist items o, o and a pair of agents j, k involved in the cycle such that:

o k o , P (k, o ) > 0, and P c+1(j, o) > 0. (3)

By Eq (3), it must hold that in round c + 1 of GPBM when P c+1 is generated, agent j consumes the item o that agent k prefers to the item o . We also note that agent k consumes o in a strictly earlier round c c of GPBM. By line 9 of Algorithm 2, this implies that s(o) > 0 at the beginning of round c of GPBM. Then, by lines 7 and 8, for any item o

consumed by agent k, i.e., where P c (k, o ) > 0, we have that either o k o or o = o, a contradiction to Eq (3). Thus by induction, P = P c m/n P c satisfies sd-E.

Remark 3. GPBM does not satisfy sd-WEF. For the assignment problem with the following profile R, GPBM outputs assignment P.

1,2 : a b c d, 3 : a 3 d 3 b 3 c, 4 : d 4 a 4 b 4 c.

Assignment P

a b c d 1,2 1/3 1/2 1/6 0 3 1/3 0 2/3 0 4 0 0 0 1

We see that P o 3o P(1, o ) = P o 3o P(3, o ) for o {a, c, d} and P o 3b P(1, o ) = 5/6 > 1/3 = P o 3b P(3, o ). It follows that P(1) = P(3) and P(1) sd 3 P(3), which violates sd-WEF.

5 An Impossibility Result

In Proposition 1, we show that for the mechanisms that satisfy FCM, PE, and EF1 ex-post, they are impossible to guarantee strategyproofness (sd-WSP) without violating neutrality, which requires that any permutation of the item labels results in an assignment where the items allocated to each agent are permuted in the same manner. Therefore, GEBM and GPBM trivially satisfy neutrality, and therefore they cannot provide guarantee of strategyproofness.

Proposition 1. There is no sd-WSP mechanism which simultaneously satisfies FCM, PE, EF1, and neutrality ex-post.

Proof. Suppose that f is an sd-WSP mechanism that satisfies FCM, PE, EF1, and neutrality ex-post. Let R be:

1 : a 1 b 1 c 1 d, 2 : d 2 a 2 b 2 c.

In any assignment satisfying PE, agent 1 cannot obtain item d. We note EF1 requires that an agent can obtain one

more item than any other at most. Then with this condition, the PE assignments for R are: A1 : 1 {a, b}, 2 {c, d}, A2 : 1 {a, c}, 2 {b, d}, A3 : 1 {b, c}, 2 {a, d}. We observe that A1 and A2 also satisfy FCM and EF1, and A3 satisfies EF1 here but violates FCM. Then we have that f(R) = α1 A1 + α2 A2, denoted P. Let R = ( 1, 2) be the profile obtained from R when agent 2 misreports her preferences as 2 below:

2 : a 2 b 2 d 2 c

In any assignment satisfying EF1 for R , each agent must get only one item in {a, b}. Moreover, PE requires that 1 gets c and 2 gets d. In this way, only A2 and A3 satisfy FCM, PE, and EF1 for the profile R . Then we have that f(R ) = α 2 A2 + α 3 A3, denoted P . We also observe that if α1 = 0 or α 3 = 0, then P = P and P 2 sd 2 P2 since A3 sd 2 A2 sd 2 A1. Since f satisfies sd-WSP, we must have that P 2 = P2 = A2(2) which means that α1 = α 3 = 0, and therefore P = P = A2. Let π = {(c, d), (d, c)} be a permutation on M that swaps the labels of items c and d. We observe that π(R ) can be obtained by swapping the preferences of agents 1 and 2 in R . Therefore f(π(R )) can be constructed in the same manner as the assignment above, and it can be obtained by swapping the allocations of agents 1 and 2 in P = A2. We also have that π(f(R )) = π(P ) = π(A2). Both assignments are shown below: f(π(R )) : 1 {b, d}, 2 {a, c},

π(f(R )) : 1 {a, d}, 2 {b, c}.

It is easy to see that f(π(R )) = π(f(R )), meaning that f must violate neutrality, a contradiction.

6 Conclusion and Future Work Our results contribute towards the efforts to achieve both exante and ex-post guarantees of both efficiency and fairness in the assignment of indivisible items. We have provided the first mechanisms that satisfy ex-post FCM, PE, and EF1 simultaneously. In terms of the ex-ante guarantee, our GEBM is fair, while GPBM is efficient. We have also shown that mechanisms of this kind cannot be strategyproof. We wonder whether it is possible to achieve stronger efficiency or fairness properties. Recent works on identifying domain restrictions, under which certain impossibility results no longer pose a barrier and allow for mechanisms with stronger guarantees [Hosseini et al., 2021; Wang et al., 2023], is a promising avenue for such investigations. In general, finding what combinations of properties can be satisfied simultaneously, and what constitutes the Bo BW, is an ongoing pursuit. Some works on designing mechanisms with desirable properties under constraints [Garg et al., 2010; Budish et al., 2017] that reflect real-world considerations such as agents quotas [Aziz and Brandl, 2022; Balbuzanov, 2022] and more generally, those involving matroid constraints [Dror et al., 2021; Biswas and Barman, 2018; Biswas and Barman, 2019] are another interesting direction for future research.

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)

Acknowledgments

XG acknowledges the National Key R&D Program of China under Grant 2021YFF1201102 for support. LX acknowledges NSF #1453542, #2007994, #2106983, and a Google Research Award for support. YC acknowledges NSFC under Grants 62172016 and 61932001 for support. HW acknowledges NSFC under Grant 61972005 for support.

References [Abdulkadiro glu and S onmez, 2003] Atila Abdulkadiro glu and Tayfun S onmez. School choice: A mechanism design approach. American Economic Review, 93(3):729 747, 2003. [Altuntas and Phan, 2022] Ac elya Altuntas and William Phan. Trading probabilities along cycles. Journal of Mathematical Economics, 100:102631, 2022. [Athanassoglou and Sethuraman, 2011] Stergios Athanassoglou and Jay Sethuraman. House allocation with fractional endowments. International Journal of Game Theory, 40(3):481 513, 2011. [Aziz and Brandl, 2021] Haris Aziz and Florian Brandl. Efficient, fair, and incentive-compatible healthcare rationing. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 103 104, 2021. [Aziz and Brandl, 2022] Haris Aziz and Florian Brandl. The vigilant eating rule: A general approach for probabilistic economic design with constraints. Games and Economic Behavior, 135:168 187, 2022. [Aziz, 2020] Haris Aziz. Simultaneously achieving ex-ante and ex-post fairness. In International Conference on Web and Internet Economics, pages 341 355. Springer, 2020. [Babaioff et al., 2022] Moshe Babaioff, Tomer Ezra, and Uriel Feige. On best-of-both-worlds fair-share allocations. In International Conference on Web and Internet Economics, pages 237 255. Springer, 2022. [Balbuzanov, 2022] Ivan Balbuzanov. Constrained random matching. Journal of Economic Theory, page 105472, 2022. [Biswas and Barman, 2018] Arpita Biswas and Siddharth Barman. Fair division under cardinality constraints. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, page 91 97. AAAI Press, 2018. [Biswas and Barman, 2019] Arpita Biswas and Siddharth Barman. Matroid constrained fair allocation problem. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 9921 9922, 2019. [Bogomolnaia and Moulin, 2001] Anna Bogomolnaia and Herv e Moulin. A new solution to the random assignment problem. Journal of Economic Theory, 100(2):295 328, 2001. [Budish et al., 2013] Eric Budish, Yeon-Koo Che, Fuhito Kojima, and Paul Milgrom. Designing random allocation mechanisms: Theory and applications. American Economic Review, 103(2):585 623, 2013.

[Budish et al., 2017] Eric Budish, G erard P Cachon, Judd B Kessler, and Abraham Othman. Course match: A largescale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation. Operations Research, 65(2):314 336, 2017. [Budish, 2011] Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061 1103, 2011. [Caragiannis et al., 2019] Ioannis Caragiannis, David Kurokawa, Herv e Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation, 7(3):1 32, 2019. [Chen and S onmez, 2006] Yan Chen and Tayfun S onmez. School choice: An experimental study. Journal of Economic Theory, 127(1):202 231, 2006. [Dror et al., 2021] Amitay Dror, Michal Feldman, and Erel Segal-Halevi. On fair division under heterogeneous matroid constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 5312 5320, 2021. [Dur et al., 2018] Umut Dur, Timo Mennle, and Sven Seuken. First-choice maximal and first-choice stable school choice mechanisms. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 251 268, 2018. [Foley, 1966] Duncan Karl Foley. Resource Allocation and the Public Sector. Ph D thesis, Yale University, 1966. [Freeman et al., 2020] Rupert Freeman, Nisarg Shah, and Rohit Vaish. Best of both worlds: Ex-ante and ex-post fairness in resource allocation. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 21 22, 2020. [Friedman, 1955] Milton Friedman. The role of government in education. In Economics and the Public Interest. Rutgers University Press, 1955. [Friedman, 1962] Milton Friedman. Capitalism and freedom. Ethics, 74(1), 1962. [Gamow and Stern, 1958] George Gamow and Marvin Stern. Puzzle-Math. Viking Press, 1958. [Garg et al., 2010] Naveen Garg, Telikepalli Kavitha, Amit Kumar, Kurt Mehlhorn, and Juli an Mestre. Assigning papers to referees. Algorithmica, 58(1):119 136, 2010. [Ghodsi et al., 2011] Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker, and Ion Stoica. Dominant resource fairness: Fair allocation of multiple resource types. In Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation, pages 323 336, 2011. [Grandl et al., 2014] Robert Grandl, Ganesh Ananthanarayanan, Srikanth Kandula, Sriram Rao, and Aditya Akella. Multi-resource packing for cluster schedulers. In Proceedings of the 2014 ACM Conference on SIGCOMM, pages 455 466, 2014.

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)

[Guo et al., 2023] Xiaoxi Guo, Sujoy Sikdar, Lirong Xia, Yongzhi Cao, and Hanpin Wang. Favoring eagerness for remaining items: Designing efficient, fair, and strategyproof mechanisms. Journal of Artificial Intelligence Research, 76:287 339, 2023. [Hoefer et al., 2022] Martin Hoefer, Marco Schmalhofer, and Giovanna Varricchio. Best of both worlds: Agents with entitlements. ar Xiv preprint ar Xiv:2209.03908, 2022. [Hosseini and Larson, 2019] Hadi Hosseini and Kate Larson. Multiple assignment problems under lexicographic preferences. In Proceedings of the 18th International Conference on Autonomous Agents and Multi Agent Systems, pages 837 845, 2019. [Hosseini et al., 2021] Hadi Hosseini, Sujoy Sikdar, Rohit Vaish, and Lirong Xia. Fair and efficient allocations under lexicographic preferences. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 5472 5480, 2021. [Irving et al., 2006] Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, and Katarzyna E. Paluch. Rank-maximal matchings. ACM Transactions on Algorithms, 2(4):602 610, 2006. [Kawase et al., 2020] Yasushi Kawase, Yutaro Yamaguchi, and Yu Yokoi. Subgame perfect equilibria of sequential matching games. ACM Transactions on Economics and Computation, 7(4):1 30, 2020. [Kirkpatrick et al., 2020] James N Kirkpatrick, Sarah C Hull, Savitri Fedson, Brendan Mullen, and Sarah J Goodlin. Scarce-resource allocation and patient triage during the COVID-19 pandemic. Journal of the American College of Cardiology, 76(1):85 92, 2020. [Kojima and Unver, 2014] Fuhito Kojima and M. Utku Unver. The Boston school-choice mechanism: an axiomatic approach. Economic Theory, 55(3):515 544, 2014. [Kojima, 2009] Fuhito Kojima. Random assignment of multiple indivisible objects. Mathematical Social Sciences, 57(1):134 142, 2009. [Li, 2020] Mengling Li. Ties matter: Improving efficiency in course allocation by allowing ties. Journal of Economic Behavior & Organization, 178:354 384, 2020. [Manlove, 2013] David Manlove. Algorithmics of Matching under Preferences. World Scientific, 2013. [Moulin, 2004] H. Moulin. Fair Division and Collective Welfare. MIT Press, 2004. [Pathak et al., 2021] Parag A Pathak, Tayfun S onmez, M Utku Unver, and M Bumin Yenmez. Fair allocation of vaccines, ventilators and antiviral treatments: Leaving no ethical value behind in health care rationing. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 785 786, 2021. [Ramezanian and Feizi, 2021] Rasoul Ramezanian and Mehdi Feizi. Ex-post favoring ranks: A fairness notion for the random assignment problem. Review of Economic Design, 25:157 176, 2021.

[Sayedahmed and others, 2022] Dilek Sayedahmed et al. Centralized refugee matching mechanisms with hierarchical priority classes. The Journal of Mechanism and Institution Design, 7(1):71 111, 2022. [Wang et al., 2023] Haibin Wang, Sujoy Sikdar, Xiaoxi Guo, Lirong Xia, Yongzhi Cao, and Hanpin Wang. Multi resource allocation with partial preferences. Artificial Intelligence, 314:103824, 2023. [Yılmaz, 2010] Ozg ur Yılmaz. The probabilistic serial mechanism with private endowments. Games and Economic Behavior, 69(2):475 491, 2010.

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)