# Weighted Proportional Allocations of Indivisible Goods and Chores: Insights
via Matchings

Vishwa Prakash H.V  Chennai Mathematical InstituteChennaiIndia
<EMAIL_ADDRESS>and  Prajakta Nimbhorkar  Chennai Mathematical
InstituteChennaiIndia<EMAIL_ADDRESS>
###### Abstract.

We study the fair allocation of indivisible goods and chores for agents with
ordinal preferences and arbitrary entitlements. In both the cases of goods and
chores, we show that there always exist allocations that are weighted
necessarily proportional up to one item (WSD-PROP1), that is, allocations that
are WPROP1 under all additive valuations consistent with agents’ ordinal
preferences. We give a polynomial-time algorithm to find such allocations by
reducing it to a problem of finding perfect matchings in a bipartite graph. We
give a complete characterization of these allocations as extreme points of a
perfect matching polytope. Using this polytope, we can optimize any linear
objective function over all WSD-PROP1 allocations, for example, to find a min-
cost WSD-PROP1 allocation of goods or most efficient WSD-PROP1 allocation of
chores. Additionally, we show the existence and computation of sequencible
(SEQ) WSD-PROP1 allocations by using rank-maximal perfect matching algorithms
and show the incompatibility of Pareto optimality under all valuations and
WSD-PROP1.

We also consider the Best-of-Both-Worlds (BoBW) fairness notion. By using our
characterization, we give a polynomial-time algorithm to compute Ex-ante envy-
free (WSD-EF) and Ex-post WSD-PROP1 allocations for both goods and chores.

Fair Division, Matchings, Proportionality

††copyright: none††ccs: Theory of computation Algorithmic game theory††ccs:
Mathematics of computing Matchings and factors††ccs: Mathematics of computing
Combinatorial algorithms††ccs: Theory of computation Approximation algorithms
analysis

##  1\. Introduction

Discrete fair allocation is a fundamental problem at the intersection of
economics and computer science with applications in various multi-agent
settings. Here, we are required to allocate a set of indivisible items to
agents based on their preferences, such that each item is allocated to exactly
one agent. This setting is commonly referred to as the _assignment problem_
(Gardenfors, 1973; Manlove, 2013; Foley, 1966; Wilson, 1977; Aziz et al.,
2015). In this setting, there is a set $A$ of $n$ agents and a set $B$ of $m$
indivisible items with each agent $a_{i}\in A$ expressing an ordinal
preference ordering over the items in $B$, given by a permutation $\pi_{i}(B)$
of the items in $B$. In addition to their ordinal preferences, agents may also
have private cardinal valuations that reflect the utility or disutility of
each item, ensuring compatibility with their ordinal preferences. The goal is
to allocate the items to agents in a _fair_ manner. In this paper, we focus on
additive valuations, where the utility (or disutility) of a set of items is
the sum of the utilitites (or disutilities) of individual items.

The set $B$ can represent _goods_ , covering scenarios such as inheritance
division, house allocation, allocation of public goods, among others.
Alternatively, $B$ could be a set of _chores_ , modeling situations like task
allocation among employees or household chore distribution between couples and
so on.

Among various notions of fairness studied in the literature, two prominent
ones are _Envy-freeness_ (EF) and _Proportionality_ (PROP). An allocation is
said to be envy-free if no agent would prefer to have the bundle held by any
of the others. On the other hand, proportionality requires that each agent
receives a set of items whose value is at least (at most, for chores) her
proportional share of the total value of all the items. Unfortunately, PROP or
EF allocations do not always exist and are NP-hard to compute (Lipton et al.,
2004; Bouveret and Lemaître, 2014; Aziz et al., 2015). Hence relaxations of
these notions have been proposed in literature. PROP is relaxed as
Proportionality _up to one item_ (PROP1) (Conitzer et al., 2017; Barman and
Krishnamurthy, 2019; Brânzei and Sandomirskiy, 2019; Aziz et al., 2020) and EF
is relaxed as Envy-free up to one item (EF1)(Budish, 2011; Lipton et al.,
2004).

In practical scenarios, agents can have varying _entitlements_ in situations
such as inheritance division, division of shares among investors and so on. To
capture such cases, a more generalized version of these notions, namely the
weighted envy-freeness WEF (Chakraborty et al., 2021; Aziz et al., 2020) and
weighted proportionality WPROP(Hoefer et al., 2023; Aziz et al., 2023) are
considered.

Given only the ordinal preferences, these notions of fairness are further
strengthened by considering the _stochastic dominance_ (SD) relation. An agent
prefers one allocation over another with respect to the SD relation if she
gets at least as much utility from the former allocation as the latter for all
cardinal utilities consistent with the ordinal preferences. An allocation is
said to be weighted _necessarily_ proportional (also known as weighted strong
SD proportionality) (WSD-PROP) if it remains WPROP under all cardinal
utilities consistent with the ordinal preferences. Similarly, the notion of
envy-freeness (EF) can be extended to weighted necessarily envy-freeness (WSD-
EF). Clearly, just like PROP and EF, WSD-PROP and WSD-EF allocations may not
exist. In fact, as shown in (Pruhs and Woeginger, 2012; Aziz et al., 2015), in
an SD-PROP allocation, each agent must receive their most favorite item -
which is not realizable when two or more agents have the same most favorite
item. For agents with varying entitlements and under ordinal preferences,
these notions can be relaxed to WSD-EF1 and WSD-PROP1 (see e.g. (Wu et al.,
2023; Chakraborty et al., 2021; Hoefer et al., 2023)).

Given the non-existence of WPROP allocations, a well studied notion of
fairness is that of WPROPx. Although WPROPx allocations exists under cardinal
valuations (Li et al., 2022), an analogous notion for the ordinal instances -
namely, WSD-PROPx allocations - need not exist (See Example B.1). This further
motivates the study of WSD-PROP1 allocations.

Another approach to tackle the non-existence of EF and PROP allocations is via
randomization. A promising notion of fairness which has gained popularity over
the recent years, is the notion of _”Best of Both Worlds Guarantees”_ (BoBW)
(Freeman et al., 2020; Aziz, 2020; Babaioff et al., 2022; Hoefer et al., 2023;
Aziz et al., 2023). The aim is to compute a randomized fair allocation which
also guarantees an approximate fairness notion in the deterministic setting.
Suppose $\mathcal{P}$ and $\mathcal{Q}$ are two notions of fairness. Given a
set of $k$ allocations $A=\langle A_{1},A_{2},\cdots,A_{k}\rangle$ and a
probability distribution $p=\langle p_{1},p_{2},\cdots,p_{k}\rangle$ over $A$,
the pair $\langle A,p\rangle$ is said to be _ex-post_ $\mathcal{Q}$ fair if
each allocation $A_{1},A_{2},\cdots,A_{k}$ are $\mathcal{Q}$ fair and is
called _ex-ante_ $\mathcal{P}$ fair if $\mathcal{P}$ fairness is guaranteed in
expectation.

In (Freeman et al., 2020; Aziz, 2020), Aziz and Freeman et al. proposed
polynomial time algorithms - the PS-Lottery algorithm (also called as the
Eating algorithms) to compute ex-ante SD-EF and ex-post SD-EF1 allocations of
goods. In their approach, the agents are asked to hypothetically _eat_ the
goods to produce a fractional allocation which is later decomposed into
integral allocations. This approach was later modified in (Hoefer et al.,
2023) where the agents eat the goods at varying speeds to compute allocations
that are ex-ante WSD-EF and ex-post WSD-PROP1 along with _weighted transfer
envy-free up to one good_ WEF(1,1).

In practice, multiple allocations satisfying WSD-PROP1 might exist, and some
could be better than others. For instance, different allocations of goods
might incur different shipping/transportation costs or agents might have
varying efficiency or expertise for each chore, independent of their own
disutility or preference. In such cases, it becomes essential to optimize over
the set of all WSD-PROP1 allocations. In this work, we particularly address
this problem, providing a unified way to deal with goods and chores.

###  1.1. Our Contributions

In this paper, we investigate fair allocation problems for agents with ordinal
preferences and unequal entitlements. We provide the following key
contributions:

  * •

In Theorem 3.6 and Theorem A.6, we show that the problem of existence and
computation of WSD-PROP1 allocations reduces to that of the existence and
computation of a perfect matching in a bipartite graph. We give such a
reduction for both goods and chores. This gives a straightforward, matching
based, polynomial-time algorithm that seamlessly adapts to computation of a
WSD-PROP1 allocation of both goods and chores.

  * •

Moreover, we show that every perfect matching in the graph constructed above
corresponds to a WSD-PROP1 allocation, and vice versa. Thus, we give a
complete characterization of WSD-PROP1 allocations for both goods and chores
as extreme points of a perfect matching polytope. This enables optimization of
any linear objective function over the set of all WSD-PROP1 allocations. (See
Section 4)

  * •

We study the economic efficiencies that can be guaranteed along with WSD-
PROP1. We provide a counter-example to show that Pareto optimality111Here,
given only ordinal rankings, we call an allocation cardinally PO if it is PO
under all cardinal valuations compatible with the ordinal rankings. (PO) is
not compatible with WSD-PROP1.

  * •

On the positive side, In Theorem 6.3 and Theorem A.9, we show that every
allocation that corresponds to a rank-maximal perfect matching in our perfect
matchings instance is sequencible. En-route to this result, we show that rank-
maximal matchings and rank-maximal perfect matchings in any bipartite graph
are sequencible. See Lemma 6.2. This may be of independent interest.

  * •

We also consider the best of both world fairness notion, in the context of our
characterization. Our characterization leads to a simple polynomial-time
algorithm for computing ex-ante WSD-EF ex-post WSD-PROP1 allocations for both
goods and chores. (See Theorem 5.3). To the best of our knowledge, prior to
this work, this result was not known for chores.

In the main part, we state the results for chores, and the results for goods
are given in Appendix A. Extensions:  Our characterization of WSD-PROP1
allocations in terms of matchings paves a way to use tools from fairness in
matchings to further generalization of the allocation problem. For instance,
items (and also agents) can belong to various categories depending on their
attributes, and there can be upper and lower quotas on each category of items
that can be allotted and also on each category of agents as to the number of
items they get. Existing results from the literature on fairness in matchings
(e.g. (Gonczarowski et al., 2019; Sönmez and Yenmez, 2022; Panda et al., 2022;
Sankar et al., 2021)) can then be used to determine the existence of WSD-PROP1
allocations satisfying the category quotas, and outputting one if it exists.

###  1.2. Related Work

Over the past two decades, there has been a growing interest in the study of
computation of discrete fair division (Bezáková and Dani, 2005; Bouveret et
al., 2010; Lipton et al., 2004; Bouveret and Lemaître, 2014; Aziz et al.,
2015, 2022; Nguyen et al., 2013; Amanatidis et al., 2022). In (Budish, 2011;
Lipton et al., 2004), Budish et al and Lipton et al show the existence of EF1
allocations for goods. In (Conitzer et al., 2017; Barman and Krishnamurthy,
2019), Conitzer et al and Baman et al, extensively studied PROP1 allocations
for goods. While significant advancements have been made in the allocation of
goods, progress in the case of chores has been notably slower, and our
understanding of chore allocation remains relatively limited in comparison to
goods allocation. In 2019, Brânzei and Sandomirskiy in (Brânzei and
Sandomirskiy, 2019) extended the notion of PROP1 to the case of chores and
gave a polynomial time222The algorithm runs in polynomial time when either the
number of agents or the number of chores is fixed algorithm to compute them.
In 2020, Bhaskar et al showed the existance and polynomial time computation of
EF1 allocation of chores (Bhaskar et al., 2020).

For agents with varying entitlements, In 2021, Chakraborty et al (Chakraborty
et al., 2021) showed the existence and computation of WEF1+PO allocation in
pseudo-polynomial time. They showed that in the context of weighted
allocations, WEF1 does not imply WPROP1 for goods, in contrast to the
unweighted case. Li et al, in (Li et al., 2022) showed the existence and
computation of WPROPx (which implies WPROP1) allocation of chores. Later in
2023, Ex-post WPROP1 allocations along with Ex-ante WEF allocations for goods
were studied in (Hoefer et al., 2023; Aziz et al., 2023). In (Aziz et al.,
2023), Aziz et al. proposed the Weighted Max Nash lottery Algorithm which
computes an Ex-ante PO and Ex-post WPROP1 allocation, for agents with additive
cardinal valuations.

In the weighted setting with agents expressing ordinal preferences for goods,
Pruhs et al. in (Pruhs and Woeginger, 2012) reduced the problem of WSD-PROP
allocation of goods to that of finding perfect matchings in a bipartite graph.
This was later generalized to preference lists with ties by Aziz et al. in
(Aziz et al., 2015). While WSD-PROP allocations may not always exist, their
method provides a polynomial-time algorithm to compute one when it exists. Our
reductions are inspired from their work. In 2023, Wu et al. proposed the
_Reversed Weighted Picking Sequence_ Algorithm (Wu et al., 2023) which always
computes a WSD-EF1+SEQ (thus WSD-PROP1+SEQ) allocation of chores in polynomial
time.

##  2\. Preliminaries

Let $A=\\{a_{1},a_{2},\ldots,a_{n}\\}$ denote the set of $n$ agents and let
$B=\\{b_{1},b_{2},\ldots,b_{m}\\}$ be set of $m$ indivisible items. Each agent
$a_{i}$ expressing ordinal preferences over the items given by a permutation
$\pi_{i}$ of the items in $B$. The item set $B$ can either be a set of goods
or a set of chores. Each agent $a_{i}\in A$ is endowed with an _entitlement_
$\alpha_{i}\in[0,1]$ such that $\sum_{a_{i}\in A}\alpha_{i}=1$.

Given an agent $a_{i}\in A$, we denote the ordinal preference of $a_{i}$ as a
rank function $\pi_{i}:[m]\to B$. The $j^{\text{th}}$ rank item is given by
$\pi_{i}(j)$ and the rank of an item $b$ is given by $\pi_{i}^{-1}(b)$. In the
case of goods, $\pi_{i}(j)$ represents the $j^{\text{th}}$-most favorite good
and in the case of chores, $\pi_{i}(j)$ is the $j^{\text{th}}$-least favorite
chore.

An instance of the allocation problem under ordinal valuations is represented
by a tuple $\mathcal{I}=\langle A,B,\Pi,\mathcal{F}\rangle$, where $A$ and $B$
are the sets of agents and goods, respectively.
$\Pi=\\{\pi_{1},\pi_{2},\ldots,\pi_{n}\\}$ denotes the set of rank functions,
and $\mathcal{F}=\\{\alpha_{1},\alpha_{2},\ldots,\alpha_{n}\\}$ represents the
entitlements of each agent.

#### Fractional and Randomized Allocations:

We adopt the definitions of fractional and randomized allocations as outlined
in (Freeman et al., 2020; Aziz, 2020; Babaioff et al., 2022; Aziz et al.,
2023). A _fractional_ allocation of the items in $B$ to the agents in $A$ is
given by a non-negative $n\times m$ matrix $X=[x_{i,j}]\in[0,1]^{n\times m}$
such that an entry $x_{i,j}$ denotes the fraction of the item $b_{j}$
allocated to the agent $a_{i}$; for each item $b_{j}\in B$, $\sum_{a_{i}\in
A}x_{i,j}=1$. We denote $X_{i}=\langle x_{i,1},x_{i,2},\ldots,x_{i,m}\rangle$
as the _fractional bundle_ of items that is assigned to agent $a_{i}$. A
fractional allocation is integral, if $x_{i,j}\in\\{0,1\\}$ for all $a_{i}\in
A$ and $b_{j}\in B$. For an integral allocation $X$, we denote with bundle
$X_{i}$ the set of items that is assigned to agent $a_{i}$ and the allocation
$X$ can be characterized by the bundles of the agents, i.e. $X=\langle
X_{1},X_{2},\ldots,X_{n}\rangle$.

A randomized allocation is a lottery over integral allocations. In particular,
a randomized allocation $R$ is determined by $k$ pairs
$\\{(p_{1},Y^{1}),(p_{2},Y^{2}),\ldots,(p_{k},Y^{k})\\}$, where each of the
integral allocations $Y^{j}$ for $j\in[k]$, is implemented with probability
$p_{j}>0$ and $\sum_{j\in[k]}p_{j}=1$. We say that such an integral allocation
is in the support of the randomized allocation. Moreover, we say that a
fractional allocation $X$ implements a randomized allocation $Y$, if the
marginal probability of agent $a_{i}$ receiving item $b_{j}$ is $x_{i,j}$.

#### Cardinal Valuations:

Each agent $a_{i}\in A$ can have a private cardinal valuation function
$v_{i}:2^{B}\to\mathbb{R}_{\geq 0}$. When $B$ represents a set of goods,
$v_{i}$ is called as a utility function. When $B$ represents a set of chores,
$v_{i}$ is called as a disutility function. The heaviest (least favorite)
chore is assigned the highest disutility value. We consider agent’s valuation
function to be additive, that is $\forall S\subseteq B,v_{i}(S)=\sum_{b\in
S}v_{i}(b)$.

A valuation function $v_{i}$ is said to be $\pi_{i}$-respecting, if $v_{i}$ is
consistent with the ordinal ranking $\pi_{i}$. That is, $\forall
b,b^{\prime}\in B,\ \pi^{-1}_{i}(b)<\pi^{-1}_{i}(b^{\prime})\implies
v_{i}(b)\geq v_{i}(b^{\prime})$. We denote the set of all $\pi_{i}$-respecting
valuations as $\mathscr{U}(\pi_{i})$.

#### The Interval Representation of Items:

Consider an agent $a_{i}\in A$ with an entitlement $\alpha_{i}$. We arrange
the items along a number line from $0$ to $m$, such that the $j^{\text{th}}$
rank item $\pi_{i}(j)$ occupies the interval $[j-1,j]$ for $1\leq j\leq m$. We
refer to the interval $[j-1,j]$ as the item $\pi_{i}(j)$ itself. Furthermore,
given an interval $I=[p,q]\subseteq[0,m]$, we refer to $I$ as a fractional
bundle itself. If $\delta$ fraction of an interval $[j-1,j]$ overlaps with the
interval $[p,q]$, that is $|[j-1,j]\cap[p,q]|=\delta$ , then $\delta$ fraction
of the item $b=\pi_{i}(j)$ belongs to the fractional bundle $I$. For a
cardinal valuation function $v_{i}$ of agent $a_{i}$, the value of the bundle
$I=[p,q]$ is calculated as
$v_{i}(I)=\sum_{j\in[m]}|[j-1,j]\cap[p,q]|.v_{i}(\pi_{i}(j))$.

Now, let the $[0,m]$ interval be sub-divided into $k_{i}=\lceil
m\alpha_{i}\rceil$ many intervals of lengths $\frac{1}{\alpha_{i}}$, except
possibly the last interval, which can be shorter. The the $\ell^{\text{th}}$
interval is given by
$I^{i}_{\ell}=\left[\frac{\ell-1}{\alpha_{i}},\frac{\ell}{\alpha_{i}}\right]$
for $1\leq\ell\leq\lfloor m\alpha_{i}\rfloor$, and, if $m\alpha_{i}$ is not
integral, then the last interval is $\left[\frac{\lfloor
m\alpha_{i}\rfloor}{\alpha_{i}},m\right]$.

###### Definition 2.1.

For an agent $a_{i}\in A$, we define the set of intervals
$I^{i}=\\{I^{i}_{1},I^{i}_{2},\ldots,I^{i}_{k_{i}}\\}$ as the _interval set_
of $a_{i}$.

Note that if $\alpha_{i}<1$, length of each interval $\frac{1}{\alpha_{i}}>1$.
Thus each interval $I^{i}_{\ell}$, except possibly the last one, contains a
non-zero portion of at least two consecutive items.

#### Stochastic Dominance(SD):

A standard way of comparing fractional/randomized allocations is through
first-order stochastic dominance. This notion has been extensively studied
previously in (Bogomolnaia and Moulin, 2001; Aziz et al., 2015). An agent
$a_{i}$ prefers one allocation over another with respect to the SD relation if
she gets at least as much value (or at most - in the case of chores) from the
former allocation as the latter under all $\pi_{i}$-respecting cardinal
valuations.

Suppose $X_{i}$ and $Y_{i}$ denote the fractional bundles of goods that an
agent $a_{i}$ receives in the allocations $X=[x_{ij}]$ and $Y=[y_{ij}]$
respectively. We say that an agent $a_{i}$ SD prefers $X_{i}$ to $Y_{i}$,
denoted by $X\succsim^{\text{SD}}_{i}Y$ if the following holds:

$\forall j^{*}\in[m],\sum_{j:\pi_{i}(j)\geq\pi(j^{*})}x_{i,j}\
\geq\sum_{j:\pi_{i}(j)\geq\pi(j^{*})}y_{i,j}$

When $X_{i}$ and $Y_{i}$ denote bundles of chores, we say
$X\succsim^{\text{SD}}_{i}Y$ if the following holds:

$\forall j^{*}\in[m],\sum_{j:\pi_{i}(j)\geq\pi(j^{*})}x_{i,j}\
\leq\sum_{j:\pi_{i}(j)\geq\pi(j^{*})}y_{i,j}$

###  2.1. Fairness and Efficiency Notions

We begin with _ex-ante - ex-post_ notions as defined in (Bogomolnaia and
Moulin, 2001; Freeman et al., 2020; Aziz, 2020; Babaioff et al., 2022; Hoefer
et al., 2023; Aziz et al., 2023). For any property $\langle{P}\rangle$ defined
for an allocation, we say that a randomized allocation $R$ satisfies
$\langle{P}\rangle$ _ex-ante_ if the allocation $X$ that implements $R$
satisfies $\langle{P}\rangle$. For any property $\langle{Q}\rangle$ defined
for an integral allocation, we say that a randomized allocation $R$ satisfies
$\langle{Q}\rangle$ _ex-post_ if every integral allocation in its support
satisfies $\langle{Q}\rangle$.

We now define various notions of weighted fairness under ordinal valuations.
We start with the classic notion of _envy-freeness._ Consider an instance of
the allocation problem under ordinal valuations $\mathcal{I}=\langle
A,B,\Pi,\mathcal{F}\rangle$.

###### Definition 2.2 (WSD-EF).

Let $B$ be a set of chores. An allocation $X=\langle
X_{1},X_{2},\ldots,X_{n}\rangle$ of $B$ is said to be _weighted_ SD _envy free
( WSD-EF)_, if for every pair of agents $a_{i},a_{k}\in A$, we have

$\frac{v_{i}(X_{i})}{\alpha_{i}}\leq\frac{v_{i}(X_{k})}{\alpha_{k}}\quad\forall{v_{i}}\in\mathscr{U}(\pi_{i}),\forall{v_{k}}\in\mathscr{U}(\pi_{k})$

And if $B$ is a set of goods, then $X$ is _WSD-EF_ (Bogomolnaia and Moulin,
2001), if for every pair of agents $a_{i},a_{k}\in A$, we have

$\frac{v_{i}(X_{i})}{\alpha_{i}}\geq\frac{v_{i}(X_{k})}{\alpha_{k}}\quad\forall{v_{i}}\in\mathscr{U}(\pi_{i}),\forall{v_{k}}\in\mathscr{U}(\pi_{k})$

We consider the following notions of relaxed proportionality defined for
integral allocations under cardinal valuations.

###### Definition 2.3 (WPROP1 (Aziz et al., 2020)).

Let $B$ be a set of chores. In an integral allocation $X=\langle
X_{1},X_{2},\ldots,X_{n}\rangle$, a bundle $X_{i}$ is said to be _weighted_
_proportional up to one item ( WPROP1)_ for an agent $a_{i}$ with a valuation
function $v_{i}$, if we have:

$\exists b\in X_{i},\quad v_{i}(X_{i}\setminus\\{b\\})\leq\alpha_{i}.v_{i}(B)$

And if $B$ is a set of goods, then a bundle $X_{i}$ is said to be _WPROP1_ for
an agent $a_{i}$ if we have:

$\exists b\in B,\quad v_{i}(X_{i}\cup\\{b\\})\geq\alpha_{i}.v_{i}(B)$

The allocation $X$ is said to be _WPROP1_ if for all $i\in[n]$, bundle $X_{i}$
is _WPROP1_ for agent $a_{i}$.

Although the notion of WPROP1 is conventionally defined for integral
allocations, for the sake of analysis, we extend this notion to fractional
allocations as follows:

###### Definition 2.4 (fractional WPROP1).

Let $B$ be a set of chores. A fractional bundle $X_{i}=\langle
x_{i,1},x_{i,2},\ldots,x_{i,m}\rangle$ is _WPROP1_ for an agent $a_{i}$ with a
valuation function $v_{i}$, if $\exists
b=\langle\beta_{1},\beta_{2},\ldots,\beta_{m}\rangle$, where
$\lVert{b}\rVert_{1}=1$ and $0\leq\beta_{j}\leq x_{i,j}$ $\forall j\in[m]$, we
have $v_{i}(X_{i}-b)\leq\alpha_{i}.v_{i}(B)$.

In the case of goods, a fractional bundle $X_{i}$ is _WPROP1_ for an agent
$a_{i}$, if $\exists b=\langle\beta_{1},\beta_{2},\ldots,\beta_{m}\rangle$,
where $\lVert{b}\rVert_{1}=1$ and $\beta_{j}\geq 0$ and $x_{i,j}+\beta_{j}\leq
1$ $\forall j\in[m]$, we have $v_{i}(X_{i}+b)\geq\alpha_{i}.v_{i}(B)$. The
allocation $X$ is _WPROP1_ if bundle $X_{i}$ is _WPROP1_ for every agent
$a_{i}\in A$.

We can extend these definitions to the case of ordinal valuations as follows:

###### Definition 2.5 (WSD-PROP1).

An allocation $X$ is said to be _WSD-PROP1_ , if $X$ is _ WPROP1 _for every
agent $a_{i}\in A$ under all valuations $v_{i}\in\mathscr{U}(\pi_{i})$

It is straightforward that for an agent $a_{i}$, if a bundle $X$ is WSD-PROP1,
then every bundle $Y$ s.t. $Y\succsim_{i}^{\text{SD}}X$ is also WSD-PROP1.

Along with the notions of fairness, we study the following economic
efficiencies considered in literature.

###### Definition 2.6 (Pareto Optimailty (PO)).

For agents with cardinal valuations, an allocation $X$ is said to be _Pareto
Optimal ( PO)_ if there is no allocation $Y$ that Pareto dominates it. In the
case of chore, this condition is expressed as $v_{i}(X_{i})\leq v_{i}(Y_{i})$
for all $i\in[n]$ and $\exists j\in[n]$ such that $v_{j}(X_{j})<v_{j}(Y_{j})$,
while for goods, it is expressed as $v_{i}(X_{i})\geq v_{i}(Y_{i})$ for all
$i\in[n]$ and $\exists j\in[n]$ such that $v_{j}(X_{j})>v_{j}(Y_{j})$.

In the absence of Pareto Optimal allocations, a weaker notion of efficiency
known as sequencibility (SEQ) is often considered. A _picking sequence_ of $n$
agents for $m$ items is an $m$-length sequence $\sigma=\langle
a^{\prime}_{1},a^{\prime}_{2},\ldots,a^{\prime}_{m}\rangle$ where
$a^{\prime}_{i}\in A$ for $i\in[m]$. An allocation $X$ is the result of the
picking sequence $\sigma$ if it is the output of the following procedure:
Initially every bundle is empty; then, at time step $t$, agent
$a^{\prime}_{t}$ inserts in her bundle the most preferred item among the
available ones. Once an item is selected, it is removed from the set of the
available items.

###### Definition 2.7 (Sequencibility (SEQ)).

An allocation $X$ is said to be _sequencible ( SEQ)_ if $X$ is the result of
some picking sequence $\sigma$.

It is known that PO implies SEQ, and when number of agents $n=2$, then PO is
same as SEQ (Brams and Kaplan, 2002).

###  2.2. Matchings

Given a bipartite graph $G=(A\cup B,E)$, an $A$ perfect matching $M$ is a
matching in $G$ that saturates all the vertices in $A$. When $|A|=|B|$,
$A$-perfect matching is same as perfect matching. Given a matching $M$ and a
matched vertex $a\in A$, we denote by $M(a)$ the matched partner of $a$.

#### Rank-Maximal Matchings _(Irving,2003; Irving et al., 2006)_:

Consider a bipartite graph $G=(A\cup B,E)$, s.t $|A|=n,|B|=m$, where each
vertex $a$ in $A$ ranks its neighbours $N(a)$ from $1$ to $|N(a)|$. For each
edge $(a,b)\in E$, let $rank(a,b)\in[m]$ denote the rank of $b$ in $a$’s
ranking. The graph $G$ along with the ranking is denoted as $G=(A\cup
B,E_{1},E_{2},\ldots,E_{m})$ where $E_{i}=\\{(a,b)\in E\mid rank(a,b)=i\\}$,
for all $i\in[n]$. A matching $M$ in $G$ can be decomposed as $M=M_{1}\cup
M_{2}\cup\cdots\cup M_{m}$ where $M_{i}=M\cap{E_{i}}$. We define signature of
a matching $M$ in $G$ as an $m$ length tuple
$\rho(M)=\langle|M_{1}|,|M_{2}|,\ldots,|M_{m}|\rangle$.

###### Definition 2.8 (Rank-Maximal Matching).

Given a bipartite graph $G=(A\cup B,E_{1},E_{2},\ldots,E_{m})$, A matching $M$
in $G$ with lexicographically highest signature $\rho(M)$ is called as a rank-
maximal matching.

Note that all rank-maximal matchings have identical signature. Furthermore, A
rank-maximal matching need not be maximum size matching.

###### Definition 2.9 (Rank-Maximal Perfect Matching).

Given a bipartite graph $G=(A\cup B,E_{1},E_{2},\ldots,E_{m})$, a perfect
matching $M$ in $G$ with lexicographically highest signature $\rho(M)$ among
all perfect matchings in $G$ is called as a rank-maximal perfect matching.

A matching $M$ in $G$ can be interpreted as an allocation of vertices in $B$
to the vertices in $A$. The ranks of the edges can be interpreted as the
ordinal preferences of the vertices in $A$. Under this interpretation, we
borrow the definition of sequencibility (SEQ) (Definition 2.7) for matchings.
A matching $M$ is said to be sequencible if the corresponding allocation $M$
is sequencible. We denote by $\rho(M)$, the picking sequence of vertices in
$A$ that constructs $M$.

##  3\. Existence and Computation of WSD-PROP1 Allocations for Chores via
Matchings

We now show that WSD-PROP1 allocations always exist for chores. To show this,
we first characterize WSD-PROP1 bundles in Lemma 3.1. Using this lemma, we
construct a bipartite graph $G_{c}=(S\cup B,E)$ called an _allocation graph_
of a chores instance. We show that a $B$-perfect matching in $G_{c}$
corresponds to a WSD-PROP1 allocation. We then use Hall’s marriage condition
(Hall, 1987) to demonstrate that such a matching always exists, thus
establishing the existence of WSD-PROP1 allocations. Later we extend these
results to the case of goods in Appendix A

###### Lemma 3.1.

Let $T\subseteq B$ be a set of $m_{i}$ chores, and let
$r_{1}<r_{2}<\cdots<r_{m_{i}}$ be the ranks of the chores in $T$ in the
ranking $\pi_{i}$ of agent $a_{i}$ (i.e, this set consists of the
$r_{1}$-least favorite chore, $r_{2}$-least favorite chore,$\cdots$, and the
$r_{m_{i}}$-least favorite chore for agent $a_{i}$). Then bundle $T$ is _WSD-
PROP1_ for $a_{i}$ if and only if the following two conditions hold:

(1) $\displaystyle m_{i}$ $\displaystyle\leq$ $\displaystyle\lfloor
m\alpha_{i}\rfloor+1$ (2) $\displaystyle\forall 1\leq\ell\leq m_{i},\quad
r_{\ell}$ $\displaystyle\geq$
$\displaystyle\left\lceil\frac{\ell-1}{\alpha_{i}}\right\rceil$

###### Proof.

Without loss of generality, for simplifying the notation, let the chores be
renumbered according to the ranking of agent $a_{i}$. Thus, $b_{j}=\pi_{i}(j)$
for $1\leq j\leq m$. We assume $\alpha_{i}<1$ as otherwise any bundle is WSD-
PROP1 for agent $a_{i}$ and further, $\alpha_{i}>0$ as otherwise agent $a_{i}$
can be removed from the instance.

First, let us prove the necessity of these conditions. If any of the two
conditions are not met, we exhibit a valuation $v_{i}$ according to which, the
bundle $T$ is not WPROP1 for agent $a_{i}$. Suppose $T$ violates condition 1.
That is $m_{i}\geq\lfloor m\alpha_{i}\rfloor+2$. We set $v_{i}(b_{j})=1$ for
all $b_{j}\in B$. Under this valuation,

$\forall b\in T,\quad v_{i}(T\setminus\\{b\\})\geq\lfloor
m\alpha_{i}\rfloor+1>m\alpha_{i}=\alpha_{i}.v_{i}(B)$

Thus $T$ is not a WPROP1 bundle. Similarly, suppose $T$ violates condition 2.
That is, $r_{\ell}\leq\left\lceil\frac{\ell-1}{\alpha_{i}}\right\rceil-1$ for
some $1\leq\ell\leq m_{i}$. We set $v_{i}(b_{j})=1$ for all $1\leq
j\leq\left\lceil\frac{\ell-1}{\alpha_{i}}\right\rceil-1$ and $v_{i}(b_{j})=0$
for all $j\geq\left\lceil\frac{\ell-1}{\alpha_{i}}\right\rceil$. Under this
valuation, $\forall b\in T$ we have

$v_{i}(T\setminus\\{b\\})\geq\ell-1=\left(\frac{\ell-1}{\alpha_{i}}\right)\alpha_{i}>\left(\left\lceil\frac{\ell-1}{\alpha_{i}}\right\rceil-1\right)\alpha_{i}=\alpha_{i}.v_{i}(B)$

Therefore, the bundle $T$ is not WPROP1.

We now show the sufficiency of these conditions. Suppose conditions 1 and 2
hold true for the bundle $T$. It suffices to consider the case when both the
conditions 1 and 2 are tight, except $r_{1}=1$. This is because, for any other
bundle
$Y_{i}=\\{\pi(r^{\prime}_{1}),\pi(r^{\prime}_{2})\cdots,\pi(r^{\prime}_{k})\\}$
where $1\leq r^{\prime}_{1}<r^{\prime}_{2}<\cdots<r^{\prime}_{k}$, and at
least one of the conditions 1 or 2 is not tight, we have
$Y_{i}\succsim^{\text{SD}}_{i}T$ since, for all $1\leq\ell\leq k$,
$r^{\prime}_{\ell}\geq r_{\ell}$.

To show that $T$ is WSD-PROP1 for agent $a_{i}$, we construct a fractional
allocation $T^{\prime}$ using $T$ such that
$T\succsim_{i}^{\text{SD}}T^{\prime}$ and $T^{\prime}$ is a WSD-PROP1
allocation.

Consider the interval set
$I^{i}=\\{I^{i}_{1},I^{i}_{2},\ldots,I^{i}_{k_{i}}\\}$ of agent $a_{i}$.
Include the chore $b_{1}$ in $T^{\prime}$. For any other chore $b_{j}\in
T\setminus\\{b_{1}\\}$, we know that
$\pi^{-1}_{i}(b_{j})=\left\lceil\frac{\ell-1}{\alpha_{i}}\right\rceil$ for
some $\ell\in[m_{i}]$. Therefore, a non-zero fraction of the chore $b_{j}$
lies in the right end of the interval
$I^{i}_{\ell-1}=\left[\frac{\ell-2}{\alpha_{i}},\frac{\ell-1}{\alpha_{i}}\right]$.
Suppose
$\frac{\ell-1}{\alpha_{i}}=\left\lceil\frac{\ell-1}{\alpha_{i}}\right\rceil-\delta$
for some $0<\delta\leq 1$. That is, $1-\delta$ fraction of $b_{j}$ lies in
$I^{i}_{\ell-1}$ and the remaining $\delta$ portion lies in the interval
$I^{i}_{\ell}$. Then, from the interval $I^{i}_{\ell-1}$ include the
$1-\delta$ fraction of chore $b_{j}$ and $\delta$ fraction of the preceding
chore $b_{j-1}$ in $T^{\prime}$ (as shown in Figure 1). Under any valuation
$v_{i}\in\mathscr{U}{(\pi_{i})}$, for every chore $b_{j}$ we have
$\delta.{v_{i}(b_{j-1})}+(1-\delta)v_{i}(b_{j})\geq v_{i}(b_{j})$. Therefore
it is clear that $T\succsim^{\text{SD}}_{i}T^{\prime}$.

$0$$1$$2$$3$$4$$5$$6$$7$$\cdots$$m$disutilitychores$I_{1}^{i}$$I_{1}^{i}$$I_{k_{i}}^{i}$
Figure 1. Construction of the fractional allocation $T^{\prime}$ (shaded in
grey) that is SD dominated by $T$.

From the construction of $T^{\prime}$, we know
$T^{\prime}\setminus\\{b_{1}\\}$ contains the least valued one unit of chore
from each interval (except possibly the last interval which could have no
contribution to $T^{\prime}$). Therefore,
$v_{i}(T-b_{1})\leq\sum_{j=1}^{k_{i}}\alpha_{i}v_{i}(I^{i}_{j})=\alpha_{i}.v_{i}(B)$.
Thus, $T^{\prime}$ is a WSD-PROP1 bundle. ∎

With the help of this characterization, we now construct an allocation graph
$G_{c}$ of chores. Given a fair allocation instance $\mathcal{I}=\langle
A,B,\Pi,\mathcal{F}\rangle$, we construct a bipartite graph - the allocation
graph $G_{c}=(S\cup B,E)$ as follows:

  * -

The set of chores $B$ forms one part of $G_{c}$ with chores interpreted as
vertices.

  * -

For every agent $a_{i}\in A$, and every $\ell=1,2,\cdots,m_{i}=\lfloor
m\alpha_{i}\rfloor+1$, create vertex $s_{i,\ell}$ in $S$. We call these the
$m_{i}$ many _slots_ of agent $a_{i}$.

  * -

From each slot $s_{i,\ell}$, draw edges to every chore $b$ for which
$\pi_{i}^{-1}(b)\geq\left\lceil\frac{\ell-1}{\alpha_{i}}\right\rceil$. That
is, $(s_{i,\ell},b)\in
E\iff\pi_{i}^{-1}(b)\geq\left\lceil\frac{\ell-1}{\alpha_{i}}\right\rceil$

The allocation graph $G_{c}$ exhibits several interesting properties:

Firstly, we have

###### Proposition 3.2.

$B$-perfect matching in $G_{c}$, i.e a matching that saturates all the chores,
satisfies Conditions 1 and 2 and this corresponds to a WSD-PROP1 allocation of
chores. Conversely, any WSD-PROP1 allocation satisfies Conditions 1 and 2 and
thus forms a $B$-perfect matching in $G_{c}$.

Moreover, in the interval set
$I^{i}=\\{I^{i}_{1},I^{i}_{2},\ldots,I^{i}_{k_{i}}\\}$ of an agent $a_{i}$, if
non-zero fraction of a chore $b$ lies in the interval
$I^{i}_{\ell}=\left[\frac{\ell-1}{\alpha_{i}},\frac{\ell}{\alpha_{i}}\right]$,
then $\pi_{i}^{-1}(b)\geq\left\lceil\frac{\ell-1}{\alpha_{i}}\right\rceil$.
Thus slot $s_{i,\ell}$ has an edge to chore $b$ in $G_{c}$. This is formally
stated in the following proposition.

###### Proposition 3.3.

In the allocation graph $G_{c}$ of a chore allocation instance $\mathcal{I}$,
each slot $s_{i,\ell}$ of each agent $a_{i}\in A$, has edges to every chore
with a non-zero portion in the interval $I^{i}_{\ell}$ in the interval set of
$a_{i}$.

We also observe the following property regarding edge relationships in
$G_{c}$:

###### Proposition 3.4.

Let $S_{i}=\\{s_{i,\ell}\mid\ell\in[m_{i}]\\}$ represent the set of slots in
$S$ that belong to an agent $a_{i}\in A$. For any two chores $b_{j}$ and
$b_{k}$ in $B$, such that $\pi_{i}^{-1}(b_{k})\geq\pi_{i}^{-1}(b_{j})$, the
neighbourhood of $b_{k}$ in $S_{i}$ contains the neighbourhood of $b_{j}$ in
$S_{i}$. That is, $N(b_{j})\cap S_{i}\subseteq N(b_{k})\cap S_{i}$. Therefore,
for any set of chores $Y=\\{b_{1},b_{2},\cdots,b_{k}\\}$, the following holds:

$S_{i}\cap
N\left(\\{\pi_{i}(1),\pi_{i}(2),\cdots,\pi_{i}(k)\\}\right)\subseteq S_{i}\cap
N(Y)$

We now show the existence of WSD-PROP1 allocations by showing that a
$B$-perfect matching always exists in $G_{c}$. To prove this, we rely on the
Hall’s marriage theorem (Hall, 1987) which characterizes the existence of
perfect matchings in bipartite graphs.

###### Theorem 3.5 (Hall’s Theorem (Hall, 1987)).

Given a bipartite graph $G=(A\cup B,E)$, there exists an $A$-perfect matching
in $G$ if and only if for every subset $S\subseteq A$, the number of vertices
in the neighbourhood $N(A)$ is greater than or equal to the size of $S$:

$\forall S\subseteq A,\ |N(S)|\geq|S|$

Now, we establish the following main result:

###### Theorem 3.6.

For any fair allocation instance of chores $\mathcal{I}=\langle
A,B,\Pi,\mathcal{F}\rangle$, there always exists a WSD-PROP1 allocation.

###### Proof.

Consider the allocation graph $G_{c}$ of $\mathcal{I}$. We show that $G_{c}$
always has a $B$-perfect matching and thus $\mathcal{I}$ has a WSD-PROP1
allocation. Let $T=\\{b_{1},b_{2},\cdots,b_{k}\\}\subseteq B$ be set of $k$
vertices in $B$. The goal is to show that the size of the neighbourhood $N(T)$
is bigger than or equal to the size of $T$. From Proposition 3.4, we can
assume _w.l.o.g_ that for each agent $a_{i}\in A$, the chores
$b_{1},b_{2},\cdots,b_{k}$ are the first (lowest rank) $k$ chores, since it
minimizes the neighbourhood. For an agent $a_{i}$, let $s_{i,\ell_{i}}$ be the
highest index slot which has an edge to $b_{k}$. Thus, all the slots
$s_{i,1},s_{i,2},\cdots,s_{i,\ell_{i}}$ have edges to $b_{k}$. Therefore, the
size of the neighbourhood $|N(T)|\geq\sum_{i\in[n]}\ell_{i}$. Since the slot
$s_{i,\ell_{i}+1}$ does not have an edge to $b_{k}$, Condition 2 is violated.
Thus,

$\displaystyle k<\left\lceil\frac{(\ell_{i}+1)-1}{\alpha_{i}}\right\rceil$
$\displaystyle\implies$ $\displaystyle k<\frac{\ell_{i}}{\alpha_{i}}+1$
$\displaystyle\implies$ $\displaystyle(k-1)\alpha_{i}<\ell_{i}$
$\displaystyle\implies$
$\displaystyle\sum_{i\in[n]}(k-1)\alpha_{i}<\sum_{i\in[n]}\ell_{i}$ (Summing
over all agents) $\displaystyle\implies$ $\displaystyle k-1<|N(T)|$ (We know
$\sum_{i\in[n]}\ell_{i}\leq|N(T)|$) $\displaystyle\implies$ $\displaystyle
k\leq|N(T)|$ (As both $|N(T)|$ and $k$ are integers)

Therefore, For any set of $k$ chores the size of the neighbourhood is more
than or equal to $k$. From Theorem 3.5, the allocation graph $G_{c}$ always
has a $B$-perfect matching - which corresponds to a WSD-PROP1 allocation of
chores. ∎

Therefore, using the famous Hopcroft-Karp algorithm (Hopcroft and Karp, 1973)
to find perfect matchings, we can compute a WSD-PROP1 allocation in time
$\mathcal{O}(m+n)^{2.5}$

##  4\. Optimizing Over Allocations

Recall that any $B$-perfect matching in the allocation graph $G_{c}$
corresponds to a WSD-PROP1 allocation and vice versa. In this section we
extend the allocation graph $G_{c}$ to $G^{+}_{c}$ by balancing the two parts
of the bipartite graph while maintaining the correspondence between WSD-PROP1
allocations and perfect matchings in $G^{+}_{c}$. We then optimize different
linear objective functions over all WSD-PROP1 allocations using the perfect
matching polytope.

#### Extending the Allocation Graph:

Consider the allocation graph $G_{c}=(S\cup B,E)$ of an instance $\mathcal{I}$
of chores allocation. For each agent $a_{i}\in A$, there are $m_{i}=\lfloor
m\alpha_{i}\rfloor+1$ many slots in $S$. Therefore the total number of slots
$|S|=n+\sum_{i\in[n]}\lfloor m\alpha_{i}\rfloor$. To construct
$G^{+}_{c}=(S\cup B^{\prime},E^{\prime})$, we create $|S|-m=q$ many additional
_dummy_ chores $b^{\prime}_{1},b^{\prime}_{2},\cdots,b^{\prime}_{q}$ in
$B^{\prime}$ to balance the bipartite graph. Draw additional edges from all
the slots in $S$ to every dummy chore.

A WSD-PROP1 allocation of chores gives a $B$-perfect matching in $G_{c}$. We
can extend this matching to a perfect matching in $G^{+}_{c}$ by matching the
dummy chores in any manner as all the dummy chores have edges to every slot.
Conversely, given a perfect matching in $G^{+}_{c}$, we can ignore the edges
from dummy chores to get a $B$-perfect matching in $G_{c}$ and thus a WSD-
PROP1 allocation.

Given a bipartite graph $G=(X\cup Y,E)$, the following constraints define the
matching polytope:

(3) $\displaystyle\begin{split}\sum_{x\in N(y)}e_{xy}&=1\quad\forall y\in Y\\\
\sum_{y\in N(x)}e_{xy}&=1\quad\forall x\in X\\\ e_{xy}&\geq 0\end{split}$

We know that above matching polytope is integral (Lovász and Plummer, 2009)
and hence a matching that maximizes a given objective function is computable
in polynomial-time (Khachiyan, 1980; Karmarkar, 1984). We now use this fact to
compute WSD-PROP1 allocations while considering agents’ efficiency in doing
the chores.

###  4.1. Considering Agent Competence

Regardless of how each agent personally values any given chore, it is
important to acknowledge that their skills and proficiency in performing them
can vary significantly across different tasks. For any specific agent-chore
pairing $a_{i},b$, we can quantify the agent’s competence in performing chore
$b$ as $u_{i}(b)\in[0,1]$, where $0$ indicates low competency and $1$
indicates high competency. This efficiency metric helps us assess how well-
suited each agent is to tackle a particular chore, guiding us in achieving a
fair and efficient chore allocation.

We can use the above given linear program formulation to maximize efficiency
over all WSD-PROP1 allocations. Given an extended allocation graph
$G^{+}_{c}=(S,B^{\prime},E^{\prime})$, We set the objective function as
follows:

$\displaystyle\text{maximize}\quad\sum_{(s_{i,\ell},b)\in
E^{\prime}}u_{i}(b)\cdot e_{(i,\ell),b}$

Similarly, we can optimize for time spent on doing chores and other linear
objective functions.

##  5\. Best of Both Worlds

In this section, using the perfect matchings in the extended allocation graph
$G^{+}_{c}$, we give a polynomial time algorithm to compute an ex-ante WSD-EF
and ex-post WSD-PROP1 allocation of chores.

We begin by constructing a WSD-EF allocation $X=\langle
X_{1},X_{2},\cdots,X_{n}\rangle$. For each agent $a_{i}\in A$, give
$\alpha_{i}$ fraction of every chore $b\in B$. In this allocation, For each
pair of agents $a_{i}$ and $a_{k}$, for any two valuations
$v_{i}\in\mathscr{U}(\pi_{i}),v_{k}\in\mathscr{U}(\pi_{k})$, we know that
$\frac{v_{i}(X_{i})}{\alpha_{i}}=\frac{v_{i}(X_{k})}{\alpha_{k}}=v_{i}(B)$ and
hence $X$ is a WSD-EF allocation. We now show that this fractional allocation
can be realized as a fractional perfect matching in the extended allocation
graph $G^{+}_{c}$.

###### Lemma 5.1.

Given an instance $\mathcal{I}=\langle A,B,\Pi,\mathcal{F}\rangle$ of chore
allocation, there exists a fractional perfect matching in the extended
allocation graph $G^{+}_{c}=(S\cup{B^{\prime}},E^{\prime})$ of $\mathcal{I}$
that corresponds to a WSD-EF chore allocation where each agent $a_{i}$
receives $\alpha_{i}$ fraction of every chore.

###### Proof.

We first construct a fractional matching $M$ that saturates all the _real_
chores (non dummy chores). Such a matching can always be extended to a
fractional perfect matching by assigning the dummy chores in any manner, as
all the dummy chores have edges to all the slots.

Consider the interval set $I^{i}$ of an agent $a_{i}\in A$. From Proposition
3.3, we know that slot $s_{i,\ell}$ has edges to every chore in the interval
$I^{i}_{\ell}$. With the help of this fact, we construct a fractional matching
$M$ in $G^{+}_{c}$ as follows:

Let $x_{i,\ell,b}$ denote the fraction of the edge $(s_{i,\ell},b)$ in $M$.
let $\delta_{b,\ell}$ denote the fraction of a chore $b\in B$ that is present
in the interval $I^{i}_{\ell}$. For every edge $(s_{i,\ell},b)$, we set
$x_{i,\ell,b}=\alpha_{i}\cdot\delta_{b,\ell}$. A slot $s_{i,\ell}$ receives
non zero fractions of the chores from the interval $I^{i}_{\ell}$. Each slot
receives at most $1$ unit of chore because total chores assigned for a slot
$s_{i,\ell}$ is :

$\displaystyle\sum_{b\in B}x_{i,\ell,b}=\alpha_{i}\sum_{b\in
B}\delta_{b,\ell}\leq\alpha_{i}\frac{1}{\alpha_{i}}=1$

The fraction of a given real chore $b$ received by agent $i$ across all the
slots is:

$\displaystyle\sum_{\ell=1}^{m_{i}}x_{i,\ell,b}=\alpha_{i}\sum_{\ell=1}^{m_{i}}\delta_{b,\ell}=\alpha_{i}$

The matching $M$ saturates all the real chores. Since the graph $G^{+}_{c}$ is
a balanced bipartite graph, and as all the dummy chores have edges to all the
slots, the matching $M$ can be extended to a fractional perfect matching by
dividing the dummy chores across the remaining spaces of all the slots in any
arbitrary way. ∎

Let us denote this fractional perfect matching as $M^{*}$. Note that $M^{*}$
lies inside the matching polytope of $G^{+}_{c}$. We now decompose this
fractional perfect matching into convex combination of integral perfect
matchings with the help of Birkhoff’s decomposition. Given a perfect matching
$M$(fractional or otherwise) of a balanced bipartite graph $G=(P\cup Q,E)$
with $2n$ vertices, $M$ can be represented as a $n\times n$ bi-stochastic
matrix $X=(x_{ij})$ where an entry $x_{ij}$ denotes the fraction of the edge
$(i,j)$ present in $M$. Given a fractional perfect matching, we can decompose
it as a convex combination of integral perfect matchings with the help of
Birkhoff-von-Neumann theorem (Birkhoff, 1946; von Neumann, 1953; Johnson et
al., 1960; Lovász and Plummer, 2009).

###### Theorem 5.2 (Birkhoff-von Neumann).

Let $X$ be a $p\times p$ bi-stochastic matrix. There exists an algorithm that
runs in $\mathcal{O}(p^{4.5})$ time and computes a decomposition
$X=\sum_{k=1}^{q}\lambda_{k}X_{k}$ where $q\leq p^{2}-p+2$; for each
$k\in[q],\lambda_{k}\in[0,1]$ and $X_{k}$ is a $p\times p$ permutation matrix;
and $\sum_{k=1}^{q}\lambda_{k}=1$.

With the help of Theorem 5.2, we design Algorithm 1: The Uniform Lottery
Algorithm, which gives an ex-ante WSD-EF and ex-post WSD-PROP1 allocation of
chores using only the ordinal valuations.

Algorithm 1 Uniform Lottery Algorithm for chores

1:A chore allocation instance
$\mathcal{I}=\langle{A},B,\Pi,\mathcal{F}\rangle$, where $|A|=n$ and $|B|=m$.

2:A fractional WSD-EF allocation $X=\sum_{k=1}^{q}~{}\lambda_{k}~{}X_{k}$
where each $X_{k}$ represents a deterministic WSD-PROP1 allocation and
$q\in\mathcal{O}(m^{c})$.

3:$G^{+}_{c}\leftarrow$ extended allocation graph of $\mathcal{I}$

4:$Y\leftarrow$ fractional perfect matching in $G^{+}_{c}$ where each agent
$a_{i}\in A$ gets $\alpha_{i}$ fraction of every real chore $\triangleright$
(As in Lemma 5.1)

5:Invoke Theorem 5.2 to compute a decomposition
$Y=\sum_{k=1}^{q}~{}\lambda_{k}Y_{k}$ where $q\leq(m+n)^{2}-(m+n)-2$

6:Convert $Y=\sum_{k=1}^{q}\lambda_{k}{Y_{k}}$ to
$X=\sum_{k=1}^{q}\lambda_{k}{X_{k}}$ where all the dummy chores are ignored.

7:return Allocation $X$ and its decomposition
$\sum_{k=1}^{q}\lambda_{k}{X_{k}}$

###### Theorem 5.3.

The randomized allocation implemented by Algorithm 1 is ex-ante WSD-EF and ex-
post WSD-PROP1

###### Proof.

Algorithm 1 returns an allocation $X$ and its decomposition
$\sum_{k=1}^{q}\lambda_{k}{X_{k}}$. From Lemma 5.1, we know that the
allocation $X$ returned by the algorithm is WSD-EF. Each of the $X_{k}$s in
the decomposition is a $B$-perfect matching in the allocation graph
$G_{c}$.Therefore, from Proposition 3.2, each $X_{k}$ is WSD-PROP1. ∎

##  6\. Beyond Fairness: Economic Guarantees

In Section 3, we discussed the reduction from WSD-PROP1 allocations to
matchings. In this section, we investigate the incorporation of additional
economic efficiency notions alongside fairness. In Appendix Section B.3, we
give an example instance where no WSD-PROP1 allocation is Pareto optimal under
all valuations. Furthermore, we give examples of instances where given the
cardinal valuations, there does not exist a Pareto optimal allocation that is
WSD-PROP1 for the underlying ordinal instance. Therefore, we explore a more
relaxed concept known as _sequencibility_ (SEQ). We prove a general graph
theoretic lemma, showing that every rank-maximizing $A$-perfect matching is
sequencible. This lemma could be of independent interest with other
applications. Using this result, we establish that computing a rank-maximizing
perfect matching, rather than an arbitrary one, yields WSD-PROP1+SEQ
allocations.

We begin with the following simple observation about rank-maximal matchings:

###### Proposition 6.1.

Given a graph $G=(A\cup B,E=E_{1}\cup\ldots\cup E_{r})$, if $M$ is a rank-
maximal matching in $G$, then $M$ is sequencible (SEQ).

###### Proof.

Define $G_{i}=(A\cup B,E_{1}\cup\ldots\cup E_{i})$. Let the rank-maximal
matching $M$ be decomposed as $M=M_{1}\cup M_{2}\cup\ldots M_{r}$ where
$M_{i}=M\cap E_{i}$ for $i\in[r]$. For a vertex $a$, we denote its matched
partner in $M$ as $M(a)$. A picking sequence for $M$ is $\langle
A_{1},A_{2},\ldots,A_{r}\rangle$ where, for $i\in[r]$, $A_{i}$ is an arbitrary
ordering of vertices in $A$ that are matched by an edge in $M_{i}$. This
sequence results in $M$, for the following reason. Firstly, $M_{1}$ is a
maximum matching in $G_{1}$. For each $i\in[r],i>1$, after the agents in
$A_{1}\cup\ldots\cup A_{i-1}$ pick the items they are matched to in $M$,
$M_{i}$ is a maximum matching on rank $i$ edges in the remaining graph. Thus,
when all the agents in $A_{1}\cup\ldots\cup A_{i}$ pick their favorite item
among the available items, there are no items left, which are ranked between
$1$ and $i$ for any of the remaining agents, this results in agents in
$A_{i+1}$ picking their rank $i+1$ items. ∎

Our interest is in finding an $A$-perfect matching that is also sequencible.
In general, a rank-maximal matching need not be an $A$-perfect matching and
all perfect matchings are not sequencible.The Figure 2 shows one such example.
We show that rank-maximal perfect matchings are sequencible. Unlike a rank-
maximal matching, a rank-maximal perfect matching $M$ may not satisfy the
properties mentioned in Proposition 6.1 i.e., $M_{1}$ may not be a maximum
matching in $G_{1}$, and in general, after agents in $A_{1}\cup\ldots\cup
A_{i-1}$ pick their respective choices, $M_{i}$ may not be a maximum matching
on rank $i$ edges in the remaining graph. Hence the ordering of vertices in
$A_{1},\ldots,A_{r}$ needs to be carefully chosen while constructing the
picking sequence.

$1$$1$$1$$1$$2$$2$$2$$2$$A$$B$$a_{1}$$a_{2}$$a_{3}$$a_{4}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$
Figure 2. The edges in red form a perfect matching - but it is not
sequencible. The blue edges correspond to a rank-maximal matching, but it is
not perfect. The squiggly edges corresponds to a rank-maximal $A$-perfect
matching. This is sequencible, and the picking sequence is $\langle
a_{1},a_{2},a_{4},a_{3}\rangle$

###### Lemma 6.2.

Given a graph $G=(A\cup B,E_{1}\cup\ldots\cup E_{r})$ which is an instance of
the rank-maximal matchings problem, and an $A$-perfect matching $M$ in $G$, if
$M$ is a rank-maximal $A$-perfect matching then $M$ is sequencible.

###### Proof.

Consider a rank-maximal $A$-perfect matching $M$. Let $A_{i}=\\{a\in A\mid
rank(a,M(a))=i\\}$ for all $i\in[r]$. We show that there always exists an
ordering $\sigma_{i}(A_{i})$ of vertices within each $A_{i}$ such that
$\sigma(A)=\langle\sigma_{1}(A_{1}),\ldots,\sigma_{r}(A_{r})\rangle$ is a
picking sequence for $M$. Clearly, each vertex $a\in A_{1}$ can appear in any
order in $\sigma(A_{1})$. As long as it appears before vertices in
$A_{i},i>1$, it gets to pick its first choice, which is $M(a)$. Since $M_{1}$
need not be maximum in $G_{1}$, a vertex in $A_{2}$ may still have its first
choice left unmatched after vertices in $A_{1}$ choose their match. However,
to get $M$, we need all the vertices in $A_{i}$ to pick their $i$th choice. We
show the existence of a picking sequence by induction on the length of the
partial sequence constructed at any point. Consider the stage where vertices
in $A^{\prime}\subseteq A$ are already arranged in a picking sequence, and
$A_{1},\ldots,A_{i-1}\subseteq A^{\prime}$, and we are currently constructing
$\sigma_{i}$. We show that there is always a vertex $a\in A_{i}\setminus
A^{\prime}$ that has its first $i-1$ choices already matched to vertices in
$A^{\prime}$. Thus, $a$ can be the next vertex in the sequence, and it will
have to pick its $i$th choice i.e. $M(a)$. Define $B^{\prime}=M(A^{\prime})$.
Define $A^{\prime\prime}=A\setminus A^{\prime}$, $B^{\prime\prime}=B\setminus
B^{\prime}$.

Call an edge $(a,b)\in E\setminus M$, with $a\in A^{\prime\prime},b\in
B^{\prime\prime}$, a $+$-edge if $rank(a,b)<rank(a,M(a))$ i.e. $a$ prefers $b$
over its match in $M$. In the picking sequence, we need to choose a vertex
$a\in A^{\prime\prime}$ that has no $+$-edge to any $b\in B^{\prime\prime}$.
Assume for the sake of contradiction that such an $a$ does not exist. Then
consider the graph $G^{\prime\prime}=(A^{\prime\prime}\cup
B^{\prime\prime},E^{\prime\prime})$, where $E^{\prime\prime}$ is set of edges
$(a,b)$ where $a\in A^{\prime\prime}$, $b\in B^{\prime\prime}$ and $(a,b)\in
M$ or $(a,b)$ is a $+$-edge in $G$. Since $M$ is an $A$-perfect matching, the
degree of every vertex in $A^{\prime\prime}$ is at least $2$. Thus
$G^{\prime\prime}$ must either have an alternating path $P$ or a cycle $C$
that alternates between $+$-edges and edges of $M$. Now, the symmetric
difference $M\oplus C$ (or $M\oplus P$) is a matching that is also perfect and
has a better signature than $M$, since every agent appearing on $C$ gets a
more preferred choice in $M\oplus C$ by the definition of a $+$-edge. This
contradicts the assumption that $M$ is a rank-maximal perfect matching. Thus,
there must be an $a\in A^{\prime\prime}$ with no $+$-edge incident on it, and
hence $M(a)$ is its most preferred choice in $B^{\prime\prime}$. This vertex
can be inserted as the next vertex in the picking sequence, breaking ties
arbitrarily, if any. ∎

Using Lemma 6.2, we now show that a rank-maximal perfect matching in the
extended allocation graph $G^{+}_{c}$ gives a sequencible WSD-PROP1
allocation.

###### Theorem 6.3.

There always exist a WSD-PROP1+SEQ allocation of chores.

###### Proof.

Let $G^{+}_{c}=(S,B^{\prime},E^{\prime})$ be the extended allocation graph of
an instance $\mathcal{I}$. Recall that $B$ is the set of real chores and
$B^{\prime}\setminus B$ is the set of dummy chores and
$|B|=m,|B^{\prime}|=m+q$. For each slot $s_{i,\ell}$, we first rank the real
chores from $1$ to $m$ as $rank(s_{i,\ell},b)=m+1-\pi_{i}(b)$ for all $b\in
B$. The dummy chores ranked from $m+1$ to $m+q$ in an arbitrary way.

For any two slots $s_{i,p}$ and $s_{i,q}$ of an agent $a_{i}$, if $p>q$, then
$N(p)\subseteq N(q)$. This is because $G^{+}_{c}$ satisfies Condition 2.
Therefore, given a matching $M$, if
$rank(s_{i,p},M(s_{i,p})>rank(s_{i,q},M(s_{i,q}))$, then we can interchange
$M(s_{i,p})$ and $M(s_{i,q})$ without altering the signature of the matching.
Thus, given a rank-maximal perfect matching $M$, we can assume w.o.l.g that
for any agent $a_{i}\in A$, and $p,q\leq m_{i}$, if $p>q$ then
$rank(s_{i,p},M(s_{i,p})<rank(s_{i,q},M(s_{i,q}))$.

Given a rank-maximal perfect matching $M$ in $G^{+}_{c}$, from Lemma 6.2 we
obtain a sequence $\sigma(S)$ of slots. To construct a sequence of agents,
replace each $s_{i,\ell}$ with the corresponding agent $a_{i}$. Since dummy
chores are ranked higher than real chores, all the slots that are matched to
dummy chore forms the tail of the sequence $\sigma(M)$ and hence they can be
safely ignored. Therefore, a rank-maximal perfect matching in $G^{+}_{c}$
gives a WSD-PROP1+SEQ allocation. ∎

Therefore, using the algorithm to find rank-maximal perfect matchings
(Michail, 2007; Irving, 2003), we can compute a WSD-PROP1+SEQ allocation in
time $\mathcal{O}((m+n)^{3.5})$.

##  7\. Conclusion

In this paper, we consider the fairness notion of weighted necessarily
proportionality up to one item (WSD-PROP1). We show that finding WSD-PROP1
allocations can be reduced to finding perfect matchings in a bipartite graph -
namely the allocation graph. This insight provides a practical framework for
leveraging tools and techniques from the field of matching theory. We show
that rank-maximal perfect matchings give picking sequences for finding WSD-
PROP1+SEQ allocations. We show that the perfect matching polytope of the
allocation graph captures all the WSD-PROP1 allocations, thus enabling us to
optimize for any linear objective function. We then create a fractional
perfect matching in the allocation graph, corresponding to a WSD-EF
allocation. Decomposing this allocation, equivalent to decomposing the
fractional matching into integral matchings, results in a randomized algorithm
for computing an Ex-ante WSD-EF Ex-post WSD-PROP1 allocation, both in the case
of goods and chores. Our works raises the open question of the existence of
WSD-PROP1 allocations in the mixed setting, where set $B$ includes both goods
and chores.

###### Acknowledgements.

We express gratitude to the anonymous reviewers of AAMAS 2024 for their
valuable comments. H.V. acknowledges support from TCS-RSP for their grant.
Special thanks to friends and colleagues at CMI - Archit Chauhan, Asif Khan,
Soumodev Mal, and Sheikh Shakil Akhtar for their time and expertise in
proofreading and discussing the contents of this paper.

## References

  * (1)
  * Amanatidis et al. (2022) Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, and Alexandros A Voudouris. 2022.  Fair division of indivisible goods: A survey.  _arXiv preprint arXiv:2202.07551_ (2022).
  * Aziz (2020) Haris Aziz. 2020.  Simultaneously Achieving Ex-ante and Ex-post Fairness. In _Web and Internet Economics_ , Xujin Chen, Nikolai Gravin, Martin Hoefer, and Ruta Mehta (Eds.). Springer International Publishing, Cham, 341–355.
  * Aziz et al. (2022) Haris Aziz, Ioannis Caragiannis, Ayumi Igarashi, and Toby Walsh. 2022.  Fair allocation of indivisible goods and chores.  _Autonomous Agents and Multi-Agent Systems_ 36 (2022), 1–21.
  * Aziz et al. (2023) Haris Aziz, Aditya Ganguly, and Evi Micha. 2023.  Best of Both Worlds Fairness under Entitlements. In _Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems_ (London, United Kingdom) _(AAMAS ’23)_. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 941–948.
  * Aziz et al. (2015) Haris Aziz, Serge Gaspers, Simon Mackenzie, and Toby Walsh. 2015.  Fair Assignment of Indivisible Objects under Ordinal Preferences.  _Artif. Intell._ 227, C (oct 2015), 71–92.  https://doi.org/10.1016/j.artint.2015.06.002
  * Aziz et al. (2020) Haris Aziz, Hervé Moulin, and Fedor Sandomirskiy. 2020.  A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation.  _Operations Research Letters_ 48, 5 (2020), 573–578.  https://doi.org/10.1016/j.orl.2020.07.005
  * Babaioff et al. (2022) Moshe Babaioff, Tomer Ezra, and Uriel Feige. 2022.  Best-of-Both-Worlds Fair-Share Allocations.  arXiv:2102.04909 [cs.GT]
  * Barman and Krishnamurthy (2019) Siddharth Barman and Sanath Kumar Krishnamurthy. 2019.  On the Proximity of Markets with Integral Equilibria. In _Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence_ (Honolulu, Hawaii, USA) _(AAAI’19/IAAI’19/EAAI’19)_. AAAI Press, Article 215, 8 pages.  https://doi.org/10.1609/aaai.v33i01.33011748
  * Bezáková and Dani (2005) Ivona Bezáková and Varsha Dani. 2005.  Allocating indivisible goods.  _ACM SIGecom Exchanges_ 5, 3 (2005), 11–18.
  * Bhaskar et al. (2020) Umang Bhaskar, AR Sricharan, and Rohit Vaish. 2020.  On approximate envy-freeness for indivisible chores and mixed resources.  _arXiv preprint arXiv:2012.06788_ (2020).
  * Birkhoff (1946) Garrett Birkhoff. 1946.  Three observations on linear algebra.  _Univ. Nac. Tucumán. Revista A._ 5 (1946), 147–151.
  * Bogomolnaia and Moulin (2001) Anna Bogomolnaia and Hervé Moulin. 2001.  A New Solution to the Random Assignment Problem.  _Journal of Economic Theory_ 100, 2 (2001), 295–328.  https://doi.org/10.1006/jeth.2000.2710
  * Bouveret et al. (2010) Sylvain Bouveret, Ulle Endriss, Jérôme Lang, et al. 2010\.  Fair division under ordinal preferences: Computing envy-free allocations of indivisible goods.. In _ECAI_. 387–392.
  * Bouveret and Lemaître (2014) Sylvain Bouveret and Michel Lemaître. 2014.  Characterizing Conflicts in Fair Division of Indivisible Goods Using a Scale of Criteria. In _Proceedings of the 2014 International Conference on Autonomous Agents and Multi-Agent Systems_ (Paris, France) _(AAMAS ’14)_. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 1321–1328.
  * Brams and Kaplan (2002) Steven J. Brams and Todd R. Kaplan. 2002.  Dividing the Indivisible.  _Journal of Theoretical Politics_ 16 (2002), 143 – 173.  https://api.semanticscholar.org/CorpusID:154854134
  * Brânzei and Sandomirskiy (2019) Simina Brânzei and Fedor Sandomirskiy. 2019.  Algorithms for Competitive Division of Chores.  _CoRR_ abs/1907.01766 (2019).  arXiv:1907.01766 http://arxiv.org/abs/1907.01766
  * Budish (2011) Eric Budish. 2011.  The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.  _Journal of Political Economy_ 119, 6 (2011), 1061–1103.
  * Chakraborty et al. (2021) Mithun Chakraborty, Ayumi Igarashi, Warut Suksompong, and Yair Zick. 2021.  Weighted envy-freeness in indivisible item allocation.  _ACM Transactions on Economics and Computation (TEAC)_ 9, 3 (2021), 1–39.
  * Conitzer et al. (2017) Vincent Conitzer, Rupert Freeman, and Nisarg Shah. 2017.  Fair Public Decision Making. In _Proceedings of the 2017 ACM Conference on Economics and Computation_ (Cambridge, Massachusetts, USA) _(EC ’17)_. Association for Computing Machinery, New York, NY, USA, 629–646.  https://doi.org/10.1145/3033274.3085125
  * Foley (1966) Duncan Karl Foley. 1966.  _Resource allocation and the public sector_.  Yale University, Michigan.
  * Freeman et al. (2020) Rupert Freeman, Nisarg Shah, and Rohit Vaish. 2020.  Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation. In _Proceedings of the 21st ACM Conference on Economics and Computation_ (Virtual Event, Hungary) _(EC ’20)_. Association for Computing Machinery, New York, NY, USA, 21–22.  https://doi.org/10.1145/3391403.3399537
  * Gardenfors (1973) Peter Gardenfors. 1973.  Assignment problem based on ordinal preferences.  _Management Science_ 20, 3 (1973), 331–340.
  * Gonczarowski et al. (2019) Yannai A. Gonczarowski, Noam Nisan, Lior Kovalio, and Assaf Romm. 2019.  Matching for the Israeli: Handling Rich Diversity Requirements. In _Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019_ , Anna Karlin, Nicole Immorlica, and Ramesh Johari (Eds.). ACM, 321.
  * Hall (1987) P. Hall. 1987.  _On Representatives of Subsets_.  Birkhäuser Boston, Boston, MA, 58–62.  https://doi.org/10.1007/978-0-8176-4842-8_4
  * Hoefer et al. (2023) Martin Hoefer, Marco Schmalhofer, and Giovanna Varricchio. 2023.  Best of Both Worlds: Agents with Entitlements. In _Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems_ (London, United Kingdom) _(AAMAS ’23)_. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 564–572.
  * Hopcroft and Karp (1973) John E. Hopcroft and Richard M. Karp. 1973.  An $n^{5/2}$ Algorithm for Maximum Matchings in Bipartite Graphs.  _SIAM J. Comput._ 2, 4 (1973), 225–231.  https://doi.org/10.1137/0202019 arXiv:https://doi.org/10.1137/0202019
  * Irving (2003) Robert W Irving. 2003.  Greedy matchings.  _University of Glasgow, Computing Science Department Research Report, TR-2003-136_ (2003).
  * Irving et al. (2006) Robert W Irving, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, and Katarzyna E Paluch. 2006.  Rank-maximal matchings.  _ACM Transactions on Algorithms (TALG)_ 2, 4 (2006), 602–610.
  * Johnson et al. (1960) Diane M. Johnson, A. L. Dulmage, and N. S. Mendelsohn. 1960.  On an Algorithm of G. Birkhoff Concerning Doubly Stochastic Matrices.  _Canad. Math. Bull._ 3 (1960), 237 – 242.  https://api.semanticscholar.org/CorpusID:124014325
  * Karmarkar (1984) N. Karmarkar. 1984.  A New Polynomial-Time Algorithm for Linear Programming. In _Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing_ _(STOC ’84)_. Association for Computing Machinery, New York, NY, USA, 302–311.  https://doi.org/10.1145/800057.808695
  * Khachiyan (1980) L.G. Khachiyan. 1980.  Polynomial algorithms in linear programming.  _U. S. S. R. Comput. Math. and Math. Phys._ 20, 1 (1980), 53–72.  https://doi.org/10.1016/0041-5553(80)90061-0
  * Li et al. (2022) Bo Li, Yingkai Li, and Xiaowei Wu. 2022.  Almost (Weighted) Proportional Allocations for Indivisible Chores. In _Proceedings of the ACM Web Conference 2022_. 122–131.
  * Lipton et al. (2004) R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi. 2004.  On Approximately Fair Allocations of Indivisible Goods. In _Proceedings of the 5th ACM Conference on Electronic Commerce_ (New York, NY, USA) _(EC ’04)_. Association for Computing Machinery, New York, NY, USA, 125–131.  https://doi.org/10.1145/988772.988792
  * Lovász and Plummer (2009) L. Lovász and M.D. Plummer. 2009.  _Matching Theory_.  AMS Chelsea Pub., American Mathematical Society, USA.
  * Manlove (2013) David Manlove. 2013.  _Algorithmics of matching under preferences_. Vol. 2.  World Scientific, Glasgow, UK.
  * Michail (2007) Dimitrios Michail. 2007.  Reducing rank-maximal to maximum weight matching.  _Theoretical Computer Science_ 389, 1-2 (2007), 125–132.
  * Nguyen et al. (2013) Trung Thanh Nguyen, Magnus Roos, and Jörg Rothe. 2013.  A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation.  _Annals of Mathematics and Artificial Intelligence_ 68, 1-3 (2013), 65–90.
  * Panda et al. (2022) Atasi Panda, Anand Louis, and Prajakta Nimbhorkar. 2022.  Bipartite Matchings with Group Fairness and Individual Fairness Constraints.  _CoRR_ abs/2208.09951 (2022).
  * Pruhs and Woeginger (2012) Kirk Pruhs and Gerhard J. Woeginger. 2012.  Divorcing Made Easy. In _Fun with Algorithms_ , Evangelos Kranakis, Danny Krizanc, and Flaminia Luccio (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 305–314.
  * Sankar et al. (2021) Govind S. Sankar, Anand Louis, Meghana Nasre, and Prajakta Nimbhorkar. 2021.  Matchings with Group Fairness Constraints: Online and Offline Algorithms. In _Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021_ , Zhi-Hua Zhou (Ed.). ijcai.org, 377–383.
  * Sönmez and Yenmez (2022) Tayfun Sönmez and M. Bumin Yenmez. 2022.  Affirmative Action in India via Vertical, Horizontal, and Overlapping Reservations.  _Econometrica_ 90, 3 (2022), 1143–1176.  https://doi.org/10.3982/ECTA17788 arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.3982/ECTA17788
  * von Neumann (1953) John von Neumann. 1953.  _1\. A Certain Zero-sum Two-person Game Equivalent to the Optimal Assignment Problem_.  Princeton University Press, Princeton, 5–12.  https://doi.org/10.1515/9781400881970-002
  * Wilson (1977) Leslie Blackett Wilson. 1977.  Assignment using choice lists.  _Journal of the Operational Research Society_ 28 (1977), 569–578.
  * Wu et al. (2023) Xiaowei Wu, Cong Zhang, and Shengwei Zhou. 2023.  Weighted EF1 Allocations for Indivisible Chores. In _Proceedings of the 24th ACM Conference on Economics and Computation_ (London, United Kingdom) _(EC ’23)_. Association for Computing Machinery, New York, NY, USA, 1155.  https://doi.org/10.1145/3580507.3597763

##  Appendix A Allocating Goods

We now extend all our results to the case of goods. Given an instance
$\mathcal{I}=\langle A,B,\Pi,\mathcal{F}\rangle$ of goods allocation, we first
characterize WSD-PROP1 bundles as follows:

###### Lemma A.1.

Let $T\subseteq B$ be a set of $m_{i}$ goods, and let
$r_{1}<r_{2}<\cdots<r_{m_{i}}$ be the ranks of the goods in $T$ in the ranking
$\pi_{i}$ of agent $a_{i}$ (i.e, this set consists of the $r_{1}$-most
favorite good, $r_{2}$-most favorite good,$\cdots$, and the $r_{m_{i}}$-most
favorite good for agent $a_{i}$). Then bundle $T$ is _WSD-PROP1_ for $a_{i}$
if and only if the following two conditions hold:

(4) $\displaystyle m_{i}$ $\displaystyle\geq$ $\displaystyle\lceil
m\alpha_{i}\rceil-1$ (5) $\displaystyle\forall 1\leq\ell\leq m_{i},\quad
r_{\ell}$ $\displaystyle\leq$
$\displaystyle\left\lfloor\frac{\ell}{\alpha_{i}}\right\rfloor+1$

###### Proof.

Without loss of generality, for simplifying the notation, let the goods be
renumbered according to the ranking of agent $a_{i}$. Thus, $b_{j}=\pi_{i}(j)$
for $1\leq j\leq m$. We assume $\alpha_{i}<1$ as otherwise, allocating all
goods to $a_{i}$ is a WSD-PROP1 allocation. Further, $\alpha_{i}>0$ as
otherwise agent $a_{i}$ can be removed from the instance.

First, let us prove the necessity of these conditions. If any of the two
conditions are not met, we exhibit a valuation $v_{i}$ according to which, the
bundle $T$ is not WPROP1 for agent $a_{i}$. Suppose $T$ violates condition 4.
That is $m_{i}\leq\lceil m\alpha_{i}\rceil-2$. We set $v_{i}(b_{j})=1$ for all
$b_{j}\in B$. Under this valuation,

$\forall b\in B,\quad v_{i}(T\cup\\{b\\})\leq\lceil
m\alpha_{i}\rceil-1<m\alpha_{i}=\alpha_{i}.v_{i}(B)$

Thus $T$ is not a WPROP1 bundle. Similarly, suppose $T$ violates condition 5.
That is, $r_{\ell}\geq\left\lfloor\frac{\ell}{\alpha_{i}}\right\rfloor+2$ for
some $1\leq\ell\leq m_{i}$. We set $v_{i}(b_{j})=1$ for all $1\leq
j\leq\left\lfloor\frac{\ell}{\alpha_{i}}\right\rfloor+1$ and $v_{i}(b_{j})=0$
for all the remaining goods. Under this valuation,

$\displaystyle\forall b\in B,\quad v_{i}(T\cup\\{b\\})$ $\displaystyle=\ell$
$\displaystyle=\alpha_{i}\left(\frac{\ell}{\alpha_{i}}\right)$
$\displaystyle<\alpha_{i}\left(\left\lfloor\frac{\ell}{\alpha_{i}}\right\rfloor+1\right)=\alpha_{i}.v_{i}(B)$

Therefore, the bundle $T$ is not WPROP1.

We now show the sufficiency of these conditions. Suppose conditions 4 and 5.
hold true for the bundle $T$. It suffices to consider the case when both the
conditions 4 and 5 are tight. This is because for any other bundle
$Y_{i}=\\{\pi(r^{\prime}_{1}),\pi(r^{\prime}_{2})\cdots,\pi(r^{\prime}_{k})\\}$
where $1\leq r^{\prime}_{1}<r^{\prime}_{2}<\cdots r^{\prime}_{k}$, and at
least one of the conditions 4 or 5 is not tight, we have
$Y_{i}\succsim^{\text{SD}}_{i}T$ since, for all $1\leq\ell\leq k$,
$r^{\prime}_{\ell}\leq r_{\ell}$.

To show that $T$ is WSD-PROP1 for agent $a_{i}$, we construct a fractional
allocation $T^{\prime}$ using $T$ such that
$T\succsim_{i}^{\text{SD}}T^{\prime}$ and $T^{\prime}$ is a WSD-PROP1
allocation.

Consider the interval set
$I^{i}=\\{I^{i}_{1},I^{i}_{2},\ldots,I^{i}_{k_{i}}\\}$ of agent $a_{i}$. For
each good $b_{j}\in T$, we know that
$\pi^{-1}_{i}(b_{j})=\left\lfloor\frac{\ell}{\alpha_{i}}\right\rfloor+1$ for
some $\ell\in[m_{i}]$. For every interval excluding the first interval, i.e.,
$I_{\ell+1}=\left[\frac{\ell}{\alpha_{i}},\frac{\ell+1}{\alpha_{i}}\right]$
for all $1<\ell\leq k_{i}-1$, a non-zero fraction of the good
$\pi^{-1}_{i}(r_{\ell})$, which occupies the interval
$\left[\left\lfloor\frac{\ell}{\alpha_{i}}\right\rfloor,\left\lfloor\frac{\ell}{\alpha_{i}}\right\rfloor+1\right]$
lies in the beginning the interval $I_{\ell+1}$. Suppose
$\left\lfloor\frac{\ell}{\alpha_{i}}\right\rfloor+1=\frac{\ell}{\alpha_{i}}+\delta$
for some $0\leq\delta<1$. That is, $1-\delta$ fraction of $b_{j}$ lies in
$I^{i}_{\ell-1}$ and the remaining $\delta$ portion lies in the interval
$I^{i}_{\ell}$. Then, from the interval $I^{i}_{\ell}$ include the $\delta$
fraction of good $b_{j}$ and $1-\delta$ fraction of the subsequent good
$b_{j+1}$ in $T^{\prime}$ (as shown in Figure 3). Under any valuation
$v_{i}\in\mathscr{U}{(\pi_{i})}$, for every good $b_{j}$ we have
$\delta.{v_{i}(b_{j})}+(1-\delta)v_{i}(b_{j+1})\leq v_{i}(b_{j})$. Therefore
it is clear that $T\succsim^{\text{SD}}_{i}T^{\prime}$.

From the construction of $T^{\prime}$, we know that
$T^{\prime}\cup\\{b_{1}\\}$ contains the highest valued one unit of good from
each interval. Therefore,
$v_{i}(T\cup\\{b_{1}\\})\geq\sum_{j=1}^{k_{i}}\alpha_{i}v_{i}(I^{i}_{j})=\alpha_{i}.v_{i}(B)$.
Thus, $T^{\prime}$ is a WSD-PROP1 bundle.

$0$$1$$2$$3$$4$$5$$6$$7$$\cdots$$m$utilitygoods$I_{1}^{i}$$I_{1}^{i}$$I_{k_{i}}^{i}$
Figure 3. Construction of the fractional allocation $T^{\prime}$ (shaded in
grey) that is SD dominated by $T$.

∎

With the help of this characterization, we now construct an allocation graph
$G_{g}$ of goods. Given a fair allocation instance $\mathcal{I}=\langle
A,B,\Pi,\mathcal{F}\rangle$, we construct a bipartite graph - the allocation
graph $G_{g}=(S\cup B,E)$ as follows:

  * -

The set of goods $B$ forms one part of $G_{g}$ with goods interpreted as
vertices.

  * -

For every agent $a_{i}\in A$, and every $\ell=1,2,\cdots,m_{i}=\lceil
m\alpha_{i}\rceil-1$, create vertex $s_{i,\ell}$ in $S$. We call these the
$m_{i}$ many _slots_ of agent $a_{i}$.

  * -

From each slot $s_{i,\ell}$, draw edges to every good $b$ for which
$\pi_{i}^{-1}(b)\leq\left\lfloor\frac{\ell}{\alpha_{i}}\right\rfloor+1$. That
is, $(s_{i,\ell},b)\in
E\iff\pi_{i}^{-1}(b)\leq\left\lfloor\frac{\ell}{\alpha_{i}}\right\rfloor+1$

The allocation graph $G_{g}$ exhibits several interesting properties:

Firstly, we have

###### Proposition A.2.

An $S$-perfect matching in $G_{g}$, i.e a matching that saturates all the
goods, satisfies Conditions 4 and 5 and this corresponds to a WSD-PROP1
allocation of goods333Note that this allocation could be a partial allocation.
However, any completion of a WSD-PROP1 partial allocation remains WSD-PROP1

Moreover, in the interval set
$I^{i}=\\{I^{i}_{1},I^{i}_{2},\ldots,I^{i}_{k_{i}}\\}$ of an agent $a_{i}$, if
non-zero fraction of a good $b$ lies in the interval
$I^{i}_{\ell}=\left[\frac{\ell-1}{\alpha_{i}},\frac{\ell}{\alpha_{i}}\right]$,
then $\pi_{i}^{-}1(b)-1\leq\left\lfloor\frac{\ell}{\alpha_{i}}\right\rfloor$.
Thus slot $s_{i,\ell}$ has an edge to good $b$ in $G_{g}$. This is formally
stated in the following proposition.

###### Proposition A.3.

In the allocation graph $G_{g}$ of a good allocation instance $\mathcal{I}$,
each slot $s_{i,\ell}$ of each agent $a_{i}\in A$, has edges to every good
with a non-zero portion in the interval $I^{i}_{\ell}$ in the interval set of
$a_{i}$.

We also observe the following property regarding edge relationships in
$G_{g}$:

###### Proposition A.4.

Let $S_{i}=\\{s_{i,\ell}\mid\ell\in[m_{i}]\\}$ represent the set of slots in
$S$ that belong to an agent $a_{i}\in A$. For any two slots $s_{i,p}$ and
$s_{i,q}$ in $S_{i}$, such that $p<q$, the neighbourhood of $s_{i,q}$ in $B$
contains the neighbourhood of $s_{i,p}$ in $B$. That is, $N(s_{i,p})\subseteq
N(s_{i,q})$. Therefore, we have:

$N(s_{i,1})\cup N(s_{i,2})\cup\cdots\cup N(s_{i,k})\subseteq N(s_{i},k)$

We also note the following observation about agents with different
entitlements:

###### Proposition A.5.

For any two agents $a_{i}$ and $a_{k}$ s.t $\alpha_{i}\geq\alpha_{k}$, agent
$a_{i}$ has at least as many slots as agent $a_{k}$ (because of Condition 4)
and the size of the neighbourhood of $\ell$th slot of agent $a_{i}$ is smaller
than or equal to the size of the neighbourhood of $\ell$th slot of agent
$a_{k}$ . That is,

$\forall 1\leq\ell\leq\lceil m\alpha_{k}\rceil-1,\
|N(s_{i,\ell})|\leq|N(s_{k,\ell})|$

We are now ready to show the existence of WSD-PROP1 allocations by showing
that an $S$-perfect matching always exists in $G_{g}$, using the Hall’s
marriage theorem (Hall, 1987).

###### Theorem A.6.

For any fair allocation instance of goods $\mathcal{I}=\langle
A,B,\Pi,\mathcal{F}\rangle$, there always exists a WSD-PROP1 allocation.

###### Proof.

Consider a subset $T$ of slots in $S$, and we aim to show $|T|\leq|N(T)|$. Let
$a^{\prime}_{1},a^{\prime}_{2},\ldots,a^{\prime}_{k}$ represent the agents
with slots in set $S$, and let
$\alpha^{\prime}_{1},\alpha^{\prime}_{2},\ldots,\alpha^{\prime}_{k}$ denote
their respective entitlements. Additionally, let
$\alpha_{1},\alpha_{2},\ldots,\alpha_{k}$ represent the entitlements of the
top $k$ most entitled agents in $A$. Without loss of generality, we assume
$\alpha^{\prime}_{1}\geq\alpha^{\prime}_{2}\geq\ldots\geq\alpha^{\prime}_{k}$
and $\alpha_{1}\geq\alpha_{2}\geq\ldots\geq\alpha_{k}$.

For each agent $a^{\prime}_{p}$ whose slot is present in $T$, let $s_{i_{p}}$
denote the highest index slot of agent $a^{\prime}_{p}$ in set $T$. From
Proposition A.4, we can safely assume that all the $i_{p}$ slots from $s_{1}$
to $s_{i_{p}}$ are included in set $T$. Therefore the size of $T$,
$|T|\leq\sum_{p=1}^{k}i_{p}$.

$\displaystyle|N(T)|$
$\displaystyle\geq\max(|N(s_{i_{1}})|,|N(s_{i_{2}})|,\ldots,|N(s_{i_{k}})|)$
$\displaystyle=\max\left(\left\lfloor\frac{i_{1}}{\alpha^{\prime}_{1}}\right\rfloor,\left\lfloor\frac{i_{2}}{\alpha^{\prime}_{2}}\right\rfloor,\ldots,\left\lfloor\frac{i_{k}}{\alpha^{\prime}_{k}}\right\rfloor\right)+1$
$\displaystyle(\because\text{Construction of\ }G_{g})$
$\displaystyle\geq\max\left(\left\lfloor\frac{i_{1}}{\alpha_{1}}\right\rfloor,\left\lfloor\frac{i_{2}}{\alpha_{2}}\right\rfloor,\ldots,\left\lfloor\frac{i_{k}}{\alpha_{k}}\right\rfloor\right)+1$
($\because$ Proposition A.5)

As $\sum_{p=1}^{k}\alpha_{p}\leq 1$, there is at least one
$\alpha_{q}\in\\{\alpha_{1},\alpha_{2},\cdots,\alpha_{k}\\}$ s.t
$\alpha_{q}\leq\frac{i_{q}}{i_{1}+i_{2}+\cdots+i_{k}}$. Therefore,

$\displaystyle\max\left(\left\lfloor\frac{i_{1}}{\alpha_{1}}\right\rfloor,\left\lfloor\frac{i_{2}}{\alpha_{2}}\right\rfloor,\ldots,\left\lfloor\frac{i_{k}}{\alpha_{k}}\right\rfloor\right)+1$
$\displaystyle\geq\left\lfloor\frac{i_{q}}{\alpha_{q}}\right\rfloor+1$
$\displaystyle\geq\sum_{p=1}^{k}i_{p}+1$ $\because$
$\alpha_{q}\leq\frac{i_{q}}{\sum_{p=1}^{k}i_{p}}$ $\displaystyle\geq|T|$

Therefore, because of Theorem 3.5, the allocation graph $G_{g}$ always has an
$S$-perfect matching. ∎

Thus, using the famous Hopcroft-Karp algorithm (Hopcroft and Karp, 1973) to
find perfect matchings, we can compute a WSD-PROP1 allocation in time
$\mathcal{O}(m+n)^{2.5}$

###  A.1. Optimizing Over All Allocations

Similar to the case of chores, we first extend the allocation graph $G_{g}$ to
$G^{+}_{g}$ so that perfect matchings in $G^{+}_{g}$ corresponds to WSD-PROP1
allocations and vice versa.

#### Extending the goods allocation graph:

Consider the allocation graph $G_{g}=(S\cup B,E)$ of an instance of goods
allocation. For each agent $a_{i}$, there are $m_{i}=\lceil
m\alpha_{i}\rceil-1$ many slots in $S$. To construct the extended allocation
graph $G^{+}_{g}=(S^{\prime}\cup B^{\prime},E^{\prime})$, create $q=m-|S|$,
that is $q=m+n-\sum_{i\in[n]}\lceil m\alpha_{i}\rceil$ many additional _spare_
slots
$s^{\prime}_{i,m_{i}+1},s^{\prime}_{i,m_{i}+2},\cdots,s^{\prime}_{i,m_{i}+q}$
for _every_ agent $a_{i}\in A$. Now the total number of slots is
$|S^{\prime}|=|S|+nq$. To balance this bipartite graph, create
$t=|S^{\prime}|-m$ many additional _dummy_ goods
$b^{\prime}_{1},b^{\prime}_{2},\cdots,b^{\prime}_{t}$ in $B^{\prime}$. Draw
edges from each spare slot to every good (both real and dummy) to extend $E$
to $E^{\prime}$.

Any perfect matching in $G^{+}_{g}$ corresponds to an $S$-perfect matching in
$G_{g}$ and hence a WSD-PROP1 allocation. Similarly, given an WSD-PROP1
allocation $X$, we know that every bundle in $X$ satisfies conditions 4 and 5
and therefore, for each agent $a_{i}$, the $m_{i}$ many slots can be matched
according to $X$. Such a matching can easily be extended to a perfect matching
as every spare slot has edges to all the remaining goods.

We now optimize over all allocations with the help of the matching polytope
given by Equation 3. Suppose a central agency, such as a government, wants to
is proportionally allocate goods to agents living in different locations. For
a given agent-good pair $a_{i},b_{j}$, there is an associated transportation
cost denoted by $u_{i}(b_{j})$. We can find in polynomial time, a WSD-PROP1
allocation that minimizes the total transportation cost by minimizing the
following objective function subject to the constraints given by Equations 3.

$\sum_{i\in[n]}\sum_{b_{j}\in B}u_{i}(b_{j})$

Similarly, we can optimize for any linear objective function.

###  A.2. Best of Both Worlds Fairness

In (Hoefer et al., 2023) and (Aziz et al., 2023), the authors give a
polynomial time algorithm to compute Ex-ante WSD-EF and Ex-post WSD-PROP1
allocations of goods. The technique used mainly relies on the _Probabilistic
Serial_ rule(Bogomolnaia and Moulin, 2001), also called as the _Eating
Algorithm_. Here we give an alternate algorithm using the matching polytope of
the extended allocation graph $G^{+}_{g}$.

Consider the fractional allocation $X$ where each agent $a_{i}\in A$ receives
$\alpha_{i}$ fraction of every real good. For each pair of agents $a_{i}$ and
$a_{k}$, under any two valuations
$v_{i}\in\mathscr{U}(\pi_{i}),v_{k}\in\mathscr{U}(\pi_{k})$, we know that
$\frac{v_{i}(X_{i})}{\alpha_{i}}=\frac{v_{i}(X_{k})}{\alpha_{k}}=v_{i}(B)$ and
hence $X$ is a WSD-EF allocation. We first show that this fractional
allocation can be realized as a fractional perfect matching in the extended
allocation graph $G^{+}_{g}$.

###### Lemma A.7.

Given an instance $\mathcal{I}=\langle A,B,\Pi,\mathcal{F}\rangle$ of goods
allocation, there exists a fractional perfect matching in the extended
allocation graph $G^{+}_{g}$ that corresponds to a the WSD-EF allocation where
each agent $a_{i}\in A$ receives $\alpha_{i}$ fraction of every good.

###### Proof.

We construct first fractional matching that saturates all the _real_ (non
dummy) goods and all the real (non spare) slots . Such a matching can always
be extended to a fractional perfect matching by assigning the dummy goods in
any manner, as all the dummy goods have edges to all the spare slots.

Consider the interval set $I^{i}$ of an agent $a_{i}\in A$. From Proposition
A.3, we know that slot $s_{i,\ell}$ has edges to every good in the interval
$I^{i}_{\ell}$. With the help of this fact, we construct a fractional matching
in $G^{+}_{g}$ as follows:

Let $x_{i,\ell,b}$ denote the fraction of the edge $(s_{i,\ell},b)$ in the
matching. let $\delta_{b,\ell}$ denote the fraction of a good $b\in B$ that is
present in the interval $I^{i}_{\ell}$. For every edge $(s_{i,\ell},b)$, we
set $x_{i,\ell,b}=\alpha_{i}\cdot\delta_{b,\ell}$. A slot $s_{i,\ell}$
receives non zero fractions of the good from the interval $I^{i}_{\ell}$. Each
slot receives at most $1$ unit of good because total good assigned for a slot
$s_{i,\ell}$ is :

$\displaystyle\sum_{b\in B}x_{i,\ell,b}=\alpha_{i}\sum_{b\in
B}\delta_{b,\ell}\leq\alpha_{i}\frac{1}{\alpha_{j}}=1$

Since $m_{i}=\lceil m\alpha_{i}\rceil-1$ and number of intervals is $\lceil
m\alpha_{i}\rceil$, the goods in the last interval could be unallocated. We
allocate $\alpha_{i}$ fraction of every good in this interval as well to one
of the spare slots of agent $a_{i}$ thus exhausting all the real goods.

The fraction of a given real good $b$ received by agent $i$ across all the
slots is:

$\displaystyle\sum_{\ell=1}^{m_{i}}x_{i,\ell,b}=\alpha_{i}\sum_{\ell=1}^{m_{i}}\delta_{b,\ell}=\alpha_{i}$

This gives us a matching $M$ which saturates all the real goods and real
slots. Since the graph $G^{+}_{g}$ is a balanced bipartite graph, and as every
dummy good has an edge to every spare slot, the matching $M$ can be extended
to a fractional perfect matching by dividing the dummy goods across the
remaining spaces of all the spare slots in any arbitrary way. ∎

Let us denote this fractional perfect matching as $M^{*}$. Note that $M^{*}$
lies inside the matching polytope of $G^{+}_{g}$. We now decompose this
fractional perfect matching into convex combination of integral perfect
matchings with the help of Birkhoff’s decomposition as given in Theorem 5.2.
We design Algorithm 2: The Uniform Lottery Algorithm, which gives an ex-ante
WSD-EF and ex-post WSD-PROP1 allocation of goods using only the ordinal
valuations.

Algorithm 2 Uniform Lottery Algorithm for goods

1:A good allocation instance
$\mathcal{I}=\langle{A},B,\Pi,\mathcal{F}\rangle$, where $|A|=n$ and $|B|=m$.

2:A fractional WSD-EF allocation $X=\sum_{k=1}^{q}~{}\lambda_{k}~{}X_{k}$
where each $X_{k}$ represents a deterministic WSD-PROP1 allocation and
$q\in\mathcal{O}(m^{c})$.

3:$G^{+}_{g}\leftarrow$ extended allocation graph of $\mathcal{I}$

4:$Y\leftarrow$ fractional perfect matching in $G^{+}_{g}$ where each agent
$a_{i}\in A$ gets $\alpha_{i}$ fraction of every real good $\triangleright$
(As in Lemma A.7)

5:Invoke Theorem 5.2 to compute a decomposition
$Y=\sum_{k=1}^{q}~{}\lambda_{k}Y_{k}$ where $k\leq(m+n)^{2}-(m+n)-2$

6:Convert $Y=\sum_{k=1}^{q}\lambda_{k}{Y_{k}}$ to
$X=\sum_{k=1}^{q}\lambda_{k}{X_{k}}$ where all the dummy goods are ignored.

7:return Allocation $X$ and its decomposition
$\sum_{k=1}^{q}\lambda_{k}{X_{k}}$

###### Theorem A.8.

The randomized allocation implemented by Algorithm 2 is ex-ante WSD-EF and ex-
post WSD-PROP1

###### Proof.

Algorithm 2 returns an allocation $X$ and its decomposition
$\sum_{k=1}^{q}\lambda_{k}{X_{k}}$. From Lemma A.7, we know that the
allocation $X$ returned by the algorithm is WSD-EF. Each of the $X_{k}$s in
the decomposition is a $B$-perfect matching in the allocation graph
$G_{g}$.Therefore, from Proposition A.2, each $X_{k}$ is WSD-PROP1. ∎

###  A.3. Sequencible Allocations via Rank-Maximal Perfect Matchings

In this section, we use the Lemma 6.2 to show that a rank-maximal $S$-perfect
matching in the allocation graph $G_{g}$ gives a sequencible WSD-PROP1
allocation.

###### Theorem A.9.

There always exist a WSD-PROP1+SEQ allocation of goods.

###### Proof.

Let $G_{g}=(S,B,E)$ be the allocation graph of an instance $\mathcal{I}$. For
each slot $s_{i,\ell}$, we first rank the goods from $1$ to $m$ as
$rank(s_{i,\ell},b)=\pi_{i}(b)$ for all $b\in B$. For any two slots $s_{i,p}$
and $s_{i,q}$ of an agent $a_{i}$, if $p>q$, then $N(q)\subseteq N(p)$. This
is because $G_{g}$ satisfies Condition 5. Therefore, given a matching $M$, if
$rank(s_{i,p},M(s_{i,p})<rank(s_{i,q},M(s_{i,q}))$, then we can interchange
$M(s_{i,p})$ and $M(s_{i,q})$ without altering the signature of the matching.
Thus, given a rank-maximal $S$-perfect matching $M$, we can assume w.o.l.g
that for any agent $a_{i}\in A$, and $p,q\leq m_{i}$, if $p>q$ then
$rank(s_{i,p},M(s_{i,p})>rank(s_{i,q},M(s_{i,q}))$.

Given a rank-maximal $S$-perfect matching $M$ in $G_{g}$, from Lemma 6.2 we
obtain a sequence $\sigma(S)$ of slots. To construct a sequence of agents,
replace each $s_{i,\ell}$ with the corresponding agent $a_{i}$. Therefore, a
rank-maximal $S$-perfect matching in $G_{g}$ gives a WSD-PROP1+SEQ allocation.
∎

Therefore, using the algorithm to find rank-maximal perfect matchings
(Michail, 2007; Irving, 2003), we can compute a WSD-PROP1+SEQ allocation of
goods in time $\mathcal{O}((m+n)^{3.5})$.

##  Appendix B Examples

In this section we give examples and instances for some of our claims.

###  B.1. Non-Existence of WSD-PROPx Allocations

Consider an ordinal instance with three agents $a_{1},a_{2},$ and $a_{3}$ with
equal entitlements and three goods $b_{1},b_{2},b_{3}$. Let the agents have
identical ranking $(b_{1}\succ b_{2}\succ b_{3})$ over the goods. For this
instance, any WSD-PROPx allocation must allocate one good per agent. Because
otherwise, there would be an agent who gets no good and the allocation is not
WPROPx under the valuation $(1,1,\epsilon)$.

Now consider an allocation where agents gets one item each. Without loss of
generality, let agent $a_{1}$ get the least valuable good $b_{3}$. This
allocation, however, is not WPROPx under the valuation $(1,\epsilon,0)$ for
agent $a_{3}$. Therefore, this instance admits no WSD-PROPx allocation. It is
evident that a similar example can be constructed even for the case of chores.

###  B.2. Impossibility of Pareto Optimal Allocations of Goods

We construct an instance $\mathcal{I}=\langle A,B,\Pi,\mathcal{F}\rangle$ such
that no WSD-PROP1 allocation is PO under all $\Pi$-respecting valuations.
Consider two agents $A=\\{a_{1},a_{2}\\}$ with three goods
$B=\\{b_{1},b_{2},b_{3}\\}$. Let both the agents have identical ordinal
preference: $\pi_{1}(1)=\pi_{2}(1)=b_{1},\pi_{1}(2)=\pi_{2}(2)=b_{2}$ and
$\pi_{1}(3)=\pi_{2}(3)=b_{3}$. Let both the agents have equal entitlements:
$\mathcal{F}=\\{0.5,0.5\\}$.

From the characterization of WSD-PROP1 allocations, we know that a WSD-PROP1
allocation must satisfy conditions 4 and 5 of Lemma A.1. Applying condition 4,
each agent must receive at least one good in any WSD-PROP1 allocation. Suppose
_w.l.o.g_ agent $a_{1}$ receives good $b_{1}$. We then set $v_{1}=(1,1,1)$.
Agent $a_{2}$ must receive at least one of $b_{2},b_{3}$. Suppose _w.l.o.g_
agent $a_{2}$ receives $b_{2}$, we then set $v_{2}=(1,\epsilon,\epsilon)$
where $\epsilon<1$. The good $b_{3}$ can be assigned to any agent (Refer to
Table 1). We see that this WSD-PROP1 allocation cannot be Pareto optimal as
trading the good $b_{1}$ with $b_{2}$ gives a Pareto improvement.

Note that in the above example, agent $a_{1}$ values all the items equally.
However, this equal valuation is not a necessary requirement to show the
incompatibility of WSD-PROP1 with cardinal PO. Specifically, even if we impose
a condition that items with higher rankings must have strictly higher values,
we can still create analogous instances. For example, consider an instance
with two agents and five goods. Let the agents have identical entitlements and
ordinal rankings. It is clear from Condition 4 that any WSD-PROP1 allocation
must give at least two items to each agent. Now, we always can set a
consistent cardinal valuation (with unequal values), that incentives trading
the $1^{\text{st}}$ item with two items of the other agent, giving a Pareto
improvement.

Goods | $b_{1}$ | $b_{2}$ | $b_{3}$
---|---|---|---
Agent $a_{1}$ | $1$ | $1$ | $1$
Agent $a_{2}$ | $1$ | $\epsilon$ | $\epsilon$
Table 1. Exchanging $b_{1}$ with $b_{2}$ gives a Pareto dominating allocation.

###  B.3. Impossibility of Pareto Optimal Allocation of Chores

We construct an instance $\mathcal{I}=\langle A,B,\Pi,\mathcal{F}\rangle$ such
that no WSD-PROP1 allocation is PO under all $\Pi$-respecting valuations.
Consider two agents $A=\\{a_{1},a_{2}\\}$ with three chores
$B=\\{b_{1},b_{2},b_{3}\\}$. Let both the agents have identical ordinal
preference: $\pi_{1}(1)=\pi_{2}(1)=b_{1},\pi_{1}(2)=\pi_{2}(2)=b_{2}$ and
$\pi_{1}(3)=\pi_{2}(3)=b_{3}$. Let both the agents have equal entitlements:
$\mathcal{F}=\\{0.5,0.5\\}$.

From the characterization of WSD-PROP1 allocations, we know that a WSD-PROP1
allocation must satisfy conditions 1 and 2 of Lemma 3.1. Applying condition 1,
we see that no agent should receive more than two chores. That is, each agent
must receive at least one chore in any WSD-PROP1 allocation. Suppose _w.l.o.g_
agent $a_{1}$ receives chore $b_{3}$. We then set $v_{1}=(1,1,1)$. Agent
$a_{2}$ must receive at least one of $b_{1},b_{2}$. Suppose _w.l.o.g_ agent
$a_{2}$ receives $b_{2}$, we then set $v_{2}=(1,1,\epsilon)$ where
$\epsilon<1$. The chore $b_{1}$ can be assigned to any agent (Refer to Table
2). We see that this WSD-PROP1 allocation cannot be Pareto optimal as trading
the chores $b_{2}$ with $b_{3}$ gives a Pareto improvement. In Appendix
section B.2 we give a similar example for the case of goods.

Furthermore, there exist instances where given the cardinal valuations, there
does not exist a Pareto optimal allocation that is WSD-PROP1 for the
underlying ordinal instance. For example, consider an instance where an agent
$a_{i}$ values more than $\alpha_{i}.m$ many chores at value zero and no other
agent values those chores at value zero. Therefore, under any Pareto optimal
allocation, agent $a_{i}$ gets more than or equal to $\alpha_{i}.m$ many
chores. However, such an allocation cannot be WSD-PROP1 for the underlying
ordinal instance as it violates the Condition 1.

Chores | $b_{1}$ | $b_{2}$ | $b_{3}$
---|---|---|---
Agent $a_{1}$ | $1$ | $1$ | $1$
Agent $a_{2}$ | $1$ | $1$ | $\epsilon$
Table 2. Exchanging $b_{3}$ with $b_{2}$ gives a Pareto dominating allocation.