# Tree Splitting Based Rounding Scheme for Weighted Proportional Allocations
with Subsidy

Xiaowei Wu IOTSC, University of Macau<EMAIL_ADDRESS>The
authors are ordered alphabetically. Shengwei Zhou∗

###### Abstract

We consider the problem of allocating $m$ indivisible items to a set of $n$
heterogeneous agents, aiming at computing a proportional allocation by
introducing subsidy (money). It has been shown by Wu et al. (WINE 2023) that
when agents are unweighted a total subsidy of $n/4$ suffices (assuming that
each item has value/cost at most $1$ to every agent) to ensure
proportionality. When agents have general weights, they proposed an algorithm
that guarantees a weighted proportional allocation requiring a total subsidy
of $(n-1)/2$, by rounding the fractional bid-and-take algorithm. In this work,
we revisit the problem and the fractional bid-and-take algorithm. We show that
by formulating the fractional allocation returned by the algorithm as a
directed tree connecting the agents and splitting the tree into canonical
components, there is a rounding scheme that requires a total subsidy of at
most $n/3-1/6$.

##  1 Introduction

We study the fair allocation problem of allocating a set of $m$ indivisible
items $M$ to a group of $n$ heterogeneous agents $N$. When all items $M$ give
positive values to all agents, the problem refers to the fair allocation of
_goods_ , which represents the situation of distributing resources or public
goods. Analogous but contrary, when all items $M$ give negative values
(positive costs) to all agents, the problem refers to the fair allocation of
_chores_ , which covers the task allocation among employees. In this paper, we
mainly focus on the allocation of chores, where each agent $i$ has a cost
function $c_{i}:2^{M}\to{\mathbb{R}}^{+}\cup\\{0\\}$, but our main result also
applies to the allocation of goods. We consider the general weighted setting
in which each agent $i$ has a $w_{i}>0$ that represents her obligation to
undertake the chores. We normalize the weights of agents such that $\sum_{i\in
N}w_{i}=1$. Traditionally, the fair allocation problem considers how to fairly
allocate the items into $n$ bundles $(X_{1},\ldots,X_{n})$, while each agent
receives exactly one bundle that guarantees some fairness criteria for her. We
say that agent $i$ has cost $c_{i}(S)$ for bundle $S\subseteq M$. One natural
and well-studied fairness notion is _proportionality_ (PROP) [40]: an
allocation is called weighted proportional (WPROP) if for all agent $i$,
$c_{i}(X_{i})\leq w_{i}\cdot c_{i}(M)$, where we refer to $w_{i}\cdot
c_{i}(M)$ as the proportional share of agent $i$.

Unfortunately, when items are indivisible, PROP allocations are not guaranteed
to exist, e.g., considering allocating a single item to two agents. One
possible way to circumvent this non-existence result is by introducing money
to eliminate the inevitable unfairness. Maskin [37] first proposed the setting
called fair allocation with money that allows each agent to receive a subsidy
$s_{i}\geq 0$ to eliminate unfairness, under which the objective is to
minimize the total subsidized money. Halpern and Shah [29] considered the fair
allocation of goods with money, for another well-known fairness notion, called
_envy-freeness_ [26]. Assuming that each item has a value of at most $1$ to
each agent, they conjecture that a total subsidy of $n-1$ suffices to
guarantee envy-freeness for the allocation of goods. The conjecture was later
verified by Brustle et al. [17].

##### Allocation of Chores with Subsidy.

The setting of fair allocation with subsidy can be naturally applied to the
allocation of chore. Consider a situation where a factory, such as _Foxconn_ ,
wants to distribute a bunch of production tasks to $n$ different working
units. Different working units have different capacities, e.g., their
proportional shares of the total tasks, and need to be compensated with money
when assigned tasks exceeding their capacity, i.e., for overtime payment. To
ensure fairness (for a stable partnership), the mass of tasks each working
unit receives, after removing the part that the subsidy offsets, should not
exceed its proportional share of the total tasks. On the other hand, to
maximize benefits, the factory objects to minimize the total (additional)
overtime payments, under the situation that all tasks are completed. In other
words, we aim to compute an allocation $(X_{1},\ldots,X_{n})$ and subsidies
$(s_{1},\ldots,s_{n})$ such that $c_{i}(X_{i})-s_{i}\leq w_{i}\cdot c_{i}(M)$
for all agent $i\in N$, with a small amount of total subsidy
$\|\mathbf{s}\|_{1}=\sum_{i\in N}s_{i}$. When all agents have equal weights,
Wu et al. [42] proposed an algorithm that computes a proportional allocation
with a total subsidy of at most $n/4$. Their algorithm is based on rounding a
fractional allocation returned by the Moving Knife Algorithm. However, when
agents have general weights, their algorithm can only guarantee an upper bound
of $(n-1)/2$ on the total subsidy.

###  1.1 Our Results

In this paper, we revisit the problem of fair allocation of chores with
subsidy. A commonly used framework for this problem is to first compute a
fractional proportional allocation and then design a rounding scheme to turn
the allocation integral with bounded total subsidy. For the unweighted
setting, the algorithm of Wu et al. [42] that guarantees a total subsidy of at
most $n/4$ is based on rounding a well-structured fractional allocation
returned by the Moving Knife Algorithm. Specifically, the algorithm computes a
fractional allocation such that each agent receives a contiguous bundle of
items in which at most two of them (the first and the last) are fractional.
However, the algorithm fails to generalize to the weighted setting where
agents have arbitrary weights. As they pointed out, any algorithm that
requires each agent to receive a contiguous bundle of items, fails to compute
a (fractional) weighted proportional allocation.

On the other hand, if we do not require any structural property on the
fractional allocation, it is easy to compute a weighted proportional
allocation. For example, the Eating Algorithm that lets all agents eat their
most preferred available item continuously at the same time, with speeds
proportional to their weights, guarantees weighted envy-freeness, and thus
weighted proportionality. However, it is easy to find instances for which
almost all items are shared by multiple agents in the fractional allocation
returned by the Eating Algorithm. This complex item-sharing structure
introduces major difficulties for devising the rounding scheme and bounding
the incurred subsidy. As a comparison, in the fractional allocation returned
by the Moving Knife Algorithm, there are at most $n-1$ fractional items and
each agent receives at most two such items. Therefore, we consider the
Fractional Bid-and-Take algorithm (FBAT) that computes fractional weighted
proportional allocations with a certain level of canonical structure. The same
fractional algorithm is considered in [42], where it is shown that there are
at most $n-1$ fractional items in the returned allocation. However, in this
fractional allocation, an agent may receive many fractional items.
Consequently, their rounding scheme can only guarantee an upper bound of
$(n-1)/2$ on the total subsidy. Whether strictly less subsidy is sufficient to
guarantee (weighted) proportionality remains unknown and is proposed as an
open problem.

In this paper, we revisit the fractional bid-and-take algorithm and answer
this question affirmatively. We characterize the structure of the fractional
allocations returned by FBAT, by introducing the _item-sharing_ graph where
agents are nodes and fractional items are edges. We show that the item-sharing
graph of the allocation returned by FBAT is a directed tree111As a comparison,
the item-sharing graph defined by the allocation returned by the Moving Knife
Algorithm is a path; while that for the Eating Algorithm can be any complex
dense multi-graph.. We introduce a general rounding framework based on tree
splitting, which allows us to split the directed tree graph into canonical
components and round each component independently. We show that there exists a
rounding scheme that guarantees weighted proportionality with a total subsidy
of at most $n/3-1/6$.

Main Result. For the allocation of chores to a group of $n$ agents with
general weights, we can compute in polynomial time a weighted proportional
allocation with subsidy, where the total subsidy is at most $n/3-1/6$.

We remark that rounding the item-sharing graph via tree splitting requires
striking a balance between the fineness of the splitting and tightness of the
subsidy upper bound. The finer we split the tree, the easier we can upper
bound the total subsidy: but this upper bound is usually very loose. For
instance, if we take every edge as a component, we can easily recover the
simple rounding scheme that guarantees a total subsidy of $(n-1)/2$ [42]. On
the other hand, regarding the tree as a whole when rounding items could help
give tighter upper bounds but it would be very difficult to characterize the
required subsidy. One notable difficulty in designing the rounding scheme is
to handle the fractional items that are shared by multiple agents, which we
call the _shattered items_. A shatter item corresponds to multiple edges (that
form a path, which we call an _atom-path_) in the item-sharing graph. Since
every item should be rounded to exactly one agent, we need to ensure that all
edges that correspond to the same shattered item belong to one component after
splitting, which puts constraints on the feasible tree splittings. To get
around this difficulty, we design an atom-path-centric splitting that
recursively splits the tree into an (near) atom-path and a collection of
subtrees meeting certain constraints, and use mathematical induction to bound
the total subsidy.

We further extend our tree splitting based rounding framework to the
allocation of goods. With some minor modifications to the analysis, we show
that a total subsidy of at most $n/3$ suffices to guarantee a weighted
proportional allocation of goods (the proof can be found in the appendix).

###  1.2 Other Related Works

Since the seminal work of Steinhaus [40], the fair allocation problem has
received significant attention in the past decades. Other than
proportionality, another well-studied fairness notion is _envy-freeness_ (EF)
[26], that is, no agent wants to exchange her bundle of items with another
agent to improve her utility. Since both EF and PROP are not guaranteed to
exist when items are indivisible, a line of literature focused on the
relaxations of these two fairness notions. _Envy-freeness up to one item_
(EF1) [35] and _envy-freeness up to any item_ (EFX) [19] are two widely
studied relaxations of envy-freeness, which require that the envy between any
two agents can be eliminated by removing some item; any item respectively.
Similarly, we have _proportionality up to one item_ (PROP1) [22, 11] and
_proportionality up to any item_ (PROPX) [7], which require the gap between
the bundle’s utility and the proportionality is bounded by some/any item, to
be two relaxations of PROP. In addition, _maximin share_ (MMS) [18] is another
popular relaxation of PROP. For a more comprehensive overview of the fair
allocation literature, we refer to the recent surveys by Amanatidis et al. [1]
and Aziz et al. [5].

##### Chore Allocation.

Most of the fairness notions, such as EF1, EFX, PROP1, PROPX, and MMS,
naturally extend to the analogous problem of chore allocation. While the chore
allocations are as common as the goods allocations in real-world scenarios,
the problem receives less attention and usually tends to have worse results.
For the allocation of chores, both EF1 [14] and PROP1 [11, 22] allocations are
guaranteed to exist and can be found in polynomial time. In contrast to the
goods allocations where PROPX allocation may not exist, PROPX allocations
always exist for chores allocation [38, 33]. Regarding EFX allocations, they
have only been shown to exist for some restricted settings [3, 27, 33, 41,
44]. While MMS allocations are not guaranteed to exist [8, 25], much attention
focuses on approximate MMS allocations [6, 12, 30], which led to the state-of-
the-art ratio of $13/11$ [31].

##### Weighted Setting.

Motivated by real-world applications where agents are usually not equally
obliged, Chakraborty et al. [20] proposed the _weighted_ (or _asymmetric_)
setting. Chakraborty et al. [20] introduced the _weighted envy-freeness up to
one item_ (WEF1) for the allocation of goods and show that WEF1 allocations
always exist and can be computed in polynomial time. Lately, WPROP1
allocations have been proved to exist for chores [16], and the mixture of
goods and chores [7]. Li et al. [33] showed the existence and computation of
WPROPX allocations of chores. Recently, Wu et al. [43] and Springer et al.
[39] proposed algorithms for the computation of WEF1 allocations for chores.
The weighted version of MMS (WMMS) has also been studied for both goods [23]
and chores [4]. In addition, generalizing MMS to the weighted setting also
inspires the fairness notion of _Anyprice Share_ (APS). Babioff et al. [9]
showed that there always exist $(3/5)$-approximate APS allocations for goods
and $2$-approximate APS allocations for chores. The approximate ratio for
chores was recently improved to $1.733$ by Feige and Huang [24].

##### Fair allocation with Money.

Beyond additive valuation functions, Brustle et al. [17] showed that a subsidy
of $2(n-1)$ dollars per agent suffices to guarantee envy-freeness for general
monotonic valuation functions. Very recently, the upper bound was improved to
$n-1$ dollars per agent by Kawase et al. [32] while the total subsidy is at
most $n(n-1)/2$. Barman et al. [10] considered the dichotomous valuations
(each good has binary marginal value) and showed that envy-freeness can be
guaranteed with a per-agent subsidy of at most $1$. Regarding truthfulness,
Goko et al. [28] showed that for general monotone submodular valuations, there
exists a truthful mechanism that guarantees envy-freeness with a subsidy of at
most one dollar per agent. A similar setting is called fair allocation with
monetary transfers, introduced by Aziz [2], that allows agents to transfer
money to each other. Instead of minimizing the total subsidy, their result
focused on the characterization of allocations that are equitable and envy-
free with monetary transfers. When considering money as a divisible good, the
setting of fair allocation with money is similar to the fair allocation of
mixed divisible and indivisible items, which also receives much attention [13,
14, 34]. For a more detailed review of the existing works on mixed fair
allocation, please refer to the recent survey [36].

##  2 Preliminary

In the following, we introduce the notation and the fairness notions. We
consider the problem of allocating $m$ indivisible chores $M$ to $n$ agents
$N$ where each agent $i\in N$ has an additive cost function
$c_{i}:2^{M}\to{\mathbb{R}}^{+}\cup\\{0\\}$. We assume that the agents are
weighted, i.e., each agent $i\in N$ has a weight $w_{i}>0$ (that represents
her obligation for undertaking the chores) and $\sum_{i\in N}w_{i}=1$. We
denote by $\mathbf{w}=(w_{1},\ldots,w_{n})$ the weights of agents. A cost
function $c_{i}$ is said to be additive if for any bundle $S\subseteq M$ we
have $c_{i}(S)=\sum_{e\in S}c_{i}(\\{e\\})$. For convenience, we use
$c_{i}(e)$ to denote $c_{i}(\\{e\\})$. We use $\mathbf{c}=(c_{1},...,c_{n})$
to denote the cost functions of agents. We assume w.l.o.g. that each item has
cost at most one to each agent, i.e. $c_{i}(e)\leq 1$ for any $i\in N$, $e\in
M$. Given an instance $\mathcal{I}=(M,N,\mathbf{w},\mathbf{c})$, an allocation
of $\mathcal{I}$ is represented by an $n$-partition
$\mathbf{X}=(X_{1},\ldots,X_{n})$ of the items $M$, where $X_{i}\cap
X_{j}=\emptyset$ for all $i\neq j$ and $\cup_{i\in N}X_{i}=M$. In allocation
$\mathbf{X}$, agent $i\in N$ receives bundle $X_{i}$. For convenience of
notation, given any set $X\subseteq M$ and $e\in M$, we use $X+e$ and $X-e$ to
denote $X\cup\\{e\\}$ and $X\setminus\\{e\\}$, respectively.

######  Definition 2.1 (WPROP).

An allocation $\mathbf{X}$ is called weighted proportional (WPROP) if
$c_{i}(X_{i})\leq w_{i}\cdot c_{i}(M)$ for all $i\in N$.

We use $\mathsf{WPROP}_{i}$ to denote agent $i$’s proportional share, i.e.,
$\mathsf{WPROP}_{i}=w_{i}\cdot c_{i}(M)$.

We use $s_{i}\geq 0$ to denote the subsidy we give to agent $i\in N$,
$\mathbf{s}=(s_{1},\ldots,s_{n})$ to denote the set of subsidies, and
$\|\mathbf{s}\|_{1}=\sum_{i\in N}s_{i}$ to denote the total subsidy.

######  Definition 2.2 (WPROPS).

An allocation $\mathbf{X}$ with subsidies $\mathbf{s}=(s_{1},\ldots,s_{n})$ is
called weighted proportional with subsidies (WPROPS) if for any $i\in N$ we
have $c_{i}(X_{i})-s_{i}\leq\mathsf{WPROP}_{i}$.

Given any instance $\mathcal{I}=(M,N,\mathbf{w},\mathbf{c})$, we aim to find
WPROPS allocation $\mathbf{X}$ with a small amount of total subsidy. Unlike
envy-freeness with subsidy222An allocation with subsidies is weighted envy-
free with subsidy if $c_{i}(X_{i})/w_{i}-s_{i}\leq c_{i}(X_{j})/w_{j}-s_{j}$
for all $i,j\in N$. We remark that even in the unweighted setting, not all
allocations are envy-freeable. In other words, there exist allocations that
cannot guarantee envy-freeness even if we introduce unbounded subsidies to the
agents., we can turn any allocation $\mathbf{X}$ into weighted proportional by
introducing subsidies to the agents as follows:

$s_{i}=\max\\{c_{i}(X_{i})-\mathsf{WPROP}_{i},0\\},\qquad\forall i\in N.$

Therefore, in the rest of this paper, we mainly focus on computing the
allocation $\mathbf{X}$. The subsidy to each agent will be automatically
decided by the above equation. Before we dive into our algorithm and analysis,
we first introduce a reduction from general instances to identical ordering
instances. An instance is called _identical ordering_ (IDO) if all agents have
the same ordinal preference over all items.

######  Definition 2.3 (Identical Ordering (IDO) Instances).

An instance is called identical ordering (IDO) if all agents have the same
ordinal preference on the items, i.e., $c_{i}(e_{1})\geq
c_{i}(e_{2})\geq\cdots\geq c_{i}(e_{m})$ for all $i\in N$.

In the unweighted setting, Wu et al. [42] showed that if there exists an
algorithm for computing PROPS allocations for IDO instances, then it can be
converted to an algorithm that works for general instances while preserving
the subsidy requirement. The IDO reduction is a general technique and is
widely used in the computation of approximate MMS allocations [12, 15, 30,
31], PROP1/PROPX allocations [7, 33]. We show that the reduction in [42] can
be naturally generalized to the weighted setting. With this reduction, in the
rest of this paper, we only consider IDO instances. For completeness, we
repeat the proof in Appendix A.

######  Lemma 2.4.

If there exists a polynomial time algorithm that given any IDO instance
computes a WPROPS allocation with total subsidy at most $\alpha$, then there
exists a polynomial time algorithm that given any instance computes a WPROPS
allocation with total subsidy at most $\alpha$.

##  3 Technical Overview

Similar to previous results on the unweighted setting, our algorithm has two
main steps: we first compute a fractional WPROP allocation, in which a small
number of items are fractionally allocated; then we find a way to round the
fractional allocation to an integral one. Since some agents may have costs
exceeding their proportional share after rounding, we offer subsidies to these
agents.

For the unweighted setting, it has been shown that there exists a rounding
scheme with a total subsidy of no more than $n/4$, based on the fractional
allocation returned by the Moving Knife Algorithm. However, as pointed out by
Wu et al. [42], the algorithm fails to compute fractional WPROP allocations
when agents have different weights.333In fact, any algorithm that tries to
allocate each agent a continuous interval (as the Moving Knife Algorithm
computes) fails in the weighted setting. See [42] for a counter-example.
Hence, generalizing the results for the unweighted setting to the weighted
setting is non-trivial. For the weighted setting, they consider the Fractional
Bid-and-Take Algorithm (FBTA) and show that there exists a rounding scheme
with a total subsidy of no more than $(n-1)/2$. Whether the fractional WPROP
allocation returned by FBTA allows total subsidy strictly smaller than
$(n-1)/2$ remains unknown. In this paper, we revisit the algorithm and give a
better characterization of the fractional WPROP allocation returned by FBTA.
We show that the returned fractional allocation forms a tree structure
connecting the agents and turning the allocation integral requires a rounding
scheme on the tree. This provides a connection between the fair allocation
problem with the graph theory. Before our study, the more extensive connection
with graph theory mainly focused on comparison-based fair allocations (when
agents are regarded as nodes and the envies between agents are regarded as
edges), e.g.,  _envy graph_ and  _champion graph_ [21]. We believe that this
special tree structure, naturally decided by the fractional allocation, might
be of independent interest.

###  3.1 Fractional Bid-and-Take Algorithm

We first introduce the notation for representing a fractional allocation. We
use $x_{i}(e)\in[0,1]$ to denote the fraction of item $e$ allocated to agent
$i\in N$. We use $\mathbf{x}_{i}=\\{x_{i}(e)\\}_{e\in M}\in[0,1]^{m}$ to
denote the fractional bundle allocated to agent $i\in N$ and
$\mathbf{x}=(\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{n})$ to denote
the fractional allocation. Note that the allocation is complete if and only if
$\sum_{i\in N}x_{i}(e)=1$ for every $e\in M$. In the fractional allocation
$\mathbf{x}$, we have $c_{i}(\mathbf{x}_{i})=\sum_{e\in M}(x_{i}(e)\cdot
c_{i}(e))$ for each agent $i\in N$. We call $\mathbf{x}$ an integral
allocation if $x_{i}(e)\in\\{0,1\\}$ for every $i\in N$ and $e\in M$. To avoid
ambiguity, we consistently use $\mathbf{X}$ to refer to an integral
allocation.

##### The Algorithm.

We consider the IDO instance444The IDO input assumption here is not necessary.
For any general instance, the Fractional Bid-and-Take algorithm computes a
fractional WPROP allocation (see [42]). Here we fix the instance to be IDO for
ease of analysis for the later rounding part. with $c_{i}(e_{1})\leq
c_{i}(e_{2})\leq\cdots\leq c_{i}(e_{m})$ and allocate the items one by one in
a continuous manner. We initialize all agents to be active. For each item
$e_{j}\in M$, we continuously allocate $e_{j}$ to the active agent $i$ with
the minimum $\frac{c_{i}(e_{j})}{c_{i}(M)}$555Recall that in this paper we
normalize cost functions such that $c_{i}(e)\leq 1$ for all $i\in N,e\in M$.
When applying the different normalization s.t. $c_{i}(M)=1$ for all $i\in N$,
the algorithm corresponds to greedily allocating each item to the agent with
minimum cost on it, which is consistent with the Bid-and-Take algorithm in
[33]., until either $e_{j}$ is fully allocated or agent $i$ reaches her
proportional share, i.e., $c_{i}(\mathbf{x}_{i})=\mathsf{WPROP}_{i}$. Besides,
once an agent reaches her proportional share, we immediately inactivate her.
The algorithm terminates when all items are fully allocated. We summarize the
detailed algorithm in Algorithm 1.

Input: An IDO instance $(M,N,\mathbf{w},\mathbf{c})$ with $c_{i}(e_{1})\leq
c_{i}(e_{2})\leq\cdots\leq c_{i}(e_{m})$ for all $i\in N$

$X_{i}\leftarrow\mathbf{0}^{m},\forall i\in N$ // current fractional bundle

$A\leftarrow N$ // the set of active agents

$\mathbf{z}\leftarrow\mathbf{1}^{m}$ // remaining fraction of the items

$j\leftarrow 1$ // item to be allocated

1 while  _$j\leq m$_ do

Let $i\leftarrow\operatorname*{argmin}_{i^{\prime}\in
A}\frac{c_{i^{\prime}}(e_{j})}{c_{i^{\prime}}(M)}$; // break tie
lexicographically

2 if  _$c_{i}(\mathbf{x}_{i})+z_{j}\cdot c_{i}(e_{j}) >\mathsf{WPROP}_{i}$_
then

$x_{i}(e_{j})\leftarrow\frac{\mathsf{WPROP}_{i}-c_{i}(\mathbf{x}_{i})}{c_{i}(e_{j})}$;
// it is guaranteed that $x_{i}(e_{j})\leq 1$

3 $z_{j}\leftarrow z_{j}-x_{i}(e_{j})$, $A\leftarrow A\setminus\\{i\\}$;

4

5 else

6 $x_{i}(e_{j})\leftarrow z_{j}$, $z_{j}\leftarrow 0$, $j\leftarrow j+1$;

7

8

Output: A fractional allocation
$\mathbf{x}=(\mathbf{x}_{1},\ldots,\mathbf{x}_{n})$.

Algorithm 1 Fractional Bid and Take Algorithm (FBTA)

######  Lemma 3.1 ([42]).

The output allocation $\mathbf{x}$ is a fractional WPROP allocation.

Note that in the above WPROP allocation, the number of fractional items is at
most $n-1$, since the number of fractional items can increase only when some
agent becomes inactive, and there is at least one active agent when the
algorithm terminates. However, in the allocation, an agent might receive many
fractional items, which introduces difficulties in designing the rounding
scheme.

Toward a better understanding of the FBTA, we give an example instance of the
chores allocations to weighted agents. Throughout the paper, whenever we use
$\mathcal{I}^{*}$, we mean the instance described as follows.

######  Example 3.2.

Consider the following instance $\mathcal{I}^{*}$ given by
$(M,N,\mathbf{w},\mathbf{c})$. The agents are $N=\\{1,2,3,4,5,6\\}$, the items
are $M=\\{e_{1},e_{2},e_{3},e_{4},e_{5},e_{6}\\}$ and
$w_{1}=w_{2}=w_{3}=1/12,w_{4}=1/6,w_{5}=1/4,w_{6}=1/3$ are the weights for
agents respectively. The cost functions are additive with the costs of the
agents for each item shown in Table 1. Note that the instance is IDO and we
have $\mathsf{WPROP}_{1}=\mathsf{WPROP}_{2}=\mathsf{WPROP}_{3}=0.4$,
$\mathsf{WPROP}_{4}=0.9$, $\mathsf{WPROP}_{5}=1.5$, and
$\mathsf{WPROP}_{6}=1.7$.

| $e_{1}$ | $e_{2}$ | $e_{3}$ | $e_{4}$ | $e_{5}$ | $e_{6}$
---|---|---|---|---|---|---
agent 1 | $0.7$ | $0.7$ | $0.7$ | $0.7$ | $1$ | $1$
agent 2 | $0.8$ | $0.8$ | $0.8$ | $0.8$ | $0.8$ | $0.8$
agent 3 | $0.7$ | $0.8$ | $0.8$ | $0.8$ | $0.8$ | $0.9$
agent 4 | $0.8$ | $0.8$ | $0.8$ | $1$ | $1$ | $1$
agent 5 | $1$ | $1$ | $1$ | $1$ | $1$ | $1$
agent 6 | $0.8$ | $0.8$ | $0.8$ | $1$ | $1$ | $1$
Table 1: Example instance $\mathcal{I}^{*}$ with $6$ agents and $6$ items.

After running Algorithm 1 on instance $\mathcal{I}^{*}$, we obtain the
following fractional allocation (see Table 2), where the number in each cell
corresponds to the fraction of item the agent receives.

| $e_{1}$ | $e_{2}$ | $e_{3}$ | $e_{4}$ | $e_{5}$ | $e_{6}$
---|---|---|---|---|---|---
agent 1 | $4/7$ | $0$ | $0$ | $0$ | $0$ | $0$
agent 2 | $0$ | $1/2$ | $0$ | $0$ | $0$ | $0$
agent 3 | $3/7$ | $1/8$ | $0$ | $0$ | $0$ | $0$
agent 4 | $0$ | $3/8$ | $3/4$ | $0$ | $0$ | $0$
agent 5 | $0$ | $0$ | $0$ | $1$ | $1/2$ | $0$
agent 6 | $0$ | $0$ | $1/4$ | $0$ | $1/2$ | $1$
Table 2: The fractional allocation returned by the algorithm.

###  3.2 Item-sharing Graph and Tree Structure

In this section, we introduce a graph called _item-sharing graph_ that
characterizes the structure of the fractional allocations. Given a fractional
allocation, we say that an item is “shared” by agents $i$ and $j$ if
$x_{i}(e)>0$ and $x_{j}(e)>0$. For any item $e$ that is shared by agents
$i,j$, we can view $e$ to be an edge between $i$ and $j$, while agents are the
nodes. Naturally, such a sharing relation would induce a graph in which two
agents are connected if they share an item (see Figure 1 for an example.)
However, in such a graph, if an item is shared by many agents, a complete
graph will be formed among these agents, which introduces complications to our
rounding scheme. Furthermore, we notice that even if an item $e$ is shared by
multiple agents, the allocation happens in sequence. For each agent $i\in N$,
we denote by $e^{i}$ the last item that agent $i$ receives. If agent $i$
reaches her (weighted) proportionality and turns inactive before she takes
item $e^{i}$ completely, the algorithm will allocate (the remaining part of)
item $e^{i}$ to some active agent $j\neq i$. We call agent $j$ a _successor_
of agent $i$ if the algorithm tries to allocate the remaining part of item
$e^{i}$ to $j$.

$1$$3$$2$$4$$5$$6$ Figure 1: When simply viewing items as edges between
agents, the graph might be complex when an item is shared by more than two
agents, e.g., $e_{2}$ is (fractional) allocated to agents $2,3,4$.

######  Definition 3.3 (successor).

If when agent $i$ turns inactive the item $e^{i}$ is not fully allocated and
agent $j$ is the next agent who was chosen to take $e^{i}$, we call $j$ a
_successor_ of agent $i$ with respect to $e^{i}$.

##### Item-sharing Graph.

Let the set of nodes be the agents, where each agent has a directed edge to
its successor (if any). We abuse the notation slightly and use $e^{i}$ to
refer to the edge from agent $i$ to her successor. We call the resulting graph
$G=(N,E)$ the _item-sharing graph_ (see Figure 2 for an example). Note that
since each node has at most one outgoing edge, $G=(N,E)$ is a forest and
$|E|\leq n-1$.

$2$$e^{2}=e_{2}$$1$$e^{1}=e_{1}$$3$$e^{3}=e_{2}$$4$$e^{4}=e_{3}$$5$$e^{5}=e_{5}$$6$
Figure 2: The item-sharing graph for the returned allocation on instance
$\mathcal{I}^{*}$.

Note that each edge in $G$ also corresponds to an item that is shared by the
two endpoint agents. Moreover, it is possible that multiple edges correspond
to the same item, e.g., $e^{2}=e^{3}=e_{2}$ in the instance $\mathcal{I}^{*}$
(see Figure 2). Hence the set of edges $E$ forms a (multi)set of fractional
items. By regarding the successor of each agent as its parent, we obtain a
collection of rooted directed trees, where each agent with no outgoing edge is
a root. For example, the graph $G^{*}$ of $\mathcal{I}^{*}$ is a tree rooted
at agent $6$ (see Figure 3). We remark that an agent might have no outgoing
edge for multiple reasons: 1) the agent is active when the algorithm
terminates, or 2) the agent reaches her proportionality exactly when she fully
consumed the item $e^{i}$.

######  Observation 3.4 (Tree Structure).

Given an instance $\mathcal{I}=(M,N,\mathbf{w},\mathbf{c})$, let $\mathbf{x}$
be the (fractional) allocation returned by the FBTA and $G=(N,E)$ be the
corresponding item-sharing graph, then $G$ is a forest.

$6$$4$$5$$3$$2$$1$ Figure 3: The item-sharing graph $G^{*}$ of instance
$\mathcal{I}^{*}$ is a tree with root of agent $6$.

##### Remark.

We remark that if we construct the item-sharing graph based on a fractional
allocation returned by the Moving Knife Algorithm (in the unweighted setting),
then the constructed graph $G$ is a path since each agent has at most one
outgoing edge and one incoming edge. Hence, for any item-sharing graph $G$
that is a path, we can naturally generalize the results of [42] to the
weighted setting, which provides an (optimal) rounding scheme that bounds the
total subsidy in $n/4$.

###  3.3 Tree Splitting and Rounding

In this section, we introduce the rounding scheme to turn the fractional
allocation $\mathbf{x}$ returned by Algorithm 1 to an integral allocation
$\mathbf{X}$. We recall that the subsidy to each agent is automatically
decided by the rounded (integral) allocation $\mathbf{X}$. We call a
fractional item _rounded_ to agent $i$ if, in the integral allocation, the
item is fully allocated to agent $i$. We only round item $e$ to some agent $i$
with $x_{i}(e)>0$ in the fractional allocation $\mathbf{x}$. Our goal is to
find a rounding scheme with limited total subsidy.

Note that when the item-sharing graph $G$ is a forest, the trees in $G$ are
independent to each other. In other words, the set of fractional items of a
tree is disjoint from those of any other tree. For any two trees, we can round
them independently. Hence, in the remaining part of this paper, we assume
w.l.o.g. that the item-sharing graph $G$ is a tree (instead of a forest). We
show that by splitting the tree into (edge-disjoint) subtrees and rounding
each subtree independently, we can upper bound the total required subsidy to
achieve proportionality. In the splitting, we regard each subtree as a
collection of edges. We denote the size of each tree by the number of edges it
contains. By splitting based on edges, we obtain a collection of subtrees,
while agents may appear in multiple trees. Note that during the splitting, we
have to ensure that edges corresponding to the same item belong to the same
subtree. As a warm-up, we consider the simple splitting that splits the graph
$G$ into multiple paths, where each path contains all edges that correspond to
the same fractional item (See Figure 4 for an example).

$2$$e^{2}=e_{2}$$3$$e^{3}=e_{2}$$4$$3$$1$$e^{1}=e_{1}$$4$$e^{4}=e_{3}$$6$$5$$e^{5}=e_{5}$$6$
Figure 4: A simple splitting of the item-sharing graph of instance
$\mathcal{I}^{*}$.

We use the natural rounding scheme called threshold rounding [42] that
greedily rounds a fractional item to the agent holding the maximum fraction of
the item.

##### Threshold Rounding.

Given $\mathbf{x}$ returned by Algorithm 1, for every item $e\in M$, we use
$N(e)=\\{i\in N:x_{i}(e)>0\\}$ to denote the set of agents who gets (a
fraction of) item $e$. Note that if $|N(e)|=1$ then item $e$ is integrally
allocated to a single agent. We call an item $e$ _fractional_ if $|N(e)|\geq
2$. In the threshold rounding schemes, we round item $e$ to the agent holding
the maximum fraction of it.

The following theorem has been shown in [42]. As a warm-up towards our tree-
splitting framework, here we give an alternative proof.

######  Theorem 3.5.

There exists an algorithm that computes WPROP allocations with subsides at
most $(n-1)/2$ for the allocation of chores to a group of weighted agents
having general additive cost functions.

###### Proof.

We first split the tree into multiple paths where all edges of each path
correspond to the same fractional item. For each path (each fractional item
$e$), we use the threshold rounding that rounds $e$ to agent
$i^{*}=\operatorname*{argmax}_{i\in N}{x_{i}(e)}$, which incurs a subsidy

$\left(1-x_{i^{*}}(e)\right)\cdot c_{i^{*}}(e)\leq
1-x_{i^{*}}(e)\leq\frac{|N(e)|-1}{|N(e)|}\leq\frac{|N(e)|-1}{2}.$

Since item $e$ corresponds to $|N(e)|-1$ edges and the total number of edges
is $n-1$, by a summation of the above upper bound, we show that the total
required subsidy is at most $(n-1)/2$. ∎

As we will show, if all items are shared by exactly two agents, then it is not
very difficult to improve the above splitting (by “pairing” edges) and give a
better upper bound of $n/3-1/6$ (see Section 4). However, the existence of
items that are shared by three or more agents complicates the splitting. We
call such items _shattered items_. Roughly speaking, every shattered item puts
a constraint on how the tree can be split and may cause an increase in the
required total subsidy unless we do the splitting in a very careful way. We
will discuss the case when shattered items exist in Section 5.

##  4 Rounding Trees without Shattered Items

Recall that we assume without loss of generality that the item-sharing graph
$G=(N,E)$ is a tree, i.e., $|E|=n-1$. In this section, we consider the case
when there is no shattered items. In other words, each of the edges in $E$
corresponds to a unique fractional item that is shared by its two endpoints.
We first consider the case of $n=3$, in which the tree is a path with two
edges.

###  4.1 Three Agents with Two Fractional Items

For the unweighted setting, Wu et al. [42] showed an upper bound of $3/4$ for
the total subsidy required to round paths with length $2$. They also give an
instance with three agents for which every PROPS allocation requires a total
subsidy of at least $2/3$. In this section, we close this gap by showing a
rounding strategy that guarantees a WPROPS allocation with a total subsidy at
most $2/3$, even for the weighted case.

######  Theorem 4.1.

For a tree with size $2$, there exists a rounding scheme that guarantees a
WPROPS allocation with a total subsidy of at most $2/3$.

For an instance $\mathcal{I}=(M,N,\mathbf{w},\mathbf{c})$ where
$N=\\{1,2,3\\}$, let $e_{1}$ be the item shared by agents $1,2$ and $e_{2}$ be
the item shared by agents $2,3$ respectively. Ignoring the directions of
edges, the item-sharing graph $G$ is as Figure 5 shows.

$1$$e_{1}$$2$$e_{2}$$3$ Figure 5: The item-sharing graph for three agents.

We first introduce four different rounding schemes, that we call
$\mathsf{LL}$, $\mathsf{RR}$, $\mathsf{LR}$, and $\mathsf{RL}$. We use
$\mathsf{LL}$ to denote the scheme that rounds $e_{1}$ to agent $1$ and
$e_{2}$ to agent $2$; $\mathsf{RR}$ to denote the scheme that rounds $e_{1}$
to agent $2$ and $e_{2}$ to agent $3$; $\mathsf{LR}$ to denote the scheme that
rounds $e_{1}$ to agent $1$ and $e_{2}$ to agent $3$; $\mathsf{RL}$ to denote
the scheme that rounds both $e_{1}$ and $e_{2}$ to agent $2$. In the
following, we upper bound the required subsidies for the four rounding
schemes. We use
$s_{\mathsf{LL}},s_{\mathsf{RR}},s_{\mathsf{LR}},s_{\mathsf{RL}}$ to denote
the subsidy required in the four rounding strategies respectively. Let
$a_{1}=c_{2}(e_{1}),a_{2}=c_{2}(e_{2})$, we assume w.l.o.g. that $a_{1}\geq
a_{2}$ and let $\alpha=a_{2}/a_{1}\in(0,1]$. For any variable $x$, we use
$(x)^{+}$ to denote $\max\\{x,0\\}$.

######  Lemma 4.2.

For the four different rounding schemes, the total required subsidy can be
upper bounded as shown in the following table.

Rounding Scheme | Upper Bound for Total Subsidy
---|---
$\mathsf{LL}$ | $x_{2}(e_{1})+\left((1-x_{2}(e_{2}))\cdot\alpha-x_{2}(e_{1})\right)^{+}$
$\mathsf{RR}$ | $x_{2}(e_{2})+\left((1-x_{2}(e_{1}))-x_{2}(e_{2})\cdot\alpha\right)^{+}$
$\mathsf{LR}$ | $x_{2}(e_{1})+x_{2}(e_{2})$
$\mathsf{RL}$ | $(1-x_{2}(e_{1}))+(1-x_{2}(e_{2}))\cdot\alpha$
Table 3: Upper bounds for the subsidies required for the four different
rounding schemes.

Given the above characterized upper bounds, we are ready to show Theorem 4.1.

######  Proposition 4.3.

For any $0<x,y<1$, we have $\min\\{xy,(1-x)(1-y)\\}\leq 1/4$

###### Proof.

When $x+y\geq 1$, we have $(1-x)(1-y)\leq x\cdot(1-x)$; when $x+y<1$, we have
$xy\leq x\cdot(1-x)$. In both cases we have $\min\\{xy,(1-x)(1-y)\\}\leq
x\cdot(1-x)\leq 1/4$. ∎

Proof of Theorem 4.1:  For notational simplicity, we use $y_{1}$ and $y_{2}$
to denote $x_{2}(e_{1})$ and $x_{2}(e_{2})$. Recall from Lemma 4.2 that we
have the following bounds:

Rounding Scheme | Upper Bound for Total Subsidy
---|---
$\mathsf{LL}$ | $y_{1}+\left((1-y_{2})\cdot\alpha-y_{1}\right)^{+}$
$\mathsf{RR}$ | $y_{2}+\left((1-y_{1})-y_{2}\cdot\alpha\right)^{+}$
$\mathsf{LR}$ | $y_{1}+y_{2}$
$\mathsf{RL}$ | $(1-y_{1})+(1-y_{2})\cdot\alpha$

To prove Theorem 4.1, we discuss different cases depending on whether
$((1-y_{2})\cdot\alpha-y_{1})^{+}=0$ and $((1-y_{1})-y_{2}\cdot\alpha)^{+}=0$.
Note that $(1-y_{2})\cdot\alpha-y_{1}\leq(1-y_{1})-y_{2}\cdot\alpha$. Hence
there are three different cases to discuss.

##### Case 1.

When $((1-y_{2})\cdot\alpha-y_{1})^{+}=0$ and
$((1-y_{1})-y_{2}\cdot\alpha)^{+}=0$, we have $s_{\mathsf{LL}}\leq y_{1}$ and
$s_{\mathsf{RR}}\leq y_{2}$. By summing up
$s_{\mathsf{LL}},s_{\mathsf{RR}},s_{\mathsf{RL}}$, we have

$\displaystyle s_{\mathsf{LL}}+s_{\mathsf{RR}}+s_{\mathsf{RL}}$
$\displaystyle\leq y_{1}+y_{2}+(1-y_{1})+(1-y_{2})\cdot\alpha$
$\displaystyle\leq y_{1}+y_{2}+(1-y_{1})+(1-y_{2})=2,$

which leads to $\min\\{s_{\mathsf{LL}},s_{\mathsf{RR}},s_{\mathsf{RL}}\\}\leq
2/3.$

##### Case 2.

When $((1-y_{2})\cdot\alpha-y_{1})^{+}=0$ and
$((1-y_{1})-y_{2}\cdot\alpha)^{+}>0$, we have $s_{\mathsf{LL}}\leq y_{1}$ and
$s_{\mathsf{RR}}\leq(1-y_{1})+y_{2}\cdot(1-\alpha)$. By Proposition 4.3, we
have $\min\\{y_{2}\cdot(1-\alpha),(1-y_{2})\cdot\alpha\\}\leq 1/4$. Hence we
have

$\min\\{s_{\mathsf{RR}},s_{\mathsf{RL}}\\}\leq(1-y_{1})+\frac{1}{4}=\frac{5}{4}-y_{1}.$

By summing up $s_{\mathsf{LL}}$ and
$\min\\{s_{\mathsf{RR}},s_{\mathsf{RL}}\\}$, we have

$s_{\mathsf{LL}}+\min\\{s_{\mathsf{RR}},s_{\mathsf{RL}}\\}\leq\frac{5}{4}\quad\Rightarrow\quad\min\\{s_{\mathsf{LL}},s_{\mathsf{RR}},s_{\mathsf{RL}}\\}\leq\frac{5}{8}<\frac{2}{3}.$

##### Case 3.

Finally, we consider the case that $((1-y_{2})\cdot\alpha-y_{1})^{+}>0$ and
$((1-y_{1})-y_{2}\cdot\alpha)^{+}>0$. In this case we have
$s_{\mathsf{LL}}\leq(1-y_{2})\cdot\alpha$ and
$s_{\mathsf{RR}}\leq(1-y_{1})+y_{2}\cdot(1-\alpha)$. Then we have

$\frac{2-\alpha}{\alpha}\cdot
s_{\mathsf{LL}}+s_{\mathsf{RR}}+s_{\mathsf{LR}}=(2-\alpha)\cdot(1-y_{2})+(1+(2-\alpha)\cdot
y_{2})=3-\alpha.$

Hence we have

$\min\\{s_{\mathsf{LL}},s_{\mathsf{RR}},s_{\mathsf{LR}}\\}\leq\frac{\alpha\cdot(3-\alpha)}{2+\alpha}\leq\frac{2}{3}.$

In conclusion, for all cases, there exists a rounding scheme that guarantees
WPROPS allocation with a total subsidy of at most $2/3$.

Given Theorem 4.1, we argue that for any instance, there exists a rounding
strategy that guarantees a WPROPS allocation with a total subsidy of at most
$n/3-1/6$. Our algorithm is based on a tree splitting that splits the item-
sharing graph $G$ into subtrees with size at most two. For each subtree, we do
rounding independently and bound the subsidy by $2/3$.

###  4.2 Simple Splitting

Recall that during the splitting, we regard each tree as a collection of
edges. If we can regard two adjacent edges as a subtree, we can bound the
subsidy for the tree by $2/3$, following Theorem 4.1. Since there are $n-1$
edges, by repeatedly splitting subtrees with size two, we can bound the total
subsidy by $\lceil(n-1)/2\rceil\cdot 2/3\leq n/3$. In the following, we
introduce the Simple Splitting, which we use to split any item-sharing graph
to a collection of subtrees with size two.

Input: An item-sharing graph $G$.

1 Let $i$ be the deepest (furthest from the root) node in $G$ ;

2 Let $j$ be $i$’s parent ;

3 if  _$j$ has another child $l\neq i$_ then

4 Take edges $e^{i},e^{l}$ as one subtree ;

5

6else if  _$j$ is the root_ then

return ; // $G$ has only one edge

7

8else

9 Take edges $e^{i},e^{j}$ as one subtree ;

10

Output: A subtree $T$ with a size of two and the remaining graph $G^{\prime}$.

Algorithm 2 Simple Splitting

######  Lemma 4.4.

After repeatedly running Simple Splitting on graph $G$, we obtain a collection
of trees with size two, and at most one of them has size one.

###### Proof.

We prove the lemma by mathematical induction on the size of $G$. When $G$ has
size at most two, Simple Splitting directly outputs $G$ as the subtree. Next
we consider $n\geq 3$. Assume the induction hypothesis holds that for any tree
with size at most $n-1$. It suffices to show that in Simple Splitting, the
remaining graph (with size $n-2$) after trimming two edges is still connected.
Recall that in Simple Splitting, we start from the deepest leaf $i$ and trace
back to its parent $j$. When $j$ has another child $l$, we trim two edges
$e^{i},e^{l}$. Since $i$ is the deepest leaf, $l$ is also a leaf node and thus
the remaining graph is still connected. When $i$ is the only child of $j$, we
trim $e^{i}$ and $e^{j}$, in which case the remaining graph is also connected.
In either case, the remaining graph (with size $n-2$) is connected, and we can
use the induction hypothesis to split it into a collection of trees with size
two, and at most one of them has size one. ∎

######  Example 4.5.

Consider an instance $\mathcal{I}^{\prime}$ that has the same item-sharing
graph as Figure 3, but the items $e^{2},e^{3}$ are different. We use it as an
example to show the execution of Simple Splitting. The splitting result is
shown in Figure 6.

$6$$5$$6$$4$$3$$3$$2$$1$ Figure 6: Illustration for the execution of Simple
Splitting on $\mathcal{I}^{\prime}$.

Given Theorem 4.1, we can round each subtree independently and bound the
subsidy required for each tree by $2/3$. We show that the total subsidy can be
upper bounded by $n/3$.

######  Theorem 4.6.

Given the fractional allocation $\mathbf{x}$ with $n-1$ fractional items
returned by Algorithm 1, there exists a rounding scheme that returns an
integral WPROPS allocation with total subsidy at most $(n-1)/3$ when $n$ is
odd; at most $n/3-1/6$ when $n$ is even.

###### Proof.

Considering the item-sharing graph $G=(N,E)$ with $|E|=n-1$. Recall that in
each splitting, we get a subtree with size two. When $n$ is odd, after Simple
Splitting, we obtain exactly $(n-1)/2$ trees with size two. By Theorem 4.1,
for each tree, we can round the fractional items with a total subsidy of at
most $2/3$. Hence the total subsidy across all subtrees is at most

$\frac{2}{3}\cdot\frac{n-1}{2}=\frac{n-1}{3}.$

When $n$ is even, after Simple Splitting, we obtain $(n-2)/2$ trees with size
two and one tree with size one. For the tree with size one, we use threshold
rounding which incurs a subsidy of at most $1/2$. Hence the total subsidy
across all subtrees is at most

$\frac{2}{3}\cdot\frac{n-2}{2}+\frac{1}{2}=\frac{n-2}{3}+\frac{1}{2}=\frac{n}{3}-\frac{1}{6}.\qed$

##  5 Rounding Trees with Shattered Item

In this section, we consider case when there are at least one shattered item.
Note that the Simple Splitting proposed in Section 4 might not work in this
case when multiple edges correspond to the same fractional item. Consider the
allocation for instance $\mathcal{I}^{*}$, returned by Algorithm 1. The item-
sharing graph $G$ of the allocation is as Figure 7 shows, where the two red
edges $e^{2}$ and $e^{3}$ correspond to the same item $e_{2}$. Following the
Simple Splitting edges $e^{2}$ and $e^{1}$ would be taken as a subtree, while
$e^{3}$ and $e^{4}$ are put into another subtree. Recall that for each
subtree, we apply the rounding scheme as in Theorem 4.1 independently.
However, we notice that items $e^{2}$ and $e^{3}$ can not be rounded
independently. We define the structure like $e^{2},e^{3}$ as an _atom-path_ ,
which contains edges that cannot be separated.

######  Definition 5.1 (Atom-path).

A path $i\to\cdots\to j$ is called an _atom-path_ if all edges in the path
correspond to the same item, and the path is maximal.

$6$$4$$5$$e^{4}$$e^{5}$$3$$2$$1$$e^{2}=e_{2}$$e^{3}=e_{2}$$e^{1}$ Figure 7:
The item-sharing graph $G^{*}$ of instance $\mathcal{I}^{*}$.

We note that any atom-path has size at least $2$. When there exists an atom-
path in $G$, we need to ensure that the edges in the atom-path are not
separated into different subtrees. In the following, we introduce the
splitting and bound the total subsidy by $n/3$ as follows.

######  Lemma 5.2.

For any tree with size $z\geq 2$ such that there exists an atom-path in the
tree, there exists a rounding scheme with total subsidy bounded by $z/3$.

We remark that Lemma 5.2 directly leads to the following theorem.

######  Theorem 5.3.

Given the fractional allocation $\mathbf{x}$ with less than $n-1$ fractional
items returned by Algorithm 1, there exists a rounding scheme that returns an
integral WPROPS allocation with total subsidy at most $(n-1)/3$.

###  5.1 Atom-path splitting

In this section, we introduce the general tree splitting that we use when
there exists at least one atom-path in the item-sharing graph $G$. A naive
idea is to take the atom-path alone (with size at least two) as a subtree and
recursively do the splitting on the remaining graph (which might have multiple
connected components). For example, in Figure 7, we can split the tree into
the atom-path $\\{e^{2},e^{3}\\}$, a subtree with edges $\\{e^{4},e^{5}\\}$,
and another subtree with edge $e^{1}$. Then we can round the subtrees
independently as in Section 4. However, notice that rounding a path with size
one, e.g., item $e^{1}$ in Figure 7, may cause an increase in subsidy by
$1/2$. This may cause a problem when the length of the atom-path is large, as
each of these “hanging edges” will incur an increase of $1/2$ in the subsidy.
It would be even harder to bound the total subsidy if there are other atom-
paths in some connected components of the resulting graph after removing the
atom-path. However, we notice that there is an easy fix to the above problem:
we can simply attach the “hanging edges” to the atom-path to form a subtree,
which we call an _expanded atom-path_ (the formal definition will be given
later). On a high level, we want to do the splitting such that after taking
out an expanded atom-path, each connected component of the resulting graph is
_good_.

######  Definition 5.4 (Good Subtree).

We say that a subtree is _good_ if either it contains at least one atom-path,
or it has even size.

Note that we can bound (using mathematical induction) the total subsidy
required to round a good subtree with size $z$ by $z/3$ using Lemma 5.2 (if it
contains an atom-path) or Theorem 4.6 (if it has even size). To ensure that we
can split the tree into an expanded atom-path and a collection of good
subtrees, we check each connected component after taking out the atom-path:

  * •

If the component is a good subtree, we keep it directly and bound the required
subsidy by $1/3$ of its size, following Lemma 5.2 or Theorem 4.6.

  * •

For any connected component with odd size and without an atom-path, we show
that there exists an edge in the connected component that can be attached to
the atom-path such that after removing the edge the remaining graph is a
collection of good subtrees.

We conclude the splitting in Algorithm 3 and call it Atom-path Splitting.

Input: An item-sharing graph $G$ with atom-path.

1 Pick an arbitrary atom-path and let it be a subtree ;

2 Remove the edges of atom-path from the original tree ;

3 for  _each connected component $T$_ do

4 if  _$T$ has an atom-path or has even size_ then

5 Let $T$ be one subtree of the splitting ;

6

7 else $T$ has odd size and no atom-path

8 Let $(i,j)\in T$ be an edge such that (1) agent $i$ is in the atom-path and
(2) the subtree containing $j$ after removing $(i,j)$ has even size;

9 Attached $(i,j)$ to the atom-path;

10 Do Simple Splitting on each connected component of $T\setminus\\{(i,j)\\}$
;

11

12

Output: A collection of subtrees and the remaining graph $G^{\prime}$.

Algorithm 3 Atom-path Splitting

By running Atom-path Splitting for a graph $G$ with atom-path(s), we obtain a
collection of good subtrees and an atom-path with multiple edges attached to
it (see Example 5.5).

######  Example 5.5.

Consider a tree graph $G$ with an atom-path $(e^{1},e^{2},e^{3})$. After
cutting the atom-path we obtain four subtrees $T_{1},T_{2},T_{3},T_{4}$ (see
Figure 8). By definition $T_{2}$ and $T_{4}$ are good subtrees.

$1$$2$$3$$4$$T_{1}$$T_{2}$$T_{3}$$T_{4}$ Figure 8: An example tree with an
atom-path $(e^{1},e^{2},e^{3})$.

Since $T_{3}$ has size one, we can simply attached the edge to the atom-path.
Observe that $T_{1}$ also has odd size. Hence there must exits an edge (the
edge with blue color in Figure 8) that is incident to node $1$ whose removal
results in a collection of even-size subtrees. The splitting result is as
follows (see Figure 9).

$1$$2$$3$$4$$1$$2$$4$ Figure 9: The splitting result of Figure 8.

Note that each node in the atom-path is attached at most one edge. We call the
resulting structure an _expanded atom-path_.

######  Definition 5.6 (Expanded Atom-path).

We call a subtree an _expanded atom-path_ if it is composed of an atom-path
and a collection of attached edges, where each node in the atom-path is
incident to at most one attached edge.

######  Lemma 5.7.

For any graph $G$ containing (at least) one atom-path, Algorithm 3 splits $G$
into an expanded atom-path and a collection of good subtrees.

###### Proof.

To prove the lemma, it suffices to consider the else condition in line $6$ as
in other cases the subtree $T$ is a good tree. Let $T$ be a subtree with odd
size and no atom-path. Let $i$ be the node in both the atom-path and $T$. Let
$(i,j_{1}),\ldots,(i,j_{t})$ be the edges incident to $i$ in $T$, and let
$T^{\prime}_{x}$ be the subtree containing $j_{x}$ after the hypothetical
deletion of edge $(i,j_{x})$. Since $T$ has odd size, at least one of
$T^{\prime}_{1},\ldots,T^{\prime}_{t}$ must have even size. Suppose
$T^{\prime}_{x}$ has even size. We attach edge $(i,j_{x})$ to the atom-path
and delete it from $T$. Then we obtain two subtrees: $T^{\prime}_{x}$ and
$T\setminus(T^{\prime}_{x}\cup{(i,j_{x})})$, both of which have even size.
Since we attach at most one edge of each node of the atom-path, the result of
the splitting is an expanded atom-path and a collection of good subtrees. ∎

Recall that we can upper bound the subsidy required to round a good subtree
with $z$ edges by $z/3$. To upper bound the total subsidy of a graph with at
least one atom-path, it remains to bound the subsidy required to round an
expanded atom-path.

######  Lemma 5.8.

For any expanded atom-path consisting of an atom-path with $k$ edges and
$h\leq k+1$ attached edges, there exists a rounding scheme with total subsidy
bounded by $(k+h)/3$.

We defer the proof of Lemma 5.8 to Section 5.2. Given Lemma 5.8, we are ready
to prove Lemma 5.2.

######  Lemma 5.2.

For any tree with size $z\geq 2$ such that there exists an atom-path in the
tree, there exists a rounding scheme with total subsidy bounded by $z/3$.

Proof of Lemma 5.2:  We prove the lemma by induction on $z$. We first consider
the base case of a tree with $z=2$ edges, which is an atom-path. In such case,
we only have one fractional item that is shared by three agents. Using
threshold rounding, we round the item to the agent holding the maximum
fraction of it, which incurs a subsidy of at most $2/3$. Hence the lemma holds
for the base case.

Now suppose that for any tree with edges $z^{\prime}<z$ containing at least
one atom-path, there exists a rounding scheme with total subsidy at most
$z^{\prime}/3$. We consider a tree with $z$ edges containing at least one
atom-path. Following Lemma 5.7, given any tree with at least one atom-path,
the Atom-path splitting returns an expanded atom-path and a collection of
subtrees that either contains an atom-path or has even size. For the former
case we can bound its required subsidy by $z^{\prime}/3$, where $z^{\prime}$
is the number of edges it contains, by induction hypothesis. For the later
case we can also bound the required subsidy by $z^{\prime}/3$ by Simple
Splitting and Theorem 4.6. Finally, by Lemma 5.8, for expanded atom-path we
can also bound the required subsidy by $1/3$ of its size. Since the summation
of the size of all good subtrees and the expanded atom-path is $z$, the total
subsidy required is at most $z/3$, and the lemma follows.

###  5.2 Expanded Atom-path

In this section, we consider the expanded atom-paths and prove Lemma 5.8. We
first define some notation. Fix any expanded atom-path $T$, we assume that the
atom-path has $k\geq 2$ edges, which correspond to the one single item denoted
by $e_{0}$. We denote the nodes in the atom-path by agents $1,\ldots,k+1$,
where agent $i+1$ is the successor of agent $i$, for all $i=1,2,\ldots,k$. We
denote the edge attached to agent $i$ by $e_{i}$. When there is no attached
edge to agent $i$, we define $e_{i}=\bot$. We call agents $1,2,\ldots,k+1$ the
_atom-path agents_ and the other agents the _attached agents_. We use $h\leq
k+1$ to denote the number of attached edges/agents in the expanded atom-path.
For each item $e_{i}$, where $i\in\\{1,\ldots,k+1\\}$, we use $y_{i}$ to
denote the fraction of item $e_{i}$ held by the corresponding attached agent,
i.e., $y_{i}=1-x_{i}(e_{i})$. For all $i\in\\{1,\ldots,k+1\\}$, when there is
no ambiguity, we use $x_{i}$ to denote $x_{i}(e_{0})$ for convenience.

$1$$2$$3$$4$$5$$e_{5}$$e_{3}$$e_{2}$ Figure 10: Example of an expanded atom-
path with $k=4$ and $h=3$, where the red edges correspond to item $e_{0}$, the
three blue edges correspond to items $e_{2},e_{3}$ and $e_{5}$ respectively.

Now we are ready to upper bound the subsidy required for expanded atom-paths.
We prove Lemma 5.8 by giving the following arguments for different types of
expanded atom-paths respectively.

######  Lemma 5.9.

For any expanded atom-path with $h\leq k\cdot(2-\frac{6}{k+1})$, there exists
a rounding scheme with total subsidy at most $(k+h)/3$.

######  Lemma 5.10.

For any expanded atom-path with $h=k+1$, there exists a rounding scheme with
total subsidy at most $(k+h)/3$.

######  Lemma 5.11.

For any expanded atom-path with $h=k$, there exists a rounding scheme with
total subsidy at most $(k+h)/3$.

######  Lemma 5.12.

For any expanded atom-path with $2\leq k\leq 3$ and $h=k-1$, there exists a
rounding scheme with total subsidy at most $(k+h)/3$.

We first show that given the above arguments, we can prove Lemma 5.8.

######  Lemma 5.8.

For any expanded atom-path consisting of an atom-path with $k$ edges and
$h\leq k+1$ attached edges, there exists a rounding scheme with total subsidy
bounded by $(k+h)/3$.

Proof of Lemma 5.8:  Recall that $h\leq k+1$. Following Lemma 5.10 and Lemma
5.11, for all the atom-paths with $h\in\\{k+1,k\\}$, there exists a rounding
scheme with total subsidy bounded by $(k+h)/3$. It can be verified that
$k-1\leq k\cdot(2-\frac{6}{k+1})$ holds for all $k\geq 4$. Hence for all
$k\geq 4$ and $h\leq k-1$ we can bound the total subsidy by $(k+h)/3$ using
Lemma 5.9. Furthermore, it can be verified that $k-1\leq
k\cdot(2-\frac{6}{k+1})$ holds when $k=3,h\leq 1$, and when $k=2,h=0$. Hence
it remains to consider the cases that $k=3,h=2$; or $k=2,h=1$, which are
covered by Lemma 5.12. In conclusion, for all types of expanded atom-path,
there exists a rounding scheme with total subsidy at most $(k+h)/3$.

It remains to prove Lemma 5.9, 5.10, 5.11 and 5.12. We use a charging argument
that charges money to the fractional items $e_{0},e_{1},\ldots,e_{k+1}$: we
charge each fractional item $e_{i}$ an amount of money $p_{i}$. In the
following analysis, we focus on bounding the money we charge for each item
$e_{i}$ and we show that the total charge to the fractional items is
sufficient to pay for the incurred subsidy.

######  Lemma 5.9.

For an expanded atom-path with $h\leq k\cdot(2-\frac{6}{k+1})$, there exists a
rounding scheme with total subsidy at most $(k+h)/3$.

###### Proof.

We consider the threshold rounding that rounds each item to the agent that
holds the maximum fraction of it. For item $e_{0}$, we round it to
$i^{*}=\operatorname*{argmax}_{1\leq i\leq k+1}x_{i}$. For each item $e_{i}$,
we round it to agent $i$ if and only if $y_{i}\leq 1/2$. We charge item
$e_{0}$ an amount of money $p_{0}=\frac{k}{k+1}$. For each item $e_{i}$ we
charge it an amount of money $p_{i}=1/2$ if and only if item $e_{i}\neq\bot$.
For completeness, we let $p_{i}=0$ when $e_{i}=\bot$.

Since the inclusion of item $e_{0}$ to agent $i^{*}$ incurs an increase in
subsidy by at most

$(1-x_{i^{*}})\cdot c_{i^{*}}(e_{0})\leq 1-x_{i^{*}}\leq\frac{k}{k+1}=p_{0},$
(1)

and the inclusion of item $e_{i}$ for $i\neq 0$ incurs an increase in subsidy
by at most $1/2$, the charged money is sufficient to pay for the subsidy. To
bound the required subsidy by $(k+h)/3$, it remains to prove that

$\sum_{0\leq i\leq k+1}p_{i}=\frac{k}{k+1}+\frac{h}{2}\leq\frac{k+h}{3},$

which is equivalent to $h\leq k\cdot(2-\frac{6}{k+1})$ as stated in the lemma.
∎

Notice that in the above analysis, rounding item $e_{0}$ to agent $i^{*}$
releases a space of $x_{i}\cdot c_{i}(e_{0})$ for all agent $i\neq i^{*}$,
which should be helpful in reducing the subsidy requirement for the attached
edges. In the following, we make use of this observation to prove Lemma 5.10,
5.11 and 5.12.

######  Observation 5.13.

For any agent $i\leq k$, $c_{i}(e_{0})\geq c_{i}(e_{i})$.

###### Proof.

We remark that for any agent $i\leq k$, $e_{0}$ is the last (fraction of) item
that she receives. Otherwise, agent $i$ would not have a successor with
respect to $e_{0}$. In other words, for any agent $i$, the event that $i$
takes (a fraction of) item $e_{i}$ happens before the event that $i$ takes (a
fraction of) item $e_{0}$. Recall that we consider IDO instances and allocate
items with increasing cost in Algorithm 1, Hence, for any agent $i\leq k$, we
have $c_{i}(e_{0})\geq c_{i}(e_{i})$. ∎

Note that the above observation might not hold for agent $k+1$: it is possible
that $e^{k+1}=e_{k+1}\neq e_{0}$. In this case we have $c_{k+1}(e_{0})\leq
c_{k+1}(e_{k+1})$. Given the above observation, for all agent $i\neq i^{*}$
that does not receive item $e_{0}$, when rounding item $e_{i}$ we should
somehow give agent $i$ a slightly higher priority (compared with the other
endpoint) as rounding $e_{i}$ to agent $i$ incurs a subsidy $(y_{i}\cdot
c_{i}(e_{i})-x_{i}\cdot c_{i}(e_{0}))^{+}\leq(y_{i}-x_{i})^{+}$. We formalize
this idea into the following rounding scheme.

##### Biased Threshold Rounding.

Given an attached edge $e_{i}$, if $y_{i}-x_{i}\leq 1-y_{i}$, we round item
$e_{i}$ to agent $i$; otherwise we round $e_{i}$ to the attached agent.

######  Proposition 5.14.

For any agent $i\in\\{1,2,\ldots,k+1\\}$ that does not receive item $e_{0}$
and satisfies $c_{i}(e_{0})\geq c_{i}(e_{i})$, the subsidy incurred by
rounding $e_{i}$ using the biased threshold rounding is at most $(1-x_{i})/2$.

###### Proof.

By the biased threshold rounding, if $y_{i}-x_{i}\leq 1-y_{i}$ then we round
item $e_{i}$ to agent $i$, which incurs a subsidy of $(y_{i}\cdot
c_{i}(e_{i})-x_{i}\cdot c_{i}(e_{0}))^{+}\leq(y_{i}-x_{i})^{+}$. Otherwise, we
round item $e_{i}$ to the other agent which incurs an increase in subsidy by
at most $(1-y_{i})$. Hence the incurred subsidy can be bounded by

$\min\\{1-y_{i},(y_{i}-x_{i})^{+}\\}\leq\frac{1-y_{i}+y_{i}-x_{i}}{2}=\frac{1-x_{i}}{2}.\qed$

######  Lemma 5.10.

For an expanded atom-path with $h=k+1$, there exists a rounding scheme with
total subsidy at most $(k+h)/3$.

###### Proof.

Recall from Observation 5.13 that we have $c_{i}(e_{0})\geq c_{i}(e_{i})$ for
all $i\in{1,2,\ldots,k}$. Unfortunately, we can not guarantee this for agent
$k+1$. In the following, we present different rounding schemes depending on
whether $c_{k+1}(e_{0})\geq c_{k+1}(e_{k+1})$. We first consider the case when
$c_{k+1}(e_{0})<c_{k+1}(e_{k+1})$.

In this case, we round $e_{0}$ to agent $k+1$ and round items
$e_{1},\ldots,e_{k}$ using the biased threshold rounding. By Proposition 5.14,
rounding each $e_{i}$ incurs a subsidy of at most $(1-x_{i})/2$, for all
$i\in{1,2,\ldots,k}$. Next, we show that at least one of the following
rounding schemes gives a total subsidy of at most $(k+h)/3$:

  * •

Scheme 1. We round item $e_{k+1}$ to the attached agent;

  * •

Scheme 2. We round item $e_{k+1}$ to agent $k+1$.

Note that rounding item $e_{k+1}$ to the attached agent release a space of
$(1-y_{k+1})\cdot c_{k+1}(e_{k+1})$ for agent $k+1$. Hence the incurred
subsidy by rounding $e_{0}$ in scheme 1 is

$\displaystyle((1-x_{k+1})\cdot c_{k+1}(e_{0})-(1-y_{k+1})\cdot
c_{k+1}(e_{k+1}))^{+}$ $\displaystyle\leq$
$\displaystyle((y_{k+1}-x_{k+1})\cdot c_{k+1}(e_{k+1}))^{+}$
($c_{k+1}(e_{0})<c_{k+1}(e_{k+1})$) $\displaystyle\leq$
$\displaystyle(y_{k+1}-x_{k+1})^{+}.$ ($c_{k+1}(e_{k+1})\leq 1$)

Since we need to compensate at most $1-y_{k+1}$ to the attached agent for
receiving $e_{k+1}$, the total subsidy required in scheme 1 can be upper
bounded by

$\sum_{1\leq i\leq k}\frac{1-x_{i}}{2}+(y_{k+1}-x_{k+1})^{+}+(1-y_{k+1}).$ (2)

Similarly, for scheme 2, the total required subsidy can be upper bounded by

$\sum_{1\leq i\leq k}\frac{1-x_{i}}{2}+(1-x_{k+1})+y_{k+1}.$ (3)

When $y_{k+1}-x_{k+1}\geq 0$, it is easy to find that Equation (2) dominates
Equation (3) (gives a smaller upper bound). We can upper bound the subsidy for
scheme 1 as follows.

$\displaystyle\|s\|_{1}$ $\displaystyle\leq(1-x_{k+1})+\sum_{1\leq i\leq
k}\frac{1-x_{i}}{2}$ (By Equation (2) and $y_{k+1}-x_{k+1}\geq 0$)
$\displaystyle=\sum_{1\leq i\leq k}x_{i}+\frac{k}{2}-\sum_{1\leq i\leq
k}\frac{x_{i}}{2}$ ($1-x_{k+1}=\sum_{1\leq i\leq k}x_{i}$)
$\displaystyle=\frac{k}{2}+\sum_{1\leq i\leq
k}\frac{x_{i}}{2}\leq\frac{k+1}{2}.$ ($\sum_{1\leq i\leq k}x_{i}\leq 1$)

Next we consider the case that $y_{k+1}-x_{k+1}<0$. We have

$\displaystyle\text{For scheme 1, }\|s\|_{1}$ $\displaystyle\leq\sum_{1\leq
i\leq k}\frac{1-x_{i}}{2}+(1-y_{k+1});$ (By Equation (2))
$\displaystyle\text{For scheme 2, }\|s\|_{1}$ $\displaystyle\leq\sum_{1\leq
i\leq k}\frac{1-x_{i}}{2}+(1-x_{k+1})+y_{k+1}.$ (By Equation (3))

Summing up the above two upper bounds, we have

$\displaystyle\sum_{1\leq i\leq
k}\frac{1-x_{i}}{2}+(1-y_{k+1})+(1-x_{k+1})+\sum_{1\leq i\leq
k}\frac{1-x_{i}}{2}+y_{k+1}$ $\displaystyle=$ $\displaystyle\sum_{1\leq
i\leq{k+1}}(1-x_{i})+1=k+2-\sum_{1\leq i\leq{k+1}}x_{i}=k+1$ ($\sum_{1\leq
i\leq{k+1}}x_{i}=1$)

Therefore, at least one of the two rounding schemes requires a total subsidy
of at most

$\frac{k+1}{2}\leq\frac{2k+1}{3}=\frac{k+h}{3},$

where the inequality holds for all $k\geq 2$.

Next, we consider the case when $c_{k+1}(e_{0})\geq c_{k+1}(e_{k+1})$.

Following Observation 5.13, in this case we have $c_{i}(e_{0})\geq
c_{i}(e_{i})$ for all $i\leq\\{1,2,\ldots,k+1\\}$ and can assume w.l.o.g. that
$x_{1}\leq x_{2}\leq\cdots\leq x_{k+1}$. We first round item $e_{0}$ to agent
$k+1$, who holds the maximum fraction of $e_{0}$. Let
$\alpha=c_{k+1}(e_{k+1})$. As before, by using biased threshold rounding to
round items $e_{1},\ldots,e_{k}$, we can bound the required subsidy by
$\sum_{i=1}^{k}\frac{1-x_{i}}{2}$. Again, we consider the following two
rounding schemes:

  * •

Scheme 1. We round item $e_{k+1}$ to the attached agent;

  * •

Scheme 2. We round item $e_{k+1}$ to agent $k+1$.

Note that rounding item $e_{k+1}$ to the attached agent release a space of
$(1-y_{k+1})\cdot\alpha$ for agent $k+1$. Hence the subsidy required in scheme
1 can be upper bounded by

$\sum_{1\leq i\leq
k}\frac{1-x_{i}}{2}+((1-x_{k+1})-(1-y_{k+1})\cdot\alpha)^{+}+(1-y_{k+1}).$ (4)

For scheme 2, the total required subsidy can be upper bounded by

$\sum_{1\leq i\leq k}\frac{1-x_{i}}{2}+(1-x_{k+1})+y_{k+1}\cdot\alpha.$ (5)

When $(1-x_{k+1})-(1-y_{k+1})\cdot\alpha\geq 0$, the subsidy required in
scheme 1 can be upper bounded by

$\sum_{1\leq i\leq k}\frac{1-x_{i}}{2}+(1-x_{k+1})+(1-y_{k+1})\cdot(1-\alpha)$
(6)

By Proposition 4.3, we have

$\min\\{(y_{k+1}\cdot\alpha),(1-y_{k+1})\cdot(1-\alpha)\\}\leq 1/4.$ ($0\leq
y_{k+1}\leq 1$ and $0\leq\alpha\leq 1$)

Hence the minimum of (5) and (6) can be bounded by (recall that
$x_{k+1}=\max_{1\leq i\leq k+1}\\{x_{i}\\}$)

$\displaystyle\sum_{1\leq i\leq
k}\frac{1-x_{i}}{2}+(1-x_{k+1})+\frac{1}{4}=\sum_{1\leq i\leq
k}\frac{1-x_{i}}{2}+\sum_{1\leq i\leq k}x_{i}+\frac{1}{4}$ $\displaystyle=$
$\displaystyle\frac{k}{2}+\frac{1}{2}\cdot\sum_{1\leq i\leq
k}x_{i}+\frac{1}{4}\leq\frac{k}{2}+\frac{k}{2k+2}+\frac{1}{4}=\frac{2k^{2}+5k+1}{4k+4}\leq\frac{2k+1}{3}=\frac{k+h}{3},$

where the last inequality holds for all $k\geq 2$.

Now suppose that $(1-x_{k+1})-(1-y_{k+1})\cdot\alpha<0$. We have the total
required subsidy for scheme 1 can be bounded by

$\sum_{1\leq i\leq k}\frac{1-x_{i}}{2}+(1-y_{k+1}).$ (7)

Summing up the upper bounds for scheme 1 (Equation (7)) and scheme 2 (Equation
(5)), the total subsidy required by the two rounding schemes combined is at
most

$\displaystyle\sum_{1\leq i\leq k}\frac{1-x_{i}}{2}+(1-y_{k+1})+\sum_{1\leq
i\leq k}\frac{1-x_{i}}{2}+(1-x_{k+1})+y_{k+1}\cdot\alpha$ $\displaystyle=$
$\displaystyle\sum_{1\leq i\leq{k+1}}(1-x_{i})+1+y_{k+1}\cdot\alpha-y_{k+1}$
$\displaystyle\leq$ $\displaystyle\sum_{1\leq
i\leq{k+1}}(1-x_{i})+1=k+2-\sum_{1\leq i\leq{k+1}}x_{i}=k+1.$

Therefore, at least one of the two rounding schemes requires a total subsidy
at most $(k+1)/2$, which is not larger than $(k+h)/3$ for all $k\geq 2$. ∎

######  Lemma 5.11.

For an expanded atom-path with $h=k$, there exists a rounding scheme with
total subsidy at most $(k+h)/3$.

###### Proof.

When $h=k$, there exists an agent $j$ in the atom-path with no edge attached,
i.e., $e_{j}=\bot$. We first consider the case that $j\neq k+1$ and
$c_{k+1}(e_{0})<c_{k+1}(e_{k+1})$.

  * •

Scheme 1. We round item $e_{0}$ to agent $k+1$ and round item $e_{k+1}$ to the
attached agent. We use the biased threshold rounding for other items $e_{i}$
s.t. $1\leq i\leq k$. By a similar argument as in Lemma 5.10, the total
subsidy required can be upper bounded by

$\sum_{1\leq i\leq
k}\frac{1-x_{i}}{2}-\frac{1-x_{j}}{2}+(y_{k+1}-x_{k+1})^{+}+(1-y_{k+1}).$ (8)

  * •

Scheme 2. We round item $e_{0}$ to agent $j$ and item $e_{k+1}$ by threshold
rounding. For any other item $e_{i}$ s.t. $1\leq i\leq k$, we use the biased
threshold rounding. The total subsidy can be upper bounded by

$\sum_{1\leq i\leq
k}\frac{1-x_{i}}{2}-\frac{1-x_{j}}{2}+(1-x_{j})+\frac{1}{2}.$ (9)

Summing up the above two upper bounds, we have

$\displaystyle\sum_{1\leq i\leq
k}(1-x_{i})+(y_{k+1}-x_{k+1})^{+}+(1-y_{k+1})+\frac{1}{2}$ $\displaystyle=$
$\displaystyle\frac{k}{2}-\sum_{1\leq i\leq
k}x_{i}+(y_{k+1}-x_{k+1})^{+}+(1-y_{k+1})+\frac{1}{2}$ $\displaystyle=$
$\displaystyle k+x_{k+1}+(y_{k+1}-x_{k+1})^{+}-y_{k+1}+\frac{1}{2}$
$\displaystyle=$ $\displaystyle k+\frac{1}{2}.$ (When $y_{k+1}-x_{k+1}\geq 0$)

Hence when $y_{k+1}-x_{k+1}\geq 0$, at least one of the two rounding schemes
requires a total subsidy at most $(2k+1)/4$, which is no larger than
$\frac{2k}{3}=\frac{k+h}{3}$ for all $k\geq 2$.

When $y_{k+1}-x_{k+1}<0$, Equation (8) becomes

$\sum_{1\leq i\leq k}\frac{1-x_{i}}{2}-\frac{1-x_{j}}{2}+(1-y_{k+1})$ (10)

We introduce one more rounding scheme.

  * •

Scheme 3. We round items $e_{0}$ to $e_{j}$ and $e_{k+1}$ to agent $k+1$. For
any other item $e_{i}$ s.t. $1\leq i\leq k$, we use the biased threshold
rounding. The total subsidy can be bounded by

$\sum_{1\leq i\leq
k}\frac{1-x_{i}}{2}-\frac{1-x_{j}}{2}+(1-x_{j})+y_{k+1}-x_{k+1}\cdot\alpha$
(11)

By summing up Equations (10) and (11), we have

$\displaystyle\sum_{1\leq i\leq
k}(1-x_{i})+(1-x_{k+1}\cdot\alpha)=k+(1-\sum_{1\leq i\leq
k}x_{i})-x_{k+1}\cdot\alpha=k+x_{k+1}-x_{k+1}\cdot\alpha.$

To show that one of the two rounding schemes requires a total subsidy of at
most $\frac{k}{2}+\frac{1}{4}\leq\frac{2k}{3}$, it suffices to show that
$x_{k+1}\cdot(1-\alpha)\leq\frac{1}{2}$. Assume otherwise
$x_{k+1}\cdot(1-\alpha)>\frac{1}{2}$. Following Proposition 4.3, we have
$(1-x_{k+1})\cdot\alpha<\frac{1}{4}$. Consider the rounding scheme that rounds
item $e_{0}$ to agent $k+1$ and uses threshold rounding to any other items. It
can be verified that the total subsidy required is at most

$(1-x_{k+1})\cdot\alpha+\frac{1}{2}\cdot
k\leq\frac{k}{2}+\frac{1}{4}\leq\frac{2k}{3}.$

Hence, for the case that $j\neq k+1$ and $c_{k+1}(e_{0})<c_{k+1}(e_{k+1})$,
there always exists a rounding scheme with total subsidy bounded by $(k+h)/3$.

Next we consider the case that $j=k+1$ or $c_{k+1}(e_{k+1})\geq
c_{k+1}(e_{0})$, in which we have $c_{i}(e_{i})\leq c_{i}(e_{0})$ for all
$i\neq j$. We round item $e_{0}$ to agent $j$ and use the biased threshold
rounding to round every item $e_{i}$ s.t. $i\neq j$. Following similar
analysis as shown before, total subsidy required is at most

$\sum_{i\in[k+1],i\neq
j}\frac{1-x_{i}}{2}+(1-x_{j})=\frac{k}{2}+\frac{1-x_{j}}{2}.$

To ensure that $\frac{k}{2}+\frac{1-x_{j}}{2}$, we need $x_{j}\geq
1-\frac{k}{3}$, which naturally holds for all $k\geq 3$.

It remains to consider the case that $k=2$ and
$x_{j}<1-\frac{2}{3}=\frac{1}{3}$. We assume w.l.o.g. that
$x_{3}=\max\\{x_{1},x_{2},x_{3}\\}$ and we round $e_{0}$ to agent $3$. Note
that $j\neq 3$ since $x_{3}\geq 1/3$. Let $\alpha=c_{3}(e_{3})$. We consider
two rounding schemes that both round item $e_{0}$ to agent $3$ but differ in
the rounding of item $e_{3}$. Let $i$ be the agent other than $j$ and $3$, and
we use the biased threshold rounding to round item $e_{i}$. Following
Proposition 5.14, the total subsidy required can be upper bounded by

$\displaystyle\begin{cases}\cfrac{1-x_{i}}{2}+((1-x_{3})-(1-y_{3})\alpha)^{+}+(1-y_{3}),&\text{if
we round $e_{3}$ to the attached agent}\\\
\cfrac{1-x_{i}}{2}+(1-x_{3})+y_{3}\cdot\alpha,&\text{if we round $e_{3}$ to
agent $3$}.\end{cases}$

When $(1-x_{3})-(1-y_{3})\alpha\geq 0$, following Proposition 4.3, the minimum
of two bounds is at most

$\displaystyle\frac{1-x_{i}}{2}+(1-x_{3})+\frac{1}{4}=\frac{5}{4}+\frac{1-x_{3}-x_{i}}{2}-\frac{x_{3}}{2}=\frac{5}{4}+\frac{x_{j}}{2}-\frac{x_{3}}{2}\leq\frac{5}{4}\leq\frac{4}{3}.$

Hence at least one of the two rounding schemes with total subsidy bounded by
$4/3=2k/3$.

When $(1-x_{3})-(1-y_{3})\alpha<0$, the sum of the above two bounds is

$\displaystyle(1-x_{i})+(1-x_{3})+(1-y_{3})+y_{3}\cdot\alpha\leq
3-x_{1}-x_{3}\leq 2+x_{j}\leq\frac{7}{3}.$

Hence at least one of the two rounding schemes requires subsidy at most
$7/6<4/3=2k/3$. ∎

######  Lemma 5.12.

For any expanded atom-path with $2\leq k\leq 3$ and $h=k-1$, there exists a
rounding scheme with total subsidy at most $(k+h)/3$.

###### Proof.

For $k=3$, the upper bound is $\frac{2k-1}{3}=\frac{5}{3}$. Note that there
exists two agents $i,j$ such that ${e_{i}}={e_{j}}=\bot$. We first consider
the case that $k+1=4\in\\{i,j\\}$. Let $p,q$ be the two agents other than
$i,j$. Consider the rounding scheme that rounds $e_{0}$ to
$\operatorname*{argmax}\\{x_{i},x_{j}\\}$, say agent $i$. Applying the biased
threshold rounding to items $e_{p}$ and $e_{q}$, we can bound the total
subsidy required by

$\frac{1-x_{p}}{2}+\frac{1-x_{q}}{2}+(x_{p}+x_{q}+x_{j})=1+\frac{x_{p}+x_{q}+2\cdot
x_{j}}{2}\leq 1+\frac{x_{p}+x_{q}+x_{j}+x_{i}}{2}=\frac{3}{2}.$

Now suppose that $k+1=4\notin\\{i,j\\}$. Let $p$ be the agent other than
$i,j,4$. Again, we round $e_{0}$ to $\operatorname*{argmax}\\{x_{i},x_{j}\\}$,
say agent $i$, and apply the biased threshold rounding to round item $e_{p}$.
By applying the threshold rounding for item $e_{4}$, we can upper bound the
total subsidy by

$\frac{1-x_{p}}{2}+1-x_{i}+\frac{1}{2}\leq\frac{3}{2}+\frac{1-x_{p}-x_{i}-x_{j}}{2}=\frac{3+x_{4}}{2}.$

Note that $\frac{3+x_{4}}{2}\leq\frac{5}{3}$ holds when $x_{4}\leq 1/3$.
Assume otherwise that $x_{4}>1/3$. We round $e_{0}$ to agent $4$ and use the
biased threshold rounding for item $e_{p}$. The total subsidy can be upper
bounded by

$\begin{cases}\frac{1-x_{p}}{2}+((1-x_{4})-(1-y_{4})\cdot\alpha))^{+}+(1-y_{4}),\quad&\text{if
we round $e_{4}$ to agent $4$}\\\
\frac{1-x_{p}}{2}+(1-x_{4})+y_{4}\cdot\alpha,&\text{if we round $e_{4}$ to the
attached agent}.\end{cases}$

When $(1-x_{4})-(1-y_{4})\cdot\alpha\geq 0$, by Proposition 4.3, the minimum
of two upper bounds is at most

$\frac{1-x_{p}}{2}+(1-x_{4})+\frac{1}{4}\leq\frac{3}{4}+(1-x_{4})\leq\frac{3}{4}+\frac{1}{3}\leq\frac{5}{3}.$

When $(1-x_{4})-(1-y_{4})\cdot\alpha<0$, the first upper bound becomes

$\frac{1-x_{p}}{2}+(1-y_{4})\leq\frac{3}{2}\leq\frac{5}{3}.$

For $k=2$, the upper bound is $\frac{2k-1}{3}=1$. Note that there exist two
agents $i,j$ such that ${e_{i}}={e_{j}}=\bot$. Let $p$ be the agent other than
$i,j$ (who has an attached edge). We first consider the case that $p\neq k+1$.
We round $e_{0}$ to $\operatorname*{argmax}\\{x_{i},x_{j}\\}$, say agent $i$,
and apply the biased threshold rounding for items $e_{p}$. The total subsidy
can be upper bounded by

$\frac{1-x_{p}}{2}+(x_{j}+x_{p})=\frac{1+x_{p}+2\cdot
x_{j}}{2}\leq\frac{1+x_{p}+x_{j}+x_{i}}{2}=1.$

Consider otherwise that $p=k+1$, where the atom-path reduces to a line.
Following Theorem 4.10 in [42], there exists a rounding scheme that requires a
total subsidy of at most $n/4=1$. ∎

##  6 Conclusion and Open Problems

In this work we revisit the problem of computing weighted proportional
allocations with subsidy, and propose a rounding scheme for the fractional
bid-and-take algorithm based on tree splitting. We show that for any instance
with $n$ agents with general weights, we can compute a weighted proportional
allocation that requires a total subsidy of at most $n/3$. Our work leaves
several natural problems open. The most fascinating open problem is to
investigate the existence of algorithms that guarantee weighted
proportionality requiring a total subsidy of at most $n/4$. We conjecture that
the fractional bid-and-take algorithm admits such rounding schemes. It would
also be interesting to study other fairness notions like Maximin Share or
AnyPrice Share and see if we can further lower the subsidy requirement.
Finally, we believe that it would be interesting to apply the tree
composition-based framework to other fair allocation settings, e.g., the Best
of Both Worlds setting, that require rounding fractional allocations.

## References

  * [1] G. Amanatidis, H. Aziz, G. Birmpas, A. Filos-Ratsikas, B. Li, H. Moulin, A. A. Voudouris, and X. Wu.  Fair division of indivisible goods: Recent progress and open questions.  Artif. Intell., 322:103965, 2023.
  * [2] H. Aziz.  Achieving envy-freeness and equitability with monetary transfers.  In AAAI, pages 5102–5109. AAAI Press, 2021.
  * [3] H. Aziz, I. Caragiannis, A. Igarashi, and T. Walsh.  Fair allocation of indivisible goods and chores.  Auton. Agents Multi Agent Syst., 36(1):3, 2022.
  * [4] H. Aziz, H. Chan, and B. Li.  Weighted maxmin fair share allocation of indivisible chores.  In IJCAI, pages 46–52. ijcai.org, 2019.
  * [5] H. Aziz, B. Li, H. Moulin, and X. Wu.  Algorithmic fair allocation of indivisible items: a survey and new questions.  SIGecom Exch., 20(1):24–40, 2022.
  * [6] H. Aziz, B. Li, and X. Wu.  Approximate and strategyproof maximin share allocation of chores with ordinal preferences.  Mathematical Programming, pages 1–27, 2022.
  * [7] H. Aziz, H. Moulin, and F. Sandomirskiy.  A polynomial-time algorithm for computing a pareto optimal and almost proportional allocation.  Oper. Res. Lett., 48(5):573–578, 2020.
  * [8] H. Aziz, G. Rauchecker, G. Schryen, and T. Walsh.  Algorithms for max-min share fair allocation of indivisible chores.  In AAAI, pages 335–341. AAAI Press, 2017.
  * [9] M. Babaioff, T. Ezra, and U. Feige.  Fair-share allocations for agents with arbitrary entitlements.  In EC, page 127. ACM, 2021.
  * [10] S. Barman, A. Krishna, Y. Narahari, and S. Sadhukhan.  Achieving envy-freeness with limited subsidies under dichotomous valuations.  In IJCAI, pages 60–66. ijcai.org, 2022.
  * [11] S. Barman and S. K. Krishnamurthy.  On the proximity of markets with integral equilibria.  In AAAI, pages 1748–1755, 2019.
  * [12] S. Barman and S. K. Krishnamurthy.  Approximation algorithms for maximin fair division.  ACM Trans. Economics and Comput., 8(1):5:1–5:28, 2020.
  * [13] X. Bei, Z. Li, J. Liu, S. Liu, and X. Lu.  Fair division of mixed divisible and indivisible goods.  Artif. Intell., 293:103436, 2021.
  * [14] U. Bhaskar, A. R. Sricharan, and R. Vaish.  On approximate envy-freeness for indivisible chores and mixed resources.  In APPROX-RANDOM, volume 207 of LIPIcs, pages 1:1–1:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [15] S. Bouveret and M. Lemaître.  Characterizing conflicts in fair division of indivisible goods using a scale of criteria.  Auton. Agents Multi Agent Syst., 30(2):259–290, 2016.
  * [16] S. Brânzei and F. Sandomirskiy.  Algorithms for competitive division of chores.  Mathematics of Operations Research, 2023.
  * [17] J. Brustle, J. Dippel, V. V. Narayan, M. Suzuki, and A. Vetta.  One dollar each eliminates envy.  In EC, pages 23–39. ACM, 2020.
  * [18] E. Budish.  The combinatorial assignment problem: approximate competitive equilibrium from equal incomes.  In BQGT, page 74:1. ACM, 2010.
  * [19] I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang.  The unreasonable fairness of maximum nash welfare.  ACM Trans. Economics and Comput., 7(3):12:1–12:32, 2019.
  * [20] M. Chakraborty, A. Igarashi, W. Suksompong, and Y. Zick.  Weighted envy-freeness in indivisible item allocation.  ACM Trans. Economics and Comput., 9(3):18:1–18:39, 2021.
  * [21] B. R. Chaudhury, J. Garg, K. Mehlhorn, R. Mehta, and P. Misra.  Improving EFX guarantees through rainbow cycle number.  In EC, pages 310–311. ACM, 2021.
  * [22] V. Conitzer, R. Freeman, and N. Shah.  Fair public decision making.  In EC, 2017.
  * [23] A. Farhadi, M. Ghodsi, M. T. Hajiaghayi, S. Lahaie, D. M. Pennock, M. Seddighin, S. Seddighin, and H. Yami.  Fair allocation of indivisible goods to asymmetric agents.  J. Artif. Intell. Res., 64:1–20, 2019.
  * [24] U. Feige and X. Huang.  On picking sequences for chores.  In EC, pages 626–655. ACM, 2023.
  * [25] U. Feige, A. Sapir, and L. Tauber.  A tight negative example for MMS fair allocations.  In WINE, volume 13112 of Lecture Notes in Computer Science, pages 355–372. Springer, 2021.
  * [26] D. Foley.  Resource allocation and the public sector.  Yale Economic Essays, pages 45–98, 1967.
  * [27] Y. Gafni, X. Huang, R. Lavi, and I. Talgam-Cohen.  Unified fair allocation of goods and chores via copies.  ACM Transactions on Economics and Computation, 11(3-4):1–27, 2023.
  * [28] H. Goko, A. Igarashi, Y. Kawase, K. Makino, H. Sumita, A. Tamura, Y. Yokoi, and M. Yokoo.  A fair and truthful mechanism with limited subsidy.  Games and Economic Behavior, 144:49–70, 2024.
  * [29] D. Halpern and N. Shah.  Fair division with subsidy.  In SAGT, volume 11801 of Lecture Notes in Computer Science, pages 374–389. Springer, 2019.
  * [30] X. Huang and P. Lu.  An algorithmic framework for approximating maximin share allocation of chores.  In EC, pages 630–631. ACM, 2021.
  * [31] X. Huang and E. Segal-Halevi.  A reduction from chores allocation to job scheduling.  In EC, page 908. ACM, 2023.
  * [32] Y. Kawase, K. Makino, H. Sumita, A. Tamura, and M. Yokoo.  Towards optimal subsidy bounds for envy-freeable allocations.  In AAAI, pages 9824–9831. AAAI Press, 2024.
  * [33] B. Li, Y. Li, and X. Wu.  Almost (weighted) proportional allocations for indivisible chores.  In WWW, pages 122–131. ACM, 2022.
  * [34] Z. Li, S. Liu, X. Lu, and B. Tao.  Truthful fair mechanisms for allocating mixed divisible and indivisible goods.  In IJCAI, pages 2808–2816. ijcai.org, 2023.
  * [35] R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi.  On approximately fair allocations of indivisible goods.  In EC, pages 125–131. ACM, 2004.
  * [36] S. Liu, X. Lu, M. Suzuki, and T. Walsh.  Mixed fair division: A survey.  CoRR, abs/2306.09564, 2023.
  * [37] E. S. Maskin.  On the fair allocation of indivisible goods.  In Arrow and the Foundations of the Theory of Economic Policy, pages 341–349. Springer, 1987.
  * [38] H. Moulin.  Fair division in the age of internet.  Annu. Rev. Econ., 2018.
  * [39] M. Springer, M. Hajiaghayi, and H. Yami.  Almost envy-free allocations of indivisible goods or chores with entitlements.  In AAAI, pages 9901–9908. AAAI Press, 2024.
  * [40] H. Steihaus.  The problem of fair division.  Econometrica, 16:101–104, 1948.
  * [41] B. Tao, X. Wu, Z. Yu, and S. Zhou.  On the existence of EFX (and pareto-optimal) allocations for binary chores.  CoRR, abs/2308.12177, 2023.
  * [42] X. Wu, C. Zhang, and S. Zhou.  One quarter each (on average) ensures proportionality.  In International Conference on Web and Internet Economics, pages 582–599. Springer, 2023.
  * [43] X. Wu, C. Zhang, and S. Zhou.  Weighted EF1 allocations for indivisible chores.  In EC, page 1155. ACM, 2023.
  * [44] S. Zhou and X. Wu.  Approximately EFX allocations for indivisible chores.  Artif. Intell., 326:104037, 2024.

##  Appendix A Missing Proofs

######  Lemma 2.4.

If there exists a polynomial time algorithm that given any IDO instance
computes a WPROPS allocation with total subsidy at most $\alpha$, then there
exists a polynomial time algorithm that given any instance computes a WPROPS
allocation with total subsidy at most $\alpha$.

###### Proof.

For any general instance $\mathcal{I}=(M,N,\mathbf{w},\mathbf{c})$, we reduce
it to an IDO instance
$\mathcal{I^{\prime}}=(M,N,\mathbf{w},\mathbf{c}^{\prime})$ by the following
construction. Let $\sigma_{i}(k)\in M$ be the $k$-th most costly item under
cost function $c_{i}$. Let $c^{\prime}_{i}(e_{k})=c_{i}(\sigma_{i}(k))$. Thus
with cost function $\mathbf{c}^{\prime}$, the instances $\mathcal{I^{\prime}}$
is IDO. Note that for all $i\in N$ we have $c^{\prime}_{i}(M)=c_{i}(M)$. Then
we run the algorithm for the IDO instance $\mathcal{I^{\prime}}$ and get a
WPROPS allocation $\mathbf{X}^{\prime}$ with subsidy $\mathbf{s}^{\prime}$
such that $\|\mathbf{s}^{\prime}\|_{1}\leq\alpha$. By definition, for all
agent $i\in N$ we have

$c^{\prime}_{i}(X^{\prime}_{i})-s^{\prime}_{i}\leq w_{i}\cdot
c^{\prime}_{i}(M)=w_{i}\cdot c_{i}(M)=\mathsf{WPROP}_{i}.$

We use $\mathbf{X}^{\prime}$ to guide us on computing a WPROPS allocation
$\mathbf{X}$ with subsidy $\mathbf{s}$ for the original instance
$\mathcal{I}$. We show that $c_{i}(X_{i})\leq c^{\prime}_{i}(X^{\prime}_{i})$
for all $i\in N$, which implies
$\|\mathbf{s}\|_{1}\leq\|\mathbf{s}^{\prime}\|_{1}\leq\alpha$. We initialize
$X_{i}=\emptyset$ for all $i\in N$ and let $P=M$ be the set of unallocated
items. Sequentially for $j=m,\ldots,1$, we let the agent $i$ who receives item
$e_{j}$ under allocation $\mathbf{X}^{\prime}$, i.e., $e_{j}\in
X^{\prime}_{i}$, pick her favorite unallocated item. At the beginning of each
round $j$, we have $|P|=j$. Since $e_{j}$ is the $j$-th most costly item under
cost function $c^{\prime}_{i}$, we must have $c_{i}(e)\leq
c^{\prime}_{i}(e_{j})$ for the item $e$ agent $i$ picks during round $j$.
Therefore for all items in $X_{i}$ and $X^{\prime}_{i}$ we can establish a
one-to-one correspondence relationship similarly, which implies
$c_{i}(X_{i})\leq c^{\prime}_{i}(X^{\prime}_{i})$. ∎

######  Lemma 3.1.

The output allocation $\mathbf{x}$ is a fractional WPROP allocation.

###### Proof.

Note that throughout the allocation process, we maintain the property that
$c_{i}(\mathbf{x}_{i})\leq\mathsf{WPROP}_{i}$ for each agent $i$.
Particularly, for every inactive agent $i\in N\setminus A$, we have
$c_{i}(\mathbf{x}_{i})=\mathsf{WPROP}_{i}=w_{i}\cdot c_{i}(M)$. Hence it
suffices to show all items are fully allocated, i.e., there is at least one
active agent when we try to allocate each item $e$. Since we allocate each
item $e$ to the active agent $i$ with the minimum $\frac{c_{i}(e)}{c_{i}(M)}$,
we have $\frac{c_{i}(e)}{c_{i}(M)}\leq\frac{c_{j}(e)}{c_{j}(M)}$ for every
active $j\neq i$. Therefore we have
$\frac{c_{j}(X_{i})}{c_{j}(M)}\geq\frac{c_{i}(X_{i})}{c_{i}(M)}$ for any
active agents $i,j\in A$.

Assume by contradiction that when assigning some item $e$, all agents are
inactive, i.e., $A=\emptyset$. Let $j$ be the last agent that becomes
inactive. Consider the moment when $j$ becomes inactive, we have

$1=\frac{c_{j}(M)}{c_{j}(M)}>\sum_{i\in
N}\frac{c_{j}(\mathbf{x}_{i})}{c_{j}(M)}\geq\sum_{i\in
N}\frac{c_{i}(\mathbf{x}_{i})}{c_{i}(M)}=\sum_{i\in N}w_{i}=1,$

which is a contradiction. ∎

######  Lemma 4.2.

For the four different rounding schemes, the total required subsidy can be
upper bounded as shown in the following table.

Rounding Scheme | Upper Bound for Total Subsidy
---|---
$\mathsf{LL}$ | $x_{2}(e_{1})+\left((1-x_{2}(e_{2}))\cdot\alpha-x_{2}(e_{1})\right)^{+}$
$\mathsf{RR}$ | $x_{2}(e_{2})+\left((1-x_{2}(e_{1}))-x_{2}(e_{2})\cdot\alpha\right)^{+}$
$\mathsf{LR}$ | $x_{2}(e_{1})+x_{2}(e_{2})$
$\mathsf{RL}$ | $(1-x_{2}(e_{1}))+(1-x_{2}(e_{2}))\cdot\alpha$
Table 4: Upper bounds for the subsidies required for the four different
rounding schemes.

###### Proof.

In the $\mathsf{LL}$ rounding scheme, we round both items $e_{1},e_{2}$ to
their left endpoint agents. The inclusion of item $e_{1}$ to agent $1$ incurs
an increase in subsidy by at most

$(1-x_{1}(e_{1}))\cdot c_{1}(e_{1})\leq 1-x_{1}(e_{1})=x_{2}(e_{1}).$

Note that rounding $e_{1}$ to agent $1$ releases a space of $x_{2}(e_{1})\cdot
a_{1}$ for agent $2$. Hence the inclusion of item $e_{2}$ to agent $2$ incurs
an increase in subsidy by at most

$\left((1-x_{2}(e_{2}))\cdot a_{2}-x_{2}(e_{1})\cdot a_{1}\right)^{+}\leq
a_{1}\cdot\left((1-x_{2}(e_{2}))\cdot\alpha-
x_{2}(e_{1})\right)^{+}\leq\left((1-x_{2}(e_{2}))\cdot\alpha-
x_{2}(e_{1})\right)^{+}.$

Hence we have

$s_{\mathsf{LL}}\leq x_{2}(e_{1})+\left((1-x_{2}(e_{2}))\cdot\alpha-
x_{2}(e_{1})\right)^{+}.$

In the $\mathsf{RR}$ rounding scheme, we round both items $e_{1},e_{2}$ to
their right endpoint agents. The inclusion of item $e_{2}$ to agent $3$ incurs
an increase in subsidy by at most

$(1-x_{3}(e_{2}))\cdot c_{3}(e_{2})\leq 1-x_{3}(e_{2})=x_{2}(e_{2}).$

Since rounding $e_{2}$ to agent $3$ releases a space of $x_{2}(e_{2})\cdot
a_{2}$ for agent $2$, the inclusion of item $e_{2}$ to agent $2$ incurs an
increase in subsidy by at most

$\left((1-x_{2}(e_{1}))\cdot a_{1}-x_{2}(e_{2})\cdot a_{2}\right)^{+}\leq
a_{1}\cdot\left((1-x_{2}(e_{1}))-x_{2}(e_{2})\cdot\alpha\right)^{+}\leq\left((1-x_{2}(e_{1}))-x_{2}(e_{2})\cdot\alpha\right)^{+}.$

Hence we have

$s_{\mathsf{LL}}\leq
x_{2}(e_{2})+\left((1-x_{2}(e_{1}))-x_{2}(e_{2})\cdot\alpha\right)^{+}.$

In the $\mathsf{LR}$ rounding scheme, we round items $e_{1}$ to agent $1$ and
$e_{2}$ to agent $3$. The total subsidy incurred can be upper bounded as
follows:

$s_{\mathsf{LR}}=(1-x_{1}(e_{1}))\cdot c_{1}(e_{1})+(1-x_{3}(e_{2}))\cdot
c_{3}(e_{2})\leq(1-x_{1}(e_{1}))+(1-x_{3}(e_{2}))=x_{2}(e_{1})+x_{2}(e_{2}).$

In the $\mathsf{RL}$ rounding scheme, we round both items $e_{1},e_{2}$ to
agent $2$. The total subsidy incurred is

$\displaystyle s_{\mathsf{RL}}=(1-x_{2}(e_{1}))\cdot
a_{1}+(1-x_{2}(e_{2}))\cdot a_{2}$
$\displaystyle=a_{1}\left((1-x_{2}(e_{1}))+(1-x_{2}(e_{2}))\cdot\alpha\right)$
$\displaystyle\leq(1-x_{2}(e_{1}))+(1-x_{2}(e_{2}))\cdot\alpha.\qed$

##  Appendix B WPROPS Allocation for Goods

In this section, we consider the allocation of goods and propose an algorithm
that computes a WPROPS allocation with total subsidy at most $n/3$. Since the
analysis is almost identical to the ones we have shown in previous sections,
we will only highlight the main ideas and changes to the proof, without
presenting too much tedious and repetitive analysis.

###  B.1 The Notation and Definitions

We consider the problem of allocating $m$ indivisible goods $M$ to $n$ agents
$N$ where each agent $i\in N$ has weight $w_{i}>0$ and additive valuation
function $v_{i}:2^{M}\to{\mathbb{R}}^{+}\cup\\{0\\}$. As before, we assume
$\sum_{i\in N}w_{i}=1$ and $v_{i}(e)\leq 1$ for all $i\in N$, $e\in M$. We
define $\mathsf{WPROP}_{i}$ as agent $i$’s proportional share, i.e.,
$\mathsf{WPROP}_{i}=w_{i}\cdot v_{i}(M)$.

######  Definition B.1 (WPROP).

An allocation $\mathbf{X}$ is called weighted proportional (WPROP) if
$v_{i}(X_{i})\geq\mathsf{WPROP}_{i}$ for all $i\in N$.

As before, we use $s_{i}\geq 0$ to denote the subsidy we give to agent $i\in
N$, $\mathbf{s}=(s_{1},\ldots,s_{n})$ and $\|\mathbf{s}\|_{1}=\sum_{i\in
N}s_{i}$.

######  Definition B.2 (WPROPS).

An allocation $\mathbf{X}$ with subsidies $\mathbf{s}=(s_{1},\ldots,s_{n})$ is
called weighted proportional with subsidies (WPROPS) if for any $i\in N$,

$v_{i}(X_{i})+s_{i}\geq\mathsf{WPROP}_{i}.$

Given any allocation $\mathbf{X}$, computing the minimum subsidy to achieve
weighted proportionality can be trivially done by setting

$s_{i}=\max\\{\mathsf{WPROP}_{i}-v_{i}(X_{i}),0\\},\qquad\forall i\in N.$

We first show a similar reduction as Lemma 2.4 which allows us to consider
only IDO instances. Since the proof is almost identical to that for Lemma 2.4,
we omit it.

######  Definition B.3 (Identical Ordering (IDO) Instances).

An instance is called identical ordering (IDO) if all agents have the same
ordinal preference on the items, i.e., $v_{i}(e_{1})\leq
v_{i}(e_{2})\leq\cdots\leq v_{i}(e_{m})$ for all $i\in N$.

######  Lemma B.4.

If there exists a polynomial time algorithm that given any IDO instance
computes a PROPS allocation with at most $\alpha$ subsidy, then there exists a
polynomial time algorithm that given any instance computes a PROPS allocation
with at most $\alpha$ subsidy.

With the above reduction, in the following, we only consider the IDO
instances. Like the chore setting, our algorithm has two main steps: we first
compute a fractional PROP allocation, in which a small number of items are
fractionally allocated; then we find a way to round the fractional allocation
to an integral one. Since some agents may have bundle value less than their
proportional share after rounding, we offer subsidies to these agents. By
carefully deciding the rounding scheme, we show that the total subsidy
required is at most $n/3$.

###  B.2 Fractional Bid-and-Take Algorithm

We use the same notation defined in Section 3.1 for representing a fractional
allocation, e.g., we use $x_{i}(e)\in[0,1]$ to denote the fraction of item $e$
that is allocated to agent $i$.

##### The Algorithm.

We continuously allocate the items one by one following an arbitrarily fixed
ordering $e_{1},e_{2},\ldots,e_{m}$ of the items. Initially, all agents are
active. For each item $e_{j}\in M$, we continuously allocate $e_{j}$ to the
active agent $i$ with the maximum $\frac{v_{i}(e_{j})}{v_{i}(M)}$, until
either $e_{j}$ is fully allocated or $v_{i}(X_{i})=\mathsf{WPROP}_{i}$. If
$v_{i}(X_{i})=\mathsf{WPROP}_{i}$, we inactive agent $i$. The algorithm
terminates when all items are fully allocated. The steps of the full algorithm
are summarized in Algorithm 4.

Input: An instance $(M,N,\mathbf{w},\mathbf{v})$ with $v_{i}(e_{1})\leq
v_{i}(e_{2})\leq\cdots\leq v_{i}(e_{m})$ for all $i\in N$

$X_{i}\leftarrow\mathbf{0}^{m},\forall i\in N$ // current fractional bundle

$A\leftarrow N$ // the set of active agents

$\mathbf{z}\leftarrow\mathbf{1}^{m}$ // remaining fraction of the items

$j\leftarrow 1$ // item to be allocated

1 while  _$j\leq m$_ do

2 Let $i\leftarrow\operatorname*{argmax}_{i^{\prime}\in
A}\frac{v_{i^{\prime}}(e_{j})}{v_{i^{\prime}}(M)}$;

3 if  _$v_{i}(X_{i})+z_{j}\cdot v_{i}(e_{j}) >\mathsf{WPROP}_{i}$_ then

4 $x_{ie_{j}}\leftarrow\frac{\mathsf{WPROP}_{i}-v_{i}(X_{i})}{v_{i}(e_{j})}$;

5 $z_{j}\leftarrow z_{j}-x_{ie_{j}}$, $A\leftarrow A\setminus\\{i\\}$;

6 if  _$|A|=1$_ then

7 Allocate all remaining items to the only active agent and go to output;

8

9

10 else

11 $x_{ie_{j}}\leftarrow z_{j}$, $z_{j}\leftarrow 0$, $j\leftarrow j+1$;

12

13

Output: A fractional allocation $\mathbf{x}$.

Algorithm 4 Fractional Bid and Take Algorithm

######  Lemma B.5.

The output allocation $\mathbf{x}$ is a fractional WPROP allocation.

###### Proof.

It suffices to show that the last active agent $n$ receives a bundle of value
at least $\mathsf{WPROP}_{n}$. Since we allocate each item $e$ to the active
agent $i$ with the maximum $\frac{v_{i}(e)}{v_{i}(M)}$, we have
$\frac{v_{i}(e)}{v_{i}(M)}\geq\frac{v_{j}(e)}{v_{j}(M)}$ for every active
$j\neq i$. Therefore we have
$\frac{v_{j}(X_{i})}{v_{j}(M)}\leq\frac{v_{i}(X_{i})}{v_{i}(M)}$ for any
active agents $i,j\in A$. Suppose that $v_{n}(X_{n})<\mathsf{WPROP}_{n}$ at
the end of the algorithm, then we have

$1=\sum_{i\in N}\frac{v_{n}(X_{i})}{v_{n}(M)}\leq\sum_{i\in
N}\frac{v_{i}(X_{i})}{v_{i}(M)}<\sum_{i\in
N}\frac{\mathsf{WPROP}_{i}}{v_{i}(M)}=\sum_{i\in N}w_{i}=1,$

which is a contradiction. ∎

The definition of item-sharing graph can be naturally extended to the goods
case. We call agent $j$ a successor of agent $i$ if Algorithm 4 tries to
allocate the remaining part of item $e^{i}$ to $j$. By letting the set of
nodes be the agents where each agent has a directed edge to its successor (if
any), we construct the item-sharing graph of the fractional allocation
$\mathbf{x}$ returned by Algorithm 4. As before, we differ in two cases of
whether there exist _shattered items_ , i.e., items shared by three or more
agents. We remark that the splitting we introduced in the chores setting can
also be used in the goods setting since it only deals with the tree structure
instead of the cost/value of items.

###  B.3 Graph without Shattered Item

We first consider the case that there is no shattered item in the item-sharing
graph $G$. Following the same analysis as in the proof of Lemma 4.1, we can
show that for any tree with size two, there exists a rounding scheme that
guarantees a WPROPS allocation with a total subsidy of at most $2/3$.

######  Theorem B.6.

For a tree with size $2$, there exists a rounding scheme that guarantees a
WPROPS allocation with total subsidy at most $2/3$, which is optimal.

Consider an instance $\mathcal{I}=(M,N,\mathbf{w},\mathbf{v})$ where
$N=\\{1,2,3\\}$ (see Figure 11). Let $a_{1}=v_{2}(e_{1})$,
$a_{2}=v_{2}(e_{2})$, we assume w.l.o.g. that $a_{1}\geq a_{2}$. We let
$\alpha=a_{1}/a_{2}$.

$1$$e_{1}$$2$$e_{2}$$3$ Figure 11: The item-sharing graph for three agents
case.

Similar to the chore setting, we introduce four different rounding schemes
called $\mathsf{LL},\mathsf{RR},\mathsf{LR},\mathsf{RL}$. We use
$s_{\mathsf{LL}},s_{\mathsf{RR}},s_{\mathsf{LR}},s_{\mathsf{RL}}$ to denote
the subsidy required in the four rounding strategies respectively. The upper
bounds for the subsidies required for the four different rounding schemes are
as shown in Table 5.

Rounding Schemes | Upper Bounds for Subsidies
---|---
$\mathsf{LL}$ | $(1-x_{2}(e_{2}))+\left(x_{2}(e_{1})-x_{2}(e_{2})\cdot\alpha\right)^{+}$
$\mathsf{RR}$ | $(1-x_{2}(e_{1}))+\left(x_{2}(e_{2})\cdot\alpha-x_{2}(e_{1})\right)^{+}$
$\mathsf{LR}$ | $x_{2}(e_{1})+x_{2}(e_{2})\cdot\alpha$
$\mathsf{RL}$ | $(1-x_{2}(e_{1}))+(1-x_{2}(e_{2}))$
Table 5: Upper bounds for the subsidies required for the four different
rounding schemes.

If we use $y_{1}$ and $y_{2}$ to denote $1-x_{2}(e_{1})$ and $1-x_{2}(e_{2})$,
then the above upper bounds are symmetrical as the upper bounds we present in
the proof of Theorem 4.1. Note that $0\leq 1-x_{2}(e_{i})\leq 1$ for both
$i\in\\{1,2\\}$, the proof of Theorem 4.1 can be extended to the goods case
straightforwardly.

Based on Theorem B.6, we call Simple Splitting to decompose any graph $G$
(without shattered item) into a collection of subtrees with size two. By Lemma
4.4 and the same analysis as in the proof of Theorem 4.6, we can bound the
total subsidy required for the graph without shattered item by $n/3$.

######  Theorem B.7.

Given the fractional allocation $\mathbf{x}$ with $n-1$ fractional items
returned by Algorithm 4, there exists a rounding scheme that returns an
integral WPROPS allocation $\mathbf{X}$ with total subsidy at most $n/3$.

###  B.4 Graph with Shattered Item

In this section, we consider the case that there exists at least one shattered
item in the item-sharing graph $G$. Similar to the chores setting, we call
Algorithm 3 to decompose the graph $G$ into an expanded atom-path and a
collection of trees. Following Lemma 5.7, each decomposed tree returned by the
Atom-path Splitting either contains an atom-path or has an even size. To upper
bound the total required subsidy, it suffices to bound the subsidy required
for each expanded atom-path.

######  Lemma B.8.

For any expanded atom-path with $k$-length atom-path and $h\leq k+1$ attached
edges, there exists a rounding scheme with total subsidy bounded by $(k+h)/3$.

Given Lemma B.8, we are ready to upper bound the total subsidy required for
graph $G$. The proof of Lemma B.9 is based on mathematical induction and
similar to the proof of Lemma 5.2. Here we omit the detailed proof.

######  Lemma B.9.

For any tree with size $z\geq 2$ such that there exists an atom-path in the
tree, there exists a rounding scheme with total subsidy bounded by $z/3$.

We remark that Lemma B.9 directly leads to the following theorem.

######  Theorem B.10.

Given the fractional allocation $\mathbf{x}$ with less than $n-1$ fractional
items returned by Algorithm 1, there exists a rounding scheme that returns an
integral WPROPS allocation with total subsidy at most $(n-1)/3$.

Next, we define some notations that will be useful to prove Lemma B.8. Fix any
expanded atom-path $T$, we assume that the atom-path has $k\geq 2$ edges,
which correspond to the item $e_{0}$. We denote the nodes in the atom-path by
agents $1,\ldots,k+1$, where agent $i+1$ is the successor of agent $i$, for
all $i=1,2,\ldots,k$. We denote the edge attached to agent $i$ by $e_{i}$.
When there is no attached edge to agent $i$, we define $e_{i}=\bot$. We call
agents $1,2,\ldots,k+1$ the _atom-path agents_ and the other agents the
_attached agents_. We use $h\leq k+1$ to denote the number of attached
edges/agents in the expanded atom-path. For each item $e_{i}$, where
$i\in\\{1,\ldots,k+1\\}$, we use $y_{i}$ to denote the fraction of item
$e_{i}$ held by the corresponding attached agent, i.e.,
$y_{i}=1-x_{i}(e_{i})$. For all $i\in\\{1,\ldots,k+1\\}$, when there is no
ambiguity, we use $x_{i}$ to denote $x_{i}(e_{0})$ for convenience.

In the following, we focus on upper bounding the subsidy required for any
expanded atom-path. We show Lemma B.8, by giving the following arguments of
different types of expanded atom-paths respectively, and show that the
arguments cover all types of expanded atom-paths.

######  Lemma B.11.

For an expanded atom-path with $h\leq k\cdot(2-\frac{6}{k+1})$, there exists a
rounding scheme with total subsidy at most $(k+h)/3$.

######  Lemma B.12.

For an expanded atom-path with $h=k+1$, there exists a rounding scheme with
total subsidy at most $(k+h)/3$.

######  Lemma B.13.

For an expanded atom-path with $h=k$, there exists a rounding scheme with
total subsidy at most $(k+h)/3$.

######  Lemma B.14.

For an expanded atom-path with $2\leq k\leq 3$ and $h=k-1$, there exists a
rounding scheme with total subsidy at most $(k+h)/3$.

Similar to the proof of Lemma 5.8, the above arguments immediately lead to
Lemma B.8. Hence we omit the proof here.

####  B.4.1 Expanded Atom-path

######  Lemma B.11.

For an expanded atom-path with $h\leq k\cdot(2-\frac{6}{k+1})$, there exists a
rounding scheme with total subsidy at most $(k+h)/3$.

###### Proof.

We consider the threshold rounding that rounds each item to the agent holding
the maximum fraction of it. For item $e_{0}$, we round it to
$i^{*}=\operatorname*{argmax}_{1\leq i\leq k+1}x_{i}$, which incurs a subsidy
of at most $\frac{k}{k+1}$. The rounding of each item $e_{i}$ incurs subsidy
at most $\frac{1}{2}$ iff $e_{i}\neq\bot$. Hence the total subsidy is bounded
by $\frac{k}{k+1}+\frac{h}{2}$, which is at most $\frac{k+h}{3}$ when $h\leq
k\cdot(2-\frac{6}{k+1})$. ∎

We remark that the major difference between the analysis of goods and chores
is the biased threshold rounding. In the case of goods, rounding item $e_{0}$
to agent $i^{*}$ would not release a space of $x_{i}\cdot v_{i}(e)$ to agent
$i\neq i^{*}$. Instead, it creates a gap of $x_{i}\cdot v_{i}(e)$ to the
proportionality and needs to be filled by rounding other items or subsidizing
money. Next, we show that in the goods setting, there also exists a biased
threshold rounding that makes use of the dependent rounding of items.

For any agent $i\neq i^{*}$ that does not receive item $e_{0}$, when we round
$e_{i}$ to agent $i$, the total subsidy required for agent $i$ and her
(corresponding) attached agent is at most $(x_{i}\cdot v_{i}(e_{0})-y_{i}\cdot
v_{i}(e_{i}))^{+}+y_{i}$, while the total subsidy required for agent $i$ in
the case that rounds $e_{i}$ to the attached agent is $x_{i}\cdot
v_{i}(e_{0})+(1-y_{i})\cdot v_{i}(e_{i})$. For any $1\leq i\leq k+1$, we use
$\alpha_{i}$ to denote $v_{i}(e_{0})$. We formalize this idea into the
following rounding scheme.

##### Biased Threshold Rounding (Goods).

For any attached edge $e_{i}$, we round item $e_{i}$ to the attached agent if
$x_{i}\cdot\alpha_{i}+(1-y_{i})\cdot
v_{i}(e_{i})<(x_{i}\cdot\alpha_{i}-y_{i}\cdot v_{i}(e_{i}))^{+}+y_{i}$;
otherwise round item $e_{i}$ to agent $i$.

######  Proposition B.15.

For any agent $i\in\\{1,2,\ldots,k+1\\}$ that does not receive item $e_{0}$,
by rounding $e_{i}$ using the biased threshold rounding, the subsidy required
for agent $i$ and her corresponding attached agent is at most
$(1+x_{i}\cdot\alpha_{i})/2$ if $x_{i}\cdot\alpha_{i}\leq\frac{1}{2}$; at most
$x_{i}\cdot\alpha_{i}+1/4$ if $x_{i}\cdot\alpha_{i}>\frac{1}{2}$.

###### Proof.

Note that the incurred subsidy by biased threshold rounding is bounded by

$\min\\{(x_{i}\cdot\alpha_{i}-y_{i}\cdot
v_{i}(e_{i}))^{+}+y_{i},\;x_{i}\cdot\alpha_{i}+(1-y_{i})\cdot
v_{i}(e_{i})\\}.$

When $(x_{i}\cdot\alpha_{i}-y_{i}\cdot v_{i}(e_{i}))^{+}=0$, the total subsidy
required for agent $i$ and her corresponding attached agent is at most

$\min\\{y_{i},\;x_{i}\cdot\alpha_{i}+(1-y_{i})\cdot
v_{i}(e_{i})\\}\leq\min\\{y_{i},\;x_{i}\cdot\alpha_{i}+1-y_{i}\\}\leq\frac{1+x_{i}\cdot\alpha_{i}}{2}.$

which is not larger than $x_{i}\cdot\alpha_{i}+1/4$ when
$x_{i}\cdot\alpha_{i}>\frac{1}{2}$.

By Proposition 4.3, when $(x_{i}\cdot\alpha_{i}-y_{i}\cdot
v_{i}(e_{i}))^{+}>0$, the total subsidy required for agent $i$ and her
corresponding attached agent is at most

$\min\\{x_{i}\cdot\alpha_{i}+y_{i}\cdot(1-v_{i}(e_{i})),\;x_{i}\cdot\alpha_{i}+(1-y_{i})\cdot
v_{i}(e_{i})\\}\leq x_{i}\cdot\alpha_{i}+\frac{1}{4}\qed$

which is not larger than $(1+x_{i}\cdot\alpha_{i})/2$ when
$x_{i}\cdot\alpha_{i}\leq\frac{1}{2}$.

######  Corollary B.16.

For any agent $i\in\\{1,2,\ldots,k+1\\}$ that does not receive item $e_{0}$,
by rounding $e_{i}$ using the biased threshold rounding, the subsidy required
for agent $i$ and her corresponding attached agent is at most $(1+x_{i})/2$ if
$x_{i}\cdot\alpha_{i}\leq\frac{1}{2}$.

Given Proposition B.15, we show that the proofs of Lemma B.11, B.12, B.13,
B.14 are similar to the proofs of analogous lemmas in the chores allocation
with minor modification.

######  Observation B.17.

For any agent $i\leq k$, $v_{i}(e_{0})\geq v_{i}(e_{i})$.

###### Proof.

We remark that for any agent $i\leq k$, $e_{0}$ is the last (fraction of) item
that she receives. Otherwise, agent $i$ would not have a successor with
respect to $e_{0}$. In other words, for any agent $i$, the event that $i$
takes (a fraction of) item $e_{i}$ happens before the event that $i$ takes (a
fraction of) item $e_{0}$. Recall that we reduce all instances to the IDO
instance with increasing value for all agents, and use the IDO instance as the
input of Algorithm 4, Hence, for any agent $i\leq k$, we have
$v_{i}(e_{0})\geq v_{i}(e_{i})$. ∎

######  Proposition B.18.

For an expanded atom-path with $k-1\leq h\leq k+1$ attached agents, if there
exists an agent $1\leq j\leq k+1$ such that
$x_{j}\cdot\alpha_{j}>\frac{1}{2}$, there exists a rounding scheme with total
subsidy at most $(k+h)/3$.

###### Proof.

If there exists an agent $1\leq j\leq k+1$ such that $x_{j}>\frac{1}{2}$, we
apply the threshold rounding to all fractional items. The rounding of item
$e_{0}$ incurs a subsidy of at most $1/2$ since $x_{j}>\frac{1}{2}$ and the
rounding of any item $e_{i}$ such that $e_{i}\neq\bot$ incurs a subsidy of at
most $1/2$. Hence the total required subsidy is at most

$\|s\|_{1}\leq\frac{h+1}{2},$

which is not larger than $(k+h)/3$ when $k\geq 4,h=k+1$, or $k\geq 3,h=k$, or
$k\geq 2,h=k-1$. Hence it remains to consider the cases of $k=3,h=4$, or
$k=2,h=3$, or $k=2,h=2$.

In the following, we ignore the directions of the attached edges and assume
w.l.o.g. that $x_{k+1}\cdot\alpha_{k+1}>\frac{1}{2}$. We first consider the
case that $k=3,h=4$, where $(k+h)/3=7/3$. Consider the rounding scheme that
rounds item $e_{0}$ to agent $4$, rounds items $e_{1},e_{2},e_{3}$ using the
biased threshold rounding, and rounds item $e_{4}$ using the threshold
rounding. The total required subsidy can be bounded by

$\sum_{1\leq i\leq
3}\frac{1+x_{i}}{2}+\frac{1}{2}=2+\frac{x_{1}+x_{2}+x_{3}}{2}<\frac{9}{4}<\frac{7}{3}.$

We move to consider the case that $k=2,h=3$, where $(k+h)/3=5/3$. We consider
the rounding scheme that rounds item $e_{0}$ to agent $1$, rounds item
$e_{1},e_{2}$ using the biased threshold rounding, and rounds item $e_{3}$ to
the attached agent. The total required subsidy is at most

$\displaystyle((1-y_{3})-(1-x_{3})\cdot\alpha_{3})^{+}+\frac{1+x_{1}}{2}+\frac{1+x_{2}}{2}.$

When $((1-y_{3})-(1-x_{3})\cdot\alpha_{3})^{+}=0$, the upper bound becomes

$\frac{1+x_{1}}{2}+\frac{1+x_{2}}{2}<\frac{5}{4}.$

When $((1-y_{3})-(1-x_{3})\cdot\alpha)^{+}>0$, the upper bound becomes

$(1-y_{3})-(1-x_{3})\cdot\alpha_{3}+\frac{1+x_{1}}{2}+\frac{1+x_{2}}{2}.$

Consider another rounding scheme that rounds item $e_{0}$ to agent $4$, rounds
items $e_{1},e_{2}$ using the biased threshold rounding, and rounds item
$e_{4}$ to agent $4$. The total required subsidy is at most.

$y_{3}+\frac{1+x_{1}}{2}+\frac{1+x_{2}}{2}$

The summation of the above two upper bounds is at most

$1-(1-x_{3})\cdot\alpha_{3}+2+x_{1}+x_{2}=3+(1-x_{3})-(1-x_{3})\cdot\alpha_{3}=3+(1-x_{3})\cdot(1-\alpha_{3})<\frac{13}{4},$

where the last inequality holds following Proportion 4.3 and
$x_{3}\cdot\alpha_{3}>1/2$. Hence, at least one of the two rounding schemes
requires a total subsidy of at most $13/8<5/3$.

Finally, we consider the case that $k=2,h=2$, where $(k+h)/3=4/3$. We assume
w.l.o.g. that $x_{3}\cdot\alpha_{3}>\frac{1}{2}$ and $x_{2}=\bot$. We consider
the rounding scheme that rounds item $e_{0}$ to agent $3$, rounds item $e_{1}$
using the biased threshold rounding, and rounds item $e_{3}$ to the attached
agent. The total required subsidy is at most

$\frac{1+x_{1}}{2}+x_{2}+((1-y_{3})-(1-x_{3})\cdot\alpha_{3})^{+}$

When $((1-y_{3})-(1-x_{3})\cdot\alpha_{3})^{+}=0$, the upper bound becomes

$\frac{1+x_{1}}{2}+x_{2}<\frac{1+x_{1}+x_{2}+x_{3}}{2}=1.$

When $((1-y_{3})-(1-x_{3})\cdot\alpha_{3})^{+}>0$, the upper bound becomes

$\frac{1+x_{1}}{2}+x_{2}+(1-y_{3})-(1-x_{3})\cdot\alpha_{3}.$

Consider another rounding scheme that rounds item $e_{0}$ to agent $3$, rounds
item $e_{1}$ using the biased threshold rounding, and rounds item $e_{3}$ to
agent $3$. The total required subsidy is at most

$\frac{1+x_{1}}{2}+x_{2}+y_{3}.$

The summation of the above two upper bounds is at most

$\displaystyle 1+x_{1}+2\cdot x_{2}+1-(1-x_{3})\cdot\alpha_{3}$
$\displaystyle=$ $\displaystyle 2+(1-x_{3})+x_{2}-(1-x_{3})\cdot\alpha_{3}$
$\displaystyle=$ $\displaystyle
2+(1-x_{3})\cdot(1-\alpha_{3})+x_{2}<\frac{9}{4}+x_{2},$

where the last inequality holds following Proportion 4.3 and
$x_{3}\cdot\alpha_{3}>1/2$. When $x_{2}\leq\frac{5}{12}$ the above summation
is at most $8/3$, leading to at least one of the rounding schemes requiring
total subsidy at most $4/3$. Consider otherwise that $x_{2}>5/12$, which
implies that $x_{1}+x_{3}<7/12$. We consider the rounding scheme that rounds
item $e_{0}$ to agent $2$, rounds items $e_{1},e_{3}$ using the biased
threshold rounding, the total subsidy is at most

$\frac{1+x_{1}}{2}+x_{3}+\frac{1}{4}\leq x_{1}+x_{3}+\frac{3}{4}<\frac{4}{3}.$

Hence for all expanded atom-path with $x_{j}\cdot\alpha_{j}>\frac{1}{2}$ for
some $1\leq j\leq k+1$, there exists a rounding scheme with total subsidy at
most $(k+h)/3$. ∎

By Proposition B.18, in the following, we only consider cases that
$x_{i}\cdot\alpha_{i}\leq 1/2$ for all $1\leq i\leq k+1$. In other words, we
assume that Corollary B.16 holds for any $1\leq i\leq k+1$ that does not
receive item $e_{0}$.

######  Lemma B.12.

For an expanded atom-path with $h=k+1$, there exists a rounding scheme with
total subsidy at most $(k+h)/3$.

###### Proof.

We consider the rounding schemes that round $e_{0}$ to agent $1$ and round the
items $e_{2},\ldots,e_{k+1}$ using the biased threshold rounding. We show that
this rounding scheme has a total subsidy of no more than $(k+h)/3$.

  * •

Scheme 1. We round item $e_{1}$ to the attached agent.

  * •

Scheme 2. We round item $e_{1}$ to agent $1$.

For scheme 1, the total required subsidy can be bounded by the following

$\displaystyle((1-y_{1})\cdot v_{1}(e_{1})-(1-x_{1})\cdot
v_{1}(e_{0}))^{+}+\sum_{2\leq i\leq k+1}\frac{1+x_{i}}{2}$ $\displaystyle\leq$
$\displaystyle((x_{1}-y_{1})\cdot v_{1}(e_{0}))^{+}+\sum_{2\leq i\leq
k+1}\frac{1+x_{i}}{2}$ ($v_{1}(e_{1})\leq v_{1}(e_{0})$) $\displaystyle\leq$
$\displaystyle(x_{1}-y_{1})^{+}+\sum_{2\leq i\leq k+1}\frac{1+x_{i}}{2}.$ (12)

For scheme 2, the total required subsidy can be bounded by

$y_{1}+\sum_{2\leq i\leq k+1}\frac{1+x_{i}}{2}.$ (13)

When $x_{1}-y_{1}\leq 0$, it is easy to find that Equation (12) dominates
Equation (13). We can upper bound the subsidy for scheme 1 as follows.

$\displaystyle\|s\|_{1}$ $\displaystyle\leq\sum_{2\leq i\leq
k+1}\frac{1+x_{i}}{2}$ (By Equation (2) and $x_{1}-y_{1}\leq 0$)
$\displaystyle=\frac{k}{2}+\sum_{2\leq i\leq
k+1}\frac{x_{i}}{2}\leq\frac{k+1}{2}.$ ($\sum_{2\leq i\leq k+1}x_{i}\leq 1$)

Next, we consider the case that $x_{1}-y_{1}>0$. We have that

$\displaystyle\text{For scheme 1, }\|s\|_{1}$ $\displaystyle\leq
x_{1}-y_{1}+\sum_{2\leq i\leq k+1}\frac{1+x_{i}}{2};$ (By Equation 12)
$\displaystyle\text{For scheme 2, }\|s\|_{1}$ $\displaystyle\leq
y_{1}+\sum_{2\leq i\leq k+1}\frac{1+x_{i}}{2}.$ (By Equation 13)

Summing up the above two upper bounds, We have that the total subsidy required
by the two rounding schemes combined is at most

$\displaystyle x_{1}-y_{1}+y_{i}+\sum_{2\leq i\leq
k+1}\frac{1+x_{i}}{2}+\sum_{2\leq i\leq k+1}\frac{1+x_{i}}{2}$
$\displaystyle=$ $\displaystyle x_{1}+\sum_{2\leq i\leq k+1}(1+x_{i})$
$\displaystyle=$ $\displaystyle k+1.$ ($\sum_{1\leq i\leq{k+1}}x_{i}=1$)

Therefore, at least one of the two rounding schemes requires a total subsidy
of at most $(k+1)/2$, which is not larger than $(k+h)/3$ for all $k\geq 2$. ∎

######  Lemma B.13.

For an expanded atom-path with $h=k$, there exists a rounding scheme with
total subsidy at most $(k+h)/3$.

###### Proof.

When $h=k$, there exists an agent $j$ in the atom-path with no edge attached,
i.e., $e_{j}=\bot$. We round item $e_{0}$ to agent $j$ and round all item
$e_{i}$ s.t. $1\leq i\leq k,i\neq j$ using the biased threshold rounding.

$\sum_{i\neq j}\frac{1+x_{i}}{2}\leq\frac{k}{2}+\sum_{i\neq
j}\frac{x_{i}}{2}=\frac{k+1-x_{j}}{2},$

which is not larger than $(k+h)/3$ when $k\geq 3$; or $k=2$ and $x_{j}\geq
1/3$. It remains to consider the case that $k=2$ and $x_{j}<1/3$. By
Observation B.17, there exists (at least) one agent $i\in N\setminus\\{j\\}$
such that $v_{i}(e_{0})\geq v_{i}(e_{i})$. Let $p$ be the agent other than
$i,j$. We round item $e_{0}$ to agent $i$ and round items $e_{p}$ using the
biased threshold rounding. We show that at least one of the following rounding
schemes gives a total subsidy of at most $4/3$.

  * •

Scheme 1. We round item $e_{i}$ to the attached agent.

  * •

Scheme 2. We round item $e_{i}$ to agent $i$.

By a similar argument as in Lemma B.12, the total subsidy required for scheme
1 is at most

$(x_{i}-y_{i})^{+}+x_{j}+\frac{1+x_{p}}{2}.$ (14)

For scheme 2, the total required subsidy can be bounded by

$y_{i}+x_{j}+\frac{1+x_{p}}{2}.$ (15)

When $x_{i}-y_{i}\geq 0$, the sum of the above two upper bounds is

$x_{i}+2x_{j}+(1+x_{p})\leq 2+x_{j}<\frac{7}{3}.$

Hence at least one of the two rounding schemes is with total subsidy bounded
by $7/6<4/3$.

When $x_{i}-y_{i}<0$, Equation (14) becomes

$x_{j}+\frac{1+x_{p}}{2}.$

Consider another rounding scheme that rounds item $e_{0}$ to agent $j$, rounds
item $e_{i}$ using the threshold rounding, and rounds item $e_{p}$ using the
biased threshold rounding. The total subsidy is at most

$x_{i}+\frac{1}{2}+\frac{1+x_{p}}{2}.$

Summing up the above two upper bounds leads to

$x_{i}+x_{j}+x_{p}+\frac{3}{2}=\frac{5}{2}.$

Hence at least one of the rounding schemes requires subsidy at most
$\frac{5}{4}<\frac{4}{3}$. ∎

######  Lemma B.14.

For an expanded atom-path with $2\leq k\leq 3$ and $h=k-1$, there exists a
rounding scheme with total subsidy at most $(k+h)/3$.

###### Proof.

For $k=3$, the upper bound is $\frac{2k-1}{3}=\frac{5}{3}$. Note that there
exists two agents $i,j$ such that ${e_{i}}={e_{j}}=\bot$. Let $p,q$ be the two
agents other than $i,j$. Consider the rounding scheme that rounds $e_{0}$ to
$\operatorname*{argmax}\\{x_{i},x_{j}\\}$, say agent $i$. Applying the biased
threshold rounding to items $e_{p}$ and $e_{q}$, we can upper bound the total
required subsidy by

$\frac{1+x_{p}}{2}+\frac{1+x_{q}}{2}+x_{j}=1+\frac{x_{p}+x_{q}+2\cdot
x_{j}}{2}\leq 1+\frac{x_{p}+x_{q}+x_{j}+x_{i}}{2}=\frac{3}{2}.$

For $k=2$, the upper bound is $\frac{2k-1}{3}=1$. Note that there exist two
agents $i,j$ such that ${e_{i}}={e_{j}}=\bot$. Let $p$ be the agent other than
$i,j$ (who has an attached edge). We round $e_{0}$ to
$\operatorname*{argmax}\\{x_{i},x_{j}\\}$, say agent $i$, and apply the biased
threshold rounding to items $e_{p}$. The total required subsidy is at most

$\frac{1+x_{p}}{2}+x_{j}=\frac{1+x_{p}+2\cdot
x_{j}}{2}\leq\frac{1+x_{p}+x_{j}+x_{i}}{2}=1.\qed$