#  Proportional Allocation of Indivisible Goods
up to the Least Valued Good on Average††thanks: An earlier version of this
work was presented in ISAAC 2022[21].

Ryoga Mahara Department of Mathematical Informatics, University of Tokyo.
E-mail<EMAIL_ADDRESS>
###### Abstract

We study the problem of fairly allocating a set of indivisible goods to
multiple agents and focus on the proportionality, which is one of the
classical fairness notions. Since proportional allocations do not always exist
when goods are indivisible, approximate concepts of proportionality have been
considered in the previous work. Among them, proportionality up to the maximin
good (PROPm) has been the best approximate notion of proportionality that can
be achieved for all instances [5]. In this paper, we introduce the notion of
proportionality up to the least valued good on average (PROPavg), which is a
stronger notion than PROPm, and show that a PROPavg allocation always exists
for all instances and can be computed in polynomial time. Our results
establish PROPavg as a notable non-trivial fairness notion that can be
achieved for all instances. Our proof is constructive, and based on a new
technique that generalizes the cut-and-choose protocol and uses a recursive
technique.

##  1 Introduction

###  1.1 Proportional Allocation of Indivisible Goods

We study the problem of fairly allocating a set of indivisible goods to
multiple agents under additive valuations. Fair division of indivisible goods
is a fundamental and well-studied problem in Economics and Computer Science.
We are given a set $M$ of $m$ indivisible goods and a set $N$ of $n$ agents
with individual valuations. Under additive valuations, each agent $i\in N$ has
a value $v_{i}(\\{g\\})\geq 0$ for each good $g$ and her value for a bundle
$S$ of goods is equal to the sum of the values of each good $g\in S$, i.e.,
$v_{i}(S)=\sum_{g\in S}v_{i}(\\{g\\})$. An indivisible good can not be split
among multiple agents and this causes finding a fair division to be a
difficult task.

One of the standard notions of fairness is proportionality (PROP). Let an
allocation $X=(X_{1},X_{2},\ldots,X_{n})$ denote a partition of $M$ to $N$
into $n$ bundles such that $X_{i}$ is allocated to agent $i$. An allocation
$X$ is proportional if $v_{i}(X_{i})\geq\frac{1}{n}v_{i}(M)$ holds for each
agent $i$. In other words, in a proportional allocation, every agent receives
a set of goods whose value is at least $1/n$ fraction of the value of the
entire set. Unfortunately, proportional allocations do not always exist when
goods are indivisible. For instance, when allocating a single indivisible good
to more than one agents it is impossible to achieve any proportional
allocation. Thus, several relaxations of proportionality such as PROP1, PROPx,
and PROPm have been considered in the previous work.

Each of these notions requires that each agent $i\in N$ receives value at
least $\frac{1}{n}v_{i}(M)-d_{i}(X)$, where $d_{i}(X)$ is a nonnegative real
number appropriately defined for each notion. Proportionality up to the
largest valued good (PROP1) is a relaxation of proportionality that was
introduced by Conitzer et al. [16]. PROP1 requires $d_{i}(X)$ to be the
largest value that agent $i$ has for any good allocated to other agents, i.e.,
$d_{i}(X)=\max_{k\in N\setminus\\{i\\}}\max_{g\in X_{k}}v_{i}(\\{g\\})$. It is
shown in [16] that there always exists a Pareto optimal111An allocation
$X=(X_{1},\ldots,X_{n})$ is Pareto optimal if there is no allocation
$Y=(Y_{1},\ldots,Y_{n})$ such that $v_{i}(Y_{i})\geq v_{i}(X_{i})$ for any
agent $i$, and there exists an agent $j$ such that
$v_{j}(Y_{j})>v_{j}(X_{j})$. allocation that satisfies PROP1\. Moreover, Aziz
et al. [3] presented a polynomial-time algorithm that finds a PROP1 and Pareto
optimal allocation even in the presence of chores, i.e., some items can have
negative value.

Another relaxation is proportionality up to the least valued good (PROPx),
which is much stronger than ${\textsf{PROP}}1$. PROPx requires $d_{i}(X)$ to
be the least value that agent $i$ has for any good allocated to other agents,
i.e., $d_{i}(X)=\min_{k\in N\setminus\\{i\\}}\min_{g\in X_{k}}v_{i}(\\{g\\})$.
Moulin [26] gave an example for which no PROPx allocation exists, and Aziz et
al. [3] gave a simpler example.

Recently, Baklanov et al. [4] introduced proportionality up to the maximin
good (PROPm). PROPm requires $d_{i}(X)=\max_{k\in N\setminus\\{i\\}}\min_{g\in
X_{k}}v_{i}(\\{g\\})$, which shows that PROPm is the notion between PROP1 and
PROPx. It is shown in [4] that a PROPm allocation always exists for instances
with at most five agents, and later Baklanov et al. [5] showed that there
always exists a PROPm allocation for any instance and it can be computed in
polynomial time. To the best of our knowledge, PROPm has been the best
approximate notion of proportionality that is shown to exist for all
instances.

However, PROPm is not a good enough relaxation of proportionality in some
cases. For example, suppose that there exists a good $g\in M$ for which every
agent has value at least $1/n$ fraction of the value of $M$. Then allocating
$g$ to some agent $i$ and allocating all the goods in $M\setminus\\{g\\}$ to
another agent achieves a PROPm allocation, whereas it will be better to
allocate $M\setminus\\{g\\}$ to $N\setminus\\{i\\}$ in a fair manner (see
Example 1). This motivates the study of better relaxations of proportionality
than PROPm.

###  1.2 Our Contribution

In this paper, we introduce proportionality up to the least valued good on
average (PROPavg), a new relaxation of proportionality, and show that there
always exists a PROPavg allocation for all instances and can be computed in
polynomial time. PROPavg requires $d_{i}(X)$ to be the average of minimum
values that agent $i$ has for any good allocated to other agents, i.e.,
$d_{i}(X)=\frac{1}{n-1}\sum_{k\in N\setminus\\{i\\}}\min_{g\in
X_{k}}v_{i}(\\{g\\})$. It is easy to see that PROPavg implies PROPm. Note that
a similar and slightly stronger notion was introduced by Baklanov et al. [4]
with the name of Average-EFX (Avg-EFX), where $d_{i}(X)=\frac{1}{n}\sum_{k\in
N\setminus\\{i\\}}\min_{g\in X_{k}}v_{i}(\\{g\\})$. It remains open whether an
Avg-EFX allocation always exists even in the case of four agents. The
following example demonstrates that PROPavg (or Avg-EFX) is a reasonable
relaxation of proportionality compared to PROPm.

######  Example 1.

Suppose that $N=\\{1,2,3\\}$, $M=\\{g_{1},g_{2},g_{3},g_{4}\\}$, and each
agent has an identical additive valuation defined as follows:
$v(\\{g_{1}\\})=10,v(\\{g_{2}\\})=v(\\{g_{3}\\})=7,v(\\{g_{4}\\})=6$.

Table 1 summarizes whether several allocations satisfy or not each fairness
notions in this instance. As $v(\\{g_{1}\\})\geq 10$, the allocation
$(\\{g_{1},g_{2},g_{3},g_{4}\\},\emptyset,\emptyset)$ satisfies PROP1 even
though agent $2$ and $3$ receive no good. Similarly, the allocation
$(\\{g_{1}\\},\\{g_{2},g_{3},g_{4}\\},\emptyset)$ satisfies PROPm even though
agent $3$ receives no good. It is easy to see that every agent has to receive
at least one good in any PROPavg allocation in this instance.

Table 1: The relationship between several allocations and fairness notions in Example 1. The symbol “✓” indicates that the corresponding allocation satisfies the corresponding fairness. The symbol “✗” indicates that the corresponding allocation does not satisfy the corresponding fairness. See Section 1.4 for the definition of EFX. | EFX | PROPavg | PROPm |  PROP1
---|---|---|---|---
$(\\{g_{1}\\},\\{g_{2},g_{4}\\},\\{g_{3}\\})$ | ✓ | ✓ | ✓ | ✓
$(\\{g_{1}\\},\\{g_{2},g_{3}\\},\\{g_{4}\\})$ | ✗ | ✓ | ✓ | ✓
$(\\{g_{1}\\},\\{g_{2},g_{3},g_{4}\\},\emptyset)$ | ✗ | ✗ | ✓ | ✓
$(\\{g_{1},g_{2},g_{3},g_{4}\\},\emptyset,\emptyset)$ | ✗ | ✗ | ✗ | ✓

The main contribution of this paper is the following theorem which extends the
results on PROPm allocations shown by Baklanov et al. [5].

######  Theorem 2.

There always exists a PROPavg allocation when each agent has a non-negative
additive valuation. Furthermore, it can be computed in polynomial time.

Known results on relaxations of proportionality are summarized in Table 2.

Table 2: Relaxations of Proportionality | $d_{i}(X)$ | Does it always exist? | Time complexity
---|---|---|---
PROPx | $\min_{k\in N\setminus\\{i\\}}\min_{g\in X_{k}}v_{i}(\\{g\\})$ | No [26, 3] | –
Avg-EFX | $\frac{1}{n}\sum_{k\in N\setminus\\{i\\}}\min_{g\in X_{k}}v_{i}(\\{g\\})$ | Open | Open
PROPavg | $\frac{1}{n-1}\sum_{k\in N\setminus\\{i\\}}\min_{g\in X_{k}}v_{i}(\\{g\\})$ | Yes (our result) | Polynomial time (our result)
PROPm | $\max_{k\in N\setminus\\{i\\}}\min_{g\in X_{k}}v_{i}(\\{g\\})$ | Yes [5] | Polynomial time
PROP1 | $\max_{k\in N\setminus\\{i\\}}\max_{g\in X_{k}}v_{i}(\\{g\\})$ | Yes [3] | Polynomial time

###  1.3 Our Techniques

Our algorithm can be seen as a generalization of cut-and-choose protocol,
which is a well-known procedure to fairly allocate resources between two
agents. In the cut-and-choose protocol, one agent partitions resources into
two bundles for her valuation, and then the other agent chooses the best
bundle of the two for her valuation. We generalize this protocol from two
agents to $n$ agents in the following way: some $n-1$ agents partition the
goods into $n$ bundles, and then the remaining agent chooses the best bundle
among them for her valuation. To apply this protocol, it suffices to show that
there exists a partition of the goods into $n$ bundles such that no matter
which bundle the remaining agent chooses, the remaining $n-1$ bundles can be
allocated to the first $n-1$ agents fairly.

In our algorithm, we find such a partition by using an auxiliary graph called
PROPavg-graph. A formal definition of the PROPavg-graph is given in Section 3.
In Section 4, we show the existence of a PROPavg allocation by constructing a
pseudo-polynomial time algorithm for finding it. In Section 5, by improving
our algorithm in Section 4, we show how to find a PROPavg allocation in
polynomial time.

Let us emphasize that introducing the PROPavg-graph is a key technical
ingredient in this paper. It is also worth noting that Hall’s marriage theorem
[20], a classical and famous result in discrete mathematics, plays an
important role in our argument.

###  1.4 Related Work

Fair division of divisible resources is a classical topic starting from the
1940’s [29] and has a long history in multiple fields such as Economics,
Social Choice Theory, and Computer Science[28, 8, 9, 25]. On the other hand,
fair division of indivisible items has actively studied in recent years (see,
e.g., [2] for a recent survey).

In the context of fair division, besides proportionality, envy-freeness (EF)
is another well-studied notion of fairness. An allocation is called envy-free
if for each agent, she receives a set of goods for which she has value at
least value of the set of goods any other agent receives. As in the
proportionality case, envy-free allocations do not always exist when goods are
indivisible, and several relaxations of envy-freeness have been considered.
Among them, a notable one is envy-freeness up to one good (EF1) [10]. It is
known that there always exists an EF1 allocation, and it can be computed in
polynomial time [22]. Another notable relaxation is envy-freeness up to any
good (EFX) [12]. An allocation $X=(X_{1},\ldots,X_{n})$ is called EFX if for
any pair of agents $i,j\in N$, $v_{i}(X_{i})\geq v_{i}(X_{j})-m_{i}(X_{j})$,
where $m_{i}(X_{j})$ is the value of the least valuable good for agent $i$ in
$X_{j}$. It is one of the major open problems in fair division whether EFX
allocations always exist or not. As mentioned in [4], it is easy to see that
EFX implies Avg-EFX. As with EFX, it is not known whether Avg-EFX allocations
always exist for instances with four or more agents. The relationship among
notions mentioned above and the existence results are summarized in Figure 1.

Figure 1: The relationship among some fairness notions and the existence
results for these fairness notions. EF, PROP, and PROPx do not always exist,
whereas PROPavg, PROPm, EF1, and PROP1 always exist when each agent has non-
negative additive valuation. It is not known whether EFX or Avg-EFX always
exist or not for all instances.

There have been several studies on the existence of an EFX allocation for
restricted cases. Plaut and Roughgarden [27] showed that an EFX allocation
always exists for instances with two agents even when each agent can have more
general valuations than additive valuations. Chaudhury et al. [13] showed that
an EFX allocation always exists for instances with three agents. It is not
known whether EFX allocations always exist even in the case of four agents
having additive valuations. There are several studies of the cases with
restricted valuations. For example, there always exists an EFX allocation when
valuations are identical [27], two types [23, 24], binary [6, 17], or bi-
valued [1].

Another approach related to EFX is a setting to allow unallocated goods, which
is known as EFX-with-charity. Obviously, without any constraints, the problem
is trivial: leaving all goods unallocated results in an envy-free allocation.
Thus, the goal here is to find allocations with better guarantees. For
additive valuations, Caragiannis et al. [11] showed that there exists an EFX
allocation with some unallocated goods where every agent receives at least
half the value of her bundle in a maximum Nash social welfare
allocation222This is an allocation that maximizes
$\Pi_{i=1}^{n}v_{i}(X_{i})$.. For normalized and monotone valuations,
Chaudhury et al. [15] showed that there exist an EFX allocation and a set of
unallocated goods $U$ such that every agent has value for her own bundle at
least value for $U$, and $|U|<n$. Berger et al. [7] showed that the number of
the unallocated goods can be decreased to $n-2$, and to just one for the case
of four agents having nice cancelable valuations, which are more general than
additive valuations. Mahara [24] showed that the number of the unallocated
goods can be decreased to $n-2$ for normalized and monotone valuations, which
are more general than nice cancelable valuations. For additive valuations,
Chaudhury et al. [14] presented a polynomial-time algorithm for finding an
approximate EFX allocation with at most a sublinear number of unallocated
goods and high Nash social welfare.

##  2 Preliminaries

Let $N=\\{1,\ldots,n\\}$ be a set of $n$ agents and $M$ be a set of $m$ goods.
We assume that goods are indivisible: a good can not be split among multiple
agents. Each agent $i\in N$ has a non-negative valuation
$v_{i}:2^{M}\rightarrow\mathbb{R}_{\geq 0}$, where $2^{M}$ is the power set of
$M$. We assume that each valuation $v_{i}$ is additive, i.e.,
$v_{i}(S)=\sum_{g\in S}v_{i}(\\{g\\})$ for any $S\subseteq M$. Note that since
valuations are non-negative and additive, they have to be normalized:
$v_{i}(\emptyset)=0$ and monotone: $S\subseteq T$ implies $v_{i}(S)\leq
v_{i}(T)$ for any $S,T\subseteq M$. For ease of explanation, we normalize the
valuations so that $v_{i}(M)=1$ for all $i\in N$.

To simplify notation, we denote $\\{1,\ldots,k\\}$ by $[k]$ for any positive
integer $k$, write $v_{i}(g)$ instead of $v_{i}(\\{g\\})$ for $g\in M$, and
use $S\setminus g$ and $S\cup g$ instead of $S\setminus\\{g\\}$ and
$S\cup\\{g\\}$, respectively.

We say that $X=(X_{1},X_{2},\ldots,X_{n})$ is an allocation of $M$ to $N$ if
it is a partition of $M$ into $n$ disjoint subsets such that each set is
indexed by $i\in N$. Each $X_{i}$ is the set of goods given to agent $i$,
which we call a bundle. It is simply called an allocation to $N$ if $M$ is
clear from context. For $i\in N$ and $S\subseteq M$, let $m_{i}(S)$ denote the
value of the least valuable good for agent $i$ in $S$, that is,
$m_{i}(S)=\min_{g\in S}\\{v_{i}(g)\\}$ if $S\neq\emptyset$ and
$m_{i}(\emptyset)=0$. For an allocation $X=(X_{1},X_{2},\ldots,X_{n})$ to $N$,
we say that an agent $i$ is PROPavg-satisfied by $X$ if v_i(X_i)
+1n-1∑_k∈[n]∖i m_i(X_k) ≥1n, where we recall that $v_{i}(M)=1$. In other
words, agent $i$ receives a set of goods for which she has value at least
$1/n$ fraction of her total value minus the average of minimum value of the
set of goods any other agent receives. An allocation $X$ is called PROPavg if
every agent $i\in N$ is PROPavg-satisfied by $X$.

Let $G=(V,E)$ be a graph. For $S\subseteq V$, let $\Gamma_{G}(S)=\\{v\in
V\setminus S\mid(s,v)\in E~{}\text{for some}~{}s\in S\\}$ denote the set of
neighbors of $S$ in $G$. For $v\in V$, let $G-v$ denote the graph obtained
from $G$ by deleting $v$. A perfect matching in $G$ is a set of pairwise
disjoint edges of $G$ covering all the vertices of $G$.

##  3 Key Ingredient: PROPavg-Graph

In order to prove Theorem 2, we give an algorithm for finding a PROPavg
allocation. As described in Section 1.3, our algorithm is a generalization of
the cut-and-choose protocol that consists of the following three steps.

  1. 1.

We partition the goods into $n$ bundles without assigning them to agents.

  2. 2.

A specified agent, say $n$, chooses the best bundle for her valuation.

  3. 3.

We determine an assignment of the remaining bundles to the agents in
$N\setminus n$.

The partition given in the first step is represented by an allocation of $M$
to a newly introduced set of size $n$, say $V_{2}$, and the assignment in the
third step is represented by a matching in an auxiliary bipartite graph, which
we call PROPavg-graph. In this section, we define the PROPavg-graph and its
desired properties.

Let $V_{2}$ be a set of $n$ elements and fix a specified element $r\in V_{2}$.
We say that $X=(X_{u})_{u\in V_{2}}$ is an allocation to $V_{2}$ if it is a
partition of $M$ into $n$ disjoint subsets such that each set is indexed by an
element in $V_{2}$, that is, $\bigcup_{u\in V_{2}}X_{u}=M$ and $X_{u}\cap
X_{u^{\prime}}=\emptyset$ for distinct $u,u^{\prime}\in V_{2}$. For an
allocation $X=(X_{u})_{u\in V_{2}}$ to $V_{2}$, we define a bipartite graph
$G_{X}=(V_{1},V_{2};E)$ called PROPavg-graph as follows. The vertex set
consists of $V_{1}=N\setminus n$ and $V_{2}$, and the edge set $E$ is defined
by (i,u) ∈E ⇔v_i(X_u)+1n-1∑_u’∈V_2 ∖{r, u} m_i(X_u’) ≥1n for $i\in V_{1}$ and
$u\in V_{2}$. It should be emphasized that the summation is taken over
$V_{2}\setminus\\{r,u\\}$, i.e., $m_{i}(X_{r})$ is not counted, in the above
definition, which is crucial in our argument. The following lemma shows that
the PROPavg-graph is closely related to the definition of PROPavg-
satisfaction.

######  Lemma 3.

Suppose that $G_{X}=(V_{1},V_{2};E)$ is the PROPavg-graph for an allocation
$X=(X_{u})_{u\in V_{2}}$ to $V_{2}$. Let $\sigma$ be a bijection from $N$ to
$V_{2}$ and define an allocation $Y=(Y_{1},\ldots,Y_{n})$ to $N$ by
$Y_{i}=X_{\sigma(i)}$ for $i\in N$. For $i^{*}\in V_{1}$, if
$(i^{*},\sigma(i^{*}))\in E$, then $i^{*}$ is PROPavg-satisfied by $Y$.

###### Proof.

Let $u^{*}=\sigma(i^{*})$ and suppose that $(i^{*},u^{*})\in E$. We directly
obtain

$v_{i^{*}}(Y_{i^{*}})+\frac{1}{n-1}\sum_{j\in[n]\setminus{i^{*}}}m_{i^{*}}(Y_{j})\geq
v_{i^{*}}(X_{u^{*}})+\frac{1}{n-1}\sum_{u\in
V_{2}\setminus\\{u^{*},r\\}}m_{i^{*}}(X_{u})\geq\frac{1}{n},$

where the first inequality follows from the definition of $Y$ and
$m_{i^{*}}(X_{r})\geq 0$, and the second inequality follows from
$(i^{*},u^{*})\in E$. ∎

Figure 2: An example of $(a)$ represents a PROPavg-graph $G_{X}$ corresponding
to $X$ that satisfies (P1) but does not satisfy (P2). An example of $(b)$
represents a PROPavg-graph $G_{X}$ corresponding to $X$ that satisfies (P2).

For an allocation $X=(X_{u})_{u\in V_{2}}$ to $V_{2}$, we consider the
following two properties, which play an important role in our argument.

(P1)

$G_{X}-r$ has a perfect matching.

(P2)

For any $u\in V_{2}$, $G_{X}-u$ has a perfect matching.

Obviously, property (P2) is stronger than property (P1). Roughly speaking, our
goal is to find an allocation $X=(X_{u})_{u\in V_{2}}$ to $V_{2}$ satisfying
(P2). As shown later, we find an allocation $X=(X_{u})_{u\in V_{2}}$ to
$V_{2}$ satisfying (P2) while keeping (P1). Examples of a PROPavg-graph
$G_{X}$ corresponding to $X$ satisfying (P1) or (P2) are described in Figure
2. We can rephrase these conditions by using the following classical theorem
known as Hall’s marriage theorem in discrete mathematics.

######  Theorem 4 (Hall’s marriage theorem [20]).

Suppose that $G=(A,B;E)$ is a bipartite graph with $|A|=|B|$. Then, $G$ has a
perfect matching if and only if $|S|\leq|\Gamma_{G}(S)|$ for any $S\subseteq
A$.

The property (P1) is equivalent to $|S|\leq|\Gamma_{G_{X}-r}(S)|$ for any
$S\subseteq V_{1}$ by this theorem. The property (P2) is equivalent to
$|S|\leq|\Gamma_{G_{X}-u}(S)|$ for any $u\in V_{2}$ and $S\subseteq V_{1}$ by
Hall’s marriage theorem. By simple observation, we can obtain another
characterization of property (P2).

######  Lemma 5.

Let $X=(X_{u})_{u\in V_{2}}$ be an allocation to $V_{2}$. Then, $X$ satisfies
(P2) if and only if $|S|+1\leq|\Gamma_{G_{X}}(S)|$ for any non-empty subset
$S\subseteq V_{1}$.

###### Proof.

By Hall’s marriage theorem, it is sufficient to show that the following two
conditions are equivalent:

  1. (i)

$|S|\leq|\Gamma_{G_{X}-u}(S)|$ for any $u\in V_{2}$ and $S\subseteq V_{1}$,
and

  2. (ii)

$|S|+1\leq|\Gamma_{G_{X}}(S)|$ for any non-empty subset $S\subseteq V_{1}$.

Suppose that (i) holds. Let $S$ be a nonempty subset of $V_{1}$. Since (i)
implies that $|\Gamma_{G_{X}}(S)|\geq|S|\geq 1$, we obtain
$\Gamma_{G_{X}}(S)\not=\emptyset$. Let $u\in\Gamma_{G_{X}}(S)$. By (i) again,
we obtain $|\Gamma_{G_{X}}(S)|=|\Gamma_{G_{X}-u}(S)|+1\geq|S|+1$. This shows
(ii).

Conversely, suppose that (ii) holds. Let $u\in V_{2}$ and let $S\subseteq
V_{1}$. If $S=\emptyset$, then it clearly holds that
$|S|\leq|\Gamma_{G_{X}-u}(S)|$. If $S\neq\emptyset$, then we have
$|S|+1\leq|\Gamma_{G_{X}}(S)|\leq|\Gamma_{G_{X}-u}(S)|+1$, which implies that
$|S|\leq|\Gamma_{G_{X}-u}(S)|$. This shows (i). ∎

##  4 Existence of a PROPavg Allocation

In this section, we show that there always exists a PROPavg allocation by
constructing a pseudo-polynomial time algorithm for finding it. Improvements
in time complexity are discussed in Section 5. Our algorithm begins with
obtaining an initial allocation ${X}=(X_{u})_{u\in V_{2}}$ to $V_{2}$
satisfying (P1). Unless $X$ satisfies (P2), we appropriately choose a good in
$\bigcup_{u\in V_{2}\setminus r}X_{u}$ and move it to $X_{r}$ while keeping
(P1). Finally, we get an allocation ${X^{*}}=(X^{*}_{u})_{u\in V_{2}}$ to
$V_{2}$ satisfying (P2). As we will see later, we can obtain a PROPavg
allocation to $N$ from $X^{*}$.

###  4.1 Our Algorithm

In order to obtain an initial allocation ${X}=(X_{u})_{u\in V_{2}}$ to $V_{2}$
satisfying (P1), we use the following previous result about EFX-with-charity.

######  Theorem 6 (Chaudhury et al. [15]).

For normalized and monotone valuations, there always exists an allocation
$X=(X_{1},\ldots,X_{n})$ of $M\setminus U$ to $N$, where $U$ is a set of
unallocated goods, such that

  * •

X is EFX, that is, $v_{i}(X_{i})+m_{i}(X_{j})\geq v_{i}(X_{j})$ for any pair
of agents $i,j\in N$,

  * •

$v_{i}(X_{i})\geq v_{i}(U)$ for any agent $i\in N$, and

  * •

$|U|<n$.

The following lemma shows that by applying Theorem 6 to agents $N\setminus n$,
we can obtain an initial allocation ${X}=(X_{u})_{u\in V_{2}}$ to $V_{2}$
satisfying (P1).

######  Lemma 7.

There exists an allocation ${X}=(X_{u})_{u\in V_{2}}$ to $V_{2}$ satisfying
(P1).

###### Proof.

By applying Theorem 6 to agents $N\setminus n$, we can obtain an allocation
$Y=(Y_{1},\ldots,Y_{n-1})$ of $M\setminus U$ to $N\setminus n$, where $U$ is a
set of unallocated goods, satisfying the conditions in Theorem 6. Let
$V_{2}=\\{r,u_{1},\dots,u_{n-1}\\}$ and define an allocation $X=(X_{u})_{u\in
V_{2}}$ to $V_{2}$ as $X_{u_{j}}=Y_{j}$ for $j\in[n-1]$ and $X_{r}=U$. Let
$G_{X}=(V_{1},V_{2};E)$ be the PROPavg-graph for $X$. We show that $X$
satisfies (P1).

Fix any agent $i\in V_{1}$. We have $v_{i}(X_{u_{i}})+m_{i}(X_{u_{j}})\geq
v_{i}(X_{u_{j}})$ for any $j\in[n-1]\setminus i$ since $Y$ is EFX and
$X_{u_{j}}=Y_{j}$. We also have $v_{i}(X_{u_{i}})=v_{i}(Y_{i})\geq
v_{i}(U)=v_{i}(X_{r})$ and a trivial inequality $v_{i}(X_{u_{i}})\geq
v_{i}(X_{u_{i}})$. By summing up these inequalities, we obtain $n\cdot
v_{i}(X_{u_{i}})+\sum_{j\in[n-1]\setminus i}m_{i}(X_{u_{j}})\geq\sum_{u\in
V_{2}}v_{i}(X_{u})$. Since $\sum_{u\in V_{2}}v_{i}(X_{u})=v_{i}(M)=1$, this
shows that $v_{i}(X_{u_{i}})+\frac{1}{n}\sum_{j\in[n-1]\setminus
i}m_{i}(X_{u_{j}})\geq\frac{1}{n}$, and hence $(i,u_{i})\in E$. Therefore,
$G_{X}-r$ has a perfect matching $\\{(i,u_{i})\mid i\in[n-1]\\}$, which
implies that $X$ satisfies (P1). ∎

The following lemma shows that if we obtain an allocation ${X}=(X_{u})_{u\in
V_{2}}$ to $V_{2}$ satisfying (P2), then there exists a PROPavg allocation to
$N$.

######  Lemma 8.

Suppose that ${X}=(X_{u})_{u\in V_{2}}$ is an allocation to $V_{2}$ satisfying
(P2). Then, we can construct a PROPavg allocation to $N$.

###### Proof.

Let ${X}=(X_{u})_{u\in V_{2}}$ be an allocation to $V_{2}$ satisfying (P2).
First, agent $n$ chooses the best bundle $X_{u^{*}}$ for her valuation among
$\\{X_{u}\mid u\in V_{2}\\}$ (if there is more than one such bundle, choose
one arbitrarily). Since $X$ satisfies (P2), there exists a perfect matching
$A$ in $G_{X}-{u^{*}}$. For each agent $i\in V_{1}(=N\setminus n)$, the bundle
that matches $i$ in $A$ is allocated to $i$. By Lemma 3, agent $i$ is PROPavg-
satisfied for each agent $i\in V_{1}$. Furthermore, since we have
$v_{n}(X_{u^{*}})=\max_{u\in V_{2}}v_{n}(X_{u})\geq\frac{1}{n}$, agent $n$ is
also PROPavg-satisfied. Therefore, the obtained allocation is a PROPavg
allocation to $N$. ∎

The following proposition shows how we update an allocation in each iteration,
whose proof is given in Section 4.2.

######  Proposition 9.

Suppose that $X=(X_{u})_{u\in V_{2}}$ is an allocation to $V_{2}$ that
satisfies (P1) but does not satisfy (P2). Then, there exists another
allocation $X^{\prime}=(X^{\prime}_{u})_{u\in V_{2}}$ to $V_{2}$ satisfying
(P1) such that $|X^{\prime}_{r}|=|X_{r}|+1$.

As we will see in Section 4.2, an allocation $X^{\prime}$ in Proposition 9 is
obtained by moving some appropriate item $g\in\bigcup_{u\in V_{2}\setminus
r}X_{u}$ to $X_{r}$. If Proposition 9 holds, then we can show that there
always exists a PROPavg allocation when each agent has a non-negative additive
valuation as follows. See also Algorithm 1.

By Lemma 7, we first obtain an initial allocation $X=(X_{u})_{u\in V_{2}}$ to
$V_{2}$ satisfying (P1). By Proposition 9, unless $X$ satisfies (P2), we can
increase $|X_{r}|$ by one while keeping the condition (P1). Since
$|X_{r}|\leq|M|$, this procedure terminates in at most $m$ steps, and we
finally obtain an allocation ${X}^{*}$ to $V_{2}$ satisfying (P2). Therefore,
there exists a PROPavg allocation to $N$ by Lemma 8.

Algorithm 1 Algorithm for finding a PROPavg allocation

1:agents $N$, goods $M$, and valuation $v_{i}$ for each $i\in N$

2:a PROPavg allocation to $N$

3:Apply Lemma 7 to obtain an allocation $X$ to $V_{2}$ satisfying (P1).

4:while $X$ does not satisfy (P2) do

5: Apply Proposition 9 to $X$ and obtain another allocation $X^{\prime}$ to
$V_{2}$.

6: $X\leftarrow X^{\prime}$.

7:Apply Lemma 8 to obtain a PROPavg allocation to $N$.

###  4.2 Proof of Proposition 9

Let $X=(X_{u})_{u\in V_{2}}$ be an allocation to $V_{2}$. For $u^{*}\in
V_{2}\setminus r$ and $g\in X_{u^{*}}$, we say that an allocation
$X^{\prime}=(X^{\prime}_{u})_{u\in V_{2}}$ to $V_{2}$ is obtained from $X$ by
moving $g$ to $X_{r}$ if

$\displaystyle X^{\prime}_{u}$
$\displaystyle=\left\\{\begin{array}[]{ll}X_{r}\cup g&{\rm if}~{}u=r,\\\
X_{u^{*}}\setminus g&{\rm if}~{}u=u^{*},\\\ X_{u}&{\rm
otherwise}.\end{array}\right.$

The following lemma guarantees that if there exists an agent $i\in V_{1}$ such
that $(i,r)\not\in E$ in the PROPavg-graph $G_{X}=(V_{1},V_{2};E)$, then we
can move some good in $\bigcup_{u\in V_{2}\setminus r}X_{u}$ to $X_{r}$ so
that the edges incident to $i$ do not disappear. This lemma is crucial in the
proof of Proposition 9.

######  Lemma 10.

Let $X=(X_{u})_{u\in V_{2}}$ be an allocation to $V_{2}$ and let $i\in V_{1}$
be an agent such that $(i,r)\not\in E$ in the PROPavg-graph
$G_{X}=(V_{1},V_{2};E)$. Then, there exist $u^{*}\in V_{2}$ and $g\in
X_{u^{*}}$ such that $(i,u^{*})\in E$, $|X_{u^{*}}|\geq 2$, and the following
property holds: if an allocation $X^{\prime}$ to $V_{2}$ is obtained from $X$
by moving $g$ to $X_{r}$, then the corresponding PROPavg-graph
$G_{X^{\prime}}$ has an edge $(i,u^{*})$.

###### Proof.

We first show that $X_{u}\neq\emptyset$ for any $u\in V_{2}$ with $(i,u)\in
E$. Indeed, if $X_{u}=\emptyset$, then we have v_i(X_r)+1n-1∑_u’ ∈V_2∖r
m_i(X_u’)≥v_i(X_u) + 1n-1∑_u’ ∈V_2∖{r, u} m_i(X_u’)≥1n, where the first
inequality follows from $v_{i}(X_{u})=m_{i}(X_{u})=0$ and the second
inequality follows from $(i,u)\in E$. This contradicts $(i,r)\not\in E$.

To derive a contradiction, assume that $u^{*}$ and $g$ satisfying the
conditions in Lemma 10 do not exist. Then, we have the following claim.

######  Claim 11.

For any $u\in V_{2}$ with $(i,u)\in E$, we obtain

$v_{i}(X_{u})-m_{i}(X_{u})+\frac{1}{n-1}\sum_{\begin{subarray}{c}u^{\prime}\in
V_{2}\setminus\\{r,u\\}:\\\ (i,u^{\prime})\in
E\end{subarray}}m_{i}(X_{u^{\prime}})<\frac{1}{n}.$ (1)

###### Proof of the Claim.

Fix $u\in V_{2}$ with $(i,u)\in E$. Let $g$ be a good in $X_{u}$ that
minimizes $v_{i}(g)$, where we note that $X_{u}\not=\emptyset$ as described
above. Then, $v_{i}(g)=m_{i}(X_{u})$. Define
$X^{\prime}=(X^{\prime}_{u^{\prime}})_{u^{\prime}\in V_{2}}$ as the allocation
to $V_{2}$ that is obtained from $X$ by moving $g$ to $X_{r}$. Let
$G_{X^{\prime}}=(V_{1},V_{2};E^{\prime})$ be the PROPavg-graph corresponding
to $X^{\prime}$. Since $u$ and $g$ do not satisfy the conditions in Lemma 10
by our assumption, we have $(i,u)\not\in E^{\prime}$ or $|X_{u}|=1$.

If $(i,u)\in E^{\prime}$, then we obtain $|X_{u}|=1$, and hence

$\displaystyle v_{i}(X_{r})+\frac{1}{n-1}\sum_{u^{\prime}\in
V_{2}\setminus{r}}m_{i}(X_{u^{\prime}})$
$\displaystyle\geq\frac{1}{n-1}\sum_{u^{\prime}\in
V_{2}\setminus\\{r,u\\}}m_{i}(X_{u^{\prime}})$
$\displaystyle=v_{i}(X^{\prime}_{u})+\frac{1}{n-1}\sum_{u^{\prime}\in
V_{2}\setminus\\{r,u\\}}m_{i}(X^{\prime}_{u^{\prime}})$
$\displaystyle\geq\frac{1}{n},$

where the equality follows from $v_{i}(X^{\prime}_{u})=v_{i}(\emptyset)=0$ and
the last inequality follows from $(i,u)\in E^{\prime}$. This contradicts
$(i,r)\not\in E$.

Thus, it holds that $(i,u)\not\in E^{\prime}$. Since
$v_{i}(X_{u})-m_{i}(X_{u})=v_{i}(X^{\prime}_{u})$, we obtain

$\displaystyle
v_{i}(X_{u})-m_{i}(X_{u})+\frac{1}{n-1}\sum_{\begin{subarray}{c}u^{\prime}\in
V_{2}\setminus\\{r,u\\}:\\\ (i,u^{\prime})\in
E\end{subarray}}m_{i}(X_{u^{\prime}})$ $\displaystyle\leq
v_{i}(X_{u})-m_{i}(X_{u})+\frac{1}{n-1}\sum_{u^{\prime}\in
V_{2}\setminus\\{r,u\\}}m_{i}(X_{u^{\prime}})$
$\displaystyle=v_{i}(X^{\prime}_{u})+\frac{1}{n-1}\sum_{u^{\prime}\in
V_{2}\setminus\\{r,u\\}}m_{i}(X^{\prime}_{u^{\prime}})$
$\displaystyle<\frac{1}{n},$

where the last inequality follows from $(i,u)\not\in E^{\prime}$. ∎

By summing up inequality (1) for each $u\in V_{2}$ with $(i,u)\in E$, we
obtain the following inequality:

$\sum_{\begin{subarray}{c}u\in V_{2}:\\\ (i,u)\in
E\end{subarray}}v_{i}(X_{u})+\left(-1+\frac{l-1}{n-1}\right)\sum_{\begin{subarray}{c}u^{\prime}\in
V_{2}\setminus r:\\\ (i,u^{\prime})\in
E\end{subarray}}m_{i}(X_{u^{\prime}})<\frac{l}{n},$ (2)

where $l=|\\{u\in V_{2}\mid(i,u)\in E\\}|$.

On the other hand, for any $u\in V_{2}$ with $(i,u)\not\in E$, we have

$v_{i}(X_{u})+\frac{1}{n-1}\sum_{\begin{subarray}{c}u^{\prime}\in
V_{2}\setminus r:\\\ (i,u^{\prime})\in
E\end{subarray}}m_{i}(X_{u^{\prime}})\leq
v_{i}(X_{u})+\frac{1}{n-1}\sum_{u^{\prime}\in
V_{2}\setminus\\{r,u\\}}m_{i}(X_{u^{\prime}})<\frac{1}{n},$ (3)

where the both inequalities follow from $(i,u)\not\in E$. Summing up
inequality (3) for each $u\in V_{2}$ with $(i,u)\not\in E$, we obtain

$\sum_{\begin{subarray}{c}u\in V_{2}:\\\ (i,u)\not\in
E\end{subarray}}v_{i}(X_{u})+\left(\frac{n-l}{n-1}\right)\sum_{\begin{subarray}{c}u^{\prime}\in
V_{2}\setminus r:\\\ (i,u^{\prime})\in
E\end{subarray}}m_{i}(X_{u^{\prime}})<\frac{n-l}{n},$ (4)

where we note that $|\\{u\in V_{2}\mid(i,u)\not\in E\\}|=n-l$.

By taking the sum of inequalities (2) and (4), we obtain ∑_u∈V_2:(i,u)∈E
v_i(X_u)+ ∑_u∈V_2:(i,u)／∈E v_i(X_u) ¡ 1, which contradicts $\sum_{u\in
V_{2}}v_{i}(X_{u})=1$.

Therefore, there exist $u^{*}\in V_{2}$ and $g\in X_{u^{*}}$ satisfying the
conditions in Lemma 10. ∎

We are now ready to prove Proposition 9.

###### Proof of Proposition 9.

Suppose that $X=(X_{u})_{u\in V_{2}}$ is an allocation to $V_{2}$ that
satisfies (P1) but does not satisfy (P2). Let $G_{X}=(V_{1},V_{2};E)$ be the
PROPavg-graph corresponding to $X$. Since $X$ does not satisfy (P2), there
exists a non-empty set $S\subseteq V_{1}$ such that
$|S|+1>|\Gamma_{G_{X}}(S)|$ by Lemma 5. Among such sets, let $S^{*}\subseteq
V_{1}$ be an inclusion-wise minimal one. By the integrality of
$|\Gamma_{G_{X}}(S^{*})|$ and $|S^{*}|$, this means that
$|S^{*}|\geq|\Gamma_{G_{X}}(S^{*})|$ and $|S|+1\leq|\Gamma_{G_{X}}(S)|$ for
any non-empty proper subset $S\subsetneq S^{*}$. We now show some properties
of $S^{*}$.

######  Claim 12.

For any $i\in S^{*}$, it holds that $(i,r)\not\in E$.

###### Proof of the claim.

Since $X$ satisfies (P1), we have $|S^{*}|\leq|\Gamma_{G_{X}-r}(S^{*})|$ by
Hall’s marriage theorem. Hence, we obtain
$|S^{*}|\leq|\Gamma_{G_{X}-r}(S^{*})|\leq|\Gamma_{G_{X}}(S^{*})|\leq|S^{*}|$,
where the last inequality follows from the definition of $S^{*}$. This shows
that all the above inequalities are tight. Since
$|\Gamma_{G_{X}-r}(S^{*})|=|\Gamma_{G_{X}}(S^{*})|$, we obtain
$r\not\in\Gamma_{G_{X}}(S^{*})$, that is, $(i,r)\not\in E$ for any $i\in
S^{*}$. ∎

######  Claim 13.

For any non-empty proper subset $S\subsetneq S^{*}$, it holds that
$|S|+1\leq|\Gamma_{G_{X}-r}(S)|$.

###### Proof of the claim.

Let $S$ be a non-empty proper subset of $S^{*}$. Since $(i,r)\not\in E$ for
any $i\in S\subsetneq S^{*}$ by Claim 12, we have that
$\Gamma_{G_{X}}(S)=\Gamma_{G_{X}-r}(S)$. Hence, we obtain
$|S|+1\leq|\Gamma_{G_{X}}(S)|=|\Gamma_{G_{X}-r}(S)|$, where the inequality
follows from the minimality of $S^{*}$. ∎

######  Claim 14.

For any $i\in S^{*}$ and $u\in\Gamma_{G_{X}}(S^{*})$ with $(i,u)\in E$,
$G_{X}-r$ has a perfect matching in which $i$ matches $u$.

###### Proof of the claim.

Fix any $i\in S^{*}$ and $u\in\Gamma_{G_{X}}(S^{*})$ with $(i,u)\in E$. Note
that $r\not\in\Gamma_{G_{X}}(S^{*})$ by Claim 12, and hence $u\neq r$.

Since $X$ satisfies (P1), $G_{X}-r$ has a perfect matching $A$. In $A$, it is
obvious that every vertex in $S^{*}$ is matched to a vertex in
$\Gamma_{G_{X}-r}(S^{*})$. Conversely, every vertex in
$\Gamma_{G_{X}-r}(S^{*})$ is matched to a vertex in $S^{*}$ as
$|S^{*}|=|\Gamma_{G_{X}-r}(S^{*})|$ (see the proof of Claim 12). Thus, by
removing the edges between $S^{*}$ and $\Gamma_{G_{X}}(S^{*})$ from $A$, we
obtain a matching $A_{1}\subseteq A$ that exactly covers $V_{1}\setminus
S^{*}$ and $V_{2}\setminus(\Gamma_{G_{X}}(S^{*})\cup\\{r\\})$.

Let $G^{\prime}_{X}$ be the subgraph of $G_{X}$ induced by $(S^{*}\setminus
i)\cup(\Gamma_{G_{X}}(S^{*})\setminus u)$. We now show that $G^{\prime}_{X}$
has a perfect matching. Consider any $S\subseteq S^{*}\setminus i$. If
$S=\emptyset$, then it clearly holds that
$|S|\leq|\Gamma_{G^{\prime}_{X}}(S)|$. If $S\neq\emptyset$, then
$|S|+1\leq|\Gamma_{G_{X}-r}(S)|\leq|\Gamma_{G^{\prime}_{X}}(S)\cup
u|=|\Gamma_{G^{\prime}_{X}}(S)|+1$, where the first inequality is by Claim 13.
Therefore, $|S|\leq|\Gamma_{G^{\prime}_{X}}(S)|$ holds for any $S\subseteq
S^{*}\setminus i$, and hence $G^{\prime}_{X}$ has a perfect matching $A_{2}$
by Hall’s marriage theorem.

Then, $A_{1}\cup A_{2}\cup\\{(i,u)\\}$ is a desired perfect matching in
$G_{X}-r$. ∎

Figure 3: A PROPavg-graph $G_{X}$ corresponding to $X$ in the proof of
Proposition 9. A non-empty minimal subset $S^{*}$ of $V_{1}$ such that
$|S^{*}|+1>|\Gamma_{G_{X}}(S^{*})|$ is represented by vertices in the above
dotted rectangle.

Fix any agent $i^{*}\in S^{*}$. Since $(i^{*},r)\not\in E$ by Claim 12, by
applying Lemma 10 to agent $i^{*}$, we obtain $u^{*}\in V_{2}$ and $g\in
X_{u^{*}}$ satisfying the conditions in Lemma 10. See also Figure 3. Let
$X^{\prime}=(X^{\prime}_{u})_{u\in V_{2}}$ be the allocation to $V_{2}$
obtained from $X$ by moving $g$ to $X_{r}$ and let
$G_{X^{\prime}}=(V_{1},V_{2};E^{\prime})$ be the PROPavg-graph corresponding
to $X^{\prime}$. Then, the conditions in Lemma 10 show that $(i^{*},u^{*})\in
E\cap E^{\prime}$ and $|X_{u^{*}}|\geq 2$. We also see that $E^{\prime}$
satisfies the following.

######  Claim 15.

For any $i\in V_{1}$ and $u\in V_{2}\setminus u^{*}$, if $(i,u)\in E$ then
$(i,u)\in E^{\prime}$.

###### Proof of the claim.

Since $|X_{u^{*}}|\geq 2$, we have
$m_{i}(X^{\prime}_{u^{*}})=m_{i}(X_{u^{*}}\setminus g)\geq m_{i}(X_{u^{*}})$
for any agent $i\in V_{1}$. Hence, for any $i\in V_{1}$ and $u\in
V_{2}\setminus u^{*}$ with $(i,u)\in E$, we obtain v_i(X’_u) + 1n-1∑_u’∈V_2
∖{r, u} m_i(X’_u’) ≥v_i(X_u) + 1n-1∑_u’∈V_2 ∖{r, u} m_i(X_u’) ≥1n, which shows
that $(i,u)\in E^{\prime}$. ∎

By Claim 14 and $(i^{*},u^{*})\in E$, there exists a perfect matching $A$ in
$G_{X}-r$ in which $i^{*}$ matches $u^{*}$. Then, by Claim 15 and
$(i^{*},u^{*})\in E^{\prime}$, we see that $A\subseteq E^{\prime}$, that is,
$A$ is a perfect matching also in $G_{X^{\prime}}-r$. Therefore, $X^{\prime}$
satisfies (P1). Since $|X^{\prime}_{r}|=|X_{r}|+1$ clearly holds by
definition, $X^{\prime}$ satisfies the conditions in Proposition 9. ∎

##  5 Finding a PROPavg Allocation in Polynomial Time

In this section, we show how to find a PROPavg allocation in polynomial time.
As mentioned in Section 4, Algorithm 1 runs in pseudo-polynomial time. This is
because we can not guarantee the polynomial solvability in line 1 of Algorithm
1. We can see that the other parts of Algorithm 1 run in polynomial time as
follows. In line 2, we can check (P2) in polynomial time by applying a maximum
matching algorithm for each $G_{X}-u$. In line 3, it suffices to find a good
$g\in\bigcup_{u\in V_{2}\setminus r}X_{u}$ such that (P1) is kept after moving
$g$. Since (P1) can be checked in polynomial time, this can be done in
polynomial time by considering all $g$ in a brute-force way. Finally, line 5
is executed in polynomial time by Lemma 8. Note that we can speed up lines 2
and 3 by using the DM-decomposition of $G_{X}$ [19, 18], but we do not go into
details, because we only focus on the polynomial solvability.

Let us now consider how to find an initial allocation $X$ to $V_{2}$
satisfying (P1) in polynomial time. Our idea is to use a recursive algorithm.
That is, we use a PROPavg allocation of $M$ to $n-1$ agents as an initial
allocation $X$ to $V_{2}$ satisfying (P1). Indeed, if it holds that
$v_{i}(g)\leq\frac{1}{n}$ for any agent $i\in N$ and any good $g\in M$, then
we can show that a PROPavg allocation of $M$ to $n-1$ agents satisfies (P1) as
follows.

######  Lemma 16.

Suppose that for any agent $i\in N$ and any good $g\in M$, we have
$v_{i}(g)\leq\frac{1}{n}$. Let $(X_{1},\ldots,X_{n-1})$ be a PROPavg
allocation for $N\setminus n$. Then, $X=(X_{1},\ldots,X_{n-1},X_{n})$ is an
allocation to $V_{2}=[n]$ satisfying (P1), where $X_{n}=\emptyset$ and the
specific element $r\in V_{2}$ is equal to $n$.

###### Proof.

Let $G_{X}=(V_{1},V_{2};E)$ be the PROPavg-graph corresponding to $X$. It is
enough to show that $(i,X_{i})\in E$ for any $i\in[n-1]$. Fix any $i\in[n-1]$.
We obtain that

$\displaystyle v_{i}(X_{i})$
$\displaystyle\geq\frac{1}{n-1}-\frac{1}{n-2}\sum_{j\in[n-1]\setminus
i}m_{i}(X_{j})$
$\displaystyle=\frac{1}{n}-\frac{1}{n-1}\sum_{j\in[n-1]\setminus
i}m_{i}(X_{j})$
$\displaystyle+\underbrace{\frac{1}{n-1}\left(\frac{1}{n}-\frac{1}{n-2}\sum_{j\in[n-1]\setminus
i}m_{i}(X_{j})\right)}_{\geq 0}$
$\displaystyle\geq\frac{1}{n}-\frac{1}{n-1}\sum_{j\in[n-1]\setminus
i}m_{i}(X_{j}),$

where the first inequality follows from the assumption that
$(X_{1},\ldots,X_{n-1})$ is a PROPavg allocation and the second inequality
follows from the assumption that $v_{i}(g)\leq\frac{1}{n}$ for any $i\in N$
and $g\in M$. This implies that $(i,X_{i})\in E$ and thus $X$ is an allocation
to $V_{2}=[n]$ satisfying (P1). ∎

Unfortunately, the argument in Lemma 16 does not work without the assumption
that $v_{i}(g)\leq\frac{1}{n}$ for any $i\in N$ and $g\in M$. To elude this
difficulty, our algorithm applies preprocessing. This preprocessing allocates
$g$ to $i$ and remove $i$ and $g$ from our instance as long as there exists an
agent $i$ and a good $g$ such that $v_{i}(g)\geq\frac{1}{n}$. See Algorithm 2
for the entire algorithm.

If this preprocessing removes at least one agent from our instance, then our
algorithm recursively computes a PROPavg allocation for the remaining agents
and goods, and returns the overall allocation together with the removed
agents. In order to verify that the returned allocation is a PROPavg
allocation for $n$ agents, we need a refined condition (see line 7 of
Algorithm 2).

Otherwise, our algorithm recursively computes a PROPavg allocation for $n-1$
agents. Since $v_{i}(g)<\frac{1}{n}$ holds for any agent $i$ and good $g$, we
can use this allocation as an initial allocation to $V_{2}$ satisfying (P1) by
Lemma 16. The rest of our algorithm finds an allocation to $V_{2}$ satisfying
(P2) and returns a PROPavg allocation as in Algorithm 1.

In the remaining part of this section, we show the correctness and the
polynomial solvability of Algorithm 2 . The following lemma shows that if the
preprocessing removes at least one agent from our instance, then the algorithm
returns a legal PROPavg allocation for $N$.

Algorithm 2 Algorithm for finding a PROPavg allocation in polynomial time

1:procedure PROPavg($N$, $M$, $\\{v_{i}\\}_{i\in N}$)

2: if $|N|=1$ then

3: return $X=(M)$

4: else

5: $N_{1}\leftarrow N,N_{2}\leftarrow\emptyset$

6: $M_{1}\leftarrow M,M_{2}\leftarrow\emptyset$

7: while $\exists i\in N_{1}$ and $\exists g\in M_{1}$ s.t.
$v_{i}(g)\geq\frac{v_{i}(M)}{|N|}-\frac{1}{|N|-1}\sum_{j\in
N_{2}}m_{i}(X_{j})$ do

8: $X_{i}\leftarrow\\{g\\}$

9: $N_{1}\leftarrow N_{1}\setminus i,N_{2}\leftarrow N_{2}\cup i$

10: $M_{1}\leftarrow M_{1}\setminus g,M_{2}\leftarrow M_{2}\cup g$

11: Let $N_{1}=\\{1,\ldots,l\\}$ and $N_{2}=\\{l+1,\ldots,|N|\\}$, renumbering
if necessary.

12: if $|N_{2}|\geq 1$ then

13: $(X_{1},\ldots,X_{l})\leftarrow$ PROPavg($N_{1}$, $M_{1}$,
$\\{v_{i}\\}_{i\in N_{1}}$)

14: return $X=(X_{1},\ldots,X_{|N|})$

15: else

16: $(X_{1},\ldots,X_{n-1})\leftarrow$ PROPavg($N\setminus n$, $M$,
$\\{v_{i}\\}_{i\in N\setminus n}$) $\triangleright$ $N_{1}=N,M_{1}=M$

17: Apply Lemma 16 to obtain an allocation $X=(X_{1},\ldots,X_{n})$ satisfying
(P1).

18: while $X$ does not satisfy (P2) do

19: Apply Proposition 9 to $X$ and obtain another allocation $X^{\prime}$ to
$V_{2}$.

20: $X\leftarrow X^{\prime}$.

21: Apply Lemma 8 to obtain a PROPavg allocation $X=(X_{1},\ldots,X_{|N|})$ to
$N$.

22: return $X=(X_{1},\ldots,X_{|N|})$

######  Lemma 17.

In line 14 of Algorithm 2, $X=(X_{1},\ldots,X_{|N|})$ is a PROPavg allocation
to $N$.

###### Proof.

Fix any $i\in N$. We show that $i$ is PROPavg-satisfied by $X$.

Case 1:

$i\in N_{2}$

In this case, agent $i$ receives exactly one good in the while statement. By
the while condition, we have

$\displaystyle v_{i}(X_{i})$
$\displaystyle\geq\frac{1}{n}-\frac{1}{n-1}\sum_{j\in N_{2}}m_{i}(X_{j})$
$\displaystyle\geq\frac{1}{n}-\frac{1}{n-1}\sum_{j\in N\setminus
i}m_{i}(X_{j}).$

Thus, $i$ is PROPavg-satisfied by $X$.

Case 2:

$i\in N_{1}$ and $l=1$

In this case, we have

$\displaystyle v_{i}(X_{i})=v_{i}(M_{1})$ $\displaystyle=v_{i}(M)-\sum_{j\in
N_{2}}m_{i}(X_{j})$ $\displaystyle=\left(\frac{1}{n}-\frac{1}{n-1}\sum_{j\in
N_{2}}m_{i}(X_{j})\right)+\underbrace{\left(\frac{n-1}{n}-\frac{n-2}{n-1}\sum_{j\in
N_{2}}m_{i}(X_{j})\right)}_{\geq 0}$
$\displaystyle\geq\frac{1}{n}-\frac{1}{n-1}\sum_{j\in N_{2}}m_{i}(X_{j})$
$\displaystyle=\frac{1}{n}-\frac{1}{n-1}\sum_{j\in N\setminus i}m_{i}(X_{j}),$

where the inequality follows from
$\frac{n-1}{n}\geq\frac{n-2}{n-1}\geq\frac{n-2}{n-1}\sum_{j\in
N_{2}}m_{i}(X_{j})$.

Case 3:

$i\in N_{1}$ and $l\geq 2$

Since $(X_{1},\ldots,X_{l})$ is a PROPavg allocation of $M_{1}$ to $N_{1}$, we
have

$\displaystyle v_{i}(X_{i})$
$\displaystyle\geq\frac{v_{i}(M_{1})}{l}-\frac{1}{l-1}\sum_{j\in
N_{1}\setminus i}m_{i}(X_{j})$
$\displaystyle=\frac{1}{l}-\frac{1}{l}\sum_{j\in
N_{2}}m_{i}(X_{j})-\frac{1}{l-1}\sum_{j\in N_{1}\setminus i}m_{i}(X_{j}).$ (5)

In line 13 of Algorithm 2, the while condition in line 7 does not hold for
agent $i$. Thus, it holds that

$m_{i}(X_{j})<\frac{1}{n}-\frac{1}{n-1}\sum_{j^{\prime}\in
N_{2}}m_{i}(X_{j^{\prime}})$ (6)

for any $j\in N_{1}\setminus i$. Summing up inequality (6) for each $j\in
N_{1}\setminus i$, we obtain

$\sum_{j\in N_{1}\setminus
i}m_{i}(X_{j})<\frac{l-1}{n}-\frac{l-1}{n-1}\sum_{j\in N_{2}}m_{i}(X_{j}).$
(7)

By multiplying inequality (7) by $\frac{n-l}{l(l-1)}>0$ and rearranging, we
have

$0>-\frac{n-l}{ln}+\frac{n-l}{l(n-1)}\sum_{j\in
N_{2}}m_{i}(X_{j})+\frac{n-l}{l(l-1)}\sum_{j\in N_{1}\setminus
i}m_{i}(X_{j}).$ (8)

Summing up inequalities (Case 3:) and (8), we have

$v_{i}(X_{i})>\frac{1}{n}+\left(-\frac{1}{l}+\frac{n-l}{l(n-1)}\right)\sum_{j\in
N_{2}}m_{i}(X_{j})+\left(-\frac{1}{l-1}+\frac{n-l}{l(l-1)}\right)\sum_{j\in
N_{1}\setminus i}m_{i}(X_{j}).$ (9)

Since $2\leq l<n$, by direct calculation, we have

$-\frac{1}{l}+\frac{n-l}{l(n-1)}+\frac{1}{n-1}=\frac{1}{l(n-1)}\geq 0$

and

$\displaystyle-\frac{1}{l-1}+\frac{n-l}{l(l-1)}+\frac{1}{n-1}$
$\displaystyle=\frac{1}{l(l-1)(n-1)}\left(-l(n-1)+(n-l)(n-1)+l(l-1)\right)$
$\displaystyle=\frac{(n-l)(n-l-1)}{l(l-1)(n-1)}$ $\displaystyle\geq 0.$

Applying these inequalities to inequality (9), we finally obtain

$\displaystyle v_{i}(X_{i})$
$\displaystyle>\frac{1}{n}-\frac{1}{n-1}\left(\sum_{j\in
N_{2}}m_{i}(X_{j})+\sum_{j\in N_{1}\setminus i}m_{i}(X_{j})\right).$
$\displaystyle=\frac{1}{n}-\frac{1}{n-1}\sum_{j\in N\setminus i}m_{i}(X_{j}),$

which implies that $i$ is PROPavg-satisfied by $X$.

Therefore, $X$ is a PROPavg allocation to $N$ in line 16 of Algorithm 2. ∎

We finally give the proof of Theorem 2 by showing that Algorithm 2 is a
polynomial time algorithm to find a PROPavg allocation.

###### Proof of Theorem 2.

We first show the correctness of Algorithm 2. If $|N|=1$, our algorithm
obviously returns a PROPavg allocation in line 3. Assume that $|N|\geq 2$. If
$|N_{2}|\geq 1$, it returns a PROPavg allocation in line 14 by Lemma 17.
Otherwise, since the while condition in line 7 does not hold for any agent in
$N_{1}$, $v_{i}(g)<\frac{1}{n}$ holds for any agent $i\in N_{1}$ and good
$g\in M_{1}$ in line 16. Thus, $X=(X_{1},\ldots,X_{n})$ satisfies (P1) by
Lemma 16, where $X_{n}$ is an empty set. The rest of the algorithm finds an
allocation to $V_{2}$ satisfying (P2) and returns a PROPavg allocation as in
Algorithm 1. Therefore, Algorithm 2 returns a PROPavg allocation in all cases.

We finally show that Algorithm 2 completes in time polynomial in the number of
agents and items. Let $T(n,m)$ be the worst case time complexity of Algorithm
2 when $|N|=n$ and $|M|=m$. Clearly, $T(1,m)=O(m)$. We can check the while
condition in line 7 and execute the body of the while loop in polynomial time
of $n$ and $m$. In addition, as mentioned at the beginning of Section 5, Lines
17 to 22 can be executed in polynomial time of $n$ and $m$. Thus, $T(n,m)$ can
be expressed as T(n,m)=O(poly(n,m))+max{max_1≤n’ ≤n-11≤m’ ≤m-1T(n’,m’), T(n-1,
m)}. Therefore, $T(n,m)$ is polynomially bounded in $n$ and $m$. ∎

##  6 Conclusion

In this paper, we have introduced PROPavg, which is a stronger notion than
PROPm, and shown that a PROPavg allocation always exists and can be computed
in polynomial time when each agent has a non-negative additive valuation. In
order to devise our algorithm, we have developed a new technique that
generalizes the cut-and-choose protocol. This technique is interesting by
itself and seems to have a potential for further applications. In fact, we can
define a bipartite graph like the PROPavg-graph for another fairness notion,
and our argument works if we obtain an allocation satisfying a (P2)-like
condition. We expect that this technique will be used in other contexts as
well.

There are still several future work. Whether Avg-EFX, which is a stronger
notion than PROPavg exists for four or more agents is an interesting open
problem. Another direction is to consider weighted approximate
proportionality. In the weighted case, each agent $i$ has a non-negative
weight $\alpha_{i}$, where $\alpha_{1}+\cdots+\alpha_{n}=1$. The goal is to
find an allocation $X$ such that
$v_{i}(X_{i})\geq\frac{\alpha_{i}}{n}-d_{i}(X)$ for each agent $i\in N$.
Whether weighted PROPavg allocation exists is also an interesting problem.

### Acknowledgments

This work was partially supported by the joint project of Kyoto University and
Toyota Motor Corporation, titled “Advanced Mathematical Science for Mobility
Society”, and by JSPS, KAKENHI grant number JP19H05485, Japan.

## References

  * [1] Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, and Alexandros A Voudouris.  Maximum Nash welfare and other stories about EFX.  Theoretical Computer Science, 863:69–85, 2021.
  * [2] Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, and Alexandros A. Voudouris.  Fair division of indivisible goods: A survey.  In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), pages 5385–5393, 2022.
  * [3] Haris Aziz, Hervé Moulin, and Fedor Sandomirskiy.  A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation.  Operations Research Letters, 48(5):573–578, 2020.
  * [4] Artem Baklanov, Pranav Garimidi, Vasilis Gkatzelis, and Daniel Schoepflin.  Achieving proportionality up to the maximin item with indivisible goods.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5143–5150, 2021.
  * [5] Artem Baklanov, Pranav Garimidi, Vasilis Gkatzelis, and Daniel Schoepflin.  PROPm allocations of indivisible goods to multiple agents.  In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pages 24–30, 2021.
  * [6] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish.  Greedy algorithms for maximizing Nash social welfare.  In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pages 7–13, 2018.
  * [7] Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat.  Almost full EFX exists for four agents.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 4826–4833, 2022.
  * [8] Steven J Brams, Steven John Brams, and Alan D Taylor.  Fair Division: From cake-cutting to dispute resolution.  Cambridge University Press, 1996.
  * [9] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D Procaccia.  Handbook of computational social choice.  Cambridge University Press, 2016.
  * [10] Eric Budish.  The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.  Journal of Political Economy, 119(6):1061–1103, 2011.
  * [11] Ioannis Caragiannis, Nick Gravin, and Xin Huang.  Envy-freeness up to any item with high Nash welfare: The virtue of donating items.  In Proceedings of the 20th ACM Conference on Economics and Computation (EC), pages 527–545, 2019.
  * [12] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang.  The unreasonable fairness of maximum Nash welfare.  ACM Transactions on Economics and Computation, 7(3):1–32, 2019\.
  * [13] Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn.  EFX exists for three agents.  In Proceedings of the 21st ACM Conference on Economics and Computation (EC), pages 1–19, 2020.
  * [14] Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, and Pranabendu Misra.  Improving EFX guarantees through rainbow cycle number.  In Proceedings of the 22nd ACM Conference on Economics and Computation (EC), pages 310–311, 2021.
  * [15] Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa.  A little charity guarantees almost envy-freeness.  SIAM Journal on Computing, 50(4):1336–1358, 2021.
  * [16] Vincent Conitzer, Rupert Freeman, and Nisarg Shah.  Fair public decision making.  In Proceedings of the 18th ACM Conference on Economics and Computation (EC), pages 629–646, 2017.
  * [17] Andreas Darmann and Joachim Schauer.  Maximizing Nash product social welfare in allocating indivisible goods.  European Journal of Operational Research, 247(2):548–559, 2015\.
  * [18] Andrew L Dulmage.  A structure theory of bipartite graphs of finite exterior dimension.  The Transactions of the Royal Society of Canada, Section III, 53:1–13, 1959.
  * [19] Andrew L Dulmage and Nathan S Mendelsohn.  Coverings of bipartite graphs.  Canadian Journal of Mathematics, 10:517–534, 1958.
  * [20] P Hall.  On representatives of subsets.  Journal of the London Mathematical Society, 1(1):26–30, 1935.
  * [21] Yusuke Kobayashi and Ryoga Mahara.  Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average.  In 33rd International Symposium on Algorithms and Computation (ISAAC), pages 55:1–55:13, 2022.
  * [22] Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi.  On approximately fair allocations of indivisible goods.  In Proceedings of the 5th ACM Conference on Electronic Commerce (EC), pages 125–131, 2004.
  * [23] Ryoga Mahara.  Existence of EFX for two additive valuations.  arXiv preprint arXiv:2008.08798, 2020.
  * [24] Ryoga Mahara.  Extension of additive valuations to general valuations on the existence of EFX.  In Proceedings of the 29th Annual European Symposium on Algorithms (ESA), pages 66:1–15, 2021.
  * [25] Hervé Moulin.  Fair division and collective welfare.  MIT press, 2004.
  * [26] Hervé Moulin.  Fair division in the internet age.  Annual Review of Economics, 11:407–441, 2019.
  * [27] Benjamin Plaut and Tim Roughgarden.  Almost envy-freeness with general valuations.  SIAM Journal on Discrete Mathematics, 34(2):1039–1068, 2020.
  * [28] Jack Robertson and William Webb.  Cake-cutting algorithms: Be fair if you can, 1998.
  * [29] Hugo Steinhaus.  The problem of fair division.  Econometrica, 16(1):101–104, 1948.