# mixed_fair_division_a_survey__f4fde760.pdf

Journal of Artificial Intelligence Research 80 (2024) 1373-1406 Submitted 12/2023; published 08/2024

Mixed Fair Division: A Survey

Shengxin Liu sxliu@hit.edu.cn School of Computer Science and Technology Harbin Institute of Technology, Shenzhen Building L, Harbin Institute of Technology Campus Xili Shenzhen University City, Shenzhen, China

Xinhang Lu xinhang.lu@unsw.edu.au Mashbat Suzuki mashbat.suzuki@unsw.edu.au Toby Walsh t.walsh@unsw.edu.au School of Computer Science and Engineering The University of New South Wales Building K17, UNSW Sydney, NSW 2052, Australia

Fair division considers the allocation of scarce resources among agents in such a way that every agent gets a fair share. It is a fundamental problem in society and has received significant attention and rapid developments from the game theory and artificial intelligence communities in recent years. The majority of the fair division literature can be divided along at least two orthogonal directions: goods versus chores, and divisible versus indivisible resources. In this survey, besides describing the state of the art, we outline a number of interesting open questions and future directions in three mixed fair division settings: (i) indivisible goods and chores, (ii) divisible and indivisible goods (mixed goods), and (iii) indivisible goods with subsidy which can be viewed like a divisible good.

1. Introduction

In fair division, we look to allocate resources fairly among agents with possibly heterogeneous preferences over the resources. Fair division is a fundamental research topic in computational social choice (Brandt et al., 2016; Endriss, 2017; Rothe, 2024). It has a long and rich history dating back to the work of Steinhaus (1948), and has attracted ongoing interest from mathematicians, economists, and computer scientists in the past several decades (Amanatidis et al., 2023; Aziz, 2020; Brams & Taylor, 1996; Moulin, 2019; Nguyen & Rothe, 2023; Robertson & Webb, 1998; Suksompong, 2021, 2025; Walsh, 2020). Moreover, fair division methods have been deployed in practice (Budish et al., 2017) and made publicly available (Goldman & Procaccia, 2015; Igarashi & Yokoyama, 2023; Han & Suksompong, 2024; Shah, 2017); see also the Adjusted Winner website1 and a Rent Division Calculator2. The vast majority of fair division literature can be divided along two orthogonal directions according to:

the (in)divisibility of the resources, and

agents valuations over the resources.

1. https://pages.nyu.edu/adjustedwinner 2. https://www.nytimes.com/interactive/2014/science/rent-division-calculator.html

2024 The Authors. Published by AI Access Foundation under Creative Commons Attribution License CC BY 4.0.

Liu, Lu, Suzuki & Walsh

Specifically, in the former case, the resource is either divisible or indivisible, and in the latter case, the resource consists of either goods (positively valued) or chores (negatively valued). In many real-world scenarios, however, the resources to be allocated may be a mixture of different types. Our first example demonstrates a mixture of (indivisible) goods and chores: when distributing household tasks, some family member may enjoy cooking while others may find it torturous. The next example touches on a mixture of divisible and indivisible goods: when dividing up an estate or assets in a divorce, we usually have divisible goods like money, as well as indivisible goods like houses, cars, paintings, etc. It may also be that monetary compensation (a.k.a. subsidies) could help circumvent unfair allocations of indivisible inheritances. Classic fairness notions or algorithmic methods that work well with a single type of resources may not fare well in the aforementioned scenarios concerning mixed types of resources. In this survey, we discuss fair division with mixed types of resources, which has received growing attention in recent years, and focus on three mixed fair division domains:

Section 4 considers fair division of indivisible goods and chores, in which each agent may have positive, zero, or negative valuation over each item;

Section 5 focuses on fair division of mixed divisible and indivisible goods (mixed goods);

Section 6 focuses on fair division of indivisible goods with subsidy.

Clearly, the first and second domains relax one of the two orthogonal directions mentioned earlier. The second and third domains share some similarity in the sense that subsidy could be viewed as a divisible good; the key difference lies in how they approach fairness. In Section 5, both the divisible and indivisible goods are fixed in advance and we find approximately fair allocations. In Section 6, we allocate indivisible goods but introduce some additional amount of money in order to satisfy exact fairness. This survey outlines new fairness notions and related theoretical results that are addressed in the above mixed fair division settings as well as highlights a number of major open questions and interesting directions for future research.

2. Preliminaries

For each k N, let [k] := {1, 2, . . . , k}. Denote by N = [n] the set of n agents to whom we allocate some resource R, which may, e.g., consist of indivisible goods and chores (Section 2.2) or be a mix of divisible and indivisible goods (Section 2.3). An allocation A = (A1, A2, . . . , An) assigns bundle Ai to agent i N and Ai Aj = for all i = j; note that Ai can be empty. An allocation is said to be complete if the entire resource is allocated, i.e., S i N Ai = R, and partial otherwise. Unless specified otherwise, we assume allocations considered in this survey are complete.

2.1 Cake Cutting

When resource R is heterogeneous and infinitely divisible, the corresponding problem is commonly known as cake cutting (Brams & Taylor, 1996; Lindner & Rothe, 2024; Procaccia, 2016; Robertson & Webb, 1998). We will use the terms cake and divisible goods

Mixed Fair Division: A Survey

interchangeably. The cake, denoted by D, is represented by the normalized interval [0, 1]. A piece of cake is a union of finitely many disjoint (closed) intervals. Each agent i N is endowed with an integrable density function fi : [0, 1] R 0, capturing how the agent values each part of the cake. Given a piece of cake S [0, 1], agent i s utility over S is defined as ui(S) := R

S fi(x) dx. Denote by (D1, D2, . . . , Dn) the allocation of cake D. In order to access agents density functions, the cake-cutting literature usually adopts the Robertson-Webb (RW) query model (Robertson & Webb, 1998), which allows an algorithm to interact with the agents via the following two types of queries:

Evali(x, y) returns ui([x, y]);

Cuti(x, α) asks agent i to return the leftmost point y such that ui([x, y]) = α, or state that no such y exists.

Homogeneous Cake A homogeneous cake is a special case in which each density function fi takes on some constant value. Put differently, every agent values all pieces of equal length the same. Money, for example, can be viewed as a homogeneous cake that is valued the same by all agents.

2.2 Mixed Indivisible Goods and Chores

Discrete fair division, in which resource R consists of indivisible items, has received considerable attention in the last two decades, especially for allocating goods; see, e.g., (Amanatidis et al., 2023; Moulin, 2019; Nguyen & Rothe, 2023; Suksompong, 2021, 2025) for an overview of the most recent developments. We present here a general model where an agent may have a positive, zero, or negative utility for each indivisible item. Specifically, denote by O = [m] the set of m indivisible items. An (indivisible) bundle is a subset of O. Each agent i N is endowed with a utility function ui : 2O R such that ui( ) = 0, capturing how the agent values each bundle of the items. For an item o O, we will write ui(o) instead of ui({o}) for simplicity. A utility function u is said to be additive if u(O ) = P o O u(o) for any O O. Unless specified otherwise, we assume agents have additive utilities in this survey. Let O = (O1, O2, . . . , On) denote the allocation of items O. We say that an item o O is a good (resp., chore) for agent i if ui(o) 0 (resp., ui(o) 0), and let Gi (resp., Ci) be the set of goods (resp., chores) for agent i. In other words, for each item, agents have subjective opinions on whether the item is a good or a chore. An item is said to be an objective good (resp., objective chore) if the item is a good (resp., chore) for all agents. The presented model includes scenarios where all items are objective goods (resp., objective chores), which we will specifically refer to as an indivisible-goods (resp., indivisible-chores) setting.

(Doubly-)Monotonic Utilities While we mostly focus on additive utilities, we will identify some results that still hold with a larger class of utility functions. The utility function ui of agent i N is said to be doubly-monotonic if agent i can partition the items as O = Gi Ci such that for any item o O and for any bundle O O \ {o},

ui(O {o}) ui(O ) if o Gi, and

Liu, Lu, Suzuki & Walsh

ui(O {o}) ui(O ) if o Ci.

In the indivisible-goods (resp., indivisible-chores) setting, all agents i N have monotonically non-decreasing (resp., non-increasing) utility functions, that is, ui(S) ui(T) (resp., ui(S) ui(T)) for any bundles S T O.

2.3 Mixed Divisible and Indivisible Goods

We now introduce a fair division model with both divisible and indivisible goods (henceforth mixed goods for short). In the mixed-goods setting, resource R consists of a cake D = [0, 1] and a set of indivisible goods O = [m]. Each agent i N has a density function fi over the cake as defined in Section 2.1 and an additive utility function ui over indivisible goods O. Denote by A = (A1, A2, . . . , An) the allocation of mixed goods, where Ai = Di Oi is the bundle allocated to agent i. Agent i s utility is defined as ui(Ai) := ui(Di) + ui(Oi). Further discussion about the model, including the definitions of fairness notions and other extensions, is provided in Section 5.

3. Solution Concepts

Before introducing fairness concepts considered in this survey, we first define Pareto optimality, an economic efficiency notion that is fundamental in the context of fair division.

Definition 3.1 (PO). Given an allocation A = (Ai)i N, another allocation A = (A i)i N is said to be a Pareto improvement if ui(A i) ui(Ai) for all i N and uj(A j) > uj(Aj) for some j N. Alternatively, we say that A is Pareto dominated by A . An allocation is said to satisfy Pareto optimality (PO) if it does not admit a Pareto improvement.

In what follows, we first introduce comparison-based fairness notions (i.e., envy-freeness relaxations) in Section 3.1, followed by fair-share-based notions (e.g., proportionality and maximin share guarantee) in Sections 3.2 and 3.3.

3.1 (Approximate) Envy-Freeness

Envy-freeness the epitome of fairness, as Procaccia (2020) put it requires that every agent likes her own bundle at least as much as the bundle given to any other agent.

Definition 3.2 (EF (Tinbergen, 1930; Foley, 1967; Varian, 1974)3). An allocation A = (A1, A2, . . . , An) is said to satisfy envy-freeness (EF) if for any pair of agents i, j N, ui(Ai) ui(Aj).

In cake cutting, an envy-free cake division always exists (Su, 1999). This can also be seen from a result of Alon (1987). A k-partition (D1, D2, . . . , Dk) of cake D is said to be perfect if each agent i N values all pieces equally, that is, ui(Dj) = ui(D)

k for all i N and j [k]. Alon (1987) showed that a perfect partition of the cake always exists for any set of agents and any k N. It implies that an envy-free cake division always exists. An envy-free allocation need not exist when allocating indivisible items. To circumvent this issue, relaxations of envy-freeness have been proposed and studied.

3. We refer the interested readers to the paper of Heilmann and Wintein (2021) for more discussion on the work of Tinbergen (1930).

Mixed Fair Division: A Survey

Definition 3.3 (EF1 (Lipton et al., 2004; Budish, 2011; Aziz et al., 2022)). An allocation (O1, O2, . . . , On) of indivisible items O is said to satisfy envy-freeness up to one item (EF1) if for every pair of agents i, j N, either

there exists O Oj with |O | 1 such that ui(Oi) ui(Oj \ O ), or

there exists O Oi with |O | 1 such that ui(Oi \ O ) ui(Oj).

Intuitively, EF1 requires that when agent i envies agent j, the envy can be eliminated by either removing some good (in agent i s view) from agent j s bundle or removing some chore (again, in agent i s view) from agent i s own bundle. We will introduce a stronger notion than EF1. Before that, we first restrict ourselves to the indivisible-goods setting and strengthen EF1 in the following sense: any envy should be eliminated even if we remove the least (positively) valued good from the envied bundle.

Definition 3.4 (EFX0 and EFX for indivisible goods4 (Caragiannis et al., 2019; Plaut & Roughgarden, 2020)). An indivisible-goods allocation (O1, O2, . . . , On) is said to satisfy

envy-freeness up to any good (EFX0) if for any pair of agents i, j N and any good g Oj, ui(Oi) ui(Oj \ {g});

envy-freeness up to any positively valued good (EFX) if for any pair of agents i, j N and any good g Oj such that ui(g) > 0, we have ui(Oi) ui(Oj \ {g}).

EFX0 is a stronger variant than EFX, which in turn imposes a stronger requirement than EF1. For indivisible goods, an EFX0 (and hence EFX) allocation always exists for at most three agents (Akrami et al., 2023; Chaudhury et al., 2024; Plaut & Roughgarden, 2020), but the existence of EFX allocations remains open for four or more agents. EFX0, however, does not fare well with PO (Plaut & Roughgarden, 2020). We will also see such nuances and conflicts in Section 5 when introducing fairness notions in the mixed-goods setting. With mixed indivisible goods and chores, we define EFX as follows:

Definition 3.5 (EFX and EFX0 for indivisible goods and chores (Aziz et al., 2022; Aziz & Rey, 2020; Hosseini et al., 2023b)). An allocation (O1, O2, . . . , On) of indivisible goods and chores is said to satisfy

envy-freeness up to any item (EFX0) if for any pair of agents i, j N:

ui(Oi) ui(Oj \ {o}) for any o Gi Oj, and

ui(Oi \ {o}) ui(Oj) for any o Ci Oi;

envy-freeness up to any non-zero valued item (EFX) if for any pair of agents i, j N:

ui(Oi) ui(Oj \ {o}) for any o Gi Oj with ui(o) = 0, and

ui(Oi \ {o}) ui(Oj) for any o Ci Oi with ui(o) = 0.

4. The nomenclature of EFX0 and EFX is adopted from Kyropoulou et al. (2020).

Liu, Lu, Suzuki & Walsh

The envy relations between the agents in an allocation are commonly captured by the envy graph, in which the vertices correspond to the agents and there is a directed edge from one agent to another if the former agent envies the latter (Lipton et al., 2004). Variants of the envy graph and additional techniques are introduced in many other papers (e.g., Halpern & Shah, 2019; Bei et al., 2021; Bhaskar et al., 2021; Amanatidis et al., 2023). The following example demonstrates EF1, EFX, and EFX0 allocations.

Example 3.6. Consider an example with three agents and four items {o1, o2, o3, o4}. Agents valuations are listed below:

o1 o2 o3 o4

u1 1 1 2 2 u2 1 1 2 2 u3 1 0 2 1

Let us consider the following three allocations:

Agent 1 Agent 2 Agent 3

Allocation A {o2, o3} {o1} {o4} Allocation A {o1} {o2, o3} {o4} Allocation A {o1} {o3} {o2, o4}

Allocation A is EF1. It is not EFX, because, e.g., a2 still envies a1 when removing a2 s least preferred good from A1, i.e., u2(A2) = 1 < 2 = u2(A1 \ {o2}). Allocation A is EFX (and thus EF1). In particular, a3 s envy towards a2 can be eliminated by removing a3 s least positively valued good o3 from A 2, i.e., u3(A 3) = 1 u3(A 2 \ {o3}) = 0. It is not EFX0 because o2 is a3 s least valued good in A 2 but u3(A 3) = 1 < 2 = u3(A 2 \ {o2}). Allocation A is EFX0 (and hence EFX and EF1). This can be seen from the fact that

a1 does not envy a2 or a3, nor is envied by any agent;

a2 s envy towards a3 can be eliminated by removing a2 s least valuable good o2 from A 3;

a3 s envy towards a2 can be eliminated by removing a3 s least valuable good o3 from A 2.

We defer our discussion on relaxations of envy-freeness in the mixed-goods model to Section 5.1. It is worth noting that Bei et al. (2021) proposed a notion that naturally combines envy-freeness and EF1 together and is guaranteed to be satisfiable.

3.2 Proportionality

We now introduce fair-share-based notions. Our first fairness notion is proportionality, which requires that each agent receives value at least 1/n of her value for the entire set of resource R. For additive utilities, proportionality is weaker than envy-freeness.

Definition 3.7 (PROP (Steinhaus, 1948)). An allocation A = (Ai)i N is said to satisfy proportionality (PROP) if for every agent i N, ui(Ai) ui(R)

Mixed Fair Division: A Survey

A proportional cake division always exists (Steinhaus, 1948). This is not the case when allocating indivisible items. As a result, relaxations of proportionality have been studied. For instance, PROP1 defined below requires that each agent receives her proportional share by either obtaining an additional good (from other agents bundles) or removing some chore from her own bundle.

Definition 3.8 (PROP1 and PROPX (Aziz et al., 2022, 2020; Conitzer et al., 2017; Moulin, 2019)). An allocation (Oi)i N of indivisible goods and chores O is said to satisfy

proportionality up to one item (PROP1) if for each agent i N,

ui(Oi) ui(O)

ui(Oi {o}) ui(O)

n for some o O \ Oi, or

ui(Oi \ {o}) ui(O)

n for some o Oi;

proportionality up to any item (PROPX) if for each agent i N,

ui(Oi \ {o}) ui(O)

n for all o Oi with ui(o) < 0, and

ui(Oi {o}) ui(O)

n for all o O \ Oi with ui(o) > 0.

It follows from the definitions that PROP = PROPX = PROP1. With mixed indivisible goods and chores, EF1 implies PROP1 (Aziz et al., 2022). With only indivisible goods, EFX and PROPX are not comparable to each other. First, it can be seen from the following example that PROPX does not imply EFX. Consider two agents, two indivisible goods, and both agents value each good at 1. Allocating all goods to a single agent satisfies PROPX. The allocation, however, is not EFX because the empty-handed agent envies the other agent even if any good is removed from the latter agent s bundle. Next, EFX does not imply PROPX either. This can be seen from the fact that an EFX allocation of indivisible goods always exists for three agents (Chaudhury et al., 2024), but there exist three-agent instances in which PROPX allocations do not exist (Moulin, 2019; Aziz et al., 2020). On the contrary, with only indivisible chores, EFX implies PROPX (Aziz et al., 2024). Moreover, unlike the indivisible-goods setting, a PROPX allocation of indivisible chores always exist and can be computed efficiently (Moulin, 2019; Li et al., 2022; Aziz et al., 2024). Below, we demonstrate PROP, PROPX and PROP1 allocations.

Example 3.9. Consider the instance in Example 3.6. The proportional share of agent 1 (resp., 2 and 3) is 2 (resp., 2 and 4/3). Allocation ( , {o1, o2, o4}, {o3}) is proportional. Allocation ({o2, o3}, {o1}, {o4}) is PROPX but not proportional:

When removing agent 1 s most-valued chore o2 from her bundle, she reaches her proportional share of 2.

When adding agent 2 s least-valued good o2 / A2 to her bundle, she reaches her proportional share of 2.

When adding agent 3 s least-valued and positively-valued good o1 / A1, she reaches her proportional share of 4/3.

Allocation ({o3, o4}, {o1}, {o2}) is PROP1 but not PROPX. Note that agent 3 s bundle does not meet the PROPX criterion.

Liu, Lu, Suzuki & Walsh

3.3 Maximin Share Guarantee

Finally, we introduce another well-known fair-share-based notion called the maximin share (MMS) guarantee, and present below a unified definition working for mixed fair division settings. The MMS guarantee is inspired by generalizing the divide-and-choose procedure which produces an (almost) envy-free allocation with two agents (see, e.g., Budish, 2011).

Definition 3.10 (α-MMS (Budish, 2011; Kulkarni et al., 2021a; Bei et al., 2021a)). Let Πn(R) be the set of n-partitions of resource R. The maximin share (MMS) of agent i is defined as

MMSi(n, R) = max (P1,...,Pn) Πn(R) min j [n] ui(Pj).

Any partition for which this maximum is attained is called an MMS partition of agent i. We will simply refer to MMSi(n, R) as MMSi when the context of parameters is clear. An allocation A = (A1, A2, . . . , An) of resource R is said to satisfy the α-approximate maximin share guarantee (α-MMS), for some α (0, 1], if for every i N,

ui(Ai) min α MMSi(n, R), 1

α MMSi(n, R) .

That is, α-MMS requires that ui(Ai) α MMSi(n, R) when agent i has a non-negative maximin share (i.e., MMSi(n, R) 0) and ui(Ai) 1

α MMSi(n, R) when the agent has a negative maximin share (i.e., MMSi(n, R) < 0). When α = 1, we simply refer to 1-MMS as the MMS guarantee.

We use the following example to demonstrate agents MMS values (and their corresponding MMS partitions), as well as approximate-MMS allocations.

Example 3.11. Consider the instance in Example 3.6. Below, we list each agent s maximin share and their corresponding MMS partition:

MMS1 = 2, and ({o1, o2}, {o3}, {o4}) is the MMS partition of agent 1;

MMS2 = 2, and ({o1, o2}, {o3}, {o4}) is the MMS partition of agent 2;

MMS3 = 1, and ({o1}, {o2, o3}, {o4}) is an MMS partition of agent 3.

Consider allocations A, A and A specified in Example 3.6. Allocation A is 1

2-MMS but not (1

2 + ε)-MMS for any ε > 0, because each agent gets a utility of at least one half of their own MMS value and agent 2 gets a utility of exactly one half of her MMS value:

u1({o2, o3}) = 3 4 = min n 1 2 ( 2), 1 1/2 ( 2) o ;

u2({o1}) = 1 = min n 1 2 2, 1 1/2 2 o ;

u3({o4}) = 1 1

2 = min n 1 2 1, 1 1/2 1 o .

Similarly, it can be verified that both allocations A and A satisfy the MMS guarantee.

Mixed Fair Division: A Survey

If an α-MMS allocation is guaranteed to exist, an α-MMS and PO allocation always exists as well, because an α-MMS allocation which does not admit a Pareto improvement is PO. In fact, for a fair-share-based notion, a Pareto improvement preserves the fairness notion. Note, however, that it is co-NP-complete to decide whether a given allocation is PO (de Keijzer et al., 2009; Aziz et al., 2019). As we have seen in Definition 3.10, the (approximate) MMS guarantee can be naturally defined for settings involving indivisible goods and chores by letting R = O (Section 2.2) or mixed goods by letting R = D O (Section 2.3). We will discuss in Sections 4.2 and 5.2 the recent results on approximate MMS guarantee in respective settings.

4. Mixed Indivisible Goods and Chores

This section is concerned with the fair division of mixed indivisible goods and chores described in Section 2.2. We will discuss approximate envy-free allocations in Section 4.1, followed by discussions of MMS in Section 4.2.

4.1 Envy-freeness Relaxations

Chores might be viewed simply as negative goods. Ordinal methods for allocating goods can then be used directly by simply ordering chores after goods. However, certain properties are lost in such an approach. The fundamental problem is an asymmetry between goods and chores: an absence of goods is the worst possible outcome, but an absence of chores is the best possible outcome. We observe this (breakdown in) duality, for example, when allocating goods in a roundrobin fashion. The round-robin algorithm works by arranging the agents in an arbitrary order, and letting each agent in the order choose her favourite good from the remaining goods. With additive utilities, this is guaranteed to return an EF1 allocation (Caragiannis et al., 2019). The proof is simple. If Alice picks before Bob, then Alice can always pick a more valuable item to her than Bob next picks. But if Alice picks after Bob, we ignore the first item that Bob picks, and now the item that Alice picks is always more valuable to Alice than the next item picked by Bob. This argument breaks when we have both goods and chores, and the allocation returned may not be EF1.

Example 4.1 (The round-robin algorithm does not satisfy EF1 (Aziz et al., 2022)). Consider the following instance with two agents who have identical utilities over four items:

o1 o2 o3 o4

Alice, Bob: 2 3 3 3

Assume without loss of generality that Alice chooses first and Bob next. Then, Alice gets the positively valued good o1 and one chore (say, o3), whereas Bob gets the other two chores. As a result, Bob remains envious even if one item is removed from the bundles of Alice and Bob.

We can, however, modify the round-robin algorithm to ensure the allocation returned is EF1 for mixed indivisible goods and chores. At a high level, the double round-robin algorithm of Aziz et al. (2022) applies the round-robin algorithm twice as follows: Agents

Liu, Lu, Suzuki & Walsh

first pick objective chores in a round-robin fashion; we then reverse the picking order of the agents for the remaining items and let the agents take turns to pick their favourite good. We demonstrate the algorithm by applying it to Example 4.1. First, we introduce one dummy chore o where both Alice and Bob value o at 0 so that the number of objective chores is a multiple of the number of agents. Next, Alice and Bob pick those objective chores in a round-robin fashion Alice picks first, followed by Bob. Suppose the resulting partial allocation is ({o, o3}, {o2, o4}). Finally, we reverse the picking order, that is, now, Bob picks first his favourite good from the remaining items and Alice next. The resulting allocation is ({o, o3}, {o2, o4, o1}); one can verify that the allocation is EF1.

Theorem 4.2 (Aziz et al. (2022)). For additive utilities, the double round-robin algorithm returns an EF1 allocation in polynomial time.

In the indivisible-goods setting, another well-known method to compute an EF1 allocation (for any number of agents with arbitrary monotonic utilities) is the envy-cycle elimination algorithm of Lipton et al. (2004), which works by iteratively allocating a good to an agent who is not envied by anyone else. We can always find such an agent by resolving envy cycles in the underlying envy graph of the partial allocation. As observed in the work of Bérczi et al. (2020) and Bhaskar et al. (2021), however, a naive extension of the method to the indivisible-chores setting (even for agents with additive utilities) could fail to find an EF1 allocation if envy cycles are resolved in an arbitrary way, let alone for mixed indivisible goods and chores. Intuitively speaking, this is because even if an agent gets a better bundle when we resolve an envy cycle, the bundle may not contain a large enough chore whose removal eliminates the envy. Nevertheless, Bhaskar et al. (2021) introduced a key insight that we can always resolve the top-trading envy cycle, in which each agent only points to the agent she envies the most, and preserve EF1. Such an insight also works for doubly-monotonic instances.

Theorem 4.3 (Bhaskar et al. (2021)). For doubly-monotonic utilities, a modified top-trading envy-cycle elimination algorithm (see Bhaskar et al., 2021, Algorithm 3) computes an EF1 allocation.

Looking beyond additive utilities, Cousins et al. (2023) introduced the class of orderneutral submodular valuations, which relaxes the assumption that each item must be classified as a good or a chore (like the assumption in doubly-monotonic utility functions), but comes with a stronger restriction of submodularity. Further restricting the possible marginal values to 1, 0, and c (a positive integer), Cousins et al. (2023) showed that a leximin allocation5 can be computed efficiently; such an allocation, however, may not be EF1 even with two agents. For two agents with arbitrary utility functions over mixed indivisible goods and chores, Bérczi et al. (2020) devised a polynomial-time algorithm based on the envy graph that always computes an EF1 allocation.

Open Question 1. For three (or more) agents with arbitrary utility functions over mixed indivisible goods and chores, does there always exist an EF1 allocation? This question remains open even if agents have identical utility functions.

5. A leximin allocation is one that maximizes the minimum among the agents utilities; subject to this, it maximizes the second smallest utility, and so on.

Mixed Fair Division: A Survey

What about additionally demanding Pareto optimality? The double round-robin and the modified top-trading envy-cycle elimination methods return allocations that are EF1 but may not be PO. In the context of allocating goods alone and additive utilities, the maximum Nash welfare (MNW) allocation satisfies both EF1 and PO (Caragiannis et al., 2019).6 The question regarding whether an EF1 and PO allocation always exists for indivisible chores alone remains unresolved, except for the cases of up to three additive agents (Aziz et al., 2022; Garg et al., 2023),7 bi-valued instances (Ebadian et al., 2022; Garg et al., 2022), and two types of chores (Aziz et al., 2023a). For two agents with additive utilities over mixed indivisible goods and chores, Aziz et al. (2022) showed that an EF1 and PO allocation can always be found using a discrete version of the well-known Adjusted Winner (AW) rule (Brams & Taylor, 1996). A natural question is whether we can extend this to three (or more) agents.

Open Question 2. With mixed indivisible goods and chores, for three (or more) agents and additive utilities, does an EF1 and PO allocation always exist? Recall that this question remains open even in the indivisible-chores setting. If so, can we compute the allocation in polynomial time? Note that it remains unknown whether, in the indivisible-goods setting, an EF1 and PO allocation can be computed in polynomial time.

When weakening EF1 to PROP1, the existence and computation of a PROP1 and PO allocation has been resolved by Aziz et al. (2020), even if agents have unequal entitlements.8

Theorem 4.4 (Aziz et al. (2020)). For additive utilities over indivisible goods and chores, there exists a polynomial-time algorithm that always computes a PROP1 and PO allocation.

So far, we have been only concerned with notions of individual fairness. Inspired by the concept of group envy-freeness (GEF) (Berliant et al., 1992) a generalization of envyfreeness for equal-sized groups of agents,9 Aziz and Rey (2020) formalized relaxations of GEF for the case of mixed indivisible goods and chores. We include their up to one relaxation here. An allocation (Oi)i N of indivisible items O is said to satisfy GEF up to one item (GEF1) if for every non-empty groups of agents S, T N with |S| = |T| and every reallocation (Bi)i S of items S i T Oi among agents S, there exists an item oi (Oi Ci) (Bi Gi) for each i S such that (Bi \ {oi})i S does not Pareto dominate (Oi \ {oi})i S. Aziz and Rey (2020) devised polynomial-time algorithms to compute a GEF1 allocation when agents have identical utilities, or when agents have ternary symmetric utilities of the form { αi, 0, αi} for a given αi > 0.

6. With indivisible goods, an MNW allocation deals with the drowning by zero problem by first maximizing the number of agents receiving positive utilities, and then maximizing the product of these positive utilities. 7. Garg et al. (2023) s result holds for EF1 and f PO. An allocation is said to satisfy fractional Pareto optimality (f PO) if it is not Pareto dominated by any fractional allocation, in which an agent may receive a fractional share of an indivisible good (Barman et al., 2018). 8. We refer the interested readers to the recent review by Suksompong (2025), which discussed about fair division involving agents with unequal entitlements. 9. An allocation (Ai)i N is said to satisfy group envy-freeness (GEF) if for every non-empty groups of agents S, T N with |S| = |T|, there is no reallocation (Bi)i S of resources S

i T Ai among agents S such that for every i S, ui(Bi) ui(Ai), with one strict inequality.

Liu, Lu, Suzuki & Walsh

What if we consider a stronger fairness property like EFX? With additive utilities, EFX allocations do not always exist. This can be seen from an instance with a mixture of objective goods and chores and lexicographic preferences (Hosseini et al., 2023b).10 However, for special classes of indivisible goods and chores such as absolute identical utilities (i.e., for each item, the agents utilities have identical magnitudes but may have different signs), ternary utilities of the form {α, 0, β}, or separable lexicographic preferences (i.e., either chores are more important than goods or goods than chores), there exist polynomial-time algorithms that always return an EFX and PO allocation (Aleksandrov & Walsh, 2020; Hosseini et al., 2023a). With non-additive utilities, we refer interested readers to the work of Bérczi et al. (2020) for various ways of defining EFX and their (non-)existence results.

Open Question 3. Are there other natural subclasses of additive utilities over mixed indivisible goods and chores that always admit an EFX allocation? Or even an EFX and PO allocation?

We remark that the question is of interest even if we only consider indivisible goods or chores. It remains unknown whether there always exists an EFX allocation of indivisible goods (resp., chores) for at least four (resp., three) agents with additive valuations (Chaudhury et al., 2024; Christoforidis & Santorinaios, 2024; Zhou & Wu, 2024).

Given Definition 3.10, the most natural and intriguing question is whether an MMS allocation always exists. The seminal work of Kurokawa et al. (2018) showed that, with only indivisible goods, an MMS allocation may not exist when there are at least three agents, but 2

3-MMS can always be satisfied. Since then, many subsequent works have been carried out on improving the approximation ratio, designing simpler algorithms or giving simpler analyses, considering more general valuations, studying the indivisible-chores setting, etc. We refer interested readers to Section 5 of Amanatidis et al. (2023) and Section 7.1 of Guo et al. (2023) for a detailed account of recent developments on computing approximate-MMS allocations in the indivisible-goods and indivisible-chores settings, respectively. In what follows, we mainly focus on the developments in the setting where we allocate mixed indivisible goods and chores. We start by discussing about the computation of agents MMS values. It is well-known that an agent s maximin share is NP-hard to compute, even with only indivisible goods (see, e.g., Kurokawa et al., 2018). Nevertheless, with indivisible goods, there exists a polynomial-time approximation scheme (PTAS) to approximate each agent s maximin share (Woeginger, 1997). To be more precise, given a constant ε > 0, we can compute in polynomial time a partition (P1, P2, . . . , Pn) of the set of indivisible goods R for agent i such that min j [n] ui(Pj) (1 ε) MMSi(n, R).

10. Let L be set of all (strict and complete) linear orders over items O. Denote by := ( 1, 2, . . . , n) the importance profile that specifies for each agent i N an importance ordering i L over O. Given any two non-identical bundles X and Y , let z (X \ Y ) (Y \ X) be the most important item according to i. Lexicographic preferences say that agent i prefers bundle X over bundle Y if either z X Gi or z Y Ci. Lexicographic preferences can be seen a special case of additive utilities in which the magnitude of utilities grow exponentially in the importance ordering.

Mixed Fair Division: A Survey

Furthermore, there exist polynomial-time approximation schemes to approximate an agent s maximin share when allocating indivisible chores (e.g., Jansen et al., 2020), or mixed divisible and indivisible goods (Bei et al., 2021a). With mixed indivisible goods and chores, however, computing an approximate MMS value is more challenging. Kulkarni et al. (2021a) showed that it is NP-hard to approximate an agent s MMS value up to any approximation factor in (0, 1]. Intuitively speaking, the bottleneck is that the absolute value of MMS can be arbitrarily small (or, in other words, an MMS value can be arbitrarily close to 0). Kulkarni et al. (2021b) later gave a PTAS to compute an agent s MMS value when its absolute value is at least 1/p times either the total value of all the goods or total cost of all the chores, for some constant p greater than 1. We now discuss to what extent we can compute an approximate-MMS allocation. Note that in both indivisible-goods and indivisible-chores settings, a constant approximation exists.11 In contrast, with mixed indivisible goods and chores, for any fixed α (0, 1], an α-MMS allocation may not exist (Kulkarni et al., 2021a). And since the problem of finding an α-MMS allocation is NP-hard for any α (0, 1], Kulkarni et al. (2021a) approached the problem by designing computationally efficient algorithms, which, given a mixed-items fair division instance and α, ε (0, 1], can compute an (α ε)-MMS allocation (in addition to being approximately PO) of the given instance, or report that no α-MMS allocation exists for the instance. Note that their algorithms hinge upon certain conditions regarding the instances and thus only work for a subclass of instances satisfying the specified conditions. Specifically, for the special case of a constant number of agents where the total value of goods is some factor away of the total absolute value of chores, Kulkarni et al. (2021a) gave a PTAS to find an (α ε)-MMS and γ-PO allocation when given ε, γ > 0, for the highest possible α (0, 1]. Along the way, they developed a novel approach of using an LP-rounding through envy-cycle elimination as a tool to ensure PO with α-MMS. The aforementioned works motivate the study of computing (approximate-)MMS (and possibly with PO) allocations if agents preferences are more restricted. To this end, given lexicographic preferences over mixed indivisible goods and chores, an MMS and PO allocation always exists and can be computed in polynomial time (Hosseini et al., 2023a, 2023b).

4.3 Further Work

Starting with the work of Bogomolnaia et al. (2017), a line of research has addressed the fair allocation of mixed homogeneous divisible goods and chores (Garg & Mc Glaughlin, 2020; Chaudhury et al., 2023; Garg et al., 2021), focusing on a central solution concept in economics called competitive equilibrium (Arrow & Debreu, 1954). Segal-Halevi (2018) considered the fair division of a heterogeneous divisible resource that contains both good parts and bad parts, and proved that a connected envy-free division of the resource always exists for three agents. Later, Meunier and Zerbib (2019) extended the existence of a connected envy-free division to the case where n is a prime number or n = 4.

11. The state-of-the-art approximation ratio is 3

4 + 3 3836 for goods due to Akrami and Garg (2024) and 11

13 for chores due to Huang and Segal-Halevi (2023). We remark that the factor of 11

13, instead of 13

11 in (Huang & Segal-Halevi, 2023), is due to the fact that we assume agents have non-positive values for chores while Huang and Segal-Halevi (2023) (and almost all of the works on approximate-MMS allocations of indivisible chores) assume (non-negative) cost functions for the agents.

Liu, Lu, Suzuki & Walsh

Such divisible allocations of goods and chores might be adapted into randomized algorithms for indivisible goods and chores. This then naturally suggests another interesting direction for future study: algorithm design for mixed indivisible goods and chores with good ex-ante and ex-post properties. Such a best-of-both-worlds perspective has recently been receiving attention when allocating indivisible goods (Akrami et al., 2024, 2023; Aziz et al., 2023a, 2023b; Babaioff et al., 2022; Feldman et al., 2024; Hoefer et al., 2023) and in collective choice contexts (Aziz et al., 2023b, 2024; Suzuki & Vollen, 2024).

Open Question 4. Can we obtain a randomized allocation of mixed indivisible goods and chores which has good (exact) fairness ex ante from which we can construct integral allocations with good (approximate) fairness ex post?

We conclude this section by pointing out studies which generalize the mixed indivisible goods and chores setting. For instance, Caragiannis and Narang (2024) studied a repeated matching setting where a set of items is matched to the same set of agents repeatedly over multiple rounds. In their model, each agent gets exactly one item per round, and her value for the item depends on how many times she has matched to the item in the previous rounds and can be positive, zero or negative. Among other results, Caragiannis and Narang (2024) showed that with mixed items, a matching that is envy-free up to one swap exists for identical agents and in several other special cases if agents have heterogeneous valuations. In this survey, we assume that agents have preferences over the items, but not the other way around. Igarashi et al. (2023) studied a fair division setting with two-sided preferences (see also Freeman et al., 2021a), that is, additionally, the items also have preferences over the agents. They focused on guaranteeing EF1 for the agents together with a stability condition for both sides. Some of their results allow the utilities to be either positive or negative. Again, we assume in this survey that agents only derive utilities from their own received items. Other work (such as Brânzei et al., 2013; Li et al., 2015; Seddighin et al., 2021; Aziz et al., 2023) have considered fair division with externalities in which each agent also receives (positive or negative) utilities from items that are assigned to other agents.

5. Mixed Divisible and Indivisible Goods

This section is concerned with the fair division of mixed divisible and indivisible goods described in Section 2.3. We will first focus on how to obtain approximately envy-free allocations in Section 5.1 and next turn our attention to allocations guaranteeing agents their fair share (depending on how we define it) in Section 5.2.

5.1 Envy-freeness Relaxations

When allocating mixed goods, Bei et al. (2021) proposed the following fairness concept called envy-freeness for mixed goods that naturally generalizes envy-freeness and EF1 to the mixed-goods model and is guaranteed to exist.

Definition 5.1 (EFM0 (Bei et al., 2021, Definition 2.3)). An allocation A = (Ai)i N of mixed goods R = D O is said to satisfy envy-freeness for mixed goods (EFM0) if for any pair of agents i, j N,

Mixed Fair Division: A Survey

if agent j s bundle Aj consists of only indivisible goods, there exists some good g Aj such that ui(Ai) ui(Aj \ {g});

otherwise, ui(Ai) ui(Aj).

At a high level, EFM0 requires that an agent is envy-free towards any agent whose bundle contains a positive amount of divisible resources and EF1 towards the rest. It can be verified that with only divisible (resp., indivisible) goods, EFM0 reduces to envy-freeness (resp., EF1). Moreover, an EFM0 allocation of mixed goods always exists.

Theorem 5.2 (Bei et al. (2021)). An EFM0 allocation of mixed goods always exists for any number of agents and can be found in polynomial time with polynomially many Robertson Webb queries and calls to an oracle which could return a perfect partition of a cake.

The high-level algorithmic idea to compute an EFM0 allocation is as follows:

We start with an EF1 allocation of the indivisible items. The partial allocation is therefore EFM0. (The EFM0 property will be an invariant of the algorithm.)

Next, we construct an envy graph (N, Eenvy Eeq) for the partial allocation, where each vertex in the envy graph corresponds to an agent, and Eenvy and Eeq consist of the following two types of edges, respectively:

if ui(Ai) < ui(Aj), we establish an envy edge from i to j, i.e., (i, j) Eenvy;

if ui(Ai) = ui(Aj), we establish an equality edge from i to j, i.e., (i, j) Eeq.

A cycle in an envy graph is called an envy cycle if it contains at least one envy edge. Given an envy graph, a non-empty subset of agents S N forms an addable set if

there is no envy edge between any pair of agents in S;

there is no edge from any agent in N \ S to any agent in S.

Then, we identify a maximal addable set among whom we divide some divisible resources using a perfect allocation (Alon, 1987) we ensure that the EFM0 property is still preserved. Along the way, in order to identify an addable set, we may need to rotate bundles of the agents involved in an envy cycle. This step is repeated until we allocate all divisible resources.

A challenge is that the perfect allocation cannot be implemented with a finite number of queries in the RW query model, even if there are only two agents (Robertson & Webb, 1998). Nevertheless, an EFM0 (and hence EFM) allocation can be computed efficiently for two agents with general additive valuations and for n agents with piecewise linear density functions over the cake (Bei et al., 2021).

Open Question 5. Does there exist a bounded or even finite protocol in the RW query model to compute an EFM allocation?

Liu, Lu, Suzuki & Walsh

Despite the strong fairness guarantee provided by EFM0, the notion is incompatible with PO (Bei et al., 2021, Example 6.3). The counter-example hinges on the fact that in an EFM0 allocation, agent i should not envy agent j if agent j s bundle contains any positive amount of the cake, although agent i may value the piece of cake at 0. In the original paper of Bei et al. (2021), the fairness criterion is simply called EFM; we rename it by following the nomenclature of Kyropoulou et al. (2020) for EFX0 and EFX (cf. Footnote 4). We let EFM be the shorthand for a more natural variant defined below.

Definition 5.3 (EFM (Bei et al., 2021, Definition 6.4)). An allocation A = (Ai)i N of mixed goods R = D O is said to satisfy weak envy-freeness for mixed goods (EFM) if for any pair of agents i, j N,

if agent j s bundle consists of indivisible goods with either no divisible good or divisible good that yields value 0 to agent i (i.e., ui(Dj) = 0), there exists an indivisible good g Aj such that ui(Ai) ui(Aj \ {g});

otherwise, ui(Ai) ui(Aj).

A strengthening of EFM0 is to incorporate the idea of being EFX0 when comparing to a bundle with only indivisible goods (see, e.g., Bei et al., 2021; Nishimura & Sumita, 2023).12 An allocation A = (A1, A2, . . . , An) of mixed goods R = D O is said to satisfy envy-freeness up to any good for mixed goods (EFXM) if for any pair of agents i, j N,

if agent j s bundle consists of only indivisible goods, ui(Ai) ui(Aj \ {g}) for any (indivisible) good g Aj;

otherwise, ui(Ai) ui(Aj).

It follows from the definitions that EF = EFXM = EFM0 = EFM. Given any mixed-goods instance, if an EFX0 allocation of indivisible goods exists, we can start with this EFX0 allocation, apply the rest of the above EFM0 algorithmic framework, and eventually compute an EFXM allocation of the mixed-goods instance. We demonstrate EFXM, EFM0 and EFM allocations below.

Example 5.4. Consider a mixed-good instance with three indivisible goods {g1, g2, g3}, one homogeneous divisible good D, two agents and their valuations as follows:

u1 2 1 1 0 u2 2 1 1 1

Let us consider the following three allocations:

Agent 1 Agent 2

Allocation A {g1, g2} {g3, D} Allocation A {g3, D} {g1, g2} Allocation A {g3} {g1, g2, D}

12. The notion can also be refined by using the EFX criterion (Definition 3.4). For the purpose of this survey, we do not explicitly give its definition here.

Mixed Fair Division: A Survey

Allocation A is EFXM (but not envy-free), because a2 envies a1, but the envy can be eliminated by removing a1 s least valued good (i.e., good g2) from a2 s bundle. Allocation A is EFM0 (but not EFXM), because

u1({g3, D}) = 1 u1({g1, g2} \ {g1}) (showing EFM0);

u1({g3, D}) = 1 < 2 = u1({g1, g2} \ {g2}) (failing EFXM).

Allocation A is not EFM0, because a2 s bundle contains divisible good D, yet still a1 envies a2. The allocation, however, is EFM. As a1 values the divisible good at 0, according to Definition 5.3, we only need to examine whether a1 s envy towards a2 can be eliminated by removing an indivisible good from a2 s bundle. And indeed this is the case since u1({g3}) = 1 = u1({g1, g2, D} \ {g1}).

We introduce here the two variants, EFM0 and EFM, as both notions have their own merits. On the one hand, EFM0 is conceptually easier to be strengthened or extended when considering more general settings, e.g., with non-additive utilities,13 and any existence result of EFM0 may still be carried over to EFM (if well-defined). On the other hand, EFM precludes the counter-intuitive incompatibility with PO (Bei et al., 2021, Example 6.3). However, EFM is incompatible with f PO (Bei et al., 2021). The compatibility between EFM and PO is still unresolved and is an very interesting open question.

Open Question 6. Are EFM and PO compatible?

Despite providing strong compatibility between PO and (approximate) envy-freeness, the maximum Nash welfare (MNW) allocation fails to guarantee a PO and EFM allocation given mixed goods (Bei et al., 2021). Nevertheless, Nishimura and Sumita (2023) provided a formal proof showing that an MNW allocation for mixed goods is PO and envy-free up to one indivisible good for mixed goods (EF1M) (Caragiannis et al., 2019), which is based on the idea of removing an indivisible good from an envied bundle to eliminate envy and is weaker than EFM. When restricting agents utilities to binary and linear, an MNW allocation is PO and EFXM (Nishimura & Sumita, 2023). Bertsimas et al. (2011) and Caragiannis et al. (2012) introduced independently the concept of price of fairness for quantifying the efficiency loss due to fairness requirements. Taking EFM0 as an example, the price of EFM0 is the worst-case ratio between the total utility under an (unconstrained) optimal allocation, and the total utility under an optimal EFM0 allocation. Since then, a series of follow-up research has provided tight (for two agents) or asymptotically tight (for n agents) bounds on the price of approximate-EF notions (like EF1, EFX0, EFM0 and EFXM) when agents have scaled (alternatively, normalized) or unscaled utilities (Barman et al., 2020; Bei et al., 2021b; Bu et al., 2023a; Li et al., 2024). Other questions concerning simultaneously fairness and economic efficiency, for example, maximizing social welfare within fair allocations (Aziz et al., 2023c; Bei et al., 2012; Bu et al., 2023a; Cohler et al., 2011; Sun et al., 2023), are equally relevant and worthy of exploration in mixed fair division settings. While Theorem 5.2 was presented in the context of additive utilities, neither the algorithm of Bei et al. (2021) nor its analysis hinges on the assumption of the utilities over

13. With indivisible items, Bérczi et al. (2020) already discussed several ways to extend EFX when agents have non-additive utilities.

Liu, Lu, Suzuki & Walsh

indivisible goods being additive. As a matter of fact, EFM0 (and hence EFM) can still always be satisfied even if agents have monotonic utilities over the indivisible goods, as long as (i) agents utilities over the divisible goods are additive and (ii) agents utilities across divisible and indivisible goods are additive. Below, we give two examples showing that if either condition (i) or (ii) is violated, an EFM allocation may not exist. Given an interval [a, b], denote its length as len([a, b]) = b a. Let b D be a piece of cake consisting of a set of intervals I b D. Then, len( b D) = P I I b D len(I) is the length of the piece of cake b D. Let ε be an arbitrarily small positive number.

Example 5.5. This example will show that an EFM allocation may not exist if agents utilities over divisible goods are not additive. Consider two agents dividing an indivisible good g and a divisible good D = [0, 1]. Both agents have identical utility function u, where u(g) = 1 and

2 + ε len( b D);

ε 2 if 0 < len( b D) < 1

2 + ε; 0 if len( b D) = 0.

We have u({g} b D) = u(g)+u( b D), i.e., agents utilities across divisible and indivisible goods are additive. Assume without loss of generality that agent 1 gets good g. We distinguish the following two cases and show that in either case, the allocation is not EFM.

2 + ε: Agent 2 has divisible good that is positively valued by agent 1; however, because u({g} D1) 1 + ε

2 < 1 + ε = u(D2), agent 1 envies agent 2.

len(D2) < 1

2 + ε: Agent 1 has divisible good that is positively valued by agent 2; however, because u(D2) ε

2 < 1 u({g} D1), agent 2 envies agent 1.

Example 5.6. This example will show that an EFM allocation may not exist if agents utilities across divisible and indivisible goods are not additive. Consider two agents dividing an indivisible good g and a homogeneous divisible good D = [0, 1]. They have identical utility function u where u(g) = 1

2 ε, u( b D) = len( b D), and

u({g} b D) =

( u(g) + u( b D) if len( b D) 1

2; max{u(g), u( b D)} if 0 len( b D) < 1

Assume without loss of generality that agent 1 gets good g. We distinguish the following two cases and show that in neither case, the allocation is EFM.

len(D2) > 1

2: Agent 2 has divisible good that is positively valued by agent 1; however, because u({g} D1) = max{u(g), u(D1)} < 1

2 < u(D2), agent 1 envies agent 2.

2: Agent 1 has divisible good that is positively valued by agent 2; however, because u(D2) 1

2 < 1 ε u({g} D1), agent 2 envies agent 1.

Bhaskar et al. (2021) studied an extension of the mixed-goods model as follows. In their mixed-resources model, the resource R consists of a set O = [m] of indivisible items as defined in Section 2.2 and a divisible resource [0, 1] which is either an objective divisible good

Mixed Fair Division: A Survey

(i.e., i N, fi : [0, 1] R 0) or an objective divisible chore (i.e., i N, fi : [0, 1] R 0), referred to as a bad cake by Bhaskar et al. (2021). An allocation of the mixed resources and agents utilities in the allocation are defined the same way as in Section 2.3. Bhaskar et al. extended the formulation of EFM as follows.

Definition 5.7 (EFM for mixed resources (Bhaskar et al., 2021)). In the mixed-resources model, an allocation A = (A1, A2, . . . , An) is said to satisfy envy-freeness for mixed resources (EFM) if for any pair of agents i, j N, either i does not envy j, that is, ui(Ai) ui(Aj), or all of the following hold:

ui(Di) 0, i.e., i does not have any bad cake,

ui(Dj) 0, i.e., j does not have any cake, and

o Oi Oj such that ui(Ai \ {o}) ui(Aj \ {o}).

Theorem 5.8 (Bhaskar et al. (2021)). An EFM allocation always exists when allocating mixed resources consisting of doubly-monotonic indivisible items and a divisible chore.

The algorithmic framework introduced earlier to obtain an EFM0 allocation does not seem to work when allocating indivisible chores and a cake (Bhaskar et al., 2021). In special cases where agents have identical rankings of the indivisible chores or m n + 1, Bhaskar et al. (2021) proved the existence of an EFM allocation.

Open Question 7. Does there always exist an EFM allocation when allocating indivisible chores and a cake?

An affirmative answer to the above question may pave the way for solving the existence of EFM in a more general setting where resource R consists of divisible and indivisible items, and each item, either divisible or indivisible, may be a good to some agents but a chore for others. As valuations are elicited from the agents, the power and limitations of truthful mechanisms in addition to being fair have been explored in a variety of resource allocation scenarios (see, e.g., Bei et al., 2024; Bogomolnaia & Moulin, 2004; Brandl et al., 2021; Freeman et al., 2021b; Freeman & Schmidt-Kraepelin, 2024; Friedman et al., 2019; Li et al., 2015; Viswanathan & Zick, 2023). Truthfulness (or strategyproofness) requires that it should be in every agent s best interest to report her true underlying preferences to the mechanism. For instance, in cake cutting, Chen et al. (2013) designed a truthful envy-free mechanism for agents with piecewise-uniform valuations when assuming free disposal, which means that the mechanism is allowed to throw away part of the resources at no cost. Bei et al. (2020) then removed the free disposal assumption and exhibited truthful envy-free cake cutting mechanisms for two agents with piecewise-uniform valuations as well as for multiple agents with more restricted classes of valuations. Bu et al. (2023b) later showed that for piecewiseconstant valuations, there does not exist a truthful proportional cake cutting mechanism. Moving to indivisible-goods setting, truthfulness and EF1 are incompatible for two agents with additive valuations (Amanatidis et al., 2017). Nevertheless, for binary additive valuations, Halpern et al. (2020) showed the MNW rule with lexicographic tie-breaking is EF1, PO and group strategyproof (no coalition of agents can misreport their preferences in a

Liu, Lu, Suzuki & Walsh

way that they all benefit). Concurrently and independently, for binary submodular (also known as matroid-rank) valuations, i.e., valuations are submodular functions with binary marginals, Babaioff et al. (2021) designed a mechanism that is truthful and returns an EF1 and PO allocation. Their mechanism was then proved to be group strategyproof by Barman and Verma (2022). Those results have also been generalized to the setting where agents have unequal entitlements (Suksompong & Teh, 2022, 2023). Regarding a mixture of both divisible and indivisible goods, Li et al. (2023) modelled the mixed goods as a set of indivisible goods together with a set of homogeneous divisible goods. While truthfulness and EFM are incompatible even if there are only two agents having additive utilities over a single indivisible good and a single divisible good, they designed truthful and EFM mechanisms in several special cases where the expressiveness of agents utilities are further restricted.

Open Question 8. An intriguing question left open in (Li et al., 2023) is to show the (in)compatibility between truthfulness and EFM when n 3 agents have binary additive utilities over an arbitrary number of indivisible and divisible goods.

We remark that as an EF1M allocation of mixed goods can be obtained by combining an EF1 allocation of the indivisible goods and an envy-free allocation of the divisible goods, a truthful EF1M mechanism can be obtained by combining a truthful EF1 mechanism (for indivisible goods) and a truthful envy-free mechanism (for divisible goods).

5.2 MMS and PROP-α

We have seen that the MMS guarantee has been extensively studied for indivisible items, and the notion is well-defined in the mixed-goods model, to which Bei et al. (2021a) extended the study of (approximate) MMS guarantee. Given a mixed-goods instance, let the MMS approximation guarantee of the instance denote the maximum value of α such that the instance admits an α-MMS allocation. Bei et al. (2021a) showed that the worst-case MMS approximation guarantee across all mixedgoods instances is the same as that across all indivisible-goods instances. It is not surprising as the non-existence of an MMS allocation only arises when the resources to be allocated become indivisible. This intuition, however, no longer holds for some specific instances. There exists some instance to which a small amount of divisible goods is added; the MMS approximation guarantee of the new instance strictly decreases. Concerning the existence and computation of approximate MMS allocations, Bei et al. (2021a) devised an algorithm that always produces an α-MMS allocation, where α monotonically increases in terms of the ratio between agents values for the entire divisible goods and their own maximin share.

Theorem 5.9 (Bei et al. (2021a)). Given any mixed-goods instance, an α-MMS allocation always exists, where

α = min 1, 1

2 + min i N

ui(D) 2(n 1) MMSi

And even though Bei et al. (2021a) discussed an approach to improve the approximation guarantee of their algorithm and can match the state-of-the-art approximation ratio of 3

Mixed Fair Division: A Survey

3 3836 for indivisible goods due to Akrami and Garg (2024), improving the ratio further is an interesting future work. They also discussed how to convert the algorithm into a polynomial-time algorithm at the cost of a small loss in the MMS approximation ratio. This is achieved by plugging in agents approximate MMS values. To be more specific, by using the PTAS of Woeginger (1997), Bei et al. (2021a) designed a new PTAS that, given a constant ε > 0, can compute a partition (Pi)i [n] of mixed goods R for agent i in polynomial time, such that

min j [n] ui(Pj) (1 ε) MMSi(n, R).

Recently, Li et al. (2024) introduced another share-based fairness notion called proportionality up to α-fraction of one good (PROP-α), which generalizes proportionality and PROP1 to the mixed-good setting. The core idea behind PROP-α is to refine PROP1 by quantifying the contribution of divisible goods to achieving fairness. Following this highlevel idea, PROP-α directly strengthens the up to one relaxation to the up to a fraction , where the specific fraction depends on the proportion of indivisible goods relative to all goods. Intuitively, an agent may desire fairer allocations when share of divisible goods is more valuable. The formal definition of PROP-α can be found as follows.

Definition 5.10 (PROP-α (Li et al., 2024)). An allocation (Ai)i N of mixed goods R = D O is said to satisfy proportionality up to α-fraction of one good (PROP-α) if for any agent i N, there exists an indivisible good g O \Ai such that ui(Ai)+αi ui(g) ui(R)

n , where the indivisibility ratio αi for agent i is defined as αi := ui(O)

We can see from the above definition that the indivisibility ratio of an agent is smaller if she has a higher utility for the divisible goods. This, in turn, implies that she is more likely to receive an allocation closer to proportionality. One can also easily verify that PROP-α reduces to proportionality (resp., PROP1) if the resource consists of only divisible goods (resp., indivisible goods). Furthermore, a PROP-α allocation can be efficiently computed, and a PROP-α and PO allocation always exists.

Theorem 5.11 (Li et al. (2024)). Given any mixed-goods instance, a PROP-α allocation can be computed in polynomial time with polynomially many Robertson-Webb queries, and a PROP-α and PO allocation always exists via the maximum Nash welfare allocation.

Li et al. (2024) also explored the tight connection between EFM (Definition 5.3) and PROP-α (Definition 5.10): EFM = PROP-α. Specifically, they showed that an EFM allocation is PROP-α, but for any ϵ > 0, an EFM allocation may not be PROP-(1 ϵ)α. Here, PROP-(1 ϵ)α is defined similarly to Definition 5.10, except that α-fraction of one good is replaced with (1 ϵ)α-fraction of one good. We remark that although PROP-α is a weaker fairness notion than EFM, it offers several advantages. First, an allocation satisfying PROP-α can be efficiently found, while efficiently computing an EFM allocation remains an open question (see Open Question 5). Second, PROP-α is compatible with PO, while it is an open question that whether EFM and PO are compatible (see Open Question 6).

To conclude, the mixed-goods (or mixed-resources) model is rich and opens up new research directions that deserve further studies. For instance, going beyond EFM and MMS,

Liu, Lu, Suzuki & Walsh

can we define and study other meaningful fairness notions in the mixed-goods (or resources) model? To this end, Kawase et al. (2024b) studied fair mixed-goods allocations whose utility vectors minimize a symmetric strictly convex function. In a different direction, Bei et al. (2023) further extended the mixed-goods model by letting agents have their own subjective divisibility over the goods. That is, some agents may find a good to be indivisible and get utilities only if they receive the whole good, while other agents consider the same good as divisible and accumulate utilities in proportion to the fraction of the good they receive.

6. Indivisible Goods with Subsidy

In this section, we discuss how to allocate indivisible goods fairly through monetary compensation. As money can be thought of as a homogeneous divisible good, this setting fits into the framework of mixed-goods setting studied in Section 5. The key difference in this section is that we consider money as a tool to achieve envy-freeness rather than an exogenously given resource to be divided fairly. As envy-freeness the quintessential notion of fairness in fair division cannot be guaranteed when the goods are indivisible, many economists have attempted to circumvent this issue by introducing monetary compensation (Maskin, 1987; Klijn, 2000). However, earlier works in this line of research have mainly focused on the unit demand setting, wherein each agent is only interested in at most one good. The setting of arbitrary number of goods under general additive valuations was considered only recently by Halpern and Shah (2019). Let us first discuss what it means to be fair in the presence of monetary compensations (also called subsidy payments). We write p = (p1, p2, . . . , pn) Rn 0 as the vector of subsidy payments given to each agent, where pi denotes the subsidy payment given to agent i. The notion of envy-freeness with subsidy payment is defined as follows:

Definition 6.1. An allocation with payments (O, p) is envy-free if for any pair of agents i, j N, ui(Oi) + pi ui(Oj) + pj.

In other words, an allocation with payments is envy-free if every agent prefers their own bundle plus payment to the bundle plus payment of any other agent. It is important to note that not all allocations can be made envy-free by introducing payments. For example, consider an instance with two agents 1 and 2, a single good g, and u1(g) > u2(g). If the good is allocated to agent 2, then no subsidy payments (p1, p2) exist so that the resulting allocation with payments is envy-free. An allocation that can be made envy-free by introducing payments is called envy-freeable. Halpern and Shah (2019) showed the following characterization of envy-freeable allocations:

Theorem 6.2 (Halpern and Shah (2019)). The following statements are equivalent:

(i) The allocation O is envy-freeable.

(ii) The allocation O maximizes utilitarian welfare among all reassignments of the bundles, i.e., for every permutation σ of the agents, Pn i=1 ui(Oi) Pn i=1 ui(Oσ(i)).

(iii) The envy graph GO contains no positive-weight directed cycle.14

14. In (Halpern & Shah, 2019), given an allocation O, its envy graph GO is the complete weighted directed graph in which for each pair of agents i, j N, directed edge (i, j) has weight w(i, j) = ui(Oj) ui(Oi).

Mixed Fair Division: A Survey

An immediate consequence of Theorem 6.2 is that any allocation can be made envyfreeable by reassigning the bundles. Furthermore, Halpern and Shah (2019) showed that for a fixed envy-freeable allocation O, setting pi = ℓGO(i) not only makes (O, p) envy-free but also minimizes the total subsidy required for doing so. Here, ℓGO(i) denotes the maximum weight of any path starting from node i in GO. Considering budgetary limitations of the mechanism designer, it is natural to study how much subsidy payment is required to guarantee envy-freeness. Halpern and Shah (2019) conjectured that under additive valuations, subsidy of n 1 always suffices.15 Brustle et al. (2020) affirmatively settled this conjecture, where they showed an even stronger result:

Theorem 6.3 (Brustle et al. (2020)). For additive utilities, there exists a polynomial-time algorithm which outputs an envy-free allocation with subsidy (O, p) such that:

(i) Subsidy to each agent is at most one, i.e., pi 1.

(ii) Allocation O is EF1 and balanced (i.e., ||Oi| |Oj|| 1 for any i, j N).

Observe that Theorem 6.3 implies the conjecture of Halpern and Shah. This is because if a subsidy payment eliminates envy, then these payments can be uniformly lowered while maintaining envy-freeness. Hence, there is at least one agent who gets zero subsidy, which makes the total subsidy at most n 1. Furthermore, the bound of n 1 on the subsidy required to guarantee the existence of envy-free allocations is tight. To see this, consider an instance with a single good and n agents who all value the good at 1. For this instance, any envy-free allocation with subsidy must have a total subsidy of at least n 1. The subsidy needed to guarantee envy-freeness is much less understood for valuation classes that are beyond additive. Brustle et al. (2020) showed that for monotone valuations, a total subsidy of 2(n 1)2 suffices to guarantee envy-free allocations. Subsequently, Kawase et al. (2024a) improved this bound to n2 n 1

2 .16 As there are no lower bounds known beyond the aforementioned n 1 bound, this leads to a natural question.

Open Question 9. For monotonic utilities, does there exist an envy-free allocation whose total subsidy is O(n2 ϵ) for some ϵ > 0?

There has been progress made towards the above problem in restricted domains. Goko et al. (2024) showed that when the valuation functions are submodular functions with binary marginals (i.e., matroid-rank valuations), a total subsidy of n 1 suffices. Their mechanism additionally satisfies truthfulness. In a subsequent work, Barman et al. (2022) showed that for general set valuations with binary marginals total subsidy payment of n 1 suffices. A natural and closely related direction is to study the optimization problem of computing an allocation using minimum total subsidy that achieves envy-freeness. This problem is NP-hard since deciding whether an envy-free allocation exists for a given fair division instance is NP-hard. The same argument shows that it is NP-hard to approximate the minimum subsidy to any multiplicative factor. As a result, existing works have focused on additive approximation algorithms. Caragiannis and Ioannidis (2021) showed that for

15. Each good is worth at most 1 for every agent. This is achieved without loss of generality through a scaling argument. Without scaling, the bound becomes (n 1) maxi N,g O ui(g). 16. Kawase et al. (2024a) s result works for doubly-monotonic utilities.

Liu, Lu, Suzuki & Walsh

constant number of agents, an ε additive approximation algorithm can be computed in time polynomial in the number of goods and 1/ε. Furthermore, they showed that when the number of agents is part of the input, the problem is hard to approximate to within an additive factor of c P i N ui(O) for some small constant c. Subsidy payments can also be studied for fairness notions other than envy-freeness. In a recent work, Wu et al. (2023) initiated the study of the minimum subsidy needed to guarantee the existence of a proportional allocation.17 They showed that a total subsidy of n/4 suffices proportionality, in contrast to the n 1 subsidy needed for envy-freeness. In a subsequent work, Wu and Zhou (2024) strengthened the subsidy bounds needed to guarantee the existence of a weighted proportional allocation. It should be noted that there are multiple ways of defining share-based notions of fairness in the presence of subsidy, and they differ from each other in subtle ways. Wu et al. (2023) defined proportionality as ui(Oi) + pi ui(O)

n for each agent i N. Here, the total subsidy is not included in the proportional share of an agent. Another possible way is to consider both the divisible good (total subsidy) and the indivisible good in the definition of proportional share, under which proportionality is defined as ui(Oi) + pi 1

n(ui(O) + P j N pj) for each agent i N. In the latter definition of proportionality, it can be seen that subsidy of n 1 is needed to guarantee the existence. Exploring other fairness notions (e.g., MMS and Any Price share (Babaioff et al., 2021)) using subsidy payments is an intriguing direction for future research. For a mechanism to utilize subsidy payments, it is necessary for the mechanism to possess sufficient funds to disburse such subsidies. In many settings, however, the mechanism may not have access to adequate funds, making it difficult to implement. Such an issue can be circumvented if we allow for negative payments and additionally require P i N pi = 0. These types of payments are referred to as transfer payments. It can be seen that subsidy payments and transfer payments are interchangeable since whenever there is an envy-free allocation with subsidies, subtracting the average subsidy from each agent s individual payment results in payments that sum to zero and remains envy-free. Narayan et al. (2021) studied whether transfer payments can be used to achieve both fairness and efficiency.18 They showed that, for general monotone valuations, there exists an envy-free allocation with transfer payments whose Nash social welfare is at least e 1

e -fraction of the optimal Nash social welfare. As for utilitarian social welfare, they give algorithms to compute an envy-free allocation with transfers that achieves a prescribed target welfare with a near-optimal bound on the amount of total transfer payments P i N |pi| needed. In a related work, Aziz (2021) showed that transfer payments can be used to give an allocation that is both envy-free and equitable provided that the valuation function is supermodular. He also studied various axiomatic properties of allocations that can be made both envy-free and equitable. As seen from this section, by introducing a small amount of subsidy (or transfer) payments, one can achieve stronger fairness guarantees that are not possible otherwise in the indivisible items setting. It is an interesting avenue of research to explore different settings for which subsidy payments can be helpful. For instance, we may consider the indivisible items setting with externalities, where the value that an agent has for an allocation depends

17. Wu et al. (2023) s work mainly focused on chores; however, they also show that their subsidy bounds also hold for goods as well. 18. Transfer payments are better suited for studying welfare notions because they do not alter the social welfare of an allocation.

Mixed Fair Division: A Survey

not only on their own bundle but also on the bundles allocated to everyone else. Can subsidy payments be used to find fair allocations for problems with externalities?

7. Conclusion

In this survey, we have discussed several mixed fair division settings that generalize classical models in different ways, capture various realistic aspects of real-world scenarios, require non-trivial examinations of appropriate and attracting fairness concepts, and open up opportunities for a number of intriguing technical questions. As we have seen in Sections 5 and 6, divisible resources to some extent help achieve stronger fairness properties. In a similar vein, Sections 4 and 5 demonstrate that approximate fairness can still be achieved with mixed types of resources. However, simultaneously achieving approximate envy-freeness and PO is a challenging problem in both mixed fair division settings, in contrast to, e.g., the classic setting with indivisible goods. In addition to open questions outlined already, we present some other interesting directions below. One direction is to allow practical allocation constraints; we refer interested readers to the recent survey of Suksompong (2021). Going beyond the context of dividing resources among agents, the idea of combining mixed types of resources has been investigated in a collective choice context (Lu et al., 2024), where all agents share a selected subset of the resources. Extending the idea further to more general settings of allocating public resources (see, e.g., Aziz & Shah, 2021; Rey & Maly, 2023, on participatory budgeting), or even to public decision making (Conitzer et al., 2017; Skowron & Górecki, 2022) is an interesting and practical direction.

Acknowledgments

A preliminary version of this survey appeared as (Liu et al., 2024). We would like to thank Ayumi Igarashi, Conrad Heilmann, Hadi Hosseini, Bo Li, Warut Suksompong, Rohit Vaish, Xiaowei Wu, and the anonymous reviewers for helpful comments and valuable feedback. This work was partially supported by ARC Laureate Project FL200100204 on Trustworthy AI , by the National Natural Science Foundation of China (Grant No. 62102117), by the Shenzhen Science and Technology Program (Grant Nos. RCBS20210609103900003 and GXWD20231129111306002), by the Guangdong Basic and Applied Basic Research Foundation (Grant No. 2023A1515011188), and by the CCF-Huawei Populus Grove Fund (Grant No. CCF-Huawei LK2022005).

Akrami, H., Alon, N., Chaudhury, B. R., Garg, J., Mehlhorn, K., & Mehta, R. (2023). EFX: A simpler approach and an (almost) optimal guarantee via rainbow cycle number. In Proceedings of the 24th ACM Conference on Economics and Computation (EC), p. 61.

Akrami, H., & Garg, J. (2024). Breaking the 3/4 barrier for approximate maximin share. In Proceedings of the 35th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 74 91.

Liu, Lu, Suzuki & Walsh

Akrami, H., Garg, J., Sharma, E., & Taki, S. (2024). Improving approximation guarantees for maximin share. In Proceedings of the 25th ACM Conference on Economics and Computation (EC). Forthcoming.

Akrami, H., Mehlhorn, K., Seddighin, M., & Shahkarami, G. (2023). Randomized and deterministic maximin-share approximations for fractionally subadditive valuations. In Proceedings of the 37th Annual Conference on Neural Information Processing Systems (Neur IPS), pp. 58821 58832.

Aleksandrov, M., & Walsh, T. (2020). Two algorithms for additive and fair division of mixed manna. In Proceedings of the 43rd German Conference on Artificial Intelligence (KI), pp. 3 17.

Alon, N. (1987). Splitting necklaces. Advances in Mathematics, 63(3), 247 253.

Amanatidis, G., Aziz, H., Birmpas, G., Filos-Ratsikas, A., Li, B., Moulin, H., Voudouris, A. A., & Wu, X. (2023). Fair division of indivisible goods: Recent progress and open questions. Artificial Intelligence, 322, 103965.

Amanatidis, G., Birmpas, G., Christodoulou, G., & Markakis, E. (2017). Truthful allocation mechanisms without payments: Characterization and implications on fairness. In Proceedings of the 18th ACM Conference on Economics and Computation (EC), pp. 545 562.

Arrow, K. J., & Debreu, G. (1954). Existence of an equilibrium for a competitive economy. Econometrica, 22(3), 265 290.

Aziz, H. (2020). Developments in multi-agent fair allocation. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pp. 13563 13568.

Aziz, H. (2021). Achieving envy-freeness and equitability with monetary transfers. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pp. 5102 5109.

Aziz, H., Biró, P., Lang, J., Lesca, J., & Monnot, J. (2019). Efficient reallocation under additive and responsive preferences. Theoretical Computer Science, 790, 1 15.

Aziz, H., Caragiannis, I., Igarashi, A., & Walsh, T. (2022). Fair allocation of indivisible goods and chores. Autonomous Agents and Multi-Agent Systems, 36(1), 3:1 3:21.

Aziz, H., Freeman, R., Shah, N., & Vaish, R. (2023a). Best of both worlds: Ex-ante and ex-post fairness in resource allocation. Operations Research. Forthcoming.

Aziz, H., Ganguly, A., & Micha, E. (2023b). Best of both worlds fairness under entitlements. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 941 948.

Aziz, H., Huang, X., Mattei, N., & Segal-Halevi, E. (2023c). Computing welfare-maximizing fair allocations of indivisible goods. European Journal of Operational Research, 307(2), 773 784.

Aziz, H., Li, B., Moulin, H., Wu, X., & Zhu, X. (2024). Almost proportional allocations of indivisible chores: Computation, approximation and efficiency. Artificial Intelligence, 331, 104118.

Mixed Fair Division: A Survey

Aziz, H., Lindsay, J., Ritossa, A., & Suzuki, M. (2023a). Fair allocation of two types of chores. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 143 151.

Aziz, H., Lu, X., Suzuki, M., Vollen, J., & Walsh, T. (2023b). Best-of-both-worlds fairness in committee voting. In Proceedings of the 19th Conference on Web and Internet Economics (WINE), p. 676.

Aziz, H., Lu, X., Suzuki, M., Vollen, J., & Walsh, T. (2024). Fair lotteries for participatory budgeting. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pp. 9469 9476.

Aziz, H., Moulin, H., & Sandomirskiy, F. (2020). A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation. Operations Research Letters, 48(5), 573 578.

Aziz, H., & Rey, S. (2020). Almost group envy-free allocation of indivisible goods and chores. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), pp. 39 45.

Aziz, H., & Shah, N. (2021). Participatory budgeting: Models and approaches. In Rudas, T., & Péli, G. (Eds.), Pathways Between Social Science and Computational Social Science: Theories, Methods, and Interpretations, pp. 215 236. Springer International Publishing.

Aziz, H., Suksompong, W., Sun, Z., & Walsh, T. (2023). Fairness concepts for indivisible items with externalities. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), pp. 5472 5480.

Babaioff, M., Ezra, T., & Feige, U. (2021). Fair and truthful mechanisms for dichotomous valuations. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pp. 5119 5126.

Babaioff, M., Ezra, T., & Feige, U. (2022). On best-of-both-worlds fair-share allocations. In Proceedings of the 18th Conference on Web and Internet Economics (WINE), pp. 237 255.

Barman, S., Bhaskar, U., & Shah, N. (2020). Optimal bounds on the price of fairness for indivisible goods. In Proceedings of the 16th International Conference on Web and Internet Economics (WINE), pp. 356 369.

Barman, S., Krishna, A., Narahari, Y., & Sadhukhan, S. (2022). Achieving envy-freeness with limited subsidies under dichotomous valuations. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), pp. 60 66.

Barman, S., Krishnamurthy, S. K., & Vaish, R. (2018). Finding fair and efficient allocations. In Proceedings of the 19th ACM Conference on Economics and Computation (EC), pp. 557 574.

Barman, S., & Verma, P. (2022). Truthful and fair mechanisms for matroid-rank valuations. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pp. 4801 4808.

Liu, Lu, Suzuki & Walsh

Bei, X., Chen, N., Hua, X., Tao, B., & Yang, E. (2012). Optimal proportional cake cutting with connected pieces. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI), pp. 1263 1269.

Bei, X., Huzhang, G., & Suksompong, W. (2020). Truthful fair division without free disposal. Social Choice and Welfare, 55, 523 545.

Bei, X., Li, Z., Liu, J., Liu, S., & Lu, X. (2021). Fair division of mixed divisible and indivisible goods. Artificial Intelligence, 293, 103436.

Bei, X., Liu, S., & Lu, X. (2023). Fair division with subjective divisibility. In Proceedings of the 19th Conference on Web and Internet Economics (WINE), p. 677.

Bei, X., Liu, S., Lu, X., & Wang, H. (2021a). Maximin fairness with mixed divisible and indivisible goods. Autonomous Agents and Multi-Agent Systems, 35(2), 34:1 34:21.

Bei, X., Lu, X., Manurangsi, P., & Suksompong, W. (2021b). The price of fairness for indivisible goods. Theory of Computing Systems, 65(7), 1069 1093.

Bei, X., Lu, X., & Suksompong, W. (2024). Truthful cake sharing. Social Choice and Welfare. Forthcoming.

Bérczi, K., Bérczi-Kovács, E. R., Boros, E., Gedefa, F. T., Kamiyama, N., Kavitha, T., Kobayashi, Y., & Makino, K. (2020). Envy-free relaxations for goods, chores, and mixed items. Co RR, abs/2006.04428.

Berliant, M., Thomson, W., & Dunz, K. (1992). On the fair division of a heterogeneous commodity. Journal of Mathematical Economics, 21(3), 201 216.

Bertsimas, D., Farias, V. F., & Trichakis, N. (2011). The price of fairness. Operations Research, 59(1), 17 31.

Bhaskar, U., Sricharan, A. R., & Vaish, R. (2021). On approximate envy-freeness for indivisible chores and mixed resources. In Proceedings of the 24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pp. 1:1 1:23.

Bogomolnaia, A., & Moulin, H. (2004). Random matching under dichotomous preferences. Econometrica, 72(1), 257 279.

Bogomolnaia, A., Moulin, H., Sandomirskiy, F., & Yanovskaya, E. (2017). Competitive division of a mixed manna. Econometrica, 85(6), 1847 1871.

Brams, S. J., & Taylor, A. D. (1996). Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press.

Brandl, F., Brandt, F., Peters, D., & Stricker, C. (2021). Distribution rules under dichotomous preferences: Two out of three ain t bad. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC), pp. 158 179.

Brandt, F., Conitzer, V., Endriss, U., Lang, J., & Procaccia, A. D. (Eds.). (2016). Handbook of Computational Social Choice. Cambridge University Press.

Brânzei, S., Procaccia, A. D., & Zhang, J. (2013). Externalities in cake cutting. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI), pp. 55 61.

Mixed Fair Division: A Survey

Brustle, J., Dippel, J., Narayan, V. V., Suzuki, M., & Vetta, A. (2020). One dollar each eliminates envy. In Proceedings of the 21st ACM Conference on Economics and Computation (EC), pp. 23 39.

Bu, X., Li, Z., Liu, S., Song, J., & Tao, B. (2023a). On the complexity of maximizing social welfare within fair allocations of indivisible goods. Co RR, abs/2205.14296.

Bu, X., Song, J., & Tao, B. (2023b). On existence of truthful fair cake cutting mechanisms. Artificial Intelligence, 319, 103904.

Budish, E. (2011). The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6), 1061 1103.

Budish, E., Cachon, G. P., Kessler, J. B., & Othman, A. (2017). Course Match: A largescale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation. Operations Research, 65(2), 314 336.

Caragiannis, I., & Ioannidis, S. (2021). Computing envy-freeable allocations with limited subsidies. In Proceedings of the 17th International Conference on Web and Internet Economics (WINE), pp. 522 539.

Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., & Kyropoulou, M. (2012). The efficiency of fair division. Theory of Computing Systems, 50(4), 589 610.

Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A. D., Shah, N., & Wang, J. (2019). The unreasonable fairness of maximum Nash welfare. ACM Transactions on Economics and Computation, 7(3), 12:1 12:32.

Caragiannis, I., & Narang, S. (2024). Repeatedly matching items to agents fairly and efficiently. Theoretical Computer Science, 981, 114246.

Chaudhury, B. R., Garg, J., Mc Glaughlin, P., & Mehta, R. (2023). A complementary pivot algorithm for competitive allocation of a mixed manna. Mathematics of Operations Research, 48(3), 1630 1656.

Chaudhury, B. R., Garg, J., & Mehlhorn, K. (2024). EFX exists for three agents. Journal of the ACM, 71(1), 4:1 4:27.

Chen, Y., Lai, J. K., Parkes, D. C., & Procaccia, A. D. (2013). Truth, justice, and cake cutting. Games and Economic Behavior, 77(1), 284 297.

Christoforidis, V., & Santorinaios, C. (2024). On the pursuit of EFX for chores: Nonexistence and approximations. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI), pp. 2713 2721.

Cohler, Y. J., Lai, J. K., Parkes, D. C., & Procaccia, A. D. (2011). Optimal envy-free cake cutting. In Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI), pp. 626 631.

Conitzer, V., Freeman, R., & Shah, N. (2017). Fair public decision making. In Proceedings of the 18th ACM Conference on Economics and Computation (EC), pp. 629 646.

Cousins, C., Viswanathan, V., & Zick, Y. (2023). The good, the bad and the submodular: Fairly allocating mixed manna under order-neutral submodular preferences. In Proceedings of the 19th Conference on Web and Internet Economics (WINE), pp. 207 224.

Liu, Lu, Suzuki & Walsh

de Keijzer, B., Bouveret, S., Klos, T., & Zhang, Y. (2009). On the complexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences. In Proceedings of the 1st International Conference on Algorithmic Decision Theory (ADT), pp. 98 110.

Ebadian, S., Peters, D., & Shah, N. (2022). How to fairly allocate easy and difficult chores. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 372 380.

Endriss, U. (Ed.). (2017). Trends in Computational Social Choice. AI Access.

Feldman, M., Mauras, S., Narayan, V. V., & Ponitka, T. (2024). Breaking the envy cycle: Best-of-both-worlds guarantees for subadditive valuations. In Proceedings of the 25th ACM Conference on Economics and Computation (EC). Forthcoming.

Foley, D. K. (1967). Resource allocation and the public sector. Yale Economics Essays, 7(1), 45 98.

Freeman, R., Micha, E., & Shah, N. (2021a). Two-sided matching meets fair division. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pp. 203 209.

Freeman, R., Pennock, D. M., Peters, D., & Wortman Vaughan, J. (2021b). Truthful aggregation of budget proposals. Journal of Economic Theory, 193, 105234.

Freeman, R., & Schmidt-Kraepelin, U. (2024). Project-fair and truthful mechanisms for budget aggregation. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pp. 9704 9712.

Friedman, E. J., Gkatzelis, V., Psomas, C.-A., & Shenker, S. (2019). Fair and efficient memory sharing: Confronting free riders. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), pp. 1965 1972.

Garg, J., Hoefer, M., Mc Glaughlin, P., & Schmalhofer, M. (2021). When dividing mixed manna is easier than dividing goods: Competitive equilibria with a constant number of chores. In Proceedings of the 14th International Symposium on Algorithmic Game Theory (SAGT), pp. 329 344.

Garg, J., & Mc Glaughlin, P. (2020). Computing competitive equilibria with mixed manna. In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 420 428.

Garg, J., Murhekar, A., & Qin, J. (2022). Fair and efficient allocations of chores under bivalued preferences. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pp. 5043 5050.

Garg, J., Murhekar, A., & Qin, J. (2023). New algorithms for the fair and efficient allocation of indivisible chores. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), pp. 2710 2718.

Goko, H., Igarashi, A., Kawase, Y., Makino, K., Sumita, H., Tamura, A., Yokoi, Y., & Yokoo, M. (2024). A fair and truthful mechanism with limited subsidy. Games and Economic Behavior, 144, 49 70.

Mixed Fair Division: A Survey

Goldman, J., & Procaccia, A. D. (2015). Spliddit: Unleashing fair division algorithms. SIGecom Exchanges, 13(2), 41 46.

Guo, H., Li, W., & Deng, B. (2023). A survey on fair allocation of chores. Mathematics, 11(16), 3616.

Halpern, D., Procaccia, A. D., Psomas, A., & Shah, N. (2020). Fair division with binary valuations: One rule to rule them all. In Proceedings of the 16th International Conference on Web and Internet Economics (WINE), pp. 370 383.

Halpern, D., & Shah, N. (2019). Fair division with subsidy. In Proceedings of the 12th International Symposium on Algorithmic Game Theory (SAGT), pp. 374 389.

Han, J., & Suksompong, W. (2024). Fast & fair: A collaborative platform for fair division applications. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pp. 23796 23798. Demonstration Track.

Heilmann, C., & Wintein, S. (2021). No envy: Jan Tinbergen on fairness. Erasmus Journal for Philosophy and Economics, 14(1), 222 245.

Hoefer, M., Schmalhofer, M., & Varricchio, G. (2023). Best of both worlds: Agents with entitlements. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 564 572.

Hosseini, H., Mammadov, A., & Wąs, T. (2023a). Fairly allocating goods and (terrible) chores. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), pp. 2738 2746.

Hosseini, H., Sikdar, S., Vaish, R., & Xia, L. (2023b). Fairly dividing mixtures of goods and chores under lexicographic preferences. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 152 160.

Huang, X., & Segal-Halevi, E. (2023). A reduction from chores allocation to job scheduling. In Proceedings of the 24th ACM Conference on Economics and Computation (EC), p. 908.

Igarashi, A., Kawase, Y., Suksompong, W., & Sumita, H. (2023). Fair division with two-sided preferences. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), pp. 2756 2764.

Igarashi, A., & Yokoyama, T. (2023). Kajibuntan: A house chore division app. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), pp. 16449 16451. Demo Track.

Jansen, K., Klein, K.-M., & Verschae, J. (2020). Closing the gap for makespan scheduling via sparsification techniques. Mathematics of Operations Research, 45(4), 1371 1392.

Kawase, Y., Makino, K., Sumita, H., Tamura, A., & Yokoo, M. (2024a). Towards optimal subsidy bounds for envy-freeable allocations. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pp. 9824 9831.

Kawase, Y., Nishimura, K., & Sumita, H. (2024b). Minimizing symmetric convex functions over hybrid of continuous and discrete convex sets. In Proceedings of the 51st EATCS International Colloquium on Automata, Languages, and Programming (ICALP), pp. 96:1 96:19.

Liu, Lu, Suzuki & Walsh

Klijn, F. (2000). An algorithm for envy-free allocations in an economy with indivisible objects and money. Social Choice and Welfare, 17(2), 201 215.

Kulkarni, R., Mehta, R., & Taki, S. (2021a). Indivisible mixed manna: On the computability of MMS + PO allocations. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC), pp. 683 684.

Kulkarni, R., Mehta, R., & Taki, S. (2021b). On the PTAS for maximin shares in an indivisible mixed manna. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pp. 5523 5530.

Kurokawa, D., Procaccia, A. D., & Wang, J. (2018). Fair enough: Guaranteeing approximate maximin shares. Journal of the ACM, 65(2), 8:1 8:27.

Kyropoulou, M., Suksompong, W., & Voudouris, A. A. (2020). Almost envy-freeness in group resource allocation. Theoretical Computer Science, 841, 110 123.

Li, B., Li, Y., & Wu, X. (2022). Almost (weighted) proportional allocations for indivisible chores. In Proceedings of the 31st ACM Web Conference (The Web Conf), pp. 122 131.

Li, B., Li, Z., Liu, S., & Wu, Z. (2024). Allocating mixed goods with customized fairness and indivisibility ratio. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI), pp. 2868 2876.

Li, M., Zhang, J., & Zhang, Q. (2015). Truthful cake cutting mechanisms with externalities: Do not make them care for others too much!. In Proceedings of the 24th International Conference on Artificial Intelligence (IJCAI), pp. 589 595.

Li, Z., Liu, S., Lu, X., & Tao, B. (2023). Truthful fair mechanisms for allocating mixed divisible and indivisible goods. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), pp. 2808 2816.

Li, Z., Liu, S., Lu, X., Tao, B., & Tao, Y. (2024). A complete landscape for the price of envy-freeness. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 1183 1191.

Lindner, C., & Rothe, J. (2024). Cake-cutting: Fair division of divisible goods. In Rothe, J. (Ed.), Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division (2nd edition)., chap. 8, pp. 507 603. Springer Cham.

Lipton, R. J., Markakis, E., Mossel, E., & Saberi, A. (2004). On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce (EC), pp. 125 131.

Liu, S., Lu, X., Suzuki, M., & Walsh, T. (2024). Mixed fair division: A survey. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pp. 22641 22649. Senior Member Presentation Track.

Lu, X., Peters, J., Aziz, H., Bei, X., & Suksompong, W. (2024). Approval-based voting with mixed goods. Social Choice and Welfare, 62(4), 643 677.

Maskin, E. S. (1987). On the fair allocation of indivisible goods. In Feiwel, G. R. (Ed.), Proceedings of the Arrow and the Foundations of the Theory of Economic Policy, pp. 341 349. Palgrave Macmillan UK.

Mixed Fair Division: A Survey

Meunier, F., & Zerbib, S. (2019). Envy-free cake division without assuming the players prefer nonempty pieces. Israel Journal of Mathematics, 234(2), 907 925.

Moulin, H. (2019). Fair division in the internet age. Annual Review of Economics, 11(1), 407 441.

Narayan, V. V., Suzuki, M., & Vetta, A. (2021). Two birds with one stone: Fairness and welfare via transfers. In Proceedings of the 14th International Symposium on Algorithmic Game Theory (SAGT), pp. 376 390.

Nguyen, T. T., & Rothe, J. (2023). Complexity results and exact algorithms for fair division of indivisible items: A survey. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), pp. 6732 6740. Survey Track.

Nishimura, K., & Sumita, H. (2023). Envy-freeness and maximum Nash welfare for mixed divisible and indivisible goods. Co RR, abs/2302.13342.

Plaut, B., & Roughgarden, T. (2020). Almost envy-freeness with general valuations. SIAM Journal on Discrete Mathematics, 34(2), 1039 1068.

Procaccia, A. D. (2016). Cake cutting algorithms. In Brandt, F., Conitzer, V., Endriss, U., Lang, J., & Procaccia, A. D. (Eds.), Handbook of Computational Social Choice, chap. 13, pp. 311 329. Cambridge University Press.

Procaccia, A. D. (2020). An answer to fair division s most enigmatic question: Technical perspective. Communications of the ACM, 63(4), 118.

Rey, S., & Maly, J. (2023). The (computational) social choice take on indivisible participatory budgeting. Co RR, abs/2303.00621.

Robertson, J., & Webb, W. (1998). Cake-Cutting Algorithm: Be Fair If You Can. A K Peters/CRC Press.

Rothe, J. (Ed.). (2024). Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division (2nd edition). Springer Cham.

Seddighin, M., Saleh, H., & Ghodsi, M. (2021). Maximin share guarantee for goods with positive externalities. Social Choice and Welfare, 56(2), 291 324.

Segal-Halevi, E. (2018). Fairly dividing a cake after some parts were burnt in the oven. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 1276 1284.

Shah, N. (2017). Making the world fairer. XRDS: Crossroads, The ACM Magazine for Students, 24(1), 24 28.

Skowron, P., & Górecki, A. (2022). Proportional public decisions. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pp. 5191 5198.

Steinhaus, H. (1948). The problem of fair division. Econometrica, 16(1), 101 104.

Su, F. E. (1999). Rental harmony: Sperner s lemma in fair division. The American Mathematical Monthly, 106(10), 930 942.

Suksompong, W. (2021). Constraints in fair division. ACM SIGecom Exchanges, 19(2), 46 61.

Liu, Lu, Suzuki & Walsh

Suksompong, W. (2025). Weighted fair division of indivisible items: A review. Information Processing Letters, 187, 106519.

Suksompong, W., & Teh, N. (2022). On maximum weighted Nash welfare for binary valuations. Mathematical Social Sciences, 117, 101 108.

Suksompong, W., & Teh, N. (2023). Weighted fair division with matroid-rank valuations: Monotonicity and strategyproofness. Mathematical Social Sciences, 126, 48 59.

Sun, A., Chen, B., & Doan, X. V. (2023). Equitability and welfare maximization for allocating indivisible items. Autonomous Agents and Multi-Agent Systems, 37(1), 8:1 8:45.

Suzuki, M., & Vollen, J. (2024). Maximum flow is fair: A network flow approach to committee voting. In Proceedings of the 25th ACM Conference on Economics and Computation (EC). Forthcoming.

Tinbergen, J. (1930). Mathematiese psychologie. Mens en Maatschappij, 6(4), 342 352.

Varian, H. R. (1974). Equity, envy, and efficiency. Journal of Economic Theory, 9(1), 63 91.

Viswanathan, V., & Zick, Y. (2023). A general framework for fair allocation under matroid rank valuations. In Proceedings of the 24th ACM Conference on Economics and Computation (EC), pp. 1129 1152.

Walsh, T. (2020). Fair division: The computer scientist s perspective. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), pp. 4966 4972.

Woeginger, G. J. (1997). A polynomial-time approximation scheme for maximizing the minimum machine completion time. Operations Research Letters, 20(4), 149 154.

Wu, X., Zhang, C., & Zhou, S. (2023). One quarter each (on average) ensures proportionality. In Proceedings of the 19th Conference on Web and Internet Economics (WINE), pp. 582 599.

Wu, X., & Zhou, S. (2024). Tree splitting based rounding scheme for weighted proportional allocations with subsidy. Co RR, abs/2404.07707.

Zhou, S., & Wu, X. (2024). Approximately EFX allocations for indivisible chores. Artificial Intelligence, 326, 104037.