Revisiting Proportional Allocation with Subsidy: Simplification and Improvements

1 Introduction

The fair division problem, with a research history dating back to 1948 [Steihaus, 1948], remains a central issue in economics, computer science, and mathematics. The problem involves fairly allocating a set of m items M among a group of n heterogeneous agents N, where an allocation is a partition of the items M into n disjoint bundles. The first and most natural fairness criterion, known as proportionality, was introduced and studied by Steihaus [1948]. Proportionality requires that each agent receives a bundle whose utility is at least 1/n of the total utility of all items. When all items are divisible, the existence of proportional allocations has been extensively studied under the frameworks of "cake cutting" and "bad cake cutting", which correspond to the cases when items have positive utility and negative utility, respectively. In recent decades, the focus of fair division research has shifted towards discrete scenarios, where items are indivisible and proportional allocations may not exist. For example, consider the instance of allocating a single item between two agents with non-zero values on the item. In the discrete setting, we distinguish between the fair allocation of goods (when all items have positive utility) and the fair allocation of chores (when all items have negative utility). When the set of items contains both goods and chores, we call the allocation instance a mixture of goods and chores.

In this paper, we explore the allocation of both indivisible goods and chores, as well as their mixtures. We use ui : 2M → R to denote the utility function of agent i, and we say that agent i derives utility ui(S) from the bundle of items S ⊆ M. The proportionality of agent i is thus defined by 1n · ui(M). In this paper, we assume that the utility functions are additive. We say that an item e ∈ M is a good (resp., chore) for agent i ∈ N if ui(e) ≥ 0 (resp., ui(e) ≤ 0). In the most general case, an item can be good to some agent while being a chore to another.

Relaxations of Proportionality. Since proportional allocations are not guaranteed to exist and do not admit any bounded (multiplicative) approximation ratio, several relaxations of proportionality have been proposed. One such relaxation is proportionality up to one item (PROP1), introduced by Conitzer et al. [2017], which requires that each agent can achieve her proportional share by either adding some good she does not own or removing some chore she owns. It has been shown that PROP1 allocations always exist and can be computed efficiently for goods [Conitzer et al., 2017; Barman and Krishnamurthy, 2019], chores [Brˆanzei and Sandomirskiy, 2024], and the mixture of goods and chores [Aziz et al., 2020]. A stronger variant, proportionality up to any item (PROPX), requires that the proportional share can be achieved by adding or removing any single item (for goods and chores, respectively). For the allocation of goods, Aziz et al. [2020] showed that PROPX allocations may not exist. In contrast, PROPX allocations for chores always exist and can be computed efficiently [Moulin, 2018; Aziz et al., 2024b].

Fair Allocation with Subsidy. The concept of resource allocation with monetary compensation has been extensively studied in economics. Maskin [1987] was one of the first to introduce the idea of incorporating monetary subsidies into the fair division problem. In this setting, each agent may receive a subsidy si ≥ 0 to eliminate the perceived unfairness, with the goal of minimizing the total subsidy required. For the allocation of goods, several studies [Halpern and Shah, 2019; Brustle et al., 2020] considered the fairness notion of envy-freeness (which implies proportionality), demonstrating that a total subsidy of n - 1 dollars is sufficient to achieve envy-freeness. The subsidy setting can also be applied to the allocation of chores. Wu et al. [2023] were the first to consider this problem, showing that the same amount of subsidy (n - 1) is sufficient to ensure envy-freeness for chores and proposing an algorithm that computes proportional allocations with a total subsidy at most n/4. They also proved that the upper bound of n/4 is optimal when n is even. However, when n is odd, their result leaves a small gap between the lower bound of (n2 - 1)/(4n) and the upper bound of n/4. Recently, Wu and Zhou [2024] partially closed this gap for the case of n = 3, showing that a total subsidy of 2/3 is sufficient to guarantee proportional allocations.

1.1 Our Results

In this paper, we revisit the problem of ensuring proportionality by introducing subsidies to the agents. Our main result is summarized as follows. Throughout the whole paper, we use X = (X1, . . . ,Xn) to denote an allocation of the items, s = (s1, . . . , sn) ∈ [0, 1]n to denote the subsidies to the agents, and τ(s) = ∑i∈N si to denote the total subsidy.

Main Result. For the allocation of a mixture of indivisible goods and chores to a group of n agents with additive utility functions, we can compute in polynomial time a PROP1 allocation X and subsidies s such that (X, s) is proportional (meaning that ui(Xi) + si ≥ 1n · ui(M), ∀i ∈ N), where the total subsidy τ(s) ≤ n/4 when n is even and τ (s) ≤ (n2 - 1)/(4n) when n is odd.

As a warm-up, we first consider the allocation of chores (the primary concerned setting of existing works [Wu et al., 2023; Wu and Zhou, 2024]), where all items have negative utility to all agents. As in many of the existing works that study share-based fairness notions, we show that it is without loss of generality (w.l.o.g.) to only consider IDO instances, in which all agents agree on the same ordering of items, i.e., ui(e1) ≥ ui(e2) ≥ · · · ≥ ui(em) for all i ∈ N. More importantly, we show that such a reduction preserves the upper bounds on the total subsidy and the PROP1 property of the allocation, and can be extended to the mixture of goods and chores. Given that agents share the same ordinal preference on the items in an IDO instance, we can partition the items into n bundles such that any two bundles admit a small gap in utility for all agents: in fact, a partition based on roundrobin would work. Now that we have n "even" bundles, it suffices to assign each bundle to the agent requiring the minimum subsidy on it in a sequential manner, and bound the total subsidy taking the perspective of the agent who receives the last bundle. Since our algorithm does not require computing any fractional allocation and rounding, the overall algorithm is very simple (consists of 5 lines), and the analysis is much shorter than that of [Wu et al., 2023].

Then we show that a similar algorithm and analysis can be applied to the allocation of a mixture of objective goods and chores, where each item is either a good to all agents, or a chore to all agents. We show that we can still compute a partition of items into n bundles that are even to all agents, by adapting the double round-robin algorithm [Aziz et al., 2022a], which first allocates the goods using round-robin in one order of agents, and then allocates the chores under a reversed order. Then, by applying the same assignment principle and analysis for upper bounding the total subsidy, we show that the optimal subsidy guarantee can also be achieved for this setting.

Finally, we generalize the algorithms and results to the mixture of subjective goods and chores, where an item can be a good to some agent while being a chore to another. Instead of devising a new algorithm for this setting, we show that we can reduce any subjective mixed instance to an objective mixed instance while preserving the property of the total subsidy and of PROP1. Then by using the algorithm for the objective mixed instances as a black box, we derive our results for the subjective mixed instances.

1.2 Other RelatedWorks

Besides the fairness criteria we have introduced, several other share-based fairness notions have been proposed for specific settings. A prominent example is maximin share (MMS) [Budish, 2011]. To address scenarios where agents might have different weights, Farhadi et al. [2019] introduced weighted maximin share (WMMS), while Babioff et al. [2021] proposed anyprice share (APS). Further research by Babioff and Feige explored general fair share allocation in both unweighted [Babaioff and Feige, 2022] and weighted [Babaioff and Feige, 2025] settings. More recently, Babichenko et al. [2024] introduced and studied quantile share, which measures expected utility in random allocations. Another well-studied class of fairness notions is envy-based, tracing back to [Foley, 1967]. While envy-freeness implies proportionality when valuations are additive, it's not guaranteed for indivisible items. Relaxations of envy-freeness, such as envy-freeness up to one item (EF1) [Lipton et al., 2004] and envy-freeness up to any item (EFX) [Caragiannis et al., 2019], have received significant attention. For a comprehensive overview of the fair allocation literature, we refer to the surveys by Amanatidis et al. [2023] and Aziz et al. [2022b].

Allocation of Chores. While chore allocations are as common as goods allocations in real-world scenarios, the problem receives less attention and usually tends to admit worse results. As we have introduced, both PROP1 and PROPX allocations are guaranteed to exist for chore allocation. While MMS allocations are not guaranteed to exist [Aziz et al., 2017; Feige et al., 2021], much attention focuses on approximate MMS allocations [Aziz et al., 2022c; Barman and Krishnamurthy, 2020; Huang and Lu, 2021], which led to the state-of-the-art ratio of 13/11 [Huang and SegalHalevi, 2023]. While EFX has been considered the most popular envy-based fairness notion, its existence has only been shown for some restricted settings [Aziz et al., 2023; Gafni et al., 2023; Aziz et al., 2024b; Zhou and Wu, 2024; Kobayashi et al., 2025; Tao et al., 2025; Lin et al., 2025].

Mixture of Goods and Chores. A setting that generalizes both the allocations of goods and chores is the mixture of goods and chores. It is worth mentioning that many existing algorithmic techniques developed for the non-mixture settings fail to work in the mixture setting [Aziz et al., 2022a; Chaudhury et al., 2023; Bhaskar et al., 2021], and hence the mixture setting usually demands independent analysis and scrutiny [Hosseini and Sethia, 2025]. As we have introduced before, Aziz et al. [2020] proposed an algorithm that computes PROP1 allocations in polynomial time. When strengthening PROP1 to EF1, the existence and computation of EF1 allocations have been solved by Bhaskar et al. [2021] and Aziz et al. [2022a]. There are also works that study other fairness notions for the mixed setting, e.g., for EFX [Aleksandrov and Walsh, 2020; Hosseini et al., 2023a; Hosseini et al., 2023b] and MMS [Feige, 2022; Cousins et al., 2023; Kulkarni et al., 2021].

Subsidy Setting and Beyond. While our setting assumes symmetric agents, recent studies have extended the model to the weighted setting. Wu and Zhou [2024] were among the first to investigate weighted fair allocations with subsidies, demonstrating that a total subsidy of n/3 is sufficient to guarantee weighted proportionality. Recently, Aziz et al. [2024a] and Elmalem et al. [2024] explored weighted envy-free allocations with subsidy for the allocation of goods. Another generalization involves extending the utility function beyond additive, for example, to monotone functions [Brustle et al., 2020; Kawase et al., 2024], matroid rank functions [Barman et al., 2022; Goko et al., 2024]. The subsidy setting has also been introduced to the house allocation problem [Choo et al., 2024; Dai et al., 2024]. In settings where money is treated as a divisible good, our problem shares similarities with the fair allocation of mixed divisible and indivisible items, a topic that has received considerable attention [Bei et al., 2021a; Bhaskar et al., 2021; Bei et al., 2021b; Li et al., 2023; Bu et al., 2024]. For a comprehensive review of existing works on mixed fair allocation, please refer to the survey by Liu et al. [2024].

2 Preliminaries

We consider the allocation of a set of indivisible items M = {e1, . . . , em} to n agents N = {1, . . . , n}, where the items can be either goods or chores. Each agent i has an additive utility function ui : 2M → R. That is, for any bundle S ⊆ M, ui(S) = ∑e∈S ui({e}), where ui({e}) is the utility of item e allocated to agent i. For convenience, we use ui(e) to denote ui({e}). We say that an item e ∈ M is a good (resp., chore) for some agent i ∈ N if ui(e) ≥ 0 (resp., ui(e) ≤ 0). We assume w.l.o.g. that ui(e) ∈ [-1, 1] for all agent i ∈ N and item e ∈ M. An instance is denoted by I = (M,N, u), where u = (u1, . . . , un) represents the utility functions of all agents. An allocation for instance I is an 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 of notation, given any set X ⊆ M and e ∈ M, we use X + e and X - e to denote X ∪{e} and X \ {e}, respectively. For any integer k ≥ 1, we use [k] to denote the set {1, 2, . . . , k}.

Definition 2.1 (Proportionality). Given an instance I = (M,N, u), the proportional share of each agent i ∈ N is defined as PROPi = 1n · ui(M). An allocation X is called proportional (PROP) if each agent receives a bundle with utility at least her proportional share, i.e., ui(Xi) ≥ PROPi.

Next, we define two fairness notions envy-freeness up to one item (EF1) and proportionality up to one item (PROP1).

We remark that any EF1 allocation is also PROP1, for the mixture of indivisible goods and chores [Aziz et al., 2022a].

Definition 2.2 (PROP1). An allocation X is called proportional up to one item (PROP1) if for any agent i ∈ N, either

• ui(Xi) ≥ PROPi; or
• ui(Xi - e) ≥ PROPi for some e ∈ Xi; or
• ui(Xi + e) ≥ PROPi for some e ∈ M \ Xi.

Definition 2.3 (EF1). An allocation X is called envy-free up to one item (EF1) if for any two agents i, j ∈ N, either

• ui(Xi) ≥ ui(Xj); or
• ∃ e ∈ Xi ∪Xj such that ui(Xi - e) ≥ ui(Xj - e).

We consider the subsidy setting, where each agent i ∈ N is subsidized with a non-negative subsidy si ≥ 0. We use vector s = (s1, . . . , sn) to denote the set of subsidies and τ(s) = ∑i∈N si to denote the total subsidy.

Definition 2.4. An outcome (X, s) consisting of an allocation X and subsidies s = (s1, . . . , sn) is proportional (PROP) if for any i ∈ N we have ui(Xi) + si ≥ PROPi.

Given any instance I = (M, N, u), we aim to find a PROP outcome with a small amount of total subsidy. We remark that given any allocation X of some instance I, we can turn X into a proportional outcome by introducing subsidies to the agents as follows:

Moreover, with the allocation fixed, this is the optimal way to set the subsidies. Therefore, to describe a PROP outcome, it suffices to define the allocation X. The subsidy to each agent is automatically determined by the above equation.

It has been proved that to bound the required subsidy for proportional allocations for chores, it suffices to consider IDO instances by implementing a reduction. We show that such a reduction can be extended to the mixed setting. We remark that Feige [2022] claimed a similar reduction for the mixed setting with respect to the fairness notion of MMS.

Specifically, given any I, we can construct (in polynomial time) another instance that is IDO and requires at least the same amount of subsidy to guarantee proportionality as I. We define IDO(·) as the subroutine that takes an instance as input and outputs the corresponding IDO instance.

Definition 2.5 (IDO Instances). An instance is called identical ordering (IDO) if for all agent i ∈ N we have ui(e1) ≥ · · · ≥ ui(em). For any instance I = (M,N, u), IDO(I) returns the instance (M,N, u′ ) such that for any i ∈ N and k ∈ {1, . . . ,m}, we have u′i (ek) = ui(σi(k)) where σi(k) ∈ M is the k-th most valuable item under ui.

Lemma 2.6 (IDO Reduction). Given a PROP outcome (X′ , s′ ) for IDO(I) where X′ is PROP1, we can compute a PROP outcome (X, s) for instance I in polynomial time, where X is PROP1 and τ (s) ≤ τ (s′ ).

With Lemma 2.6, in the following, we only have to consider instances that are IDO.

3 Allocations of Chores

In this section, we propose an algorithm for computing PROP outcomes for the allocation of chores. Recall that Wu et al. [2023] showed that no algorithm can ensure the existence of PROP outcomes for n agents with a total subsidy smaller than α(n), where

In the following, we prove the following theorem.

Theorem 3.1. Given any instance I = (M,N, u) for the allocation of chores, we can compute in polynomial time a PROP1 allocation X such that in the corresponding PROP outcome, the total subsidy is at most α(n).

Our algorithm follows a simple idea:

1. Suppose that we can partition the items into bundles whose utilities are roughly the same for all agents (e.g., differ by at most 1), then we can treat the n bundles as n "mega-items";
2. By sequentially allocating each mega-item to the agent requiring the minimum subsidy on it, we can upper bound the total subsidy utilizing the efficiency of subsidization.

Observe that the first step can be easily done for IDO instances in a round-robin manner. For the second step, we can upper bound the total subsidy by α(n) from the perspective of the agent who receives the last bundle. We assume that m is divisible by n by adding dummy items with zero utility to all agents. Following these ideas, we formalize our algorithm as follows.

Algorithm 1: PROP Outcome for Chores

Input: An IDO instance I = (M, N, u) with ui(e1) ≥ ui(e2) ≥ · · · ≥ ui(em) for all i ∈ N. 1 Let Ai ← {ej : j = i + z · n for some integer z}, for all i ∈ [n] ; 2 Let N ′ ←N ; 3 for j = 1, 2, . . . , n do 4 Let i∗ ← argmini∈N ′{PROPi -ui(Aj)} ; 5 Update Xi∗ ←Aj and N ′ ←N ′ \ {i∗ } ; Output: PROP outcome with allocation X.

As shown in Algorithm 1, we first partition the items into A = (A1, · · · ,An) in a round-robin manner, and then sequentially allocate each bundle to the active agent who requires the minimum amount of subsidy (to guarantee proportionality), where N ′ contains all active agents (who have not received a bundle). Clearly, the algorithm runs in polynomial time. Therefore, to prove Theorem 3.1, it suffices to show that the total required subsidy is upper bounded by α(n).

We show that the partition A is approximately even, i.e., for all agents, the utility difference between any two bundles is small. Moreover, we show that the partition is EF1 for all agents, meaning that as long as each agent receives exactly one bundle, then the allocation is EF1 1 .

Lemma 3.2. For the partition A computed in Alg. 1, for any agent i ∈ N and any two bundles Ax, Ay, either Ax = ∅, or there exists e ∈ Ax such that ui(Ax - e) ≥ ui(Ay).

Proof. Suppose m = k · n, we have |Ax| = |Ay| = k. By definition we have Ax = {ex, ex+n, ex+2n, . . .} and Ay = {ey, ey+n, ey+2n, . . .}. Since the instance is IDO, we have

which proves the lemma.

Next, we provide an upper bound for the total subsidy.

Lemma 3.3. For the allocation X computed in Alg. 1, the total subsidy of the corresponding PROP outcome (X, s) is at most α(n).

Proof. We allocate the bundles in n rounds while in each round j ∈ {1, 2, . . . , n} we allocate bundle Aj to the active agent i ∈ N ′ with minimum PROPi - ui(Aj). For the convenience of notation, we reindex agents and assume w.l.o.g. that agent i receives bundle Ai. Thus, agent n is the last active agent. By definition, when allocating each bundle Aj where j < n, agent n is one of the active agents but does not receive bundle Aj . Hence for all j ∈ [n] we have

Therefore, we can upper-bound the total subsidy by

Let H = {Aj : un(Aj) < PROPn} be the bundles with utility lower than the proportional share of agent n and f = |H|. We use h to denote maxAj∈H {PROPn -un(Aj)}. See Figure 1 for an example. Then we can upper bound the total required subsidy by

1 Note that EF1 holds only for the IDO instances. The IDO reduction cannot guarantee preserving EF1.

On the other hand, observe that ∑j∈N un(Aj) = un(M) = n · PROPn, which implies

Hence, the total subsidy can also be bounded by

where the last inequality holds by Lemma 3.2: for all Aj ∈ A \ H we have

Combining Equations (1) and (2), we upper bound the total subsidy by

where the first inequality holds because when h ≤ n-f n , we have fh ≤ f(n-f) n ; when h > n-f n , we have (n-f)(1-h) < f (n-f ) n . The second inequality holds because f ∈ {1, . . . , n} and f (n-f ) attains the maximum value α(n) when f = n/2 for even n; f = (n - 1)/2 for odd n.

4 Allocation of Mixed Items

In this section, we show that our algorithm and analysis can be extended to the settings of mixed items. We first consider the mixture of objective goods and chores, where every item is either a good to all agents or a chore to all agents. Note that this setting subsumes the allocation of goods and chores as special cases. For this case, we show that the optimal subsidy guarantee α(n) can be obtained. Then we generalize the results to the mixture of subjective goods and chores, where an item can be a good to some agent while being a chore to another. We show that every subjective mixed instance can be reduced to an objective mixed instance, and we can transform the allocation for the objective mixed instance to an allocation for the subjective mixed instance, preserving the upper bound on the total subsidy and the PROP1 property.

4.1 Objective Mixed Instance

We first consider the mixture of objective goods and chores [Hosseini et al., 2023b], for which we can partition the items M into M + and M -, where M + contains all the goods and M - contains all the chores. We show that the optimal subsidy guarantee α(n) can be achieved by implementing the double round-robin algorithm, which is proposed by Aziz et al. [2022a] to compute EF1 allocations for the mixed setting. Note that in their setting, the input instance is not necessarily IDO. In the following, we show that for IDO instances, any arbitrary permutation of the bundles in the computed allocation results in an EF1 allocation. We call such a partition an EF1 partition.

Definition 4.1 (EF1 Partition). A partition A is EF1 if for all i ∈ N and Ax, Ay ∈ A, either

• ui(Ax) ≥ ui(Ay); or
• there exists some item e ∈ Ax ∪Ay such that ui(Ax - e) ≥ ui(Ay - e).

As we have introduced before, we implement the double round-robin algorithm (see Lines 1 - 7 of Alg. 2) to compute an approximately even partition, which is used to replace the round-robin partition we used in Algorithm 1. Roughly speaking, we allocate the goods and the chores both in a round-robin manner. However, when allocating the goods, bundle A1 has the highest priority, e.g., e1 (the best good) is allocated to A1 while bundle An has the lowest priority. When allocating the chores, bundle An has the highest priority while bundle A1 has the lowest priority, e.g., em (the worst chore) is allocated to A1 (see Figure 2 for an illustration). We show in Lemma 4.2 that the computed partition is EF1. We remark that the partition (instead of the allocation) being EF1 is crucial to our setting because we need the freedom to decide the assignment of the bundles to minimize the required total subsidy. Note that we can assume w.l.o.g. that both |M +| and |M -| are divisible by n, as we can add dummy items with zero utility to all agents. Suppose |M +| = z · n. Since the instance is IDO, for all i ∈ N we have

Algorithm 2: PROP Outcome for Objective Mixed

Input: An IDO objective mixed instance I = (M, N, u) with ui(e1) ≥ · · · ≥ ui(ezn) ≥ 0 ≥ ui(ezn+1) ≥ · · · ≥ ui(em) for all i ∈ N. 1 Let Ai ← ∅ for all i ∈ N ; 2 for j = 1, 2, . . . , zn do 3 Let i ← ((j -1) mod n) +1 ; 4 Ai ←Ai + ej ; 5 for j = zn+1, . . . ,m do 6 Let i ←n- ((j -1) mod n) ; 7 Ai ←Ai + ej ; 8 Let N ′ ←N ; 9 for j = 1, 2, . . . , n do 10 Let i∗ ← argmini∈N ′{PROPi -ui(Aj)} ; 11 Update Xi∗ ←Aj and N ′ ←N ′ \ {i∗ } ; Output: PROP outcome with allocation X.

Proof. Fix any agent i ∈ N and any two bundles Ax,Ay ∈ A. Suppose ui(Ax) < ui(Ay), we show that there exists an item e ∈ Ax ∪ Ay such that ui(Ax - e) ≥ ui(Ay - e).

We first consider the case when x < y. Recall that in the round-robin allocation of goods, bundle Ax has a higher priority and in each round receives an item that is at least as good as the one bundle Ay receives. Therefore we have ui(Ax ∩ M +) ≥ ui(Ay ∩ M +). On the other hand, for the chores allocated to Ax and Ay, bundle Ay has a higher priority. However, by the property of round-robin, if we remove the last item (the worst chore) em-x+1 that is allocated Ax, the total utility of chores in Ax - em-x+1 is at least that of chores in Ay (see Figure 2 for an illustration). Therefore, combining both goods and chores, we have ui(Ax - em-x+1) ≥ ui(Ay).

Next, we consider the case when x > y. By a similar argument as above, since Ax has a higher priority than Ay during the allocation of chores, we have ui(Ax ∩ M -) ≥ ui(Ay ∩ M -). On the other hand, while Ax has a lower priority in receiving goods, by removing the first item (the best good) ey allocated to Ay, the total utility of goods in Ax is at least that of the goods in Ay - ey. Hence we have ui(Ax) ≥ ui(Ay -ey). Since the bundles Ax and Ay and the agent i ∈ N are chosen arbitrarily, by definition the partition is EF1 for all agents.

Given that the partition A is EF1, we can bound the total required subsidy of allocation X by an analysis almost identical to that of the chores instance (Lemma 3.3).

Lemma 4.3. For the allocation X computed in Alg. 2, the total subsidy of the corresponding PROP outcome (X, s) is at most α(n).

Combining the above two lemmas with Lemma 2.6, we have proved Theorem 4.4.

Theorem 4.4. Given any objective mixed instance I = (M, N, u), we can compute in polynomial time a PROP1 allocation X such that in the corresponding PROP outcome, the total subsidy is at most α(n).

Since the allocation of goods is a special case of objective mixed instances, Theorem 4.4 not only generalizes our first result (Theorem 3.1) but also implies that the optimal subsidy guarantee α(n) can be obtained for the allocation of goods. 2

4.2 Subjective Mixed Instance

In this section, we extend our framework to the setting where an item can be a good for one agent but a chore for another, i.e., the identity of goods and chores can be subjective.

Our analysis involves a reduction from the subjective mixed instances to the objective mixed instances 3 . Given any IDO subjective mixed instance I, we construct a new instance I ′ which is IDO and objective mixed. By running Algorithm 2 on instance I ′ , we obtain a PROP outcome (X′ , s′ ) for I ′ , based on which we construct (X, s) that is a PROP outcome for the original instance I. We show that the total subsidy τ(s) ≤ τ(s′ ), which implies that the optimal subsidy bound of α(n) can also be achieved for the subjective mixed instance. We first describe our construction of the objective mixed instance I.

2 It is also shown in [Wu et al., 2023] that no algorithm can guarantee PROP outcomes with subsidy strictly less than α(n) for the allocation of goods.

3 Similar reductions can be obtained for other share-based fairness notions like maximin share (MMS).

Reduction to Objective Mixed Instances Given any subjective mixed instance I that is IDO, we first identify the agent with the maximum number of goods, i.e.,

Note that we can assume w.l.o.g. that i∗ = 1. For any agent i, we let ki be the number of items that are goods to agent i. Therefore we have ki ≤ k1 for all i ∈ N. We construct a new instance I ′ = (M,N, u′ ) as follows: for every agent i ∈ N, we define her utility function u′i as

In other words, for the items that are goods to agent 1 but chores to agent i, we raise their utilities to zero in u′i . Particularly, we have u′1 = u1. Hence we can view all these items as goods to all agents, resulting in an objective mixed instance.

Observation 1. The constructed instance I ′ is an IDO objective mixed instance.

Proof. Fix some agent i ∈ N. We show that u′i (ex) ≥ u′i (ey) for any x < y. Recall that I is an IDO instance and u′i (ex) = ui(ex) holds for any x ≤ ki and x > k1. Hence to show that I ′ is IDO, it suffices to consider: 1) ki < x < k1; and 2) ki < y < k1.

• If ki < x ≤ k1, we have u′i (ex) = 0. For any y > x, we have u′i (ey) ≤ 0 = u′i (ex).
• If ki < y ≤ k1, we have u′i (ey) = 0. For any x < y, we have u′i (ex) ≥ 0 = u′i (ey).

Hence we have u′i (e1) ≥ · · · ≥ u′i (em) for all i ∈ N, and the instance is IDO. Moreover, for all agent i ∈ N, we have u′i (ej) ≥ 0 for all j ≤ k1 and u′i (ej) ≤ 0 for all j > k1. Therefore the instance I ′ is an objective mixed instance.

For the constructed instance I ′ , we use PROP′i to denote agent i's proportional share, i.e., PROP′i = u′i (M) n . Since the utility of any item on any agent does not decrease during the reduction, we have PROP′i ≥ PROPi for all i ∈ N.

Following Theorem 4.4, we can compute a PROP outcome (X′ , s′ ) for instance I ′ , where the total subsidy τ(s′ ) ≤ α(n) and for any agent i ∈ N we have

Based on the allocation X′ , we construct a new allocation X for instance I as follows. For any agent i ≥ 2, we define Si as the set containing all the items ej ∈ X′ i that are chores to i (under ui) but goods to agent 1, which can be equivalently expressed as Si = {ej ∈ X′ i : ki < j ≤ k1}.

Note that by the construction of u′i , we have u′i (Si) = 0 for all i ≥ 2. Then we define the allocation X as follows:

• for all i ≥ 2, let Xi =X′ i \ Si;
• for agent 1, let X1 =X′1 ∪ (⋃i≥2 Si).

In other words, we reallocate all items that are chores to its receiver in allocation X′ but goods to agent 1 back to agent 1 in allocation X. We summarize the steps of the whole algorithm in Algorithm 3.

Algorithm 3: PROP Outcome for Subjective Mixed

We argue that for all i ∈ N, we have ui(Xi) ≥ u′i (X′ i ). Lemma 4.5. For any agent i ∈ N, we have ui(Xi) ≥ u′i (X′ i ). Moreover, for all e ∈ Xi we have ui(e) = u′i (e).

Proof. We first consider agent 1. Since u1 = u′1 and X′1 ⊆ X1, it suffices to argue that u1(⋃i≥2 Si) ≥ 0. Note that for any item ej ∈ ⋃i≥2 Si, we have j ≤ k1. Following the definition of k1, we have ui(ej ) > 0 for all j ≤ k1. Hence we have ui(⋃i>2 Si) > 0, which implies that ui(Xi) > u′i (X′ i ).

Next, we consider any agent i ≥ 2. By the definition of ui and Si, we have ui(ej) = u′i (ej) for all ej ∈ Xi = X′ i \ Si.

Therefore we have

where the last equality holds since u′i (Si) = 0. Hence, the lemma follows.

Finally, we show that X is a PROP1 allocation, and the corresponding PROP outcome requires a total subsidy ≤ τ(s′ ).

Lemma 4.6. The allocation A computed in Alg. 3 is PROP1.

Lemma 4.7. For the allocation X computed in Alg. 3, the total subsidy of the corresponding PROP outcome (X, s) is at most τ(s′ ).

Proof. Following Lemma 4.5 and Observation 2, for any agent i ∈ N we have

Since si = max{PROPi-ui(Xi), 0}, we have si ≤ s′i for all i ∈ N. Hence, the total required subsidy is at most τ(s′ ).

Combining the above two lemmas with the result for the objective mixed instances (see Theorem 4.4) and the IDO reduction (see Lemma 2.6), we have proved Theorem 4.8.

Theorem 4.8. Given any subjective mixed instance I = (M,N, u), we can compute in polynomial time a PROP1 allocation X whose corresponding PROP outcome requires subsidy at most α(n).

5 Conclusion

In this paper, we revisit the problem of fair allocation with subsidy, for goods, chores, and their mixture. We show that even for the mixture of subjective goods and chores, we can compute PROP outcomes with subsidy at most α(n) (which is n/4 for even n and (n2 - 1)/(4n) for odd n). Our upper bound matches the previous lower bound of the required subsidy for PROP allocations in the setting of chores, making it optimal. Unlike previous results based on the rounding framework, we present a new framework that first computes a partition of items into n bundles that are even to all agents and then decides a subsidy-efficient assignment of the bundles.

Our result completes the work of Wu et al. [2023] and generalizes it to the mixed setting. However, there are still many open problems on the topic of fair allocation with subsidy. For example, for the case when agents have general weights, there is still a gap between the upper bound of n/3 [Wu and Zhou, 2024] and the lower bound of n/4 for the total subsidy. It seems difficult to extend our framework to the weighted setting since when agents have different weights, it is inherently impossible to partition the items into n bundles without deciding their assignments. It would also be interesting to investigate the problem together with efficiency or strategyproofness guarantees. Finally, we believe that it would be a nice topic to study allocations with subsidy for other fairness criteria, e.g., Maximin Share (MMS) or AnyPrice Share (APS). Since these fairness notions are strictly easier to satisfy than proportionality, it would be interesting to know whether a total subsidy strictly less than n/4 is sufficient.

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, 001/2024/SKL, and SKL-IOTSC-2024-2026).

Contribution Statement

The authors are ordered alphabetically.