# Round-Robin Beyond Additive Agents:
Existence and Fairness of Approximate Equilibria††thanks:  This work was
supported by the ERC Advanced Grant 788893 AMDROMA “Algorithmic and Mechanism
Design Research in Online Markets”, the MIUR PRIN project ALGADIMAR
“Algorithms, Games, and Digital Markets”, and the NWO Veni project No.
VI.Veni.192.153.

Georgios Amanatidis  Georgios Birmpas  Philip Lazos  Input Output; London, UK
Stefano Leonardi  Rebecca Reiffenhäuser  Institute for Logic, Language and
Computation
University of Amsterdam; Amsterdam, The Netherlands

###### Abstract

Fair allocation of indivisible goods has attracted extensive attention over
the last two decades, yielding numerous elegant algorithmic results and
producing challenging open questions. The problem becomes much harder in the
presence of _strategic_ agents. Ideally, one would want to design _truthful_
mechanisms that produce allocations with fairness guarantees. However, in the
standard setting without monetary transfers, it is generally impossible to
have truthful mechanisms that provide non-trivial fairness guarantees.
Recently, Amanatidis et al. [5] suggested the study of mechanisms that produce
fair allocations in their equilibria. Specifically, when the agents have
additive valuation functions, the simple Round-Robin algorithm always has pure
Nash equilibria and the corresponding allocations are _envy-free up to one
good_ (EF1) with respect to the agents’ _true valuation functions_. Following
this agenda, we show that this outstanding property of the Round-Robin
mechanism extends much beyond the above default assumption of additivity. In
particular, we prove that for agents with _cancelable_ valuation functions (a
natural class that contains, e.g., additive and budget-additive functions),
this simple mechanism always has equilibria and even its approximate
equilibria correspond to approximately EF1 allocations with respect to the
agents’ true valuation functions. Further, we show that the approximate EF1
fairness of approximate equilibria surprisingly holds for the important class
of _submodular_ valuation functions as well, even though exact equilibria fail
to exist!

##  1 Introduction

Fair division refers to the problem of dividing a set of resources among a
group of agents in a way that every agent feels they have received a “fair”
share. The mathematical study of (a continuous version of) the problem dates
back to the work of Banach, Knaster, and Steinhaus [36], who, in a first
attempt to formalize fairness, introduced the notion of _proportionality_ ,
i.e., each of the $n$ agents receives at least $1/n$-th of the total value
from fer perspective. Since then, different variants of the problem have been
studied in mathematics, economics, political science, and computer science,
and various fairness notions have been defined. The most prominent fairness
notion is _envy-freeness_ [22, 21, 37], where each agent values her set of
resources at least as much as the set of any other agent. When the available
resources are _indivisible_ items, i.e., items that cannot be split among
agents, notions introduced for infinitely divisible resources, like
proportionality and envy-freeness are impossible to satisfy, even
approximately. In the last two decades fair allocation of indivisible items
has attracted extensive attention, especially within the theoretical computer
science community, yielding numerous elegant algorithmic results for various
new fairness notions tailored to this discrete version of the problem, such as
_envy-freeness up to one good_ (EF1) [28, 16], _envy-freeness up to any good_
(EFX) [18], and _maximin share fairness_ (MMS) [16]. We refer the interested
reader to the surveys of Procaccia [34], Bouveret et al. [15], Amanatidis et
al. [6].

In this work, we study the problem of fairly allocating indivisible _goods_ ,
i.e., items of non-negative value, to _strategic_ agents, i.e., agents who
might misreport their private information if they have an incentive to do so.
Incentivising strategic agents to truthfully report their valuations is a
central goal—and often a notorious challenge—in mechanism design, in general.
Specifically in fair division, this seems particularly necessary, since any
fairness guarantee on the outcome of a mechanism typically holds with respect
to its input, namely the _reported_ preferences of the agents rather than
their true, private preferences which they may have chosen not to reveal.
Without truthfulness, fairness guarantees seem to become meaningless.
Unfortunately, when monetary transfers are not allowed, as is the standard
assumption in fair division, such _truthful_ mechanisms fail to exist for any
meaningful notion of fairness, even for simple settings with two agents who
have additive valuation functions [2].

As an alternative, Amanatidis et al. [5] initiated the study of _equilibrium
fairness_ : when a mechanism always exhibits stable (i.e., pure Nash
equilibrium) states, each of which corresponds to a fair allocation with
respect to the _true_ valuation functions, the need for extracting agents’
true preferences is mitigated. Surprisingly, they show that for the standard
case of additive valuation functions, the simple _Round-Robin_ routine is such
a mechanism with respect to EF1 fairness. Round-Robin takes as input an
ordering of the goods for each agent, and then cycles through the agents and
allocates the goods one by one, giving to each agent their most preferred
available good. For agents with additive valuation functions, Round-Robin is
known to produce EF1 allocations (see, e.g., [30]). Note that, without
monetary transfers, what distinguishes a mechanism from an algorithm is that
its input is the, possibly misreported, agents’ preferences.

To further explore the interplay between incentives and fairness, we take a
step back and focus solely on this very simple, yet fundamental, allocation
protocol. It should be noted that the Round-Robin algorithm is one of the very
few fundamental procedures one can encounter throughout the discrete fair
division literature. Its central role is illustrated by various prominent
results, besides producing EF1 allocations: it can be modified to produce
approximate MMS allocations [3], as well as EF1 allocations for _mixed goods
and chores_ (i.e., items with negative value) [9]. It produces _envy-free_
allocations with high probability when the values are drawn from distributions
[29], it is used to produce a “nice” initial allocation as a subroutine in the
state-of-the-art approximation algorithms for _pairwise maximin share fair_
(PMMS) allocations [25] and EFX allocations [4], it has the lowest
communication complexity of any known fair division algorithm, and, most
relevant to this work, it is the _only_ algorithm for producing fair
allocations for more than two agents that, when viewed as a mechanism, is
known to even have equilibria [8].

We investigate the existence and the EF1 guarantees of approximate pure Nash
equilibria of the Round-Robin mechanism beyond additive valuation functions,
i.e., when the goods already assigned to an agent potentially change how they
value the remaining goods. In particular, we are interested in whether
anything can be said about classes that largely generalize additive functions,
like _cancelable_ functions, i.e., functions where the marginal values with
respect to any subset maintain the relative ordering of the goods, and
_submodular_ functions, i.e., functions capturing the notion of diminishing
returns. Although the stability and equilibrium fairness properties of Round-
Robin have been visited before [8, 5], to the best of our knowledge, we are
the first to study the problem for non-additive valuation functions and go
beyond exact pure Nash equilibria. Cancelable functions also generalize
budget-additive, unit-demand, and multiplicative valuation functions [12], and
recently have been of interest in the fair division literature as several
results can be extended to this class [12, 1, 19]. For similar reasons,
cancelable functions seem to be a good pairing with Round-Robin as well, at
least in the algorithmic setting (see, e.g., Proposition 2.5).

Nevertheless, non-additive functions seem to be massively harder to analyze in
our setting and come with various obstacles. First, it is immediately clear
that, even without strategic agents, the input of an ordinal mechanism
implemented as a simultaneous-move one-shot game, like the Round-Robin
mechanism we study here, can no longer capture the complexity of a submodular
function (see also the relevant discussion in Our Contributions). As a result,
translating this sequential assignment to an estimate on the value of each
agent’s _bundle_ of goods, is not obvious. Lastly, and this applies to
cancelable functions as well, assuming equilibria do exist and enough can be
shown about the value of the assigned bundles to establish fairness, there is
no reason to expect that any fairness guarantee will hold with respect to the
true valuation functions, as the agents may misreport their preferences in an
arbitrary fashion.

###  1.1 Contribution and Technical Considerations

We study the well-known Round-Robin mechanism (Mechanism 1) for the problem of
fairly allocating a set of indivisible goods to a set of strategic agents. We
explore the existence of approximate equilibria, along with the fairness
guarantees that the corresponding allocations provide with respect to the
agents’ true valuation functions. Qualitatively, we generalize the surprising
connection between the stable states of this simple mechanism and its fairness
properties to all approximate equilibria equilibria and for valuation
functions as general as subadditive cancelable and submodular. In more detail,
our main contributions can be summarized as follows:

  * •

We show that the natural generalization of the _bluff profile_ of Aziz et al.
[8] is an exact PNE that always corresponds to an EF1 allocation, when agents
have _cancelable_ valuation functions (Theorem 3.2 along with Proposition
2.5). Our proof is simple and intuitive and generalizes the results of Aziz et
al. [8] and Amanatidis et al. [5].

  * •

For agents with submodular valuation functions, we show that there are
instances where no $(3/4+\varepsilon)$-approximate PNE exists (Proposition
3.4), thus creating a separation between the cancelable and the submodular
cases. Nevertheless, we prove that an appropriate generalization of the bluff
profile is a $1/2$-approximate PNE (Theorem 3.7) that also produces an
$1/2$-EF1 allocation with respect to the true valuation functions (Theorem
3.8).

  * •

We provide a unified proof that connects the factor of an approximate PNE with
the fairness approximation factor of the respective allocation. In particular,
any $\alpha$-approximate PNE results in a ${\alpha}/{2}$-EF1 allocation for
subadditive cancelable agents (Theorem 4.5), and in a ${\alpha}/{3}$-EF1
allocation for submodular agents (Theorem 4.4). We complete the picture by
providing lower bounds in both cases (Theorem 4.3 and Proposition 4.8), which
demonstrate that our results are almost tight.

While this is not the first time Round-Robin is considered for non-additive
agents, see, e.g., [13], to the best of our knowledge, we are the first to
study its fairness guarantees for cancelable and submodular valuation
functions, independently of incentives. As a minor byproduct of our work,
Theorem 3.8 and the definition of the bluff profile imply that, given _value
oracles_ for the submodular functions, we can use Round-Robin as a subroutine
to produce ${1}/{2}$-EF1 allocations.

This also raises the question of whether one should allow a more expressive
bid, e.g., a value oracle. While, of course, this is a viable direction, we
avoid it here as it comes with a number of issues. Allowing the input to be
exponential in the number of goods is already problematic, especially when
simplicity and low communication complexity are two appealing traits of the
original mechanism. Moreover, extracting orderings from value oracles would
essentially result in a mechanism equivalent to ours (if the ordering of an
agent depended only on _her_ function) or to a sequential game (if the
orderings depended on all the functions) which is not what we want to explore
here. Note that less information is not necessarily an advantage towards our
goal. While this results in a richer space of equilibria, fairness guarantees
are increasingly harder to achieve.

As a final remark, all the algorithmic procedures we consider run in
polynomial time, occasionally assuming access to value oracles, e.g.,
Algorithms 2, 3, 4. Although we do not consider computational complexity
questions here, like how do agents compute best responses or how do they reach
approximate equilibria, we do consider such questions interesting directions
for future work.

###  1.2 Further Related Work

The problem of fairly allocating indivisible goods to additive agents in the
non-strategic setting has been extensively studied; for a recent survey, see
Amanatidis et al. [6]. Although the additivity of the valuation functions is
considered a standard assumption, there are many works that explore richer
classes of valuation functions. Some prominent examples include the
computation of EF1 allocations for agents with general non-decreasing
valuation functions [28], EFX allocations (or relaxations of EFX) under agents
with cancelable valuation functions [12, 1, 19] and subaditive valuation
functions [33, 20], respectively, and approximate MMS allocations for
submodular, XOS, and subadditive agents [11, 23].

Moving to the strategic setting, Caragiannis et al. [17] and Markakis and
Psomas [31] were the first to consider the question of whether it is possible
to have mechanisms that are truthful and fair at the same time, again assuming
additive agents. Amanatidis et al. [2] resolved this question for two agents,
showing there is no truthful mechanism with fairness guarantees under any
meaningful fairness notion. As a result, subsequent papers considered truthful
mechanism design under restricted valuation function classes [24, 10].

The stability of Round-Robin was first studied by Aziz et al. [8], who proved
that it always has PNE by using a special case of retracted result of Bouveret
and Lang [13] (this did not affect the former though; see [7]). Finally,
besides the work of Amanatidis et al. [5] mentioned earlier, the fairness
properties of Round-Robin under strategic agents have recently been studied by
Psomas and Verma [35]. Therein it is shown that Round-Robin, despite being
non-truthful, satisfies a relaxation of truthfulness, as it is _not obviously
manipulable_.

##  2 Preliminaries

For $a\in\mathbb{N}$, let $[a]$ denote the set $\\{1,2,\ldots,a\\}$. We will
use $N=[n]$ to denote the set of agents and $M=\\{g_{1},\ldots,g_{m}\\}$ to
denote the set of goods. Each agent $i\in N$ has a valuation function
$v_{i}:2^{M}\to\mathbb{R}_{\geq 0}$ over the subsets of goods. We assume that
all $v_{i}$ are _normalized_ , i.e., $v_{i}(\emptyset)=0$. We also adopt the
shortcut $v_{i}(T\,|\,S)$ for the _marginal value_ of a set $T$ with respect
to a set $S$, i.e., $v_{i}(T\,|\,S)=v_{i}(T\cup S)-v(S)$. If $T=\\{g\\}$, we
write $v_{i}(g\,|\,S)$ instead of $v(\\{g\\}\,|\,S)$. For each agent $i\in N$,
we say that $v_{i}$ is

  * •

_non-decreasing_ (often referred to as _monotone_), if $v_{i}(S)\leq v_{i}(T)$
for any $S\subseteq T\subseteq M$.

  * •

_submodular_ , if $v_{i}(g\,|\,S)\geq v_{i}(g\,|\,T)$ for any $S\subseteq
T\subseteq M$ and $g\notin T$.

  * •

_cancelable_ , if $v_{i}(S\cup\\{g\\})>v_{i}(T\cup\\{g\\})\Rightarrow
v_{i}(S)>v_{i}(T)$ for any $S,T\subseteq M$ and $g\in M\setminus(S\cup T)$.

  * •

_additive_ , if $v_{i}(S\cup T)=v_{i}(S)+v_{i}(T)$ for every $S,T\subseteq M$
with $S\cap T=\emptyset$.

  * •

_subadditive_ , if $v_{i}(S\cup T)\leq v_{i}(S)+v_{i}(T)$ for every
$S,T\subseteq M$.

Throughout this work, we only consider non-decreasing valuation functions,
e.g., when we refer to submodular functions, we mean non-decreasing submodular
functions. Note that although both submodular and (subadditive) cancelable
functions are strict superclasses of additive functions, neither one is a
superclass of the other.

We will occasionally need an alternative characterization of submodular
functions due to Nemhauser et al. [32].

######  Theorem 2.1 (Nemhauser et al. [32]).

A function $v:2^{M}\rightarrow\mathbb{R}_{\geq 0}$ is (non-decreasing)
submodular if and only if we have $v(T)\leq v(S)+\sum_{i\in T\setminus
S}v(i\,|\,S)$, for all $S,T\subseteq M$.

Also, the following lemma summarizes some easy observations about cancelable
functions.

######  Lemma 2.2.

If $v:2^{M}\rightarrow\mathbb{R}_{\geq 0}$ is cancelable, then $v_{i}(S\cup
R)>v_{i}(T\cup R)\Rightarrow v_{i}(S)>v_{i}(T)$, implying that $v_{i}(S)\geq
v_{i}(T)\Rightarrow v_{i}(S\cup R)\geq v_{i}(T\cup R)$, for any
$S,T,R\subseteq M$, such that $R\subseteq M\setminus S\cup T$. In particular,
$v_{i}(S)=v_{i}(T)\Rightarrow v_{i}(S\cup R)=v_{i}(T\cup R)$.

Note that, for $S,T\subseteq M$, Lemma 2.2 directly implies that
$\operatorname*{arg\,max}_{g\in T}v(g)\subseteq\operatorname*{arg\,max}_{g\in
T}v(g\,|\,S)$.

Despite the fact that the agents have valuation functions, the mechanism we
study (Mechanism 1) is _ordinal_ , i.e., it only takes as input a _preference
ranking_ from each agent. Formally, the preference ranking $\succ_{i}$, which
agent $i$ reports, defines a total order on $M$, i.e., $g\succ_{i}g^{\prime}$
implies that good $g$ precedes good $g^{\prime}$ in agent $i$’ declared
preference ranking.111See the discussion after the statement of Mechanism 1
about why assuming that the reported preference rankings are total (rather
than partial) orders is without loss of generality. We call the vector of the
agents’ declared preference rankings,
$\bm{\succ}\,=(\succ_{1},\ldots,\succ_{n})$, the _reported profile_ for the
instance. So, while an instance to our problem is an ordered triple
$(N,M,\mathbf{v})$, where $\mathbf{v}=(v_{1},\ldots,v_{n})$ is a vector of the
agents’ valuation functions, the input to Mechanism 1 is $(N,M,\bm{\succ})$
instead.

Note that $\succ_{i}$ may not reflect the actual underlying values, i.e.,
$g\succ_{i}g^{\prime}$ does not necessarily mean that
$v_{i}(g)>v_{i}(g^{\prime})$ or, more generally,
$v_{i}(g\,|\,S)>v_{i}(g^{\prime}\,|\,S)$ for a given $S\subseteq M$. This
might be due to agent $i$ misreporting her preference ranking, or due to the
fact that any single preference ranking is not expressive enough to fully
capture all the partial orders induced by a submodular function. Nevertheless,
a valuation function $v_{i}$ does induce a _true preference ranking_
$\succcurlyeq^{*}_{i|S}$ for each set $S\subseteq M$, which is a partial
order, i.e., $g\succcurlyeq^{*}_{i|S}g^{\prime}\Leftrightarrow
v_{i}(g\,|\,S)\geq v_{i}(g^{\prime}\,|\,S)$ for all $g,g^{\prime}\in M$. We
use $\succ^{*}_{i|S}$ if the corresponding preference ranking is _strict_ ,
i.e., when
$g\succcurlyeq^{*}_{i|S}g^{\prime}\,\wedge\,g^{\prime}\succcurlyeq^{*}_{i|S}g\,\Rightarrow\,g=g^{\prime}$,
for all $g,g^{\prime}\in M\setminus S$. For additive (and more generally, for
cancelable) valuations, we drop $S$ for the notation and simply write
$\succcurlyeq^{*}_{i}$ or $\succ^{*}_{i}$. Finally, for a total order $\succ$
on $M$ and a set $T\subseteq M$, we use $\mathrm{top}(\succ,T)$ to denote the
“largest” element of $T$ with respect to $\succ$.

###  2.1 Fairness Notions

A fair division mechanism produces an _allocation_ $(A_{1},\ldots,A_{n})$,
where $A_{i}$ is the _bundle_ of agent $i$, which is a partition of $M$. The
latter corresponds to assuming no free disposal, namely all the goods must be
allocated.

There are several different notions which attempt to capture which allocations
are “fair”. The most prominent such notion in the fair division literature has
been _envy-freeness_ (EF) [22, 21, 37], which has been the starting point for
other relaxed notions, more appropriate for the indivisible goods setting we
study here, as _envy-freeness up to one good_ (EF1) [28, 16] and _envy-
freeness up to any good_ (EFX) [18]. Here we focus on EF1.

######  Definition 2.3.

An allocation $(A_{1},\ldots,A_{n})$ is

  * •

$\alpha$-envy-free ($\alpha$-EF), if for every $i,j\in N$,
$v_{i}(A_{i})\geq\alpha\cdot v_{i}(A_{j})$.

  * •

$\alpha$-envy-free up to one good ($\alpha$-EF1), if for every pair of agents
$i,j\in N$, with $A_{j}\neq\emptyset$, there exists a good $g\in A_{j}$, such
that $v_{i}(A_{i})\geq\alpha\cdot v_{i}(A_{j}\setminus\\{g\\})$.

When for every agent $j\in N$ with $A_{j}\neq\emptyset$, we have
$v_{i}(A_{i})\geq\alpha\cdot v_{i}(A_{j}\setminus\\{g\\})$ for some good $g\in
A_{j}$, we say that $(A_{1},\ldots,A_{n})$ is $\alpha$-EF1 _from agent $i$’s
perspective_, even when the allocation is not $\alpha$-EF1!

###  2.2 Mechanisms and Equilibria

We are interested in _mechanisms_ that produce allocations with EF1
guarantees. When no payments are allowed, like in our setting, an allocation
mechanism $\mathcal{M}$ is just an allocation algorithm that takes as input
the agents’ reported preferences. In particular, Round-Robin, the mechanism of
interest here, takes as input the reported profile $\bm{\succ}$ and produces
an allocation of all the goods. This distinction in terminology is necessary
as the reported input may not be consistent with the actual valuation
functions due to the agents’ incentives. When the allocation returned by
$\mathcal{M}(\bm{\succ})$ has some fairness guarantee, e.g., it is $0.5$-EF1,
we will attribute the same guarantee to the reported profile itself, i.e., we
will say that $\bm{\succ}$ is $0.5$-EF1.

We study the fairness guarantees of the (approximate) pure Nash equilibria of
Round-Robin. Given a preference profile
$\bm{\succ}\,=({\succ}_{1},\ldots,{\succ}_{n})$, we write $\bm{\succ}_{-i}$ to
denote
$({\succ}_{1},\ldots,{\succ}_{i-1},\allowbreak{\succ}_{i+1},\ldots,{\succ}_{n})$
and given a preference ranking ${\succ}^{\prime}_{i}$ we use
$({\succ}^{\prime}_{i},\bm{\succ}_{-i})$ to denote the profile
$({\succ}_{1},\ldots,{\succ}_{i-1},\allowbreak{\succ}^{\prime}_{i},\allowbreak{\succ}_{i+1},\ldots,{\succ}_{n})$.
For the next definition we abuse the notation slightly: given an allocation
$(A_{1},\ldots,\allowbreak A_{n})$ produced by $\mathcal{M}(\bm{\succ})$, we
write $v_{i}(\mathcal{M}(\bm{\succ}))$ to denote $v_{i}({A}_{i})$; similarly
for $\mathcal{M}({\succ}^{\prime}_{i},\bm{\succ}_{-i})$.

######  Definition 2.4.

Let $\mathcal{M}$ be an allocation mechanism and consider a preference profile
$\bm{\succ}\,=({\succ}_{1},\ldots,\allowbreak{\succ}_{n})$. We say that the
total order ${\succ}_{i}$ is an _$\alpha$ -approximate best response_ to
$\bm{\succ}_{-i}$ if for every total order, i.e., permutation
${\succ}^{\prime}_{i}$ of $M$, we have $\alpha\cdot
v_{i}(\mathcal{M}({\succ}^{\prime}_{i},\bm{\succ}_{-i}))\leq
v_{i}(\mathcal{M}(\bm{\succ}))$. The profile $\bm{\succ}$ is an _$\alpha$
-approximate pure Nash equilibrium_ (PNE) if, for each $i\in N$, ${\succ}_{i}$
is an $\alpha$-approximate best response to $\bm{\succ}_{-i}$.

When $\alpha=1$, we simply refer to best responses and exact PNE.

###  2.3 The Round-Robin Mechanism

We state Round-Robin as a mechanism (Mechanism 1) that takes as input a
reported profile $({\succ}_{1},\ldots,{\succ}_{n})$. For the sake of
presentation, we assume that the agents in each _round_ (lines 3–6) are always
considered according to their “name”, i.e., agent $1$ is considered first,
agent $2$ second, and so on, instead of having a permutation determining the
priority of the agents as an extra argument of the input. This is without loss
of generality, as it only requires renaming the agents accordingly. We often
refer to the process of allocating a good to an agent (lines 4–6) as a _step_
of the mechanism.

Mechanism 1 Round-Robin$({\succ}_{1},\ldots,{\succ}_{n})$ // For $i\in N$,
${\succ}_{i}$ is the reported preference ranking of agent $i$.

1:$S=M$; $(A_{1},\dots,A_{n})=(\emptyset,\ldots,\emptyset)$; $k=\lceil
m/n\rceil$

2:for $r=1,\dots,k$ do // Each value of $r$ determines the corresponding
round.

3: for $i=1,\dots,n$ do // The combination of $r$ and $i$ determines the
corresponding step.

4: $g=\mathrm{top}(\succ_{i},S)$

5: $A_{i}=A_{i}\cup\\{g\\}$ // The current agent receives (what appears to be)
her favorite available good.

6: $S=S\setminus\\{g\\}$ // The good is no longer available.

7:return $(A_{1},\dots,A_{n})$

Note that there is no need for a tie-breaking rule here, as the reported
preference rankings are assumed to be total orders. Equivalently, one could
allow for partial orders (either directly or via cardinal bids as it is done
in [5]) paired with a deterministic tie-breaking rule, e.g., lexicographic
tie-breaking, a priori known to the agents.

In the rest of the paper, we will assume that $m=kn$ for some
$k\in\mathbb{N}$, for simplicity. Note that this is without loss of
generality, as we may introduce at most $n-1$ dummy goods that have marginal
value of $0$ with respect to any set for everyone and append them at the end
of the reported preference rankings to be allocated during the last steps of
the mechanism.

We have already mentioned that Round-Robin as an algorithm produces EF1
allocations for additive agents, where the input is assumed to be any strict
variant
$\bm{\succ}^{*}\,=(\succ^{*}_{1|\emptyset},\succ^{*}_{2|\emptyset},\ldots,\succ^{*}_{n|\emptyset})$
of the truthful profile
$(\succcurlyeq^{*}_{1|\emptyset},\succcurlyeq^{*}_{2|\emptyset},\ldots,\succcurlyeq^{*}_{n|\emptyset})$,
i.e., the profile where each agent ranks the goods according to their
singleton value. This property fully extends to cancelable valuation functions
as well. The proof of Proposition 2.5 is rather simple, but not as
straightforward as the additive case; note that it requires Lemma 3.3 from the
next section.

######  Proposition 2.5.

Let be $\bm{\succ}^{*}$ be as described above. When all agents have cancelable
valuation functions, the allocation returned by Round-Robin$(\bm{\succ}^{*})$
is EF1.

###### Proof.

Let $(A_{1},\dots,A_{n})$ be the allocation returned by Round-
Robin$(\bm{\succ}^{*})$. Fix two agents, $i$ and $j$, and let
$A_{i}=\\{x_{1},x_{2},\ldots,x_{k}\\}$ and
$A_{j}=\\{y_{1},y_{2},\ldots,y_{k}\\}$, where the goods in both sets are
indexed according to the round in which they were allocated to $i$ and $j$,
respectively. By the way Mechanism 1 is defined, we have
$x_{r}\succ^{*}_{i|\emptyset}y_{r+1}$, for all $r\in[k-1]$. Therefore,
$x_{r}\succcurlyeq^{*}_{i|\emptyset}y_{r+1}$, or equivalently,
$v_{i}(x_{r})\geq v_{i}(y_{r+1})$, for all $r\in[k-1]$. Thus, by Lemma 3.3, we
get $v_{i}(A_{i}\setminus\\{x_{k}\\})\geq v_{i}(A_{j}\setminus\\{y_{1}\\})$,
and using the fact that $v_{i}$ is non-decreasing, $v_{i}(A_{i})\geq
v_{i}(A_{j}\setminus\\{y_{1}\\})$. ∎

##  3 Existence of approximate PNE

At first glance, it is not clear why Mechanism 1 has any pure Nash equilibria,
even approximate ones for a constant approximation factor. For additive
valuation functions, however, it is known that for any instance we can
construct a simple preference profile, called the _bluff profile_ , which is
an exact PNE. While the proof of this fact, in its full generality, is
fragmented over three papers [8, 14, 5], we give here a simple proof that
generalizes the existence of exact PNE to cancelable valuation functions. As
we shall see later, extending this result to submodular functions is not
possible and even defining a generalization of the bluff profile which is a
$0.5$-approximate PNE is not straightforward.

###  3.1 Cancelable valuations

Defining the bluff profile for cancelable agents, we will start from a strict
variant of the truthful profile
$(\succcurlyeq^{*}_{1|\emptyset},\succcurlyeq^{*}_{2|\emptyset},\ldots,\succcurlyeq^{*}_{n|\emptyset})$,
i.e., the profile where each agent ranks the goods according to their value
(as singletons) in descending order, as we did for Proposition 2.5. Assume
that any ties are broken deterministically to get the strict version
$\bm{\succ}^{*}\,=(\succ^{*}_{1|\emptyset},\succ^{*}_{2|\emptyset},\ldots,\succ^{*}_{n|\emptyset})$.
Now, consider $\textrm{Round-Robin}(\bm{\succ}^{*})$ and let
$h_{1},h_{2},\ldots,h_{m}$ be a renaming of the goods according to the order
in which they were allocated and $\succ^{\mathrm{b}}$ be the corresponding
total order (i.e.,
$h_{1}\succ^{\mathrm{b}}h_{2}\succ^{\mathrm{b}}\ldots\succ^{\mathrm{b}}h_{m}$).
The _bluff profile_ is the preference profile
$\bm{\succ}^{\mathrm{b}}\,=(\succ^{\mathrm{b}},\succ^{\mathrm{b}},\ldots,\succ^{\mathrm{b}})$,
where everyone ranks the goods in the order they were allocated in Round-
Robin$(\bm{\succ}^{*})$. The following fact follows directly from the
definition of the bluff profile and the description of Round-Robin.

######  Fact 3.1.

If $(\bm{\succ}^{*})$ is a strict version of the truthful preference profile
and $(\bm{\succ}^{\mathrm{b}})$ is the corresponding bluff profile, then
$\mathrm{Round\text{-}Robin}(\bm{\succ}^{\mathrm{b}})$ and
$\mathrm{Round\text{-}Robin}(\bm{\succ}^{*})$ both return the same allocation.

An interesting observation about this fact is that, combined with Proposition
2.5 and Theorem 3.2, it implies that there is at least one PNE of Mechanism 1
which is EF1! Of course, it is now known that all exact PNE of Round-Robin are
EF1 for agents with _additive_ valuation functions and, as we will see later
on, even approximate PNE have (approximate) EF1 guarantees for much more
general instances, including the case of _subadditive cancelable_ valuation
functions.

######  Theorem 3.2.

When all agents have cancelable valuation functions, the bluff profile is an
exact PNE of Mechanism 1.

We first need to prove the following lemma that generalizes a straightforward
property of additive functions for cancelable functions.

######  Lemma 3.3.

Suppose that $v(\cdot)$ is a cancelable valuation function. Consider sets
$X=\\{x_{1},x_{2},\ldots,x_{k}\\}$ and $Y=\\{y_{1},y_{2},\ldots,y_{k}\\}$. If
for every $j\in[k]$, we have that $v(x_{j})\geq v(y_{j})$, then $v(X)\geq
v(Y)$.

###### Proof.

We begin by arguing that it is without loss of generality to first assume that
the elements of $X$ are ordered by non-increasing value with respect to $v$
and then also assume that $y_{j}\notin\\{x_{1},x_{2},\ldots,x_{j-1}\\}$, for
any $j\in[k]$. The former is indeed a matter of reindexing, if necessary, the
elements of $X$ and consistently reindexing the corresponding elements of $Y$.
For the latter, suppose that there exist $j$ such that $y_{j}=x_{t}$ for
$t\leq j-1$ and consider the smallest $t$ for which this happens. We have
$v(x_{t})\geq v(x_{t+1})\geq\ldots\geq v(x_{j})$ by the assumption on the
ordering of the elements of $X$, $v(x_{j})\geq v(y_{j})$ by hypothesis, and
$v(y_{j})=v(x_{t})$. Thus, $v(x_{t})=v(x_{t+1})=\ldots=v(x_{j})$. Now we may
rename the elements of $Y$ to $\\{y^{\prime}_{1},\ldots,y^{\prime}_{k}\\}$ by
inserting $y_{j}$ to the $t$-th position, i.e., $y^{\prime}_{t}=y_{j}$,
$y^{\prime}_{s}=y_{s-1}$, for $t+1\leq s\leq j$, and $y^{\prime}_{s}=y_{s}$,
for $s<t$ or $s>j$. Since only $y_{t},y_{t+1},\ldots,y_{j}$ changed indices
but $v(x_{t})=v(x_{t+1})=\ldots=v(x_{j})$, we again have that $v(x_{j})\geq
v(y^{\prime}_{j})$ for every $j\in[k]$. Moreover, now the smallest $\ell$ for
which there exist $j>\ell$ such that $y_{j}=x_{\ell}$ is strictly larger than
$t$. By repeating this renaming of the elements of $Y$ we end up with a
renaming $\\{y^{*}_{1},\ldots,y^{*}_{k}\\}$ such that for every $j\in[k]$,
$v(x_{j})\geq v(y^{*}_{j})$ and
$y^{*}_{j}\notin\\{x_{1},x_{2},\ldots,x_{j-1}\\}$.

So, assuming that the elements of $X$ are ordered in non-increasing value with
respect to $v$ and that $y_{j}\notin\\{x_{1},x_{2},\ldots,x_{j-1}\\}$, for any
$j\in[k]$, suppose towards a contradiction that $v(X)<v(Y)$. That is,
$v(\\{x_{1},x_{2},\ldots,x_{k}\\})\allowbreak<v(\\{y_{1},y_{2},\allowbreak\ldots,y_{k}\\})$.
Observe that if $v(\\{x_{1},x_{2},\ldots,x_{k-1}\\})\geq
v(\\{y_{1},y_{2},\ldots,y_{k-1}\\})$, this would imply that
$v(\\{x_{1},\ldots,x_{k-1},y_{k}\\})\geq v(\\{y_{1},\ldots,y_{k-1},y_{k}\\})$,
by the definition of cancelable valuations and the fact that
$y_{k}\notin\\{x_{1},\ldots,x_{k-1}\\}\cup\\{y_{1},\ldots,y_{k-1}\\}$. This
leads to

$v(\\{x_{1},\ldots,x_{k-1},x_{k}\\})\geq
v(\\{x_{1},\ldots,x_{k-1},y_{k}\\})\geq v(\\{y_{1},\ldots,y_{k-1},\allowbreak
y_{k}\\})\,,$

where the first inequality follows from $v(x_{k})\geq v(y_{k})$ and Fact 2.2,
contradicting our initial assumption. Therefore,
$v(\\{x_{1},\ldots,x_{k-1}\\})<v(\\{y_{1},\ldots,y_{k-1}\\})$. By repeating
the same argument $k-2$ more times, we end up with $v(x_{1})<v(y_{1})$, a
contradiction. ∎

###### Proof of Theorem 3.2.

Now we show that the bluff profile for cancelable valuations is an exact PNE.
Consider the goods named $h_{1},\dots,h_{m}$ as in the bluff profile, i.e., by
the order in which they are picked when each agent reports their preference
order to be the one induced by all singleton good values. Consider agent $i$.
Her assigned set of goods under the bluff profile is
$A_{i}^{\mathrm{b}}=\\{h_{i},h_{n+i},\dots,h_{(k-1)n+i}\\}$, where $k=m/n$.
Assume now that she deviates from $\succ^{\mathrm{b}}$ to $\succ_{i}$,
resulting in some allocated set $A_{i}=\\{y_{1},y_{2},\dots,y_{k}\\}$, where
we assume $y_{r}$ to be allocated in round $r$. We need to show
$v_{i}(A_{i}^{\mathrm{b}})\geq v_{i}(A_{i})$.

To this end, we compare the goods allocated to agent $i$ in both reports, one
by one. If $v_{i}(y_{r})\leq v_{i}(h_{(r-1)n+i})$ for every $r\in[k]$, then we
are done by applying Lemma 3.3 with $A_{i}^{\mathrm{b}}$ and $A_{i}$. If some
of these inequalities fail, let $r$ denote the latest round such that
$v_{i}(y_{r})>v_{i}(h_{(r-1)n+i}$. Therefore, in the execution of Mechanism 1
with the bluff profile as input, $y_{r}$ was no longer available in round $r$.
However, $y_{r}$ becomes available in round $r$ once agent $i$ deviates. This
can only stem from the fact that at some point before round $r$, a good
$h_{t}$ with $t>(r-1)n+i$ was picked (since the overall number of goods picked
per round always stays the same). Clearly, the only agent who could have done
so (since she is the only one deviating from the common bluff order) is agent
$i$. Therefore, it holds that $h_{t}=y_{j}$ for some $j<r$. Now, we replace
the ordered set $Y=(y_{1},y_{2},\dots,y_{k})$ by
$Y^{\prime}=(y_{1},\dots,y_{j-1},y_{r},y_{j+1},\dots,y_{r-1},y_{j},y_{r+1},\dots,y_{k})$,
i.e., we simply exchange $y_{r}$ and $y_{j}$. It will be convenient to rename
$y_{1},\ldots,y_{k}$ so that
$Y^{\prime}=(y^{\prime}_{1},y^{\prime}_{2},\dots,y^{\prime}_{k})$

We claim that it if agent $i$ reports a preference ranking
$\succ^{\prime}_{i}$ that starts with all goods in $Y^{\prime}$, in that
specific order, followed by everything else, in any order, she still gets
$A_{i}$ but the goods are allocated in the order suggested by $Y^{\prime}$.
Indeed, first notice that the first $j-1$ rounds of Round-Robin will be the
same as in the run with the original deviation $\succ_{i}$. Further,
$y^{\prime}_{j}=y_{r}$ is allocated earlier under $\succ^{\prime}_{i}$ than
under $\succ_{i}$, and thus it surely is available at the time. After that,
rounds $j-1$ to $r-1$ will be the same as in the run with the deviation
$\succ_{i}$. Now $y^{\prime}_{r}=y_{j}$ is allocated later than before, namely
in round $r$, but it is not among the first $(r-1)n+i$ goods in the bluff
order, as noted above, which means it is not allocated to any other agent in
any round before the $r$-th under $\succ^{\prime}_{i}$. Finally, rounds $r+1$
to $k$ will be the same as in the run with $\succ_{i}$.

Although agent $i$ still is assigned the same set $A_{i}$ by deviating to
$\succ^{\prime}_{i}$, we now have $v_{i}(y^{\prime}_{r})=v_{i}(y_{j})\leq
v_{i}(h_{(r-1)n+i}$, where the inequality holds because both goods are
available in round $r$ of the bluff run, and agent one prefers $h_{(r-1)n+i}$.
Also, all later goods in $Y^{\prime}$ remain unchanged, i.e.,
$y^{\prime}_{s}=y_{s}$ for $s>r$. Therefore, the latest occurrence of some
$y^{\prime}_{\ell}>h_{(\ell-1)n+i}$ now happens at an earlier point in the
sequence, if at all. Repeating this process until no such occurrence is left
yields an ordering $Y^{*}=(y^{*}_{1},y^{*}_{2},\dots,y^{*}_{k})$ of $A_{i}$
such that for all $r\in[k]$, $v_{i}(y^{*}_{r})\leq v_{i}(h_{(r-1)n+i})$. Now
using Lemma 3.3 completes the proof. ∎

###  3.2 Submodular valuations

We move on to the much more general class of submodular valuations. In order
to define the bluff profile in this case, we again would like to start from
the truthful profile. However, recall that Round-Robin restricts each agent’s
report to specifying an ordering on the good set $M$ and these preference
rankings are not expressive enough to fully capture submodular valuation
functions. In fact, it is not obvious what ‘truthful’ means here without
further assumptions on what information is known by the agents. Still, we
define a truthfully greedy allocation and use this as our starting point.

Imagine that, instead of having a full preference profile from the beginning,
we only ask the active agent $i$ (i.e., the agent to which we are about to
allocate a new good) for the good with the largest marginal value with respect
to her current set of goods $A_{i}$ and give this to her. Let
$h_{1},h_{2},\ldots,h_{m}$ be a renaming of the goods according to the order
in which they would be allocated in this hypothetical truthfully greedy
scenario and $\succ^{\mathrm{b}}$ be the corresponding total order. Like in
the cancelable case, the bluff profile is the preference profile
$\bm{\succ}^{\mathrm{b}}\,=(\succ^{\mathrm{b}},\succ^{\mathrm{b}},\ldots,\succ^{\mathrm{b}})$.

Formally, the renaming of the goods is performed as described in Algorithm 2
below. It should be noted that this definition of the bluff profile is
consistent with the definition for cancelable functions, assuming that all
ties are resolved lexicographically.

Algorithm 2 Greedy renaming of goods for defining the bluff profile
Input: $N$, $M$, value oracles for $v_{1}(\cdot),\ldots,v_{n}(\cdot)$

1:$X_{i}=\emptyset$ for $i\in[n]$

2:for $j=1,\dots,m$ do

3: $i=(j-1)\\!\pmod{n}+1$

4: $h_{j}=\displaystyle\operatorname*{arg\,max}_{g\in
M\setminus\bigcup_{\ell}X_{\ell}}v_{i}(g\,|\,X_{i})$ // Ties are broken
lexicographically.

5: $X_{i}=X_{i}\cup\\{h_{j}\\}$

6:return $(h_{1},h_{2},\ldots,h_{m})$

Also notice that the allocation
$\mathrm{Round\text{-}Robin}(\bm{\succ}^{\mathrm{b}})$ produced under the
bluff profile is exactly $(X_{1},X_{2},\allowbreak\ldots,\allowbreak X_{n})$,
as described in Algorithm 2, i.e.,
$X_{i}=A_{i}^{\mathrm{b}}=\\{h_{i},h_{n+i},\dots,h_{(k-1)n+i}\\}$, where
recall that $k=m/n$.

The main result of this section is Theorem 3.7 stating that the bluff profile
is a $\frac{1}{2}$-approximate PNE when agents have submodular valuation
functions. While this sounds weaker than Theorem 3.2, it should be noted that
for submodular agents Mechanism 1 does not have PNE in general, even for
relatively simple instances, as stated in Proposition 3.4. In fact, even the
existence of approximate equilibria can be seen as rather surprising, given
the generality of the underlying valuation functions.

######  Proposition 3.4.

There exists an instance where all agents have submodular valuation functions
such that Mechanism 1 has no $(\frac{3}{4}+\varepsilon)$-approximate PNE.

###### Proof.

Consider an instance with 2 agents and 4 goods
$M=\\{g_{1},g_{2},g_{3},g_{4}\\}$, with the following valuation for all
possible 2-sets:

$v_{1}(\\{g_{1},g_{2}\\})=3$ $v_{1}(\\{g_{1},g_{3}\\})=3$
$v_{1}(\\{g_{1},g_{4}\\})=4$ $v_{1}(\\{g_{2},g_{3}\\})=4$
$v_{1}(\\{g_{2},g_{4}\\})=3$ $v_{1}(\\{g_{3},g_{4}\\})=3$

$v_{2}(\\{g_{1},g_{2}\\})=4$ $v_{2}(\\{g_{1},g_{3}\\})=4$
$v_{2}(\\{g_{1},g_{4}\\})=3$ $v_{2}(\\{g_{2},g_{3}\\})=3$
$v_{2}(\\{g_{2},g_{4}\\})=4$ $v_{2}(\\{g_{3},g_{4}\\})=4$

In addition, all individual goods have the same value: $v_{1}(x)=v_{2}(x)=2$
for $x\in M$, while all $3$-sets and $4$-sets have value $4$, for both agents.

We begin by establishing that this valuation function is indeed submodular for
both agents. Observe for any set $S\subseteq M$ and $i\in[2],j\in[4]$ we have:

$\displaystyle|S|=0$ $\displaystyle\Rightarrow v_{i}(g_{j}\;|\;S)\in\\{2\\}$
$\displaystyle|S|=1$ $\displaystyle\Rightarrow v_{i}(g_{j}\;|\;S)\in\\{1,2\\}$
$\displaystyle|S|=2$ $\displaystyle\Rightarrow v_{i}(g_{j}\;|\;S)\in\\{0,1\\}$
$\displaystyle|S|=3$ $\displaystyle\Rightarrow v_{i}(g_{j}\;|\;S)=0\,,$

which immediately implies that both valuation functions are indeed submodular.

Notice that for any reported preferences ${\succ}_{1},{\succ}_{2}$, one of the
two agents will receive goods leading to a value of $3$. If this is the agent
$1$, she can easily deviate and get $4$ instead. In particular, if agent $2$
has good $g_{2}$ or $g_{3}$ first in their preferences then agent $1$ can get
$\\{g_{1},g_{4}\\}$, and if agent $2$ has good $g_{1}$ or $g_{4}$ as first
then agent $1$ can get $\\{g_{2},g_{3}\\}$ instead. On the other hand, if
agent $2$ received a value of $3$ they can also always deviate to $4$. Notice
that for any $g_{a}$, agent $2$ always has two sets different sets
$\\{g_{a},g_{b}\\},\\{g_{a},g_{c}\\}$ with value $4$ and one
$\\{g_{a},g_{d}\\}$ with value 3. Thus, for any preference of agent $1$ with
$g_{\hat{a}}\succ_{1}g_{\hat{b}}\succ_{1}g_{\hat{c}}\succ_{1}g_{\hat{d}}$,
agent 2 can deviate and get either $\\{g_{\hat{b}},g_{\hat{d}}\\}$ or
$\\{g_{\hat{c}},g_{\hat{d}}\\}$, one of which must have value $4$. Therefore,
in every outcome there exists an agent that can deviate to improve their value
from $3$ to $4$. ∎

Moving towards the proof of Theorem 3.7 for the submodular case, we note that
although it is very different from that of Theorem 3.2, we will still need an
analog of the main property therein, i.e., the existence of a good-wise
comparison between the goods an agent gets under the bluff profile and the
ones she gets by deviating. As expected, the corresponding property here (see
Lemma 3.5) is more nuanced and does not immediately imply Theorem 3.7 as we
are now missing the analog of Lemma 3.3.

Throughout this section, we are going to argue about an arbitrary agent $i$.
To simplify the notation, let us rename
$X_{i}=A_{i}^{\mathrm{b}}=\\{h_{i},h_{n+i},\dots,h_{(k-1)n+i}\\}$ to simply
$X=\\{x_{1},x_{2},\ldots,x_{k}\\}$, where we have kept the order of indices
the same, i.e., $x_{j}=h_{(j-1)n+i}$. This way, the goods in $X$ are ordered
according to how they were allocated to agent $i$ in the run of Mechanism 1
with the bluff profile as input.

We also need to define the ordering of the goods agent $i$ gets when she
deviates from the bluff bid $\succ^{\mathrm{b}}$ to another preference ranking
$\succ_{i}$. Let $A_{i}=Y=\\{y_{1},y_{2},\ldots,y_{k}\\}$ be this set of
goods. Instead of renaming the elements of $Y$ in a generic fashion like in
the proof of Theorem 3.2, doing so becomes significantly more complicated, and
we need to do it in a more systematic way, see Algorithm 3.

Algorithm 3 Greedy renaming of goods for the deviating agent $i$
Input: $X=\\{x_{1},x_{2},\ldots,x_{k}\\}$, $Y$, and a value oracle for
$v_{i}(\cdot)$

1:$Z=Y$

2:for $j=|Y|,\dots,1$ do

3: $y^{\prime}_{j}=\displaystyle\operatorname*{arg\,min}_{g\in
Z}v_{i}(g\,|\,\\{x_{1},\ldots,x_{j-1}\\})$ // Ties are broken
lexicographically.

4: $Z=Z\setminus\\{y^{\prime}_{j}\\}$

5:return $(y^{\prime}_{1},y^{\prime}_{2},\ldots,y^{\prime}_{|Y|})$

In what follows, we assume that the indexing $y_{1},y_{2},\ldots,y_{k}$ is
already the result of Algorithm 3. This renaming is crucial and it will be
used repeatedly. In particular, we need this particular ordering in order to
prove that $v_{i}(x_{j}\,|\,\\{x_{1},\ldots,x_{j-1}\\})\geq
v_{i}(y_{j}\,|\,\\{x_{1},\ldots,x_{j-1}\\})$, for all $j\in[k]$, in Lemma 3.5
below. Towards that, we need to fix some notation for the sake of readability.
For $j\in[k]$, we use $X^{j}_{-}$ and $X^{j}_{+}$ to denote the sets
$\\{x_{1},x_{2},\ldots,x_{j}\\}$ and $\\{x_{j},x_{j+1},\ldots,x_{k}\\}$,
respectively. The sets $Y^{j}_{-}$ and $Y^{j}_{+}$, for $j\in[k]$, are defined
analogously. We also use $X^{0}_{-}=Y^{0}_{-}=\emptyset$. The main high-level
idea of the proof is that if
$v_{i}(y_{\ell}\,|\,X^{\ell-1}_{-})>v_{i}(x_{\ell}\,|\,X^{\ell-1}_{-})$ for
some $\ell$, then it must be the case that during the execution of Round-
Robin$(\bm{\succ}^{\mathrm{b}})$ every good in
$Y^{\ell}_{-}=\\{y_{1},\ldots,y_{\ell}\\}$ is allocated before the turn of
agent $i$ in round $\ell$. Then, using a simple counting argument, we show
that agent $i$ cannot receive all the goods in $Y^{\ell}_{-}$ when deviating,
leading to a contradiction.

######  Lemma 3.5.

Let $X=\\{x_{1},x_{2},\ldots,x_{k}\\}$ be agent $i$’s bundle in Round-
Robin$(\bm{\succ}^{\mathrm{b}})$, where goods are indexed in the order they
were allocated, and $Y=\\{y_{1},y_{2},\ldots,y_{k}\\}$ be $i$’s bundle in
Round-Robin$({\succ}_{i},\bm{\succ}^{\mathrm{b}}_{-i})$, where goods are
indexed by Algorithm 3. Then, for every $j\in[k]$, we have
$v_{i}(x_{j}\,|\,X^{j-1}_{-})\geq v_{i}(y_{j}\,|\,X^{j-1}_{-})$.

###### Proof.

The way goods in $X$ are indexed, we have that $x_{j}$ is the good allocated
to agent $i$ in round $j$ of Round-Robin$(\bm{\succ}^{\mathrm{b}})$. Suppose,
towards a contradiction, that there is some ${\ell}\in[k]$, for which we have
$v_{i}(y_{\ell}\,|\,X^{\ell-1}_{-})>v_{i}(x_{\ell}\,|\,X^{\ell-1}_{-})$. First
notice that ${\ell}\neq 1$, as $x_{1}$ is, by the definition of the bluff
profile, a singleton of maximum value for agent $i$ excluding the goods
allocated to agents $1$ through $i-1$ in round $1$, regardless of agent $i$’s
bid. Thus, ${\ell}\geq 2$.

Let $B\subseteq M$ and $D\subseteq M$ be the sets of goods allocated (to any
agent) up to right before a good is allocated to agent $i$ in round $\ell$ in
Round-Robin$(\bm{\succ}^{\mathrm{b}})$ and Round-
Robin$({\succ}_{i},\bm{\succ}^{\mathrm{b}}_{-i})$, respectively. Clearly,
$|B|=|D|=(\ell-1)n+i-1$. In fact, we claim that in this case the two sets are
equal.

######  Claim 3.6.

It holds that $B=D$. Moreover, $\\{y_{1},\ldots,y_{\ell}\\}\subseteq B$.

###### Proof of the claim.

We first observe that $v_{i}(y_{j}\,|\,X^{\ell-1}_{-})\geq
v_{i}(y_{\ell}\,|\,X^{\ell-1}_{-})>v_{i}(x_{\ell}\,|\,X^{\ell-1}_{-})$, for
every $j\in[\ell-1]$, where the first inequality follows from way Algorithm 3
ordered the elements of $Y$. Now consider the execution of Round-
Robin$(\bm{\succ}^{\mathrm{b}})$. Since $x_{\ell}$ was the good allocated to
agent $i$ in round $\ell$, $x_{\ell}$ had maximum marginal value for agent $i$
with respect to $X^{\ell-1}_{-}$ among the available goods. Thus, none of the
goods $y_{1},\ldots,y_{\ell}$ were available at the time. That is,
$y_{1},\ldots,y_{\ell}$ were all already allocated to some of the agents
(possibly including agent $i$ herself). We conclude that
$\\{y_{1},\ldots,y_{l}\\}\subseteq B$.

Now suppose for a contradiction that $D\neq B$ and consider the execution of
Round-Robin$({\succ}_{i},\bm{\succ}^{\mathrm{b}}_{-i})$. Recall that the goods
in $B$ are still the $(\ell-1)n+i-1$ most preferable goods for every agent in
$N\setminus\\{i\\}$ according to the profile
$({\succ}_{i},\bm{\succ}^{\mathrm{b}}_{-i})$. Therefore, all agents in
$N\setminus\\{i\\}$ will get goods from $B$ allocated to them up to the point
when a good is allocated to agent $i$ in round $\ell$, regardless of what
${\succ}_{i}$ is. If agent $i$ also got only goods from $B$ allocated to her
in the first $\ell-1$ rounds of Round-
Robin$({\succ}_{i},\bm{\succ}^{\mathrm{b}}_{-i})$, then $D$ would be equal to
$B$. Thus, at least one good which is not in $B$ (and thus, not in
$\\{y_{1},\ldots,y_{\ell}\\}$) must have been allocated to agent $i$ in the
first $\ell-1$ rounds. As a result, at the end of round $\ell-1$, there are at
least two goods in $\\{y_{1},\ldots,y_{\ell}\\}$ that have not yet been
allocated to $i$.

However, we claim that up to right before a good is allocated to agent $i$ in
round $\ell+1$, all goods in $B$ (and thus in $\\{y_{1},\ldots,y_{\ell}\\}$ as
well) will have been allocated, leaving $i$ with at most $\ell-1$ goods from
$\\{y_{1},\ldots,y_{\ell}\\}$ in her final bundle and leading to a
contradiction. Indeed, this follows from a simple counting argument. Right
before a good is allocated to agent $i$ in round $\ell+1$, the goods allocated
to agents in $N\setminus\\{i\\}$ are exactly
$\ell(n-1)+i-1\geq(\ell-1)n+i-1=|B|$. As noted above, agents in
$N\setminus\\{i\\}$ will get goods from $B$ allocated to them as long as they
are available. Thus, no goods from $B$, or from $\\{y_{1},\ldots,y_{\ell}\\}$
in particular, remain unallocated right before a good is allocated to agent
$i$ in round $\ell+1$. Therefore, agent $i$ may get at most $\ell-1$ goods
from $\\{y_{1},\ldots,y_{\ell}\\}$ (at most $\ell-2$ in the first $\ell-1$
rounds and one in round $\ell$), contradicting the definition of the set $Y$.
We conclude that $D=B$. ∎

Given the claim, it is now easy to complete the proof. Clearly, in the first
$\ell-1$ rounds of Round-Robin$({\succ}_{i},\bm{\succ}^{\mathrm{b}}_{-i})$ at
most $\ell-1$ goods from $\\{y_{1},\ldots,y_{\ell}\\}$ have been allocated to
agent $i$. However, when it is $i$’s turn in round $\ell$, only goods in
$M\setminus D$ are available, by the definition of $D$. By Claim 3.6, we have
$\\{y_{1},\ldots,y_{l}\\}\subseteq D$, and thus there is at least one good
$\\{y_{1},\ldots,y_{\ell}\\}$ that is allocated to another agent, which
contradicts the definition of $Y$. ∎

We are now ready to state and prove the main result of this section.

######  Theorem 3.7.

When all agents have submodular valuation functions, the bluff profile is a
$\frac{1}{2}$-approximate PNE of Mechanism 1. Moreover, this is tight, i.e.,
for any $\varepsilon>0$, there are instances where the bluff profile is not a
$\big{(}\frac{1}{2}+\varepsilon\big{)}$-approximate PNE.

###### Proof.

We are going to use the notation used so far in the section and consider the
possible deviation of an arbitrary agent $i$. Like in the statement of Lemma
3.5, $X=\\{x_{1},\ldots,x_{k}\\}$ is agent $i$’s bundle in Round-
Robin$(\bm{\succ}^{\mathrm{b}})$, with goods indexed in the order they were
allocated, and $Y=\\{y_{1},y_{2},\ldots,y_{k}\\}$ is $i$’s bundle in Round-
Robin$({\succ}_{i},\bm{\succ}^{\mathrm{b}}_{-i})$, with goods indexed by
Algorithm 3. Also, recall that $X^{j}_{-}=\\{x_{1},\ldots,x_{j}\\}$ and
$X^{j}_{+}=\\{x_{j},\ldots,x_{k}\\}$ (and similarly for $Y^{j}_{-}$ and
$Y^{j}_{+}$). We also use the convention that $Y_{+}^{k+1}=\emptyset$. For any
$j\in[k]$, we have

$\displaystyle v_{i}(X_{-}^{j})-v_{i}(X_{-}^{j-1})$
$\displaystyle=v_{i}(x_{j}\,|\,X_{-}^{j-1})$ $\displaystyle\geq
v_{i}(y_{j}\,|\,X_{-}^{j-1})$ $\displaystyle\geq
v_{i}(y_{j}\,|\,X_{-}^{j-1}\cup Y_{+}^{j+1})$
$\displaystyle=v_{i}(X_{-}^{j-1}\cup
Y_{+}^{j+1}\cup\\{y_{j}\\})-v_{i}(X_{-}^{j-1}\cup Y_{+}^{j+1})$
$\displaystyle=v_{i}(X_{-}^{j-1}\cup Y_{+}^{j})-v_{i}(X_{-}^{j-1}\cup
Y_{+}^{j+1})$ $\displaystyle\geq v_{i}(X_{-}^{j-1}\cup
Y_{+}^{j})-v_{i}(X_{-}^{j}\cup Y_{+}^{j+1})\,.$

The first inequality holds because Lemma 3.5 applies on $X$ and $Y$, whereas
the second inequality holds because of submodularity. Finally, the last
inequality holds since $X_{-}^{j-1}\subseteq X_{-}^{j}$ and $v_{i}(\cdot)$ is
non-decreasing, for every $i\in N$. Using these inequalities along with a
standard expression of the value of a set as a sum of marginals, we have

$\displaystyle v_{i}(X)$ $\displaystyle=v_{i}(X_{-}^{k})-v_{i}(X_{-}^{0})$
$\displaystyle=\sum_{j=1}^{k}\left(v_{i}(X_{-}^{j})-v_{i}(X_{-}^{j-1})\right)$
$\displaystyle\geq\sum_{j=1}^{k}\left(v_{i}(X_{-}^{j-1}\cup
Y_{+}^{j})-v_{i}(X_{-}^{j}\cup Y_{+}^{j+1})\right)$
$\displaystyle=v_{i}(X_{-}^{0}\cup Y_{+}^{1})-v_{i}(X_{-}^{k}\cup
Y_{+}^{k+1})$ $\displaystyle=v_{i}(Y)-v_{i}(X)\,.$

Thus, we have $v_{i}(X)\geq\frac{1}{2}\cdot v_{i}(Y)$, and we conclude that
$\bm{\succ}^{\mathrm{b}}$ is a $\frac{1}{2}$-approximate PNE of Mechanism 1.

To show that the result is tight, consider an example with two agents and five
goods. The valuation function of agent $1$ is additive and defined as follows
on the singletons:

$v_{1}(g_{1})=2\quad v_{1}(g_{2})=1\quad v_{1}(g_{3})=1-\varepsilon_{1}\quad
v_{1}(g_{2})=1-\varepsilon_{2}\quad v_{1}(g_{5})=1-\varepsilon_{3}\,,$

where $1\gg\varepsilon_{3}>\varepsilon_{2}>\varepsilon_{1}>0$.

The valuation function of agent $2$ is OXS222Roughly speaking, OXS functions
generalize unit-demand functions. The set of OXS functions is a strict
superset of additive functions and a strict subset of submodular functions.
See, [26, 27]. and defined by the maximum matchings in the bipartite graph
below, e.g., $v_{2}(\\{g_{1},g_{2}\\})=2+1=3$ and
$v_{2}(\\{g_{1},g_{4},g_{5}\\})=2+1-\varepsilon_{2}=3-\varepsilon_{2}$.

$g_{1}$$g_{2}$$g_{3}$$g_{4}$$g_{5}$21$1-\varepsilon_{1}$$1-\varepsilon_{2}$$1-\varepsilon_{3}$

It is not hard to see that the bluff profile for this instance consists of the
following declared ordering by both agents: $g_{1}>g_{2}>g_{3}>g_{4}>g_{5}$.
The allocation produced by Mechanism 1 for the bluff profile is then
$A=(A_{1},A_{2})$, where $A_{1}=\\{g_{1},g_{3},g_{5}\\}$, and
$A_{2}=\\{g_{2},g_{4}\\}$. Observe that
$v_{1}(A_{1})=4-\varepsilon_{1}-\varepsilon_{3}$ and $v_{2}(A_{2})=1$. It is
easy to see that there is no profitable deviation for agent $1$, while the
maximum value that agent $2$ can attain by deviating is
$2-\varepsilon_{1}-\varepsilon_{2}$. Agent $2$ achieves this by reporting the
preference ranking: $g_{3}>g_{4}>g_{1}>g_{2}>g_{5}$ and getting goods
$\\{g_{3},g_{4}\\}$. This implies that for any $\varepsilon>0$ one can chose
appropriately small $\varepsilon_{1},\varepsilon_{2},\varepsilon_{3}$ so that
the bluff profile is not a $\big{(}\frac{1}{2}+\varepsilon\big{)}$-approximate
PNE. ∎

In Section 4, we show that every approximate PNE of Mechanism 1 results in an
approximately EF1 allocation. Here, as a warm-up, we start this endeavor with
an easy result which holds specifically for the bluff profile (and can be
extended to approximate PNE where all agents submit the same preference
ranking) but shows a better fairness guarantee than our general Theorem 4.4.

######  Theorem 3.8.

When all agents have submodular valuation functions $v_{1},\ldots,v_{n}$, the
allocation returned by Round-Robin$(\bm{\succ}^{\mathrm{b}})$ is
$\frac{1}{2}$-EF1 with respect to $v_{1},\ldots,v_{n}$. Moreover, this is
tight, i.e., for any $\varepsilon>0$, there are instances where this
allocation is not $\big{(}\frac{1}{2}+\varepsilon\big{)}$-EF1.

###### Proof.

In order to obtain a contradiction, suppose that the allocation
$(A_{1}^{\mathrm{b}},A_{2}^{\mathrm{b}},\ldots,A_{n}^{\mathrm{b}})$ returned
by Round-Robin$(\bm{\succ}^{\mathrm{b}})$ is not $\frac{1}{2}$-EF1. That is,
there exist agents $i$ and $j$ such that $v_{i}(A_{i}^{\mathrm{b}})<0.5\cdot
v_{i}(A_{j}^{\mathrm{b}}\setminus\\{g\\})$, for all $g\in A_{j}^{\mathrm{b}}$.
We are going to show that this allows us to construct a deviation for agent
$i$ where she gets value more than $2v_{i}(A_{i}^{\mathrm{b}})$, contradicting
the fact that $\bm{\succ}^{\mathrm{b}}$ is a $\frac{1}{2}$-approximate PNE.
Recall that using the renaming $h_{1},h_{2},\ldots$ produced by Algorithm 2,
we have $A_{i}^{\mathrm{b}}=\\{h_{i},h_{n+i},\dots,h_{(k-1)n+i}\\}$ and
$A_{j}^{\mathrm{b}}=\\{h_{j},h_{n+j},\dots,h_{(k-1)n+j}\\}$.

Let $\delta$ be the indicator variable of the event $j<i$, i.e., $\delta$ is
$1$ if $j<i$ and $0$ otherwise. We will show that it is possible for agent $i$
to get the set $\\{h_{\delta
n+j},h_{(1+\delta)n+j},h_{(2+\delta)n+j},\dots,h_{(k-1)n+j}\\}$, which is
either the entire $A_{j}^{\mathrm{b}}$ (when $i<j$) or
$A_{j}^{\mathrm{b}}\setminus\\{h_{j}\\}$ (when $j<i$). In particular, let
$\succ_{i}$ be a preference ranking that starts with all goods in
$A_{j}^{\mathrm{b}}$ in the same order as they were allocated to agent $j$ in
Round-Robin$(\bm{\succ}^{\mathrm{b}})$, followed by everything else, in any
order.

Consider the execution of Round-
Robin$(\succ_{i},\bm{\succ}_{-i}^{\mathrm{b}})$. The crucial, yet simple,
observation (that makes an inductive argument work) is that the first $i-1$
goods $h_{1},\ldots,h_{i-1}$ are allocated as before, then good $h_{\delta
n+j}$ (rather than $h_{i}$) is allocated to agent $i$, and after that the
$n-1$ top goods for all agents in $N\setminus\\{i\\}$ according to
$\bm{\succ}_{-i}^{\mathrm{b}}$ are $h_{i},h_{i+1},\dots,h_{\delta
n+j-1},h_{\delta n+j+1},\dots,h_{n+i-1}$, and these are allocated in the next
$n-1$ steps of the algorithm. As a result, right before a second good is
allocated to agent $i$, the available goods are
$h_{n+i},h_{n+i+1},\dots,h_{m}$ exactly as in the execution of Round-
Robin$(\bm{\succ}^{\mathrm{b}})$.

More generally, right before an $r$-th good is allocated to $i$, her bundle is
$\\{h_{\delta
n+j},h_{(1+\delta)n+j},h_{(2+\delta)n+j},\allowbreak\dots,h_{(r-2+\delta)n+j}\\}$,
and the available goods are $h_{(r-1)n+i},h_{(r-1)n+i+1},\dots,h_{m}$ (as they
were in the execution of Round-Robin$(\bm{\succ}^{\mathrm{b}})$). Then good
$h_{(r-1+\delta)n+j}$ (rather than $h_{(r-1)n+i}$) is allocated to agent $i$,
and after that the $n-1$ top goods for all agents according to
$\bm{\succ}_{-i}^{\mathrm{b}}$ are

$h_{(r-1)n+i},h_{(r-1)n+i+1},\dots,h_{(r-1+\delta)n+j-1},h_{(r-1+\delta)n+j+1},\dots,h_{rn+i-1}\,,$

and they are allocated in the next $n-1$ steps of the algorithm. At the end,
agent $i$ gets the entire $A_{j}^{\mathrm{b}}$ or
$A_{j}^{\mathrm{b}}\setminus\\{h_{j}\\}$ plus some arbitrary good, depending
on whether $i<j$ or $j<i$. In either case, by monotonicity, agent $i$’s value
for her bundle is at least
$v_{i}(A_{j}^{\mathrm{b}}\setminus\\{h_{j}\\})>2v_{i}(A_{i}^{\mathrm{b}})$,
where the last inequality follows from our assumption that
$(A_{1}^{\mathrm{b}},A_{2}^{\mathrm{b}},\ldots,A_{n}^{\mathrm{b}})$ is not
$\frac{1}{2}$-EF1. Therefore, by deviating from $\succ^{\mathrm{b}}$ to
$\succ_{i}$, agent $i$ increases her value by a factor strictly grater than
$2$, contradicting Theorem 3.7.

To show that this factor is tight, we again turn to the example given within
the proof of Theorem 3.7. Recall the allocation produced by Mechanism 1 for
the bluff profile is $A=(A_{1},A_{2})$, with $A_{1}=\\{g_{1},g_{3},g_{5}\\}$
and $A_{2}=\\{g_{2},g_{4}\\}$. Observe that agent $1$ is envy-free towards
agent $2$ as
$v_{1}(A_{1})=4-\varepsilon_{1}-\varepsilon_{3}>2-\varepsilon_{2}=v_{1}(A_{2})$.
On the other hand, $v_{2}(A_{2})=1$, whereas
$v_{2}(A_{1})=4-\varepsilon_{1}-\varepsilon_{3}$ and
$v_{2}(A_{1}\setminus\\{g_{1}\\})=2-\varepsilon_{1}-\varepsilon_{3}$. The
latter implies that for any $\varepsilon>0$ one can chose appropriately small
$\varepsilon_{1},\varepsilon_{2},\varepsilon_{3}$ so that the bluff profile
does not result in a $\big{(}\frac{1}{2}+\varepsilon\big{)}$-EF1 allocation
with respect to the true valuation functions of the agents. ∎

##  4 Fairness properties of PNE

In Section 2.3, Proposition 2.5, we state the fairness guarantees of Round-
Robin—viewed as an algorithm—when all agents have cancelable valuation
functions. So far, we have not discussed this matter for the submodular case.
It is not hard to see, however, that Theorem 3.8 and the definition of the
bluff profile via Algorithm 2 imply that when we have (value oracles for) the
valuation functions, then we can use Round-Robin to algorithmically produce
$\frac{1}{2}$-EF1 allocations. Using similar arguments, we show next that for
any preference profile $\bm{\succ}\,=(\succ_{1},\ldots,\succ_{n})$ and any
$i\in N$, there is always a response $\succ^{\prime}_{i}$ of agent $i$ to
$\bm{\succ}_{-i}$, such that the allocation returned by Round-
Robin$(\succ^{\prime}_{i},\bm{\succ}_{-i})$ is $\frac{1}{2}$-EF1 _from agent
$i$’s perspective_.

Towards this, we first need a variant of Algorithm 2 that considers everyone
in $N\setminus\\{i\\}$ fixed to their report in $\bm{\succ}_{-i}$ and greedily
determines a “good” response for agent $i$. An intuitive interpretation of
what Algorithm 4 below is doing, can be given if one sees Mechanism 1 as a
sequential game. Then, given that everyone else stays consistent with
$\bm{\succ}_{-i}$, agent $i$ _picks_ a good of maximum marginal value every
time her turn is up.

Algorithm 4 Greedy response of agent $i$ to $\bm{\succ}_{-i}$
Input: $N$, $M$, $\bm{\succ}_{-i}$, value oracle for $v_{i}$

1:$S=M$; $X=\emptyset$

2:for $j=1,\dots,m$ do

3: $\ell=(j-1)\\!\pmod{n}+1$

4: if $\ell=i$ then

5: $x_{\lceil j/n\rceil}=\displaystyle\operatorname*{arg\,max}_{g\in
S}v_{i}(g\,|\,X)$ // Ties are broken lexicographically.

6: $X=X\cup\\{x_{\lceil j/n\rceil}\\}$

7: $S=S\setminus\\{x_{\lceil j/n\rceil}\\}$

8: else

9: $g=\mathrm{top}(\succ_{\ell},S)$

10: $S=S\setminus\\{g\\}$

11:return
$x_{1}\succ^{\prime}_{i}x_{2}\succ^{\prime}_{i}\ldots\succ^{\prime}_{i}x_{k}\succ^{\prime}_{i}\ldots$
// Arbitrarily complete $\succ^{\prime}_{i}$ with goods in $M\setminus X$.

Proving the next lemma closely follows the proof of Theorem 3.7 but without
the need of an analog of Lemma 3.5, as we get this for free from the way the
greedy preference profile $\succ^{\prime}_{i}$ is constructed.

######  Lemma 4.1.

Assume that agent $i$ has a submodular valuation function $v_{i}$. If
$\succ^{\prime}_{i}$ is the ranking returned by Algorithm 4 when given $N$,
$M$, $\bm{\succ}_{-i}$, $v_{i}$, then the allocation
$(A^{\prime}_{1},A^{\prime}_{2},\ldots,A^{\prime}_{n})$ returned by Round-
Robin$(\succ^{\prime}_{i},\bm{\succ}_{-i})$ is such that for every $j\in N$,
with $A^{\prime}_{j}\neq\emptyset$, there exists a good $g\in A^{\prime}_{j}$,
so that $v_{i}(A^{\prime}_{i})\geq\frac{1}{2}\cdot
v_{i}(A^{\prime}_{j}\setminus\\{g\\})$.

###### Proof.

First, it is straightforward to see that $A^{\prime}_{i}=X$, as computed in
Algorithm 4. Indeed, Algorithm 4 simulates Mechanism 1 for all $j\in
N\setminus\\{i\\}$ and iteratively builds $\succ^{\prime}_{i}$, so that in
every turn of Round-Robin$(\succ^{\prime}_{i},\bm{\succ}_{-i})$ the good
allocated to agent $i$ is one of maximum marginal value. As a result, the
goods in $A^{\prime}_{i}=X=\\{x_{1},x_{2},\ldots,x_{k}\\}$ are already indexed
in the order they are allocated.

Now consider an arbitrary $j\in N\setminus\\{i\\}$ and let
$A^{\prime}_{j}=Y=\\{y_{1},y_{2},\ldots,y_{k}\\}$, where goods are again
indexed in the order they are allocated in Round-
Robin$(\succ^{\prime}_{i},\bm{\succ}_{-i})$. Notice that when good $x_{r}$ is
allocated to agent $i$ in round $r$, goods $y_{r+1},y_{r+2},\ldots$ are still
available and, by construction of $X$, their marginal value with respect to
the set $\\{x_{1},x_{2},\ldots,x_{r-1}\\}$ is no better than the marginal
value of $x_{r}$. In particular,
$v_{i}(x_{r}\,|\,\\{x_{1},\ldots,x_{r-1}\\})\geq
v_{i}(y_{r+1}\,|\,\\{x_{1},\ldots,x_{r-1}\\})$.

Also, recall the use of $X^{r}_{-}$, $X^{r}_{+}$, $Y^{r}_{-}$, $Y^{r}_{+}$
notation from the proof of Theorem 3.7. We will use a similar calculation here
as well, but we will omit the first element of $Y$. For any $r\in[k]$, we have

$\displaystyle v_{i}(X_{-}^{r})-v_{i}(X_{-}^{r-1})$
$\displaystyle=v_{i}(x_{r}\,|\,X_{-}^{r-1})$ $\displaystyle\geq
v_{i}(y_{r+1}\,|\,X_{-}^{r-1})$ $\displaystyle\geq
v_{i}(y_{r+1}\,|\,X_{-}^{r-1}\cup Y_{+}^{r+2})$
$\displaystyle=v_{i}(X_{-}^{r-1}\cup
Y_{+}^{r+2}\cup\\{y_{r+1}\\})-v_{i}(X_{-}^{r-1}\cup Y_{+}^{r+2})$
$\displaystyle=v_{i}(X_{-}^{r-1}\cup Y_{+}^{r+1})-v_{i}(X_{-}^{r-1}\cup
Y_{+}^{r+2})$ $\displaystyle\geq v_{i}(X_{-}^{r-1}\cup
Y_{+}^{r+1})-v_{i}(X_{-}^{r}\cup Y_{+}^{r+2})\,,$

where we used the convention that $Y_{+}^{k+1}=Y_{+}^{k+2}=\emptyset$. The
first inequality holds by the construction of $X$ as discussed above, the
second inequality follows from submodularity, and the last inequality holds
because $v_{i}(\cdot)$ is non-decreasing. Using these inequalities and a
standard expression of the value of a set as a sum of marginals, we have

$\displaystyle v_{i}(X)$ $\displaystyle=v_{i}(X_{-}^{k})-v_{i}(X_{-}^{0})$
$\displaystyle=\sum_{r=1}^{k}\left(v_{i}(X_{-}^{r})-v_{i}(X_{-}^{r-1})\right)$
$\displaystyle\geq\sum_{r=1}^{k}\left(v_{i}(X_{-}^{r-1}\cup
Y_{+}^{r+1})-v_{i}(X_{-}^{r}\cup Y_{+}^{r+2})\right)$
$\displaystyle=v_{i}(X_{-}^{0}\cup Y_{+}^{2})-v_{i}(X_{-}^{k}\cup
Y_{+}^{k+2})$ $\displaystyle=v_{i}(Y\setminus\\{y_{1}\\})-v_{i}(X)\,.$

Thus, we have $v_{i}(A^{\prime}_{i})=v_{i}(X)\geq\frac{1}{2}\cdot
v_{i}(Y\setminus\\{y_{1}\\})=\frac{1}{2}\cdot
v_{i}(A^{\prime}_{j}\setminus\\{y_{1}\\})$. ∎

###  4.1 The Case of Two Agents

As a warm-up, we begin with the easier case of $n=2$. Not only the proofs of
our main results for submodular and additive functions are much simpler here,
but the fairness guarantees are stronger as well.

######  Theorem 4.2.

Let $\alpha\in(0,1]$. Assume we have a fair division instance with two agents,
whose valuation functions $v_{1},v_{2}$ are submodular. Then any allocation
that corresponds to a $\alpha$-approximate PNE of the Round-Robin mechanism is
$\frac{\alpha}{2}$-EF1 with respect to $v_{1},v_{2}$.

###### Proof.

Let $\bm{\succ}\,=(\succ_{1},\succ_{2})$ be a $\alpha$-approximate PNE of
Mechanism 1 for a given instance, and let $(A_{1},A_{2})$ be the allocation
returned by Round-Robin$(\bm{\succ})$. Consider one of the two agents; we call
this agent $i\in[2]$ and the other agent $j$. We are going to show that
$v_{i}(A_{i})\geq\frac{\alpha}{2}\cdot v_{i}(A_{j}\setminus\\{g\\})$ for some
good $g\in A_{j}$.

Suppose that agent $i$ deviates to $\succ^{\prime}_{i}$ produced by Algorithm
4 when given $\bm{\succ}_{-i}\,=(\succ_{j})$ and $v_{i}$, and let
$(A^{\prime}_{1},A^{\prime}_{2})$ be the allocation returned by Round-
Robin$(\succ^{\prime}_{i},\bm{\succ}_{-i})$. Let
$A^{\prime}_{i}=\\{x_{1},x_{2},\ldots,x_{k}\\}$ and $A_{j}\setminus
A^{\prime}_{i}=\\{y_{t_{1}},y_{t_{2}},\ldots,y_{t_{\ell}}\\}$, where in both
sets goods are indexed by the round in which they were allocated in the run of
Round-Robin$(\succ^{\prime}_{i},\bm{\succ}_{-i})$. Note that all indices in
$A_{j}\setminus A^{\prime}_{i}$ are distinct exactly because $n=2$ and, thus,
all these goods are allocated to agent $j$. This indexing guarantees that when
$x_{t_{\lambda}-1}$ gets allocated, $y_{t_{\lambda}}$ is still available for
$2\leq\lambda\leq\ell$ and, thus,

$v(x_{t_{\lambda}-1}\,|\,\\{x_{1},x_{2},\ldots,x_{t_{\lambda}-2}\\})\geq
v(y_{t_{\lambda}}\,|\,\\{x_{1},x_{2},\ldots,x_{t_{\lambda}-2}\\})\,,$ (1)

by the way $\succ^{\prime}_{i}$ is constructed (see also the proof of Lemma
4.1). Using Theorem 2.1, we have

$\displaystyle v_{i}(A_{j}\setminus\\{y_{t_{1}}\\})$ $\displaystyle\leq
v_{i}(A^{\prime}_{i})+\\!\\!\sum_{g\in(A_{j}\setminus\\{y_{t_{1}}\\})\setminus
A^{\prime}_{i}}\\!\\!\\!\\!\\!v(g\,|\,A^{\prime}_{i})$
$\displaystyle=v_{i}(A^{\prime}_{i})+\sum_{\lambda=2}^{\ell}v(y_{t_{\lambda}}\,|\,A^{\prime}_{i})$
$\displaystyle\leq
v_{i}(A^{\prime}_{i})+\sum_{\lambda=2}^{\ell}v(y_{t_{\lambda}}\,|\,\\{x_{1},x_{2},\ldots,x_{t_{\lambda}-2}\\})$
$\displaystyle\leq
v_{i}(A^{\prime}_{i})+\sum_{\lambda=2}^{\ell}v(x_{t_{\lambda}-1}\,|\,\\{x_{1},x_{2},\ldots,x_{t_{\lambda}-2}\\})$
$\displaystyle\leq
v_{i}(A^{\prime}_{i})+\sum_{\lambda=1}^{k}v(x_{\lambda}\,|\,\\{x_{1},x_{2},\ldots,x_{\lambda-1}\\})$
$\displaystyle=v_{i}(A^{\prime}_{i})+v_{i}(A^{\prime}_{i})$
$\displaystyle\leq\frac{2}{\alpha}\cdot v_{i}(A_{i})\,,$

where the first inequality follows directly from Theorem 2.1, the second one
follows from submodularity, the third inequality holds because of (1), the
fourth one follows from the monotonicity of $v_{i}$, and the last inequality
follows from the fact that $\bm{\succ}$ is a $\alpha$-approximate PNE and thus
$v_{i}(A_{i})\geq\alpha\cdot v_{i}(A^{\prime}_{i})$. We conclude that
$(A_{1},A_{2})$ is $\frac{\alpha}{2}$-EF1 with respect to the underlying
valuation functions. ∎

For additive valuation functions we can get a slightly stronger fairness
guarantee, which we show that is also tight for any $\alpha$, with an even
easier proof. Note that this reproduces the result of Amanatidis et al. [5]
for exact PNE in the case of two agents.

######  Theorem 4.3.

Let $\alpha\in(0,1]$. Assume we have a fair division instance with two agents,
whose valuation functions $v_{1},v_{2}$ are additive. Then any allocation that
corresponds to a $\alpha$-approximate PNE of the Round-Robin mechanism is
$\frac{\alpha}{2-\alpha}$-EF1 with respect to $v_{1},v_{2}$. This is tight,
i.e., for any $\varepsilon>0$, there are instances where a
$\alpha$-approximate PNE does not correspond to a
$(\frac{\alpha}{2-\alpha}+\varepsilon)$-EF1 allocation.

###### Proof.

Let $\bm{\succ}\,=(\succ_{1},\succ_{2})$, $A_{1}$, $A_{2}$ be as in the proof
of Theorem 4.2, but now consider the deviation of agent $i$ to
$\succ^{\prime}_{i}$ which is a strict version of her true preference ranking
$\succcurlyeq^{*}_{i}$. Again, let $(A^{\prime}_{1},A^{\prime}_{2})$ be the
allocation returned by Round-Robin$(\succ^{\prime}_{i},\bm{\succ}_{-i})$.

Let $g$ be good of maximum value in $A^{\prime}_{j}$ according to $v_{i}$.
Since $\succ^{\prime}_{i}$ is a true preference ranking of agent $i$,
according to Proposition 2.5 $(A^{\prime}_{1},A^{\prime}_{2})$ is EF1 from the
point of view of agent $i$. That is, we have $v_{i}(A^{\prime}_{i})\geq
v_{i}(A^{\prime}_{j}\setminus\\{g\\})$ and, thus,
$v_{i}(A^{\prime}_{i})\geq\frac{1}{2}\cdot v_{i}(M\setminus\\{g\\})$.
Therefore,

$\displaystyle v_{i}(A_{j}\setminus\\{g\\})$
$\displaystyle=v_{i}(M\setminus\\{g\\})-v_{i}(A_{i})$ $\displaystyle\leq
2\cdot v_{i}(A^{\prime}_{i})-v_{i}(A_{i})$
$\displaystyle\leq\frac{2}{\alpha}\cdot v_{i}(A_{i})-v_{i}(A_{i})$
$\displaystyle=\frac{2-\alpha}{\alpha}\cdot v_{i}(A_{i})\,,$

where the second inequality follows from the fact that $\bm{\succ}$ is a
$\alpha$-approximate PNE and thus $v_{i}(A_{i})\geq\alpha\cdot
v_{i}(A^{\prime}_{i})$. We conclude that $(A_{1},A_{2})$ is
$\frac{\alpha}{2-\alpha}$-EF1 with respect to $v_{1},v_{2}$.

To see that this guarantee is tight, consider an instance with two agents, and
a set of five goods $\\{g_{1},g_{2},\ldots,g_{5}\\}$. In addition, let the
valuation functions of the agents to be additive and defined by:

$v_{1}(g_{j})=\begin{cases}6,&\text{if $j=1$}\\\ 3+\delta,&\text{if $j=2$}\\\
3,&\text{if $j=3$}\\\ 0.5+\delta,&\text{if $j=4$}\\\ 0.5,&\text{if
$j=5$}\end{cases}$

$v_{2}(g_{j})=\begin{cases}6\beta,&\text{if $j=1$}\\\ 3\beta+\delta,&\text{if
$j=2$}\\\ 3\beta,&\text{if $j=3$}\\\ 0.5+\delta,&\text{if $j=4$}\\\
0.5,&\text{if $j=5$}\end{cases}$

where $0.5\gg\delta$, and $\beta>\frac{1}{6}+\delta$. Now suppose that the
agents bid as follows: Agent $1$ bids truthfully (i.e., an ordering
$\succ_{1}$ that is consistent with her true valuation function), while agent
$2$ bids $g_{5}\succ_{2}g_{4}\succ_{2}g_{1}\succ_{2}g_{2}\succ_{2}g_{3}$. It
is easy to confirm that the produced allocation is
$A=(A_{1},A_{2})=(\\{g_{1},g_{2},g_{3}\\},\\{g_{4},g_{5}\\})$. Regarding agent
1, she takes her three most desirable goods in this allocation so there is no
profitable deviation for her. For the same reason, she is envy-free towards
agent 2.

Moving to agent 2, by observing her valuation function, we immediately derive
that she is $\frac{1+\delta}{6\beta+\delta}$-EF1 towards agent 1. The only
thing that remains, is to check how much agent $2$ can improve her utility
through deviating. Initially notice that agent $2$ cannot get good $g_{1}$
regardless of her bid as this good is taken by agent $1$ in round 1. At the
same time, it is easy to verify that she cannot get both goods $g_{2}$ and
$g_{3}$ due to the declared ordering of agent 1. Thus, the best bundle of
goods that she can acquire is $\\{g_{2},g_{4}\\}$ by deviating to the bid:
$g_{2}\succ^{\prime}_{2}g_{4}\succ^{\prime}_{2}g_{1}\succ^{\prime}_{2}g_{3}\succ^{\prime}_{2}g_{5}$
and attain a value of $3\beta+0.5+2\delta$.

By setting $\alpha=\frac{1+\delta}{3\beta+0.5+2\delta}$ we trivially have that
$(\succ_{1},\succ_{2})$ is a $\alpha$-approximate PNE. On the other hand, for
a given $\varepsilon>0$, we have
$\frac{\alpha}{2-\alpha}+\varepsilon=\frac{1+\delta}{6\beta+3\delta}+\varepsilon$
which is strictly larger than $\frac{1+\delta}{6\beta+\delta}$ for
sufficiently small $\delta$. That is, there is a choice of $\delta$ so that
the $\alpha$-approximate PNE $(\succ_{1},\succ_{2})$ is not
$\frac{\alpha}{2-\alpha}+\varepsilon$-EF1. ∎

###  4.2 The Case of $n$ Agents

Looking back at the proofs of Theorems 4.2 and 4.3, the obvious fact that
everything not in $A_{i}$ or $A^{\prime}_{i}$ was allocated to agent $j$
played a key role in proving our sharp bounds. Moving to the general case of
$n$ agents, there is no reason to expect that we have some control on how the
goods are redistributed between agents in $N\setminus\\{i\\}$ when agent $i$
deviates from an (approximate) equilibrium. Surprisingly, we show that this
redistribution does not favor any agent too much from $i$’s perspective when
the valuation functions are submodular or subadditive cancelable (Lemmata 4.6
and 4.7). Consequently, the main results of this section have similar flavor
not only with respect to their statements, but with respect to their proofs as
well.

######  Theorem 4.4.

Let $\alpha\in(0,1]$. For instances with submodular valuation functions
$\\{v_{i}\\}_{i\in N}$, any $\alpha$-approximate PNE of the Round-Robin
mechanism is $\frac{\alpha}{3}$-EF1 with respect to $\\{v_{i}\\}_{i\in N}$.

######  Theorem 4.5.

Let $\alpha\in(0,1]$. For instances with subadditive cancelable valuation
functions $\\{v_{i}\\}_{i\in N}$, any $\alpha$-approximate PNE of the Round-
Robin mechanism is $\frac{\alpha}{2}$-EF1 with respect to $\\{v_{i}\\}_{i\in
N}$.

As the proofs of both theorems have the same general structure and share
Lemmata 4.6 and 4.7, we begin with some common wording and notation,
consistent with our proofs for two agents. Given any instance, we use
$\bm{\succ}\,=(\succ_{1},\ldots,\succ_{n})$ for an arbitrary
$\alpha$-approximate PNE of Mechanism 1. We then consider the deviation of
some agent $i$ to a preference ranking $\succ^{\prime}_{i}$; in the submodular
case $\succ^{\prime}_{i}$ is the output of Algorithm 4 when given
$\bm{\succ}_{-i}$ and $v_{i}$, whereas in the cancelable case
$\succ^{\prime}_{i}$ is a strict version of $i$’s true preference ranking
$\succcurlyeq^{*}_{i}$. We use $(A_{1},\ldots,A_{n})$ and
$(A^{\prime}_{1},\ldots,A^{\prime}_{n})$ to denote the allocations returned by
Round-Robin$(\bm{\succ})$ and Round-
Robin$(\succ^{\prime}_{i},\bm{\succ}_{-i})$, respectively.

In order to show that $(A_{1},\ldots,A_{n})$ as $\frac{\alpha}{\kappa}$-EF1
from agent $i$’s perspective (where $\kappa$ is $3$ for submodular and $2$ for
cancelable functions), we use the stronger EF1 guarantees that
$(A^{\prime}_{1},\ldots,A^{\prime}_{n})$ has from her perspective. To this
end, we use $h_{r}^{\ell}$ to denote the good that was allocated to an agent
$\ell\in N$ in round $r$ of Round-Robin$(\succ^{\prime}_{i},\bm{\succ}_{-i})$.
In particular, $A^{\prime}_{i}=\\{h^{i}_{1},h^{i}_{2},\ldots,h^{i}_{k}\\}$;
recall that $k=m/n$. Further, given that we have fixed agent $i$, we use
$S_{r}$ and $S^{\prime}_{r}$, for $0\leq r\leq k-1$, to denote the set of
goods that had been allocated up to right before a good was allocated to $i$
in round $r+1$ of Round-Robin$(\bm{\succ})$ and Round-
Robin$(\succ^{\prime}_{i},\bm{\succ}_{-i})$, respectively. That is, for $0\leq
r\leq k-1$, $S_{r}$ and $S^{\prime}_{r}$ contain the goods allocated in steps
$1$ through $rn+i-1$ of Round-Robin$(\bm{\succ})$ and Round-
Robin$(\succ^{\prime}_{i},\bm{\succ}_{-i})$, respectively.

For the next technical lemma we assume that the valuation functions are either
submodular or cancelable and, in each case, we use the corresponding
$\succ^{\prime}_{i}$ as described above.

######  Lemma 4.6.

For any $r\in[k]$, right before an $r$-th good is allocated to agent $i$ in
Round-Robin$(\bm{\succ})$, there are at most $r-1$ goods from
$S^{\prime}_{r-1}$ that are still unallocated, i.e.,
$\left|S^{\prime}_{r-1}\setminus S_{r-1}\right|\leq r-1$.

###### Proof.

We will prove the statement using induction on $r$. For $r=1$, it is
straightforward that $S_{0}=S^{\prime}_{0}$, as the preference rankings of
agents $1$ through $i-1$ are the same in the two runs of the mechanism and,
thus, the first goods allocated to them are exactly the same.

Now suppose that the statement is true for every round up to round $r$; we
will show that it is true for round $r+1$ as well. Initially, observe that if
the number of unallocated goods from $S^{\prime}_{r-1}$ is $r-1$ right before
a good is allocated to agent $i$ in round $r$, it will trivially be at most
$r-1$ right before a good is allocated to agent $i$ in round $r+1$ (as the
number of unallocated goods from any set cannot increase as the allocation
progresses). That is, $\left|S^{\prime}_{r-1}\setminus S_{r}\right|\leq r-1$.

Notice that the goods that might cause $S^{\prime}_{r}\setminus S_{r}$ to
increase are the elements of

$S^{\prime}_{r}\setminus
S^{\prime}_{r-1}=\\{h^{i}_{r},h^{i+1}_{r},\ldots,h^{n}_{r},h^{1}_{r+1},h^{2}_{r+1},\ldots,h^{i-1}_{r+1}\\}\,,$

and suppose that there are $\lambda$ goods therein which are still unallocated
right before a good is allocated to agent $i$ in round $r+1$ of Round-
Robin$(\bm{\succ})$. Clearly, if $\lambda\leq 1$, we are done. So, assume that
$\lambda\geq 2$. This means that there are $\lambda-1\geq 1$ unallocated goods
in $(S^{\prime}_{r}\setminus S^{\prime}_{r-1})\setminus\\{h^{i}_{r}\\}$. Let
$g$ be one of these goods and let $j$ be the agent to whom $g$ was given,
i.e., $g=h^{j}_{\bar{r}}$, where $\bar{r}=r$, if $j>i$, and $\bar{r}=r+1$, if
$j<i$. In either case, notice that according to $\succ_{j}$ the good $g$ is
better than any good in $M\setminus S^{\prime}_{r}$ or else it would not have
been allocated to $j$ at round $\bar{r}$ of Round-
Robin$(\succ^{\prime}_{i},\bm{\succ}_{-i})$ when everything in $M\setminus
S^{\prime}_{r}$ is still available. We claim that $g$ does not increase the
number of elements in $S^{\prime}_{r}\setminus S_{r}$. Indeed, given that $g$
was available during step $(\bar{r}-1)n+j$ of Round-Robin$(\bm{\succ})$ and
that $j$’s declared preference ranking is still $\succ_{j}$, the only
possibility is that during that step one of the unallocated goods from
$S^{\prime}_{r-1}\cup\\{h^{i}_{r},h^{i+1}_{r},\ldots,h^{j-1}_{\bar{r}}\\}$ was
allocated to $j$ instead.

Therefore, the only good out of the $\lambda$ candidate goods of
$S^{\prime}_{r}\setminus S^{\prime}_{r-1}$ which might count towards the
number of elements in $S^{\prime}_{r}\setminus S_{r}$ is $h^{i}_{r}$. We
conclude that $S^{\prime}_{r}\setminus S_{r}\leq(r-1)+1=r$. ∎

Lemma 4.6 is global, illustrating that the sets $S_{r}$ and $S^{\prime}_{r}$
cannot differ in more than a $1/n$-th of their elements. The next lemma shows
that no agent can accumulate too many goods from $S^{\prime}_{r}$, for any
$0\leq r\leq k-1$. Again, we assume that the valuation functions are either
submodular or cancelable and, in each case, the appropriate
$\succ^{\prime}_{i}$ is used as discussed after the statements of Theorems 4.2
and 4.3. Note that $S^{\prime}_{0}$ in the lemma’s statement contains exactly
these goods which we will exclude when showing the EF1 guarantee for our two
theorems.

######  Lemma 4.7.

For any $r\in[k]$ and any $j\in N$, agent $j$ gets at most $2(r-1)$ goods from
$S^{\prime}_{r-1}\setminus S^{\prime}_{0}$ in the allocation
$(A_{1},\ldots,A_{n})$ returned by Round-Robin$(\bm{\succ})$, i.e.,
$|A_{j}\cap(S^{\prime}_{r-1}\setminus S^{\prime}_{0})|\leq 2(r-1)$.

###### Proof.

Fix an $r\in[k]$ and a $j\in N$. Consider the end of step $(r-1)n+i-1$ of
Round-Robin$(\bm{\succ})$, i.e., right before an $r$-th good is allocated to
agent $i$. Ignoring all the goods allocated before $i$ got her first good,
agent $j$ has received exactly $r-1$ goods up to this point. As a result, the
number of goods allocated to $j$ from $S^{\prime}_{r-1}\setminus
S^{\prime}_{0}$ at this point is at most $r-1$.

At the same time, the number of goods from $S^{\prime}_{r-1}\setminus
S^{\prime}_{0}$ that might end up in $A_{j}$ in any future steps of Round-
Robin$(\bm{\succ})$ are at most as many as the goods from $S^{\prime}_{r-1}$
that are still unallocated at the end of step $(r-1)n+i-1$. The latter, by
Lemma 4.6, are also at most $r-1$.

From these two observations, we have that the final bundle $A_{j}$ of agent
$j$ may contain at most $2(r-1)$ goods from $S^{\prime}_{r-1}\setminus
S^{\prime}_{0}$. ∎

With Lemma 4.7 at hand, we are now ready to prove Theorems 4.4 and 4.5;

###### Proof of Theorem 4.4.

We, of course, adopt the notation that has been used throughout this section,
focusing on an arbitrary agent $i\in N$ and assuming that her deviation
$\succ^{\prime}_{i}$ has been the output of Algorithm 4 with input
$\bm{\succ}_{-i}$ and $v_{i}$. In particular, $(A_{1},\ldots,A_{n})$ and
$(A^{\prime}_{1},\ldots,A^{\prime}_{n})$ are the allocations returned by
Round-Robin$(\bm{\succ})$ and Round-
Robin$(\succ^{\prime}_{i},\bm{\succ}_{-i})$, respectively.

Consider another agent $j\in N\setminus\\{i\\}$. Let
$A^{\prime}_{i}=\\{x_{1},x_{2},\ldots,x_{k}\\}$ and
$A_{j}=\\{y_{1},y_{2},\ldots,y_{k}\\}$, where in both sets goods are indexed
in the order in which they were allocated in the run of Round-
Robin$(\succ^{\prime}_{i},\bm{\succ}_{-i})$. For $A^{\prime}_{i}$, this means
that $x_{r}$ was allocated in round $r$ for all $r\in[k]$. For $A_{j}$, this
indexing guarantees that for every $0\leq\ell<r\leq k-1$, the goods in
$A_{j}\cap(S^{\prime}_{\ell}\setminus S^{\prime}_{\ell-1})$ all have smaller
indices than the goods in $A_{j}\cap(S^{\prime}_{r}\setminus
S^{\prime}_{r-1})$ (where we use the convention that
$S^{\prime}_{-1}=\emptyset$). We further partition $A_{j}\setminus\\{y_{1}\\}$
to $Y_{1}=\\{y^{1}_{1},\ldots,y^{1}_{\tau_{1}}\\}$ and
$Y_{2}=\\{y^{2}_{1},\ldots,y^{2}_{\tau_{2}}\\}$ which contain the goods of
$A_{j}\setminus\\{y_{1}\\}$ with odd and even indices, respectively, and are
both renamed according to Algorithm 3 with inputs $A^{\prime}_{i}$, $Y_{1}$,
$v_{i}$, and $A^{\prime}_{i}$, $Y_{2}$, $v_{i}$, respectively. Clearly,
$\tau_{1}=\lfloor\frac{k-1}{2}\rfloor$ and
$\tau_{2}=\lceil\frac{k-1}{2}\rceil$.

By Lemma 4.7, we have that $A_{j}$ contains at most $2(r-1)$ goods from
$S^{\prime}_{r-1}\setminus S^{\prime}_{0}$, for any $r\in[k]$. The original
ordering $y_{1},y_{2},\ldots$ of the goods in $A_{j}$ and the way
$A_{j}\setminus\\{y_{1}\\}$ was partitioned into $Y_{1}$ and $Y_{2}$ imply
that $\left||Y_{1}\cap(S^{\prime}_{r-1}\setminus
S^{\prime}_{0})|-|Y_{2}\cap(S^{\prime}_{r-1}\setminus
S^{\prime}_{0})|\right|\leq 1$ and, thus, each of $Y_{1}$ and $Y_{2}$ contains
at most $r-1$ goods from $S^{\prime}_{r-1}\setminus S^{\prime}_{0}$.

We also claim that, for $\ell\in\\{1,2\\}$ and $r\in[\tau_{\ell}]$, we have

$v_{i}(x_{r}\,|\,\\{x_{1},\ldots,x_{r-1}\\})\geq
v_{i}(y^{\ell}_{r}\,|\,\\{x_{1},\ldots,x_{r-1}\\})\,.$ (2)

Suppose not. That is, there are $\ell\in\\{1,2\\}$ and $r\in[\tau_{\ell}]$ so
that (2) is violated. Note that, by the way Algorithm 3 ordered the elements
of $Y_{1}$ and $Y_{2}$, this implies

$v_{i}(x_{r}\,|\,\\{x_{1},\ldots,x_{r-1}\\})<v_{i}(y^{\ell}_{r}\,|\,\\{x_{1},\ldots,x_{r-1}\\})\leq
v_{i}(y^{\ell}_{t}\,|\,\\{x_{1},\ldots,x_{r-1}\\})\,,$

for all $t\in[r]$. Since $x_{r}$ was the good allocated to agent $i$ at step
$(r-1)n+i$ of Round-Robin$(\succ^{\prime}_{i},\bm{\succ}_{-i})$, $x_{r}$ had
maximum marginal value for $i$ with respect to $\\{x_{1},\ldots,x_{r-1}\\}$
among the available goods. Thus, none of the goods
$y^{\ell}_{1},\ldots,y^{\ell}_{r}$ were available at the time, i.e.,
$y^{\ell}_{1},\ldots,y^{\ell}_{r}\in S^{\prime}_{r-1}$. Given that the only
good of $A_{j}$ that could possibly be in $S^{\prime}_{0}=S_{0}$ was $y_{1}$
which is not in $Y_{1}\cup Y_{2}$. Therefore,
$y^{\ell}_{1},\ldots,y^{\ell}_{r}\in S^{\prime}_{r-1}\setminus
S^{\prime}_{0}$, which contradicts the fact that
$|Y_{\ell}\cap(S^{\prime}_{r-1}\setminus S^{\prime}_{0})|\leq r-1$. We
conclude that (2) holds for all $\ell\in\\{1,2\\}$ and $r\in[\tau_{\ell}]$.

We are now ready to apply Theorem 2.1 to bound the value of
$A_{j}\setminus\\{y_{1}\\}$. We have

$\displaystyle v_{i}(A_{j}\setminus\\{y_{1}\\})$ $\displaystyle\leq
v_{i}(A^{\prime}_{i})+\\!\\!\sum_{g\in(A_{j}\setminus\\{y_{1}\\})\setminus
A^{\prime}_{i}}\\!\\!\\!\\!\\!v(g\,|\,A^{\prime}_{i})$
$\displaystyle=v_{i}(A^{\prime}_{i})+\\!\sum_{g\in Y_{1}\setminus
A^{\prime}_{i}}\\!\\!v(g\,|\,A^{\prime}_{i})+\\!\sum_{g\in Y_{2}\setminus
A^{\prime}_{i}}\\!\\!v(g\,|\,A^{\prime}_{i})$
$\displaystyle=v_{i}(A^{\prime}_{i})+\sum_{\ell=1}^{\tau_{1}}v(y^{1}_{{\ell}}\,|\,A^{\prime}_{i})+\sum_{\ell=1}^{\tau_{2}}v(y^{2}_{{\ell}}\,|\,A^{\prime}_{i})$
$\displaystyle\leq
v_{i}(A^{\prime}_{i})+\sum_{\ell=1}^{\tau_{1}}v(y^{1}_{{\ell}}\,|\,\\{x_{1},\ldots,x_{\ell-1}\\})+\sum_{\ell=1}^{\tau_{2}}v(y^{2}_{{\ell}}\,|\,\\{x_{1},\ldots,x_{\ell-1}\\})$
$\displaystyle\leq
v_{i}(A^{\prime}_{i})+\sum_{\ell=1}^{\tau_{1}}v(x_{{\ell}}\,|\,\\{x_{1},\ldots,x_{\ell-1}\\})+\sum_{\ell=1}^{\tau_{2}}v(x_{{\ell}}\,|\,\\{x_{1},\ldots,x_{\ell-1}\\})$
$\displaystyle\leq
v_{i}(A^{\prime}_{i})+2\cdot\\!\sum_{\ell=1}^{k}v(x_{\ell}\,|\,\\{x_{1},x_{2},\ldots,x_{\ell-1}\\})$
$\displaystyle=v_{i}(A^{\prime}_{i})+2\cdot v_{i}(A^{\prime}_{i})$
$\displaystyle\leq\frac{3}{\alpha}\cdot v_{i}(A_{i})\,,$

where the first inequality follows directly from Theorem 2.1, the second one
follows from submodularity, the third inequality holds because of (2), the
fourth one follows from the monotonicity of $v_{i}$, and the last inequality
follows from the fact that $\bm{\succ}$ is a $\alpha$-approximate PNE and thus
$v_{i}(A_{i})\geq\alpha\cdot v_{i}(A^{\prime}_{i})$. We conclude that
$(A_{1},A_{2},\ldots,A_{n})$ is $\frac{\alpha}{3}$-EF1 with respect to the
underlying valuation functions. ∎

###### Proof of Theorem 4.5.

Note that in the proof of Theorem 4.2, the submodularity of $v_{i}$ is not
used until the final bounding of $A_{j}\setminus\\{y_{1}\\}$. Up to that
point, the proof here is essentially identical (the only difference being that
now $\succ^{\prime}_{i}$ is a strict version of $i$’s true preference ranking
$\succcurlyeq^{*}_{i}$ but this does not change any of the arguments). In
particular, for $A^{\prime}_{i}=\\{x_{1},x_{2},\ldots,x_{k}\\}$,
$A_{j}=\\{y_{1},y_{2},\ldots,y_{k}\\}$,
$Y_{1}=\\{y^{1}_{1},\ldots,y^{1}_{\tau_{1}}\\}$, and
$Y_{2}=\\{y^{2}_{1},\ldots,y^{2}_{\tau_{2}}\\}$, like in the proof of Theorem
4.2, we still have (2), for any $\ell\in\\{1,2\\}$ and $r\in[\tau_{\ell}]$,
i.e., $v_{i}(x_{r}\,|\,\\{x_{1},\ldots,x_{r-1}\\})\geq
v_{i}(y^{\ell}_{r}\,|\,\\{x_{1},\ldots,x_{r-1}\\})$.

Notice that (2) can be rewritten as
$v_{i}(\\{x_{1},\ldots,x_{r-1},x_{r}\\})\geq
v_{i}(\\{x_{1},\ldots,x_{r-1},y^{\ell}_{r}\\})$. Since $v_{1}$ is cancelable,
the latter implies that $v_{i}(x_{r})\geq v_{i}(y^{\ell}_{r})$, for
$\ell\in\\{1,2\\}$ and $r\in[\tau_{\ell}]$. Now we apply Lemma 3.3 to get
$v_{i}(\\{x_{1},x_{2},\ldots,x_{\tau_{\ell}}\\})\geq v_{i}(Y_{\ell})$, for
$\ell\in\\{1,2\\}$. At this point, we can easily bound the value of
$A_{j}\setminus\\{y_{1}\\}$. We have

$\displaystyle v_{i}(A_{j}\setminus\\{y_{1}\\})$
$\displaystyle=v_{i}(Y_{1}\cup Y_{2})$ $\displaystyle\leq
v_{i}(Y_{1})+v_{i}(Y_{2})$ $\displaystyle\leq
v_{i}(\\{x_{1},x_{2},\ldots,x_{\tau_{1}}\\})+v_{i}(\\{x_{1},x_{2},\ldots,x_{\tau_{2}}\\})$
$\displaystyle\leq v_{i}(A^{\prime}_{i})+v_{i}(A^{\prime}_{i})$
$\displaystyle\leq\frac{2}{\alpha}\cdot v_{i}(A_{i})\,,$

where the first inequality follows from subadditivity, the third one follows
from the monotonicity of $v_{i}$, and the last inequality follows from the
fact that $\bm{\succ}$ is a $\alpha$-approximate PNE. We conclude that
$(A_{1},\ldots,A_{n})$ is $\frac{\alpha}{2}$-EF1 with respect to the
underlying valuation functions. ∎

The ${\alpha}/({2-\alpha})$ upper bound of Theorem 4.3 for the additive case
applies to both submodular and subadditive cancelable valuation functions,
leaving a very small gap for the latter. For the submodular case, we improve
this upper bound to ${\alpha}/{2}$.

######  Proposition 4.8.

Let $\alpha,\varepsilon\in(0,1]$. For instances with submodular valuation
functions $\\{v_{i}\\}_{i\in N}$, a $\alpha$-approximate PNE of the Round-
Robin mechanism may not be $(\frac{\alpha}{2}+\varepsilon)$-EF1 with respect
to $\\{v_{i}\\}_{i\in N}$.

###### Proof.

We construct an instance with four agents and nine goods, i.e., $N=[4]$ and
$M=\\{g_{1},g_{2},\ldots,g_{9}\\}$. Let
$1\gg\varepsilon_{1}>\varepsilon_{2}>\varepsilon_{3}>\varepsilon_{4}>\varepsilon_{5}>\varepsilon_{6}$
and $\beta>({1+\varepsilon_{4}})/{2}$. The first three agents have additive
valuation functions, defined as follows:

$v_{1}(g_{j})=\begin{cases}5,&\text{if $j=1$}\\\ \varepsilon_{5},&\text{if
$j=2$}\\\ \varepsilon_{6},&\text{if $j=3$}\\\ 1,&\text{if $j=4$}\\\
2,&\text{if $j=5$}\\\ \varepsilon_{1},&\text{if $j=6$}\\\
\varepsilon_{2},&\text{if $j=7$}\\\ \varepsilon_{3},&\text{if $j=8$}\\\
\varepsilon_{4},&\text{if $j=9$}\end{cases}$

$v_{2}(g_{j})=\begin{cases}\varepsilon_{5},&\text{if $j=1$}\\\ 5,&\text{if
$j=2$}\\\ \varepsilon_{6},&\text{if $j=3$}\\\ 1,&\text{if $j=4$}\\\
\varepsilon_{1},&\text{if $j=5$}\\\ \varepsilon_{2},&\text{if $j=6$}\\\
2,&\text{if $j=7$}\\\ \varepsilon_{3},&\text{if $j=8$}\\\
\varepsilon_{4},&\text{if $j=9$}\end{cases}$

$v_{3}(g_{j})=\begin{cases}\varepsilon_{5},&\text{if $j=1$}\\\
\varepsilon_{6},&\text{if $j=2$}\\\ 5,&\text{if $j=3$}\\\
\varepsilon_{1},&\text{if $j=4$}\\\ \varepsilon_{2},&\text{if $j=5$}\\\
2,&\text{if $j=6$}\\\ \varepsilon_{3},&\text{if $j=7$}\\\
\varepsilon_{4},&\text{if $j=8$}\\\ 1,&\text{if $j=9$}.\end{cases}$

Agent $4$ has an OXS (and, thus, submodular) valuation function that is
defined by the maximum weight matchings in the bipartite graph below.

$g_{1}$$g_{2}$$g_{3}$$g_{4}$$g_{5}$$g_{6}$$g_{7}$$g_{8}$$g_{9}$$5\cdot\beta$$4\cdot\beta$$3\cdot\beta$$2\cdot\beta$$2\cdot\beta-\varepsilon_{4}$1$1-\varepsilon_{3}$$\varepsilon_{1}$$\varepsilon_{2}$

Now consider a bidding profile where the first three agents bid truthfully
(i.e., they bid the strict preference rankings
$\succ^{*}_{1},\succ^{*}_{2},\succ^{*}_{3}$ which are consistent with
$v_{,}v_{2},v_{3}$), while the fourth agent bids the preference ranking
$\succ_{4}$:
$g_{3}\succ_{4}g_{6}\succ_{4}g_{8}\succ_{4}g_{1}\succ_{4}g_{2}\succ_{4}g_{4}\succ_{4}g_{5}\succ_{4}g_{7}\succ_{4}g_{9}$.
It is easy to confirm that the produced allocation is
$(A_{1},A_{2},A_{3},A_{4})=\\{\\{g_{1},g_{4},g_{5}\\},\\{g_{2},g_{7}\\},\\{g_{3},g_{9}\\},\\{g_{6},g_{8}\\}\\}$.

We first examine the first three agents. Agents $1$ and $2$ get their most
valuable goods in this allocation something that implies that there is no
profitable deviation for them. For the same reason they are also envy-free
towards the other agents. Regarding agent $3$, the only bundle that improves
her utility is $\\{g_{3},g_{6}\\}$. However, there is no bid that she can
report and get these two goods. The reason for this is that if she does not
get good $g_{3}$ in round 1 of Mechanism 1 (by not declaring it as her best
good among the available ones), then $g_{3}$ is lost to agent $4$. If, on the
other hand, she gets good $g_{3}$ in round 1 (by declaring it as her best good
among the available ones), then good $g_{6}$ is lost to agent $4$. Therefore,
there is no profitable deviation for her. Finally, it is easy to see that she
is also envy-free towards the other agents.

Moving to agent $4$, we have that

$v_{4}(A_{i})=\begin{cases}v_{4}(g_{1})+4\beta-\varepsilon_{4},&\text{if
$i=1$}\\\ v_{4}(g_{2})+1-\varepsilon_{3},&\text{if $i=2$}\\\
v_{4}(g_{3})+\varepsilon_{2},&\text{if $j=3$}\\\ 1+\varepsilon_{1},&\text{if
$j=4$},\end{cases}$

where $g_{1},g_{2},g_{3}$ are the most valuable goods from sets
$A_{1},A_{2},A_{3}$, respectively, according to agent $4$. Therefore,
$v_{4}(A_{1}\setminus\\{g_{1}\\})>v_{4}(A_{2}\setminus\\{g_{2}\\})>v_{4}(A_{3}\setminus\\{g_{3}\\})$,
and by comparing $v_{4}(A_{4})$ with $v_{4}(A_{1}\setminus\\{g_{1}\\})$ we get
that agent $4$ is $\frac{1+\varepsilon_{1}}{4\beta-\varepsilon_{4}}$-EF1
towards agent 1. The only thing that remains is to explore the possible
deviations of agent 4. Initially, notice that regardless of what agent $4$
declares, she cannot get goods $g_{1},g_{2},g_{3}$ as these are taken in round
1 by the agents that precede her. With that in mind, we will examine what is
the best attainable value through deviating, based on what she gets in round
1. Take note that she can get any goods from $\\{g_{4},g_{5},\ldots,g_{9}\\}$
in round 1 as they are available when her turn comes:

  * •

Agent $4$ gets good $g_{4}$ in round 1. Based on the reported preferences
$\succ^{*}_{1},\succ^{*}_{2},\succ^{*}_{3}$ of the other agents, in round 2 we
have the following: Good $g_{5}$ is lost to agent 1, good $g_{7}$ is lost to
agent 2, and good $g_{6}$ to agent 3. Therefore, only goods $g_{8}$ and
$g_{9}$ remain available for agent 4, and she can get only one of them. Thus,
the maximum attainable value for her is $2\beta+\varepsilon_{1}$.

  * •

Agent $4$ gets good $g_{5}$ in round 1. In that case, based on the declaration
of the rest of the agents, in round 2 we have the following: Good $g_{4}$ is
lost to agent 1, good $g_{7}$ is lost to agent 2, and good $g_{6}$ to agent 3.
Therefore, only goods $g_{8}$ and $g_{9}$ remain available for agent 4, and
once more she can get only one of them. Thus, the maximum attainable value for
her is $2\beta-\varepsilon_{4}+\varepsilon_{1}$.

  * •

Agent $4$ gets good $g_{6}$ in round 1. Based on the reported preferences
$\succ^{*}_{1},\succ^{*}_{2},\succ^{*}_{3}$ of the other agents, in round 2 we
have the following: Good $g_{5}$ is lost to agent 1, good $g_{7}$ is lost to
agent 2, and good $g_{9}$ to agent 3. Therefore, only goods $g_{4}$ and
$g_{9}$ remain available for agent 4. Now observe that
$v_{4}(g_{4},g_{6})=2\beta$ (as this is the value of the maximum matching),
while $v_{4}(g_{9},g_{6})=1+\varepsilon_{2}$. Thus, the maximum attainable
value for her is $2\beta$.

  * •

Agent $4$ gets good $g_{7}$ in round 1. Based on the reported preferences
$\succ^{*}_{1},\succ^{*}_{2},\succ^{*}_{3}$ of the other agents, in round 2 we
have the following: Good $g_{5}$ is lost to agent 1, good $g_{4}$ is lost to
agent 2, and good $g_{6}$ to agent 3. Therefore, only goods $g_{8}$ and
$g_{9}$ remain available for agent 4, and once more she can get only one of
them. Thus, the maximum attainable value for her is
$1-\varepsilon_{3}+\varepsilon_{1}$.

  * •

Agent $4$ gets good $g_{8}$ in round 1. Based on the reported preferences
$\succ^{*}_{1},\succ^{*}_{2},\succ^{*}_{3}$ of the other agents, in round 2 we
have the following: Good $g_{5}$ is lost to agent 1, good $g_{7}$ is lost to
agent 2, and good $g_{6}$ to agent 3. Therefore, only goods $g_{4}$ and
$g_{9}$ remain available for agent 4, and once more she can get only one of
them. Thus, the maximum attainable value for her is $2\beta+\varepsilon_{1}$.

  * •

Agent $4$ gets good $g_{9}$ in round 1. In that case, based on the declaration
of the rest of the agents, in round 2 we have the following: Good $g_{5}$ is
lost to agent 1, good $g_{7}$ is lost to agent 2, and good $g_{6}$ to agent 3.
Therefore, only goods $g_{4}$ and $g_{8}$ remain available for agent 4, and
once more she can get only one of them. Thus, the maximum attainable value for
her is $2\beta+\varepsilon_{2}$.

From the above discussion we get that the maximum value that agent $4$ can
attain through a deviation is $2\cdot\beta+\varepsilon_{1}$. At the same time
$v_{4}(A_{4})=1+\varepsilon_{1}$. By setting
$\alpha=\frac{1+\varepsilon_{1}}{2\cdot\beta+\varepsilon_{1}}$ we trivially
have that $(\succ_{1},\succ_{2})$ is a $\alpha$-approximate PNE. On the other
hand, for a given $\varepsilon>0$, we have that
$\frac{1+\varepsilon_{1}}{2\cdot\beta+\varepsilon_{1}}+\varepsilon$ is
strictly larger than $\frac{1+\varepsilon_{1}}{4\beta-\varepsilon_{4}}$ for
sufficiently small $\varepsilon_{1}$. That is, there is a choice of
$\varepsilon_{1},\ldots,\varepsilon_{6}$ so that the $\alpha$-approximate PNE
$(\succ^{*}_{1},\succ^{*}_{2},\succ^{*}_{3},\succ_{4})$ is not
$\frac{\alpha}{2}+\varepsilon$-EF1. ∎

##  5 Discussion and Future Directions

In this work we studied the existence and fairness guarantees of the
approximate pure Nash equilibria of the Round-Robin mechanism for agents with
cancelable and submodular valuation functions. In both cases, we generalized
the surprising connection between the stable states of the mechanism and its
fairness properties, a connection that was only known for exact equilibria and
additive valuation functions. For the function classes considered, we provide
tight or almost tight bounds, thus giving a complete picture of the strengths
and the limitations of the Round-Robin mechanism for these scenarios. There
are several interesting related directions, some of which we discuss below.

An obvious first direction is to explore function classes beyond the ones
studied here, with XOS or subadditive functions being prominent candidates.
Since our results heavily rely on the properties of cancelable and submodular
functions, it is likely that different approaches are needed for this
endeavour. As we mention in the introduction, a second interesting direction,
related to this one, is the study of the stability and fairness properties of
variants of the Round-Robin mechanism that allow the agents to be more
expressive. Analyzing mechanisms that take as an input value oracles seems to
be highly non-trivial, and although some of our results might transfer in this
setting, we suspect that, in general, strong impossibility results hold
regarding the fairness guarantees of approximate PNE.

Finally, although here we focused on Round-Robin and EF1, most fair division
algorithms have not been considered in the strategic setting. One promising
such algorithm, which is both fundamental in a number of variants of the
problem and simple enough, is the Envy-Cycle-Elimination algorithm of Lipton
et al. [28] which is known to compute EF1 allocations for general non-
decreasing valuation functions. An appealing alternative here is studying the
existence of equilibria of approximation algorithms for MMS allocations. An
impoertant advantage in this case is that once the existence of an approximate
PNE is shown, the corresponding MMS guarantee comes for free (see also the
related discussion in Remark 2.9 of Amanatidis et al. [5]).

## References

  * Akrami et al. [2022] H. Akrami, B. R. Chaudhury, J. Garg, K. Mehlhorn, and R. Mehta.  EFX allocations: Simplifications and improvements.  _CoRR_ , abs/2205.07638, 2022.  doi: 10.48550/arXiv.2205.07638.  URL https://doi.org/10.48550/arXiv.2205.07638.
  * Amanatidis et al. [2017a] G. Amanatidis, G. Birmpas, G. Christodoulou, and E. Markakis.  Truthful allocation mechanisms without payments: Characterization and implications on fairness.  In _Proceedings of the 2017 ACM Conference on Economics and Computation, EC’ 17_ , pages 545–562. ACM, 2017a.
  * Amanatidis et al. [2017b] G. Amanatidis, E. Markakis, A. Nikzad, and A. Saberi.  Approximation algorithms for computing maximin share allocations.  _ACM Trans. Algorithms_ , 13(4):52:1–52:28, 2017b.
  * Amanatidis et al. [2020] G. Amanatidis, E. Markakis, and A. Ntokos.  Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination.  _Theor. Comput. Sci._ , 841:94–109, 2020.
  * Amanatidis et al. [2021] G. Amanatidis, G. Birmpas, F. Fusco, P. Lazos, S. Leonardi, and R. Reiffenhäuser.  Allocating indivisible goods to strategic agents: Pure Nash equilibria and fairness.  In _Proceedings of the 17th International Conference on Web and Internet Economics, WINE 2021_ , volume 13112 of _LNCS_ , pages 149–166, 2021.
  * Amanatidis et al. [2022] G. Amanatidis, H. Aziz, G. Birmpas, A. Filos-Ratsikas, B. Li, H. Moulin, A. A. Voudouris, and X. Wu.  Fair division of indivisible goods: A survey.  _CoRR_ , abs/2208.08782, 2022.  doi: 10.48550/arXiv.2208.08782.  URL https://doi.org/10.48550/arXiv.2208.08782.
  * Aziz et al. [2017a] H. Aziz, S. Bouveret, J. Lang, and S. Mackenzie.  Complexity of manipulating sequential allocation.  In _Proceedings of the 31st AAAI Conference on Artificial Intelligence, AAAI ’17_ , pages 328–334. AAAI Press, 2017a.
  * Aziz et al. [2017b] H. Aziz, P. Goldberg, and T. Walsh.  Equilibria in sequential allocation.  In _Proceedings of the 5th International Conference on Algorithmic Decision Theory, ADT ’17_ , volume 10576 of _LNCS_ , pages 270–283. Springer, 2017b.
  * Aziz et al. [2022] H. Aziz, I. Caragiannis, A. Igarashi, and T. Walsh.  Fair allocation of indivisible goods and chores.  _Autonomous Agents and Multi Agent Systems_ , 36(1):3, 2022.
  * Babaioff et al. [2021] M. Babaioff, T. Ezra, and U. Feige.  Fair and truthful mechanisms for dichotomous valuations.  In _Proceedings of the 35th AAAI Conference on Artificial Intelligence, AAAI 2021_ , pages 5119–5126. AAAI Press, 2021.
  * Barman and Krishnamurthy [2020] S. Barman and S. K. Krishnamurthy.  Approximation algorithms for maximin fair division.  _ACM Trans. Economics and Comput._ , 8(1):5:1–5:28, 2020.
  * Berger et al. [2022] B. Berger, A. Cohen, M. Feldman, and A. Fiat.  Almost full EFX exists for four agents.  In _Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022_ , pages 4826–4833. AAAI Press, 2022.
  * Bouveret and Lang [2014] S. Bouveret and J. Lang.  Manipulating picking sequences.  In _Proceedings of the 21st European Conference on Artificial Intelligence - ECAI 2014_ , volume 263, pages 141–146. IOS Press, 2014.
  * Bouveret and Lemaître [2016] S. Bouveret and M. Lemaître.  Characterizing conflicts in fair division of indivisible goods using a scale of criteria.  _Autonomous Agents and Multi-Agent Systems_ , 30(2):259–290, 2016.
  * Bouveret et al. [2016] S. Bouveret, Y. Chevaleyre, and N. Maudet.  Fair allocation of indivisible goods.  In _Handbook of Computational Social Choice_ , pages 284–310. Cambridge University Press, 2016.
  * Budish [2011] E. Budish.  The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.  _Journal of Political Economy_ , 119(6):1061–1103, 2011.
  * Caragiannis et al. [2009] I. Caragiannis, C. Kaklamanis, P. Kanellopoulos, and M. Kyropoulou.  On low-envy truthful allocations.  In _Proceedings of the 1st International Conference on Algorithmic Decision Theory, ADT 2009_ , volume 5783 of _LNCS_ , pages 111–119. Springer, 2009.
  * Caragiannis et al. [2019] I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang.  The unreasonable fairness of maximum Nash welfare.  _ACM Trans. Economics and Comput._ , 7(3):12:1–12:32, 2019.
  * Caragiannis et al. [2022] I. Caragiannis, J. Garg, N. Rathi, E. Sharma, and G. Varricchio.  Existence and computation of epistemic efx allocations.  _CoRR_ , abs/2206.01710, 2022.  doi: 10.48550/arXiv.2206.01710.  URL https://doi.org/10.48550/arXiv.2206.01710.
  * Chaudhury et al. [2021] B. R. Chaudhury, J. Garg, and R. Mehta.  Fair and efficient allocations under subadditive valuations.  In _Proceedings of the 35th AAAI Conference on Artificial Intelligence, AAAI 2021_ , pages 5269–5276. AAAI Press, 2021.
  * Foley [1967] D. K. Foley.  Resource allocation and the public sector.  _Yale Economics Essays_ , 7:45–98, 1967.
  * Gamow and Stern [1958] G. Gamow and M. Stern.  _Puzzle-Math_.  Viking press, 1958.
  * Ghodsi et al. [2022] M. Ghodsi, M. T. Hajiaghayi, M. Seddighin, S. Seddighin, and H. Yami.  Fair allocation of indivisible goods: Beyond additive valuations.  _Artif. Intell._ , 303:103633, 2022.
  * Halpern et al. [2020] D. Halpern, A. D. Procaccia, A. Psomas, and N. Shah.  Fair division with binary valuations: One rule to rule them all.  In _Proceedings of the 16th International Conference on Web and Internet Economics, WINE 2020_ , volume 12495 of _LNCS_ , pages 370–383. Springer, 2020.
  * Kurokawa [2017] D. Kurokawa.  _Fair Division in Game Theoretic Settings_.  PhD thesis, Carnegie Mellon University, 2017.
  * Lehmann et al. [2006] B. Lehmann, D. Lehmann, and N. Nisan.  Combinatorial auctions with decreasing marginal utilities.  _Games Econ. Behav._ , 55(2):270–296, 2006.
  * Leme [2017] R. P. Leme.  Gross substitutability: An algorithmic survey.  _Games Econ. Behav._ , 106:294–316, 2017.
  * Lipton et al. [2004] R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi.  On approximately fair allocations of indivisible goods.  In _Proceedings of the 5th ACM Conference on Electronic Commerce, EC ’04_ , pages 125–131. ACM, 2004.
  * Manurangsi and Suksompong [2021] P. Manurangsi and W. Suksompong.  Closing gaps in asymptotic fair division.  _SIAM Journal on Discrete Mathematics_ , 35(2):668–706, 2021.
  * Markakis [2017] E. Markakis.  Approximation algorithms and hardness results for fair division with indivisible goods.  In _Trends in Computational Social Choice_ , chapter 12. AI Access, 2017.
  * Markakis and Psomas [2011] E. Markakis and C. Psomas.  On worst-case allocations in the presence of indivisible goods.  In _Proceedings of the 7th International Conference on Web and Internet Economics, WINE 2011_ , volume 7090 of _LNCS_ , pages 278–289. Springer, 2011.
  * Nemhauser et al. [1978] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher.  An analysis of approximations for maximizing submodular set functions \- I.  _Math. Program._ , 14(1):265–294, 1978.
  * Plaut and Roughgarden [2020] B. Plaut and T. Roughgarden.  Almost envy-freeness with general valuations.  _SIAM J. Discret. Math._ , 34(2):1039–1068, 2020.
  * Procaccia [2016] A. D. Procaccia.  Cake cutting algorithms.  In _Handbook of Computational Social Choice_ , pages 311–330. Cambridge University Press, 2016.
  * Psomas and Verma [2022] A. Psomas and P. Verma.  Fair and efficient allocations without obvious manipulations.  In _Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022_ , 2022\.
  * Steinhaus [1949] H. Steinhaus.  Sur la division pragmatique.  _Econometrica_ , 17 (Supplement):315–319, 1949.
  * Varian [1974] H. R. Varian.  Equity, envy and efficiency.  _Journal of Economic Theory_ , 9:63–91, 1974.