# random_assignment_of_indivisible_goods_under_constraints__95961d03.pdf

Random Assignment of Indivisible Goods under Constraints

Yasushi Kawase1 , Hanna Sumita2 and Yu Yokoi2

1University of Tokyo 2Tokyo Institute of Technology kawase@mist.i.u-tokyo.ac.jp, {sumita, yokoi}@c.titech.ac.jp

We investigate the problem of random assignment of indivisible goods, in which each agent has an ordinal preference and a constraint. Our goal is to characterize the conditions under which there always exists a random assignment that simultaneously satisfies efficiency and envy-freeness. The probabilistic serial mechanism ensures the existence of such an assignment for the unconstrained setting. In this paper, we consider a more general setting in which each agent can consume a set of items only if the set satisfies her feasibility constraint. Such constraints must be taken into account in student course placements, employee shift assignments, and so on. We demonstrate that an efficient and envy-free assignment may not exist even for the simple case of partition matroid constraints, where the items are categorized, and each agent demands one item from each category. We then identify special cases in which an efficient and envyfree assignment always exists. For these cases, the probabilistic serial cannot be naturally extended; therefore, we provide mechanisms to find the desired assignment using various approaches.

1 Introduction Assigning indivisible items to agents with preferences is one of the most fundamental problems in computer science and economics [Nisan et al., 2007; Rothe, 2015]. Examples of such problems include university housing assignments, student course placements, employee shift assignments, and professional sports drafts. In these kinds of problems, we are given a set of agents, a set of indivisible items, and preferences of the agents. The goal of the problem is to find an assignment that satisfies efficiency and fairness. This study deals with the case where only ordinal information on preferences is available. Such an assumption is common in the literature because eliciting precise cardinal preferences would be difficult in practice (see Bogomolnaia and Moulin [2001] for more detailed justifications). Randomization is frequently used to achieve both efficiency and fairness when assigning indivisible items. Such a randomized assignment is referred to as lottery assignment.

The standard way to define efficiency and fairness for a lottery assignment when only ordinal preferences are available is to use stochastic dominance (SD) relation. An agent prefers one lottery assignment over another in terms of the SD relation if she obtains at least as much utility on average from the former assignment as the latter for all possible cardinal utilities consistent with the revealed ordinal preference. We consider sd-efficiency as an efficiency concept, which states that no agent can be made better off without making at least one other agent worse off with respect to the SD relation. The sd-efficiency means efficiency in the ex ante sense and also leads to efficiency in the ex post sense [Bogomolnaia and Moulin, 2001]. Additionally, as a concept of fairness, we consider sd-envy-freeness, which states that every agent prefers her (ex ante) assignment to that of every other agent with respect to the SD relation. Note that the sd-envyfreeness guarantees fairness in the ex ante sense but not in the ex post sense. The ex post unfairness is inevitable in the assignment of indivisible items. We also examine some other efficiency and fairness criteria. In a random assignment problem in which each agent receives one object, Bogomolnaia and Moulin [2001] proposed the probabilistic serial (PS) mechanism. In the mechanism, agents eat their preferred goods at an equal rate until all goods are consumed. This outputs a lottery assignment that is both sd-efficient and sd-envyfree. Kojima [2009] generalized this result to the case where each agent can receive more than one item and the agents preferences are additively separable over the items. Note that these studies focused on the unconstrained case. In reality, however, assignment problems frequently involve constraints. Motivated by real-world applications such as refugee resettlement [Delacr etaz et al., 2016], college admissions with budget constraints [Abizada, 2016], and day-care allocation [Okumura, 2019], assignment (or matching) problems under constraints have recently been an active research subject. As for random assignment under constraints, Aziz and Brandl [2022] proposed a generalized PS mechanism, called vigilant eating rule (VER), for a constrained case. This mechanism produces a random assignment that satisfies sdefficiency and equal treatment of equals, which is a weaker fairness notion than our sd-envy-freeness. However, VER may not produce an sd-envy-free lottery assignment. In this study, we seek to attain sd-efficiency and sd-envyfreeness in a general setting where each agent can consume a

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

set of items only if it satisfies her feasibility constraints. We suppose that constraints satisfy the hereditary property, that is, any subset of a feasible set is also feasible. A typical example of the hereditary property is a knapsack constraint, which represents the capacity of a limited resource, such as budget, time, or space. We also take a particular interest in matroid constraints, which is a subclass of hereditary constraints. It is known that matroid structure provides fruitful results in many other related assignment or matching problems [Babaioff et al., 2021; Benabbou et al., 2021; Barman and Verma, 2021; Goko et al., 2022]. Furthermore, the class of matroids is expressive enough to represent various constraints that naturally arise in many real-life assignment problems. For example, in the context of weekly employee shift assignments, if an employee can work at most one time slot per day, then her feasibility constraint is represented by a partition matroid. Even if she additionally declares that she can work at most three days a week, then her feasibility constraint is still a matroid (for the formal definition, see Model section). This study aimed to identify the settings in which sdefficiency and sd-envy-freeness are compatible. We demonstrate that an sd-efficient and sd-envy-free lottery assignment may not exist even for the simple case of partition matroid constraints. We then identify special cases in which an sdefficient and sd-envy-free lottery assignment always exists. Moreover, for such cases, we provide mechanisms to find the desired lottery assignment. This study does not address the strategic issue because no mechanism simultaneously satisfies sd-efficiency, sd-envy-freeness, and sd-weak-strategyproofness, even for 2 agents with no constraints [Kojima, 2009]. Due to space limitations, some proofs can be found in full version [Kawase et al., 2022].

1.1 Our Contributions We investigate the existence of sd-efficient and sd-envy-free assignments in 16 settings according to the following: (i) the number of agents is 2 or arbitrary n, (ii) the constraints are matroids or general hereditary constraints, (iii) the constraints of the agents are identical or heterogeneous, and (iv) the ordinal preferences of the agents are identical or heterogeneous. We demonstrate the impossibility of an sd-efficient and sdenvy-free assignment even when there are either

2 agents with identical preferences (Theorem 4) or

3 agents with identical partition matroid constraints (Theorem 5).

As tractability results, we demonstrate that an sd-efficient and sd-envy-free assignment always exists when there are

2 agents with matroid constraints (Theorem 1),

agents with identical preferences and heterogeneous matroid constraints (Theorem 2), or

identical agents (Theorem 3).

Moreover, we provide polynomial-time algorithms that find desired assignments in the settings of Theorems 1 and 2. By considering the inclusion relation, we obtain the results shown in Figure 1. The existence of an sd-efficient and sdenvy-free assignment is open when there are 2 agents with

identical constraints. Meanwhile, even when there are two agents with identical preferences and constraints, finding an sd-efficient and sd-envy-free lottery assignment is NP-hard (see full version). We investigate possible-envy-freeness, anonymity, necessarily Pareto-efficiency, and sd-proportionality as other efficiency and fairness notions (see Section 2.1 and full version).

1.2 Related Work Random assignment problems under partition matroid constraints are studied under the name of multi-type resource allocation problem [Monte and Tumennasan, 2015; Mackin and Xia, 2016; Wang et al., 2020; Guo et al., 2021]. Compared to our setting, these studies assume that ordinal preferences of agents over bundles are available. The above mentioned works and the present work deal with constraints on the agent side. There are also studies on random assignment with constraints on the item side [Fujishige et al., 2018; Budish et al., 2013]. Fujishige et al. [2018] provided an extension of the PS mechanism that outputs an sd-efficient and sd-envy-free assignment if the set of feasible integral vectors of items forms an integral polymatroid. Their proof heavily depends on the (generalized) Birkhoff von Neumann theorem: every fractional assignment can be expressed as a probability distribution over deterministic assignments. Note that the theorem also holds for our problem if the constraints are matroids. This leads us to expect that the PS mechanism produces an sd-efficient and sd-envy-free assignment when the constraints are matroids, but it is not the case, as we will show in Theorem 5. For the cardinal case, Cole and Tao [2021] proved that there always exists a Pareto-efficient and envy-free lottery assignment. Their framework is so general that any partitionbased utility functions (including additive utility functions with any constraints) can be handled. Their proof is based on fixed-point arguments and does not imply polynomial-time algorithms. Kawase and Sumita [2020] studied the computational complexity of finding a max-min fair lottery assignment under envy-free constraint in a cardinal setting.

2 Model We let [k] := {1, 2, . . . , k} for any nonnegative integer k. An instance of our problem is a tuple (N, E, ( i, Fi)i N), where N = [n] represents the set of agents and E = {e1, e2, . . . , em} represents the set of indivisible items. Each agent i N has a strict preference i over E and can consume a set of items in Fi 2E, which is the feasible set family of agent i. We assume that Fi is given by a membership oracle for each i N. The preferences over sets of items are additively separable across items, meaning that each agent i has a cardinal utility function ui : E R++, and her utility for a bundle E Fi is P e E ui(e). Here, R++ is the set of positive real numbers. We assume that the preference of each agent i has no ties and that the central authority knows only the ordinal preferences i that are consistent with ui. In other words, i is a strict order on E such that e i e if and only if ui(e) > ui(e ). For each agent i N, we assume that the pair (E, Fi) forms an independence system: the feasible set family Fi

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

Theorem 1 Theorem 2 Theorem 3

Theorem 4 Theorem 5

n,m,i,i 2,g,i,i

n,m,i,h 2,g,i,h

n,m,h,i 2,g,h,i

n,m,h,h 2,g,h,h

Figure 1: Summary of our results on the existence of an sd-efficient and sd-envy-free assignment. Each of the 16 cases is identified by four characters, such as 2,m,i,i. The first, second, third, and fourth characters, respectively, indicate whether there are 2 or an arbitrary n number of agents, whether the constraints are matroids or general, whether the constraints are identical or heterogeneous, and whether the preferences are identical or heterogeneous. For each case, the box is painted green if such a lottery assignment always exists and red otherwise.

2E is nonempty and satisfies the hereditary property, that is, X Y Fi implies X Fi. We denote by conv(Fi) the convex hull of the characteristic vectors of the members of Fi, where the characteristic vector of X Fi is a vector in {0, 1}E whose component corresponding to e E is 1 if and only if e X, and the convex hull of S RE is the smallest convex set containing S. We note that conv(Fi) [0, 1]E. We will also consider a special case where each (E, Fi) is a matroid, which is an independence system satisfying a property called the augmentation axiom: if X, Y Fi and |X| < |Y | then there exists e Y \ X such that X {e} Fi. A simple example of a matroid is a partition matroid, which represents a constraint in which items are categorized, and the number of items we can take from each category is constrained. More precisely, a partition matroid (E, F) is determined by a partition E1, E2, . . . , Ek of E and capacities q1, q2, . . . , qk Z+, and F is of the form {X E : |X Ei| qi ( i [k])}. A deterministic assignment is a list A = (A1, . . . , An) of subsets of E such that (i) Ai Fi for all i N and (ii) Ai Aj = for all distinct i, j N. Let A be the set of all deterministic assignments. A lottery assignment is a probability distribution over A. We denote the set of all lottery assignments by (A). A fractional assignment is a matrix π = (πie)i N,e E RN E such that P i N πie 1 for every item e E. We interpret πie as the probability that agent i N receives item e E. For each i N, we denote the row in π corresponding to agent i by πi, that is, πi = (πie)e E [0, 1]E. A lottery assignment p (A) induces a fractional assignment π RN E such that πie = Pr A p[e Ai] = P A A: e Ai p A for all i N and e E. We will write πp for the fractional assignment induced from p. A fractional assignment is called feasible if it is induced from some lottery assignment. Let conv(A) RN E be the convex hull of the characteristic vectors of the members of A. By definition, a fractional assignment belongs to conv(A) if and only if it is feasible, i.e., induced from some lottery assignment p (A). For

any feasible fractional assignment π conv(A), a lottery assignment inducing π is not unique in general. According to Carath eodory s theorem (see, e.g., Schrijver [1998, p.94]), there exists such a lottery assignment with a support size of not more than |N| |E| + 1.

2.1 Desirable Properties For a preference i, let U( i, e) := {e E : e i e} be the set of items that are not worse than e with respect to i. We say that x RE + weakly stochastically dominates y RE +, denoted by x sd i y, if P e U( i,e) xe P e U( i,e) ye for all e E. If x sd i y and x = y, we say that x stochastically dominates y and denote x sd i y. Note that x stochastically dominates y if and only if the expected utility of x is greater than that of y for all possible cardinal utilities consistent with i. Pareto-efficiency is a standard efficiency concept where no agents can be made better off without making at least one other agent worse off. A natural notion of efficiency for lottery assignments is defined as Pareto-efficiency with respect to the SD relation. Definition 1 (sd-efficiency). A lottery assignment p (A) is called sd-efficient (also called ordinally efficient or necessarily Pareto-efficient) if there is no lottery assignment q (A) that satisfies πq i sd i πp i for all i N and πq j sd j πp j for some j N. Note that, for any lottery assignment p (A), we have P e U( i,e) πp ie = P

e U( i,e) P

A A: e Ai p A = P A A p A|Ai U( i, e)|, and hence the condition πq i sd i πp i in Definition 1 is equivalent to the condition X

A A q A|Ai U( i, e)| X

A A p A|Ai U( i, e)| ( e E).

In addition, a lottery assignment is sd-efficient if and only if it is Pareto-efficient for some possible cardinal utilities consistent with ( i)i N.

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

A weaker notion of efficiency can be defined as an ex post sense. A lottery assignment p (A) is called ex post efficient if, for any A A with p A > 0, a lottery assignment that takes A with probability 1 is sd-efficient. By definition, sd-efficiency implies ex post efficiency. On the other hand, ex post efficiency does not imply sd-efficiency. Example 1 (ex post efficiency does not imply sd-efficiency). Consider an instance (N, E, ( i, Fi)i N) where N = {1, 2}, E = {a, b, c, d}, Fi = {X E : |X {c, d}| 1 and |X| 2}, and a i b i c i d for both i = 1, 2. Note that (E, F1) (= (E, F2)) is a matroid. Let p be the lottery assignment that takes each of (A1, A2) = ({a, c}, {b, d}) and ({b, d}, {a, c}) with probability 0.5. Also, let q be the lottery assignment that takes each of (A1, A2) = ({a, b}, {c}) and ({c}, {a, b}) with probability 0.5. It is not difficult to check that the lottery assignments p and q are ex post efficient. Note that p and q respectively induce the following fractional assignments:

1 1/2 1/2 1/2 1/2

2 1/2 1/2 1/2 1/2

1 1/2 1/2 1/2 0

2 1/2 1/2 1/2 0

Thus, q is not sd-efficient because πp i sd πq i for all i N. On the other hand, p is sd-efficient. Necessarily Pareto-efficient is a stronger notion of efficiency, which means that a lottery assignment is Paretoefficient under every possible cardinal utility consistent with the given ordinal preferences. This notion is outside the scope of this paper because no assignment may satisfy it, even in the single-agent case (see full version). As a notion of fairness, we consider envy-freeness. For the unconstrained setting, a standard definition of sd-envyfreeness requires a fractional assignment to satisfy πp i sd i πp j for any agents i, j N. This condition is equivalent to the expected utility of the fractional assignment of agent i being no worse than that of any other agent j with respect to any cardinal utility consistent to i [Aziz et al., 2015]. In our setting, however, this equivalence does not hold due to the existence of constraints. Indeed, the bundle assigned to agent j is not feasible for agent i in general. Therefore, we have to take constraints into account when considering each agent s envy toward other agents. For a utility function ui consistent to i, let ui(X) be i s evaluation of a bundle X E (that may be infeasible for i to consume). That is, ui(X) = max { P e Y ui(e) : Y X, Y Fi }. Then, a natural generalization of sd-envy-freeness is to impose a lottery assigngment p (A) to satisfy

EA p[ ui(Ai)] EA p[ ui(Aj)]

( i, j N, ui RE ++ consistent to i). (1)

It turns out that the condition (1) is equivalent to the condition (2) below. Since (2) does not use utility functions, we adopt (2) as the definition of sd-envy-freeness. We show the equivalence in Proposition 1, whose proof is found in full version. Definition 2 (sd-envy-freeness). A lottery assignment p (A) is called sd-envy-free (also called necessary envy-free

or not envy-possible) if X

A A p A|Ai U( i, e)| X

A A p A max Y Aj : Y Fi |Y U( i, e)|

( i, j N, e E). (2)

Note that, if the constraints are identical (i.e., F1 = = Fn), the condition (2) coincides with πp i sd i πp j (recall that P e U( i,e) πp ie = P A A p A|Ai U( i, e)|). Hence, Definition 2 indeed generalizes the standard definition of sd-envyfreeness. Proposition 1. A lottery assignment p (A) is sd-envyfree if and only if it satisfies (1). In contrast to sd-efficiency, which is defined only by the induced fractional assignment πp, the definition of sd-envyfreeness requires the information of a lottery assignment p itself. That is, sd-envy-freeness is a property of lottery assignments and cannot be that of fractional assignments in our constrained setting. The following example gives two lottery assignments that induce the same fractional assignment, but only one of them is sd-envy-free. Example 2. Consider an instance (N, E, ( i, Fi)i N) where N = {1, 2}, E = {a, b}, F1 = , {a}, {b} , F2 = , {a}, {b}, {a, b} , and a i b for i = 1, 2. Then, the lottery assignment p that takes (A1, A2) = ({a}, ) and ( , {a, b}) with probability 0.5 each is sd-envy-free. In contrast, the lottery assignment q that takes (A1, A2) = ({a}, {b}) and ( , {a}) with probability 0.5 each is not sdenvy-free because P A A q A|A1 U( i, b)| = 0.5 is smaller than P A A q A max Y A2: Y F1 |Y U( i, b)| = 1. However, the two lottery assignments lead to the same fractional assignment, i.e., πp = πq. We call a lottery assignment p possible-envy-free if, for each agent i, there exists a cardinal utility ui RE ++ consistent to i such that i does not envy any other agent in terms of expectation (i.e., EA p[ ui(Ai)] EA p[ ui(Aj)] for all j N). Hence, a lottery assignment p is sd-efficient and possible-envy-free if there exist consistent cardinal utilities that make p Pareto-efficient and envy-free in the cardinal sense. Combined with a fact known for a cardinal setting, this implies the existence of an sd-efficient and possible-envy-free lottery assignment in our setting. That is, to find such a lottery assignment, it is sufficient to fix a consistent utility function for each agent (say, ui(e) = |{e E : e e }| for each i N and e E) and take a lottery assignment that satisfies Pareto-efficiency and envy-freeness with respect to these utility functions, where the existence of such an assignment is guaranteed [Cole and Tao, 2021]. For the unconstrained setting, the PS mechanism is known to satisfy both sd-efficiency and sd-envy-freeness. Therefore, to achieve these two desirable properties in our constrained setting, a natural approach is to consider the generalized version of the PS mechanism in which each agent consumes the best remaining item while preserving feasibility. The vigilant eating rule (VER) mechanism in [Aziz and Brandl, 2022] includes this generalization. However, the generalized PS mechanism does not guarantee sd-envy-freeness, as shown in the following example.

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

Example 3 (generalized PS is not sd-envy-free). Consider an instance (N, E, ( i, Fi)i N) where N = {1, 2}, E = {e1, e2, . . . , e7}, e1 i e2 i i e7 (i = 1, 2), F1 = {X E : |X {e1, e2, e3, e5}| 2}, and F2 = {X E : |X {e1, e2, e3}| 1}. Note that (E, F1) and (E, F2) are matroids. For this instance, the generalized PS mechanism (the VER mechanism) outputs

π = e1 e2 e3 e4 e5 1 1/2 1/2 1 0 0

2 1/2 1/2 0 1 1

However, this is not sd-envy-free because the total amount of items assigned to agent 2 is larger than that of agent 1, which causes agent 1 to envy agent 2.

3 Related Properties of Matroids We introduce several matroid properties, which will be used in our analyses. Let (E, F) be a matroid and conv(F) RE + be the convex hull of the characteristic vectors of the members of F. For any vector x RE +, define a polytope conv(F)x := { y conv(F) : y x } RE +. Recall that, for any total order on E, we denote s sd t if s RE + stochastically dominates t RE + with respect to . We call a vector s conv(F)x lexicographically maximum with respect to in conv(F)x if the value of the highest rank component is as large as possible; subject to this, the value of the next highest rank component is as large as possible, and so on. The following lemma shows that the lexicographically maximum vector stochastically dominates all other vectors in the polytope conv(F)x. Note that this is a special property of a matroid and is not satisfied in general if (E, F) is an arbitrary independence system1. Lemma 1. For any matroid (E, F), any vector x RE +, and any total order on E, let y be the lexicographically maximum vector in conv(F)x with respect to . Then, y sd y holds for every vector y conv(F)x. For a matroid (E, F) and a total order on E, let F : RE + RE + be a function that returns the vector F[x] that is lexicographically maximum with respect to in conv(F)x for any given vector x RE +. We refer to this function F as the choice function induced from (E, F) and . For example, if E = {e1, e2, e3, e4}, F = {X E : |X {e1, e3}| 1 and |X| 2}, e1 e2 e3 e4, and x = (xe1, xe2, xe3, xe4) = (0.4, 0.8, 1, 1), the induced choice F[x] is (0.4, 0.8, 0.6, 0.2). The following fact is an immediate consequence of Lemma 1. Lemma 2. For any matroid (E, F) and any total order on E, let F : RE + RE + be the choice function induced from (E, F) and . For any x, y RE +, the condition xe ye ( e E) implies F[x] sd F[y].

1Consider the convex hull of the non-matroid family F = , {e1}, {e2}, {e3}, {e2, e3} and the total order such that e1 e2 e3, and let x = (xe1, xe2, xe3) = (1, 1, 1). The lexicographically maximal solution is y = (1, 0, 0) conv(F)x, but y does not stochastically dominate (0, 1, 1) conv(F)x.

Recall that P := conv(A) RN E denotes the polytope corresponding to the set of feasible fractional assignments. When (E, Fi) is a matroid for every i N, the following properties are known to hold for P: (i) P is represented as

P = π RN E : πi conv(Fi) ( i N), P

i N πie 1 ( e E)

[Schrijver, 2003]; (ii) For a given feasible fractional assignment π P, we can compute in polynomial time a lottery assignment that induces π [Gr otschel et al., 2012]. Note that property (i) can be viewed as a generalization of the Birkhoff von Neumann theorem. Finally, we state a sufficient condition for a lottery assignment to be sd-envy-free on matroid constraints. Let Fi be the choice function induced from (E, Fi) and i for each i N. Proposition 2. Suppose that the constraints are matroid. For any lottery assignment p (A), if πp i sd i Fi[πp j ] for every i, j N then p is sd-envy-free. By summarizing the discussion in this section, we conclude that an sd-envy-free and sd-efficient lottery assignment can be found by computing a feasible fractional assignment p P that satisfies πp i sd i Fi[πp j ] ( i, j N) and q P \ {p} such that πq i sd i πp i ( i N), when the constraints are matroid.

4 Tractability Results Now, we provide our tractability results.

4.1 Two Agents with Matroid Constraints First, we provide a polynomial-time algorithm to find an sd-efficient and sd-envy-free lottery assignment for the case where there are two agents (i.e., N = {1, 2}) and the constraints F1 and F2 are matroids. Note that due to Example 3, we need a different approach from generalizing the PS mechanism. Let (wie)i N,e E be positive weights such that wia > wib if and only if a i b (e.g., wie = |{e E : e i e }| for each i N and e E). Then, a feasible fractional assignment x P that maximizes P i N P e E wiexie is sd-efficient. Indeed, if there exists a feasible fractional assignment x P \ {x} such that x i sd i xi, then we have P i N P e E wiex ie > P i N P e E wiexie, and hence x does not attain the maximum weight. This may raise the expectation that a fractional assignment that satisfies both sd-efficiency and sd-envy-freeness can be found by computing a maximum weight feasible fractional assignment subject to an sd-envy-free constraint. If F1 = F2, such an optimization problem is formulated as the following linear programming:

max P i {1,2} P e E wiexie

s.t. x1 sd 1 x2, x2 sd 2 x1, x P. (4)

However, the optimal solution for (4) is not always sdefficient. To observe this, let us consider an instance where E = {e1, e2, e3}, F1 = F2 = {X E : |X {e1, e2}| 1}, e3 1 e2 1 e1, and e2 2 e1 2 e3. By setting wie = |{e E : e i e }| for each i N and

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

e E, the optimal solution of the linear programming (4) is (x1, x2) = ((0, 0, 1), (0, 1, 0)). However, this is not sdefficient because, for (y1, y2) = ((1, 0, 1), (0, 1, 0)) P, we have y1 sd 1 x1 and y2 = x2. In our approach, the following notion will be useful.

Definition 3 (sd-proportional). A lottery assignment p (A) is called sd-proportional if πp i sd i xi holds for any i N and x P with xi 1

n 1, where 1 is the all-ones vector in RE.

We can observe that sd-proportional lottery assignments must exist as follows. Consider a fractional assignment π = (π 1, π 2) = (F1[ 1

2 1], F2[ 1

2 1]), where Fi is the choice function induced from (E, Fi) and i for each i = 1, 2. Then π belongs to P = conv(A) as P is represented by (3). Then, there is a lottery assignment that induces π , while π satisfies the condition for sd-proportionality by Lemma 1. We remark that the existence of sd-proportional lottery assignment does not hold for the general hereditary constraints case (see full version). Furthermore, by using Lemma 2, we can observe that sdproportionality is a stronger condition than sd-envy-freeness.

Lemma 3. If the number of agents is 2 and the constraints are matroids, sd-proportionality implies sd-envy-freeness.

Consider the following linear programming, which is obtained from (4) by replacing sd-envy-freeness constraint with sd-envy-proportionality constraint:

max P i {1,2} P e E wiexie

s.t. x1 sd 1 F1[ 1

2 1], x2 sd 2 F2[ 1

2 1], x P. (5)

We can show that, unlike the case of (4), the optimal solution for (5) is sd-efficient. Furthermore, it is sd-proportional, and hence sd-envy-free by Lemma 3. Thus, we obtain the following theorem.

Theorem 1. A lottery assignment that satisfies sd-efficiency and sd-envy-freeness always exists and can be computed in polynomial time if the number of agents is 2 and the constraints are matroids.

4.2 Matroid Constraints and Identical Preferences Next, we provide a polynomial-time algorithm to find an sd-efficient and sd-envy-free lottery assignment for the case where the preferences are identical and the constraints are (heterogeneous) matroids. Suppose that E = {e1, e2, . . . , em} and the preference of each agent i satisfies e1 i e2 i i em without losing generality. We use to represent i for simplicity. Recall that the natural generalization of the PS mechanism does not work for this setting as shown in Example 3. We generalize the mechanism in a different way. In our algorithm, we regard each item as a divisible item of probability shares and process the items one at a time. During the first round, each agent eats e1 at the same speed while e1 is not eaten up and is available for her. Similarly, at the kth round, each agent eats ek at the same speed while it remains and is available for her. Our algorithm is formally described in Algorithm 1, where χek is the characteristic vector in {0, 1}E,

Algorithm 1: Heterogeneous matroid constraints and identical preferences

1 Let x 0 RN E;

2 for k 1, 2, . . . , m do

3 while True do

4 Let εi max{ε : xi + ε χek conv(Fi)} ( i N);

5 Let N + {i N : εi > 0};

6 Let s P i N xiek;

7 if N + = or s = 1 then Break;

8 Let ε min{mini N + εi, (1 s)/|N +|};

9 Update xi xi + ε χek for each i N +;

10 return a lottery assignment p (A) s.t. πp = x;

i.e., its component corresponding to e E is 1 if e = ek and 0 otherwise. Note that Algorithm 1 can be implemented to run in polynomial time because εi at line 4 can be computed via submodular function minimization (for details, see the proof of Theorem 2 in full version). For the instance in Example 3, Algorithm 1 outputs an sdefficient and sd-envy-free lottery assignment p such that

πp = e1 e2 e3 e4 e5 1 1/2 1/2 1 1/2 0

2 1/2 1/2 0 1/2 1

By using properties of matroids shown in Lemma 2 and Proposition 2, we can show the correctness of Algorithm 1 for an arbitrary number of agents. Theorem 2. An sd-efficient and sd-envy-free lottery assignment always exists and can be computed in polynomial time if the constraints are matroids, and the preferences are identical.

4.3 Identical Constraints and Preferences Finally, we provide the existence result when the constraints and preferences are identical. Theorem 3. For any instance with identical constraints and preferences, an sd-efficient and sd-envy-free lottery assignment must exist. We note that an sd-efficient and sd-envy-free lottery assignment can be computed in polynomial time when the agents have identical matroid constraints and identical preferences. In contrast, for general identical constraints, computing such a lottery assignment is NP-hard even if n = 2 (see full version).

5 Impossibility Results In this section, we present impossibility results.

5.1 Identical Preferences We first consider the case where the preferences are identical. We have demonstrated that, if the constraints are matroids, then an sd-efficient and sd-envy-free lottery assignment must exist (Theorem 2). However, it is not true for general hereditary constraints.

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

Theorem 4. An sd-efficient and sd-envy-free lottery assignment may not exist even with two agents, and the preferences are identical.

Proof. Let (N, E, ( i, Fi)i N) be an instance where N = {1, 2}, E = {e1, e2, e3, e4}, F1 = 2{e1} 2{e2} 2{e3,e4}, F2 = 2E, and e1 i e2 i e3 i e4 (i = 1, 2). Then, no lottery assignment in this instance satisfies sd-efficiency and sd-envy-freeness simultaneously. Suppose to the contrary that p (A) is an sd-efficient and sd-envy-free lottery assignment. Because F2 is 2E and p is sd-efficient, we have p A > 0 only if A = (A1, A2) satisfies A1 A2 = E. Thus, πp 1e + πp 2e = 1 for all e E. By the sd-envy-freeness of p, we must have πp 1e1 = πp 2e1 = 1/2, and hence p({e1},{e2,e3,e4}) = 1/2. Additionally, πp 1e2 = πp 2e2 = 1/2 by the sd-envy-freeness, and hence p({e2},{e1,e3,e4}) = 1/2. Then, the condition (2) is violated for i = 1, j = 2, and e = e4 because we have X

A A p A|A1 U( 1, e4)| < X

A A p A max Y A2: Y F1 |Y U( 1, e4)|,

where the left-hand side is 1 and the right-hand side is 2. This contradicts sd-envy-freeness of p.

5.2 Identical Matroid Constraints

Next, we observe the case where the constraints are an identical matroid.

Theorem 5. An sd-efficient and sd-envy-free lottery assignment may not exist even with three agents and identical matroid constraints.

Proof. Let (N, E, ( i, Fi)i N) be an instance where N = {1, 2, 3}, E = {a, b, c, d, e}, Fi = {X E : |X {a, b, c}| 1} for all i N, and

d 1 a 1 b 1 c 1 e, d 2 b 2 e 2 a 2 c, a 3 d 3 e 3 b 3 c.

We prove that no lottery assignment in this instance satisfies sd-efficiency and sd-envy-freeness simultaneously. To obtain a contradiction, suppose that an sd-efficient and sd-envy-free lottery assignment induces π P. Then, by sdefficiency, each agent receives a unit amount of item {a, b, c} and 2/3 amount of {d, e}. Let π1d = α, π3a = β, and π2c = γ. By sd-envy-freeness, the fractional assignment π can be written as follows:

1 1 3α+β 1+3α β+2γ 1 2γ α 2 3 α

2 3α 2β 1 3α+2β γ γ α 2 3 α

3 β 1 β γ γ 1 2α 1

As π is a feasible fractional assignment, we have π3d = 1 2α 0 and π2a = 3α 2β 0. Thus, we obtain

α 1/2 and β 3α/2 3/4. (6)

Moreover, we have α+2γ = π1d +π1a +π1b π2d +π2a + π2b = 1 + α γ by sd-envy-freeness; therefore, γ 1/3. (7) For a sufficiently small positive ε, let

1 ε ε 0 0 0

2 ε ε 0 0 0

3 0 0 0 0 0

1 ε 0 ε ε ε

2 0 0 0 0 0

3 ε 0 ε ε ε

Because π and π improve π, they must be infeasible. By the infeasibility of π , we have (i) π1b = 1+3α β+2γ = 0 or (ii) π2a = 3α 2β = 0 (because π1b > 0 implies π2b < 1 and π2a > 0 implies π1a < 1). Additionally, by the infeasibility of π , we have (iii) π1a = 1 3α + β = 0 or (iv) π3d = 1 2α = 0 (because π1c = 1 2γ 1/3 < 1, π1d = α 1/2 < 1, π1e = 2/3 α 1/6 > 0, π3a = β 3/4 < 1, π3c = γ 1/3 > 0, and π3e = 1/3 + 2α 2/3 < 1 from (6) and (7)). We consider four possible cases separately.

Case 1 (i) 1 + 3α β + 2γ = 0 and (iii) 1 3α + β = 0. Then, γ = 0, which contradicts γ 1/3 from (7).

Case 2 (i) 1 + 3α β + 2γ = 0 and (iv) 1 2α = 0. Then, γ = (1 3α + β)/2 = ( 1/2 + β)/2 1/3 from (7). This implies β 7/6, which contradicts β = π3a 1.

Case 3 (ii) 3α 2β = 0 and (iii) 1 3α + β = 0. Then, α = 2/3, which contradicts α 1/2 from (6). Case 4 (ii) 3α 2β = 0 and (iv) 1 2α = 0. Then, α = 1/2 and β = 3/4. Hence, π3b = 1/4 γ 0, which contradicts γ 1/3 from (7). Thus, no fractional assignment in the instance satisfies sdefficiency and sd-envy-freeness simultaneously.

We can also demonstrate that, for any n 3, there exists an instance that has no sd-efficency and sd-envy-freeness lottery assignment. Consider an instance (N, E, ( i, Fi)i N) where N = {1, 2, . . . , n}, E = {a, b, c, d, e, o6, . . . , o2n}, Fi = {X E : |X {a, b, c}| 1} for all i N, and d 1 a 1 b 1 c 1 e 1 o6 1 , d 2 b 2 e 2 a 2 c 2 o6 2 , a 3 d 3 e 3 b 3 c 3 o6 3 , o2i 1 i o2i i (i = 4, 5, . . . , n). Then, analysis similar to that in the proof of Theorem 5 demonstrates that this instance does not have an sd-efficient and sd-envy-free lottery assignment.

Acknowledgments We would like to thank the anonymous reviewers for their valuable comments. This work was partially supported by JSPS KAKENHI Grant Numbers JP17K12646, JP18K18004, JP20K19739, JP21K17708, and JP21H03397, by JST PRESTO Grant Numbers JPMJPR2122 and JPMJPR212B, and by Value Exchange Engineering, a joint research project between Mercari, Inc.

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

References [Abizada, 2016] Azar Abizada. Stability and incentives for college admissions with budget constraints. Theoretical Economics, 11(2):735 756, 2016. [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 et al., 2015] Haris Aziz, Serge Gaspers, Simon Mackenzie, and Toby Walsh. Fair assignment of indivisible objects under ordinal preferences. Artificial Intelligence, 227:71 92, 2015. [Babaioff et al., 2021] Moshe Babaioff, Tomer Ezra, and Uriel Feige. Fair and truthful mechanisms for dichotomous valuations. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pages 5119 5126, 2021. [Barman and Verma, 2021] Siddharth Barman and Paritosh Verma. Existence and computation of maximin fair allocations under matroid-rank valuations. In Proceedings of the 20th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), page 169 177, 2021. [Benabbou et al., 2021] Nawal Benabbou, Ayumi Igarashi, Mithun Chakraborty, and Yair Zick. Finding fair and efficient allocations for matroid rank valuations. ACM Transactions on Economics and Computation, 9(4):1 41, 2021. [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. [Cole and Tao, 2021] Richard Cole and Yixin Tao. On the existence of Pareto efficient and envy-free allocations. Journal of Economic Theory, 193, 2021. [Delacr etaz et al., 2016] David Delacr etaz, Scott Duke Kominers, and Alexander Teytelboym. Refugee resettlement. University of Oxford Department of Economics Working Paper, 2016. [Fujishige et al., 2018] Satoru Fujishige, Yoshio Sano, and Ping Zhan. Submodular optimization views on the random assignment problem. Mathematical Programming, 178(1 2):485 501, 2018. [Goko et al., 2022] Hiromichi Goko, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino, Hanna Sumita, Akihisa Tamura, Yu Yokoi, and Makoto Yokoo. Fair and truthful mechanism with limited subsidy. In Proceedings of the 21st International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 534 542, 2022. [Gr otschel et al., 2012] Martin Gr otschel, L aszl o Lov asz, and Alexander Schrijver. Geometric algorithms and combinatorial optimization, volume 2. Springer Science & Business Media, 2012.

[Guo et al., 2021] Xiaoxi Guo, Sujoy Sikdar, Haibin Wang, Lirong Xia, Yongzhi Cao, and Hanpin Wang. Probabilistic serial mechanism for multi-type resource allocation. Autonomous Agents and Multi-Agent Systems, 35(1):1 48, 2021. [Kawase and Sumita, 2020] Yasushi Kawase and Hanna Sumita. On the max-min fair stochastic allocation of indivisible goods. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pages 2070 2078, 2020. [Kawase et al., 2022] Yasushi Kawase, Hanna Sumita, and Yu Yokoi. Random assignment of indivisible goods under constraints. ar Xiv, 2208.07666, 2022. [Kojima, 2009] Fuhito Kojima. Random assignment of multiple indivisible objects. Mathematical Social Sciences, 57(1):134 142, 2009. [Mackin and Xia, 2016] Erika Mackin and Lirong Xia. Allocating indivisible items in categorized domains. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, pages 359 365, 2016. [Monte and Tumennasan, 2015] Daniel Monte and Norovsambuu Tumennasan. Centralized allocation in multiple markets. Journal of Mathematical Economics, 61:74 85, 2015. [Nisan et al., 2007] Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. Algorithmic game theory. Cambridge University Press, New York, NY, USA, 2007. [Okumura, 2019] Yasunori Okumura. School choice with general constraints: a market design approach for the nursery school waiting list problem in Japan. The Japanese Economic Review, 70(4):497 516, 2019. [Rothe, 2015] J org Rothe. Economics and computation, volume 4. Springer, 2015. [Schrijver, 1998] Alexander Schrijver. Theory of linear and integer programming. John Wiley & Sons, 1998. [Schrijver, 2003] Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics. Springer, 2003. [Wang et al., 2020] Haibin Wang, Sujoy Sikdar, Xiaoxi Guo, Lirong Xia, Yongzhi Cao, and Hanpin Wang. Multi-type resource allocation with partial preferences. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pages 2260 2267, 2020.

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