# Fair Division with money and prices

Anna Bogomolnaia and Hervé Moulin Adam Smith Business School, University of
Glasgow, U. K., CNRS, France, and Higher School of Economics, St Petersburg,
RussiaAdam Smith Business School, University of Glasgow, U. K., and Higher
School of Economics, St Petersburg, Russia

( February 10, 2022)

###### Abstract

We must divide a finite number of indivisible goods and cash transfers between
agents with quasi-linear but otherwise arbitrary utilities over the subsets of
goods. We compare two division rules with cognitively feasible and privacy
preserving individual messages.

In Sell&Buy agents bid for the role of Seller or Buyer: with two agents the
smallest bid defines the Seller who then charges any a price constrained only
by her winning bid.

In Divide&Choose agents bid for the role of Divider, then everyone bids on the
shares of the Divider’s partition.

S&B dominates D&C on two counts: its guaranteed utility in the worst case
rewards (resp. penalises) more subadditive (resp. superadditive) utilities;
playing safe is never ambiguous and is also better placed to collect a larger
share of the efficient surplus.

Key words: ex ante fairness, guarantees, safe play, Sell & Buy, Divide &
Choose

###### Acknowledgement 1

We are grateful for the comments of participants to the OSGAD meeting at the
University Paris 1, the Israeli Algorithmic Game Theory seminar and the
MEET-2021 conference at the Higher School of Economics. Moulin’s research was
supported by a Blaise Pascal Chair of the Region Ile-de-France, 2020-21.

##  1 Introduction

The fair allocation of indivisible objects is greatly facilitated if the
agents who get few good objects or many bad ones accept compensations in cash
or any other transferable and divisible commodity (workload, stocks, caviar,
bitcoin). Examples of this common practice include the classic rent division
problem ([14], Spliddit.org), the dissolution of a partnership ([9], the Texas
Shoot Out clause to terminate a joint venture111Both parties submit sealed
bids and the party who makes the higher bid buys the company at that price.),
and the NIMBY problem (the allocation of a noxious facility between several
communities [17]).

The familiar assumption that utilities are quasi-linear – each agent can
attach to each bundle of objects a personal “price” and switching from one
bundle to another is exactly compensated by the difference in their prices –
yields a versatile fair division model that the economic literature discussed
with any depth only in the special case of the assignment problem where each
of the $n$ agents must receive at most one object (see the literature review
in section 2).

We initiate the discussion of fair division rules with a finite number of
indivisible goods (freely disposable objects) and money. Utilities are weakly
increasing over subsets of goods but externalities across goods are
arbitrarily complex, exactly like in the combinatorial auction problem ([10]):
if we distribute the $m$ goods in a set $A$, a full description of an agent’s
utility measured in money is a vector of dimension $2^{|A|}-1$.

The key design constraint of such rules is the simplicity of individual
messages: even with a handful of objects it is not cognitively feasible to
report a vector of such large dimension. A dual argument against against
eliciting a full report, even when $A$ is small, is privacy protection: a
message of dimension (much) smaller than $2^{|A|}$ is an advantage in future
bargaining interactions. That a single cut of the cake reveals so little about
the Divider’s preferences, and even less of the Chooser’s, is what makes
Divide&Choose so appealing.

In the new Sell and Buy rule (S&B) we propose, the messages are prices. The
fair division rule implemented on the Spliddit platform routinely elicits
price reports which we take as evidence of the practical applicability of the
price-based S&B rule.

If only two agents divide $m$ goods they bid first to determine the roles of
Seller and Buyer in the next stage. A bid is interpreted as the price the
Seller can charge for all the goods; the agent with the smallest bid $x$ takes
that role. The Seller then chooses a price for every good so that their sum is
$x$ and the Buyer buys at those prices any subset of goods,including all goods
or none. The remaining goods go the the Seller, along with the cash from the
Buyer’s purchase.

It is also possible to adapt the Divide&Choose rule (D&C) to our model with
cash transfers. The first round of bids picks the Divider, this time because
her bid $y$ is the highest. After paying $\frac{1}{n}y$ to each of the other
$n-1$ participants, the Divider selects an allocation in which each of the $n$
shares is a set of goods (possibly empty) plus a cash transfer, such that all
goods are distributed and the sum of the cash transfers is zero.222We also
discuss a version of D&C with the same guarantee but eliciting more
information from the agents: first each agent proposes a partition of the
objects in $n$ shares after which they all bid to select the “best” partition:
see section 6.

Both rules elicit cognitively realistic, if very different, messages. Our
results focus on their performances with respect to ex ante fairness and the
efficiency of the “safe play” by the participants. A message is safe if it
maximises the worst case utility the agent clueless about the preferences and
behaviour of the other – possibly adversarial – participants. More
sophisticated strategies exploiting some information about other participants’
behaviour or preferences are unsafe inasmuch as this information may be wrong.

That worst case utility is called the guarantee offered by the rule and the
first step toward its ex ante fairness is that the guarantee should be the
same for two participants with identical utility functions. The next step is
to make the guarantee as “efficient” as possible in the sense that the sum of
individual guarantees, and/or the outcome of independent safe play captures a
large share of the efficient surplus.

To appreciate the difficulty of taking into account arbitrary complex
externalities, consider on the contrary the case of utilities additive over
perfectly substitutable objects and in money too: they are described by an
$m$-dimensional vector $(u_{a})_{a\in A}$ and utility for the subset $S$ of
$A$ is $u(S)=\sum_{a\in S}u_{a}$. The compelling division rule is the familiar
Multi Auction (MA): each agent $i$ places a bid $\beta_{ia}$for each good $a$,
the highest bidder $i^{\ast}$ on $a$ gets this object and pays
$\frac{1}{n}\beta_{i^{\ast}a}$ to each of the $n-1$ other agents. Clearly the
truthful bid $u_{ia}$ on each $a$ is the unique safe play. MA is fair ex ante:
it guarantees to each agent $i$ her Fair Share $\frac{1}{n}u_{i}(A)$ which is
the best guarantee we can offer in the additive context. It is fair ex post:
by playing safe I will not envy anyone else’s allocation. And if all agents
play safe the efficient allocation is selected.

MA can be used as well with our much more complex utilities. Now the marginal
utility of adding good $a$ to a subset of goods varies so there is no
“truthful” bid on $a$. The safe bid solves a program similar to the one we
shall use for the S&B rule, but delivers in all problems a very low guarantee,
much below those of the S&B and D&C rules. It also fares badly in terms of
efficiency and ex post fairness. See subsection 11.1 in the Appendix.

In our model it is still feasible to guarantee the utility
$\frac{1}{n}u_{i}(A)$ to each agent $i$ but it is a untenably coarse
interpretation of ex ante fairness that fails to reward agents with
subadditive utilities and to penalise those with superadditive utilities. This
is the normative motivation of our analysis, captured by contrasting two
extreme utilities that play a major role throughout.

Example 0. We divide $m\geq 2$ identical goods between two agents Frugal and
Greedy with the following utilities

$u_{F}(S)=1\text{ for all }S,\varnothing\neq S\subseteq A\text{ ;
}u_{F}(\varnothing)=0$ $u_{G}(S)=0\text{ for all }S,\varnothing\subseteq
S\varsubsetneq A\text{ ; }u_{G}(A)=1$

Frugal is content with any single good – her utility is maximally sub-additive
– while Greedy needs all goods to derive any utility – his utility is
maximally super-additive.

We submit that it is not fair to offer ex ante the same guarantee
$\frac{1}{2}$ to both agents – achieved by auctioning the bundled goods as in
MA. Under the veil of ignorance where we (as impartial observer) don’t know
person X who will share the goods with Frugal, we should take into account
that together Frugal and X can produce at least as much utility surplus – and
often much more – than if X is paired with Greedy. For this reason we dismiss
$\frac{1}{n}u_{i}(A)$ as a “repugnant” interpretation of ex ante fairness.
This benchmark utility still plays a significant role in our analysis: we will
call it agent $i$’s Familiar Share (FS) and regard it as a compelling
guarantee only for additive utilities.

The Responsiveness property says that we should guarantee strictly more than
her FS to Frugal, which implies that Greedy is guaranteed strictly less than
his FS. The Positivity property, by contrast, protects Greedy: it requires to
give him some positive guarantee because his equal rights to the goods should
amount to something regardless of his uncompromising utility.

Divide&Choose guarantees to Greedy a utility of $\frac{1}{4}$, half of his FS.
As the Divider he secures $\frac{1}{2}$ by offering to pay $\frac{1}{2}$ for
the bundled objects, or be paid $\frac{1}{2}$ and get no object; as the
Chooser being offered two non empty piles of objects with zero transfers, he
will get no surplus at all; so his safe bid of $\frac{1}{4}$ to be the Divider
guarantees a benefit of $\frac{1}{4}$ whatever his role in the second stage.

By contrast Frugal can secure a utility of $\frac{3}{4}$: as the Divider she
gets the full benefit $1$ by proposing two non empty piles and zero transfers;
as a Chooser the sum of her utility for the two shares is at least $1$ so one
of them at least gives her utility $\frac{1}{2}$; then a bid of $\frac{1}{4}$
guarantees $1-\frac{1}{4}$ if she Divides, and $\frac{1}{2}+\frac{1}{4}$ if
she Chooses.

The guarantees offered by Sell&Buy to Frugal and Greedy are more nuanced: they
take into account that the contrast between their preferences increases with
the number $m$ of goods to divide. Specifically Greedy’s guaranteed utility is
$\frac{1}{m+1}$ and Frugal’s is $\frac{m}{m+1}$. S&B sensibly penalises Greedy
and rewards Frugal more and more than D&C as $m$ grows.

Frugal’s safe bid $\frac{m}{m+1}$ in stage 1 goes as follows. As Seller she
will charge $\frac{1}{m+1}$ per good and end up with utility $\frac{m}{m+1}$
if Buyer buys everything, and at least $1$ if Buyer buys at least one good. As
Buyer she will faces a total price of at most $\frac{m}{m+1}$ so at least one
good will cost $\frac{1}{m+1}$ or less and buying just that good guarantees
the benefit $\frac{m}{m+1}$.

Greedy’s safe bid is $\frac{m}{m+1}$ as well. As Seller charging
$\frac{1}{m+1}$ per good he will get $\frac{1}{m+1}$by selling one or more
goods, and $1$ by selling nothing; as Buyer the whole bundle will cost him at
most $\frac{m}{m+1}$.

Responsiveness and Positivity of guarantees together reveal a surprising
tension between ex ante and ex post fairness, when the latter is taken to mean
– as in essentially all the fair division literature – that the final
allocation is Envy Free. This simple fact is already apparent when we divide
the $m$ goods between Frugal and Greedy: it is easy to check that the envy
free allocations are of two types: someone eats $A$ and pays $\frac{1}{2}$ to
the other; or they each get at least one good and no transfer takes place. The
former violates Responsiveness because it gives their FS utility to both
agents, and the latter violates Positivity for Greedy.

##### our punchlines

Both the Sell&Buy and Divide&Choose division rules offer new interpretations
of ex ante fairness rewarding sub-additive utilities and penalising super-
additive ones. The price message in S&B allows its guarantee more flexibility
than the partition in D&C does in response to the shape of utilities.

Playing safe in either rule cannot extract the efficient surplus because the
messages reveal much less than full utilities. But D&C is particularly bad
when utilities are nearly additive or when one agent values each good much
more than any of the others, two problems that the S&B avoids.

Preliminary numerical experiments suggest S&B captures more of the efficient
surplus than D&C, on average if not necessarily in the worst case. This is
plausible because the S&B rule processes more information than D&C.

##### overview of the paper

After the literature review in section 2 and the basics of the model in
section 3, we define guarantees and the Positivity and Responsiveness
properties in section 4. There we also describe simple auctions implementing
the fixed partition guarantees, a key ingredient of the D&C rules. Section 5
introduces two critical utility levels: the Maxmin utility that an agent can
secure as the Divider is an upper bound on all guarantees; the minMax utility
that she can secure as a Chooser against an adversarial Divider is a lower
bound on all reasonable guarantees: Proposition 1.

Section 6 defines the D&C rule and computes its safe play and guarantees:
Proposition 2. Section 7 does the same for the S&B rule – Proposition 3 – and
gives full computations in the simple case of two agents dividing identical
goods – Proposition 4.

The systematic comparison of the S&B and D&C guarantees (and the FS) in
section 8 starts by some common properties: they all increase in the number of
goods and decrease in the number of agents: Proposition 5. Then Propositions 6
and 7 formalises their differences revealed in a handful of examples. Compared
to the benchmark FS, the range of the S&B guarantee is much larger than that
of the D&C one: Proposition 7. Unlike D&C, the S&B guarantee coincides with FS
on a large subset of utilities with non empty interior: Proposition 6.

Section 9 offers two results toward the general statement, to be checked by
systematic numerical experiments, that if all participants play safely the
outcome in S&B collects on average a bigger share of the efficient surplus
than in D&C.

With two agents and for both rules the profile of guarantees reduces the
bargaining gap, i. e., it distributes at least the total utility at the worst
partition of the goods: Lemma 10. But with three or more agents this is no
longer true for D&C, while we conjecture that it is still true for S&B.

The final Proposition 8 considers the situation where agent $1$’s marginal
utility for each good dominates that of every other agent: then the S&B safe
play achieves full efficiency, i.e., gives all the goods to agent $1$, while
under D&C all but a $\frac{1}{n}$-th share of the efficient surplus can be
lost.

All difficult proofs are gathered in the Appendix, section 11.

##  2 Relevant literature

Allowing cash compensations to smooth out indivisibilities of objects has been
essentially ignored by the first four decades of the theoretical literature on
fair division, if we except the cogent discussion by Steinhaus of what we call
above the Multi Auction rule for additive utilities ([24] p. 317).

This changed with the microeconomic discussion of the assignment problem. Each
agent wants at most one object and utilities are only assumed increasing in
money but not necessarily quasi-linear; monetary compensations can restore
fairness interpreted as Envy Freeness and even a version of the competitive
equilibrium with equal incomes: [25] [1]]. The quasi-linear case of the model
is discussed in [2] selecting a canonical envy free allocation, in [9] for the
dissolution of partnership, in [17] for adressing the NIMBY problem, and
currently implemented on the user-friendly Spliddit platform [15].

In the assignment problem ex ante fairness is captured by the unanimous
utility: the best equal utility in the hypothetical problem where everyone
else shares my preferences ([20], [26]). This is unambiguously the best
possible guarantee and it is compatible with Envy Freeness.

In our model the set of allocations and utilities are vastly more complex than
in an assignment problem and the unanimity utility – that we call the Maxmin
utility – is an upper bound on guarantees but not itself a feasible guarantee.
Our newfound critique of Envy Freeness (stated as Lemma 3 in section 4.2)
complements the normative objections developed in [20].

The search for a practical and appealing guarantee started the mathematical
cake cutting literature ([23], [18]) and is a prominent theme in the vibrant
21st century algorithmic literature on fair division surveyed in [21], [4] and
[27]. The standard model has utilities additive over objects and no cash
transfers or lotteries, so the definition of a convincing guarantee is
complicated by the presence of “un-smoothable” indivisibilities.Our Maxmin and
minMax utilities (section 5) are the counterpart of, respectively, the
influential MaxMinShare due to Buddish [8] and its dual MinMaxShare [7]. The
MaxMinShare is almost a feasible guarantee (it is not feasible in extremely
rare configurations [22]); its dual minMax version is strongly unfeasible: the
exact opposite holds in our model (Lemma 4 section 5), as well as when we
divide a non atomic cake and utilities are continuous but otherwise arbitrary:
see [6], [3].

Other definitions of guarantees are also discussed in the algorithmic
literature, e. g. [5], as are guarantees adjusted to the granularity of the
utilities in [13].

In the first of our two $n$-person versions of the Divide&Choose rule (section
6) the participants bid first for the role of Divider, which is similar to and
inspired by a similar auction in [11] and [12] for implementing the
egalitarian-equivalent division rule when we distribute Arrow-Debreu
commodities.

##  3 Basic definitions and notation

##### objects and money

The finite set $A$ with cardinality $m$ and generic elements $a,b,\cdots$,
contains the indivisible objects that must all be distributed between the $n$
agents in the set $N$ with generic elements $i,j,\cdots$.

A $n$-partition $\pi$ of $A$ is a list $\pi=\\{S_{k}\\}_{k=1}^{n}$ of possibly
empty and pairwise disjoint subsets of $A$ such that
$A={\large\cup}_{k=1}^{n}S_{k}$: up to $n-1$ shares can be empty. The set of
$n$-partitions is $\mathcal{P}(n;A)$ if the shares $S_{k}$ are not assigned to
specific agents, and $\mathcal{P}(N;A)$ if they are.

Money is available in unbounded quantities to perform transfers
$t=(t_{i})_{i\in N}$ that are balanced, $\sum_{N}t_{i}=0$; the set of such
transfers is $\mathcal{T}(N)$. An allocation is a pair
$(\pi,t)\in\mathcal{P}(N;A)\times\mathcal{T}(N)$.

##### utilities

Each agent $i$ is endowed with a quasi-linear utility
$u_{i}\in\mathbb{R}^{2^{A}}$ over shares, with the important normalisation
$u_{i}(\varnothing)=0$: her utility from the allocation $(\pi,t)$ is
$u_{i}(S_{i})+t_{i}$. The marginal utility of object $a$ at $S\subseteq A$ for
utility $u$ is $\partial_{a}u(S)=u(S\cup a)-u(S\diagdown a)$. We assume
throughout the paper that all objects are goods: $\partial_{a}u_{i}(S)\geq 0$
for all $S\subseteq A$; utility functions can be any (weakly) inclusion
increasing non negative function on $2^{A}$, and $\mathcal{M}^{+}$ is our
notation for this domain.

The utility $u$ is additive if for all $a\in A$ the marginal
$\partial_{a}u(S)=u_{a}$ is independent of $S$; in this case we write
$u_{S}=\sum_{S}u_{a}$ instead of $u(S)$.

We often use the following cover operation to generate examples in the domain
$\mathcal{M}^{+}$ . Fix a subset $\\{S_{k};1\leq k\leq K\\}$ of
$2^{A}\diagdown\varnothing$ and $K$ positive utilities $v_{k}$; the cover of
the subset $\\{(S_{k},v_{k})\\}$ of
$2^{A}\diagdown\varnothing\times\mathbb{R}_{+}$ is the smallest utility $u$ in
$\mathcal{M}^{+}$ such that $u(S_{k})=v_{k}$ for all $k$:

$u(S)=\max_{k:S_{k}\subseteq S}v_{k}\text{ ; }u(S)=0\text{ if }S_{k}\nsubseteq
S\text{ for all }k$

For instance the Greedy utility $u_{G}$ in section 1 is the cover of
$\\{(A,1)\\}$ while the Frugal utility $u_{F}$ is the cover of $\\{(a,1);a\in
A\\}$.

##### efficiency

A $N$-profile of utilities is $\overrightarrow{u}=(u_{i})_{i\in
N}\in\mathcal{M}^{+}{}^{N}$ and if $\pi\in\mathcal{P}(N;A)$ we write
$\overrightarrow{u}(\pi)=\sum_{i\in N}u_{i}(S_{i})$. The unanimity profile
where all agents have the same utility $u$ is written $[u]$.

The efficient surplus at profile $\overrightarrow{u}$ is
$\mathcal{W}(\overrightarrow{u})=\max_{\pi\in\mathcal{P}(N;A)}\overrightarrow{u}(\pi)$.
Recall an easy but critical consequence of the quasi-linearity assumption: the
allocation $(\pi^{\ast},t)\in\mathcal{P}(N;A)\times\mathcal{T}(N)$ is
efficient (Pareto optimal: PO) if and only if $\pi^{\ast}$ maximises
$\overrightarrow{u}(\pi)$ over $\mathcal{P}(N;A)$: Pareto optimality is
independent of the balanced cash transfers.

##### implementation

In an arbitrary $n$-agent mechanism agent $i$’s strategy is safe if it
delivers to $i$ the largest “worst case” utility against all other agents who
play adversarially against $i$ after seeing $i$’s strategy. That utility is
the guarantee implemented by this mechanism: it only depends upon the
mechanism including $n$ and agent $i$’s utility function.

In our model as always many rules can implement the same guarantee: an example
is the two versions of Divide&Choose in section 6. We systematically omit many
tie-breaking details from the description of rules, and the reader will find
it easy to check that they (the details) never affect the guarantee they
implement.

We will also discuss the efficiency performance of a rule at the outcome
resulting from the simultaneous safe play by all agents; if multiple choices
of safe play or tie-breaking details affect the outcome, we focus on the least
efficient possible outcome. This performance is meaningful in the fully
decentralised context where no agent’s choice of strategy uses any information
about other agents. Naturally this restriction does not apply to a guarantee:
its ex ante protection applies against all possible moves of the other agents
including highly strategic moves based on knowledge of my own utility.

##  4 Guarantees, Positive and Responsive

Definition 1: An $n$-person guarantee is a mapping $\mathcal{M}^{+}\ni
u\rightarrow\Gamma_{n}(u)\in\mathbb{R}_{+}$ such that

$\sum_{i\in N}\Gamma_{n}(u_{i})\leq\mathcal{W}(\overrightarrow{u})\text{ for
each }\overrightarrow{u}\in\mathcal{M}^{+}{}^{N}$ (1)

The set of $n$-guarantees on $A$ is written $\mathcal{G}(A;n)$.

Guarantees are anonymous by construction: they do not discriminate between
agents on the basis of their name. The three guarantees getting most of our
attention, Familiar Share, Sell&Buy, Divide&Choose are also neutral, i. e.,
oblivious to the name of the objects in $A$: the definition of a neutral
guarantee only depends upon the numbers of objects and agents.

The simplest guarantee is the Familiar Share
$\Gamma_{n}^{FS}(u)=\frac{1}{n}u(A)$: indeed
$u_{i}(A)=\overrightarrow{u}(\pi)$ for the partition $\pi$ giving all goods to
$i$.

More generally to any $\pi\in\mathcal{P}(n;A)$ we associate the
$\pi$-guarantee

$\Gamma_{n}^{\pi}(u)=\frac{1}{n}[u](\pi)=\frac{1}{n}\sum_{k=1}^{n}u(S_{k})\text{
for all }u\in\mathcal{M}^{+}$

and we call $\Gamma_{n}^{\pi}$ a fixed partition guarantee.

To check inequality (1) at profile $\overrightarrow{u}=(u_{i})_{i\in N}$
assign the shares of $\pi$ to agents in $N$ arbitrarily, pick a circular
permutation $\sigma$ of $N$ and sum up the inequalities $\sum_{i\in
N}u_{i}(S_{\sigma^{k}(i)})\leq\mathcal{W}(\overrightarrow{u})$ for all
$k=0,\cdots,n-1$.

The Familiar Share terminology comes from the special case of additive
utilities where we have long known that it is the compelling guarantee (as
explained in section 5 after Proposition 1).

###  4.1 three simple auction rules

The simple Bundled Auction (BA) implements $\Gamma_{n}^{FS}$: each agent $i$
submits a non negative bid $\beta_{i}$ that the rule interprets as this
agent’s utility for the entire set $A$; (one of) the highest bidder(s)
$i^{\ast}$gets $A$ and pays $\frac{1}{n}\beta_{i}$ to each of the $n-1$ other
agents.

The only safe bid in BA is the truthful one $\beta_{i}=u_{i}(A)$: it
guarantees to agent $i$ her Familiar Share $\frac{1}{n}u_{i}(A)$ while any
other bid risks delivering a smaller benefit: this is clear for a winning
overbid, and for an underbid losing to a bid between $\beta_{i}$and
$u_{i}(A)$.333The tie break rule is irrelevant and the safe strategy does not
change if the winner only pays $\frac{1}{n}$-th of the second highest price to
each loser.

The $\pi$-auction and averaging-auction we introduce now are the key
ingredients of the Divide&Choose rules in section 6.

The $\pi$-auction implements the $\pi$-guarantee. Given
$\pi=\\{S_{k}\\}_{k=1}^{n}$ and the set $N$, each agent $i$ reports a vector
$t^{i}=(t_{k}^{i})_{k\in[n]}\in\mathcal{T}(n)$ of balanced transfers over
those shares (with the notation $[n]=\\{1,\cdots,n\\}$).

Write $\mathcal{C}$ for the set of bijections $\sigma$ of $N$ into $[n]$. An
optimal assignment of $\pi$ at $t=(t^{i})_{i\in N}$ is (one of) the
bijection(s) $\sigma^{\ast}\in\mathcal{C}$ minimising $\sum_{i\in
N}t_{\sigma(i)}^{i}$ over $\mathcal{C}$ (the interpretation of optimality
comes below). Because each vector $t^{i}$ is balanced, the slack
$\delta=\sum_{j\in N}t_{\sigma^{\ast}(j)}^{j}$is negative or zero. After each
agent $j$ is “paid” $t_{\sigma^{\ast}(j)}^{j}$ (a cash handout if
$t_{\sigma^{\ast}(j)}^{j}>0$, a tax if $t_{\sigma^{\ast}(j)}^{j}<0$) the
remaining cash surplus $\delta$ is divided equally between all agents. Agent
$i$’s final allocation is
$(S_{\sigma^{\ast}(i)},t_{\sigma^{\ast}(i)}^{i}-\frac{1}{n}\delta)$.

What is the agent $i$’s worst utility by reporting $t^{i}\in\mathcal{T}(n)$?
Check first that any $\sigma$ in $\mathcal{C}$ can be selected as uniquely
optimal for some reports of the other agents. This happens if we pick some
$\varepsilon>0$ and the reports $t^{j},j\neq i$ are

$t_{\sigma(j)}^{j}=t_{\sigma(j)}^{i}-\varepsilon\text{ ;
}t_{k}^{j}=t_{k}^{i}+\frac{1}{n-1}\varepsilon\text{ for all }k\neq\sigma(j)$

In this case the slack is $\delta=-(n-1)\varepsilon$ and our agent’s final
utility is $u_{i}(S_{\sigma(i)})+t_{\sigma(i)}^{i}+\frac{n-1}{n}\varepsilon$.
As $\sigma$ and $\varepsilon$ were arbitrary we conclude that $i$’s utility
could be as low as $\min_{k\in[n]}u_{i}(S_{k})+t_{k}^{i}$. The unique choice
of $t^{i}$ maximising the latter equalises $i$’s utility across these shares

$u_{i}(S_{k})+t_{k}^{i}=u_{i}(S_{\ell})+t_{\ell}^{i}\text{ for all
}k,\ell\in[n]$ (2)

and secures the utility
$\frac{1}{n}\sum_{k\in[n]}u_{i}(S_{k})=\frac{1}{n}[u_{i}](\pi)$, while any
other report is unsafe. We just proved

Lemma 1 The $\pi$-auction implements the $\pi$-guarantee, and the unique safe
play is to report the transfers equalising one’s utility across the shares of
$\pi$ (as in (2)).

If all agents report safely, an assignment of the shares in $\pi$ is efficient
if and only if the corresponding transfers in (2) have the smallest sum. Thus
the $\pi$-auction interprets the report $t^{i}$ as revealing the utilities
$u_{i}(S_{k}),k\in[n]$, up to an additive constant (except of course if agent
$i$ reports – unsafely – different transfers for two empty shares).

The set $\mathcal{G}(A;n)$ of $n$-guarantees is clearly convex (it is defined
by inequalities (1)) and the canonical way to implement the average
$\frac{1}{\rho}\sum_{r=1}^{\rho}\Gamma_{n}^{r}$ of an arbitray set of
guarantees is the averaging-auction. Each agent $i\in N$ must report a vector
$t^{i}=(t_{r}^{i})_{r\in[\rho]}\in\mathcal{T}(\rho)$ of balanced transfers
over those guarantees. The rule interpretes $t^{i}$ as equalising the
utilities $\Gamma_{n}^{r}(\widetilde{u}_{i})$

$\text{for all }r,r^{\prime}\text{:
}\Gamma_{n}^{r}(\widetilde{u}_{i})+t_{r}^{i}=\Gamma_{n}^{r^{\prime}}(\widetilde{u}_{i})+t_{r^{\prime}}^{i}=\frac{1}{\rho}\sum_{r=1}^{\rho}\Gamma_{n}^{r}(\widetilde{u}_{i})$
(3)

and it selects a guarantee $\Gamma_{n}^{r^{\ast}}$ such that
$r^{\ast}\in\arg\min_{r\in\rho}\sum_{i\in
N}t_{r}^{i}=\arg\max_{r\in\rho}\sum_{i\in
N}\Gamma_{n}^{r}(\widetilde{u}_{i})$. The slack $\theta=\sum_{j\in
N}t_{r^{\ast}}^{j}$ is negative or zero, each agent $i$ receives the transfer
$t_{r^{\ast}}^{i}-\frac{1}{n}\theta$ and the guarantee $\Gamma_{n}^{r^{\ast}}$
is implemented.

Lemma 2 The averaging-auction implements the average guarantee
$\frac{1}{\rho}\sum_{r=1}^{\rho}\Gamma_{n}^{r}$, and the unique safe play is
to report the transfers equalising one’s utility across guarantees (as in
(3)).

The omitted proof is similar to that of Lemma 1.

Remark: It is just as easy to implement any convex combination of guarantees
$\sum_{r=1}^{\rho}\lambda_{r}\Gamma_{n}^{r}$ where each $\lambda_{r}$ is
positive and $\sum_{r=1}^{\rho}\lambda_{r}=1$. Each agent $i$ reports a vector
of $\lambda$-balanced transfers $t^{i}$,
$\sum_{r=1}^{\rho}\lambda_{r}t_{r}^{i}=0$, and the rule proceeds as before: it
implements $\Gamma_{n}^{r^{\ast}}$ where $r^{\ast}$ minimises $\sum_{i\in
N}t_{r}^{i}$ so that the slack $\theta=\sum_{i\in N}t_{r^{\ast}}^{i}$ is still
non positive and $i$ receives $t_{r^{\ast}}^{i}-\frac{1}{n}\theta$. The safe
strategy is to choose $\lambda$-balanced transfers $t^{i}$ equalising
utilities as in (3).

###  4.2 Positivity and Responsiveness

Definition 2 The $n$-guarantee $\Gamma_{n}\in\mathcal{G}(n,A)$ is

Positive if for all $u\in\mathcal{M}^{+}:\Gamma_{n}(u)>0\Longrightarrow
u(A)>0$

Responsive if $\Gamma_{n}(u_{F})>\frac{1}{n}u_{F}(A)$

Positivity applies to all utilities except the null one, so if $\Gamma_{n}$ is
weakly increasing in $u$ (as are all the guarantees we discuss: Proposition 4
section 8), it simply requires $\Gamma_{n}(\lambda u_{G})>0$ for all
$\lambda>0$.

Responsiveness implies the strictly weaker inequality
$\Gamma_{n}(u_{G})<\frac{1}{n}u_{G}(A)$: simply apply (1) to a $n$-profile
with one $u_{F}$ and the rest $u_{G}$ utilities, where theefficient surplus is
$1$.

Among the fixed partition guarantees, only $\Gamma_{n}^{FS}$ is Positive; all
fixed partition guarantees are Responsive, with the single exception of
$\Gamma_{n}^{FS}$.444So a convex mixture of $\Gamma_{n}^{FS}$ with some other
$\pi$-guarantees meets both properties, for instance
$\frac{1}{2n}u(A)+\frac{1}{2n}\sum_{A}u(a)$ if $n=m$.

The next result formalises the important trade-off of our two normative
requirements with Envy Freeness, the standard interpretation of ex post
fairness. Recall that the allocation $(\pi,t)$ is Envy Free if
$u_{i}(S_{i})+t_{i}\geq u_{i}(S_{j})+t_{j}$ for all $i,j\in N$.

Lemma 3 If $|A|\geq 2$ and the $n$-guarantee $\Gamma_{n}$ in $\mathcal{M}^{+}$
is Positive and Responsive, it is incompatible with Envy Freeness: at some
profile $\overrightarrow{u}\in\mathcal{M}^{+N}$ at least one agent is envious
in every envy free allocation.

Proof: in the two agent problem (Greedy, Frugal) we saw that envy free
allocations either give the utility $\frac{1}{2}$ to both agents, or give zero
to Greedy. For a general $n$ the argument is the same in the problem with
$n-1$ Greedy and one Frugal agents.

Note that the safe play in the BA ensures Envy Freeness for that agent,
whether other agents are playing safe or not.

##  5 Maxmin and minMax utilities

The recent literature on fair division pays close attention to these two
canonical utility levels inspired by Divide&Choose for cake-cutting, but
playing a role in many other models. We adapt them as follows. Recall the
notation $[u]$ for the unanimity profile where all agents have utility $u$.

Definition 3 Fix $A,n$ and $u\in\mathcal{M}^{+}$.

$i)$ the Maxmin utility at $u$ is
$Maxmin_{n}(u)=\frac{1}{n}\max_{\pi\in\mathcal{P}(n;A)}[u](\pi)$; it is the
largest utility agent $u$ can secure by choosing an (anonymous) allocation
$(\pi,t)\in\mathcal{P}(n;A)\times\mathcal{T}(n)$ and eating his worst share
$(S_{k},t_{k})$ of that allocation.

$ii)$ the minMax utility at $u$ is
$minMax_{n}(u)=\frac{1}{n}\min_{\pi\in\mathcal{P}(n;A)}[u](\pi)$; it is the
largest utility agent $u$ can secure by picking her best share in the worst
possible (anonymous) allocation
$(\pi,t)\in\mathcal{P}(n;A)\times\mathcal{T}(n)$.

Given an $n$-partition $\pi=\\{S_{k}\\}_{k\in[n]}$ of $A$, the $\pi$-auction
guarantees the utility $\frac{1}{n}[u_{i}](\pi)$ to each agent $i$: therefore
$i$ reaches her $Maxmin$ utility if she can choose $\pi$, and at least her
$minMax$ one if the choice of $\pi$ is adversarial.

Lemma 4 Fix $A$, $n$ and the domain $\mathcal{M}^{+}$

$i)$ $\mathcal{M}^{+}\ni u\rightarrow Maxmin_{n}(u)$ is not a $n$-guarantee
(inequality (1) fails)

$ii)$ but it is an upper bound for every guarantee
$\Gamma_{n}\in\mathcal{G}(A;n)$:

$\Gamma_{n}(u)\leq Maxmin_{n}(u)\text{ for all }u\in\mathcal{M}^{+}$

$iii)$ $\mathcal{M}^{+}\ni u\rightarrow minMax_{n}(u)$ is a $n$-guarantee:
$minMax_{n}(\cdot)\in\mathcal{G}(A;n)\vskip 3.0pt plus 1.0pt minus 1.0pt$

The proof is easy.555All three statements hold in the cake-cutting model
(Bogomolnaia and Moulin (201X)), but there the proof of $iii)$ is hard! For
$ii)$ we fix $\Gamma_{n},u,$and $n$. Inequality (1) at the unanimity profile
$[u]$ for all $i$ is $n\Gamma_{n}(u)\leq\max_{\pi\in\mathcal{P}(n;A)}u(\pi)$
as desired. For $i)\ $one checks easily

$Maxmin_{n}(u_{F})=\min\\{1,\frac{m}{n}\\}\text{ and
}Maxmin_{n}(u_{G})=\frac{1}{n}$

so (1) fails at the $n$-profile with one $u_{F}$ agent and all others are
$u_{G}$ because $W(\overrightarrow{u})=1$. Note that this is not a knife edge
situation: the set of profiles where the corresponding profile of Maxmin
utilities is not feasible is open in $\mathbb{R}_{+}^{2^{A}}$.

For $iii)$ note that for any fixed partition guarantee
$\Gamma_{n}^{\pi}(u)=\frac{1}{n}[u](\pi)\geq minMax_{n}(u)$ for all $u$, so
that (1) holds for the latter as well. This also shows that the minMax
guarantee can easily be improved for instance $minMax_{2}(u_{G})=0$ ;
$minMax_{2}(u_{F})=\frac{1}{2}$. $\blacksquare\vskip 3.0pt plus 1.0pt minus
1.0pt$

Our next result, technically very simple, shows an important benefit of
choosing a guarantee in the “duality interval”
$[minMax_{n}(u),Maxmin_{n}(u)]$. Write $\mathcal{S}up$ and $\mathcal{S}ub$ for
the sub-domains of superadditive and subadditive utilities: in $\mathcal{S}up$
we have $u(S)+u(T)\leq u(S\cup T)$ for all disjoint $S,T$ ; and the opposite
inequality in $\mathcal{S}ub$.

Proposition 1 Suppose the guarantee $\Gamma_{n}$ is such that

$\Gamma_{n}(u)\in[minMax_{n}(u),Maxmin_{n}(u)]\text{ for all
}u\in\mathcal{M}^{+}$ (4)

Then $\Gamma_{n}(u)=\frac{1}{n}u(A)$ if $u$ is additive;
$\Gamma_{n}(u)\geq\frac{1}{n}u(A)$ if $u$ is subadditive; and
$\Gamma_{n}(u)\leq\frac{1}{n}u(A)$ if $u$ is superadditive.

Clearly if $u\in\mathcal{S}ub$ (resp. $u\in\mathcal{S}up$) we have
$u(A)=\min_{\pi\in\mathcal{P}(n;A)}[u](\pi)$ (resp.
$\max_{\pi\in\mathcal{P}(n;A)}[u](\pi)$) therefore (4) implies the desired
inequalities.

If $u$ is additive $Maxmin_{n}(u)=\frac{1}{n}u(A)$, so by statement $ii)$ in
Lemma 4 the Familiar Share is the best possible guarantee and the compelling
interpretation of ex ante fairness. The other two inequalities are a weak form
of the normative principle conveyed by the Responsiveness property.

Note that property (4) is not very restrictive: it is clearly satisfied by the
Familiar Share, the fixed partitions guarantees $\Gamma_{n}^{\pi}$, the D&C
and S&B guarantees defined shortly, and their convex combinations.

In subsection 11.1 of the Appendix we describe the plausible Multi Auction
rule and show that its guarantee falls outside the duality interval, often
strictly smaller than the $minMax$ guarantee. We dismiss that rule for this
very reason.

Remark: there is a precise connection between the duality interval in (4) and
Envy Freeness, confirming the trade-off between ex ante and ex post fairness
in Lemma 3 above. At an envy free allocation, it is clear that every agent $i$
gets at least her $minMax_{n}(u_{i})$ utility. Conversely if the single-valued
rule $(\mathcal{M}^{+})^{N}\ni(u_{i})_{i\in
N}\rightarrow(\pi,t)\in\mathcal{P}(N;A)\times\mathcal{T}(N)$ is efficient and
envy-free, then it implements precisely the $minMax$ guarantee. For each
utility function $u_{i}$ we can complete a profile $(u_{i},u_{-i})$ at which
the rule gives to agent $i$ precisely his $minMax_{n}(u)$ utility.666Proof:
Fix $u_{1}\in\mathcal{M}^{+}$ and $\pi=(S_{k})_{k=1}^{n}$ achieving
$\min_{\pi\in\mathcal{P}(n;A)}[u_{1}](\pi)$, and a positive number $\delta$.
Construct a profile where the common utility $v$ of the $n-1$ other agents is
the cover of the sequence $\\{(S_{k},u_{1}(S_{k})+\delta);k\in[n]\\}$. If
$\delta$ is very large any assignment of the shares $S_{k}$ to the agents is
efficient (and any other efficient partition distributes the same utilities
pre-transfers). By the construction of utility $v$, at an envy free and
efficient allocation the transfers make agent 1 indifferent between all the
shares so her utility is $minMax_{n}(u)$.

##  6 Two Divide&Choose rules

The two rules have the same guarantee, their building blocks are the
$\pi$-auction and averaging-auction in subsection 4.1.

Definition 4 Divide&Choose${}_{n}^{\mathbf{1}}$

stage 1: run a simple auction for the role of Divider; the winner $i$’s bid
$\beta_{i}\geq 0$ is (one of) the highest bid(s)

stage 2: agent $i$ pays $\frac{1}{n}\beta_{i}$ to every other agent and picks
a partition $\pi=\\{S_{k}\\}_{k=1}^{n}$ in $\mathcal{P}(n,A)$

stage 3: run the $\pi$-auction.

In the second rule the initial bidding to become the Divider is replaced by a
stage in which each agent $i$ proposes her own partition (as if she was the
Divider).

Definition 5 Divide&Choose${}_{n}^{\mathbf{2}}$

stage 1: each agent $i$ picks a partition $\pi^{i}$ in $\mathcal{P}(n,A)$;
those partitions are publicly revealed

stage 2: run the averaging auction between the guarantees
$\Gamma_{n}^{\pi_{i}},i\in[n]$.

The D&C${}_{n}^{2}$ rule takes longer to run than D&C${}_{n}^{1}$: once the
agents submit balanced transfers between the proposed partitions $\pi^{i}$ and
the rule selects the efficient $\pi_{i^{\ast}}$ – maximising
$\sum_{i}\Gamma_{n}^{\pi_{i^{\ast}}}(u_{i})$ according to the reported
transfers –, we still need to run the $\pi_{i^{\ast}}$-auction.

Proposition 2

In the D&C${}_{n}^{1}$ rule, agent $i$’s play is safe iff he bids
$\beta_{i}=Maxmin_{n}(u_{i})-minMax_{n}(u_{i})$ in stage 1, chooses a
partition $\pi_{i}$ maximising $[u_{i}](\pi)$ in stage 2, and reports
truthfully equalising transfers across the shares of $\pi$ in stage 3

In the D&C${}_{n}^{2}$ rule, agent $i$’s play is safe iff she proposes a
partition $\pi_{i}$ maximising $[u_{i}](\pi)$ in stage 1, then reports
truthfully equalising transfers across the guarantees
$\Gamma_{n}^{\pi_{j}}(u_{i}),j\in N$, and finally reports truthful transfers
in the final $\pi_{i^{\ast}}$-auction;

Both rules implement the guarantee

$\Gamma_{n}^{DC}(u)=\frac{1}{n}Maxmin_{n}(u)+\frac{n-1}{n}minMax_{n}(u)$
$=\frac{1}{n^{2}}\max_{\pi\in\mathcal{P}(n,A)}u(\pi)+\frac{n-1}{n^{2}}\min_{\pi\in\mathcal{P}(n,A)}u(\pi)$
(5)

Proof

For D&C${}_{n}^{1}$. By Lemma 1 the worst drop in guaranteed utility to agent
$i$ between the roles of Divider and Chooser (non-Divider) is
$\delta_{i}=Maxmin_{n}(u_{i})-minMax_{n}(u_{i})$. Therefore the safe bid in
stage 1 is precisely $\delta_{i}$. If $i$ becomes the Divider she pays
$\frac{n-1}{n}\delta_{i}$ then secures $Maxmin_{n}(u_{i})$ in the
$\pi$-auction; otherwise she is paid at least $\frac{1}{n}\delta_{i}$ and
secures $minMax_{n}(u_{i})$ in the $\pi$-auction.

For D&C${}_{n}^{2}$. By Lemma 2 agent $i$’s guaranteed utility in stage 2 is
$\frac{1}{n}\sum_{j}\frac{1}{n}[u_{i}](\pi_{j})$ where the worst case will be
if $\frac{1}{n}[u_{i}](\pi_{j})=minMax_{n}(u_{i})$ for each $j\neq i$;
therefore by proposing in stage 1 a partition $\pi_{i}$ maximising
$[u_{i}](\pi_{i})$ she secures the utility (5).

It is easy to check that no other play is safe. $\blacksquare$

Lemma 5

$i)$ the guarantee $\Gamma_{n}^{DC}$ is Positive, Responsive, and in the
duality interval (4)

$ii)$ if $u$ is additive the safe bid in D&C1 is zero and any partition is a
safe proposal in both rules.

The easy proof is omitted.

Statement $i)$ says that the D&C rules are “reasonable” in terms of
Proposition 1. Statement $ii)$ on the contrary is an unappealing feature of
D&C1,2: if my utility is additive all partitions are equally safe choices they
convey no information relevant to the selection of an efficient allocation.

In the reporting stages common to both rules I only reveal the relative
utilities between the shares of certain partitions but the level of my
absolute utility remains private: this increases privacy but is detrimental to
efficiency. If a certain agent $i$’s utility is everywhere higher than other
utilities, efficiency means that all the goods should go to $i$: the reports
in D&C1,2 fail to recognise this feature. On the contrary in the Sell&Buy rule
individual messages are related to the absolute utilities and avoid this type
of inefficiencies: Proposition 8 in section 9.

##  7 the Sell&Buy rule

###  7.1 defining the rule and its guarantee

A non negative price $p\in\mathbb{R}_{+}^{A}$ is formally an additive utility;
we use the same notation $p_{S}=\sum_{a\in S}p_{a}$. Next $\Delta(x)$ is the
simplex of prices such that $p_{A}=x$, the whole bundle costs $x$. Because the
recursive definitions of the S&B rule and its guarantee works over shrinking
subsets of objects, we make explicit their dependence on the set $A$.

Definition 6 Sell&Buy, S&B${}_{2}(A)$ for two agents

stage 1: the agents bid to become the Seller: this is (one of) the lowest
bidder(s) with bid $x$

stage 2: the Seller chooses a price $p\ $in $\Delta(x)$

stage 3: the Buyer can buy any share $S$ of objects (possibly $\varnothing$)
at this price and the Seller eats the unsold objects

$\text{final allocation: Buyer }(S,-p_{S})\text{ ; Seller }(A\diagdown
S,p_{S})$

To understand how to bid safely we compute first the worst utility
$W_{2}(u;x|A)$ an agent with utility $u$ can get by bidding $x$ and becoming
the Seller

$W_{2}(u;x|A)=\max_{p\in\Delta(x)}\min_{\varnothing\subseteq T\subseteq
A}(u(T)+p_{A\diagdown
T})=\max_{p\in\Delta(x)}{\large\\{}\min_{\varnothing\subseteq T\subseteq
A}(u(T)-p_{T})+x{\large\\}}$ (6)

because he must expect the worst purchase from the Buyer.

We compare it with the worst utility $L_{2}(u;x|A)$ of this agent if her bid
$x$ loses by a hair (to a bid just below $x$) and she is offered the worst
possible price but a total price no larger than $x$:

$L_{2}(u;x|A)=\min_{p\in\Delta(x)}\max_{\varnothing\subseteq S\subseteq
A}(u(S)-p_{S})$ (7)

Clearly $W_{2}(u;x|A)$ increases in $x$ while $L_{2}(u;x|A)$ decreases hence
the safe bid is where they intersect which we show below is an unambiguous bid
$x^{\ast}$; the common value is the guarantee $\Gamma_{2}^{SB}(u|A)$.

With $n$ agents there are at most $n-1$ rounds of bidding in S&B${}_{n}(A)$:
in each round one agent becomes the Buyer and all others become Sellers; the
Buyer leaves after being offered to buy some goods from all the Sellers.

Definition 7 Sell&Buy, S&B${}_{n}(A)$ recursive definition

stage 1: each agent $i$ bids $x_{i}$ to become Seller or Buyer; (one of) the
highest bidders becomes the Buyer

stage 2: each of the $n-1$ Sellers $j$ chooses a price $p_{j}$ in
$\Delta(x_{j})$

stage 3: the Buyer buys a share $S$ of goods (possibly $\varnothing$) by
paying $p_{j}(S)$ to each Seller and leaves; the rule stops if $S=A$,
otherwise we go to

stage 4: the remaining agents play S&B${}_{n-1}(A\diagdown S)\vskip 3.0pt plus
1.0pt minus 1.0pt$

The worst utility $W_{n}(u;x|A)$ from becoming a Seller after bidding $x$ is
now

$W_{n}(u;x|A)=\max_{p\in\Delta(x)}\min_{\varnothing\subseteq T\subseteq
A}(\Gamma_{n-1}^{SB}(u|T)+p_{A\diagdown
T})=\max_{p\in\Delta(x)}\min_{\varnothing\subseteq T\subseteq
A}(\Gamma_{n-1}^{SB}(u|T)-p_{T})+x$ (8)

and the worst utility as a Buyer after bidding $x$ is

$L_{n}(u;x|A)=\min_{p\in\Delta((n-1)x)}\max_{\varnothing\subseteq S\subseteq
A}(u(S)-p_{S})=\min_{p\in\Delta(x)}\max_{\varnothing\subseteq S\subseteq
A}(u(S)-(n-1)p_{S})$ (9)

because the worst case is when the $n-1$ other bids are just below $x$.

Lemma 6 For any non null utility $u\in\mathcal{M}^{+}$ the recursive programs
(8),(9), together with the initial pair (6), (7), define unambiguously
the function $W_{n}(u;x|A)$ concave and strictly increasing in $x$ from $0$ to
$u(A)$
the function $L_{n}(u;x|A)$ convex and strictly decreasing in $x$ from $u(A)$
to $0$
and the guarantee $\Gamma_{n}^{SB}(u)$ at their intersection:
$W_{n}(u;x^{\ast}|A)=L_{n}(u;x^{\ast}|A)=\Gamma_{n}^{SB}(u|A)\mathit{\vskip
3.0pt plus 1.0pt minus 1.0pt}$

These properties imply: $0<\Gamma_{n}^{SB}(u|A)<u(A)$.

Proposition 3 the guarantee $\Gamma_{n}^{SB}$ is Positive, Responsive, and in
the duality interval (4).

The proof of the key Lemma 6 and its corollary Proposition 3 is an application
of the minimax theorem, in subsection 11.2 of the Appendix.

###  7.2 computing the guarantee $\Gamma_{n}^{SB}$

The recursive computation of $\Gamma_{n}^{SB}$ is not easy in the general
case, but greatly facilitated when some goods are identical.

Lemma 7 If the goods $a,b$ enter symmetrically in $u$ – $u(S-b+a)=u(S)$ if
$a\notin S\ni b$ – the optimal price in $W_{n}(x;u|A)$ and the worst price in
$L_{n}(x;u|A)$ can be taken equal.

Proof in the Appendix subsection 11.3 where we state a stronger group version
of this property.

Our first example illustrates the recursive computation of $\Gamma_{n}^{SB}$
in a simple family of fully symmetric step functions connecting the Frugal and
Greedy utilities.

Example 1 The $m$ objects are identical and for each integer $\theta\in[m]$
the dichotomous utility $u^{\theta}$ requires no less and no more than
$\theta$ goods:

$u^{\theta}(S)=1\text{ if }|S|\geq\theta\text{ ; }u^{\theta}(S)=0\text{ if
}|S|<\theta$

So $u^{1}$ is Frugal and $u^{m}$ is Greedy.

For $t\in[m]$ write $\Gamma_{n}(\theta|t)=\Gamma_{n}^{SB}(u^{\theta}|T)$ the
$n$ person S&B-guarantee when there are only $t$ goods to divide and note that
$\Gamma_{n}(\theta|t)=0$ if $t<\theta$. We compute first
$\Gamma_{2}(\theta|t)$ for $t\geq\theta$:

$W_{2}(\theta;x|t)=\min\\{1,\frac{t-\theta+1}{t}x\\}\text{ ;
}L_{2}(\theta;x|t)=\max\\{0,1-\frac{t}{m}x\\}$
$\Longrightarrow\Gamma_{2}(\theta|t)=\frac{t-\theta+1}{t+1}\text{ for
}\theta\leq t\leq m$

For $n=3$ equation (9) is simply:
$L_{3}(\theta;x|m)=\max\\{0,1-\frac{2\theta}{m}x\\}$. By the concavity of
$t\rightarrow\Gamma_{2}(\theta|t)$ (8) becomes

$W_{3}(\theta;x|m)=\min_{\theta-1\leq t\leq
m}\\{\Gamma_{2}(\theta|t)+\frac{m-t}{m}x\\}=\min\\{\frac{m-\theta+1}{m}x,\frac{1}{\theta+1}+\frac{m-\theta}{m}x\\}$

after which one checks that the graph of $L_{3}$ intersects that of $W_{3}$ on
the line $x\rightarrow\frac{m-\theta+1}{m}x$, and finally
$\Gamma_{3}(\theta|m)=\frac{m+1-\theta}{m+1+\theta}$ with the optimal bid
$x^{\ast}=\frac{m}{m+1+\theta}$. The general inductive step works in exactly
the same way: the optimal bid is $x^{\ast}=\frac{m}{m+1+(n-2)\theta}$ and the
guarantees are

$\Gamma_{n}^{SB}(u_{F})=\frac{m}{m+n-1}\geq\Gamma_{n}^{SB}(u^{\theta})=\frac{m+1-\theta}{m+1+(n-2)\theta}\geq\Gamma_{n}^{SB}(u_{G})=\frac{1}{m(n-1)+1}$

For instance the ratio $\frac{\Gamma_{n}^{SB}(u_{F})}{\Gamma_{n}^{SB}(u_{G})}$
is already $10$ with four agents and five goods.

We conclude with two important special cases where $\Gamma_{n}^{SB}$ is easy
to describe.

Lemma 8 if $u$ is additive then
$x^{\ast}(u)=\frac{1}{n}u_{A}=\Gamma_{n}^{SB}(u)$ and, if chosen as Seller the
price $p=\frac{1}{n}u$ is safe.

The omitted proof checks by induction that if $u$ is additive
$W_{n}(u;x)=\min\\{x,u_{A}\\}$ and $L_{n}(u;x)=\max\\{u_{A}-(n-1)x,0\\}$.

Contrast this result with the fact that any play is safe in the D&C rules when
my utility is additive (statement $ii)$ in Lemma 5).

The final result in this section covers all problems with fully symmetric
goods and two agents. The utility function takes the form $u(S)=u_{s}$ if
$|S|=s$, $1\leq s\leq m$ and $u_{0}=0$. We write the non negative marginals
$\partial_{k}u_{\ell}=u_{\ell+k}-u_{\ell}$.

Proposition 4 $n=2$, identical goods

Agent $u$’s optimal bid in the S&B rule is

$x^{\ast}=\max\\{\frac{m}{m+k}\partial_{k}u_{\ell}|0\leq k,\ell\leq m\text{
and }0\leq\ell+k\leq m\\}$ (10)

If $x^{\ast}=\frac{m}{m+k}\partial_{k}u_{\ell}$ then

$\Gamma_{2}^{SB}(u)=\frac{\ell+k}{m+k}u_{\ell}+\frac{m-\ell}{m+k}u_{\ell+k}$
(11)

Proof in subsection 11.4. The recursive formula for larger $n$ is more
complicated but still solvable numerically.

Corollary:

If in addition $u$ is convex then $x^{\ast}=\max_{0\leq k\leq
m}\\{\frac{m}{m+k}(u_{m}-u_{m-k})\\}$
and $\Gamma_{2}^{SB}(u)=\frac{m}{m+k}u_{m-k}+\frac{k}{m+k}u_{m}$

If in addition $u$ is concave then $x^{\ast}=\max_{0\leq k\leq
m}\frac{m}{m+k}u_{k}$ and $\Gamma_{2}^{SB}(u)=\frac{m}{m+k}u_{k}$

##  8 Comparing the S&B, D&C, and FS guarantees

Proposition 5

$i)$ The three guarantees $\Gamma_{n}^{SB}(u),\Gamma_{n}^{DC}(u)$ and
$\Gamma_{n}^{FS}=\frac{1}{n}u(A)$ are continuous and weakly increasing in $u$.

$ii)$ They are also scale invariant ($\Gamma_{n}(\lambda
u)=\lambda\Gamma_{n}(u)$ for $\lambda>0$) increasing in $A$ and decreasing in
$n$: for all $A,a\notin A,n,u$ we have

$\Gamma_{n}(u|A)\leq\Gamma_{n}(u|A\cup a)\text{ and
}\Gamma_{n+1}(u|A)\leq\Gamma_{n}(u|A)$

Proof in subsection 11.5.

We start our numerical examples with the simplest choices of $n$ and $m$.

Example 2: two agents, two goods: $n=2$, $A=\\{a,b\\}$

Here the S&B and D&C guarantees only depend upon $u(A)$ and $u(a)+u(b)$; by
scale invariance we can normalise $u(A)=1$ then set $z=u(a)+u(b)\in[0,2]$;
note that $z=1$ means the utility is additive.

Clearly $\Gamma_{2}^{DC}(z)=\frac{1+z}{4}$ with a bid of $\frac{|z-1|}{2}$ in
D&C1. The omitted computations are almost as easy for $\Gamma_{2}^{SB}$ and
the optimal bid:

$\begin{array}[]{cccccccc}z&0&\cdots&\frac{1}{2}&\cdots&\frac{3}{2}&\cdots&2\\\
\Gamma_{2}^{SB}&\frac{1}{3}&\frac{z+1}{3}&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&\frac{1}{3}z&\frac{2}{3}\\\
x^{\ast}&\frac{2}{3}&\frac{2-z}{3}&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&\frac{1}{3}z&\frac{2}{3}\end{array}$

So $\Gamma_{2}^{SB}$ is more generous than $\Gamma_{2}^{DC}$ for superadditive
utilities, and less generous for subadditive ones.

Example 3: $n=3,A=\\{a,a\\}$ three agents, two identical goods

We set $u(A)=u_{2}=1$ and $z=2u_{1}\in[0,2]$ as above. Compute

$\Gamma_{3}^{DC}(z)=\frac{1}{9}\min\\{2z+1,z+2\\}\text{ with the bid
}\frac{|z-1|}{3}\text{ in D\&C}^{1}$
$\begin{array}[]{cccccccc}z&0&\cdots&\frac{2}{3}&\cdots&\frac{4}{3}&\cdots&2\\\
\Gamma_{3}^{SB}&\frac{1}{5}&\frac{z+1}{5}&\frac{1}{3}&\frac{1}{3}&\frac{1}{3}&\frac{z}{4}&\frac{1}{2}\\\
x^{\ast}&\frac{2}{5}&\frac{4-z}{10}&\frac{1}{3}&\frac{1}{3}&\frac{1}{3}&\frac{z}{4}&\frac{1}{2}\end{array}$

This time $\Gamma_{3}^{DC}>\Gamma_{3}^{SB}$ holds only in the interval
$]1,\frac{8}{5}[$.

The striking feature in these two examples is that $\Gamma^{SB}$ is exactly
the Familiar Share on a large interval of the parameter $z$, while for
$\Gamma^{DC}$ this only happens for a single value of $z$.

Example 11.6.1 in the Appendix computes our guarantees with two agents and
three identical goods and finds that the equality $\Gamma^{SB}=\Gamma^{FS}$
holds over 39% of the two parameter space. Here is the general fact explaining
these observations.

Proposition 6

$i)$ The guarantee $\Gamma_{n}^{SB}$ (resp. $\Gamma_{n}^{DC}$) is identical to
the Familiar Share on a subset $\mathcal{E}$ of $\mathcal{M}^{+}$ with non
empty interior (resp. with empty interior)

$ii)$ If the duality interval is not trivial ($minMax_{n}(u)<Maxmin_{n}(u)$)
then $\Gamma_{n}^{DC}$ is an interior point, but $\Gamma_{n}^{SB}$ needs not
be: it is one of the end points on a subset of $\mathcal{M}^{+}$ with non
empty interior

Proof in subsection 11.7.

The first example in subsection 11.6 shows that the set of additive utilities
is not entirely contained in the interior of $\mathcal{E}$: in words,
arbitrarily small perturbations away from additivity can destroy this
equality. The proof of Proposition 6 only shows that a neighborhood of the
uniform additive utility ($\partial_{a}u=\partial_{b}u$ for all $a,b$) is
contained in $\mathcal{E}$.

The same proof delivers a sufficient condition for the equality
$\Gamma_{n}^{SB}(u)=\frac{1}{n}u(A)$ in two agent problems, and a complete
characterisation if in addition the goods are identical.

Lemma 9 for two agents $n=2$

$i)$ Fix a utility $u\in\mathcal{M}^{+}$. If there exists a price vector $p$
s.t.

$p_{A}=\frac{1}{2}u(A)\text{ and }p_{S}\leq u(S)\leq
p_{S}+\frac{1}{2}u(A)\text{ for all }S\subseteq A$ (12)

then $\Gamma_{2}^{SB}(u)=\frac{1}{2}u(A)$ and $p$ is a safe price for $u$ if
she is the Seller.

$ii)$ If the goods are identical, the equality
$\Gamma_{2}^{SB}(u)=\frac{1}{2}u_{m}$ holds true if $u$ is bounded as follows:

$\frac{1}{2}\frac{k}{m}u_{m}\leq
u_{k}\leq\frac{1}{2}u_{m}+\frac{1}{2}\frac{k}{m}u_{m}\text{ for all }k,0\leq
k\leq m$ (13)

If $u$ is convex $\frac{u_{k}}{k}$ increases weakly in $k$, so the
inequalities (13) boil down to
$\partial_{1}u=u_{1}\geq\frac{1}{2}\frac{u_{m}}{m}$; similarly if $u$ is
concave (13) reduces to
$\partial_{m}u=u_{m}-u_{m-1}\geq\frac{1}{2}\frac{u_{m}}{m}$.

We turn to the opposite effect already illustrated in the Introduction for the
very simple step functions: when it does not coincide with the Familiar Share,
the $\Gamma^{SB}$ guarantee is more sensitive than $\Gamma^{DC}$ to the
convexity/concavity of the utility. One formal way to say this is that the S&B
guarantee diverges more from the FS benchmark than the D&C guarantee does.

Proposition 7

For all $n$ and all $u\in\mathcal{M}^{+}$ we have

$\frac{n}{(n-1)m+1}\leq\frac{\Gamma_{n}^{SB}(u)}{\frac{1}{n}u(A)}\leq\frac{n\times
m}{n+m-1}$
$\frac{1}{n}\leq\frac{\Gamma_{n}^{DC}(u)}{\frac{1}{n}u(A)}\leq\frac{\min\\{m,n\\}+n-1}{n}$

In both cases the bounds are achieved at $u_{G}$ and $u_{F}$ respectively.

Proof It is enough to show that $u_{G}$ and $u_{F}$ achieve those bounds:
indeed every utility $u$ in $\mathcal{M}^{+}$ s. t. $u(A)=1$ is between these
two: $u_{G}\leq u\leq u_{F}$ and the two guarantees
$\Gamma_{n}^{SB},\Gamma_{n}^{DC}$ increase weakly in $u$ and are scale
invariant (Proposition 5).

Example 1 in section 7 gives $\Gamma_{n}^{SB}(u_{F})$ for which the upper
bound is an equality, and $\Gamma_{n}^{SB}(u_{G})$ for which the lower bound
is. The same situation applies to $\Gamma_{n}^{DC}(u_{F})$ and
$\Gamma_{n}^{DC}(u_{G})$ after checking
$Maxmin_{n}(u_{F})=\min\\{1,\frac{m}{n}\\}$. $\blacksquare\vskip 3.0pt plus
1.0pt minus 1.0pt$

We see that the ratio $\frac{\Gamma_{n}^{DC}}{\Gamma_{n}^{FS}}$ is always
below $2$, while $\frac{\Gamma_{n}^{SB}}{\Gamma_{n}^{FS}}$ can be arbitrarily
large.777The upper bound of $\frac{\Gamma_{n}^{SB}}{\Gamma_{n}^{FS}}$ is
strictly larger than that of $\frac{\Gamma_{n}^{DC}}{\Gamma_{n}^{FS}}$, with a
single exception at $n=m=2$. The lower bound of
$\frac{\Gamma_{n}^{SB}}{\Gamma_{n}^{FS}}$ is strictly lower than that of
$\frac{\Gamma_{n}^{DC}}{\Gamma_{n}^{FS}}$ if $m\geq n+2$, strictly larger if
$m\leq n$, and equal if $m=n+1$.

In the last example of this section the D&C guarantee is unpalatable because
it does not take into account important aspects of the externalities across
objects. This critique is more subtle than – but similar to – that of the
Familiar Share by the way it treats Greedy and Frugal.

Example 4: The goods are partitioned as $A=R\cup R^{\ast}\cup L\cup L^{\ast}$,
where each subset contains $\ell$ objects so $m=4\ell$. Think of $2\ell$ right
gloves and $2\ell$ left gloves.

Abstemious is happy with any pair of one right and one left glove: her utility
is the cover of $\\{((r,\ell),1)\\}$ over the whole set $(R\cup
R^{\ast})\times(L\cup L^{\ast})$. Choosy wants no less than all gloves in
$R\cup L$ or all in $R^{\ast}\cup L^{\ast}$: his utility is the cover of
$\\{(R\cup L,1)$, $(R^{\ast}\cup L^{\ast},1)\\}$.

For both agents $minMax_{2}(u)=0$, $Maxmin_{2}(u)=1$, so
$\Gamma_{2}^{DC}(u_{A})=\Gamma_{2}^{DC}(u_{C})=\frac{1}{4}$: the D&C guarantee
is shockingly coarse, the more so as $\ell$ grows. By contrast one checks that
the optimal bid in the S&B rule is $x^{\ast}=\frac{2\ell}{\ell+1}$ for both
agents (almost twice larger than $u(A)$): to Abstemious this guarantees
$\Gamma_{2}^{SB}(u_{A})=\frac{\ell}{\ell+1}$,888because her worst case as
Seller is to sell exactly $R\cup R^{\ast}$ or exactly $S\cup S^{\ast}$ for a
net utility $\frac{x}{2}$; and as Buyer there will be at least one pair
costing at most $\frac{2x}{m}$. but to Choosy only
$\frac{1}{\ell+1}$.999because his worst case as Seller is to sell exactly one
glove in $R\cup R^{\ast}$ and one in $S\cup S^{\ast}$ for a net utility
$\frac{2x}{m}$; and as Buyer he will have to pay $\frac{x}{2}$ to get any
benefit.

Subsection 11.6 gives three more examples contrasting the guarantees of our
two rules.

##  9 The efficiency of guarantees and safe play

Before running extensive numerical experiments, we provide only two systematic
results, one about the efficiency loss measured from the profile of
guarantees, the other about the outcome of safe play when one player’s utility
dominates that of all the others.

###  9.1 guarantees and the bargaining gap

Given a profile of utilities $\overrightarrow{u}\in(\mathcal{M}^{+})^{N}$ we
call the interval
$G(\overrightarrow{u})=[\min_{\mathcal{P}(N;A)}\overrightarrow{u}(\pi),\max_{\mathcal{P}(N;A)}\overrightarrow{u}(\pi)]$
the bargaining gap. It is the worst case efficiency loss resulting from a
misallocation of the objects.

We say that the guarantee $\Gamma_{n}$ reduces the bargaining gap if

$\max_{\pi\in\mathcal{P}(N;A)}\overrightarrow{u}(\pi)\geq\sum_{N}\Gamma_{n}(u_{i})\geq\min_{\pi\in\mathcal{P}(N;A)}\overrightarrow{u}(\pi)\text{
for all }\overrightarrow{u}\in(\mathcal{M}^{+})^{N}$ (14)

where the first inequality is just the definition (1) of a guarantee, so only
the second inequality has bite.

For instance the FS $\frac{1}{n}u(A)$ meets (14) because
$u_{i}(A)\geq\min_{\mathcal{P}(N;A)}\overrightarrow{u}(\pi)$ for each $i$.

Recall that $\Gamma^{SB}$, $\Gamma^{DC}$ and $\Gamma^{FS}$ meet the lower
bound $\sum_{N}\Gamma_{n}(u_{i})\geq\sum_{N}minMax_{n}(u_{i})$ implied in the
duality interval: this lower bound and (14) are not logically related. On the
one hand if $A=\\{a,b,c,d\\}$, $u_{1}$ is the cover of $\\{ab,bc,cd,ad\\}$ and
$u_{2}$ is the cover of $\\{ac,ad,bc,bd\\}$ (all with value $1$), then
$minMax_{2}(u_{i})=0$ for $i=1,2$, but $\min_{\pi}\overrightarrow{u}(\pi)$ for
all $\pi$; on the other hand if $A=\\{a,a^{\prime},b,b^{\prime}\\}$, $u_{1}$
is the cover of $\\{a,a^{\prime}\\}$ and $u_{2}$ is the cover of
$\\{b,b^{\prime}\\}$, (all with value $1$) then $\overrightarrow{u}(\pi)=0$ if
each agent gets useless goods, but $minMax_{2}(u_{i})=\frac{1}{2}$ for
$i=1,2$.

Whether a guarantee systematically reduces the bargaining gap, and if so by
how much, is one way to measure its efficiency performance.

Lemma 10

$i)$ With two agents, $n=2$, the S&B and D&C guarantees reduce the bargaining
gap:

$ii)$ With three or more agents, the D&C guarantee may not reduce the
bargaining gap.

Proof Statement $i)$

Step 1: for S&B. Fix a profile $u,v$ where $u$’s optimal bid $x^{\ast}$ wins
against $v$’s larger optimal bid $y^{\ast}$. Let $p\in\Delta(x^{\ast})$ be
such that $\Gamma_{2}^{SB}(u)=L(u;x^{\ast})=(u-p)^{+}$. We increase $p$ to
some $q\in\Delta(y^{\ast})$ so that $\Gamma_{2}^{SB}(u)\geq(u-q)^{+}$.

Then
$\Gamma_{2}^{SB}(v)=W(v;y^{\ast})\geq(v-q)^{-}+y^{\ast}=v(S)-q_{S}+y^{\ast}$
for some $S,\varnothing\subseteq S\subseteq A$. Also $\Gamma_{2}^{SB}(u)\geq
u(S^{c})-q_{S^{c}}$ so $\Gamma_{2}^{SB}(u)+\Gamma_{2}^{SB}(v)\geq
u(S^{c})+v(S)$.

Step 2: for D&C. Fix a profile $u,v$ and let $S,T$ be such that
$\min_{\pi}[u](\pi)=u(S)+u(S^{c})$ and $\min_{\pi}[v](\pi)=v(T)+v(T^{c})$. The
definition of $\Gamma_{2}^{DC}$ implies

$\Gamma_{2}^{DC}(u)\geq\frac{1}{4}{\large(}u(T)+u(T^{c})+u(S)+u(S^{c}){\large)}$

and a similar lower bound for $\Gamma_{2}^{DC}(v)$. Summing up these
inequalities and rearranging gives the desired inequality (14).

Statement $ii)$ Recall the step functions $u^{\theta}$ in Example 1 (section
7.2): the $m$ goods are identical and $u^{\theta}(S)=1$ if $|S|\geq\theta$,
$=0$ if $|S|<\theta$ (so $u^{1}$ is the frugal utility). The simplest101010A
similar example applies for any $m=2m^{\prime}+1$ at the profile
$(u^{m^{\prime}+1},u^{m^{\prime}+1},u^{1})$. profile violating (14) for
$\Gamma_{2}^{DC}$ has three goods and the profile
$\overrightarrow{u}=(u^{2},u^{2},u^{1})$:

$\Gamma_{2}^{DC}(u^{2})=\frac{1}{9}\text{ ,
}\Gamma_{2}^{DC}(u^{1})=\frac{5}{9}\text{ but }G(\overrightarrow{u})=[1,2]$

$\blacksquare\vskip 3.0pt plus 1.0pt minus 1.0pt$

We conjecture that the S&B guarantee reduces the bargaining gap for any $n$.
Our intuition comes from the profiles
$\overrightarrow{u}=(u^{\theta_{i}})_{i=1}^{n}$ of step functions in Example 1
over $m$ identical goods, just used in the proof above. From the earlier
computation $\Gamma^{SB}(u^{\theta})=\frac{m+1-\theta}{m+1+(n-2)\theta}$ and
the fact that $\min_{\pi}\overrightarrow{u}(\pi)=1$ if and only if
$\sum_{i=1}^{n}\theta_{i}\leq m+n-1$ it is easy to deduce that the inequality
in (14) follows from the convexity of
$\theta\rightarrow\Gamma^{SB}(u^{\theta})$ and is tight.

###  9.2 safe play when an agent dominates

For any two $u,v\in\mathcal{M}^{+}$ we say that $u$ dominates $v$ (resp.
dominates strictly) if we have

$\max_{\varnothing\subseteq S\subseteq
A}\partial_{a}v(S)\leq\min_{\varnothing\subseteq S\subseteq
A}\partial_{a}u(S)\text{ (resp. a strict inequality) for all }a\in A$

If in the profile $\overrightarrow{u}=(u_{i})_{i=1}^{n}$ utility $u_{1}$
dominates all $u_{i}$-s, $i\geq 2$, it is efficient to give all the goods to
agent $1$, strictly so if each domination is strict. This follows by repeated
application of the inequality $u_{1}(S)+u_{i}(T)\leq u_{1}(S\cup
a)+u_{i}(T\diagdown a)$ when $S,T$ are disjoint and $a\in T$.

Our last result reveals another serious advantage of the Sell&Buy rule over
the Divide&Choose rules.

Proposition 8 Fix a profile $\overrightarrow{u}=(u_{i})_{i=1}^{n}$ where
utility $u_{1}$ dominates strictly all $u_{i}$-s, $i\geq 2$.

$i)$ the S&B division rule where all agents play safely implements the
efficient outcome where agent $1$ eats all the goods.

$ii)$ the outcome of safe play in the D&C rules may only collect
$\frac{1}{n}$-th of the efficient surplus

Proof of statement $i)$ in subsection 11.8.

For statement $ii)$ suppose that all agents have strictly subadditive
utilities: nobody proposes the trivial partition with all goods in a single
share, so efficiency is lost. In the worst case in each partition the shares
are of equal value to the proposer, so we can lose all but $\frac{1}{n}$-th of
the efficient surplus. With the D&C1 rule, there is the additional possibility
that the utility-dominant agent does not have the largest duality gap.

##  10 Future research

We have assumed throughout that objects are goods – freely disposable objects
–. Other types of division problems include the division of bads (aka chores),
of a mixture of goods and bads, even of objects of which the marginal
utilities $\partial_{a}(S)$ can change sign for different $S$-s, as in the
familiar example of utilities single-peaked or single-dipped over identical
objects.

The definition of the two Divide&Choose rules is unchanged in these more
complex domains. That of the Sell&Buy rule requires some adjustments. The
fairness and efficiency performance of these rules will be the object of
future research.

##  11 Appendix: missing proofs and more

###  11.1 the Multi Auction rule

Recall the definition of MA: each agent $i$ bids on each good and his profile
of bids is $\beta^{i}\in\mathbb{R}_{+}^{A}$; (one of) the highest bidders on
$a$, agent $i^{\ast}$, gets it and pays $\frac{1}{n}\beta_{i^{\ast}a}$ to
every other agent. Given the utility $u\in\mathcal{M}^{+}$ the safe vector of
bids solves the program:

$\Gamma_{n}^{MA}(u)=\max_{\beta\in\mathbb{R}_{+}^{A}}{\large\\{}\min_{\varnothing\subseteq
S\subseteq
A}(u(S)-\frac{n-1}{n}\beta_{S}+\frac{1}{n}\beta_{S^{c}}{\large\\}}=\max_{\beta\in\mathbb{R}_{+}^{A}}\min_{\varnothing\subseteq
S\subseteq A}(u(S)-\beta_{S})+\frac{1}{n}\beta_{A}$ (15)

If our agent wins the auctions for the goods in $S$ and those only, she pays
$\frac{n-1}{n}\beta_{a}$ for each $a$ in $S$, and gets in the worst case
$\frac{1}{n}\beta_{a}$ for each $a$ outside $S$.

The guarantee $\Gamma_{n}^{MA}$ is Responsive but Not Positive:
$\Gamma_{n}^{MA}(u_{G})=0<\frac{1}{n}=\Gamma_{n}^{MA}(u_{F})$. Indeed if
Greedy’s bid $\beta$ is not zero, pick $a$ such that $\beta_{a}=\min_{b\in
A}\beta_{b}$, suppose Greedy wins all auctions except $a$ and check that his
worst utility is negative or zero. And Frugal’s safe bid is $\frac{1}{n}$ on
every good, securing $\frac{1}{n}$ in the worst cases where she wins all
auctions or none of them.

Moreover $\Gamma_{n}^{MA}$ is dominated by the $minMax$ guarantee, often
strictly so. To check the first claim pick any $u\in\mathcal{M}^{+}$ any
partition $\pi=\\{S_{k}\\}_{k\in[n]}$ of $A$ and any bid $\beta$: (15) implies
$\Gamma_{n}^{MA}(u)\leq(u(S_{k})-\beta_{S_{k}})+\frac{1}{n}\beta_{A}$ for all
$k$ and the sum of these inequalities is $\Gamma_{n}^{MA}(u)\leq[u](\pi)$.

An example where domination is strict is the utility $u=u_{F}+u_{G}$. We let
the reader check that $Maxmin_{2}(u)=minMax_{2}(u)=1$ but
$\Gamma_{n}^{MA}(u)=\frac{m}{2(m-1)}$.

###  11.2 proof of Lemma 6 and Proposition 3

Fixing $A$ and a single utility $u\in\mathcal{M}^{+}$, the first step is to
rewrite the programs (6) (7) in a more compact though less transparent format
using a well known combinatorial concept.

A vector $\delta=(\delta_{S})\in\mathbb{R}_{+}^{2^{A}}$ is a balanced (set of)
weights if for all $a\in A$ we have $\sum_{S:S\ni a}\delta_{S}=1$. We call
$\delta$ minimal if it is an extreme point of the convex compact set of
balanced weights, and write $\mathcal{B}_{m}$ the set of minimal balanced
weights for $m$ goods.111111The size of $\mathcal{B}$ grows astronomically
fast with $m$: $|\mathcal{B}|=2$ for $m=2$, $=6$ for $m=3$, $=27$ for $m=4$
and more than $15,000$ for $m=5$: see [16]. The simplest elements of
$\mathcal{B}_{m}$ come from the true partitions $\\{S_{k}\\}$ of $A,$ i.e.
each $S_{k}$ is non empty: set $\delta_{S_{k}}=1$ for each $k$, and all other
weights to $0$. Let $\mathcal{B}_{m}^{\ast}$ be $\mathcal{B}_{m}$ minus the
balanced weights $\delta_{A}=1$ coming from the trivial partition $\\{A\\}$.

The total weight of $\delta$ is $\overline{\delta}=\sum_{S\in
2^{A}\diagdown\varnothing}\delta_{S}$. Then $\overline{\delta}>1$ for each
$\delta$ in $\mathcal{B}_{m}^{\ast}$. The smallest of these sums is
$\overline{\delta}=\frac{m}{m-1}$ when $\delta_{A\diagdown a}=\frac{1}{m-1}$
for all $a$, and the largest one is $\overline{\delta}=m$ when $\delta_{a}=1$
for all $a$. Both claims follow from the identity $\sum_{S\varsubsetneq
A}|S|\cdot\delta_{S}=m$.

Lemma 11

The programs (6) (7) can be rewritten as follows:

$W_{2}(u;x)=\min\\{x,u(A),\min_{\mathcal{B}_{m}^{\ast}}\frac{1}{\overline{\delta}}(\delta\cdot
u-x)+x\\}$ (16)
$L_{2}(u;x)=\max\\{0,u(A)-x,\max_{\mathcal{B}_{m}^{\ast}}\frac{1}{\overline{\delta}}(\delta\cdot
u-x)\\}$ (17)

Proof.

We write $\nabla(Z)$ for the set of convex weights on $Z$. We apply the minmax
theorem to the maxmin expression in (6):

$W_{2}(u;x)-x=\max_{p\in\Delta(x)}\min_{\varnothing\subseteq T\subseteq
A}(u(T)-p_{T})=\max_{p\in\Delta(x)}\min_{\xi\in\nabla(2^{A})}\sum_{T\in
2^{A}}\xi_{T}(u(T)-p_{T})$

where $\xi$ has two coordinates $\xi_{A}$ and $\xi_{\varnothing}$.

Note that the mapping
$\nabla(2^{A})\ni\xi\rightarrow\zeta\in\mathbb{R}^{A}:\zeta_{a}=\sum_{T:a\in
T}\xi_{T}$ is onto $[0,1]^{A}$, and apply the minimax theorem to rewrite the
last maxmin term above as

$\min_{\xi\in\nabla(2^{A})}\max_{a\in A}\sum_{T\in
2^{A}}\xi_{T}u(T)-x\zeta_{a}\Longrightarrow
W_{2}(u;x)=\min_{\xi\in\nabla(2^{A})}\sum_{T\in
2^{A}}\xi_{T}u(T)+x(1-\min_{a}\varsigma_{a})$

We check now that for some optimal $\xi$ in the minimisation program above
$\zeta_{a}$ is independent of $a$. Assume $\zeta_{a}>\min_{b}\zeta_{b}$ where
the minimum is achieved by some good $b^{\ast}$. We can choose $S$ containing
$a$ but not $b^{\ast}$ and such that $\xi_{S}>0$: if this was impossible
$\zeta_{a}\leq\zeta_{b^{\ast}}$ would follow. For $\varepsilon$ small enough
we construct $\xi^{\prime}\in\nabla(2^{A})$ identical to $\xi$ except for
$\xi_{S}^{\prime}=\xi_{S}-\varepsilon$,
$\xi_{S\diagdown\\{a,b^{\ast}\\}}^{\prime}=\xi_{S\diagdown\\{a,b^{\ast}\\}}^{\prime}+\varepsilon$.
By construction $\zeta_{b^{\ast}}^{\prime}=\zeta_{b^{\ast}}$ and the same
holds true for any $b$ minimising $\zeta$: thus $\min\zeta^{\prime}=\min\zeta$
for $\varepsilon$ small enough and the net change on the objective is
$-\varepsilon u(S)+\varepsilon u(S\diagdown\\{a,b^{\ast}\\})\leq 0$.

If $\xi$ is deterministic on $\varnothing$ or on $A$, we get the first two
terms in (16). For another $\xi$ we can assume $\xi$ puts no weight on
$\varnothing$ or on $A$, and write $\zeta\in[0,1]$ for the common value
$\zeta_{a}$. Setting $\delta=\frac{1}{\zeta}\xi$ defines a balanced set of
weights and $\sum_{T}\xi_{T}u(T)+x(1-\zeta)=\zeta(\delta\cdot u)+(1-\zeta)x$.
Without loss we can minimise over minimal balanced weights. Finally
$\overline{\delta}=\frac{1}{\zeta}$ and the proof of (16) is complete.

The similar argument for (17) starts with

$L_{2}(u,x)=\min_{p\in\Delta(x)}\max_{\xi\in\nabla(2^{A})}\sum_{T\in
2^{A}}\xi_{T}(u(T)-p_{T})=\max_{\xi\in\nabla(2^{A})}\\{\sum_{T\in
2^{A}}\xi_{T}u(T)-x(\max_{a\in A}\zeta_{a})\\}$

The critical argument that we can take $\zeta_{a}$ independent of $a$ assumes
$\zeta_{a}<\max\zeta=\zeta$, picks $S$ s. t. $\xi_{S}>0$ and containing
$b^{\ast}$ but not $a$ and changes $\xi$ by
$\xi_{S}^{\prime}=\xi_{S}-\varepsilon$, $\xi_{S\cup a}^{\prime}=\xi_{S\cup
a}+\varepsilon$: for $\varepsilon$ small enough the $\max\zeta$ does not
change and the net change on the objective is at least$-\varepsilon
u_{S}+\varepsilon u_{S\cup a}\geq 0$. $\blacksquare\vskip 3.0pt plus 1.0pt
minus 1.0pt$

Equation (16) defines a concave function. Each term in $x$ increases strictly
because $\overline{\delta}>1$ and reaches $u(A)$ for $x$ large enough,
therefore $W_{2}(u;x)$ increases strictly up to $u(A)$. Similarly in (17)
$L_{2}(u;x)$ is convex and strictly decreasing as long as all terms in $x$ are
positive, which terminates for $x$ large enough. So the intersection of
$W_{2}(u;\cdot)$ and $L_{2}(u;\cdot)$ as $\Gamma_{2}^{SB}(u|A)$ is well
defined.

We proceed now by induction after checking that the function
$S\rightarrow\Gamma_{2}^{SB}(u|S)$ is in $\mathcal{M}^{+}(A)$. Going back to
the definition (6) we see that $W_{2}(u;x|S)$ increases weakly in $S$ because
agent $u$ can choose in the problem augmented to $S\cup a$ a price s. t.
$p_{a}=0$; and so does $L_{2}(u;x|S)$ by (7) because in the augmented problem
the agent can choose only among subsets not containing $a$. Both
$W_{2}(u;x|S)$ and $L_{2}(u;x|S)$ increase weakly in $S$, so their
intersection in $x$ increases too.

The induction step applies Lemma 11 to
$\Gamma_{n-1}^{SB}(u|\cdot)\in\mathcal{M}^{+}(A)$ and gives
$W_{n}(u;x|A),L_{n}(u;x|A)$ by the two programs

$W_{n}(u;x|A)=\min\\{x,u(A),\min_{\mathcal{B}_{m}}\frac{1}{\overline{\delta}}(\delta\cdot\Gamma_{n-1}^{SB}(u|\cdot)-x)+x\\}$
(18)
$L_{n}(u;x|A)=\max\\{0,u(A)-(n-1)x,\max_{\mathcal{B}_{m}}\frac{1}{\overline{\delta}}(\delta\cdot
u-(n-1)x)\\}$ (19)

with the properties announced in Lemma 6, and their intersection
$\Gamma_{n}^{SB}(u|\cdot)$ as a function in $\mathcal{M}^{+}(A)$.

Turning to Proposition 3. If $u(A)>0$ both functions $W_{n}(u;x),L_{n}(u;x)$
are strictly positive for $x$ small enough, proving Positivity. For
Responsiveness we compute formally $\Gamma_{2}^{SB}(u_{F})$ (more rigorously
than in the Introduction). First (16) gives $W_{2}(u_{F};x)=\min\\{x,1\\}$
because the smallest $\overline{\delta}$ in $\mathcal{B}_{m}^{\ast}$ is
$\frac{m}{m-1}$ and $L_{2}(u_{F};x)=\max\\{0,1-\frac{1}{m}x\\}$ because the
largest $\overline{\delta}$ in $\mathcal{B}_{m}^{\ast}$ is $m$. This shows
$\Gamma_{2}^{SB}(u_{F}|S)=\frac{|S|}{|S|+1}$

We omit the straightforward induction argument giving
$\Gamma_{n}^{SB}(u_{F}|S)=\frac{|S|}{|S|+n-1}$.

It remains to check $\Gamma_{n}^{SB}(u)\geq minMax_{n}(u)$ for all $u$ and
$n$. This is true for $n=1$. Assume next it holds for $\Gamma_{n-1}^{SB}$ and
pick any $u\in\mathcal{M}^{+}(A)$ with optimal bid $x^{\ast}$ where $W_{n}$
and intersect. Choose $p\in\Delta(x^{\ast})$ optimal in program (9) so that
$L_{n}(u;x^{\ast}|A)=\max_{\varnothing\subseteq S\subseteq
A}(u(S)-(n-1)p_{S})$. Then (8) and the inductive argument imply

$W_{n}(u;x^{\ast})\geq\min_{\varnothing\subseteq S\subseteq
A}(\Gamma_{n-1}^{SB}(u|S)-p_{S})+x^{\ast}=\Gamma_{n-1}^{SB}(u|T)-p_{T}+x^{\ast}\text{
for some }T$ $\Longrightarrow
W_{n}(u;x^{\ast})\geq\frac{1}{n-1}[u](\pi)-p_{T}+x^{\ast}\text{ where
}\pi\text{ is some }(n-1)\text{-partition of }T$

We can now combine this lower bound for $(n-1)W_{n}(u;x^{\ast})$ with
$L_{n}(u;x^{\ast})\geq u(T^{c})-(n-1)p_{T^{c}}$ to get
$n\Gamma_{n}^{SB}(u)\geq[u](\pi)+u(T^{c})$ which completes the proof.

###  11.3 proof of Lemma 7

For brevity we give the argument for $n=2$ and omit the obvious induction
argument.

Fix $u\in\mathcal{M}^{+}$ and assume $u$ is symmetric in the goods $a,b$. In
the program (7) defining $L_{2}(u;x)$ assume the worst price $p$ has
$p_{a}<p_{b}$. Let $q$ obtains from $p$ by averaging $p_{a}$ and $p_{b}$ and
changing nothing else. Then $(u-p)^{+}$ differs from $(u-q)^{+}$ only in pairs
of terms of the form $u(S)-p_{S}$, $u(S-b+a)-p_{S-b+a}$. Replacing $p$ by $q$
lowers the largest of these two terms, so $q$ is still optimal in the program
(7). The argument for $W_{2}(x;u)$ is identical.

The group version of the Lemma is very useful and almost as easy to prove.
Suppose two subsets $T,T^{\ast}$ of equal size are treated symmetrically by
$u$: for any permutation $\sigma$ of $A$ exchanging $T$ and $T^{\ast}$ and
leaving other goods unchanged we have $u(\sigma(S))=u(S)$ for all $S$. Then to
solve $W_{2}(x;u)$ and $L_{2}(x;u)$ we can take identical prices for all goods
in $T\cup T^{\ast}$.

###  11.4 proof of Proposition 4

By the symmetry Lemma the programs (6) and (7) simplify to

$W_{2}(u;x)=\min_{0\leq k\leq m}\\{u_{k}+\frac{m-k}{m}x\\}\text{ ;
}L_{2}(u;x)=\max_{0\leq k\leq m}\\{u_{k}-\frac{k}{m}x\\}$

The optimal bid $x^{\ast}$ solves $W_{2}(u;x^{\ast})=L_{2}(u;x^{\ast})$.
Because $W_{2}$ increases and $L_{2}$ decreases, both strictly, the inequality
$x\geq x^{\ast}$ is equivalent to $W_{2}(u;x)\geq L_{2}(u;x)$. If
$k^{\prime}\leq k$ the inequality $u_{k}+\frac{m-k}{m}x\geq
u_{k^{\prime}}-\frac{k^{\prime}}{m}x$ is automatic, therefore $x\geq x^{\ast}$
amounts to

$u_{\ell}+\frac{m-\ell}{m}x\geq u_{\ell+k}-\frac{\ell+k}{m}x\text{ for all
}k,\ell\geq 0\text{ s. t. }\ell+k\leq m$ $\Longleftrightarrow
x\geq\max_{0\leq\ell+k\leq m}\frac{m}{m+k}(u_{\ell+k}-u_{\ell})$

which proves (10) and in turn (11).

Remark: a similar computation using the recursive definition of S&B for three
agents gives the optimal bid $x^{\ast}=\max_{0\leq k+k^{\prime}\leq
m}\frac{m}{m+2k^{\prime}-k}(u_{k^{\prime}}-\Gamma_{2}^{SB}(u|k))$, where
$\Gamma_{2}^{SB}(u|k)$ refers to the restriction of the problem to just $k$
goods.

###  11.5 proof of Proposition 5

Proof. Statement $i)$ is clear for $\Gamma_{n}^{DC}$ and $\Gamma_{n}^{FS}$;
for $\Gamma_{n}^{SB}$ both functions $W_{n}(u;\cdot)$ and $L_{n}(u;\cdot)$
increase weakly in $u$, so their intersection does too.

Statement $ii)$. For $\Gamma_{n}^{DC}$ scale invariance is clear. For the
first inequality one checks easily that both $Maxmin_{n}(u|A)$ and
$minMax_{n}(u|A)$ increase weakly in $A$. For the second inequality observe
that for any $\pi^{\ast}\in\mathcal{P}(n+1;A)$ we can find a share $S$ in
$\pi^{\ast}$ such that $[u](\pi^{\ast})-u(S)\geq\frac{n}{n+1}[u](\pi^{\ast})$;
as $[u](\pi^{\ast})-u(S)\leq\max_{\pi\in\mathcal{P}(n;A)}[u](\pi)$ we see that
$Maxmin_{n}(u)$ decreases weakly in $n$. This is clearly true for
$minMax_{n}(u)$ as well, and in turn for $\Gamma^{DC}$.

For $\Gamma^{SB}$ scale invariance is routinely checked. The monotonicity in
$A$ was proven in subsection 11.2, shortly after the proof of Lemma 11.

For the monotonicity in $n$: taking $T=A$ in the minimisation part of program
(8) gives $W_{n+1}(u;x)\leq\Gamma_{n}^{SB}(u)$ for all $x$, in particular at
the $x^{\ast}$ optimal in the problem with $n+1$ agents. $\blacksquare$

###  11.6 three more examples

####  11.6.1 two agents, three identical goods: $n=2,A=\\{a,a,a\\}$

The utilities $(u_{1},u_{2},u_{3})$ cover the cone $0\leq u_{1}\leq u_{2}\leq
u_{3}$. The D&C guarantee is simply additive:
$\Gamma_{3}^{DC}(u)=\frac{1}{4}(u_{1}+u_{2}+u_{3})$ because $[u](\pi)$ takes
only two values; it coincides with $\Gamma_{2}^{FS}(u)=\frac{1}{2}u_{3}$ if
and only if $u$ is additive.

Contrast this with $\Gamma_{2}^{SB}(u)$ which is piecewise linear – linear on
6 subcones of utilities – and coincides with the familiar share first in a
thick cone where the ratios $\frac{u_{1}}{u_{3}}$ and $\frac{u_{2}}{u_{3}}$
are both not far from the additive benchmark, but also in a slice of additive
utilities where these ratios are “extreme”:

$\Gamma_{2}^{SB}(u)=\frac{1}{2}u_{3}\Longleftrightarrow\\{\frac{1}{6}u_{3}\leq
u_{1}\leq\frac{2}{3}u_{3}\text{ and }\frac{1}{3}u_{3}\leq
u_{2}\leq\frac{5}{6}u_{3}\\}\text{ or }\\{u_{1}+u_{2}=u_{3}\text{ and
}u_{1}\leq\frac{1}{6}u_{3}\\}$

The thick subcone occupies 39% of the entire cone of utilities (computed in
any slice where $u_{3}$ is constant).

####  11.6.2 a one-dimensional path from $u_{F}$ to $u_{G}$

We have two agents and identical goods sufficiently numerous to justify a
smooth approximation. we construct a parametrised family of utilities
connecting Frugal to Greedy.

Part 1. Utilities with decreasing concavity from Additive at $\lambda=0$ to
Frugal as $\lambda$ goes to $1$

$u_{k}=\frac{k}{(1-\lambda)m+\lambda k}\text{ for }0\leq k\leq m\text{ so
}u(A)=u_{m}=1$

The Corollary of Proposition 4 shows that $\Gamma_{2}^{SB}$ is the FS
$\frac{1}{2}u_{m}$ iff $\lambda\leq\frac{1}{2}$:

$\Gamma_{2}^{DC}(\lambda)=\frac{4-\lambda}{4(2-\lambda)}\text{ ;
}\Gamma_{2}^{SB}(\lambda)=\max\\{\frac{\sqrt{\lambda}}{\sqrt{\lambda}+\sqrt{1-\lambda}},\frac{1}{2}\\}$

Part 2.: Utilities with increasing convexity from Additive at $\mu=0$ to
Greedy for $\mu$ going to $1$

$u_{k}=\frac{(1-\mu)k}{m-\mu k}\text{ for }0\leq k\leq m$

Here too $\Gamma_{2}^{SB}=\Gamma_{2}^{FS}=\frac{1}{2}$ iff
$\mu\leq\frac{1}{2}$

$\Gamma_{2}^{DC}(\mu)=\frac{4-3\mu}{4(2-\mu)}\text{ ;
}\Gamma_{2}^{SB}(\mu)=\frac{1}{2}\text{ in }[0,\frac{1}{2}]\text{ ;
}=\frac{2\sqrt{\mu(1-\mu)}}{(\sqrt{\mu}+\sqrt{1-\mu})^{2}}\text{ in
}[\frac{1}{2},1]$

####  11.6.3 a versatile dichotomous example

We have $m=h\times\ell$ goods and $A={\Large\cup}_{k=1}^{h}B_{k}$ is
partitioned into $h\geq 2$ subsets $B_{k}$ each of size $\ell\geq 2$. The
utility $u$ is the cover of the sequence $\\{(B_{k},1)\\}$.

Computing $\Gamma_{n}^{DC}$ is easy: $minMax_{n}(u)=0$,
$Maxmin_{n}(u)=\min\\{1,\frac{h}{n}\\}$ therefore

$\Gamma_{n}^{DC}(u)=\frac{\min\\{h,n\\}}{n^{2}}$

in particular $\Gamma_{n}^{DC}(u)=\Gamma_{n}^{FS}(u)$ if and only if $n\leq
h$.

For S&B we compute first $W_{2}(u;x)$ by the group version of the symmetry
Lemma 7 (subsection 11.3): each object is priced $\frac{x}{h\times\ell}$ then
$W_{2}(u;x)=\frac{x}{\ell}$ because in the worst case the Seller sells one
object in each $B_{k}$; and $L_{2}(u;x)=1-\frac{x}{h}$ because each set
$B_{k}$ costs $\frac{x}{h}$.

So $\Gamma_{2}^{SB}(u)=\frac{h}{h+\ell}$ and a routine induction argument
shows

$\Gamma_{n}^{SB}(u)=\frac{h}{h+(n-1)\ell}$

in particular $\Gamma_{n}^{SB}(u)=\Gamma_{n}^{FS}(u)$ if and only if $h=\ell$.

So for this family of utilities $\Gamma_{n}^{DC}$ equals the Familiar Share
much more frequently than $\Gamma_{n}^{SB}$.

###  11.7 proof of Proposition 6 and Lemma 9

####  11.7.1 Lemma 9

For statement $i)$ suppose $u$ and the price $p$ meet the inequalities (12).
The left one implies $\min_{\varnothing\subseteq S\subseteq A}(u(S)-p_{S})=0$
hence $W_{2}(u;\frac{1}{2}u(A))\geq\frac{1}{2}u(A)$ and in fact
$W_{2}(u;\frac{1}{2}u(A))=\frac{1}{2}u(A)$ because $W_{2}(u;x)\leq x$ is
always true.

Next the right hand inequality gives
$L_{2}(u;\frac{1}{2}u(A))\leq\max_{\varnothing\subseteq S\subseteq
A}(u(S)-p_{S})\leq\frac{1}{2}u(A)$, but $L_{2}(u;x)\geq u(A)-x$ is always true
therefore $L_{2}(u;\frac{1}{2}u(A))=\frac{1}{2}u(A)$ and the desired
conclusion $\Gamma_{2}^{SB}(u)=\frac{1}{2}u(A)$ holds. Checking that $p$ is
the optimal selling price is now easy.

Statement $ii)$ then follows from Proposition 4 and the fact that if goods are
identical the inequalities (12), if they hold at all, must hold for the
symmetric price $p_{a}=\frac{1}{2m}u(A)$ for all $a$.

####  11.7.2 Proposition 6

Step 1. Fixing $n$ and $A$ we show that $\Gamma_{n}^{SB}(u|A)=\frac{1}{n}u(A)$
if the utility $u$ satisfies the following system of (many) inequalities. For
all $n^{\prime},2\leq n^{\prime}\leq n$, and all $S$, $\varnothing\neq
S\subseteq A$ there exists a price $p\in\mathbb{R}_{+}^{S}$ s. t.

$p_{S}=\frac{1}{n^{\prime}}u(S)\text{ and }(n^{\prime}-1)p_{T}\leq
u(T)\leq(n^{\prime}-1)p_{T}+\frac{1}{n^{\prime}}u(S)\text{ for all
}T\varsubsetneq S$ (20)

We prove the claim by induction on $n^{\prime}$. For $n^{\prime}=2$ the system
above is exactly (12) when we replace $A$ by $S$, so by Lemma 9
$\Gamma_{2}^{SB}(u|S)=\frac{1}{2}u(S)$ for all $S$, and for $S=A$ this is our
claim.

For $n^{\prime}=3$ we fix again $S$, $\varnothing\neq S\subseteq A$, and the
previous step allows us to simplify $W_{3}(u;x|S)$ in (LABEL:18):

$W_{3}(u;x|S)=\max_{p\in\Delta(x)}\min_{\varnothing\subseteq T\subseteq
S}(\frac{1}{2}u(T)-p_{T})+x$

so that (20) applied to $n^{\prime}=3$ and the corresponding price $p$ implies
$W_{3}(u;\frac{1}{3}u(S)|S)\geq\frac{1}{3}u(S)$ hence an equality because
$W_{3}(u;x|S)\leq x$ for all $x$. We use next (LABEL:19) to majorise
$L_{3}(u;\frac{1}{3}u(S)|S)$ by $\max_{\varnothing\subseteq T\subseteq
S}(u(T)-2p_{T})$, where $2p_{S}=\frac{2}{3}u(S)$; then (20) to deduce
$L_{3}(u;\frac{1}{3}u(S)|S)\leq\frac{1}{3}u(S)$, which is an equality because
$L_{3}(u;x|S)\geq u(S)-2x$ is always true. We have just proven
$\Gamma_{3}^{SB}(u|S)=\frac{1}{3}u(S)$ for all $S$ and the claim for
$n^{\prime}=3$ by taking $S=A$.

The induction argument is now clear.

Step 2. Fixing $n$ and $m$ we choose a small positive number $\varepsilon$ and
consider the subset of utilities in $\mathcal{M}^{+}$ such that $u(A)=1$ and

$\frac{s}{m}(1-\varepsilon)\leq u(S)\leq\frac{s}{m}(1+\varepsilon)\text{ for
all }S\subseteq A\text{ with }|S|=s$ (21)

They approximate the additive utility $u_{a}\equiv 1$. If such a utility
satisfies (20) for some price $p$, the desired equality
$\Gamma_{n}^{SB}(u;A)=\frac{1}{n}u(A)$ follows by step 1. By scale invariance
of $\Gamma_{n}^{SB}$ it extends to the cone they generate as well, a subset
with non empty interior in $\mathcal{M}^{+}$.

We choose $p$ as $p_{T}=\frac{\tau}{n^{\prime}s}u(S)$ where $\tau=|T|$ and
(20) becomes

$\frac{n^{\prime}-1}{n^{\prime}}\frac{\tau}{s}u(S)\leq
u(T)\leq(\frac{n^{\prime}-1}{n^{\prime}}\frac{\tau}{s}+\frac{1}{n^{\prime}})u(S)$

The left hand inequality holds if we replace $u(S)$ by its upper bound and
$u(T)$ by its lower bound in (21). This boils down to
$\frac{1+\varepsilon}{1-\varepsilon}\leq 1+\frac{1}{n^{\prime}-1}$. A similar
evaluation of the right hand inequality gives
$\frac{1+\varepsilon}{1-\varepsilon}\leq
1+\frac{1}{n^{\prime}}(\frac{s}{t}-1)$. The worst case happens for
$n^{\prime}=n,s=m,\tau=m-1$ and it is $\frac{1+\varepsilon}{1-\varepsilon}\leq
1+\frac{1}{(n-1)(m-1)}$. $\blacksquare$

###  11.8 proof of Proposition 8 statement $i)$

We assume $n=2$ and omit for brevity the straightforward induction argument
extending the result to any $n$.

Fix any $u\in\mathcal{M}^{+}$; from Lemma 6 and Lemma 11(in the proof of Lemma
6) we know that $W_{2}(u;x)$ reaches $u(A)$ at some finite point denoted
$\widetilde{x}(u)$: $W_{2}(u;\cdot)$ increases strictly up to
$\widetilde{x}(u)$ after which it is flat. Agent $u$’s optimal bid
$x^{\ast}(u)$ in S&B is strictly below $\widetilde{x}(u)$ (because
$W_{2}(u;\widetilde{x}(u))=u(A)>L_{2}(u;\widetilde{x}(u)$).

Below we use the shorthands $\partial_{a}^{+}u=\max_{\varnothing\subseteq
S\subseteq A}\partial_{a}u(S)$ and
$\partial_{a}^{-}u=\min_{\varnothing\subseteq S\subseteq A}\partial_{a}u(S)$.

Step 1 Fix $u$ and $x\leq\widetilde{x}(u)$ and suppose that in the program (6)
an optimal price is $p\in\Delta(x)$. Then $p_{a}\leq\partial_{a}^{+}u$ for all
$a$.

Proof by contradiction: we assume $p_{a}>\partial_{a}^{+}u$ for some $a$ and
define a new price $p^{\prime}$ s. t. $p_{a}^{\prime}=p_{a}-\varepsilon$ and
$p_{b}^{\prime}=p_{b}$ otherwise; we choose $\varepsilon>0$ small enough that
$p_{a}^{\prime}>\partial_{a}^{+}u$ still holds. For some $T\in 2^{A}$ we have
$\min_{\varnothing\subseteq S\subseteq
A}(u(S)-p_{S}^{\prime})=u(T)-p_{T}^{\prime}$. This implies $a\in T$ otherwise
adding $a$ to $T$ would contradict the optimality of $T$. We compute now

$W_{2}(u;x-\varepsilon)\geq u(T)-p_{T}^{\prime}+(x-\varepsilon)=u(T)-p_{T}+x$
$\geq\min_{\varnothing\subseteq S\subseteq A}(u(S)-p_{S})+x=W_{2}(u;x)$

We see that $W_{2}(u;\cdot)$ is flat before $x$ therefore $x>\widetilde{x}(u)$
contradicting the choice of $x$.

Step 2 Assume $u_{1}$ dominates $u_{2}$ strictly.

A first consequence is $L_{2}(u_{1};x)>L_{2}(u_{2};x)$ for all $x\leq
x^{\ast}(u_{2})$. Indeed $u_{1}(S)-p_{S}>u_{2}(S)-p_{S}$ for all non empty $S$
and $p\in\Delta(x)$, and $L_{2}(u_{2};x)$ is positive therefore for any
$p\in\Delta(x)$ the maximum of $u_{2}(S)-p_{S}$ is achieved at some non empty
$S$.

Next we pick $p\in\Delta(x^{\ast}(u_{2}))$ optimal in (6) for $u_{2}$. By step
1 and inequality $x^{\ast}(u_{2})<\widetilde{x}(u_{2})$ we have
$p_{a}\leq\partial_{a}^{+}u_{2}<\partial_{a}^{-}u_{1}$ for all $a$, implying
$u_{1}(S)>p_{S}$ for all non empty $S$. We have now

$W_{2}(u_{1};x^{\ast}(u_{2}))\geq\min_{\varnothing\subseteq S\subseteq
A}(u(S)-p_{S})+x^{\ast}(u_{2})=x^{\ast}(u_{2})$

Because $W_{2}(u_{1};y)\leq y$ for all $y$ we see that $W_{2}(u_{1};y)=y\geq
W_{2}(u_{2};y)$ for all $y\leq x^{\ast}(u_{2})$.

Gathering the first and last statements in this step we conclude that
$L_{2}(u_{1};\cdot)$ and $W_{2}(u_{1};\cdot)$ intersect beyond
$x^{\ast}(u_{2})$ so agent $u_{1}$’s safe bid makes her the Seller in stage 2.
We showed a few lines ago $u_{1}(S)>p_{S}$ for any $S$ and any possible price
charged by agent $u_{2}$ therefore agent $u_{1}$ will buy all the goods and
the proof is complete. $\blacksquare$

## References

  * [1] Alkan A, Demange G, Gale D. 1991. Fair allocation of indivisible objects and criteria of justice, Econometrica, 59, 1023-1039.
  * [2] Aragones E. 1995. A derivation of the money rawlsian solution, Social Choice and Welfare, 12, 3, 267-276
  * [3] Avvakumov S, Karasev R. 2019. Envy-free Division under Mapping Degree, forthcoming Maths Operations Research, arxiv.org/pdf/1907.11183.pdf
  * [4] Aziz H. 2020. Developments in multi-agent fair allocation, AAAI, pages 13563–13568.
  * [5] Babaioff M, Tomer E, and Feige U. 2021. Fair-share allocations for agents with arbitrary entitlements. In P´eter Bir´o, Shuchi Chawla, and Federico Echenique, editors, EC, p.127.
  * [6] Bogomolnaia A, Moulin H. 2020. Guarantees in Fair Division: general and monotone preferences, forthcoming Maths Operations Research,arXiv:1911.10009v3 [econ.TH].
  * [7] Bouveret S, Lemaitre M. 2016. Characterizing conflicts in fair division of indivisible goods using a scale of criteria. Auton Agent Multi-Agent Syst, 30:259–290.
  * [8] Budish E. 2011. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. J. Polit. Econ. 119, 6, 1061–103.
  * [9] Cramton P, Gibbons R, Klemperer P. 1987. Dissolving a partnership efficiently. Econometrica 55(3):615–632.
  * [10] Cramton, P., Shoham, Y., & Steinberg, R. (Eds.). 2006. Combinatorial auctions. Cambridge: MIT Press.
  * [11] Crawford V P 1979. A Procedure for Generating Pareto-Efficient Egalitarian Equivalent Allocations,” Econometrica, 47,49-60.
  * [12] Demange G. 1984. Implementing Efficient Egalitarian Equivalent Allocations, Econometrica, 52,5,1167-1177.
  * [13] Demko S, Hill T P. 1988. Equitable distribution of indivisible objects, Math. Soc. Sci., 16, 145-158.
  * [14] Gal Y,Mash M,Procaccia A d, Zick Y. 2017. Which Is the Fairest (Rent Division) of Them All?, Journal of the ACM, Vol. 64, No. 6, Article 39, November 2017.
  * [15] Goldman J, Procaccia A D. 2014. Spliddit: Unleashing Fair Division Algorithms, SIGecom Exchanges 13, 2, 41–46.
  * [16] Grabisch M. 2016. Set functions, games and capacities in decision making, Theory and Decison Library #46, Springer.
  * [17] Kunreuther H, Kleindorfer, P R. 1986. A Sealed-Bid Auction Mechanism for Siting Noxious Facilities.” American Economic Review, May 1986 (Papers and Proceedings), 76, 2, 295-299.
  * [18] Kuhn, H.1967. On games of fair division, Essays in Mathematical Economics in Honour of Oskar Morgenstern, Princeton University Press, pp. 29–37.
  * [19] Mas-Colell A, Whinston MD, Green JR. Microeconomic Theory. Oxford University Press New York, 1995.
  * [20] Moulin, H. 1992. An application of the Shapley value to fair division with money. Econometrica, 60, 1331–1349.
  * [21] Moulin H. 2019. Fair Division in the Internet Age, Annual Review of Economics,11:407-41.
  * [22] Procaccia AD, Wang J. 2014. Fair enough: guaranteeing approximatemaximin shares, Proceedings of the 14th ACM Conference on Economics and Computation (EC ‘14), p.675–92. New York: ACM
  * [23] Steinhaus H. 1948. The Problem of Fair Division. Econometrica, 16:101–104.
  * [24] Steinhaus H. 1949. Sur la division pragmatique Econometrica (supplement), 17, 315-319.
  * [25] Svensson L G. 1983. Large Indivisibles: An Analysis with Respect to Price Equilibrium and Fairness, Econometrica,51,4,939-954.
  * [26] Tadenuma K, Thomson W. 1993. The fair allocation of an indivisible good when monetary compensations are possible. Math Soc Sci 25: 117–132
  * [27] Walsh T. 2020. Fair division: The computer scientist’s perspective. In IJCAI, pages 4966–4972.