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

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 to achieve the "best of both worlds" (BoBW), 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 details 1 .

1.1 RelatedWork 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.

1 https://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, 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, andmechanisms. 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×mmatrix. 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 andMoulin, 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, ∑o′∈U(≻,o) p(o′ ) ≥ ∑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).

Amechanism 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 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 \ ⋃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 \ ⋃r′<r TA,r′ ), A(j) /∈ ⋃r′<r TA,r′ }.

3 Generalized Eager BostonMechanism

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 = ∑⌈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 ′ ̸= ∅ andM 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 fromNo ̸= ∅ uniformly at random.
• 10: Ac (jo, o) ← 1.
• 11: M c ←M c \ {o ∈M c | No ̸= ∅}.
• 12: N ′ ←N ′ \ ∪o∈Mc{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:

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.

• 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) = ∑⌈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) = ∑⌈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.

Proof. Given any preference profile R, let A = GEBM(R). (PE) We prove by mathematical induction that for any c ∈ {1, . . . , ⌈m/n⌉}, assignment ∑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′ = ∑c′<c Ac′ satisfies PE, we prove that A = ∑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 = ∑⌈m/n⌉ c=1 P c and:

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 = ∑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 | ∑j∈N A<c (j, o) = 0}.

We first show that:

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 = ∑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 ∑si=1 pi ̸= ∑si=1 qi, then ∑si=1 pi ≻lexi ∑si=1 qi .

By P = ∑⌈m/n⌉ c=1 P c andClaim1, 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.

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 - ∑o′∈U(j,o) P c (j, o′ ) + δj = 1, or - ⋃k∈No δk = s(o). 8.2: P c (j, o) ← δj, and s(o) ← s(o) - ⋃k∈No δk. 9: M ′ ←M ′ \{o ∈M ′ | s(o) = 0}. N ′ ←N ′ \{j ∈ N ′ | ∑o′∈U(j,o) P c (j, o′ ) = 1}. 10: r ← r + 1. ⌈m/n⌉ ∑ P c .
• 11: return c=1
• 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:

We show in Lemma 4 that the random assignment P c obtained at the end of each round c of GPBM satisfies sdE, 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 j 1 , . . . , 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., the assignment A in Example 1 is a possible result drawn from {P 1 , P 2 }. Since ∑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 j c 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) = ∑⌈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⌉;

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)) = ∑c≤⌈m/n⌉ P c . We prove by mathematical induction that for any c ∈

{1, . . . , ⌈m/n⌉}, it holds that P ≤c = ∑c′≤c P c′ satisfies sdE.

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 = ∑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:

By Eq (3), it must hold that in round c+1 of GPBMwhen 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).

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

We see that ∑o′≻3o P(1, o′ ) = ∑o′≻3o P(3, o′ ) for o ∈ {a, c, d} and ∑o′≻3b P(1, o′ ) = 5/6 > 1/3 = ∑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-WSPmechanism that satisfies FCM, PE, EF1, and neutrality ex-post. Let R be:

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:

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:

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:

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

6 Conclusion and FutureWork

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 BoBW, 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.

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.