Random Assignment of Indivisible Goods under Constraints

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

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) Birkhoffvon 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 ∑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 ⊆

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 ∑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 = PrA∼p[e ∈ Ai] = ∑A∈A: e∈Ai pA 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 ∑e′∈U(≻i,e) xe′ ≥ ∑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 ∑e′∈U(≻i,e) πp ie′ = ∑e′∈U(≻i,e) ∑A∈A: e′∈Ai pA = ∑A∈A pA|Ai ∩ U(≻i, e)|, and hence the condition πq i ⪰sd i πp i in Definition 1 is equivalent to the condition

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 .

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 pA > 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:

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{ ∑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

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

Note that, if the constraints are identical (i.e., F1 = · · · = Fn), the condition (2) coincides with πp i ⪰sd i πp j (recall that ∑e′∈U(≻i,e) πp ie′ = ∑A∈A pA|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 ∑A∈A qA|A1∩U(≻i, b)| = 0.5 is smaller than ∑A∈A qAmaxY⊆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.

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),

Note that (E,F1) and (E,F2) are matroids. For this instance, the generalized PS mechanism (the VER mechanism) outputs

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 system 1 .

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].

1 Consider 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

[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 Birkhoffvon 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 withMatroid 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 ∑i∈N ∑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 ∑i∈N ∑e∈E wiex′ie > ∑i∈N ∑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:

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 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 ≤ 1n · 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[ 12 · 1], F2[ 12 · 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:

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 ← ∑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 +;

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

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.

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 pA > 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

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

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:

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

Moreover, we have α+2γ = π1d +π1a +π1b ≥ π2d +π2a + π2b = 1 + α - γ by sd-envy-freeness; therefore,

For a sufficiently small positive ε, let

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

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.