[name=Theorem, sibling=theorem]rThm [name=Lemma, sibling=lemma]rLem
[name=Corollary, sibling=corollary]rCor [name=Proposition,
sibling=theorem]rPro

# Fair Shares: Feasibility, Domination and Incentives

Moshe Babaioff, Uriel Feige Microsoft Research — E-mail:
<EMAIL_ADDRESS>Institute and Microsoft Research — E-mail:
<EMAIL_ADDRESS>
###### Abstract

We consider fair allocation of a set ${\cal{M}}$ of indivisible goods to $n$
equally-entitled agents, with no monetary transfers. Every agent $i$ has a
valuation function $v_{i}$ from some given class of valuation functions. A
_share_ $s$ is a function that maps a pair $(v_{i},n)$ to a non-negative
value, with the interpretation that if an allocation of ${\cal{M}}$ to $n$
agents fails to give agent $i$ a bundle of value at least equal to
$s(v_{i},n)$, this serves as evidence that the allocation is not fair towards
$i$. For such an interpretation to make sense, we would like the share to be
_feasible_ , meaning that for any valuations in the class, there is an
allocation that gives every agent at least her share. The maximin share (MMS)
was a natural candidate for a feasible share for additive valuations. However,
Kurokawa, Procaccia and Wang [2018] show that it is not feasible.

We initiate a systematic study of the family of feasible shares. We say that a
share is _self maximizing_ if truth-telling maximizes the implied guarantee
(the worse true value of any bundle that gives the share with respect to the
report). We show that every feasible share is dominated by some self-
maximizing and feasible share. We seek to identify those self-maximizing
feasible shares that are polynomial time computable, and offer the highest
share values. We show that a SM-dominating feasible share – one that dominates
every self-maximizing (SM) feasible share – does not exist for additive
valuations (and beyond). Consequently, we relax the domination property to
that of domination up to a multiplicative factor of $\rho$ (called _$\rho$
-dominating_). For additive valuations we present shares that are feasible,
self-maximizing and polynomial-time computable. For $n$ agents we present such
a share that is $\frac{2n}{3n-1}$-dominating, and is $\frac{4}{5}$-dominating
when $n\leq 4$. For two agents we present such a share that is
$(1-\epsilon)$-dominating. Moreover, for each of these shares we present a
polynomial time algorithm that computes allocations that give every agent at
least her share.

##  1 Introduction

There is a large literature concerning the fair partition of indivisible goods
among agents with equal entitlements to the items, without monetary transfers.
Central to this problem is the definition of what is “fair” and when should an
agent claim that she was treated unfairly be considered founded. One can
roughly partition the approaches in the literature to two. The first aims to
eliminate (or minimize) envy between the agents.111This approach is based on
envy-freeness and its relaxations, we discuss it in Section 1.3. The other
aims to give each agent the value she “deserves”, or close to it.

In this paper we follow the latter approach, considering fairness based on the
value that an agent obtains from the items she gets (relative to her own
valuation). Prior work have defined some specific notions of _shares_ , and in
particular, the maximin share (known as MMS) which is the highest value that
the worse-off agent gets, when all agents have the same valuation.
Intuitively, a share aims to capture the value the agent should always get, no
matter what the valuations of the others are. The maximin share (MMS) was a
natural candidate for a share such that for any additive valuations of the
participating agents, there is an allocation that gives every agent her share
(as this is so when valuations are identical). However, Kurokawa, Procaccia
and Wang [25] show that there are instances for which it is not possible to
give every agent her MMS share.

We are not aware of prior work that attempts to formally define what a “share”
means as a general concept, and which properties it should satisfy. In this
paper we aim to address this issue, formalizing the notion of a _share_ and of
a _feasible share_ , studying relation between different shares (domination)
and studying incentives for truthful valuation reporting. A share may serve as
a fairness notion for a given class of valuations if it is _feasible_ ,
meaning that for any valuations of the agents in the class, there is an
allocation that gives every agent at least her share. When a share is
feasible, allocations that do not give some agent her share may plausibly be
considered not to be fair. Thus, a feasible share serves as a lower bound on
the value that an agent can expect to get, for any valuations of the others.
As discussed above, the MMS is not feasible.

###  1.1 Shares as Contracts

We introduce properties that we would like shares to have. In order to
motivate these properties, we take the view that shares can be interpreted as
contracts. This view and its implications are presented in this section.

We consider fair allocation of a set ${\cal{M}}$ of indivisible goods to $n$
equally-entitled agents, with no monetary transfers. Every agent $i$ has a
valuation function $v_{i}$ from some class of valuations ${\mathcal{C}}$. The
valuation assigns a value $v_{i}(S)$ to any bundle $S\subseteq{\cal{M}}$.
Valuations are assumed to be normalized ($v_{i}(\emptyset)=0$) and monotone
non-decreasing. We formalize the notion of a _share_ as a function that maps a
pair $(v_{i},n)$ to a non-negative value $s(v_{i},n)$, and the function
satisfies some minimal requirements (independence of item names222That is,
permuting the names of the items does not change the value of the share. In
particular, the share does not rely on different agents agreeing on the names
of the items. and being _realizable_ : no larger than the value of the most
valuable bundle, which is $v({\cal{M}})$ when items are goods). Note that to
capture the ex-ante symmetry between the players (all have equal entitlement
to the goods), the share function is anonymous: the function is the same for
all agents and does not depend on the identity of the agent applying it.

It is instructive to think of the notion of a share as if it is a contract
between the agent and the entity that produces the allocation. We refer to
this entity as the allocator. (Depending on the setting, the allocator can
take one of many different forms, such as an actual person doing the
allocation, or an algorithm doing the allocation.) The context of the contract
is a set ${\cal{M}}$ of items, a number $n$ of agents, and a class
${\mathcal{C}}$ of valuation functions. The terms of the contract are that the
agent reports an allocation function $v$ in the class ${\mathcal{C}}$, and the
allocator guarantees that the agent will get a bundle that she values at least
as (her share) $s(v,n)$. Consequently, for a given $v\in{\mathcal{C}}$, the
contract partitions the set of bundles into two: those bundles $B$ that are
_acceptable_ , namely, satisfy $v(B)\geq s(v,n)$, and those that are not
acceptable ($v(B)<s(v,n)$). Given a share $s$ and valuation $v$, the _share
guarantee_ $\hat{s}(v,n)$ is defined to be the value of the least valuable
acceptable bundle for $v$. The contract gives some rights to the agent,
namely, the right to receive an acceptable bundle. The contract also gives
rights to the allocator, namely, the right to choose which of the acceptable
bundles to give to the agent.

We now list properties that we desire contracts to have. They motivate
concepts considered in the current paper.

  * •

Feasibility. The allocator offers shares to all agents of the allocation
instance. Viewing shares as contracts, a natural requirement is that they do
not contradict each other, so that the allocator can fulfil his side of the
contract with respect to every agent. In the terminology of the paper, we say
that a share is feasible if for every allocation instance there is an
allocation that gives every agent an acceptable bundle. Such an allocation
will be referred to as an _acceptable allocation_.

  * •

Legibility (poly-time computability). A contract should be written in such a
language that the parties to the contract can understand its content. In the
context of shares, the content is the value of the function $s(v,n)$. In a
computational setting, we interpret the notion of “understanding” as that of
being able, given $n$ and $v$ (or if $v$ does not have a succinct
representation, then access to $v$ using value queries), to compute in
polynomial time the value $s(v,n)$ of the share. Thereafter, upon receiving a
bundle $B$, the agent can determine whether the allocator has fulfilled his
side of the contract. The agent can also determine whether she was fortunate
to get a value much larger than her share. Likewise, the allocator can test
whether his proposed allocation to the agents fulfills his side of the
contract with every agent.

  * •

Incentive for truthful reporting (self maximizing). Suppose that an agent
evaluates a contract by her value to the worst possible acceptable bundle
under the contract.333The assumption that agents are risk averse is common in
the literature of fair division, e.g., when considering the behaviour of the
splitting agent in the _cut-and-choose_ protocol (equal cut is optimal only
under worse-case assumption about the other’s valuation). We assume that this
risk aversion extends beyond the valuations of others, and holds also to with
respect to choice of allocation (satisfying the contract). Indeed, for most
valuation classes of interest (e.g., unit demand, additive, submodular,
subadditive), the agent might get this worst bundle, under an adversarial
choice of an acceptable allocation and valuation functions for the other
agents (see Proposition 13). As part of the contract, the agent reports a
valuation function. Incentive for truthful reporting in this context means
that the agent cannot get a better contract by reporting a different valuation
function $v^{\prime}$ instead of her true valuation function $v$. This serves
two purposes. One is that the agent need not waste efforts in figuring out
which report gives her the best contract – she can simply report her true
valuation function. The other is that by receiving the true valuation
functions of all agents, the allocator holds the relevant information that is
needed in order to serve both the goal of giving each agent at least her share
according to her true valuation function, and in order to obtain any auxiliary
goals of the allocation mechanism (such as maximizing welfare), if there are
such goals. The notion of a share giving incentive for truthful reporting
should not be confused with the notion of an allocation mechanism being
incentive compatible. The former concerns getting the best contract, and the
report of the agent can be given even before an allocation algorithm has been
decided upon. The latter concerns getting the best bundle, and requires that
the allocation algorithm be fixed before the agent reports a valuation
function. We shall refer to shares that give incentive for truthful reporting
as being self maximizing, so as to avoid confusion with the notion of an
allocation mechanism being incentive compatible.

An example of a share that is feasible, poly-time computable and self-
maximizing, even when ${\mathcal{C}}$ is the class of all monotone valuation
functions (items are goods), is a share that we shall denote by $s_{n}$, where
$s_{n}(v,n)$ is the value of the $n$-th most valuable item according to $v$.
Feasibility is established by the following allocation mechanism, that we
shall refer to as $AM_{n}$. Sort the agents in an arbitrary order, and let
$v_{i}$ denote the valuation function reported by agent $i$. Items are
allocated in rounds. In round $i<n$ agent $i$ gets an item of highest value
according to $v_{i}$, among the items not yet allocated. In round $n$, agent
$n$ gets all remaining items. Under $AM_{n}$, every agent $i$ gets a bundle
that contains at least one of her top $n$ items, and as valuation functions
are monotone, agent $i$ receives a bundle of value at least $s_{n}(v_{i},n)$.
Poly-time computability of $s_{n}$ is evident444As $m$ value queries suffice
in order to determine the value of every single item, and after sorting these
values, the $n$-th largest value is the value of the share.. The share $s_{n}$
is self-maximizing because for every report $v^{\prime}_{i}$, the allocator is
allowed to allocate to the agent any one of the top $n$ items according to
$v^{\prime}_{i}$, and the true value of the worst of these items (value
according to $v_{i}$) cannot have value larger than $s_{n}(v_{i},n)$, the
$n$-th most valuable item according to the true valuation $v_{i}$.

The reader may have observed that $AM_{n}$ is an incentive compatible
allocation mechanism. Agent $i$ cannot improve her allocation by reporting a
different $v^{\prime}_{i}$ instead of her true $v_{i}$. Hence the share
$s_{n}$ has an associated incentive compatible allocation mechanism. However,
nothing in the definition of the share $s_{n}$ requires that this particular
mechanism be used. For example, the allocator is free to implement a round
robin allocation instead (agent $i$ selects items in rounds $i+kn$ for
$k\in\\{0,1,2,\ldots\\}$, where in each such round she gets the yet not
allocated item of highest marginal value relative to the set of items that she
already holds). The round robin allocation gives every agent value of at least
her share value $s(v,n)$, but is not an incentive compatible allocation
mechanism: depending on valuation functions of other agents, agent $i$ might
improve her allocation by reporting a different $v^{\prime}_{i}$ instead of
her true $v_{i}$.

One may further observe that the allocation algorithm $AM_{n}$ actually offers
every agent a share that dominates $s_{n}$ (always of value at least $s_{n}$,
and sometimes higher). We refer to this share as $s_{n-1}$, where
$s_{n-1}(v,n)$ is the minimum between the value of the $(n-1)$-th most
valuable item according to $v$, and the value of the least valuable bundle
among those containing $m-n+1$ items. Like $s_{n}$, the share $s_{n-1}$ is
also feasible (by allocation algorithm $AM_{n}$), self maximizing (as we prove
later, see Lemma 14, for example), and when valuations are additive, it is
also poly-time computable.

Given the above examples of $s_{n}$ and $s_{n-1}$, and the fact that agents
are better off when $s_{n-1}$ is the share rather than $s_{n}$, it is natural
to ask (for a given class ${\mathcal{C}}$ of valuations) whether there is a
feasible share that is the “best possible” – at least as large as any other
feasible share. Share $s$ _dominates_ share $s^{\prime}$ for a class of
valuations functions ${\mathcal{C}}$, if for every $n$ (for which the share is
defined) and for every valuation $v\in{\mathcal{C}}$ it holds that $s(v,n)\geq
s^{\prime}(v,n)$. For a given class ${\mathcal{C}}$ of valuations, a feasible
share is a _dominant feasible share_ if it dominates every other feasible
share for that class. A feasible share is a _SM-dominant feasible share_ if it
dominates every other feasible share that is self maximizing (SM).

###### Question 1

For which classes ${\mathcal{C}}$ of valuations is there a share that is
feasible (and better still, also self maximizing and poly-time computable)
that dominates all other feasible shares (or at least dominates those feasible
shares that are self maximizing)?

As we shall see, there are classes ${\mathcal{C}}$ for which SM-dominant
feasible shares do not exist. Moreover, we show that the class of additive
valuations over goods does not have a feasible share that dominates every
self-maximizing feasible share that is poly-time computable. This leads to a
relaxed version of the above question, in which we look for a feasible share
that dominates a scaled-down version of any other feasible share. Formally,
for $\rho\geq 0$, share $s$ _$\rho$ -dominates_ share $s^{\prime}$ for a class
of valuations functions ${\mathcal{C}}$, if for every valuation
$v\in{\mathcal{C}}$ it holds that $s(v,n)\geq\rho\cdot s^{\prime}(v,n)$.
Feasible share $s$ is a _$\rho$ -dominating share_ for class ${\mathcal{C}}$
if it $\rho$-dominates every other feasible share for ${\mathcal{C}}$ (self
maximizing or not).

###### Question 2

For a given class ${\mathcal{C}}$, what is the maximum value of $\rho$ (where
$0\leq\rho\leq 1$) for which there is a feasible share (and better still, also
self maximizing and poly-time computable) that is $\rho$-dominating for
${\mathcal{C}}$?

In Appendix A we discuss auxiliary goals and the fact that there might be a
tradeoff between such goals and maximizing $\rho$ when picking a
$\rho$-dominating share. In Appendix B we discuss the possibility of combining
a guarantee to give agents at least their share with additional non-binding
“statements of intent” to provide allocations with additional desirable
properties.

Our paper is concerned with the above questions. We next describe our results.

###  1.2 Our Results

We start by considering Question 1, which asks for which classes of valuations
there exists a share that is feasible and that dominates every other feasible
share (or at least dominates those feasible shares that are self maximizing).
We first observe that whenever the MMS is feasible, it is a feasible share
that dominates every other feasible share, and the unique one (see Proposition
4). For example, this is the case for the class of unit-demand valuations, in
which the MMS (which is the value of the $n^{th}$ most valuable item) is
feasible. In contrast, our main negative result shows that for any class of
valuations that contains the additive valuations, a _dominant feasible share_
(a share that dominates every other feasible share) does not exist. Moreover,
there does not exist a _SM-dominant feasible share_ : a share that dominates
every other feasible share that is self maximizing (SM).

###### Theorem 1

Let ${\mathcal{C}}$ be any class of valuations that contains all additive
valuations over goods. For ${\mathcal{C}}$, there is no feasible share that
dominates all feasible shares that are self maximizing. Thus, there does not
exist an SM-dominant feasible share for class ${\mathcal{C}}$.

Note that the impossibility result holds although we do not require the
dominating share itself to be self maximizing. Additionally, note that our
impossibility result does not rely on bounded computational power – it holds
even when there are no computational constraints.

We prove the theorem by defining a family of shares that are feasible and are
self maximizing for any class ${\mathcal{C}}$ of valuations.555For additive
valuations these shares are also poly-time computable. We also show that for
each additive valuation, there is a share in the family that has value that is
the same as the MMS for that valuation. Thus, to dominate all these shares,
the dominating share must dominate the MMS. To complete the proof we use the
fact that the MMS is not feasible for additive valuations ([25]).

The theorem can also be proven as a corollary of another result that we prove
and is of independent interest. We show that any feasible share can be
transformed to a feasible share that dominates it, and is self-maximizing.
Thus, in a sense, we can always assume that a feasible share is self-
maximizing. This transformation is not done in polynomial time, thus, when
computation is important, this transformation does not show that self
maximization comes for free (computationally).

###### Theorem 2

Let ${\mathcal{C}}$ be an arbitrary class of valuation functions, and let $s$
be an arbitrary feasible share for class ${\mathcal{C}}$. Then for class
${\mathcal{C}}$ there exists a feasible share $s^{\prime}$ that dominates $s$
and is self-maximizing.

Theorem 1 shows that there is no SM-dominating feasible share for additive
valuations and beyond. The direct implication of this result is that there is
no ”ultimate” feasible share for these classes: no matter how we define a
feasible share, there will always be room for additional shares not dominated
by it.

We thus move our focus to Question 2, and consider the problem of finding a
share that is poly-time computable and self maximizing and is a
$\rho$-dominating feasible share. That is, we relax exact domination to
approximate domination, and look for shares that are $\rho$-dominating and
have $\rho$ that is as large as possible. We first observe that for any class
of valuations ${\mathcal{C}}$, a share is a $\rho$-dominating feasible share
if and only if it $\rho$-dominates the MMS (see Proposition 6).

The rest of our paper focuses on additive valuations over items that are
goods. Observe that as the MMS is not feasible for more than two agents, and
hard to compute even for two agents, we cannot hope to find a
$\rho$-dominating share for $\rho=1$, and not even for two agents (if we want
the share to be polynomial time computable). We thus look for poly-time
computable and self maximizing feasible shares that are $\rho$-dominating,
with $\rho<1$ that is as large as possible.

We present a class of shares for additive valuations over goods which we call
ordinal maximin shares, and show that every share in this class is self
maximizing. Moreover, for two agents, any share in this class is feasible. We
then present several $\rho$-domination results, for each we define a share
that is an ordinal maximin share (thus self maximizing), and we show that each
is feasible and can be computed in polynomial time.

###### Theorem 3

For the class of additive valuations over goods with $n$ agents, there exists
a share that is feasible, self-maximizing, polynomial-time computable and
$\frac{2n}{3n-1}$-dominating. For at most four agents this share is
$\frac{4}{5}$-dominating. Furthermore, for two agents, for any positive
$\epsilon$ there exists a share that is feasible, self-maximizing, polynomial-
time computable and is $(1-\epsilon)$-dominating.

Interestingly, the result for four agents implies the first known poly-time
allocation algorithm that gives every agent a $\frac{4}{5}$ fraction of her
MMS (the prior result of $\frac{4}{5}$ by [19] was only existential).

We remark that it is known [22] that for additive valuations it is possible to
find an allocation that gives every agent
$\left(\frac{3}{4}+\frac{1}{12n}\right)$ fraction of her MMS. This immediately
implies that the $\left(\frac{3}{4}+\frac{1}{12n}\right)$-MMS is a share that
is feasible. Yet, this share is not self maximizing, as so is the case for any
$\rho$-MMS share for $\rho<1$ (see Proposition 2). One can apply Theorem 2 on
this share, to transform it to a feasible share that is self maximizing and
$\left(\frac{3}{4}+\frac{1}{12n}\right)$-dominating, but the transformation is
not poly-time computable. Alternatively, one can consider the poly-time
algorithm of [22] that finds an allocation that gives every agent
$\frac{3}{4}$ of her MMS and use it to define a polynomial time computable
share as follows: for valuation $v$ the share is defined to be the lowest
value of any of the $n$ bundles that the algorithm outputs, when the input is
$n$ agents each with valuation $v$ (same valuation $v$ for all agents).
However, such a share would not be self maximizing666For example, if $n=2$ and
item values are $9,5,5,1$, then the bundle containing only the first item is
acceptable under this share. However, if the values $6,5,5,4$ are reported
instead, then every acceptable bundle that might be allocated by the algorithm
of [22] has value at least 10, with respect to both the reported valuation and
the true valuation.. Moreover, it is not clear whether this share is
feasible777One might hope that given additive valuations $v_{1},\ldots,v_{n}$,
running the allocation algorithm of [22] on these valuation functions will
produce an allocation that gives every agent at least her share. However, this
might not be true, because the share value for each agent $i$ is determined by
running the algorithm on a different instance, one in which all valuation
functions are $v_{i}$. A-priori, there is no reason to believe that in the
former run agent $i$ would necessarily get a higher value than the share value
determined by the latter run.. We leave open the problem of finding the
largest value of $\rho$ for which there is a $\rho$-dominating share that is
feasible, self maximizing, and poly-time computable for additive valuations.

###  1.3 Related Work

In our work we initiate a systematic study of the notion of fair shares in
item allocation problems. We are not aware of any previous such systematic
studies. However, various shares have been proposed in previous work, and were
extensively studied. For divisible items and additive valuations, the
proportional share (PS) can always be guaranteed, or using the terminology of
the current paper, it is feasible. For indivisible items, the PS is not
feasible. This served as partial motivation for introducing other types of
shares, and the one which has been most extensively studied is the maximin
share (MMS), introduced in [11]. For additive valuations, the MMS is no larger
than the PS, though for non-additive valuations it may be larger. It turns out
that for additive valuation and $n\geq 3$, also the MMS is not feasible [25].
This led to multiple works [25, 4, 19, 8, 17, 20 ,22, 16] trying to determine
the best ratio $\rho$ such that in instances with additive valuations, there
always is an allocation giving every agent a bundle of value at least a $\rho$
fraction of her MMS (a $\rho$-MMS allocation). The current known bounds on
$\rho$ for general $n$ are $\frac{3}{4}+\Theta(\frac{1}{n})\leq\rho\leq
1-\frac{1}{n^{4}}$. For $n=3$, the bounds are
$\frac{8}{9}\leq\rho\leq\frac{39}{40}$. The definition of MMS easily extends
to non-additive valuations, though the values of $\rho$ for which $\rho$-MMS
allocations are guaranteed to exist deteriorate the more we extend the class
of valuations (see 17).

The fact that the MMS is not feasible led to consideration of other notions of
shares. A closely related notion is the “$1$-out-of-$d$” share (see [24], for
example), in which in an instance with $n$ agents, the share of the agent is
the value of her MMS in instances with $d$ agents. If $d$ is sufficiently
larger than $n$ ($d=2n$ certainly suffices, and it is an open question whether
$d=n+1$ suffices), then the “$1$-out-of-$d$” share becomes feasible. However,
it does not provide any approximation to the MMS (for $d>n$ the “$1$-out-
of-$d$” share might be 0 even when the MMS is strictly positive). A different
type of share is the Truncated-Proportional Share (TPS) [6]. Its value (for
additive valuations) lies between the PS and the MMS, and hence it is not
feasible. (The TPS was not introduced so as to handle feasibility issues, but
for different reasons: using the TPS simplifies proofs concerning the
approximation ratios achievable by allocations.)

The main focus of our paper is the fair allocation of indivisible _goods_ to
agents with _equal_ entitlement. Shares have been extended to other related
settings. One such setting is allocation of chores (items of negative value).
See for example [5, 23]. Another such setting is that of agents of arbitrary
entitlement. This setting led to definitions of additional types of shares,
including the WMMS [14] (which in fact does not qualify as a share under our
definitions, as it depends on more than just the valuation and entitlement of
the agent), the “$\ell$-out-of-$d$” share [10], and the AnyPrice Share (APS)
[7]. We briefly discuss these related settings in Section 7.

In the current paper, the criterion for “fairness” of allocations is based on
shares. Other fairness criteria have also been extensively studied. For
additive valuations, the notion of envy freeness provides a strengthening of
the proportionality requirement, in the sense that every envy free allocation
(one in which no agent envies the bundle received by a different agent) offers
every agent at least her proportional share, and hence at least also her MMS.
(For non-additive valuations, envy free allocations need not give every agent
her MMS.) Envy free allocations exist for divisible items (and additive
valuations), but need not exist for indivisible items. A relaxation of envy
freeness, envy-free-up-to-one-good (EF1) [11], is feasible for every class of
valuation functions [26], but does not even offer better than a $\frac{1}{n}$
approximation to the MMS when valuations are additive888For example, in an EF1
allocation in which an agent gets a single item of value 1, and every other
agent gets one item of value 1 and one item of value $n$.. An intermediate
notion, envy-free-up-to-any-good (EFX) [13], does offer a constant
approximation to the MMS when valuations are additive, but it is not known if
it is feasible beyond two agent for general valuations, and beyond three
agents when valuations are additive (this is a well known open question [27]).
In the current paper, we do not address envy-based fairness notions.

A self-maximizing share provides incentives to risk-averse agents to report
their true valuations, in settings in which they do not know the inner details
of the allocation mechanism and the valuations of other agents. However, if
agents do know (or have beliefs about) what valuation functions others agents
report and how the allocation algorithm actually works, then the question of
whether the underlying share is self-maximizing might become irrelevant. This
is because the agent no longer needs to use the share value as an indication
to what value she will receive – she can instead simulate runs of the
allocation algorithm to rank her possible reports based on her beliefs, and
report accordingly. The allocation algorithm $AM_{n}$ presented in Section 1.1
(and well known also from previous work [2]) is incentive compatible even in
such full information settings, but does not offer the agents a good
approximation to their MMS value. More generally, no allocation algorithm that
offers a good approximation to the MMS (and allocates all items) is incentive
compatible in the full information setting [2]. In contrast, we are able to
combine incentives and a good approximation to the MMS, but our incentives are
not for an _allocation algorithm_ but rather for the _share guarantee_.

##  2 Model

We consider fair allocation of a set ${\cal{M}}$ of $m$ indivisible items to a
set ${\cal{N}}$ of $n$ agents with equal entitlements to the items, without
monetary transfers. Each agent’s preference over subsets of items is captured
by a _valuation_ $v$ which is a function that maps every subset of items
$S\subseteq{\cal{M}}$ to a non-negative value $v(S)$ that the agent derives
from getting $S$. We assume that $v$ is normalized: $v(\emptyset)=0$. If $v$
is non-decreasing then the items are referred to as goods (with respect to
$v$). Throughout the paper we assume items are goods, except when explicitly
stated otherwise.

A valuation $v$ over the set of goods ${\cal{M}}$ is called additive if each
good $j\in{\cal{M}}$ is associated with a value $v(j)\geq 0$, and the value of
a set of goods $S\subseteq{\cal{M}}$ is $v(S)=\sum_{j\in S}v(j)$. A valuation
$v$ is called unit-demand if each good $j\in{\cal{M}}$ is associated with a
value $v(j)\geq 0$, and the value of a set of goods $S\subseteq{\cal{M}}$ is
$v(S)=\max_{j\in S}v(j)$.

Let $v_{i}(\cdot)$ denote the valuation of agent $i$, and let
$\textbf{v}=(v_{1},\ldots,v_{n})$ denote the vector of agents’ valuations. We
assume that there are no transfers (no money involved). The set of items
${\cal{M}}$ needs to be partitioned between the agents in a fair way. In this
work we consider deterministic allocations (partitions). An _allocation_ $A$
is a partition of the items to $n$ disjoint bundles $A_{1},\ldots,A_{n}$ (some
of which might be empty), where $A_{i}\subseteq{{\cal{M}}}$ for every
$i\in{\cal{N}}$. We denote the set of all allocations of ${\cal{M}}$ to the
$n$ agents by $\mathcal{A}$.

We next present the definitions of several types of shares that were
introduced in prior work. For a setting with $n$ agents with valuations over a
set ${\cal{M}}$ of items, the proportional share (PS) of an agent with
valuation $v$ is $PS_{{n}}(v)=\frac{v({\cal{M}})}{n}$. For indivisible items,
it might not possible to give every agent her proportional share, for example,
if there are fewer items than agents. The _maximin share (MMS)_ aims to
address this issue. The MMS of an agent is the highest value that she can
ensure herself by splitting the goods to $n$ bundles and getting the worst
one.

######  Definition 1 (maximin Share (MMS))

The _maximin share (MMS)_ of an agent with valuation $v$ over a set of items
${\cal{M}}$, when there are $n$ agents, which we denote by $MMS_{n}(v)$, is
defined to be the highest value she can ensure herself by splitting the item
in ${\cal{M}}$ to $n$ bundles and getting the worst one. Formally:

$MMS_{n}(v)=\max_{(A_{1},\ldots,A_{n})\in\mathcal{A}}\min_{j\in[n]}\left\\{v(A_{j})\right\\},$

When $v$ and $n$ are clear from context we simply use the term MMS to denote
the MMS share $MMS_{n}(v)$.

Somewhat surprisingly, there are allocation instances with additive valuations
over goods for which there is no allocation that gives every agent her MMS
[25]. In this work we study shares can be concurrently given to all agents,
the relations between such shares, and properties of such shares.

##  3 Shares and the Quest for a Dominant Feasible Share

In this section we formally define the notions that we study in this paper and
prove some basic properties of these notions. We start with the definition of
a _share_ and the _share guarantee_. We then move to discuss _feasible shares_
and _self-maximizing shares_. We conclude with _share domination_ and the
notions of _dominant feasible shares_ and _SM-dominant feasible shares_.

We start by formalizing the notion of a _share_ for a class of valuations. A
_share_ for a class of valuations ${\mathcal{C}}$ is a function mapping the
set ${\cal{M}}$ of items, a valuation $v$ in ${\mathcal{C}}$ and number $n$ of
agents, to a real value. The share is required to be realizable (no larger
than the value of the most valuable bundle, which is $v({\cal{M}})$ when items
are goods) and to not depend on names of items. To give an agent her share, we
must give her a bundle of value at least her share - the minimal such value is
defined to be her _share guarantee_.

###### Definition 2

A share function (or simply _share_) $s$ for a class of valuations
${\mathcal{C}}$ is a function that outputs a real value $s(v,n)$ when given
two parameters: a valuation function $v\in{\mathcal{C}}$ over a set of items
${\cal{M}}$, and the number of agents $n$. It needs to satisfy two properties:

  * •

Realizability: for every $v\in{\mathcal{C}}$ and $n$ it holds that
$s(v,n)\leq\max_{S\subseteq{\cal{M}}}v(S)$.999For the case that items are
goods this condition is simply $s(v,n)\leq v({\cal{M}})$. We present this
general definition so that it will apply to valuations that are not
necessarily over goods, e.g, apply when items that are chores (bads).

  * •

Name independence: renaming the items does not change the value of the share.

Given a share function $s$, a bundle $S$ is _acceptable_ for agent with
valuation $v$ and share $s$, if its value is at least the share guarantee:
$v(S)\geq s(v,n)$.

Given a share function $s$, the associated share guarantee $\hat{s}$ is
defined as the function satisfying

$\hat{s}(v,n)\doteq\min_{\\{S\;|\;v(S)\geq s(v,n)\\}}v(S).$

Namely, for any given input, the share guarantee is the minimum value of a
bundle whose value is at least as high as the share for that input.
Alternatively, for any valuation $v$, the share guarantee is the lowest value
of any acceptable bundle for the valuation $v$ and share $s$.

Observe that for every share $s$, the realizability property implies that the
corresponding share guarantee is well defined. When items are goods, the
realizability property implies that the corresponding share guarantee is non-
negative. Every allocation that gives an agent a bundle of value at least
equal to the share, necessarily gives the agent a bundle of value at least
equal to the share guarantee. As a simple example, if there are two agents
($n=2$) and there are two items with $v(e_{1})=1$ and $v(e_{2})=2$, then the
proportional share guarantee is $2$ (whereas the proportional share is only
$\frac{3}{2}$).

We remark that for any share that is defined to be a value of some bundle
(like the MMS), the share guarantee is the same as the share itself. Yet, for
a share that is not defined as a value of a bundle (like the proportional
share), the share guarantee might be strictly larger than the share.

The intended interpretation of a share guarantee is as a guarantee to an agent
$i$ who reports her true valuation function $v_{i}$: if the underlying
allocation algorithm is one that gives every agent at least her share
(according to the reported valuation functions), then regardless of the
reports of all other agents, agent $i$ is guaranteed to receive a bundle of
value at least equal to her share guarantee. Thus, we next discuss the concept
of a _feasible share_ , a share for which it is always possible to give every
agent an acceptable bundle according to the share.

###  3.1 Feasible Shares

We focus on shares for which every agent can always get her share. For a class
${\mathcal{C}}$ of valuation functions, we say that a share $s$ for
${\mathcal{C}}$ is _feasible_ if for any agents’ valuation vector
$\textbf{v}=(v_{1},\ldots,v_{n})$ such that $v_{i}\in{\mathcal{C}}$ for every
$i$, there exists an _acceptable_ allocation $A$: an allocation that gives
every agent an acceptable bundle. That is, for every agent $i$ the bundle
$A_{i}$ has value at least her share: $v_{i}(A_{i})\geq s(v_{i},n)$. Note that
by definition, an allocation that is acceptable must also gives every agent
$i$ a bundle of value at least her share guarantee, that is,
$v_{i}(A_{i})\geq\hat{s}(v_{i},n)$.

It is well known that feasible shares have the advantage that even in
strategic environments, agents will get their shares under equilibrium
behaviour.101010Such properties are much harder to prove for envy-based
fairness notions like EF1, see [1]. Fix any class of valuations
${\mathcal{C}}$, a share $s$ that is feasible for ${\mathcal{C}}$, and any
algorithm for share $s$: an algorithm that for any vector
$\textbf{v}^{\prime}=(v^{\prime}_{1},\ldots,v^{\prime}_{n})$ of $n$ reported
valuations in ${\mathcal{C}}$ outputs an allocation $A^{\prime}$ that gives
each agent her share with respect to her reported valuation
($v^{\prime}_{i}(A^{\prime}_{i})\geq s(v^{\prime}_{i},n)$). The mechanism that
is defined by the algorithm is not necessarily (dominant strategy) truthful
(as is the case for the round-robin mechanism for the share $s_{n}$ presented
in Section 1.1). Nevertheless, as the share is feasible, each agent has a
“safe strategy” (being truthful) which guarantees that she gets some minimal
utility (her share guarantee). This property implies that outcomes of the
mechanism will have nice utility guarantees even when agents are acting
strategically: if the algorithm is deterministic, in any pure Nash equilibrium
of the game, each agent’s utility must be at least her share guarantee.
Similarly, if agents are risk neutral, if the algorithm is randomized then in
any mixed Nash equilibrium of the game each agent’s expected utility must be
at least her share guarantee.111111Similar claim is also true for any mixed
Nash equilibrium in Bayesian settings.

As observed above, for any deterministic algorithm for a feasible share, in
any pure Nash equilibrium of the game, each agent’s utility must be at least
her share guarantee. Yet, not every allocation algorithm will induce a game in
which a pure Nash equilibrium exists. Does there always exist some algorithm
for a feasible share $s$ for which a pure equilibrium always exists? We next
show that such an algorithm indeed exists.

###### Proposition 1

Let $s$ be any feasible share. There exists an algorithm for share $s$ that
induces a full-information game in which a pure Nash equilibrium always
exists, and the equilibrium allocation is acceptable.

Proof. The game is defined as follows. First an arbitrary order over the
agents is fixed. Without loss of generality we assume that agents’ names are
according to the given order (so agent $1$ is the first, $2$ is second, etc.).
In the first stage, agents are approached according to that order, and each is
requested to report a valuation, after being informed of the reports of all
prior agents. We denote the reported valuation of agent $i$ by
$v^{\prime}_{i}$. Let $S^{\prime}$ be the family of all acceptable allocations
for share $s$ with respect to the reported valuations
$(v^{\prime}_{1},v^{\prime}_{2},\ldots,v^{\prime}_{n})$. As the share is
feasible the set $S^{\prime}$ is non-empty. Now, in the second stage, a
deterministic algorithm (that was fixed in advance) picks an allocation out of
$S^{\prime}$ and implements it. For example, the algorithm might pick the
first (according to some fixed order) welfare maximizing allocation in
$S^{\prime}$.

We next claim that in this game there exists a pure Nash equilibrium (and even
a subgame-perfect equilibrium). This holds as this is a full-information
sequential game, and thus can be solved by backward induction. Specifically,
in this subgame-perfect equilibrium, when considering her report, agent $n$,
knowing all reports $(v^{\prime}_{1},v^{\prime}_{2},\ldots,v^{\prime}_{n-1})$
of other agents and the deterministic algorithm that will be used to pick an
allocation, reports some valuation $v^{\prime}_{n}$ that maximizes her
utility. This serves as the base case for the induction. Similarly, any agent
$i$ (from $n-1$ to $1$), knowing all reports
$(v^{\prime}_{1},v^{\prime}_{2},\ldots,v^{\prime}_{i-1})$ of other agents
before her, and the strategies used by the agents that report after her (as
defined recursively by this procedure), reports some valuation
$v^{\prime}_{i}$ that maximizes her utility. These strategies clearly define a
subgame-perfect equilibrium. The allocation is acceptable as any agent can
guarantee she gets her share by being truthful, so her report must give her at
least as high utility as her share. $\blacksquare$

We note that the algorithm might not run in polynomial time, and even if it
does, it might be computationally hard to find these equilibrium strategies.

###  3.2 Self-Maximizing Shares

We next define the notion of a self-maximizing share. We say that a share
function is self-maximizing for a class of valuations ${\mathcal{C}}$ if for
every valuation function in ${\mathcal{C}}$, reporting the true valuation
function is a dominant strategy for maximizing the lowest value bundle (with
respect to the true valuation) among all bundles that are acceptable for the
reported valuation. To formalize this, we first define some useful notation.
For share $s$ and any valuation $v\in{\mathcal{C}}$, define the share _implied
guarantee_ when reporting $v^{\prime}\in{\mathcal{C}}$:

$\hat{s}_{{v}}({{v^{\prime}}})=\min_{\\{S\;|\;v^{\prime}(S)\geq
s(v^{\prime},n)\\}}v(S)$

to be the lowest true value of any set (measured by the true valuation $v$),
among all sets that are acceptable with respect to $v^{\prime}$. Observe that
the implied guarantee when the report is the true valuation is simply the
share guarantee, that is, $\hat{s}_{{v}}({{v}})=\hat{s}(v,n)$.

Note that in the definition of the implied guarantee, $v^{\prime}$ only
influences the family of bundles that are considered acceptable, yet the
values of these bundles are measured with respect to the _true_ valuation $v$.

The implied guarantee $\hat{s}_{{v}}({{v^{\prime}}})$ depends on
$s(v^{\prime},n)$ which depends on $n$, but as $n$ will always be clear from
the context we do not make this dependence explicit in the notation, in order
to keep the notation simple.

To illustrate the concept of the share implied guarantee, consider the
proportional share $s$ over additive valuations. Assume that $n=3$ and
consider valuations over four items, with items of values $(5,4,4,2)$ for
valuation $v$. The value of the share is $s(v,n)=5$ and the share guarantee is
$\hat{s}(v,n)=5$ as well. For reported valuation $v^{\prime}$ with reported
item values $(4,4,4,3)$, it holds that $s(v^{\prime},n)=5$ so no single item
forms an acceptable bundle, and the set of acceptable bundles for $v^{\prime}$
contains all bundles of size at least 2. The implied guarantee is the true
value of the least valuable pair, which has value of $6$ and thus the implied
guarantee when reporting $v^{\prime}$ is $\hat{s}_{{v}}({{v^{\prime}}})=6$.
Observe that this is larger than the share guarantee
($\hat{s}_{{v}}({{v^{\prime}}})=6>\hat{s}(v,n)=5$), so by misreporting the
implied guarantee increases.

With the notation of implied guarantee we can now formally define the notion
of self-maximizing share, a share in which truthful reporting ($v^{\prime}=v$)
maximizes $\hat{s}_{{v}}({{\cdot}})$, the implied guarantee:

###### Definition 3

A share $s$ is self-maximizing for class of valuations ${\mathcal{C}}$ if for
every set ${\cal{M}}$ of items and number of agents $n$, for every true
valuation $v\in{\mathcal{C}}$ and every report $v^{\prime}\in{\mathcal{C}}$ it
holds that

$\hat{s}_{{v}}({{v}})=\hat{s}(v,n)\geq\hat{s}_{{v}}({{v^{\prime}}})$

Let us briefly discuss the relation between a share being self-maximizing and
incentives to agents to report their true valuation functions
(“truthfulness”). Suppose first that we are in a setting in which the agent
knows the items and her valuation function. The agent does not know the
valuation functions of other agents, and does not know the details of the
allocation algorithm, except for the fact that it gives every agent at least
her share guarantee with respect to its input (the share is feasible), for a
share that is self-maximizing. In such a setting, for a risk averse agent who
wishes to maximize the minimum possible value that it receives (minimum
possible with respect to the information that the agent does not have), being
truthful is a dominant strategy (for any valuation class for which the worse
case can indeed be realized, as is the case for most classes of interest, see
Appendix D). By being truthful she guarantees to herself at least her share
guarantee, and no misreporting of her valuation function offers a higher
guarantee. However, for an agent that is either not risk averse (for example –
in a Bayesian setting in which there is some probability distribution over
valuations of other agents and over the choice of allocation algorithm to
use), or knows the details of the allocation algorithm, truthfulness need not
be a dominant strategy.

####  3.2.1 The MMS is Self Maximizing but any $\rho-$MMS is not

We next show that the MMS is self maximizing for any class of valuations, yet
even for additive valuations, for any positive $\rho<1$, the $\rho$-MMS is
not. Additionally, we observe that the proportional share is not self
maximizing for $n\geq 3$ even for additive valuations (while it is so for
$n=2$). For the proof see Section E.1.1.

###### Proposition 2

The MMS is a self-maximizing share for every class ${\mathcal{C}}$ of
valuations. In contrast, even just for additive valuation functions, the
$\rho$-MMS (for any $0<\rho<1$) is not self-maximizing for $n\geq 2$, and the
proportional share is not self-maximizing for $n\geq 3$ (while it is so for
$n=2$).

####  3.2.2 Properties of Self-Maximizing Shares

In this section we show that any self-maximizing share for class of valuations
${\mathcal{C}}$ satisfies several natural properties:

  * •

Scale Invariant: Assume that class of valuations ${\mathcal{C}}$ is closed
under multiplication by any positive constant ($v\in{\mathcal{C}}$ implies
$v^{\prime}=c\cdot v$ is in ${\mathcal{C}}$ for any $c>0$). A share function
$s$ is _scale invariant_ for ${\mathcal{C}}$ if for every $c>0$, scaling the
valuation function $v\in{\mathcal{C}}$ by a multiplicative factor of $c$, also
scales the share guarantee by the same multiplicative factor $c$:
$\hat{s}(c\cdot v,n)=c\cdot\hat{s}(v,n)$ for every $c>0,v\in{\mathcal{C}}$.

  * •

Monotone: A share function $s$ is _monotone_ for ${\mathcal{C}}$ if the share
guarantee is a monotone function of the valuation function: for every
$v,v^{\prime}\in{\mathcal{C}}$ such that $v\geq v^{\prime}$ (meaning that
$v(S)\geq v^{\prime}(S)$ for every $S\subseteq{\cal{M}}$) it holds that
$\hat{s}(v,n)\geq\hat{s}(v^{\prime},n)$.

  * •

$1$-Lipschitz: A share function $s$ is $1$-Lipschitz  for ${\mathcal{C}}$ if
the following holds for every $\delta>0$ and valuation function
$v\in{\mathcal{C}}$: if the value of every set changes by at most $\delta$
then the share guarantee increases by at most $\delta$. In other words, for
valuations $v,v^{\prime}\in{\mathcal{C}}$, if $|v^{\prime}(S)-v(S)|\leq\delta$
for every set $S\in{\cal{M}}$, then
$\hat{s}(v^{\prime},n)\leq\hat{s}(v,n)+\delta$.

###### Proposition 3

Any share that is self maximizing for ${\mathcal{C}}$, is monotone,
$1$-Lipschitz and scale invariant for ${\mathcal{C}}$.

We present the proof in Section E.1.2.

###  3.3 The Dominant Feasible Share

Recall that a share is feasible if for any agents’ valuation vector there
exists an acceptable allocation. Clearly the share function that is
identically zero is feasible, yet not very attractive as we want the feasible
share to be “as large as possible”. We next formalize what this means. One can
naturally define a partial order over share functions. A share (function) $s$
_dominates_ share (function) $s^{\prime}$ for a class of valuations functions
${\mathcal{C}}$, if for every $n$ (for which $s$ and $s^{\prime}$ are defined)
and every valuation $v\in{\mathcal{C}}$ it holds that $s(v,n)\geq
s^{\prime}(v,n)$. For a given class ${\mathcal{C}}$ of valuations, is there a
feasible share that is “the best” in the sense that it dominates all other
feasible shares for this class? We say that a feasible share $s$ is a
_dominant feasible share_ for a class of valuations functions ${\mathcal{C}}$,
if for the class ${\mathcal{C}}$ the share $s$ dominates any other feasible
share $s^{\prime}$. It is easy to see that any instance that demonstrates that
the MMS is not feasible can be used to show that a dominant feasible share
does not exist: Consider for example the instance $I$ presented in [25] for
three agents with valuations denoted by $(v_{1},v_{2},v_{3})$, for which it is
not possible to give every agent her MMS. We can define three feasible shares
$s_{i}$ for $i\in\\{1,2,3\\}$ in which $s_{i}(v_{i},3)$ equals to the MMS of
$v_{i}$, and for any $v\neq v_{i}$ we have $s_{i}(v,3)=0$. Each such share is
clearly feasible. For instance $I$, any share $s$ that dominates all these
three shares must give every agent her MMS, but that is known to be
impossible.

The proof above feels very unsatisfactory as the three shares that are defined
in the proof are clearly very artificial. Expecting a share to dominate even
those artificial feasible shares seems too much to ask for. We thus only ask
that $s$ dominate the subset of feasible shares that are also self maximizing.
As being self maximizing is a strong requirement, it seems much more plausible
that there might exist a feasible share that dominates only those feasible
shares that are self-maximizing. We say that a feasible share $s$ is a _SM-
dominant 121212SM stands for ”Self-Maximizing”.  feasible share_ for a class
of valuations functions ${\mathcal{C}}$, if for the class ${\mathcal{C}}$ it
dominates every other feasible and self-maximizing (SM) share $s^{\prime}$.

Our main negative result is that for additive valuations (and beyond), even if
we look for a feasible share that dominates only those feasible shares that
are _self maximizing_ , such a share does not exist. Note that even for SM-
domination, while the dominating share $s$ needs to be feasible, we do _not_
require it to be self maximizing (making our negative result stronger). Before
discussing the proof we discuss the relation between the MMS and the concept
of SM-dominant feasible shares.

We first observe that for valuation classes for which the MMS is feasible, the
MMS is the unique SM-dominant feasible share (see proof in Section E.2.1):

###### Proposition 4

Consider a setting with $n$ agents and a set of items ${\cal{M}}$. For any
class of valuations ${\mathcal{C}}$, the MMS dominates every feasible share
for ${\mathcal{C}}$. Moreover, if the MMS is feasible, then it is the unique
dominant feasible share for ${\mathcal{C}}$, and the unique SM-dominant
feasible share for ${\mathcal{C}}$.

Two immediate corollaries follow. First, for the class of unit-demand
valuations, for which the MMS is the value of the $n$-th most valuable item,
the MMS is feasible (and self maximizing), so it is the unique SM-dominant
feasible share for these valuations. Second, for two agents and additive
valuations the MMS is feasible (obtained by _cut-and-choose_) so it is the
unique SM-dominant feasible share for these valuations. Yet, beyond two agent
the MMS is known to be infeasible for additive valuations [25] so the
proposition cannot be used to find an SM-dominant feasible share. Yet, it does
not rule out that maybe there is a different SM-dominant feasible share for
additive valuations and more than two agents.

In the next section we consider additive valuations as well as more general
classes of valuations that contain additive valuations (e.g., submodular and
sub-additive) and show that in contrast to the case of unit-demand valuations,
SM-dominant feasible shares for those classes do not exist. This nonexistence
result holds even if we do not require the dominating share to be self
maximizing. We prove this claim by presenting an explicit family of feasible
shares that are self maximizing and have the following property: for any
additive valuation there is a share in the family for which the share for this
valuation equals to the MMS for this valuation. The result is then derived
from the fact that the MMS for additive valuations is not feasible.

We remark that our nonexistence result can also be derived as a corollary
(Corollary 4) from our result that shows that any feasible share is dominated
by a feasible share that is also self maximizing (Theorem 2). Yet, for the
class of additive valuations, while the shares defined in the first proof are
poly-time computable, our transformation from a feasible share to a self
maximizing feasible share that dominates it (Theorem 2) uses super-polynomial
computation.

##  4 No Dominant Feasible Share for Additive and Beyond

Our first main result shows that for any class of valuations that contains
additive valuations, there is no feasible share that dominates even only those
feasible shares that are self-maximizing. Thus, there is no SM-dominant
feasible share for any of these classes of valuations.

See 1

We note that this result shows that there is no SM-dominant feasible share,
even if we do not restrict that dominating share itself to be self maximizing.
We also highlight the fact that the non-existence of an SM-dominant feasible
share does not rely on computational feasibility – it holds even with
unbounded computational power.

The proof of the theorem uses shares that are based on picking orders (also
refered to as picking sequences) that we define below. Thus, before presenting
the proof of the theorem (Section 4.2), we present these shares (Section 4.1).

###  4.1 The $\omega$-Picking-Order Share

To prove Theorem 1 we need to show that for any class ${\mathcal{C}}$ of
valuation functions that contains all additive valuations, there is no
feasible share that dominates every feasible self-maximizing share. To do so,
for every such class ${\mathcal{C}}$, we design a collection ${\mathcal{Q}}$
of shares, where every share in ${\mathcal{Q}}$ is feasible and self
maximizing. The feasibility and self maximization properties need to hold for
all valuations in ${\mathcal{C}}$, not just for additive valuations. To prove
that there is no SM-dominant feasible share we show that no feasible share $s$
dominates every share in ${\mathcal{Q}}$: for every share $s$ that is feasible
for ${\mathcal{C}}$ (even if $s$ is not self maximizing), there is some share
$s^{\prime}$ in ${\mathcal{Q}}$ that for some valuation function
$v\in{\mathcal{C}}$ offers higher value than $s$ does.

The class ${\mathcal{Q}}$ that we consider is based on picking orders, that
is, sets that are created by the $n$ agents picking items according to some
predefined order in which they pick. Such shares, mostly based on the round
robin picking sequence, have been introduced also in previous work (see [12,
18]), though our treatment is concerned with arbitrary picking sequences. Such
shares will be defined even for non-additive valuations, and will be feasible
and self maximizing (although not necessarily poly-time computable when the
valuations are not additive).

For a setting with $n$ agents and a set ${\cal{M}}$ or size $m$, a _picking
order $\omega$_ is a list $\omega_{1},\omega_{2},\ldots,\omega_{m}$, with
$\omega_{j}\in[n]$ for each $j\in[m]$. The value $\omega_{j}$ determines which
agent picks an item at the $j$-th step in the picking sequence.

Fix a valuation $v$ and a picking order $\omega$. Let $x_{k}$ be the maximum
value that agent $k\in[n]$ with valuation $v$ can ensure she gets when the
picking order is $\omega$. That is, the maximum value when facing an adversary
that makes all picks when $\omega_{j}\neq k$ in order to minimize the value
that agent $k$ gets. Note that computing the strategy of the agent and of such
an adversary is easy for additive valuations (by greedily picking items from
high to low value according to the agent’s valuation), but not necessarily so
for more general classes of valuations.

Fix a picking order $\omega$. The _$\omega$ -Picking-Order share_ of an agent
with valuation $v$ is $\min_{k\in[n]}x_{k}$. That is, the minimum over all
possible identities of the agent, of the maximum she can ensures herself with
that identity when the picking order is $\omega$. Note that as these shares
are defined to be a value of some bundle, for each picking order $\omega$ the
share guarantee is the same as the share itself.

To illustrate this share, let us consider the case that the valuation is
additive. In this case, both the agent and the adversary will simply pick
items in order of decreasing value according to the agent’s valuation
(breaking ties arbitrarily). Note that tie breaking (by the agent or the
adversary) in picking has no effect on the final value the agent gets. In this
case, the share will simply be the minimal value that any of the $n$ agents
get, when every agent has valuation $v$ (all valuations are the same), and
simply pick items in non-increasing order of values. Consequently, when agents
are additive, the picking order share is a special case of a more general
family of shares that we define in Section 6.1, which we call _ordinal maximin
shares_ (see Definition 5). We show that all shares in this general family are
self maximizing (Proposition 7), and hence picking order shares are self
maximizing when valuations are additive. Moreover, we show that picking-order
shares are self maximizing for all valuations (even non-additive).

We summarize our results for picking shares in the next proposition (see proof
in Section F.1.1).

###### Proposition 5

Fix any class ${\mathcal{C}}$ of valuations. For any picking order $\omega$,
the $\omega$-Picking-Order share is feasible and self maximizing for
${\mathcal{C}}$. Moreover, if valuations are additive then an acceptable
allocation can be computed in polynomial time. Finally, for any additive
valuation $v$ there exists a picking order $\omega_{v}$ for which the
$\omega_{v}$-Picking-Order share for an agent with valuation $v$ equals to the
MMS of that agent, that is, to $MMS_{n}(v)$.

###  4.2 Proof of Theorem 1

In this section we restate and prove Theorem 1, our main negative result.

See 1

Proof. Fix any share $s$. By Proposition 5, for every picking order $\omega$
and any valuation (including all valuations in the class ${\mathcal{C}}$), the
$\omega$-Picking-Order share is self maximizing and feasible. Thus, if $s$
dominates every self-maximizing and feasible share it must dominate every
$\omega$-Picking-Order share.

As ${\mathcal{C}}$ includes all additive valuations, $s$ must, in particular,
dominate every self-maximizing and feasible share for additive valuations. As
for additive valuations, by Proposition 5, for some picking order $\omega$ the
$\omega$-Picking-Order share is the same as the MMS, we conclude that for
additive valuations, for $f$ to dominate every self-maximizing and feasible
share, it must dominate the MMS.

Yet, for agents with additive valuations, there are instances for which no
allocation gives each agent her MMS [25]. We thus conclude that for class
${\mathcal{C}}$, the share $s$ does not dominate every self-maximizing and
feasible share. $\blacksquare$

Our nonexistence result shows in particular that an SM-dominant feasible share
for additive valuations does not exist. Given this negative result, in Section
6 we consider approximate domination, and present several positive results for
additive valuations. Before focusing on additive valuations we present a
general transformation from any feasible share to a dominating share that is
feasible and self maximizing. This result also implies an alternative proof of
our nonexistence result.

##  5 Domination Relations among Shares

###  5.1 Domination by a Self-Maximizing Share

In this section we show that any feasible share can be transformed to a
feasible share that dominates it, and is self-maximizing. Thus, in a sense, we
can always assume that a feasible share is self-maximizing. Yet, this
transformation is not done in polynomial time, thus, when computation is
important, this proof does not show that self maximization comes for free.

See 2

The main idea in the proof of Theorem 2 is to construct $s^{\prime}$ as
follows. For every valuation $v$, the value of $s^{\prime}(v)$ is equal to the
implied guarantee of $s$ with respect to the report $v^{\prime}$ that
maximizes this implied guarantee. The details of how this idea is turned into
a proof are presented in Section G.1.

From Theorem 2 we derive the following immediate corollary.

###### Corollary 4

Let ${\mathcal{C}}$ be an arbitrary class of valuation functions, and let $s$
be an arbitrary feasible share for class ${\mathcal{C}}$. The share $s$ is a
dominant feasible share for ${\mathcal{C}}$ if and only if $s$ is a SM-
dominant feasible share for ${\mathcal{C}}$.

The corollary combined with the simple observation that there is no dominant
feasible share for additive valuations (implied by the fact the the MMS is not
feasible, see Section 3.3), gives an alternative proof to Theorem 1 for any
class that contains the additive valuations.

We have shown that any feasible share can be transformed to a feasible share
that dominates it, and is self-maximizing. Yet, this transformation is not
done in polynomial time (not even for the class of additive valuations). This
suggests the following open problem: find such a transformation that can be
computed in polynomial time when valuations are additive and the original
share is polynomial time computable, or prove that the problem is
computationally hard.

###  5.2 $\rho$-Domination

An immediate corollary of Proposition 4 is that for any class of valuations
${\mathcal{C}}$, a share $s$ that $\rho$-dominates the MMS also
$\rho$-dominates every feasible share. This is stated in the next proposition,
together with two stronger versions of the converse claim.

###### Proposition 6

For any class of valuations ${\mathcal{C}}$, a share $s$ that $\rho$-dominates
the MMS also $\rho$-dominates every feasible share.

For any class of valuations ${\mathcal{C}}$, a share $s$ that $\rho$-dominates
every feasible share that is self maximizing also $\rho$-dominates the MMS.

Furthermore, for the class of additive valuations, a share $s$ that
$\rho$-dominates every feasible share that is self maximizing and poly-time
computable, also $\rho$-dominates the MMS.

Proof. By Proposition 4, for any class of valuations ${\mathcal{C}}$ the MMS
dominates every feasible share for ${\mathcal{C}}$. An immediate corollary is
that a share $s$ that $\rho$-dominates the MMS also $\rho$-dominates every
feasible share for ${\mathcal{C}}$.

Next, we prove that for any class of valuations ${\mathcal{C}}$, a share $s$
that $\rho$-dominates every feasible share that is self maximizing also
$\rho$-dominates the MMS. Indeed, for any valuation $v\in{\mathcal{C}}$, let
$s_{v}$ the share that is defined as follows: it equals the MMS on $v$, and is
zero otherwise. This share is clearly feasible for ${\mathcal{C}}$, by the MMS
definition. By Theorem 2, the share $s_{v}$ is dominated by some share
$s^{\prime}_{v}$ that is feasible and self maximizing. The share
$s^{\prime}_{v}$ must also be equal to the MMS on $v$, as it is at least as
large as $s_{v}$ on $v$, and is no larger since it is feasible. Thus, in order
for $s$ to $\rho$-dominate all self-maximizing feasible shares, it must
dominate $s^{\prime}_{v}$ for every $v\in{\mathcal{C}}$, and thus it must
$\rho$-dominate the MMS for ${\mathcal{C}}$.

Finally, we show that for the class of additive valuations, a share $s$ that
$\rho$-dominates every feasible share that is self maximizing and poly-time
computable, also $\rho$-dominates the MMS. By Proposition 5, for any additive
valuation $v$ there exists a picking order $\omega_{v}$ for which the
$\omega_{v}$-Picking-Order share for an agent with valuation $v$ equals to the
MMS of $v$. Additionally, by Proposition 5, for any additive valuation $v$ the
$\omega_{v}$-Picking-Order share is feasible, self maximizing and can be
computed in polynomial time. Thus, in order for share $s$ to $\rho$-dominate
every feasible share that is self-maximizing and poly-time computable, it must
$\rho$-dominate the $\omega_{v}$-Picking-Order share for every additive
valuation $v$, and thus it must $\rho$-dominates the MMS. $\blacksquare$

Denote by $\alpha$-MMS the share that is defined to be an $\alpha$-fraction of
the MMS (that is $\alpha\cdot MMS$ for positive $\alpha\leq 1$). By
definition, for every valuation the $\alpha$-MMS $\alpha$-dominates the MMS.
Thus, for any class of valuations ${\mathcal{C}}$, by Proposition 6, the
$\alpha$-MMS $\alpha$-dominates every feasible share for ${\mathcal{C}}$.

Fix the number of agents $n\geq 2$. For a class ${\mathcal{C}}$ of valuations,
let $\alpha_{n}^{*}({\mathcal{C}})$ be the supremum131313 For the class of
additive valuations the maximum is actually obtained, although there are
infinitely many possibilities for the number of items, and infinitely many
possible valuation functions. See [15] for details.  over all values of
$\alpha$ for which the $\alpha$-MMS is feasible for class ${\mathcal{C}}$ for
$n$ agents (for any number of items $m$). For $n$ agents, the
$\alpha_{n}^{*}({\mathcal{C}})$-MMS share
$\alpha_{n}^{*}({\mathcal{C}})$-dominates every feasible share for
${\mathcal{C}}$ (by Proposition 6). Yet, by Proposition 2, this share is not
self maximizing, not even for the class of additive valuations. One can use
Theorem 2 to turn the $\alpha_{n}^{*}({\mathcal{C}})$-MMS to a feasible self-
maximizing share that dominates it, thus
$\alpha_{n}^{*}({\mathcal{C}})$-dominating every feasible self-maximizing
share for ${\mathcal{C}}$. Yet, the transformation of Theorem 2 is not
polynomial time, not even for the class of additive valuations. Thus, in the
next section we focus on the class of additive valuations over goods and we
seek a self-maximizing feasible share that is poly-time computable and
$\rho$-dominates the MMS, for $\rho$ that is as large as possible.

##  6 Results for Additive Valuations over Goods

In this section we focus on the class of additive valuations over goods (which
we will simply call _additive valuations_ below, for short). Given the
discussion at the end of the prior section (Section 5.2), we seek self-
maximizing feasible shares that are poly-time computable and $\rho$-dominate
the MMS, for $\rho$ that is as large as possible.

We first present a family of shares, referred to as _ordinal maximin shares_ ,
and show that all members of this family are self-maximizing (see Section
6.1). We then present several ordinal maximin shares, all of them are
feasible, self-maximizing and polynomial-time computable. For general $n$, we
present such a share that is $\frac{2n}{3n-1}$-dominating. Furthermore, for up
to four agents we show that this share is $\frac{4}{5}$-dominating. For two
agents and any positive $\epsilon$ we present such a share that is
$(1-\epsilon)$-dominating (a PTAS). (As the MMS is NP-hard to compute even for
$n=2$, we cannot hope the get the MMS exactly by a poly-time share.) Moreover,
for each of those shares we present a polynomial time algorithm that computes
allocations that give every agent at least her share. The PTAS for two agents
appears in Section 6.2. The other shares are presented in Section 6.3.

###  6.1 Ordinal Maximin Shares

For additive valuation functions, we define the class of ordinal maximin
shares, and we show that every share in this class is self maximizing. We
slightly abuse the notion of share and instead of thinking about one share
that is defined for every $n$, we think of shares that are each defined for a
specific value of $n$ (e.g., this enables us to define a PTAS-based share only
for the case that $n=2$). We first define the notion of a family of
partitions.

###### Definition 4

Fix $n\geq 2$. For any integer $m$, an $(m,n)$-partition $P$ of the set $[m]$
into $n$ parts is a collection of $n$ disjoint bundles that together contain
the set: $P=(B_{1},\ldots,B_{n})$ satisfying $\cup_{j}B_{j}=[m]$, $B_{k}\cap
B_{j}=\emptyset$ for every pair $k\neq j$. (Some of the bundles might be
empty.) For given $n$ and $m$, a family ${\cal{F}}_{m,n}$ of partitions is
collection of $(m,n)$-partitions. For $n\geq 2$, a _family ${\cal{F}}_{n}$ of
partitions_ is a collection of families ${\cal{F}}_{m,n}$ of partitions, one
such family for every $m$.

###### Definition 5

Fix the number of agents $n\geq 2$. A share for $n$ agents with additive
valuation functions is ordinal maximin if for every value of $m$ (number of
items) it has an associated family of partitions ${\cal{F}}_{m,n}$, and for
every additive valuation function $v$ over $m$ items, the corresponding share
value can be computed as follows.

  1. 1.

Sort items from highest value to lowest value according to $v$ (breaking ties
arbitrarily – the share value is not affected by how ties are broken). Without
loss of generality, we denote the $j$-th highest value item according to this
order by $e_{j}$ (thus, $v(e_{j})\geq v(e_{k})$ for $j<k$).

  2. 2.

Relative to this order, for a set $S\subseteq[m]$, let $v(S)=\sum_{j\in
S}v(e_{j})$. For every partition $P=(B_{1},\ldots,B_{n})\in{\cal{F}}_{m,n}$,
let $v(P)=\min_{j}[v(B_{j})]$.

  3. 3.

The value of the share for $v$ is $\max_{P\in{\cal{F}}_{m,n}}[v(P)]$. A
partition $P$ is _optimal_ if $v(P)$ equals to the value of the share ($P$
belongs to the argmax).

Hence, an ordinal maximin share for $n$ agents is completely characterized by
its associated family ${\cal{F}}_{n}$ of collections of partitions
${\cal{F}}_{m,n}$ (one for every $m$). For any such family ${\cal{F}}_{n}$, we
denote the associated ordinal maximin share over the additive valuations by
_${\cal{F}}_{n}$ -maximin share_.

The MMS is an example of a share that is ordinal maximin for every $n$ (with
${\cal{F}}_{m,n}$ being the family of all $(m,n)$-partitions). The following
round robin share, based on the round robin allocation procedure, is also
ordinal maximin. For every $(m,n)$, the family ${\cal{F}}_{m,n}$ contains a
single partition $P=\\{B_{1},\ldots,B_{n}\\}$, where for every $j$, bundle
$B_{j}$ contain the items $e_{j+kn}$ (for non-negative integers $k$, where
items are sorted from highest to lowest value). The value of the round robin
share is equal to the value of $B_{n}$. More generally, every picking order
induces an ordinal maximin share, in which ${\cal{F}}_{m,n}$ contains only a
single partition. Given valuation function $v$, bundle $B_{i}$ in this
partition contains those items whose index is those rounds in which agent $i$
gets to pick in the picking order.

We observe that for two agents, for any family ${\cal{F}}_{2}$ the
${\cal{F}}_{2}$-maximin share is feasible (see 17 in Section H.1). For more
than two agents, the ${\cal{F}}_{n}$-maximin share might not be feasible (as
in the case for the MMS with $n=3$), but specific families of partitions yield
feasible shares (as we prove in Section 6.3).

The main attractive property of ordinal maximin shares is that they are all
self maximizing (see proof in Section H.1.1).

###### Proposition 7

For any family ${\cal{F}}_{n}$ of partitions, its associated ordinal maximin
share ${\cal{F}}_{n}$-maximin is self maximizing.

###  6.2 A Self-maximizing PTAS for Two Agents

For two agents with additive valuations, the MMS is a self-maximizing share
that is feasible. However, computing the MMS is NP-hard even for two agents,
and thus we cannot hope the get the MMS exactly by a poly-time share (assuming
$P\neq NP$). In this section, for the case of two agents with additive
valuations and for every $\epsilon>0$, we present a share that we shall refer
to as the $PTAS(\epsilon)$ share. For every additive valuation function, the
value of the $PTAS(\epsilon)$ share is at least $(1-\epsilon)$ times the value
of the MMS. Like the MMS, the $PTAS(\epsilon)$ share is self maximizing and
feasible. However, unlike the MMS, for every $\epsilon>0$, the
$PTAS(\epsilon)$ share can be computed in polynomial time. Moreover, given the
valuation functions of the two agents, an allocation giving each agent at
least her $PTAS(\epsilon)$ share can be computed in polynomial time.

The $PTAS(\epsilon)$ share is based on the following principle. Recall that
for $n=2$, the value of the MMS is a solution to the following partition
problem. The input to the problem is a set
${\cal{M}}=\\{e_{1},\ldots,e_{m}\\}$ of items and their values
$\\{x_{1}=v(e_{1}),\ldots,x_{m}=v(e_{m})\\}$. The desired output is a
partition of ${\cal{M}}$ into two disjoint bundles, $B_{1}$ and $B_{2}$, such
that $\min[v(B_{1}),v(B_{2})]$ is maximized, or equivalently,
$\min_{i\in\\{1,2\\}}\sum_{j\;|\;e_{j}\in B_{i}}x_{j}$, is maximized. As the
partition problem is (weakly) NP-hard, so is the problem of computing the MMS.

To overcome the NP-hardness issue, we use a polynomial time approximation
algorithm, referred to here as $PTAS_{ALG}$, for the partition problem. On
every input instance, $PTAS_{ALG}$ returns a partition in which the value of
the less valuable part of the partition is within a factor of $(1-\epsilon)$
the value of the less valuable part in the optimal (most balanced) partition.
We associate a share with $PTAS_{ALG}$, where for every additive valuation
function, the value of the share is the value returned by $PTAS_{ALG}$. The
$PTAS_{ALG}$ share is feasible, because on every allocation instance (for two
agents), we can use the cut and choose procedure: consider the partition that
$PTAS_{ALG}$ induces for agent 1, let agent 2 choose which part she takes, and
agent 1 gets the remaining part. The $PTAS_{ALG}$ share is also polynomial
time computable and approximates the MMS within a ratio of $(1-\epsilon)$, by
its definition. Hence it remains to address the issue of being self
maximizing.

The partition problem has very efficient approximation algorithms: it has a
fully polynomial time approximation scheme (FPTAS), that has polynomial
dependence on $\frac{1}{\epsilon}$. However, known approximation algorithms
for the partition problem to not appear to induce a share that is self
maximizing. Instead, we design a new polynomial time approximation scheme
(PTAS), with exponential dependence of $\frac{1}{\epsilon}$, which produces a
share that is an ordinal maximin share, and hence self maximizing (by
Proposition 7).

With the above introduction in mind, we present the $PTAS(\epsilon)$ share in
the proof of the following theorem.

###### Theorem 5

Consider a setting with two agents that have additive valuations over a set of
items ${\cal{M}}$. For any fixed $\epsilon>0$, the $PTAS(\epsilon)$ share
(described in the proof of the theorem) is self-maximizing, computable in
polynomial time, and is at least a $1-\epsilon$ fraction of the MMS.
Additionally, the share is feasible, and an acceptable allocation can be found
in polynomial time.

Proof. We may assume that $m\geq\frac{3}{\epsilon}$, as for
$m<\frac{3}{\epsilon}$ we can set $PTAS(\epsilon)$ to be equal to the MMS.
(The MMS can be computed in time exponential in $2^{O(1/\epsilon)}$ in this
case, which is constant time when $\epsilon>0$ is constant.)

We may also assume that $MMS_{n}(v_{i})\geq\frac{v_{i}({\cal{M}})}{3}$. The
only way that this assumption can be violated is if there is an item $e_{1}$
of value $v_{i}(e_{1})>\frac{2v_{i}({\cal{M}})}{3}$, but then again we can
take $PTAS(\epsilon)$ to be equal to the MMS (whose value in this case is
$v_{i}({\cal{M}})-v_{i}(e_{1})$).

Given a desired approximation ratio of $1-\epsilon$, let
$k=\left\lceil\frac{3}{2\epsilon}\right\rceil$. Note that $k\leq m$ as
$m\geq\frac{3}{\epsilon}\geq\left\lceil\frac{3}{2\epsilon}\right\rceil=k$.
Partition ${\cal{M}}$ into the set $Z$ of the $k$ most valuable items
(breaking ties arbitrarily), and the set $S$ of remaining items. Order the
items of $S$ in order of decreasing value (breaking ties arbitrarily), and let
$e_{m}$ denote the last item in this order. Consider the following family
${\cal{F}}_{m,2}$ of at most $2^{k}m$ partitions of ${\cal{M}}$. A partition
of ${\cal{M}}$ into two bundles $(B_{1},B_{2})$ is a member of
${\cal{F}}_{m,2}$ if and only if $B_{1}\cap S$ is a suffix of $S$. That is,
bundle $B_{1}$ contains an arbitrary subset of $Z$, but the set of items that
$B_{1}$ contains from $S$ must be a (possibly empty) set of consecutive items,
ending in $e_{m}$. The value of the PTAS share for agent $i$ is
$PTAS(\epsilon)_{i}=\max_{(B_{1},B_{2})\in{{\cal{F}}_{m,2}}}\min[v_{i}(B_{1}),v_{i}(B_{2})]$.
That is, the definition of $PTAS(\epsilon)_{i}$ is similar to
$MMS_{n}(v_{i})$, except that instead of maximizing (the minimum value of a
bundle) over all possible partitions, one maximizes only over the partitions
in ${{\cal{F}}_{m,2}}$. For every item $e$ in $S$ we have that
$v_{i}(e)\leq\frac{v_{i}(Z)+v_{i}(e)}{k+1}\leq\frac{v_{i}({\cal{M}})}{k+1}$.
We claim that this implies that $PTAS(\epsilon)_{i}\geq
MMS_{n}(v_{i})-\frac{v_{i}({\cal{M}})}{2(k+1)}$. Recalling the assumption that
$MMS_{n}(v_{i})\geq\frac{v_{i}({\cal{M}})}{3}$ and the choice of
$k=\left\lceil\frac{3}{2\epsilon}\right\rceil$, the claim implies that
$(1-\epsilon)\cdot MMS_{n}(v_{i})\leq PTAS(\epsilon)_{i}\leq MMS_{n}(v_{i})$.

We now prove the claim that $PTAS(\epsilon)_{i}\geq
MMS_{n}(v_{i})-\frac{v_{i}({\cal{M}})}{2(k+1)}$. Let $(B^{*}_{1},B^{*}_{2})$
denote the optimal partition. Construct a partition
$(B_{1},B_{2})\in{{\cal{F}}_{m,2}}$ as follows. For items in $Z$, we choose
$B_{i}\cap Z=B^{*}_{i}\cap Z$ (for $i\in\\{1,2\\}$). If either $B^{*}_{1}$ or
$B^{*}_{2}$ contain no items from $S$, then the partition
$(B^{*}_{1},B^{*}_{2})$ itself is one of the partitions in
${{\cal{F}}_{m,2}}$. Hence we may assume that both $B^{*}_{1}$ and $B^{*}_{2}$
contain items from $S$. Consequently, $\max[v_{i}(B^{*}_{1}\cap
Z),v_{i}(B^{*}_{2}\cap Z)]\leq\frac{v_{i}({\cal{M}})}{2}$. By choosing for
$B_{1}$ either the longest suffix of $S$ for which
$v_{i}(B_{1})\leq\frac{v_{i}({\cal{M}})}{2}$ or one additional item from $S$,
we get that
$\min[v_{i}(B_{1}),v_{i}(B_{2})]\geq\frac{v_{i}({\cal{M}})}{2}-\frac{1}{2}\max_{i\in
S}[v_{i}(e)]\geq MMS_{n}(v_{i})-\frac{v_{i}({\cal{M}})}{2(k+1)}$, as claimed.

$PTAS(\epsilon)_{i}$ can be computed by the following algorithm that uses only
addition operations and comparison operations. Sort all items in non-
increasing order of values. This can be done using $O(m\log m)$ comparison
operations. The set $Z$ is composed of the first $k$ items, and $S$ is
composed of the remaining items. For every suffix of $S$, compute the sum of
item values in the suffix. This can be done using $O(m)$ addition operations
(starting from the last suffix, and extending the suffix one item at a time).
Thereafter, there are $2^{k}$ possible partitions of $Z$. For each such
partition $(Z_{1},Z_{2})$, the sum of item values in $Z_{1}$ can be computed
using $O(k)$ addition operations. The optimal choice of suffix of $S$ to add
to $Z_{1}$ can be found using $O(\log m)$ operations, by binary search over
the suffixes. Hence $PTAS(\epsilon)_{i}$ can be computed using $O(m\log
m+2^{k}(k+\log m))$ operations. As $k=O(\frac{1}{\epsilon})$, and the time to
perform a single operation is at most linear in the input size (note that the
number of input bits required in order to represent the value of an item might
be much larger than $m$, and be the dominating factor in the input size), this
running time is polynomial in the input size, for every fixed $\epsilon>0$
(and also when $\frac{1}{\epsilon}$ is logarithmic in the input size).

As $PTAS(\epsilon)$ is an ordinal maximin share, it is feasible for two agents
by Observation 17, and self maximizing by Proposition 7. $\blacksquare$

The approximation algorithm used in the proof of Theorem 5 in order to compute
the $PTAS(\epsilon)$ share can be extended to any number $n$ of agents. This
requires, among other changes, to increase $k$ to
$n\lceil\frac{1}{\epsilon}\rceil$ in order for the approximation to still
hold. As the running time is exponential in $k$, it becomes exponential in
$n$, but is still polynomial in $m$ for every fixed $n$. However, for $n\geq
3$ and $\epsilon\leq\frac{1}{4}$, the resulting share is not feasible (unlike
the case for $n=2$), as it is the same as the MMS for instances in which it is
impossible to give every agent her MMS. Indeed, recall that for every $n\geq
3$, there are allocation instances with additive valuations and $m\leq 4n$
items in which no allocation gives every agent her MMS [25]. In such instances
and when $\epsilon\leq\frac{1}{4}$, the value of $k$ is at least $4n$, and as
$4n\geq m$ the family ${{\cal{F}}_{m,n}}$ contains all possible partitions of
$m$ items to $n$ agents. Consequently, in these instances, for every agent,
$PTAS(\epsilon)_{i}=MMS_{n}(v_{i})$. Hence no allocation gives every agent her
$PTAS(\epsilon)$ share.

###  6.3 The Class of Nested Shares

We introduce a class of ordinal maximin shares for additive valuations that we
refer to as $NS$, standing for _Nested Shares_. For $n$ agents, a share in
this class is parameterized by a parameter $q\in[n]$. It will be convenient to
have both $n$ and $q$ explicit in the notation of the share, so we use
$NS_{n,q}$ to denote this share for parameters $n$ and $q$.

For $n$ agents, given parameter $q$, we next define the _Nested Share_
$NS_{n,q}$. Sort the items in decreasing value (breaking ties arbitrarily),
and denote the $j$-th highest value item by $e_{j}$. Like the MMS, if the
number of items $m$ satisfies $m<n$ then $NS_{n,q}(v)=0$, and if $m=n$, then
$NS_{n,q}(v)=v(e_{n})$. Hence we present the definition for $m>n$. A
_consecutive partition_ of a set of items $Z$ is defined by $n$ indexes
$i_{1}\leq i_{2}\leq\ldots\leq i_{n}$ (we also denote $i_{0}=0$). These
indexes define a partition of the items to $n$ bundles of consecutive items:
for $j\in[n]$ bundle $Z_{j}$ contains items
$\\{e_{i_{j-1}+1},\ldots,e_{i_{j}}\\}$ ($Z_{j}$ is empty if $i_{j}=i_{j-1}$).

The family of partitions that define the share $NS_{n,q}$ is defined as
follows. Fix an integer variable $k$, whose value satisfies $n-q<k\leq m$. For
$k$, consider the following family ${{\cal{F}}_{m,n,q,k}}$ of (at most
$m^{n+q-2}$) partitions $(B_{1},\ldots,B_{n})$ of ${\cal{M}}$ that are defined
as follows. Let $Z$ be the set of items $\\{e_{1},\ldots,e_{k}\\}$. Fix any
consecutive partition $(Z_{1},\ldots,Z_{n})$ of $Z$ to $n$ sets, such that
$i_{j}=j$ for every $j\leq n-q$ (that is, the $n-q$ first sets are
singletons). Then, fix any consecutive partition
$(S^{\prime}_{1},\ldots,S^{\prime}_{n})$ of suffix
$S^{\prime}=S={\cal{M}}\setminus Z$ to $n$ sets (possible empty), and for
convenience denote $S_{j}=S^{\prime}_{n-j+1}$ for $j\in[n]$. A partition of
${\cal{M}}$ into $n$ bundles $(B_{1},\ldots,B_{n})$ is a member of
${{\cal{F}}_{m,n,q,k}}$ if and only if for some pair of partitions as defined
above, $B_{j}=Z_{j}\cup S_{j}$ for every $j\in[n]$.

The value of the $NS_{n,q}$ share for valuation $v$ over $m$ items is defined
to be
$NS_{n,q}(v)=\max_{k}\max_{(B_{1},\ldots,B_{n})\in{{\cal{F}}_{m,n,q,k}}}\min_{j}[v_{i}(B_{j})]$.
The definition of the $NS_{n,q}$ share is similar to that of the MMS, except
that instead of maximizing (the minimum value of a bundle) over all possible
partitions, one maximizes only over the partitions in
${\cal{F}}_{n,q}={\bigcup_{n-q<k\leq m}{\cal{F}}_{m,n,q,k}}$.141414Note that
${\cal{F}}_{n,q}$ depends also on $m$. Yet, the only way in which we use
${\cal{F}}_{n,q}$ is in the definition of the share $NS_{n,q}$, which accepts
a valuation as an argument. As $m$ could always be deduced from the valuation,
to simplify notation we omit explicitly including $m$ in the notation.  We
remark that $NS_{n,q}$ shares are called the _Nested Shares_ as for every
$j\in[n-1]$ all items in $B_{j+1}$ are nested inside the items of $B_{j}$
(within the sorted order).

Observe that for every $n$ and every $q>q^{\prime}$ (and every $m$) it holds
that ${\cal{F}}_{n,q^{\prime}}\subseteq{\cal{F}}_{n,q}$, and consequently
$NS_{n,q}(v)\geq NS_{n,q^{\prime}}(v)$ for every valuation $v$. In particular,
$NS_{n,n}$ dominates $NS_{n,q}$ for every $q\in[n]$.

###### Example 1

To illustrate the $NS_{n,q}$ share consider the following example with four
agents ($n=4$). The valuation is additive and item values are (3, 3, 2, 2, 2,
2, 2, 2, 1, 1). Here, the MMS is 5 (the MMS partition contains two bundles of
the form $(3,2)$ and two bundles of the form $(2,2,1)$). However, for every
integer $q$ such that $1\leq q\leq 4$, the value of the nested share
$NS_{4,q}$ is 4. To lower bound $NS_{4,q}$, it suffices to consider $q=1$. The
$NS_{4,1}$ partition is required to place the first four items in separate
bins, and may reach a value of 4 by placing at least one additional item in
each bin (e.g., creating bins $(3,1)$, $(3,1)$, $(2,2,2)$, $(2,2,2)$). To
upper bound $NS_{4,q}$, it suffices to consider $q=4$. The $NS_{4,4}$
partition allows for $Z_{j}$ to be of any size, but still it must create at
least one bin of value at most 4. (There are four items of odd value. For all
bins to have value 5, the odd valued items must be in different bins. However,
in every $NS_{4,4}$ partition, either there is a bin with only a single item,
or two odd valued items are in the same bin.)

Though some of our results apply to $NS_{n,q}$ shares for arbitrary values of
$n\geq 2$ and $1\leq q\leq n$, our most interesting current results apply to
the case of $q=3$.

###### Theorem 6

Consider a setting with $n$ agents that have additive valuations over a set
${\cal{M}}$ of goods. Then the $NS_{n,3}$ share is self-maximizing, poly-time
computable, and is at least a $\frac{2n}{3n-1}$ fraction of the MMS, and at
least a $\frac{4}{5}$ fraction of the MMS when $n\leq 4$. Additionally, the
share is feasible, and an acceptable allocation can be found in polynomial
time.

We outline the main ideas of the proof of Theorem 6, and refer the reader to
Section H.2 for further details. The fact that $NS_{n,3}$ is self maximizing
is an immediate consequence of the fact that it is an ordinal maximin share
(Proposition 7). Polynomial time computability of the $NS_{n,q}$ share value
(for every $1\leq q\leq n$) and an associated optimal partition is
demonstrated by an algorithm based on dynamic programming. See Lemma 18. The
$\frac{2n}{3n-1}$ approximation holds already for $q=1$, and the proof of this
fact can be derived from results in [21], showing that a related allocation
algorithm provides allocations that give every agent a $\frac{2n}{3n-1}$
fraction of her MMS. In our case, we only need to prove this approximation
ratio when all agents have the same valuation function, making the proof
simpler. See Lemma 19. We also complement this result by showing that even for
$q=3$, as $n$ grows, the approximation ratio of $NS_{n,3}$ converges (from
above) to $\frac{2}{3}$. See Proposition 26. The $\frac{4}{5}$ approximation
for $n=4$ uses in an essential way the choice of $q=3$, and does not hold for
$q\leq 2$. (Likewise, the $\frac{4}{5}$ approximation for $n=3$ requires
$q\geq 2$, and does not hold for $q=1$.) The $\frac{4}{5}$ approximation
crucially depends on considering partitions in which the first $n$ items are
not all placed in separate bins. See Lemma 23 (for $n=3$) and Lemma 24 (for
$n=4$). We remark that the proof of Lemma 24 is computer assisted, see
Appendix H.2.1.

####  6.3.1 Proof that $NS_{n,3}$ is a feasible share

Here we prove part of Theorem 6, showing that the $NS_{n,q}$ share is feasible
for $q=3$ (thus also for $q=2$ and $q=1$). Moreover, we show that an
acceptable allocation can be computed in polynomial time. We do not know
whether the $NS_{n,q}$ share is feasible for larger values of $q$.

For our feasibility proof, we shall make use of the notion of _ordered
allocation instances_.

###### Definition 6

We say that an allocation instance is ordered if for every $j$ and $k$ such
that $1\leq j<k\leq m$ and every agent $i$, it holds that $v_{i}(e_{j})\geq
v_{i}(e_{k})$.

The following lemma is an immediate corollary of a result of [9].

###### Lemma 8

Consider the class of additive valuations, any share for this class (e.g.,
MMS, $NS_{n,q}$) and any value of $\rho$ (including $\rho=1$). Then any
(polynomial time) allocation algorithm that gives every agent at least a
$\rho$ fraction of her share for ordered instances, can be transformed into a
(polynomial time) algorithm that produces such an allocation for arbitrary
instances.

The proof of Lemma 8 is based on defining a picking order for the arbitrary
instance, based on the allocation for an ordered version of the instance. See
[9] for further details.

###### Lemma 9

For the class of additive valuations and every $q\geq 1$, if $NS_{q,q}$ is
feasible, then so is $NS_{n,q}$ for every $n>q$. Moreover, if an acceptable
allocation for $NS_{q,q}$ can be found in polynomial time, so can an
acceptable allocation for $NS_{n,q}$.

Proof. Consider an instance with $n>q$ agents, and the associated $NS_{n,q}$
partitions for the $n$ agents. We assume that the instance is ordered. This
assumption can be made without loss of generality, by Lemma 8.

Create $n$ bins. Place items $e_{1},\ldots,e_{n-q}$ in bins
$B_{1},\ldots,B_{n-q}$, respectively. Now insert the minimum number of items
in reverse order (starting at $e_{m}$, the minimum may be 0) into $B_{1}$
until there is an agent that desires $B_{1}$, where we say that an agent
_desires a bin_ if the agent’s total value for the items in the bin is at
least as large as her $NS_{n,q}$ share value. Give $B_{1}$ to the respective
agent (breaking ties arbitrarily if there is more than one such agent), and
remove the agent and the bin. Observe that for each of the remaining agents,
the $NS_{n-1,q}$ share with respect to the remaining items is at least as
large as her original $NS_{n,q}$ share with respect to all items. (The bins
$B_{2},\ldots,B_{n}$ in the partition in ${\cal{F}}_{n,q}$ that gave rise to
$NS_{n,q}$ can serve as a partition in ${\cal{F}}_{n-1,q}$ with respect to the
remaining items. If some items of the original $B_{1}$ also remain, they can
be moved into $B_{2}$, while still giving a partition in ${\cal{F}}_{n-1,q}$.)
Continue in the same fashion with bin $B_{2}$, and more generally with the
remaining bins, up to and including bin $B_{n-q}$. At this point only $q$
agents remain, and for each of them the $NS_{q,q}$ share over the remaining
items has value at least as high as the original $NS_{n,q}$ share. After
computing the respective $NS_{q,q}$ partitions over these remaining items, the
assumption that $NS_{q,q}$ is feasible implies that one can allocate to each
of the $q$ remaining agents a bundle that she values at least as much as her
share.

The above algorithm runs in polynomial time (if an acceptable allocation for
$NS_{q,q}$ can be found in polynomial time). This follows from Lemma 18 that
shows that the $NS_{n,q}$ value of each of the agents can be computed in
polynomial time, together with a respective $NS_{n,q}$ partition.
$\blacksquare$

###### Definition 7

Consider two partitions of ${\cal{M}}$ into three disjoint bundles,
$P^{i}=(B_{1}^{i},B_{2}^{i},B_{3}^{i})$ and
$P^{j}=(B_{1}^{j},B_{2}^{j},B_{3}^{j})$. We say that $P^{i}$ and $P^{j}$ are
fully intersecting if every bundle of $P^{i}$ intersects every bundle of
$P^{j}$.

###### Lemma 10

Consider $n=3$, and for every agent $i\in\\{1,2,3\\}$ a partition of
${\cal{M}}$ into three disjoint bundles
$P^{i}=(B_{1}^{i},B_{2}^{i},B_{3}^{i})$. If no two partitions $P^{i}$ and
$P^{j}$ are fully intersecting, then there is an allocation
$A=(A_{1},A_{2},A_{3})$ such that for every agent $i$ with an additive
valuation function $v_{i}$ it holds that
$v_{i}(A_{i})\geq\min[v_{i}(B_{1}^{i}),v_{i}(B_{2}^{i}),v_{i}(B_{3}^{i})]$.
Moreover, given the partitions $P^{i}$ for $i\in\\{1,2,3\\}$ and the additive
valuations $(v_{1},v_{2},v_{3})$, such an allocation $A$ can be computed in
polynomial time.

Proof. Consider three agents with additive valuation functions, $v_{i}$ for
each agent $i$, and associated partitions
$P^{i}=(B_{1}^{i},B_{2}^{i},B_{3}^{i})$, for every agent $i\in\\{1,2,3\\}$.

For every two agents $i$ and $k$ (it can be that $i=k$) we define
$v_{i}(P^{k})=\min_{j\in\\{1,2,3\\}}[v_{i}(B_{j}^{k})]$. We refer to
$v_{i}(P^{i})$ as the share of agent $i$. We show that there is an allocation
that gives every agent at least her share.

We say that a bundle $B$ is acceptable for agent $i$ if $v_{i}(B)\geq
v_{i}(P^{i})$. Every bundle in her $P^{i}$ partition is acceptable for $i$.
Moreover, for every $k\not=i$, at least one bundle in the $P^{k}$ partition is
acceptable for $i$ (as
$\max_{j\in\\{1,2,3\\}}[v_{i}(B_{j}^{k})]\geq\frac{1}{3}\sum_{j\in\\{1,2,3\\}}v_{i}(B_{j}^{k})=\frac{1}{3}\sum_{j\in\\{1,2,3\\}}v_{i}(B_{j}^{i})\geq
v_{i}(P^{i})$).

Consider two of the agents, say 1 and 2. Suppose that there are two bundles in
the $P^{2}$ partition that are acceptable for agent 1. Then we can give agent
3 the bundle that is acceptable for her in the $P^{2}$ partition, give agent 1
a different bundle from the $P^{2}$ partition that is acceptable for agent 1,
and give the remaining bundle to agent 2. This is an acceptable allocation.
Hence we may assume that at most one bundle in $P^{2}$ is acceptable for agent
1.

As at most one bundle in $P^{2}$ is acceptable for agent 1, there is a bundle
$B^{2}_{j}$ in the $P^{2}$ partition that is not acceptable for agent 1.
Suppose that there is a bundle $B^{1}_{j^{\prime}}$ in the $P^{1}$ partition
that is disjoint from $B^{2}_{j}$. In this case, if $B^{2}_{j}$ is removed,
agent 1 can still make two bundles each of value at least $v_{i}(P^{i})$,
where one bundle is $B^{1}_{j^{\prime}}$ and the other is
${\cal{M}}\setminus(B^{1}_{j^{\prime}}\cup B^{2}_{j})$. Hence if
$v_{3}(B^{2}_{j})\geq v_{3}(P^{3})$, we can give $B^{2}_{j}$ to agent 3, and
use cut and choose (any of the agents 1 or 2 can serve as the cutter) to give
each of the other two agents a bundle of value at least her share.
Alternatively, if $v_{3}(B^{2}_{j})<NS_{3,3}(v_{3})$, we can give $B^{2}_{j}$
to agent 2, and let agent 3 choose among the two bundles, $B^{1}_{j^{\prime}}$
or ${\cal{M}}\setminus(B^{1}_{j^{\prime}}\cup B^{2}_{j})$, the one with higher
$v_{3}$ value. This value is at least $PS_{3}(v_{3})$, and hence at least her
share $v_{3}(P^{3})$. As argued above, the remaining bundle gives agent 1 at
least her share $v_{i}(P^{i})$. In any case, we get an acceptable allocation.

Hence we can assume that each of the two bundles in the $P^{2}$ partition that
are not acceptable for agent 1 intersect all three bundles in the $P^{1}$
partition.

As partitions $P^{1}$ and $P^{2}$ are assumed not to be fully intersecting,
there must be two bundles (one from each partition) that do not intersect.
Moreover, we may assume that there is exactly one pair of bundles that do not
intersect, and that each of these bundles is the only bundle from that
partition that is acceptable for the other agent. (In every other case, the
above arguments show that an acceptable allocation exists.) In other words, we
may assume that the pair of acceptable bundles do not intersect. A similar
assumption holds for every pair of two different agents.

In a given input instance, if two different bundles in the $P^{i}$ partition
of agent $i$ are acceptable, each for a different other agent, then we have an
acceptable allocation. (For example, if $B^{1}_{1}$ is acceptable for agent 2
and $B^{1}_{2}$ is acceptable for agent 3, then
$(B^{1}_{3},B^{1}_{1},B^{1}_{2})$ is an acceptable allocation.) Hence each
agent $i$ has in her $P^{i}$ partition a unique bundle that is acceptable for
the other two agents. As acceptable bundles do not intersect, these three
bundles are disjoint. Hence they form an acceptable allocation (each agent
gets the acceptable bundle from her own partition). $\blacksquare$

###### Lemma 11

Consider an ordered allocation instance with three agents, and let $P^{i}$ and
$P^{j}$ be two $NS_{3,3}$ partitions of ${\cal{M}}$. Then $P^{i}$ and $P^{j}$
are not fully intersecting.

Proof. Let $e_{1},\ldots,e_{m}$ be an ordering of the items (from most to
least valuable) in the ordered instance. Given this order, an $NS_{3,3}$
partition is fully specified by four integral cutting points $0\leq c_{1}\leq
c_{2}\leq c_{3}\leq c_{4}\leq m$, where
$B_{1}=\\{e_{1},\ldots,e_{c_{1}}\\}\cup\\{e_{c_{4}},\ldots e_{m}\\}$,
$B_{2}=\\{e_{c_{1}},\ldots,e_{c_{2}}\\}\cup\\{e_{c_{3}},\ldots e_{c_{4}}\\}$,
and $B_{3}=\\{e_{c_{2}},\ldots,e_{c_{3}}\\}$. That is, $B_{3}$ is composed of
a single interval, whereas each of $B_{1}$ and $B_{2}$ is a union of two
intervals. (If there are equalities in the chain $0\leq c_{1}\leq c_{2}\leq
c_{3}\leq c_{4}\leq m$ of weak inequalities, then some of the intervals are
empty.)

Each of the partitions $P^{i}$ and $P^{j}$ has four cutting points, and
together these cutting points create $2*4+1=9$ intervals (some of which might
be empty). Each of these intervals (when non-empty) represents a consecutive
set of items that in each of the two partitions belong to a single bundle.
Hence there is a mapping between these non-empty intervals and pairs of
bundles of $P^{i}$ and $P^{j}$ that intersect: every non-empty interval can be
mapped to such an intersecting pair, and every intersecting pair is mapped to
by some non-trivial interval. The mapping is surjective (onto) but cannot be
one-to-one. In particular, both the first interval and the last interval (when
non-empty) map to the same pair $(B_{1}^{i},B_{1}^{j})$. Hence the number of
intersecting pairs is at most $9-1=8$, proving that $P^{i}$ and $P^{j}$ are
not fully intersecting. $\blacksquare$

###### Theorem 7

For the class of additive valuations and every $n\geq 3$, the $NS_{n,3}$ share
is feasible. Moreover, an acceptable allocation can be found in polynomial
time.

Proof. We prove the theorem for $n=3$, namely, for $NS_{3,3}$. By Lemma 9 this
will imply the theorem for all $n>3$. Moreover, we assume that the instance is
ordered. This assumption can be made without loss of generality, by Lemma 8.

Let $P^{i}=(B_{1}^{i},B_{2}^{i},B_{3}^{i})$ for $i\in\\{1,2,3\\}$ be an
$NS_{3,3}$ partition of ${\cal{M}}$ for $v_{i}$. By Lemma 11, $P^{i}$ and
$P^{j}$ are not fully intersecting for any $i,j\in\\{1,2,3\\}$. By Lemma 10
there is an allocation $A=(A_{1},A_{2},A_{3})$ such that for every agent $i$
with an additive valuation function $v_{i}$ it holds that
$v_{i}(A_{i})\geq\min[v_{i}(B_{1}^{i}),v_{i}(B_{2}^{i}),v_{i}(B_{3}^{i})]=NS_{3,3}(v_{i})$.
Thus, the share $NS_{3,3}$ is feasible. Moreover, Lemma 10 also shows that
given the partitions $P^{i}$ for $i\in\\{1,2,3\\}$ and the additive valuations
$(v_{1},v_{2},v_{3})$, such an allocation $A$ can be computed in polynomial
time. $\blacksquare$

##  7 Discussion

In this paper we have focused on fair allocation of indivisible _goods_ when
agents have _equal_ entitlements to the goods, and have suggested notions for
share-based fairness.

While we focus on _equal_ entitlements, the notions of a share, a share
guarantee, and of a self-maximizing share, can naturally be extended to
_arbitrary_ (non-equal) entitlements. In the definition of a share and of a
share guarantee, one should simply replace the number of agents parameter $n$,
by the entitlement of the agent. In Appendix C we discuss some shares that
were defined in prior work for arbitrary entitlements, and whether they are
self maximizing or not. Note that our non-existence results for SM-dominant
feasible shares clearly extend to this more general set of problems. An
interesting direction for future work is of extending our work to settings
where agents have arbitrary entitlements.

One can also consider items that are chores (bads) instead of goods. Our
definitions naturally extend to chores as well. Our positive results (Section
6) are for agents with additive valuations over goods. The positive results
are not based on picking orders, since it is impossible to obtain such results
using picking order shares when items are goods. That is, for every $\rho>0$,
for sufficiently large $n$, no picking order share has value larger than
$\rho$-MMS when valuations are additive over goods. This follows from results
in [2]. However, for chores, there are picking orders that guarantee that
every agent with an additive valuation gets a bundle of value no more than
$\frac{5}{3}$ times her MMS. See [3]. As our results that picking order shares
are feasible, self maximizing and poly-time computable for additive valuations
(see Section 4.1) do not rely on the items being goods, we get that for
additive valuations over chores, there is a feasible share that is
$\frac{5}{3}$-dominating, self maximizing and poly-time computable.

Finally, we note that we leave open the problem of finding (for additive
valuations, and also beyond this class), the largest value of $\rho$ for which
there exists a feasible share that is $\rho$-dominating, self maximizing and
poly-time computable.

## References

  * ABF+ [21] Georgios Amanatidis, Georgios Birmpas, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenhäuser.  Allocating indivisible goods to strategic agents: Pure nash equilibria and fairness.  In Web and Internet Economics - 17th International Conference, WINE 2021, Potsdam, Germany, December 14-17, 2021, Proceedings, volume 13112 of Lecture Notes in Computer Science, pages 149–166. Springer, 2021\.
  * ABM [16] Georgios Amanatidis, Georgios Birmpas, and Evangelos Markakis.  On truthful mechanisms for maximin share allocations.  In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI’16, pages 31–37, 2016.
  * ALW [20] Haris Aziz, Bo Li, and Xiaowei Wu.  Approximate and strategyproof maximin share allocation of chores with ordinal preferences.  CoRR, abs/2012.13884, 2020.
  * AMNS [17] Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, and Amin Saberi.  Approximation algorithms for computing maximin share allocations.  ACM Transactions on Algorithms (TALG), 13(4):1–28, 2017.
  * ARSW [17] Haris Aziz, Gerhard Rauchecker, Guido Schryen, and Toby Walsh.  Algorithms for max-min share fair allocation of indivisible chores.  In Satinder P. Singh and Shaul Markovitch, editors, Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA, pages 335–341. AAAI Press, 2017\.
  * [6] Moshe Babaioff, Tomer Ezra, and Uriel Feige.  Best-of-both-worlds fair-share allocations.  arXiv preprint arXiv:2102.04909, 2021.
  * [7] Moshe Babaioff, Tomer Ezra, and Uriel Feige.  Fair-share allocations for agents with arbitrary entitlements.  In EC ’21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021, page 127. ACM, 2021.
  * BK [20] Siddharth Barman and Sanath Kumar Krishnamurthy.  Approximation algorithms for maximin fair division.  ACM Transactions on Economics and Computation (TEAC), 8(1):1–28, 2020.
  * BL [16] Sylvain Bouveret and Michel 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\.
  * BNT [20] Moshe Babaioff, Noam Nisan, and Inbal Talgam-Cohen.  Competitive equilibrium with indivisible goods and generic budgets.  Mathematics of Operations Research, 2020.
  * Bud [11] Eric Budish.  The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.  Journal of Political Economy, 119(6):1061–1103, 2011.
  * CFS [17] Vincent Conitzer, Rupert Freeman, and Nisarg Shah.  Fair public decision making.  In Constantinos Daskalakis, Moshe Babaioff, and Hervé Moulin, editors, Proceedings of the 2017 ACM Conference on Economics and Computation, EC ’17, Cambridge, MA, USA, June 26-30, 2017, pages 629–646. ACM, 2017.
  * CKM+ [19] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang.  The unreasonable fairness of maximum nash welfare.  ACM Transactions on Economics and Computation (TEAC), 7(3):1–32, 2019.
  * FGH+ [19] Alireza Farhadi, Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Sebastien Lahaie, David Pennock, Masoud Seddighin, Saeed Seddighin, and Hadi Yami.  Fair allocation of indivisible goods to asymmetric agents.  Journal of Artificial Intelligence Research, 64:1–20, 2019.
  * FN [22] Uriel Feige and Alexey Norkin.  Improved maximin fair allocation of indivisible items to three agents.  CoRR, abs/2205.05363, 2022.
  * FST [21] Uriel Feige, Ariel Sapir, and Laliv Tauber.  A tight negative example for MMS fair allocations.  CoRR, abs/2104.04977, 2021.
  * GHS+ [18] Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami.  Fair allocation of indivisible goods: Improvements and generalizations.  In Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, pages 539–556. ACM, 2018.
  * GLW [21] Laurent Gourvès, Julien Lesca, and Anaëlle Wilczynski.  On fairness via picking sequences in allocation of indivisible goods.  In Dimitris Fotakis and David Ríos Insua, editors, Algorithmic Decision Theory - 7th International Conference, ADT 2021, Toulouse, France, November 3-5, 2021, Proceedings, volume 13023 of Lecture Notes in Computer Science, pages 258–272. Springer, 2021.
  * GM [19] Laurent Gourvès and Jérôme Monnot.  On maximin share allocations in matroids.  Theor. Comput. Sci., 754:50–64, 2019.
  * [20] Jugal Garg, Peter McGlaughlin, and Setareh Taki.  Approximating maximin share allocations.  Open access series in informatics, 69, 2019.
  * [21] Jugal Garg, Peter McGlaughlin, and Setareh Taki.  Approximating maximin share allocations.  In Jeremy T. Fineman and Michael Mitzenmacher, editors, 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8-9, 2019, San Diego, CA, USA, volume 69 of OASICS, pages 20:1–20:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * GT [20] Jugal Garg and Setareh Taki.  An improved approximation algorithm for maximin shares.  In Proceedings of the 21st ACM Conference on Economics and Computation, pages 379–380, 2020.
  * HL [19] Xin Huang and Pinyan Lu.  An algorithmic framework for approximating maximin share allocation of chores.  arXiv preprint arXiv:1907.04505, 2019.
  * HS [21] Hadi Hosseini and Andrew Searns.  Guaranteeing maximin shares: Some agents left behind.  In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, pages 238–244. ijcai.org, 2021.
  * KPW [18] David Kurokawa, Ariel D. Procaccia, and Junxing Wang.  Fair enough: Guaranteeing approximate maximin shares.  J. ACM, 65(2):8:1–8:27, 2018.
  * LMMS [04] Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi.  On approximately fair allocations of indivisible goods.  In Proceedings of the 5th ACM Conference on Electronic Commerce, EC’04, pages 125–131, 2004.
  * Pro [20] Ariel D. Procaccia.  An answer to fair division’s most enigmatic question: technical perspective.  Commun. ACM, 63(4):118, 2020.

##  Appendix A Notes on Auxiliary Goals

It is important to clarify the following point. Though it is interesting to
know what the highest possible value of $\rho$ is in Question 2, this does not
necessarily imply that one would want to actually use a share that has the
highest possible value of $\rho$. It is true that shares with high value of
$\rho$ improve the guarantees given to agents. However, it is also true that
the improved guarantees limit the flexibility given to the allocator – he has
fewer acceptable allocations to choose from. This might hurt other measures of
performance that the allocator cares about, and possibly also the agents care
about. We refer to these other measures of performance as auxiliary goals, as
they go beyond the goal of giving every agent at least her share. Here are
some examples of auxiliary goals.

  * •

Auxiliary goals such as maximizing welfare (the sum of values received by all
agents) or maximizing Nash Social Welfare (the product of values received by
all agents) attempt to choose a “best possible” allocation (according to the
auxiliary goal), subject to the constraint that every agent gets at least her
share.

  * •

Ex-ante guarantees. Allocation processes are often randomized. For example,
when allocating a single indivisible item to one of two agents, having a
lottery to decide who receives the item is common practice. The lottery offers
the agents an ex-ante guarantee that is valuable (for example, that the agent
has probability $\frac{1}{2}$ of winning the item), whereas no ex-post
guarantee can be given to both agents. Hence an allocator may have the
auxiliary goal of selecting a distribution over allocations that offers some
desirable ex-ante guarantee. The “contracts” with the agents then require that
this distribution be supported only over allocations that give each agent at
least her share.

  * •

Mechanisms with money. Though the interest in this paper is in settings
without money, the notion of a share may be relevant also to mechanisms with
money. Suppose for example that the items are health services (such as doctor
appointments, or medical drugs) and the agents are members of a health
maintenance organization (HMO) that provides these services. Every member, as
a function of her needs (her valuation function), is entitled to at least some
minimum service (her share). Suppose now that members can ask for additional
services beyond their share, as long as they are willing to pay for these
additional services, and as long as the shares of other members are respected.
In this case, the auxiliary goal of the HMO when running the allocation
mechanism might be to maximize revenue (choosing the allocation of resources
that generates maximum revenue from the members), subject to the constraint
that every member gets at least her share, and can be charged only for
services that are beyond her share.

As the examples above show, there may be some tension between the desire to
have shares of high value and the desire to accomplish additional auxiliary
goals. High share values protect each individual agent against the possibility
that the auxiliary goals will drive her value to be too low. High share values
also reduce the motivation of agents to try to manipulate the allocation
mechanism, as there is less to gain by manipulation, and potentially more to
lose. However, share values that are too high might limit the extent to which
the auxiliary goals can be achieved, and hence might also not be desirable. If
auxiliary goals are present, then they should be taken into account when
deciding on a choice of share function, so as to strike a good balance between
the share guarantees and the auxiliary goals. In the current paper we are only
concerned with determining what values of $\rho$ are achievable by
$\rho$-dominating shares, and leave aspects concerning tradeoffs with other
auxiliary goals to future work.

We end this section by noting that the standard economic efficiency auxiliary
goal of producing a Pareto optimal allocation is never in conflict with the
selection of a feasible share. For every feasible share, there always an
acceptable allocation that is also Pareto optimal. This is because replacing
an acceptable allocation by an allocation that Pareto dominates it preserves
acceptability.

##  Appendix B Statement of Intent

Our focus in this paper is on the _guarantee_ that a feasible share provides
to each agent. This should be distinguished from what we shall refer to as a
_non-binding “statement of intent”_. Such a statement might be, for example,
an intent to implement an allocation that gives every agent her maximin share.
Often this statement can be met, but sometimes not (either because no maximin
allocation exists, or because of computational difficulties of finding such an
allocation even when it does exist, or because of computational difficulties
of computing the maximin share values of the agents and verifying whether a
given allocation satisfies them). The statement of intent is non-binding and
is perceived as such by the agents.

Our paper concerns with a _guarantee_ (not just a non-binding statement of
intent) that the implemented allocation will give the agent at least her
share, for some share that is different than the maximin share and is
feasible. Let us call our share the FSMP-share, where FSMP stands for
feasible. self maximizing, and polynomial time computable. The actual value of
the FSMP-share can be computed in polynomial time (so the agent can verify
that the guarantee is met), and the share is self maximizing (reporting the
true valuation function maximizes the value of the guarantee). Moreover, the
FSMP-share is at least a $\rho$-fraction of the MMS. (Our current value of
$\rho$ for every $n$ is $2/3$, but this ratio might be improved in the
future.)

Using the above terminology, one might wonder what would an agent prefer, a
statement of intent that is “simple-to-understand” (e.g., concerning the
maximin share), or a guaranteed FSMP-share? Our answer is that the agent would
prefer not to be forced to choose between the two, but rather to get both.
This is exactly what we offer the agent. The FSMP-share does not dictate which
allocation algorithm is to be used. (On the contrary - the property of a share
being self maximizing is more closely connected to incentive compatibility if
the agent does not know which allocation algorithm will be run. See discussion
on incentive compatibility in Section 1.1.) The polynomial time allocation
algorithm that we offer that guarantees every agent her FSMP-share only serves
as a “safety” allocation algorithm. However, in practice, the social planner
can (and is advised to) additionally run any number of allocation algorithms
of his choice (possibly, including allocation algorithms that search for a
maximin allocation). For every allocation produced in any of the runs, the
social planner can check in polynomial time whether every agent got at least
her FSMP-share. Among the allocations that survive this test (the safety
algorithm guarantees that at least one allocation survives), the social
planner is allowed to choose any surviving allocation. If the social planner
made a statement of intent with respect to MMS allocations and determines that
some surviving allocations is an MMS allocation, he may choose such an
allocation (fulfilling the statement of intent). In any case, whichever
allocation is chosen, it will give every agent at least her FSMP-share
(satisfying the guarantee).

We believe that in practice agents will appreciate getting an FSMP-share
guarantee. (The actual FSMP-share of choice may be from the $NS_{n,q}$ family
of shares introduced in this paper, or some other FSMP-share that is yet to be
introduced.) This guarantee is easy to understand, in a sense that there is a
polynomial time algorithm that translates it to a guaranteed value. In
addition, the agent may also appreciate getting a “statement of intent” of
some sort (e.g., that an effort will be made to find a maximin fair allocation
and such an allocation will often be implemented). Both FSMP-share guarantees
and statements of intent have value in practice, and they can be taken into
account simultaneously.

##  Appendix C Self-Maximizing Shares for Arbitrary Entitlements

Two share notions (among others) defined for arbitrary entitlements are the
Truncated-Proportional Share (TPS) [6] and the AnyPrice Share (APS) [7]. We
next observe that while the APS is self maximizng, the TPS is not.

###### Proposition 12

The APS is self-maximizing. In contrast, the TPS is not self-maximizing, not
even for additive valuation functions.

Proof. The APS is self-maximizing: given any price vector, the affordable
bundle of highest value according to $v^{\prime}$ is among the bundles
considered when the APS chooses the bundle with highest value according to
$v$, and hence no better than that bundle.

The example presented in the proof of Proposition 2 which shows that the
proportional share is not self-maximizing also proves that the TPS is not
self-maximizing, as the TPS and PS are the same for that example.
$\blacksquare$

##  Appendix D No More than the Share Guarantee

In this section we show that for most valuation classes of interest (e.g.,
unit demand, additive, submodular, subadditive), it is indeed the case that an
agent might only get her guaranteed share (and no more) when the allocation
and valuations of others are worse case.

For the purpose of Proposition 13 below, we define the notion of a hereditary
class of valuation functions.

###### Definition 8

We say that a class $\cal{C}$ of valuation functions is hereditary if for
every two sets of items, ${\cal{M}}^{\prime}\subset{\cal{M}}$, and for every
valuation function $v^{\prime}\in\cal{C}$ for ${\cal{M}}^{\prime}$, the
valuation function $v$ for ${\cal{M}}$, defined as
$v(S)=v^{\prime}(S\cap{\cal{M}}^{\prime})$ for every $S\subseteq{\cal{M}}$, is
also in $\cal{C}$.

Most valuation classes of interest (e.g., unit demand, additive, submodular,
subadditive) are hereditary. An example of a valuation function that is not
hereditary is an additive valuation function in which the value of every item
is required to be a strictly positive integer.

###### Proposition 13

Let $\cal{C}$ be a hereditary class of valuation functions, and let $s$ be a
feasible share for $\cal{C}$, with associated share guarantee $\hat{s}$. Then
for every set ${\cal{M}}$ of items and every number $n\geq 2$ of agents, for
every valuation $v\in\cal{C}$ defined over ${\cal{M}}$, there is a feasible
allocation mechanism $AM_{v}$ for $\cal{C}$ and there are valuations in
$\cal{C}$ for the remaining $n-1$ agents, such that $AM_{v}$ allocates to the
agent holding valuation function $v$ a bundle of items of value exactly
$\hat{s}(v,n)$.

Proof. Let $B\subseteq{\cal{M}}$ be such that $v(B)=\hat{s}(v,n)$. Without
loss of generality we need to prove the claim for agent 1. For agent 1, let
$v_{1}=v$, and for every other agent $i>1$, let $v^{\prime}_{i}\in\cal{C}$ be
an arbitrary valuation function defined over
${\cal{M}}^{\prime}={\cal{M}}\setminus B$, and let $v_{i}$ be such that
$v_{i}(S)=v^{\prime}_{i}(S\cap{\cal{M}}^{\prime})$ (note that as $\cal{C}$ is
a hereditary class of valuation functions there exist such $v_{i}$ in
$\cal{C}$). Let $AM$ be an arbitrary feasible allocation mechanism for
$\cal{C}$, and let $(A_{1},\ldots,A_{n})$ be its allocation on this given
instance. Modify $AM$ to $AM_{v}$, as follows. Only in this given instance,
replace the allocation to $(B,A_{2}\setminus B,\ldots,A_{n}\setminus B)$. As
for any $i>1$ it holds that $v_{i}(A_{i}\setminus B)=v_{i}(A_{i})$, the
allocation still gives every agent at least her share value, and hence is
feasible. Thus $AM_{v}$ is a feasible allocation mechanism, and on this
instance, it gives the agent holding $v$ a bundle of value exactly
$\hat{s}(v,n)$. $\blacksquare$

###### Remark 9

The condition that the class of valuation functions is hereditary is not
strictly necessary for Proposition 13. Weaker conditions also suffice, though
may require a different proof. On the other hand, if conditions stronger than
just being hereditary are imposed, the proposition can be strengthened by
reversing the order of quantifiers – choosing one universal allocation
mechanism $AM$ that applies for all $v$. For example, if $\cal{C}$ is the
class of additive valuation functions, than $AM$ can be chosen as an
allocation mechanism that maximizes welfare, conditioned on giving every agent
at least her fair share. Then, for every additive valuation function $v$, one
can choose additive valuation functions for the remaining agents, such that
the allocation mechanism will necessarily give the agent holding $v$ a bundle
of value exactly equal to the corresponding share guarantee. Further details
are omitted.

##  Appendix E Missing Proof from Section 3

###  E.1 Missing Proof from Section 3.2

####  E.1.1 Proof of Proposition 2

We restate and prove Proposition 2.

See 2

Proof. Fix any class ${\mathcal{C}}$ of valuations. The MMS is self-maximizing
for ${\mathcal{C}}$: for any valuation $v\in{\mathcal{C}}$, any MMS partition
that is computed with respect to $v^{\prime}\in{\mathcal{C}}$ is also a
legitimate candidate for an MMS partition for $v$, and hence no better than
the actual best MMS partition with respect to $v$.

The proportional share is self maximizing for additive valuations if $n=2$:
for additive valuation function $v$, the proportional share guarantee is
$\min_{\\{B\;|\;v(B)\geq\frac{1}{2}v({\cal{M}})\\}}[v(B)]$. Let $B^{*}$ be a
bundle achieving the minimum in this expression. Then for every additive
valuation function $v^{\prime}$, either $B^{*}$ or ${\cal{M}}\setminus B^{*}$
gives the proportional share with respect to $v^{\prime}$ (because $n=2$), so
at least one of these sets is considered acceptable when reporting
$v^{\prime}$. As $v({\cal{M}}\setminus B^{*})\leq v(B^{*})$, the implied
guarantee cannot improve by reporting $v^{\prime}$ instead of $v$. Thus, for
any $v^{\prime}$:
$\hat{s}_{{v}}({{v}})=\hat{s}(v,n)=v(B^{*})=\max\\{v(B^{*}),v({\cal{M}}\setminus
B^{*})\\}\geq\hat{s}_{{v}}({{v^{\prime}}})$

The proportional share (PS) is not self-maximizing for additive valuations and
$n\geq 3$: let $n\geq 3$ and ${\cal{M}}=\\{e_{1},\ldots,e_{n+2}\\}$, with
$v(e_{j})=\frac{n-1}{n}$ for $j\leq n$, and
$v(e_{n+1})=v(e_{n+2})=\frac{1}{2}$. The proportional share (PS) and the PS
guarantee (the bundle $\\{e_{n+1},e_{n+2}\\}$) are both 1. However, reporting
$v^{\prime}(e_{j})=\frac{2n-1}{2n}$ for $j\leq n$, and
$v^{\prime}(e_{n+1})=v^{\prime}(e_{n+2})=\frac{1}{4}$, still have that the
proportional share with respect to $v^{\prime}$ is $1$. However, the bundle
$\\{e_{n+1},e_{n+2}\\}$ no longer gives the PS-guarantee with respect to
$v^{\prime}$ (as its value with respect to $v^{\prime}$ is less than $1$), and
any acceptable bundle with respect to $v^{\prime}$ contains at least one item
$e_{j}$ with $j\leq n$, and has at least two items. Consequently, by reporting
$v^{\prime}$ the PS-guarantee with respect to $v$ improves to
$\frac{n-1}{n}+\frac{1}{2}>1$, where the inequality holds for $n\geq 3$.
Formally, for $v$ and $v^{\prime}$ it holds that
$\hat{s}_{{v}}({{v}})=\hat{s}(v,n)=1<\frac{n-1}{n}+\frac{1}{2}=\hat{s}_{{v}}({{v^{\prime}}})$,
and thus the proportional share for $n\geq 3$ is not self maximizing.

$\rho$-MMS is not self-maximizing for additive valuations and any $\rho$ such
that $0<\rho<1$. We consider different values of $\rho$ and for each present
an instance with a beneficial manipulation:

  * •

$\frac{1}{2}<\rho<1$: There are $n$ agents and $m=n+1$ items, $v_{i}(e_{j})=1$
for $1\leq j\leq n-1$, $v_{i}(e_{n})=\rho$, and $v_{i}(e_{n+1})=1-\rho$. The
MMS is 1, and the $\rho$-MMS guarantee may give the agent only item $e_{n}$,
of value $\rho<1$. By reporting value of $\frac{1}{2}$ for each of the items
$e_{n}$ and $e_{n+1}$, the MMS remains 1, but neither $e_{n}$ alone nor
$e_{n+1}$ alone have reported value at least $\rho$. Every bundle that has
reported value at least $\rho$ has true value at least 1, which is larger than
$\rho$. Hence, reporting $v_{i}$ does not maximize the implied guarantee of
agent $i$.

  * •

$0<\rho<\frac{1}{2}$: The above example extends to every $0<\rho<\frac{1}{2}$,
by reporting values of $\frac{\rho}{2}$ and $1-\frac{\rho}{2}$ instead of
$\rho$ and $1-\rho$, for items $e_{n}$ and $e_{n+1}$, respectively. (By
misreporting, the agent improves the implied guarantee from $\rho<\frac{1}{2}$
to $1-\rho>\frac{1}{2}$.)

  * •

For the case $\rho=\frac{1}{2}$ and $n\geq 2$, consider an example with
$m=n+2$ items, $v_{i}(e_{j})=1$ for $1\leq j\leq n-2$,
$v_{i}(e_{n-1})=v_{i}(e_{n})=\frac{3}{4}$, and
$v_{i}(e_{n+1})=v_{i}(e_{n+2})=\frac{1}{4}$. By reporting values $\frac{1}{8}$
instead of $\frac{1}{4}$ and $\frac{7}{8}$ instead of $\frac{3}{4}$, the
implied guarantee improves from $\frac{1}{2}$ to $\frac{3}{4}$.

$\blacksquare$

####  E.1.2 Proof of Proposition 3

We restate and prove Proposition 3. See 3 Proof. Suppose that $s$ is a share
that is not scale invariant for ${\mathcal{C}}$. Then there is a valuation
function $v\in{\mathcal{C}}$ and a multiplicative factor $c>0$ for which the
share guarantee satisfies $\hat{s}_{{c\cdot v}}({{c\cdot v}})=\hat{s}(c\cdot
v,n)\neq c\cdot\hat{s}(v,n)=c\cdot\hat{s}_{{v}}({{v}})$. Assume that
$\hat{s}_{{c\cdot v}}({{c\cdot v}})>c\cdot\hat{s}_{{v}}({{v}})$. Then $s$ is
not self maximizing, because for an agent with valuation function $v$, by
reporting $c\cdot v$ (which is in ${\mathcal{C}}$ by assumption) the agent
guarantees to herself a bundle of higher value (according to her original $v$)
than by reporting $v$. Formally, $c\cdot\hat{s}_{{v}}({{c\cdot
v}})=\hat{s}_{{c\cdot v}}({{c\cdot v}})>c\cdot\hat{s}_{{v}}({{v}})$.

Suppose that $s$ is a share that is not monotone for ${\mathcal{C}}$. Then
there are two valuation functions, $v,v^{\prime}\in{\mathcal{C}}$, such that
$v\geq v^{\prime}$ but
$\hat{s}_{{v}}({{v}})=\hat{s}(v,n)<\hat{s}(v^{\prime},n)=\hat{s}_{{v^{\prime}}}({{v^{\prime}}})$.
Then $s$ is not self maximizing, because for an agent with valuation function
$v\in{\mathcal{C}}$, by reporting $v^{\prime}\in{\mathcal{C}}$ she guarantees