A Little Subsidy Ensures MMS Allocation for Three Agents

1 Introduction

Fair allocation of resources among diverse agents has been a popular problem across various disciplines since proposed in 1948 by Steinhaus [1948], encompassing social science, economics, and computer science. The allocation of items, whether goods that individuals desire or chores that they seek to avoid, requires intricate considerations to ensure fairness. Early studies on fair allocations, such as the renowned "Cake Cutting" problem, considered divisible resources, emphasizing fairness notions like envy-freeness: each agent prefers her own share of the cake over any other agents [Foley, 1966; Lipton et al., 2004; Caragiannis et al., 2019] and proportionality: each agent gets a share at least as valuable as the average of the whole cake [Steinhaus, 1948].

In this work, we consider the fair division of indivisible items. An instance of fair division of indivisible items comprises a set N of agents and a set M of indivisible items. We consider both the allocation of goods and chores. For the allocation of goods (resp. chores), let vi(S) (resp. ci(S)) represent the value of the goods (resp. cost of the chores) in bundle S ⊆ M for agent i. The goal is to determine an allocation X = (X1,X2, . . . ,Xn), where agent i receives Xi, and X meets certain fairness criteria. When dealing with indivisible items, the landscape changes significantly. Traditional notions of envy-freeness and proportionality face inherent challenges in this context because an exact solution may not always exist. For example, consider a scenario with two agents who value a single item equally. An allocation that satisfies either fairness notion does not guarantee existence, underscoring the complexity of allocating indivisible items. In response to these complexities, a more relaxed fairness concept emerges in the form of maximin share, initially proposed by Budish [2011], then becomes one of the most popular fairness concepts. For each agent i, her maximin share MMSi is defined as the best utility she can guarantee if she divides all the items into n bundles and picks the worst one. However, similar to the case of proportionality and envy-freeness, MMS allocations are not guaranteed to exist for both goods [Kurokawa et al., 2018; Feige et al., 2021] and chores [Aziz et al., 2017; Feige et al., 2021]. Consequently, many studies focus on approximating the maximin share (MMS).

α-MMS. An allocation of chores is α-MMS (α > 1) if the cost of each agent's bundle is at most α times her maximin share. Aziz et al. [2017] presented the first polynomial-time approximation algorithm that achieves a ratio of 2 - 1/n. Subsequently, Barman et al. [2018] improved this ratio to 4/3 and Huang and Lu [2021] improved it to 11/9. The best-known ratio to date is 13/11 [Huang and Segal-Halevi, 2023]. Another line of literature followed the work of Aziz et al. [2017] that approximating MMS allocations with only ordinal preference [Aziz et al., 2024b; Feige and Huang, 2023], leading to the current best ratio of 3/2. As for lower bounds, Feige et al. [2021] show that an approximation ratio smaller than 44/43 is not achievable. An allocation of goods is said to be α-MMS (α < 1) if every agent receives a bundle with value at least α times their MMS. Kurokawa et al. [2018] demonstrated the existence of 2/3-MMS allocations, while the computation of such allocations (in polynomial time) was established in [Amanatidis et al., 2017b; Barman and Krishnamurthy, 2020]. This ratio was later improved to 3/4 [Ghodsi et al., 2018; Garg and Taki, 2020]. More recently, the 3/4 barrier was surpassed through a series of studies [Akrami et al., 2023; Akrami and Garg, 2024], resulting in the current best ratio of 3/4 + 3/3836.

The Case of Three Agents. Several algorithms have been designed to produce α-MMS allocations for goods when there are only three agents. The first result of α = 7/8 was established in [Amanatidis et al., 2017b], and later this ratio is improved to α = 8/9 [Gourv`es and Monnot, 2019]. The ratio was subsequently enhanced to α = 11/12 [Feige and Norkin, 2022]. Regarding upper bounds, an instance with three agents demonstrating α ≤ 39/40 was constructed in [Feige et al.,

2021]. For the case of chores, there is a polynomial-time algorithm achieving a ratio of 19/18 [Feige and Norkin, 2022]. For lower bounds, Feige et al. [2021] presented an instance with three agents for which no allocation can achieve an approximation ratio strictly small than 44/43.

Fair Allocation with Money. While the aforementioned works focused on the multiplicative approximation of MMS, it is also natural to consider the additive approximation which can be modeled as the subsidy setting that compensates agents with subsidies to achieve fairness. We use s = (s1, . . . , sn) to denote the subsidies. We assume that the valuation/cost functions are normalized such that the largest value/cost of items is 1. Regarding the allocation of goods, several studies [Halpern and Shah, 2019; Brustle et al., 2020] have demonstrated that a subsidy of n - 1 is sufficient to ensure envy-freeness, while each agent is subsidized at most one dollar. This also implies that the same amount of subsidy is sufficient to achieve proportionality (PROP), as every envy-free allocation is also proportional. Subsequently, Wu et al. [2023] showed that n/4 dollars are sufficient and necessary to achieve PROP allocations for both goods and chores. However, the total subsidy required to achieve maximin share (MMS) criterion for either goods or chores has not yet been explored.

Connections between α-MMS and subsidy frameworks. Notably, when MMSi is very large, the deviation fromMMSi for each agent i is much smaller within the framework of subsidy compared to the framework of α-MMS and methods for α-MMS does not directly applicable to the framework of MMS. For example, in [Feige and Norkin, 2022], the authors address three-agent scenarios by dividing items into 3×3 atomic bundles using two agents' MMS partitions, then treating these bundles as indivisible units. While innovative, this approach has notable limitations in our framework: the absence of explicit upper bounds on atomic bundle valuations may lead to unbounded subsidy requirements. Specifically, when bundles carry extreme valuations, even slight (multiplicative) deviations from optimal allocations could necessitate disproportionately large subsidies.

1.1 Our results

Our work aims to fill in the gaps in the maximin share allocation with subsidy for both goods and chores. We focus on the case of three agents. An outcome (X, s) consisting of an allocation X and subsidies s = (s1, . . . , sn) is MMS if ci(Xi) - si ≤ MMSi (for chores) or vi(Xi) + si ≥ MMSi (for goods) for all i ∈ N.

Result 1. For allocating chores to three agents, a total subsidy of 1/6 is sufficient to guarantee MMS. No algorithm can guarantee MMS with a total subsidy of less than 2/49.

Result 2. For allocating goods to three agents, a total subsidy of 1/6 is sufficient to guarantee MMS.

We first consider the allocation of chores and then show that our technique can be naturally extended to the setting of goods. Due to the page limit, we defer the analysis for the allocation of goods to the full version of this paper.

Let A be the MMS partition of agent 1. We construct a bipartite graph G = (N ∪ A, E), where E = {(i, Aj) : i ∈ N,Aj ∈ A, ci(Aj) ≤ MMSi}. The graph reflects agents' preference towards the partition A. We show that we can either obtain an assignment of A such that the required subsidy can be bounded by 1/6; or the partition A exhibits certain structural properties. Specifically, if all assignments of A require a total subsidy larger than 1/6, we can repartition the bundles, say, under the cost function of agent 2, and decide an assignment of the new bundles such that the allocation is MMS to agents 1 and 3, and agent 2 requires a subsidy at most 1/6. Although MMS is a well-known fairness notion and has received much attention during the past decade, we remark that the knowledge of its properties is still limited, and utilizing the properties for approximating MMS is challenging. The techniques used in our analysis reveal certain properties of MMS that could potentially inspire future research.

Complexity of Allocation Computation. While our results are only existential, the bottleneck for computing such allocations lies in constructing MMS partitions - an NPhard problem through reduction from Partition [Garey and Johnson, 1979]. However, polynomial-time approximation schemes (PTAS) exist for both goods [Woeginger, 1997] and chores [Jansen et al., 2020]. Consequently, our existence results yield a PTAS: for any ϵ > 0, one can compute (1 + ϵ)- MMS allocations with ≤ 1/6 subsidy in polynomial time.

1.2 Other RelatedWorks

Allocation with Subsidy. Aziz [2021] introduced fair allocation with monetary transfers, in which agents can ensure fairness by money exchange. Brustle et al. [2020] showed that a subsidy of 2(n - 1) per agent is sufficient for general monotonic valuations. For dichotomous valuations, Barman et al. [2022] found that a subsidy of at most 1 per agent is sufficient. When treating money as divisible goods, the subsidy setting shows the similarity to the problem of allocating the mixture of divisible and indivisible goods, which was first introduced by Bei et al. [2021a], who proposed the notion of envy-freeness for mixed goods (EFM) and demonstrated its existence for additive valuations. Meanwhile, Bhaskar et al. [2021] established the existence of envy-free allocations for mixed resources that include doubly-monotonic indivisible items and a divisible chore. MMS allocations have also been explored in the context of mixed goods [Bei et al., 2021b]. For a comprehensive overview, see [Liu et al., 2024].

Other Related Settings. In addition to additive valuations, MMS allocations have been explored for more general valuations [Barman and Krishnamurthy, 2020; Ghodsi et al., 2018; Li and Vetta, 2021; Uziahu and Feige, 2023]. MMS allocations under allocation constraints have also been examined, including matroid constraints [Gourv`es and Monnot, 2019], cardinality constraints [Biswas and Barman, 2018], graph connectivity constraints [Bei et al., 2022; Truszczynski and Lonc, 2020], and online constraints [Zhou et al., 2023]. Another area of interest is the development of strategyproof mechanisms for fair division [Barman et al., 2019; Amanatidis et al., 2016; Amanatidis et al., 2017a; Aziz et al., 2024b], where the focus is on designing algorithms that ensure no agents have the incentive to misreport their preferences. Various MMS variants have also been studied, including weighted MMS [Farhadi et al., 2019], AnyPrice Share (APS) [Babaioff et al., 2021], and 1-out-of-d share [Hosseini and Searns, 2021]. Furthermore, MMS allocations have been investigated in best-of-both-worlds scenarios [Babaioff et al., 2022; Akrami et al., 2024].

Matching-Based Algorithms. Several recent works adopt an approach that involves constructing a bipartite graph based on a given partition of the items. In this graph, one side represents the set of agents, while the other side represents the partitioned items. The edges of the graph are determined by the agents' valuations or costs associated with the partitions on the opposite side. Matching in this bipartite graph plays a crucial role in finding a fair allocation, e.g., in the polynomial-time algorithm designed to find an EFX allocation when |M| ≤ 2|N| [Kobayashi et al., 2025], for the computation of allocations satisfying both PROP1 and 1 2 -MMS in the query model [Bu et al., 2024], and for computing allbut-one MMS allocations for chores [Qiu et al., 2024]. They all demonstrated that either the bipartite graph has a perfect matching, or it is possible to perform a re-partitioning that possesses certain desirable properties.

2 Preliminaries

We define the necessary notations and fairness for the allocation of chores. We consider allocating a set of indivisible chores to n agents. We use M = {e1, . . . , em} to denote the set of items and N = {1, . . . , n} to denote the set of agents, respectively. Every agent i has an additive cost function ci : 2M → R+ ∪ {0}. An instance is denoted by I = (M,N, c), where c = {c1, . . . , cn} is the set of cost functions. We assume without loss of generality (w.l.o.g.) that each item has cost at most one to each agent, i.e. ci({e}) ≤ 1 for any i ∈ N, e ∈ M. For convenience, we use ci(e) to denote ci({e}).

Definition 2.1 (Additive Cost Functions). A cost function ci is said to be additive if for any S ⊆ M, ci(S) = ∑e∈S ci(e).

An allocation is a n-partition X = (X1, . . . ,Xn) of the items M, where Xi ∩ Xj = for all i ̸= j and ∪i∈NXi = M. In allocation X, agent i ∈ N receives bundle Xi. For convenience, given any set X ⊆ M and e ∈ M, we use X+e and X - e to denote X ∪ {e} and X \ {e}, respectively.

Definition 2.2 (Maximin Share). Given any subset of items M ′ ⊆ M, an integer k, the maximin fair share of agent i ∈ N on items M ′ among k agents is defined as

where Πk(M ′ ) is the collection of all k-partitions of M ′ . We use MMSi to denote MMSi(M, n). An allocation X is MMS if ci(Xi) ≤MMSi for all i ∈ N.

Definition 2.3 (Maximin Share Partition). Given any subset of items M ′ ⊆ M, an integer k, a partition X of M ′ is a Maximin Share (MMS) Partition of agent i of size k if

By definition, such a partition always exists.

We use si ≥ 0 to denote the subsidy we give to agent i ∈ N, s = (s1, . . . , sn) to denote the set of subsidies.

Definition 2.4. An outcome (X, s) consisting of an allocation X and subsidies s = (s1, . . . , sn) is MMS if ci(Xi) - si ≤MMSi for all i ∈ N.

Given any instance I = (M, N, c), we aim to find an MMS outcome with minimal total subsidy, i.e., minimize ∑i∈N si. We remark that given any allocation X, computing the minimum subsidy to achieve MMS can be trivially done by setting si = max{ci(Xi) -MMSi, 0}, ∀i ∈ N. Therefore, in the rest of this paper, we focus mainly on computing the allocation X. The subsidy to each agent will be automatically decided by the above equation.

Definition 2.5 (MMS-feasible). For any agent i ∈ N, a bundle A is MMS-feasible to agent i if ci(A) ≤ MMSi.

Definition 2.6 (MMS-feasibility Graph). Given a partition A = {A1, . . . ,An}, we put an edge (i,Aj) if bundle Aj is MMS-feasible to agent i, i.e., ci(Aj) ≤MMSi. Let E be the set of edges and G = (N ∪ A,E) be the resulting bipartite graph. For a set of agents S ⊆ N, we use L(S) ⊆ A to denote the set of neighbors of S.

3 MMS Allocations with Subsidy for Chores

In this section, we show that when there are only three agents, a total subsidy of 1/6 is sufficient to guarantee the existence of MMS allocations. Our main result of this section is presented in Theorem 3.1.

Theorem 3.1. Given any instance I = (N,M, c) with three agents, there exists an allocation X and subsidies s such that (X, s) is MMS, and the total subsidy is at most 16 .

We remark that before our result, the existence of MMS allocations with subsidy at most 2/3 has been established for three agents [Wu and Zhou, 2024] (implied by proportional allocations with subsidy). Moreover, for proportional allocations, the subsidy bound of 2/3 is optimal. Our result presents the first non-trivial upper bound of the required subsidy for MMS allocations, showing that guaranteeing MMS is strictly easier than proportionality for three agents. We also investigate the lower bound of the required subsidy. Feige et al. [2021] presented a negative instance for the existence of MMS allocation for three agents, which implies that 1/27 subsidy is necessary to guarantee MMS allocations for three agents. In this section, we present a better lower bound of 2/49 for the case of three agents.

Theorem 3.2. There exists an instance I with three agents and nine items such that the required subsidy for any MMS outcome is at least 2/49.

We first focus on the proof of Theorem 3.1. The correctness of Theorem 3.2 will be addressed in Section 3.4.

3.1 Properties of the MMS Partition of Agent 1

Let A = {A1, A2, A3} be the MMS partition of agent 1. We show that either we can have an assignment of A that requires subsidy at most 1/6, or the partition A has certain structural properties. We construct the MMS-feasibility graph with respect to A. We remark that if there exists a perfect matching in the MMS-feasibility graph, then we can find a corresponding allocation that is MMS (without subsidy). Hence it remains to consider that there is no perfect matching. Based on Hall's Theorem, we have the following observation:

Observation 1. For any MMS-feasibility graph G, there is no perfect matching for G if and only if there exists a subset S ⊆ N, such that |S| > |L(S)|.

By Observation 1, it suffices to consider the case where there exists a subset S ⊆ N such that |S| > |L(S)|. Otherwise, we can find a perfect matching which implies an MMS allocation. Note that A is the MMS partition of agent 1, we have |L({1})| = 3. Since A is a partition of M, we have |L({i})| ≥ 1 for every agent i ∈ N. Otherwise, we have a contradiction since ∑3j=1 ci(Aj) > 3 · MMSi = 3 · maxj ci(Aj) ≥ ∑3j=1 ci(Aj). Therefore, |S| > |L(S)| happens only if |S| = 2 and 1 /∈ S. In other words, it suffices to consider the case when |L({2, 3})| = 1. We assume w.l.o.g. that L({2, 3}) = {A1} as shown in Figure 1a. Next, we investigate further properties of partition A.

(a) G has no perfect matching only if |L({2, 3})| = 1.

For all i ̸= 1

(b) Illustration for the case when all assignments of the bundles require a total subsidy > 1/6. Every dashed edge represents that the corresponding assignment requires subsidy > 1/6.

Figure 1: Illustration of the Critical Case for Focus.

We first consider the case where there exists a bundle A ∈ A \ {A1} with ci(A) ≤ MMSi + 1/6 for some i ∈ {2, 3}. Note that L({5 - i}) = {A1}, we can assign bundle A1 to agent 5 - i, bundle A to agent i, and the remaining bundle to agent 1. Since all bundles are MMS-feasible to agent 1 and bundle A1 is MMS-feasible to agent 5 - i, agent i is the only one that needs to be subsidized, while the subsidy can be bounded by 1/6. Hence it remains to consider the case that both A2,A3 costs are larger than MMSi + 1/6 to agent

ci(A3) > MMSi + 1/6,

where the first inequality follows from the fact that ci(M) ≤ 3 · MMSi. See Figure 1b for an illustration.

In the following, we take the perspective of agent 2 and show that there exists j ∈ {2, 3} and another partition of items in A1 ∪ Aj into two bundles, such that at least one bundle has cost at most MMS2 + 1/6 (under c2).

Lemma 3.3. When c2(A2) > MMS2 + 1/6 and c2(A3) > MMS2 + 1/6, there exists j ∈ {2, 3} such that

Before presenting the proof the lemma, we show that Lemma 3.3 implies Theorem 3.1.

Proof of Theorem3.1. We assume w.l.o.g. that MMS2(A1 ∪ A2, 2) ≤ MMS2 + 1/6. Let {B1,B2} be the partition that defines MMS2(A1 ∪ A2, 2), e.g., we have

Then we can assign A3 to agent 1, let agent 3 pick her preferred bundle between B1,B2, and assign the remaining bundle to agent 2. Since

there exists a bundle that is MMS-feasible to agent 3. Since A3 is MMS-feasible to agent 1, agent 2 is the only agent that needs to be subsidized. Following Equation (1), the subsidy required by agent 2 is bounded by 1/6.

Hence, it remains to prove Lemma 3.3, which will be presented in the next two subsections. Suppose MMS2(A1 ∪ Aj, 2) > MMS2 + 1/6 for both j ∈ {2, 3}, we show that there are several structural properties of A (see Lemma 3.8 for details), for which we conclude that there is no partition guaranteeing MMS2, as a contradiction. During the analysis, we will implement the classic load-balancing procedure as an analysis tool to guarantee some partition with nice properties. Hence, we first introduce the load-balancing procedure and some necessary claims.

3.2 Load-Balancing and Its Properties

Given a set of items M ′ , a number n′ , and a cost function c, the algorithm processes items in decreasing order of costs under c and assigns each item to the bundle with the minimum cost (see Algorithm 1 for the details). Next, we introduce some definitions and useful properties. As before, we take the perspective of agent 2 and will omit phrases such as "from the perspective of agent 2" when the context is clear.

Definition 3.4 (Large Item). We call an item e ∈ M large if c2(e) > 1/2. Let L = {e ∈ M : c2(e) > 1/2} be the set of large items.

Definition 3.5 (Top and Bottom Sets). Given any subset S ⊆ M, we define Top(S, t) as the set containing the t items in S with the largest cost (under c2), Bottom(S, t) as the set containing the t items in S with the lowest cost (under c2).

Algorithm 1: Load-Balancing(M ′ , n′ , c)

Require: Item set M ′ , number n′ , and cost function c with c(e1) ≥ c(e2) ≥ · · · ≥ c(em′ ).

• 1: for all k from 1 to n′ do
• 2: Pk ← ∅;
• 3: end for
• 4: Let N ′ = {1, 2, . . . , n′ };
• 5: for j = 1, 2, . . . ,m′ do
• 6: k∗ ← argmink∈N ′{c(Pk)};
• 7: Update Pk∗ ←Pk∗ + ej;
• 8: end for
• 9: return A partition P = {P1, . . . , Pn′}.

Lemma 3.6 is a standard property of the load-balancing.

Lemma 3.6. Given a partition P returned by load-balancing, for any P, P ′ ∈ P, any e ∈ P , we have ci(P - e) ≤ ci(P ′ ).

Proof. Note that the algorithm allocates items with decreasing cost. To prove the lemma, it remains to consider the last item e that is allocated to bundle P. Before allocating this item e, bundle P must be the bundle with the minimum value, which proves the lemma.

When all items are large and the number of items is even, the following lemma characterizes the structural properties of the load-balancing output.

Lemma 3.7. Suppose M ′ contains only large items, |M ′ | is even and n′ = 2, the output P = (P1, P2) of load-balancing satisfies |P1| = |P2| and |c2(P1) - c2(P2)| < 1/2.

Proof. We prove the claim by induction on |M|. The claim is trivially true when |M| = 0. Suppose the claim holds for |M| ≤ 2t, and we now prove it for |M| = 2t + 2.

• (b) After assigning e1 to P ′1, we have c2(P ′1) > c2(P ′2).

Figure 2: Illustration of allocating e1, e2.

Let P ′1 and P ′2 be the two bundles right after the moment when load-balancing has allocated 2t items. By induction hypothesis, we have |P ′1 | = |P ′2 | and |c2(P ′1 ) - c2(P ′2 )| < 1/2. If c2(P ′1 ) = c2(P ′2 ), the load-balancing procedure will assign the remaining two item to P ′1 , P ′2 respectively and result in |c2(P1)-c2(P2)| < 1/2. Consider otherwise and we assume w.l.o.g. that c2(P ′1 ) < c2(P ′2 ).

Let e1 and e2 be the remaining two items with c2(e1) ≥ c2(e2). Following the load-balancing procedure, item e1 will be assigned to P ′1 because c2(P ′1 ) < c2(P ′2 ). Recall that c2(P ′1 ) > c2(P ′2 ) - 1/2. Since e1 is a large item, we have c2(P ′1 + e1) > c2(P ′2 ) - 1/2 + c2(e1) > c2(P ′2 ).

Therefore, e2 will be assigned to P ′2 and the resulting bundles are P1 = P ′1 + e1 and P2 = P ′2 + e2. See Figure 2 for an illustration. Thus, we have |P1| = |P2|. Let d = c2(P1) - c2(P2) == c2(P ′1 ) - c2(P ′2 ) + c2(e1) - c2(e2). We have d < 1/2 since c2(e1) - c2(e2) < 1/2 and c2(P ′1 ) - c2(P ′2 ) is non-positive. Similarly, d > -1/2 since c2(P ′1 ) - c2(P ′2 ) < -1/2 and c2(e1) - c2(e2) is nonnegative.

3.3 Proof of Lemma 3.3

We have described the necessary properties of the loadbalancing subroutine, with which we are ready to prove Lemma 3.3. Assume for contradiction that the statement in Lemma 3.3 does not hold, i.e., for both j ∈ {2, 3} we have MMS2(A1 ∪ Aj) > MMS2 + 1/6. The following lemma characterizes the structural properties of such instances.

Lemma 3.8. If for all j ∈ {2, 3}, MMS2(A1 ∪ Aj) > MMS2 + 1/6, then for all j ∈ {2, 3}, we have

1. |(A1∪Aj)∩L| is odd, i.e., ∃k such that |(A1∪Aj)∩L| = 2k + 1.
2. c2(Bottom((A1 ∪Aj) ∩L, k +1)) >MMS2 +1/6;
3. |A1 ∩L| +1 = |Aj ∩L| = k +1.

Proof. Fix any j ∈ {2, 3} and let P = {P1, P2} be the partition output by Load-Balancing((A1 ∪ Aj ), 2, c2). We assume w.l.o.g. that c2(P1) ≤ c2(P2), we show that the cost difference of two bundles is bounded.

Claim 3.9. Given any partition {B1,B2} of A1 ∪ Aj with c2(B2) ≥ c2(B1), we must have c2(B2) - c2(B1) > 1/2.

Proof. Assume otherwise that c2(B2)-c2(B1) ≤ 1/2. Note that {B1, B2} is a partition of A1 ∪ Aj , we have

Combining the two equations, we obtain

Note that we must have MMS2(A1 ∪ Aj) ≤ c2(B2). This implies that MMS2(A1 ∪Aj ) < MMS2 + 1/6, which contradicts our assumption.

Since P = {P1, P2} is a partition of A1∪Aj , by Claim 3.9, we have c2(P2) - c2(P1) > 1/2. Following Lemma 3.6, for all e ∈ P2 we have c2(e) ≥ c2(P2) - c2(P1) > 1/2. In other words, all items in P2 are large.

We first show that |(A1∪Aj)∩L| is odd (Property (1)). For the sake of contradiction, we assume that it is even. Note that the load-balancing procedure will distribute large items first. Following Lemma 3.7, we have c2(P2 ∩ L) - c2(P1 ∩ L) < 1/2. Since all items in P2 are large, we have P2 ∩ L = P2 while P1 ∩ L ⊆ P1. Hence we have

which is a contradiction. Hence |(A1∪Aj)∩L| is odd and we define k = |(A1∪Aj)∩L|-1 2 , which means that |(A1 ∪ Aj) ∩ L| = 2k + 1. Let

which defines a new partition {Q1, Q2} of A1∪Aj . We claim that c2(Q1) ≥ c2(Q2), following which we have

which proved Property (2).

Proof. Assume otherwise that c2(Q1) < c2(Q2). Note that Q1 contains the smallest k + 1 large items and |Q1| = |B2|. Recall that c2(B2) > c2(B1), there must exist e1 ∈ B1, e2 ∈ B2 such that c2(e2) > c2(e1). By swapping items e1 and e2, i.e., B′1 = B1 - e1 + e2, B′2 = B2 + e1 - e2, we have c2(B′1 ) > c2(B1) and c2(B′2 ) < c2(B2). Note that we can always implement such an item swap to decrease c2(B2) and increase c2(B1) until c2(B2) ≤ c2(B1). Let e1 ∈ B1, e2 ∈ B2 be the last item pair swapped, after which B1 becomes B′1 , and B2 becomes B′2 . Note that c2(B1) < c2(B2), and c2(B′1 ) ≥ c2(B′2 ). By Claim 3.9, we have c2(B2)-c2(B1) > 1/2. Since both e1, e2 are large, we have c2(B′1 ) - c2(B1) < 1/2 and c2(B2) - c2(B′2 ) < 1/2. Then we have

By Claim 3.9, there is a contradiction.

Lastly, we move to the correctness of Property (3). Recall that |(A1 ∪Aj) ∩L| = 2k +1. Hence it suffices to show that |A1 ∩ L| = k. We first show that |A1 ∩ L| ≤ k. Suppose otherwise, we have

which is a contradiction. |A1∩L| ≤ k implies that |Aj∩L| ≥ k + 1. We further show that |Aj ∩ L| ≤ k + 1 that matches the lower bound. For the sake of contradiction, assume that |Aj ∩ L| > k + 1. We have

Let Q1, Q2 be the corresponding partition of MMS2(A1 ∪ A5-j , 2) with c2(Q1) ≥ c2(Q2). We have

Figure 3: Consider A1 ∩ L and A2 ∩ L as two bundles. Consider another partition of (A1 ∪ A2) ∩ L: A′ = Top(A1 ∪ A2, k), A′′ = Bottom((A1 ∪ A2) ∩ L, k + 1). For all e1 ∈ A′ , e2 ∈ A′′ , e2 is smaller than e1. In addition, for any 1 ≤ i ≤ k, the i-th costly item in A′ has a cost larger than the i-th costly item in A1.

Finally, we prove Lemma 3.3.

Proof of Lemma 3.3. We prove the lemma by contradiction. Suppose for all j ∈ {2, 3} we have

Let k = |A1 ∩ L|. By Lemma 3.8, we have

which implies |L| = 3k + 2. Now consider the partition (P1, P2, P3) that defines MMS2, e.g., we have c2(Pj) ≤ MMS2 for all j ∈ {1, 2, 3}. Assume w.l.o.g. that |P1 ∩L| ≤ k. We have

The equality holds due to the following argument: Let A′ = Top(A1∪A2, k). It is evident that any item in Top(A′ ∪ A3, k) is larger than any item in Bottom((A′ ∪A3)∩L, k+1) since there are 2k+1 large items in A′ ∪A3. To establish the equality, we need to show that any item in Top(A′ ∪A3, k) is larger than any item in Bottom((A1 ∪ A2) ∩ L, k + 1). This holds true because every item in Top(A1 ∪ A2, k) is larger than any item in Bottom((A1 ∪ A2) ∩ L, k + 1), and for 1 ≤ i ≤ k, the i-th item in Top(A′ ∪A3, k) is larger than the i-th item in A′ = Top(A1 ∪ A2, k).

The second inequality holds because both Top(A1 ∪A2, k) and A1 has k large items, and for 1 ≤ i ≤ k, i-th largest item in Top(A1 ∪ A2, k) is larger than the i-th largest item in A1 (See Figure 3 for an illustration). The last inequality follows from Lemma 3.8. Hence we have a contradiction as c2(P2 ∪ P3) ≤ 2 · MMS2.

3.4 Lower Bound

In this section, we focus on the correctness of Theorem 3.2. We remark that Feige et al. [2021] presented a negative instance for the existence of MMS allocations, in which there are three agents and nine items and items can be presented in a three-by-three matrix (see the following illustration).

While all agents have a maximin share of 43, they showed that for all allocations, at least one agent receives a bundle of cost at least 44. Specifically, in their negative example, the maximum item cost is 26. By normalizing the cost functions, the same instance provides a lower bound of 1/26 subsidy with respect to our setting. In the following, we present an example specifically for the subsidy setting, improving the lower bound from 1/26 to 2/49. Our construction follows the same framework as Feige et al. [2021].

They characterized two possible structures for the potential hardness examples. For both structures, agents can be named as R (stands for row), C (stands for column), and U, where the MMS partition of agent R (resp., C) is into the three rows (resp. columns). As for agent U, the first possible MMS partition is {e2, e4}, {e3, e5, e7}, {e1, e6, e8, e9}, while the second possible partition is {e2, e4}, {e1, e5, e9}, {e3, e6, e7, e8}. Since each structure induces linear constraints on the valuation functions of the agents, by adding additional constraints that limit each allocation to being not MMS, they set up a linear program that produces negative examples. When setting the objective to be the maximum approximation ratio, the LP admits a solution with a ratio of 44/43. We follow the same framework that implements an LP to produce negative examples. A subtle difference is that we need some instances that admit the maximum required subsidy. To achieve the objective, we fix the subsidy to 1 and minimize the maximum item cost. We provide the complete code of our LP in Supplementary Material. Our LP generates an instance for which any allocation requires a total subsidy of at least 2/49. For ease of presentation, in the following, we present the scaled instance in which the (minimum) required subsidy is exactly 1.

Consider the following instance with 3 agents and 9 items. The agents are referred to as R, C, and U, where the MMS of each agent is 46. The cost function of agent R is presented in the following matrix:

The cost function of agent C is as the following matrix:

The cost function of agent U is as the following matrix. The MMS partition is {e2, e4}, {e3, e5, e7}, {e1, e6, e8, e9}, in which each bundle has a cost of exactly 46:

We claim that in any allocation, at least one agent receives a bundle cost of at least 47. We verify this by enumerating all allocations in the experiment. We provide the complete code for verification in Supplementary Material. Note that in the above instance, the maximum item cost is 24.5, while for all positive allocations, there is at least one agent who receives a bundle cost of 47 and needs to be subsidized 1. After normalization, the required subsidy is at least 2 49 ≈ 0.0408.

4 Conclusion and Open Questions

In this paper, we investigate the total subsidy required to achieve MMS (for both the allocation of goods and chores). We show that a total subsidy of 1/6 suffices to satisfy MMS allocations when there are only three agents. Our work is the first to apply the framework of subsidy to the fairness notion of MMS, demonstrating that using the properties of MMS, a small subsidy is enough.

Our work leaves many interesting questions open. There is still a gap between the upper and lower bounds for both cases of goods and chores. We remark that during our analysis, we only make use of the properties of the MMS partitions for agents 1 and 2. It would be interesting to close this gap, possibly by leveraging the MMS properties of agent 3. Additionally, it is worth exploring whether our framework can be generalized to more than three agents. Note that Wu et al. [2023] showed that a total subsidy of n/4 is necessary to achieve proportionality. It would be more than interesting to evaluate if an upper bound strictly smaller than n/4 can be achieved for general n, which separates the notion of MMS and proportionality in the subsidy setting. Another interesting direction is to investigate the weighted setting, i.e., APS allocations with subsidy. It is worth mentioning that both weighted envy-freeness [Aziz et al., 2024a; Dai et al., 2024; Elmalem et al., 2024] and weighted proportionality [Wu and Zhou, 2024] have been studied in the subsidy setting.

Acknowledgments

Xiaowei Wu is funded by the Science and Technology Development Fund (FDCT), Macau SAR (file no. 0147/2024/RIA2, 0014/2022/AFJ, 0085/2022/A and SKLIOTSC-2024-2026).

Contribution Statement

The authors are ordered alphabetically.