of existence of an equilibrium (since we require finite utility functions),
and therefore can not be used. In fact, an equilibrium may not even exist if
we allow $\infty$ disutility values [22]. Thus, in the bads case every agent
can possibly be assigned any bad and utility functions must be designed in
such a way that only certain desired allocations happen at equilibrium.

We first show the hardness for the exchange model that we later extend to the
Fisher (and CEEI) model. Let us start by defining approximate equilibrium of
exchange setting.

##### Approximate Exchange Equilibrium

Recall that an exchange equilibrium
$(\mbox{\boldmath$p$}^{*},\mbox{\boldmath$x$}^{*})$ satisfies the following
two conditions:

  1. C1.

Optimal bundle: For each $i\in N$,
$\mbox{\boldmath$x$}^{*}_{i}\in{\operatorname{\mathrm{arg\,min}}}\\{f_{i}(\mbox{\boldmath$x$})\
\text{ s.t. }\ \mbox{\boldmath$x$}\geq 0;\
\mbox{\boldmath$x$}^{*}_{i}\cdot\mbox{\boldmath$p$}^{*}\geq\mbox{\boldmath$w$}_{i}\cdot\mbox{\boldmath$p$}^{*}\\}$.

  2. C2.

Supply-Demand: For each $j\in M$, $\sum_{i\in N}x^{*}_{ij}=\sum_{i\in
N}W_{ij}$.

The equilibrium is said to be $\epsilon$-approximate, for $\epsilon>0$, if the
optimal bundle condition holds as above and the demand meets supply
approximately:

  * C2’.

$\epsilon$-Supply-Demand: For each $j\in M$, $|\sum_{i\in
N}x^{*}_{ij}-\sum_{i\in N}W_{ij}|\leq\epsilon(\sum_{i\in N}W_{ij})$.

In our proof of hardness, we reduce finding approximate well-supported Nash
equilibrium of a two-player game to finding approximate competitive
equilibrium, defined as follows.

##### 2-Nash

A two-player game, where each player has $n$ moves to chose from, can be
represented by two $n\times n$ payoff matrices $(R,C)$. This is because in a
play one of the player can be thought of choosing a row (row-player) and the
other player choosing a column (column-player), and the corresponding entry in
$R$ and $C$ are their payoffs respectively. The Nash equilibrium problem can
be states as follows: Given payoff matrices $R,C\in[0,1]^{n\times n}$ and
$\epsilon>0$, find mixed-strategy (probability distribution)
$\boldsymbol{\alpha}$ for the row-player and $\boldsymbol{\beta}$ for the
column-player such that,
$\boldsymbol{\alpha},\boldsymbol{\beta}\in\\{\mathbf{z}\geq
0|\sum_{s\in[n]}z_{s}=1\\}$ and,

$\forall s,t\in[n],\ \ \ \
(R\boldsymbol{\beta})_{s}\leq(R\boldsymbol{\beta})_{t}-\epsilon\Rightarrow\alpha_{s}=0\
\ \mbox{ and }\ \
(\boldsymbol{\alpha}^{T}C)_{s}\leq(\boldsymbol{\alpha}^{T}C)_{t}-\epsilon\Rightarrow\beta_{s}=0.$
(17)

A remarkable series of results in 2006 settled the complexity of finding
(approximate) Nash equilibrium in finite games [32, 24]. In particular, [24]
show that for any $c>0$, finding $1/n^{c}$-approximate well-supported Nash
equilibrium in two player games is ${\sf PPAD}$-hard. We provide a reduction
from finding a $1/n$-approximate Nash equilibrium to finding a
$1/poly(n)$-approximate equilibrium in the exchange setting for bads under
SPLC cost functions to show Theorem 28. And then reduce exchange to CEEI to
show Theorem 29 below.

######  Theorem 28.

Finding a $\frac{1}{poly(n)}$-approximate equilibrium in a bads exchange
setting with SPLC cost is ${\sf PPAD}$-hard, where $m$ is the number of bads.
This holds even if every utility function has at most two segments with $O(1)$
costs.

######  Theorem 29.

Finding a $\frac{1}{poly(n)}$-approximate equilibrium in a bads Fisher setting
with equal budgets (CEEI) under SPLC costs is ${\sf PPAD}$-hard, where $m$ is
the number of bads. This holds even if every utility function has at most
three segments with $O(1)$ costs.

###  7.1 Exchange Setting Construction

Given an $n\times n$ game $(R,C)$ we construct an exchange setting
$\mathcal{M}(R,C)$ of bads with SPLC utilities as follows:

Bads. The setting has $m=2n+2$ bads, $M={1,\dots,m}$. Intuitively prices of
items $\\{1,\dots,n\\}$ will correspond to vector $\boldsymbol{\alpha}$, and
that of items $\\{n+1,\dots,2n\\}$ will correspond to vector
$\boldsymbol{\beta}$ of the Nash equilibrium.

Agents, their endowments, and utility functions. Let $H$ be a large constant
that we will set later, and let $(c)^{+}$ denote $\max\\{c,0\\}$. Next, we
will describe four sets of agents, and $N$ is the union of these four. If the
cost function is linear we only specify the slope and if it is PLC then we
represent it by a list of (slope, length) pairs. Note that we work with
disutility values $D_{ijk}=|U_{ijk}|$. Also note that we only specify non-zero
endowments.

  * •

Price-regulating agents $N_{PR}$. For every pair of items $(j,j^{\prime})\in
M\times M$ where $j\neq j^{\prime}$, there is an agent $a_{j,j^{\prime}}\in
N_{PR}$. For notational simplicity let $i=a_{j,j^{\prime}}$, then $i$’s
endowment and utility functions are

    * –

Endowment: $W_{i,j}=1/n$.

    * –

Utility Functions: $u_{ij}=1$, $u_{ij^{\prime}}=2$, and $u_{ik}=H$ otherwise.

  * •

Deficit agents $N_{D}$. For every item $j\in[2n]$, there is an agent $a_{j}\in
N_{D}$. Let $i=a_{j}$, then $i$’s endowment and utility functions are

    * –

Endowment: $W_{i,(m-1)}=W_{i,(2n+1)}=1/n^{8}$.

    * –

Utility Functions: $u_{ij}=1$, and $u_{ik}=H$ otherwise.

  * •

Row-player’s agents $N_{R}$. For every pair $s,s^{\prime}\in[n]$, there are
two agents, $a_{s,s^{\prime},R}\in N_{R}$ and $a_{s^{\prime},s,R}\in N_{R}$.
Let us denote these by $i$ and $i^{\prime}$ respectively. Our goal is to
capture the NE conditions for the row-player using the optimal bundles of
these two agents, and therefore their endowments and utility functions are
closely related.

    * –

Endowment: For each $k\in[n]$, let $r_{k}=(R_{s^{\prime}k}-R_{sk})$, and
define $r=\sum_{k}r_{k}$.

      * *

$W_{is}=W_{i^{\prime}s^{\prime}}=1/n^{4}$.

      * *

For each $k\in[n]$, $W_{i(n+k)}=\frac{(r_{k})^{+}}{n^{6}}$, and
$W_{i^{\prime}(n+k)}=\frac{(-r_{k})^{+}}{n^{6}}$.

      * *

$W_{i(m-1)}=\frac{(-r)^{+}}{n^{6}}$ and
$W_{i^{\prime}(m-1)}=\frac{(r)^{+}}{n^{6}}$.

    * –

Utility Functions:

      * *

$u_{i,s}=u_{i^{\prime},s^{\prime}}=\\{(1,1/n^{4}),(H,\infty)\\}$

      * *

For each $k\in[n]$, $u_{i,(n+k)}=\\{(1/3,(-r_{k})^{+}/n^{6}),(H,\infty)\\}$
and

$u_{i^{\prime},(n+k)}=\\{(1/3,(r_{k})^{+}/n^{6}),(H,\infty)\\}$.

      * *

$u_{i,(m-1)}=\\{(1/3,(r)^{+}/n^{6}),(H,\infty)\\}$ and
$u_{i^{\prime},(m-1)}=\\{(1/3,(-r)^{+}/n^{6}),(H,\infty)\\}$.

      * *

$u_{i,m}=u_{i^{\prime},m}=3$.

      * *

$u_{i,k}=u_{i^{\prime},k}=H$, otherwise.

  * •

Column-player’s agents $N_{C}$. For every pair $s,s^{\prime}\in[n]$, there are
two agents, $a_{s,s^{\prime},C}\in N_{C}$ and $a_{s^{\prime},s,C}\in N_{C}$.
Let us denote these by $i$ and $i^{\prime}$ respectively. Again, the goal is
to capture the NE conditions for the column-player using the optimal bundles
of these two agents, and therefore their endowments and utility functions are
constructed in similar way as above.

    * –

Endowment: For each $k\in[n]$, let $c_{k}=(C_{ks^{\prime}}-C_{ks})$, and set
$c=\sum_{k}c_{k}$.

      * *

$W_{i(n+s)}=W_{i^{\prime}(n+s^{\prime})}=1/n^{4}$.

      * *

For each $k\in[n]$, $W_{i,k}=\frac{(c_{k})^{+}}{n^{6}}$,
$W_{i^{\prime},k}=\frac{(-c_{k})^{+}}{n^{6}}$.

      * *

$W_{i(m-1)}=\frac{(-c)^{+}}{n^{6}}$ and
$W_{i^{\prime}(m-1)}=\frac{(c)^{+}}{n^{6}}$.

    * –

Utility Functions:

      * *

$u_{i,(n+s)}=u_{i^{\prime},(n+s^{\prime})}=\\{(1,1/n^{4}),(H,\infty)\\}$.

      * *

For each $k\in[n]$, $u_{i,k}=\\{(1/3,(-c_{k})^{+}/n^{6}),(H,\infty)\\}$ and

$u_{i^{\prime},k}=\\{(1/3,(c_{k})^{+}/n^{6}),(H,\infty)\\}$.

      * *

$u_{i,(m-1)}=\\{(1/3,(c)^{+}/n^{6}),(H,\infty)\\}$ and
$u_{i^{\prime},(m-1)}=\\{(1/3,(-c)^{+}/n^{6}),(H,\infty)\\}$.

      * *

$u_{i,m}=u_{i^{\prime},m}=3$.

      * *

$u_{i,k}=u_{i^{\prime},k}=H$, otherwise.

Note that, each of the $c_{k}$’s and $r_{k}$’s above are in $[-1,1]$, and
therefore for any bad $j\in M$, total endowment of it in the setting is
$\sum_{i\in
A}W_{ij}\leq\frac{(m-1)}{n}+\frac{n}{n^{4}}+\frac{2n^{2}}{n^{6}}+\frac{2n}{n^{8}}\leq
3$. Thus, the $\epsilon$-approximate supply-demand condition the above setting
$\mathcal{M}(R,C)$. can be re-written as,

$\forall j\in M,\ \ \ |\sum_{i\in N}x^{*}_{ij}-\sum_{i\in N}W_{ij}|\leq
3\epsilon.$ (18)

###  7.2 Correctness

In this section, we will show the following theorem.

######  Theorem 30.

Computing $\frac{1}{n}$-approximate well-supported Nash equilibrium in game
$(R,C)$ reduces to $\frac{1}{m^{8}}$-approximate exchange setting equilibrium
of $\mathcal{M}(R,C)$.

Let $(p^{*},\mbox{\boldmath$x$}^{*})$ be a $\frac{1}{m^{8}}$-approximate
exchange setting equilibrium of $\mathcal{M}(R,C)$. Using the fact that
$m=(2n+2)$ and equation (18), the approximate supply-demand condition
satisfied by the equilibrium is,

$\forall j\in M,\ \ \ |\sum_{i\in A}x_{ij}^{*}-\sum_{i\in A}W_{ij}|\leq
3/m^{8}<1/n^{8}.$ (19)

Before starting the reduction, we introduce some notation. We work with
absolute value of prices, but for notational simplicity we use $p^{*}_{j}>0$
to denote the price of bad $j$ in absolute value at equilibrium. Also, for any
subset of agents $\tilde{N}\subset N$, and any bad $j\in M$, let
$W_{j}(\tilde{N})=\sum_{i\in\tilde{N}}W_{ij}$. Similarly, define
$x^{*}_{j}(\tilde{N})=\sum_{i\in\tilde{N}}x_{ij}^{*}$.

The first step in each the reduction is to ensure that the prices are “well-
behaved” [23]. In particular, we will show that ratio of prices for any two
bads is bounded above by two. The agents of $N_{PR}$ are constructed mainly
for this task. Recall that the price of all bads are negative an equilibrium.

######  Lemma 31.

For any $j,k\in M$, $\frac{p^{*}_{j}}{p^{*}_{k}}\leq 2$.

To prove the above claim, first we need to understand consumption of $N_{R}$
and $N_{C}$ agents on the first segments of their cost functions. If the
function $u_{ij}$ is non-linear then let $x_{ijk}$ denote the amount agent $i$
is assigned of bad $j$ on segment $k$.

######  Claim 6.

For any $s\neq s^{\prime}\in[n]$, let $i=a_{(s,s^{\prime},R)}$ and
$i^{\prime}=a_{(s^{\prime},s,R)}$. Then for every bad $j\in[m-1]$,
$W_{ij}+W_{i^{\prime}j}\geq x^{*}_{ij1}+x^{*}_{i^{\prime}j1}$. Similarly, for
$i=a_{(s,s^{\prime},C)}$ and $i^{\prime}=a_{(s^{\prime},s,C)}$.

###### Proof.

The claims follow from the construction of $N_{R}$ and $N_{C}$ respectively.
Note that, allocation on the first segment can not be more than its length.
Therefore, $x^{*}_{is1}\leq 1/n^{4}=W_{i,s}$ and for the remaining $j\in[n]$
both $x^{*}_{ij1}$ and $W_{ij}$ are zero. Similarly,
$x^{*}_{i^{\prime},s^{\prime},1}\leq 1/n^{4}=W_{i^{\prime},s^{\prime}}$ and
$x^{*}_{i^{\prime}j}=W_{i^{\prime}j}=0$ for $j\in[n],j\neq s^{\prime}$. For
$j\in\\{n+1,\dots,2n\\}$, we have
$x^{*}_{ij1}\leq(-r_{j-n})^{+}/n^{6}=W_{i^{\prime}j}$ and
$x^{*}_{i^{\prime}j1}\leq(r_{j-n})^{+}/n^{6}=W_{ij}$, where
$r_{k}=(R_{s^{\prime}k}-R_{sk})$. Similarly for $j=(m-1)$,
$x^{*}_{ij1}\leq(\sum_{k\in[n]}r_{k})^{+}/n^{6}=W_{i^{\prime}j}$, and
$x^{*}_{i^{\prime}j1}\leq(-\sum_{k\in[n]}r_{k})^{+}/n^{6}=W_{ij}$. The proof
for $i=(s,s^{\prime},C)$ and $i^{\prime}=(s^{\prime},s,C)$ follows similarly.
∎

The main intuition behind the proof of Lemma 31 is that if the maximum to
minimum price ratio is more than $2$, then $N_{PR}$ will leave out a $1/n$
amount of the minimum price bad to be consumed by the remaining agents. And
among the remaining agents, if they have to consume this bad at high-slope
segment (with disutility $H$) then they would prefer maximum priced bad
instead. Claim to consume the mm 6 will come handy in if agents outside
$N_{PR}$ have to consume the $1/n$ amount any bad from $[(m-1)]$ then they
“have to” consume it on the high-slope segment.

Proof of Lemma 31. Let $b^{\prime}\in{\operatorname{\mathrm{arg\,max}}}_{j\in
B}\ p^{*}_{j}$, and $b\in{\operatorname{\mathrm{arg\,min}}}_{j\in B}\
p^{*}_{j}$. Due to scale invariance of equilibria, we may assume without loss
of generality that $p^{*}_{b}=1$.

Assume for contradiction that $p_{b^{\prime}}>2p_{b}$. Note that
$W_{b}(N_{PR})=\frac{(m-1)}{n}$. In $N_{PR}$ all agents except of type $(b,j)$
and $(j,b)$ have slope $H$ for bad $b$, $\forall j\in M,\ j\neq b$. All of
these agents will strictly prefer bad $b^{\prime}$ over bad $b$, as it has
lower pain per buck. Agents of type $(j,b)$ have cost $1$ for $j$ and $2$ for
bad $b$, and therefore will strictly prefer to consume $j$ over bad $b$. Agent
$(b,b^{\prime})$ has cost $1$ for $b$ and $2$ for $b^{\prime}$ but still
strictly prefers $b^{\prime}$ since
$\frac{p^{*}_{b^{\prime}}}{p^{*}_{b}}>2\Rightarrow\frac{1}{p^{*}_{b}}>\frac{2}{p^{*}_{b^{\prime}}}$.
The remaining agents $(b,j)$ for $j\neq b,b^{\prime}$, they bring $1/n$ units
of $b$ and can consume only as much. Therefore $x^{*}_{b}(N_{PR})\leq(m-2)/n$.
Due to (19), $N\setminus N_{PR}$ has to consume $(1/n-1/n^{8})$ amount of bad
$b$. We consider two cases: $b\in[m-1]$, or $b=m$.

Case I: $b\in[m-1]$. Any agent $a_{j}\in N_{D}$, other than $a_{b}$, strictly
prefers bad $b^{\prime}$ over $b$ since it provides lower pain per buck. Also,
agent $a_{b}$ can only buy $p^{*}_{(m-1)}/n^{8}$ amount of $b$. Observe that
$p^{*}_{(m-1)}\leq p^{*}_{b^{\prime}}\leq 3H$. Indeed, if
$p^{*}_{b^{\prime}}>3H$, then all agents strictly prefer bad $b^{\prime}$ over
any segment of $b$ and the setting cannot clear, even approximately. Thus,
$x_{b}(N_{D})\leq O(H/n^{8})$, which leaves the remaining $O(1/n-H/n^{8})$ of
bad $b$ to be purchased by the agents of $N_{R}\cup N_{C}$.

By Claim 6, $x^{*}_{b}(N_{R}\cup N_{C})\leq w_{b}(N_{R}\cup
N_{C})=O(1/n^{3})$. Therefore, the agents of $N_{R}\cup N_{C}$ must consume
$b$ at a disutility of $H$. However, in that case they prefer $b^{\prime}$
over $b$, and the setting cannot clear, even approximately.

Case II: $b=m$. First, note that none of the agents of $N_{D}$ will consume
$b=m$ since they strictly prefer $b^{\prime}$. Thus, all demand for $m$
outside of $N_{PR}$ comes from $N_{R}\cup N_{C}$.

Observe, all agents of $N_{C}$ and $N_{R}$ must consume the bads
$\\{1,\dots,(m-1)\\}$ on their first segments with disutility 1/3, before
consuming any of bad $m$ with disutility $3$. Consider agent $i=a_{(s,t,R)}\in
N_{R}$. Her total earnings are

$\sum_{j\in
M}W_{ij}p^{*}_{j}=\frac{p^{*}_{s}}{n^{4}}+\frac{1}{n^{6}}\sum_{k\in[n]}(R_{tk}-R_{sk})^{+}p^{*}_{(n+k)}+\frac{1}{n^{6}}(\sum_{k\in[n]}R_{sk}-R_{tk})^{+}p^{*}_{(m-1)}.$
(20)

The total cost of her first segments of bads $\\{(n+1),\dots,(m-1)\\}$ is

$\frac{1}{n^{6}}\sum_{k\in[n]}(R_{sk}-R_{tk})^{+}p^{*}_{(n+k)}+\frac{1}{n^{6}}(\sum_{k\in[n]}R_{tk}-R_{sk})^{+}p^{*}_{(m-1)}.$
(21)

After purchasing her first segments of $\\{(n+1),\dots,(m-1)\\}$, her
remaining money which can be used to purchase bad $m$ is

$\displaystyle\frac{p^{*}_{s}}{n^{4}}$
$\displaystyle+\frac{1}{n^{6}}\sum_{k\in[n]}(R_{tk}-R_{sk})^{+}p^{*}_{(n+k)}+\frac{1}{n^{6}}(\sum_{k\in[n]}R_{sk}-R_{tk})^{+}p^{*}_{(m-1)}$
$\displaystyle-\bigg{(}\frac{1}{n^{6}}\sum_{k\in[n]}(R_{sk}-R_{tk})^{+}p^{*}_{(n+k)}+\frac{1}{n^{6}}(\sum_{k\in[n]}R_{tk}-R_{sk})^{+}p^{*}_{(m-1)}\bigg{)}$
$\displaystyle=\frac{p^{*}_{s}}{n^{4}}+\frac{1}{n^{6}}\left[(\sum_{k\in[n]}R_{sk}-R_{tk})p^{*}_{(m-1)}-\sum_{k\in[n]}(R_{sk}-R_{tk})p^{*}_{(n+k)}\right]$
$\displaystyle=\frac{p^{*}_{s}}{n^{4}}+\frac{1}{n^{6}}\left[\sum_{k\in[n]}(R_{sk}-R_{tk})(p^{*}_{(m-1)}-p^{*}_{(n+k)})\right].$
(22)

Now consider the agent $i^{\prime}=a_{(t,s,R)}\in N_{R}$ paired with $i$. By
the same argument, after purchasing the first segments of bads
$\\{(n+1),\dots,(m-1)\\}$, $i^{\prime}$ has the remaining money

$\frac{p^{*}_{t}}{n^{4}}+\frac{1}{n^{6}}\left[\sum_{k\in[n]}(R_{tk}-R_{sk})(p^{*}_{(m-1)}-p^{*}_{(n+k)})\right].$

Then the total money $i$ and $i^{\prime}$ can spend on $m$ is
$(p^{*}_{s}+p^{*}_{t})/n^{4}=O(H/n^{4})$, since $p^{*}_{b^{\prime}}<O(H)$. A
similar argument shows that for any pair
$i=a_{(s,t,C)},i^{\prime}=a_{(t,s,C)}$ in $N_{C}$, after spending on their
first segments of bads $\\{1,\dots,n\\}$, their remaining money to spend on
$m$ is at most $O(H/n^{4})$. Summing over all pairs $i$ and $i^{\prime}$ shows
that the total amount the agents of $N_{R}\cup N_{C}$ can spend on $m$ is
$O(H/n^{2})<(1/n-1/n^{8})$, for $n$ sufficiently large. Then setting cannot
clear, even approximately.∎

Let us set $H=10$. Scale $p^{*}$ so that the minimum price is $1$. Then using
Lemma 31 we have that $p^{*}\in[1,2]^{m}$. Define $u_{s}=2-p^{*}_{s}$ and
$v_{i}=2-p^{*}_{(n+s)}$ for all $s\in[n]$. Note that,
$\mbox{\boldmath$u$},\mbox{\boldmath$v$}\in[0,1]^{n}$ but they need not be
probability distributions. We will show Nash equilibrium conditions (17) for
$(\mbox{\boldmath$u$},\mbox{\boldmath$v$})$ first.

######  Lemma 32.

For any $s,t\in[n]$ if
$(R\mbox{\boldmath$v$})_{s}-(R\mbox{\boldmath$v$})_{t}<-1/n$ then $u_{s}=0$,
and if $(\mbox{\boldmath$u$}^{T}C)_{s}-(\mbox{\boldmath$u$}^{T}C)_{t}<-1/n$
then $v_{s}=0$.

To show the above lemma, we will first make a couple of simple observations.
Define agent set ${\overline{N_{PR}}}=N\setminus N_{PR}$ to be everyone
outside $N_{PR}$. In order to get $u_{s}=0$ we need to force $p^{*}_{s}=2$.
Next, we show that if ${\overline{N_{PR}}}$ leave leave a large enough amount
of bad $s$ to be consumed by $N_{PR}$ then it must be that $p^{*}_{s}=2$.

######  Observation 33.

No agent consumes any bad at cost $H$.

###### Proof.

Note that for every agent $i$ there is at least one bad $j$ such that the cost
function $f_{ij}$ is linear with slope at most $3$. Given that $H=10$ and
$10/3>2$, the claim follows using Lemma 31. ∎

######  Observation 34.

For any bad $b\in M$, $(i)$
$W_{b}({\overline{N_{PR}}})-x^{*}_{b}({\overline{N_{PR}}})\geq
1/n^{8}\Rightarrow p^{*}_{b}=2$, and $(ii)$
$W_{b}({\overline{N_{PR}}})-x^{*}_{b}({\overline{N_{PR}}})\leq-1/n^{8}\Rightarrow
p^{*}_{b}=1$

###### Proof.

If $W_{b}({\overline{N_{PR}}})-x^{*}_{b}({\overline{N_{PR}}})\geq 1/n^{8}$,
then the supply-demand condition (18) requires that
$W_{b}(N_{PR})-x^{*}_{b}(N_{PR})<0$. Recall that, for any agent
$(j,j^{\prime})\in N_{PR}$ the cost for bad $j$ is $1$, that of bad
$j^{\prime}$ is $2$, and $H$ for all other bads. At equilibrium she only
purchases bads that minimizes cost/price. Therefore, if $p^{*}_{b}<2$ then
from $N_{PR}$, only the agents $(b,j^{\prime}),\ \forall j^{\prime}\neq b$ are
willing to consume bad $b$. Each of them brings exactly $1/n$ amount of bad
$b$ and can consume only what they bring, which contradicts
$W_{j}(N_{PR})-x^{*}_{j}(N_{PR})<0$. Instead, if $p^{*}_{b}=2$, then agents of
type $(j^{\prime},b)$ may also be able to consume bad $b$.

Now suppose
$W_{b}({\overline{N_{PR}}})-x^{*}_{b}({\overline{N_{PR}}})<-1/n^{8}$, then the
supply-demand condition (18) requires that
$W_{b}(N_{PR})-x^{*}_{b}(N_{PR})>0$. Notice that agents $(b,j)$, $\forall
j\neq b$ of bring all the of the bad $b$ from $N_{PR}$. Moreover, these agents
strictly prefer $b$ over $j$ when $p^{*}_{b}>1$, since all $p^{*}_{j}\in[1,2]$
by Lemma 31 (given that the minimum price is 1). Therefore
$W_{b}(N_{PR})-x^{*}_{b}(N_{PR})\leq 0$, which contradicts approximate supply-
demand. ∎

######  Observation 35.

$p^{*}_{(m-1)}=2$.

###### Proof.

Claim 6 together with Observation 33 implies that $W_{(m-1)}(N_{R}\cup
N_{C})\geq x^{*}_{(m-1)}(N_{R}\cup N_{C})$. And from Observation 33 we also
know that $x^{*}_{(m-1)}(N_{D})=0$ while $W_{(m-1)}(N_{D})=2n/n^{8}>1/n^{7}$.
Both of these together gives,
$W_{(m-1)}({\overline{N_{PR}}})-x^{*}_{(m-1)}({\overline{N_{PR}}})>1/n^{7}$
and then Observation 34 implies $p^{*}_{(m-1)}=2$. ∎

Using Observation 33 next we show a stronger version of Claim 6.

######  Observation 36.

For any $s\neq s^{\prime}\in[n]$, let $i=a_{(s,s^{\prime},R)}$ and
$i^{\prime}=a_{(s^{\prime},s,R)}$. Then for every bad $j\in[m-1]$,
$W_{ij}+W_{i^{\prime}j}\geq x^{*}_{i,j}+x^{*}_{i^{\prime},j}$, and the
condition holds with equality for $j\in\\{(n+1),\dots,(m-1)\\}$. Similarly,
for $i=a_{(s,s^{\prime},C)}$ and $i^{\prime}=a_{(s^{\prime},s,C)}$ where the
equality holds for $j\in[n]\cup\\{(m-1)\\}$.

###### Proof.

The inequality follows using the fact that no agent consumes any bad at cost
$H$ by Observation 33. To show equality for $j>n$ when
$i=a_{(s,s^{\prime},R)}$ and $i^{\prime}=a_{(s^{\prime},s,R)}$, we only need
to make sure that $i$ and $i^{\prime}$ consumes the first segment of bad $j$
completely.

For agent $i$, recall that the cost of any $j\in\\{(n+1),\dots,(m-1)\\}$ on
the first segment is $1/3$, compared to that the next lowest cost of $1$ (on
the first segment of bad $s$). Since price ratios of any two bads is not more
than $2$, she prefers to buy all the segments with cost $1/3$ first. To
consume all of them she needs money of,

$\frac{1}{n^{6}}\sum_{k\in[n]}(R_{sk}-R_{tk})^{+}p^{*}_{(n+k)}+\frac{1}{n^{6}}(\sum_{k\in[n]}R_{tk}-R_{sk})^{+}p^{*}_{(m-1)}\leq\frac{4n}{n^{6}}$

The above inequality follows from the fact that $R\in[0,1]^{n\times n}$ and
every price is at most $2$ (given that the minimum price is $1$). Her
endowment of $1/n^{4}$ amount of bad $s$ earns her at least $1/n^{4}$ units of
money, which is enough to buy the above bundle. Similar argument follows for
agent $i^{\prime}$.

The case for for $i=a_{(s,s^{\prime},C)}$ and
$i^{\prime}=a_{(s^{\prime},s,C)}$ follows similarly. ∎

Now to prove Lemma 32 we only need to show that agents of set
${\overline{N_{PR}}}$ leave at least $1/n^{8}$ amount of bad $s$ to be
consumed by $N_{PR}$. We will crucially use the above observations for the
same.

Proof of Lemma 32. Let $i=a_{(s,t,R)}\in N_{R}$. The total earning of $i$ is
given by (20). Given that price ratio of any two bads is bounded above by $2$
(Lemma 31), agent $i$ will first buy the first segments of bads
$\\{(n+1),\dots,(m-1)\\}$, then the first segment of bad $s$, and then consume
bad $m$ if any money left. By Observation 36, agent $i$ spends exactly (21) on
the bads $\\{(n+1),\dots,(m-1)\\}$.

The left over money after the above spending is given by (22)

$\begin{array}[]{l}\ \ \
\frac{p^{*}_{s}}{n^{4}}+\frac{1}{n^{6}}\left[\sum_{k\in[n]}(R_{sk}-R_{tk})(p^{*}_{(m-1)}-p^{*}_{(n+k)})\right]\\\\[10.0pt]
\ \ \
=\frac{p^{*}_{s}}{n^{4}}+\frac{1}{n^{6}}\sum_{k\in[n]}(R_{sk}-R_{tk})v_{k}\\\\[10.0pt]
\ \ \
=\frac{p^{*}_{s}}{n^{4}}+\frac{1}{n^{6}}\big{[}(R\mbox{\boldmath$v$})_{s}-(R\mbox{\boldmath$v$})_{t}\big{]}\\\\[10.0pt]
\ \ \ <\frac{p^{*}_{s}}{n^{4}}-\frac{1}{n^{7}}\leq
p^{*}_{s}\left(\frac{1}{n^{4}}-\frac{1}{2n^{7}}\right)\\\ \end{array}$

The last inequality above follows from $p^{*}_{s}\leq
2\Rightarrow-1/p^{*}_{s}\leq-1/2$. Thus, agent $i$ can only consume at most
$\left(\frac{1}{n^{4}}-\frac{1}{2n^{7}}\right)$ amount of bad $s$ from the
$1/n^{4}$ units that she brings. By Observation 36, agents of $N_{R}$ and
$N_{C}$ are unable to consume any of the remaining $\frac{1}{2n^{7}}$ amount
of $s$. Among the agents of $N_{D}$ only agent $a_{s}$ can consume $s$, but
only up to the amount of
$\frac{p^{*}_{(m-1)}}{n^{8}p^{*}_{s}}\leq\frac{2}{n^{8}}$. Thus,
$W_{s}({\overline{N_{PR}}})-x_{s}^{*}({\overline{N_{PR}}})\geq\frac{1}{2n^{7}}-\frac{2}{n^{8}}>\frac{1}{n^{8}}$,
and then using Observation 34 it follows that $p^{*}_{s}=2$. This in turn
implies $u_{s}=2-p^{*}_{s}=0$.

The second part of the lemma follows similarly. ∎

######  Observation 37.

Let
$s\in{\operatorname{\mathrm{arg\,max}}}_{k\in[n]}(R\mbox{\boldmath$v$})_{k}$,
then $p^{*}_{s}=1$. Similarly, for
$s\in{\operatorname{\mathrm{arg\,max}}}_{k\in[n]}(\mbox{\boldmath$u$}C)_{k}$,
$p^{*}_{(n+s)}=1$.

###### Proof.

As observed in the proof of Lemma 32, for all $t\in[n],t\neq s$, the
corresponding agent $i=a_{(s,t,R)}\in N_{R}$, the total earning minus spending
on the segments with slope $1/3$ is,

$\frac{p^{*}_{s}}{n^{4}}+\frac{1}{n^{6}}\big{[}(R\mbox{\boldmath$v$})_{s}-(R\mbox{\boldmath$v$})_{t}\big{]}\geq\frac{p^{*}_{s}}{n^{4}},$

since $(R\mbox{\boldmath$v$})_{s}-(R\mbox{\boldmath$v$})_{t}\geq 0$.
Therefore, $i$ will consume all of the bad $s$ that she brings, i.e.,
$1/n^{4}$ amount. By Observation 36 remaining agents of $N_{R}$ and $N_{C}$
together will consume all of $s$ that they bring to the setting. Among
$N_{D}$, the agent $a_{s}$ brings $1/n^{8}$ units of $(m-1)$ and wants to
consume only bad $s$. Price of $2$ for bad $(m-1)$ (Obs. 35), gives earning of
$2/n^{8}$ to agent $a_{s}$. Since price of $s$ can be at most $2$ (by Lemma 31
assuming the minimum price is 1), she will demand at least $1/n^{8}$ units of
bad $s$. Putting supply and demand of all the agents in ${\overline{N_{PR}}}$
together we get,

$W_{s}({\overline{N_{PR}}})-x_{s}^{*}({\overline{N_{PR}}})\leq-1/n^{8}$

From the above inequality, Observation 34 gives us $p^{*}_{s}=1$. The second
part follows similarly. ∎

The above observation ensures that vectors $u$ and $v$ are not zero vectors.
Using this together with Lemma 32 we will show the main theorem next.

Proof of Theorem 30 Given an equilibrium $(p^{*},x^{*})$ of setting
$\mathcal{M}(R,C)$ construct vectors $u$ and $v$ as defined above,

$\forall s\in[n],\ \ u_{s}=2-p_{s}^{*},\ \ \mbox{ and }v_{s}=2-p_{(n+s)}^{*}$

Observation 37 ensures that
$\mbox{\boldmath$u$},\mbox{\boldmath$v$}\neq\mbox{\boldmath$0$}$. Construct
strategy vectors

$\boldsymbol{\alpha}=\frac{\mbox{\boldmath$u$}}{\sum_{s\in[n]}u_{s}},\ \ \
\mbox{ and }\ \ \
\boldsymbol{\beta}=\frac{\mbox{\boldmath$v$}}{\sum_{s\in[n]}v_{s}}$

We will show that $(\boldsymbol{\alpha},\boldsymbol{\beta})$ satisfies Nash
equilibrium conditions (17) for $\epsilon=1/n$. For any pair of strategies
$s,t\in[n]$

$\begin{array}[]{lcl}(R\boldsymbol{\beta})_{s}-(R\boldsymbol{\beta})_{t}<-1/n&\Rightarrow&(\sum_{s\in[n]}v_{s})^{-1}((R\mbox{\boldmath$v$})_{s}-(R\mbox{\boldmath$v$})_{t})<-1/n\\\
&\Rightarrow&((R\mbox{\boldmath$v$})_{s}-(R\mbox{\boldmath$v$})_{t})<-1/n\ \ \
\ (\because(\sum_{s\in[n]}v_{s})\geq 1\mbox{ using Obs. \ref{ob.5}})\\\
&\Rightarrow&p^{*}_{s}=2\ \ \ \ (\because\mbox{ Lemma \ref{lem:ne-cond}})\\\
&\Rightarrow&u_{s}=0\ \ \ \ (\because u_{s}=2-p^{*}_{s})\\\
&\Rightarrow&\alpha_{s}=0\ \ \ \ (\because u_{s}=2-p^{*}_{s})\end{array}$

By the similar argument as above we can show that for any pair $s,t\in[n]$ if
$(\boldsymbol{\alpha}^{T}C)_{s}-(\boldsymbol{\alpha}^{T}C)_{t}<-1/n$ then
$v_{s}=0$. ∎

Proof of Theorem 28. Clearly, our construction is polynomial (in number of
agents and bads) with respect to the input size of the 2-player game $(R,C)$.
Theorem 30 shows that a $1/m^{8}$-approximate exchange setting equilibrium
yields a $1/n$-approximate well-supported NE of $(R,C)$. Moreover, this
conversion from exchange equilibrium to NE runs in polynomial time. As finding
a $1/n$-approximate well-supported NE is ${\sf PPAD}$-hard, it follows that
finding a $1/poly(n)$-approximate exchange equilibrium is ${\sf PPAD}$-hard. ∎

Proof of Theorem 29. We will show how to convert our exchange setting
construction into a Fisher setting with equal budgets in a way such that the
equilibria of the two settings are in one-to-one correspondence. Moreover, a
$O(\epsilon/n)$ approximate equilibrium in the Fisher setting is a
$O(\epsilon)$ approximate equilibrium in the exchange setting. Both the
reduction from exchange to Fisher setting, and conversion of Fisher to
exchange equilibrium take polynomial time which establishes the ${\sf
PPAD}$-hardness of the Fisher case. We use the notation
$(\mbox{\boldmath$w$},\mbox{\boldmath$x$},\mbox{\boldmath$p$})$ and
$(\tilde{\mbox{\boldmath$w$}},\tilde{\mbox{\boldmath$x$}},\tilde{\mbox{\boldmath$p$}})$
to denote endowments, allocations, and prices in the exchange and Fisher
settings respectively.

First we show how to convert our exchange setting construction into a Fisher
setting. We ensure equal budgets by giving each agent an equal amount of each
bad. Recall in the construction of the exchange setting, the agents of
$N_{PR}$ bring the largest amount of each bad $j\in[m]$, specifically a $1/n$
amount. In the Fisher setting, we give each agent a $\tilde{W}_{ij}=1/n$
amount of each bad $j$, by increasing $i$’s initial endowment of each bad $j$
by $1/n-W_{ij}$. As all agents bring the same amount of each bad, the new
instance is a Fisher setting with equal budgets.

Next, we want to ensure a one-to-one correspondence between the equilibria of
the two settings. For each agent $i$ and bad $j$ we add an extra segment to
$f_{ij}$ with disutility $\tilde{d}_{ij1}=0$ and length
$\tilde{L}_{ij1}=1/n-W_{ij}$, the additional amount of bad $j$ given to agent
$i$. Note that this new segment becomes the first segment of $f_{ij}$, and
‘shifts’ all other segments to the right. Moreover, for any set of prices $p$,
these newly created first segments are: optimal purchases since they have 0
disutility, and can be fully purchased since the cost
$\tilde{L}_{ij1}p_{j}=(1/n-W_{ij})p_{j}$ is exactly equal to extra money $i$
earns from bad $j$ in the Fisher setting. Thus, after purchasing all the new
first segments, $i$ is left with a remaining budget of $\sum_{j\in
M}\tilde{W}_{ij}p_{j}-\sum_{j\in B}\tilde{L}_{ij1}p_{j}=\sum_{j\in
M}W_{ij}p_{j}$, i.e., her budget in the exchange setting. Finally, since we
shift all remaining segments of $f_{ij}$ to the right, it is easy to check
that $i$’s forced, flexible, and undesirable segments are the same (up to the
newly added first segments) in both the exchange and Fisher settings for any
prices $p$. Thus, if $x_{i}=(x_{ij})_{j\in M}$ is an affordable and optimal
bundle in the exchange setting, then $\tilde{x}_{i}=(L_{ij1}+x_{ij})_{j\in M}$
is an affordable and optimal bundle in the Fisher setting. It follows that the
set of equilibria of the two settings are in one-to-one correspondence.

Finally, we show that if
$(\tilde{\mbox{\boldmath$x$}}^{*},\tilde{\mbox{\boldmath$p$}}^{*})$ is an
$\epsilon/(6n)$ approximate equilibrium of the Fisher setting, then
$(\mbox{\boldmath$x$}^{*},\mbox{\boldmath$p$}^{*})$ is an $\epsilon$
approximate equilibrium of the exchange setting where

$x_{ij}^{*}=\tilde{x}_{ij}^{*}-\tilde{L}_{ij1},\quad
p_{j}^{*}=\tilde{p}_{j}^{*},\ \forall i,j.$ (23)

As previously argued, if $\tilde{x}_{i}^{*}$ is an affordable and optimal
bundle for the Fisher setting, then $x_{i}^{*}$ is an affordable and optimal
bundle for the exchange setting. Thus, if condition C1 holds for
$(\tilde{\mbox{\boldmath$x$}}^{*},\tilde{\mbox{\boldmath$p$}}^{*})$, then it
holds for $(\mbox{\boldmath$x$}^{*},\mbox{\boldmath$p$}^{*})$. It remains to
check condition C2’. Observe, that there are

$|N|=2\frac{m(m-1)}{2}+2n+2\frac{n(n-1)}{2}+2\frac{n(n-1)}{2}=6n^{2}+6n+2$

agents used in the construction, and $\tilde{W}_{ij}=1/n$ for all $i,j$. Thus,
$\sum_{i\in N}\tilde{W}_{ij}=6n+6+2/n<6n+7$, for all $j\in M$. By (23),
$|\sum_{i\in N}(\tilde{W}_{ij}-\tilde{x}_{ij}^{*})|=|\sum_{i\in
N}(W_{ij}-x_{ij}^{*})|$, since $\tilde{L}_{ij1}=1/n-W_{ij}$. Therefore, if
$(\tilde{\mbox{\boldmath$x$}^{*}},\tilde{\mbox{\boldmath$p$}^{*}})$ is
$\epsilon/(6n)$ approximate equilibrium of the Fisher setting, then

$|\sum_{i\in N}(W_{ij}-x_{ij}^{*})|=|\sum_{i\in
N}(\tilde{W}_{ij}-\tilde{x}_{ij}^{*})|\leq\frac{\epsilon}{6n}\sum_{i\in
N}\tilde{W}_{ij}\leq\epsilon(1+7/(6n))<3\epsilon,\ \forall j\in M,$ (24)

so that $(\mbox{\boldmath$x$}^{*},\mbox{\boldmath$p$}^{*})$ is an $\epsilon$
approximate equilibrium for the exchange setting by (18).

It follows that computing a Fisher setting equilibrium (with equal budgets) is
${\sf PPAD}$-hard, since both the reduction from exchange to Fisher setting,
and the conversion from Fisher to exchange equilibrium take polynomial time
(and space). ∎

##  8 Numerical Experiments

Table 1 summarizes the results of numerical experiments conducted on randomly
generated trials using a Matlab implementation of our algorithm. Note that we
used the same number of segments, shown as #Seg in the table, for each agent
and each item. We drew the $U_{ijk}$’s, $L_{ijk}$’s, and $W_{ij}$’s uniformly
at random from the intervals $[-1,0]$, $[0,1/\\#\text{Seg}]$ , and $[0,1]$
respectively. Then, we rescaled the $W_{ij}$ values to ensure a unit amount of
each bad. Finally, for each agent $i$ and each bad $j$, we sorted the
$U_{ijk}$’s decreasing order to generate an SPLC utilities.

$N\times M\times$ #Seg | Instances | Min iters | Mean iters | Max iters
---|---|---|---|---
$5\times 5\times 5$ | 1000 | 85 | 137.3 | 297
$10\times 5\times 5$ | 1000 | 107 | 170.9 | 395
$10\times 10\times 5$ | 1000 | 130 | 369.1 | 609
$15\times 15\times 5$ | 50 | 168 | 750.3 | 1393
$20\times 20\times 5$ | 10 | 1127 | 1398.2 | 2001
Table 1: Experimental results conducted on random instances. Figure 2: Plot of
$N\times M\times$ #Seg versus maximum number of iterations.

Figure 2 compares the maximum number of iterations versus the total number of
segments in the agent’s utility functions, i.e., $N\times M\times$ #Seg
$=\sum_{i,j}|u_{ij}|$. Note that even in the worst case, the maximum number of
iterations is on the order of the total number of segments of the agents’
utility functions.

##  Appendix A Converting Bads into Goods?

Bogomolnaia et al. [14] propose a method to convert a competitive division
problem with bads into a problem with only goods. Note that their argument
only applies to the Fisher setting and uses linear utility functions. The
approach relies on the interpretation of leisure as the opposite of work.
Therefore, if agent $i$ is assigned an $x_{ij}$ fraction of bad $j$, then we
can equivalently view this as a good representing an exemption from completing
a $1-x_{ij}$ fraction of the task.

The reduction from bads to goods proposed by [14] is as follows. Assume there
are $n$ agents in the competitive division problem. For each bad $j$, we
create $n-1$ units of a good $j^{\prime}$ representing an exemption from
completing bad $j$. Suppose agent $i$ has utility $D_{ij}<0$ for bad $j$, then
$i$’s utility for good $j^{\prime}$ is SPLC with two segments. The first
segment has slope $|D_{ij}|>0$ and length $L_{ij}=1$, and the second segment
has slope 0. Note that this means $i$ values up to 1 unit of exemption to the
bad $j$.

Bogomolnaia et al. [14] state that given an equilibrium
$(\mbox{\boldmath$x$}^{\prime},\mbox{\boldmath$p$}^{\prime})$ in the problem
of goods, one can obtain an equilibrium in bads by setting
$p_{j}^{*}=-p_{j}^{\prime}$, and $x_{ij}^{*}=1-x_{ij}^{\prime}$.

Counter Example: Consider a competitive division problem with two agents $a$
and $b$, and three bads 1, 2, and 3. The agents’ utility functions are:
$u_{a}(x)=-10x_{a1}-2x_{a2}-x_{a3}$, and
$u_{b}(x)=-x_{a1}-100x_{a2}-100x_{a3}$. We create 1 unit of exemption for each
bad. The utility functions for agent $a$ are SPLC where the first segment has
slope $(10,2,1)$ for goods 1, 2, and 3 respectively, and are capped at 1 unit
of good. One can verify that the prices
$\mbox{\boldmath$p$}^{\prime}=(4/3,1/3,1/3)$, and the allocations
$x_{a}^{\prime}=(3/4,0,0)$ and $x_{b}=(1/4,1,1)^{\prime}$ are an equilibrium
in goods. In bads, this becomes $\mbox{\boldmath$p$}^{*}=(-4/3,-1/3,-1/3)$,
with the allocation $x_{a}^{*}=(1/4,1,1)$ and $x_{b}^{*}=(3/4,0,0)$. However,
this is not a competitive equilibrium since $a$ does not receive the same
$pbp$ for all bads. One can check that the prices
$\mbox{\boldmath$p$}^{*}=(-20/13,-4/13,-2/13)$, along with the allocation
$x_{a}^{*}=(7/20,4/13,2/13)$ and $x_{b}^{*}=(13/20,0,0)$ give an equilibrium.

##  Appendix B Approach of [38, 46] Gets Stuck on Secondary-Rays

Previous works of Eaves [38] and Garg et al. [46] developed complementary
pivot algorithms based on Lemke’s scheme for all goods under SPLC utilities.
The basic structure of our LCP is similar to prior works. However, they use a
different change of variables. Both [38, 46] use a _lower bound_ on prices by
making the price of good $j$: $1+p_{j}$, where $p_{j}\geq 0$. Thus, the
_minimum_ price is 1 (in absolute value). In addition, [38, 46] make no
changes to the variable $r_{i}=1/ppb_{i}$, where $ppb_{i}$ is the pain per
buck of agent $i$’s flexible segment. In this section, we examine this change
of variables when applied to the special case of all bads with linear
utilities. The resulting formulation is as follows:

$\displaystyle\forall i\in N,\ \ \sum_{j\in M}W_{ij}p_{j}-\sum_{j\in
M}f_{ij}-\epsilon_{i}z\leq-\sum_{j\in M}W_{ij}$ $\displaystyle\perp r_{i}$
(25) $\displaystyle\forall j\in M,\ \ \sum_{i\in N}f_{ij}-p_{j}\leq 1$
$\displaystyle\perp p_{j}$ (26) $\displaystyle\forall i\in N,\ \forall j\in
M,\ \ \ p_{j}-D_{ij}r_{i}-\delta_{ij}z\leq-1$ $\displaystyle\perp f_{ij}$ (27)

The constraints have the same interpretation as before: a budget constraint
for all agents (25), a constraint on the total spending of agents for each bad
(26), and a minimum pain per buck constraint for each agent, for each bad
(27). Note that we add coefficients $\epsilon_{i}$, and $\delta_{ij}$ to $z$
for all terms with negative rhs for two purposes. First, this provides a
degree of control over the primary ray, i.e., the initial double label, and
therefore how the algorithm starts. Second, we require $\delta_{ij}$’s
coefficients to ensure nondegeneracy of LCP when $z>0$. To see this, suppose
$p_{j}=0$ for some $j\in M$, and $r_{i}=0,\ \forall i\in N$. Then by setting
$z=1$, the constraints (27) become tight (hold with equality) for this $j$,
$\forall i\in N$. Thus, there is no unique double label.

We now examine the behavior of Lemke’s algorithm when starting from a
constraint (25) or (27). We show that in both cases the algorithm quickly
reaches a secondary ray.

###  B.1 Starting from (25)

Suppose we select $\epsilon_{i}=1,\ \forall i\in N$, and ensure
$1/\delta_{ij}<\max_{k}\sum_{j}W_{kj}$. By setting $z=\max_{k}\sum_{j}W_{kj}$
and all other variables
$(\mbox{\boldmath$p$},\mbox{\boldmath$r$},\mbox{\boldmath$f$})=\mbox{\boldmath$0$}$,
we obtain a unique double label for constraint (25) for agent
$a=\arg\max_{k}\sum_{j}W_{kj}$. Specifically, all constraints (27) hold with
strict inequality.

Lemke’s algorithm then fixes $z=\max_{k}\sum_{j}W_{kj}=\sum_{j}W_{aj}$, and
increases $r_{a}$. Observe that $r_{a}$ only appears in the constraints (27).
However, since $\delta_{aj}z>1$, and $D_{aj}>0,\ \forall j\in M$, increasing
$r_{a}$ never makes any inequality (27) tight for any $j\in M$. That is, we
arrived at secondary ray. Notice that the same problem arises regardless of
which budget constraint (25) we start from (assuming appropriate choice of
$\epsilon_{i}$’s and $\delta_{ij}$’s). Therefore, starting from a budget
constraint (25) _always_ leads to a secondary ray.

###  B.2 Starting from (27)

Suppose we fix $\epsilon_{i}=1,\ \forall i\in N$, and $\delta_{ij}$’s such
that $\max_{k}\sum_{j}W_{kj}<\max_{ij}1/\delta_{ij}$. Then, setting
$z=\max_{ij}1/\delta_{ij}$ and all other variables
$(\mbox{\boldmath$p$},\mbox{\boldmath$r$},\mbox{\boldmath$f$})=\mbox{\boldmath$0$}$,
yields the unique double label at constraint (27) for the pair
$(a,b)=\arg\min_{ij}\delta_{ij}$, i.e., the agent $a\in N$ and bad $b\in M$
that achieve $\max_{ij}1/\delta_{ij}$. Further, all constraints (25) hold with
strict inequality.

Lemke’s algorithm fixes $z=1/\delta_{ab}$, and increases $f_{ab}$ until some
other inequality becomes tight. Note that (25) can not become tight due to our
choice of $z$. Then, (26) becomes tight for bad $b$. At this point, we may
change $p_{j}$ subject to the following constraints

$\displaystyle f_{ab}$ $\displaystyle=1+p_{b}$ $\displaystyle 1+p_{b}$
$\displaystyle=\delta_{ab}z.$

We check whether a constraint of form (25) or (27) can become tight.

Starting from Pain per Buck Constraints (27). For any $i\neq a$, we would
require that (27) becomes tight while observing the relationship between
$f_{ab}$, $p_{b}$, and $z$ above. Thus, we need

$1+p_{b}=\delta_{ib}z=\frac{\delta_{ib}}{\delta_{ab}}(1+p_{b})>1+p_{b},$

since $\delta_{ab}=\min_{ij}\delta_{ij}$. Thus, no constraint of the form (26)
can become tight.

Budget Constraints (25). For any $i\in N$ (including $a$), we would require
that (25) becomes while maintaining the relationship between $f_{ab}$,
$p_{b}$, and $z$ above. Thus, for $i\neq a$ we need

$W_{ib}\ p_{b}+\sum_{j}W_{ij}=z=\frac{1+p_{b}}{\delta_{ab}},$

or after rearranging

$\underbrace{\Sigma_{j}W_{ij}-1/\delta_{ab}}_{<0}=\underbrace{\big{(}1/\delta_{ab}-W_{ib}\big{)}}_{>0}\
p_{b},$

where the inequalities of the coefficients follow from
$1/\delta_{ab}>\max_{k}\sum_{j}W_{kj}\geq W_{ib}$. However, no value of
$p_{b}\geq 0$ suffices. Similarly, if we want (25) to become tight for agent
$a$, then we need

$\underbrace{\Sigma_{j}W_{ij}-1/\delta_{ab}-1}_{<0}=\underbrace{\big{(}1/\delta_{ab}-W_{ib}+1\big{)}}_{>0}\
p_{b},$

and again no value of $p_{b}>0$ works.

Conclusion: The examples demonstrate that for this relationship between
$f_{ab}$, $p_{b}$, and $z$, no constraints can become tight, i.e., we have
reached a secondary ray.

##  Appendix C Omitted Proofs

###  C.1 Proof of Lemma 4

We will need the following lemma to prove the result.

######  Lemma 38.

If $\mbox{\boldmath$p$}^{*}$ is an equilibrium price vector, then $\exists\
\mbox{\boldmath$f$}$ such that (8a) and (8b) hold. Further, if $p$ and $f$
satisfy (8a) and (8b), and $\mbox{\boldmath$p$}>0$, then the market clears.

###### Proof.

Let $\mbox{\boldmath$p$}^{*}$ be an equilibrium price vector and set
$\mbox{\boldmath$p$}=|\mbox{\boldmath$p$}^{*}|$. Let $\mbox{\boldmath$x$}^{*}$
be the equilibrium allocation for $\mbox{\boldmath$p$}^{*}$. For each agent
$i$ and each bad $j$, we distribute $x_{ij}^{*}$ among individual segments by
filling starting from the first segment until all of $x_{ij}^{*}$ is used

$x_{ijk}^{*}=\min\bigg{(}\max\bigg{(}x_{ij}^{*}-\sum_{k^{\prime}<k}L_{ijk},\
0\bigg{)},\ L_{ijk}\bigg{)}.$ (28)

The market clearing conditions ensures that setting $f_{ijk}=x_{ijk}^{*}p_{j}$
together with $p$ satisfies (8a) and (8b).

Next, suppose $\mbox{\boldmath$p$},\mbox{\boldmath$f$}$ satisfy (8a) and (8b)
and $\mbox{\boldmath$p$}>\mbox{\boldmath$0$}$. Summing (8a) over all $i\in N$
and (8b) over all $j\in M$ gives

$\sum_{j}p_{j}=\sum_{i,j}W_{ij}p_{j}\leq\sum_{i,j,k}f_{ijk}\leq\sum_{j}p_{j},$

where the first equality uses the fact that there is a unit amount of each
bad, i.e., $\sum_{i}W_{ij}=1$, $\forall j\in M$. It follows from the non-
negativity of all variables that all constraints (8a) and (8b) hold with
equality. Therefore, setting $x_{ijk}=f_{ijk}/p_{j}$ ensures the market
clears. ∎

###### Proof.

(of Lemma 4) Let $(\mbox{\boldmath$x$}^{*},\mbox{\boldmath$p$}^{*})$ be a
competitive equilibrium. Define $p$ and $f$ as in Lemma 38, and set $r_{i}$
according to (9) for any segment $(i,j,k)$ of $i$’s flexible partition. Note
that $r_{i}>0$ since $0<D_{ij1}\leq D_{ij2}\leq\dots$ for all bads $j\in M$.
By Lemma 38, (8a) and (8b) hold with equality since
$(\mbox{\boldmath$x$}^{*},\mbox{\boldmath$p$}^{*})$ clears the market.
Therefore, so do (8a’) and (8b’).

We set the variables $s_{ijk}$ as follows: if $(i,j,k)$ is undesirable or
flexible set $s_{ijk}=0$, if $(i,j,k)$ is a forced segment set $s_{ijk}$ to
satisfy

$\frac{1}{r_{i}}=\frac{D_{ijk}}{p_{j}-s_{ijk}}\ \ \Rightarrow\ \
s_{ijk}=p_{j}-D_{ijk}r_{i}.$

Note that $s_{ijk}\geq 0$ since $D_{ijk}>0$ and
$D_{ijk}/p_{j}\leq\frac{1}{r_{i}}$ for forced segments. It can be easily
verified that in each case: the segment is forced, flexible, or undesirable;
the constraints (8c) and (8d), and corresponding complementarity conditions
(8c’) and (8d’) are satisfied. ∎

###  C.2 Proof of Theorem 5

We will need the following lemma to prove the theorem.

######  Lemma 39.

In any solution to LCP (10) with $p_{j}<P,\ \forall j\in M$, and $r_{i}<R,\
\forall i\in N$, agents receive an optimal bundle of bads.

###### Proof.

Recall that $D_{ijk}=|U_{ijk}|>0,\ \forall\ (i,j,k)$ since for each agent, her
utility for each bad is a concave, decreasing function, i.e., $0<D_{ij1}\leq
D_{ij2}\leq\dots$. Due to scale invariance of competitive equilibria, we may
pick any maximum price (in absolute value) $P$. Given the choice of $P$, we
selected $R$ such that $R>P/\min_{ijk}D_{ijk}$. This ensures $D_{ijk}R-P>0$,
$\forall(i,j,k)$, which makes the right hand side of (10c) positive for all
segments $(i,j,k)$. Notice this implies that $r_{i}>0,\ \forall\ i\in N$,
otherwise (10c) is a strict inequality. In turn, (10c’) forces $f_{ijk}=0,\
\forall\ (i,j,k)$. Then, for each $j\in M$, $p_{j}<P$ implies (10a) is strict
and therefore $p_{j}=0$ which will violate inequality (10b).

Let $(i,j,k)$ be a segment with highest $ppb$ that agent $i$ spends on in the
solution to LCP (10). Define $\sigma_{i}$ as the inverse of the pain per buck
of the this segment

$\sigma_{i}=\frac{P-p_{j}}{D_{ijk}}=\frac{1}{ppb_{ijk}}.$

Observe that $\sigma_{i}>0$, since $p_{j}<P$, and $D_{ijk}>0$, for all
segments of all bads.

We want to show that $(R-r_{i})\leq\sigma_{i}$. Since agent $i$ spends on the
segment $(i,j,k)$, i.e., $f_{ijk}>0$, complementarity condition (10c’)
requires constraint (10c) holds with equality. Since $s_{ijk}\geq 0$, this
yields

$D_{ijk}(R-r_{i})=P-p_{j}-s_{ijk}\leq P-p_{j}=D_{ijk}\sigma_{i}.$ (29)

Thus, $(R-r_{i})\leq\sigma_{i}$ since $D_{ijk}>0$.

Let $Q_{i}$ denote all segments of $i$’s utility function with
$ppb=1/\sigma_{i}$, and call this the flexible partition. Similarly, let the
forced partition be all segments with strictly lower $ppb$ than
$1/\sigma_{i}$, and the undesirable partition be all segments with strictly
higher $ppb$ than $1/\sigma_{i}$. We show that these segments correspond to
forced, flexible, and undesirable partitions described in Section 4.

Observe that undesirable partitions are unallocated by construction, since we
selected $\sigma_{i}$ based on the segment receiving a positive allocation
with highest $ppb$. Now consider any segment $(i,j,k)$ in agent $i$’s forced
partition. We have,

$\frac{D_{ijk}}{P-p_{j}}<\frac{1}{\sigma_{i}}\Rightarrow D_{ijk}(R-r_{i})\leq
D_{ijk}\sigma_{i}<P-p_{j}.$

Hence to satisfy (10c), it must be that that $s_{ijk}>0$. Therefore, (10d)
must hold with equality to satisfy (10d’). That is, the segment is fully
allocated.

Finally, let $(i,j,k)\in Q_{i}$. If $(R-r_{i})<\sigma_{i}$ then all the
segments of this partition are also fully allocated by the similar argument as
above. In other words, the agent exhausts her budget when she is done
consuming $Q_{i}$ as the last partition. It follows from the characterization
in Section 4 that each agent receives an optimal bundle of bads. ∎

###### Proof.

(of Theorem 5) By Lemma 38 at prices $p^{*}_{j}=-(P-p_{j})$ for all $j$ the
market clears. And by Lemma 39, each agent receives an optimal bundle of goods
in any solution to LCP (10), i.e., it is a competitive equilibrium. Further,
upto change of variables from LCP (8) to LCP (10), Lemma 4 shows that every
competitive equilibrium yields a solution to LCP (10). ∎

###  C.3 Proof of Lemma 7

###### Proof.

The proof follows similarly to Lemma 38 in Appendix C.1. Let
$(\mbox{\boldmath$x$}^{*},\mbox{\boldmath$p$}^{*})$ be an equilibrium. Set
$p_{j}=|p_{j}^{*}|,\ \forall j\in M^{-}$, and $p_{j}=p_{j}^{*},\ \forall j\in
M^{+}$. For each agent $i$ and each item $j$, we distribute $x_{ij}^{*}$ among
individual segments by filling starting from the first segment until all of
$x_{ij}^{*}$ is used, according to (28). The market clearing conditions for
the equilibrium ensures that setting $f_{ijk}=x_{ijk}^{*}p_{j}$ together with
$p$ satisfies (11a), (11b), and (11c).

Next, suppose $\mbox{\boldmath$p$},\mbox{\boldmath$f$}$ satisfy (11a), (11b),
(11c) and $\mbox{\boldmath$p$}>0$. Summing (11a) over all $i\in N$, (11b) over
all $j\in M^{-}$, and (11c) over all $j\in M^{+}$ gives

$\sum_{j\in M^{+}}p_{j}-\sum_{j\in M^{-}}p_{j}=\sum_{i,k,j\in
M^{+}}f_{ijk}-\sum_{i,k,j\in M^{-}}f_{ijk}\leq\sum_{i,j\in
M^{+}}W_{ij}p_{j}-\sum_{i,j\in M^{-}}W_{ij}p_{j}=\sum_{j\in
M^{+}}p_{j}-\sum_{j\in M^{-}}p_{j}$

since there is a unit amount of each item, i.e., $\sum_{i}W_{ij}=1$. Since all
variables are non-negative, it follows that (11a), (11b), and (11c) hold with
equality. Therefore, setting $x_{ijk}=f_{ijk}/p_{j}$ ensures the market
clears. ∎

###  C.4 Proof of Lemma 8

###### Proof.

Let $(\mbox{\boldmath$x$}^{*},\mbox{\boldmath$p$}^{*})$ be a competitive
equilibrium. In the LCP set $p_{j}=|p^{*}_{j}|,\ \forall j\in M$ and $f$ as
done in the proof of Lemma 7. By Lemma 7, (11a), (11b), and (11c) hold with
equality since $(\mbox{\boldmath$x$}^{*},\mbox{\boldmath$p$}^{*})$ clears the
market. Therefore, so do (11a’), (11b’), and (11c’). For each agent $i$, if
$i$ purchases any goods, then set $r_{i}$ according to (12) for any flexible
segment of goods. Otherwise, set $r_{i}$ according to (12) for any flexible
segment of bads. In either case $r_{i}>0$ since $i$ is non-satiated for some
good $j$, i.e., $U_{ijk}>0$, and $0<D_{ij1}\leq D_{ij2}\leq\dots$, for all
bads $j\in M^{-}$.

We set the variables $s_{ijk}$ as follows. If $(i,j,k)$ is undesirable or
flexible set $s_{ijk}=0$, whether $j$ is a good or a bad. Recall that, for a
forced segment $(i,j,k)$, if $j\in M^{+}$ then
$\frac{1}{r_{i}}<\frac{U_{ijk}}{p_{j}}$, and if $j\in M^{-}$ then
$\frac{1}{r_{i}}>\frac{U_{ijk}}{p_{j}}$. Using this, set it’s $s_{ijk}$ to
satisfy

$\frac{1}{r_{i}}=\frac{U_{ijk}}{p_{j}+s_{ijk}},\mbox{ if $j\in
M^{+}$},\quad\text{or}\quad\frac{1}{r_{i}}=\frac{D_{ijk}}{p_{j}-s_{ijk}},\mbox{
if $j\in M^{-}$}.$

It is easy to verify that in each case: the segment is forced, flexible, or
undesirable; the constraints (11d), (11e), and (11f) are satisfied, as well as
the corresponding complementarity conditions (11d’), (11e’), and (11f’). ∎

###  C.5 Proof of Lemma 9

###### Proof.

Given a solution of LCP (13), define $p^{*}_{j}=(P-p_{j}),\ \forall j\in
M^{+}$ and $p^{*}_{j}=-(P-p_{j}),\ \forall j\in M^{-}$. And allocation
$x^{*}_{ij}=\sum_{k}f_{ijk}/p^{*}_{j},\ \forall(i,j)$. We want to show that
$(\mbox{\boldmath$p$}^{*},\mbox{\boldmath$x$}^{*})$ gives a competitive
equilibrium. It is easy to show that market clears at
$(\mbox{\boldmath$p$}^{*},\mbox{\boldmath$x$}^{*})$ using (13a), (13b), and
(13c) using similar argument as in Lemma 7. Next, we show that every agent
receives an optimal bundle as per $\mbox{\boldmath$x$}^{*}$ at prices
$\mbox{\boldmath$p$}^{*}$.

Recall that we have picked $P$ and $R$ such that $\min_{j\in
M^{-},i,k}D_{ijk}R-P>0$, and $P-\min_{j\in M^{+},i.k}$ $U_{ijk}R<0$. While
similar to the proof of Lemma 39, we now rely on the assumption that each
agent $i$ is non-satiated for some good $j$, i.e., the final segment $(i,j,k)$
of good $j$ satisfies $U_{ijk}>0$. Notice that since $D_{ijk}>0,\forall i,k$
for any bad $j$, and the above assumption on goods implies that $r_{i}>0,\
\forall\ i\in N$. Consider two cases: an agent purchases some bads, or they
purchase only goods. In the first case, if $r_{i}=0$, then (13d) is a strict
inequality. Then (13d’) requires $f_{ijk}=0,\ \forall\ i,k$, $\forall j\in
M^{-}$, contradicting market clearing, Lemma 7. Similarly, in the second case,
if $r_{i}=0$, then (13e) can not hold for the non-satiated segment with
infinite length.

Here, we diverge from the case of all bads, depending on whether an agent
purchases any goods (or bads). Consider any agent $i$. There are three cases,
$i$ purchases: a) only goods, b) only bads, or c) goods and bads. We focus on
the last case as it is the most complicated. The first two cases can be
handled in a similar manner. Let $(i,j,k)$ be the segment of goods with lowest
bang per buck that agent $i$ spends on, i.e., with $f_{ijk}>0$. Define
$\nu_{i}$ as the inverse $bpb$ of this segment

$\nu_{i}=\frac{P-p_{j}}{U_{ijk}}.$

Note that $0<\nu_{i}<\infty$, since $p_{j}<P$, and each agent is non-satiated
for some good $j$. Similarly, let $(i,j^{\prime},k^{\prime})$ be the segment
of bads with the highest pain per buck, $ppb$, that $i$ spends on, and define
$\sigma_{i}$ as in Lemma 39. We want to show that
$\nu_{i}\leq(R-r_{i})\leq\sigma_{i}$. Therefore, $bpb_{ijk}\geq
ppb_{ij^{\prime}k^{\prime}}$ for any good $j$ and any bad $j^{\prime}$ that
$i$ spends on. From (29), we have $(R-r_{i})\leq\sigma_{i}$. By a similar
argument, for the segment $(i,j,k)$ with lowest bang per buck

$U_{ijk}(R-r_{i})=(P-p_{j})+s_{ijk}\geq(P-p_{j})=U_{ijk}\nu_{i}.$

Thus, $(R-r_{i})\geq\nu_{i}$.

Let $G_{i}$ denote the set of segments of goods with $bpb=1/\nu_{i}$, and call
this the flexible partition of goods. Similarly, let the forced partition of
goods be all segments with strictly higher $bpb$ than $1/\nu_{i}$, and the
undesirable partition of goods be all segments with strictly lower $bpb$ than
$1/\nu_{i}$. Define the various partitions of bads as: forced for $ppb$
strictly less than $\sigma_{i}$, undesirable if $ppb$ strictly more than
$\sigma_{i}$, and let $B_{i}$ be the flexible partition for bads where
$ppb=1/\sigma_{i}$. As per the optimal bundle characterization described in
Section 4 we need to show that $f_{ijk}$’s are zero for the segments in
undesirable partitions, $f_{ijk}=L_{ijk}(P-p_{j})$ for the segments in forced
partitions, and $0\leq f_{ijk}\leq L_{ijk}(P-p_{j})$ for segments in $G_{i}$
and $B_{i}$.

Observe that undesirable goods (bads) are unallocated by construction, since
we selected $\nu_{i}$ ($\sigma_{i}$) based on the segment receiving a positive
allocation with lowest $bpb$ (highest $ppb$). Consider any segment $(i,j,k)$
in agent $i$’s forced partition, whether a bad or a good. Observe that
$s_{ijk}>0$, in order to satisfy (13d) or (13e). Therefore, (13f’) requires
that (13f) holds with equality. That is the segment is fully allocated.

For the flexible partition, if $\nu_{i}<(R-r_{i})$, then for all $(i,j,k)\in
G_{i}$ it must be that $s_{ijk}>0$ and hence $f_{ijk}=L_{ijk}(P-p_{j})$,
otherwise $(i,j,k)$ could be partially allocated. Similarly, if
$(R-r_{i})<\sigma_{i}$, then all the segments in $B_{i}$ are fully allocated,
otherwise they could be partially allocated. Thus, $i$ only purchases goods
with $bpb\geq ppb$, and in the flexible partition of goods and bads $bpb=ppb$.
It follows from the characterization in Section 4 that each agent receives an
optimal bundle of bads. ∎

###  C.6 Proof of Theorem 10

###### Proof.

By Lemmas 7 and 9, the market clears and each agent receives an optimal bundle
of goods in any solution to LCP (13) with $p_{j}<P,\ \forall j\in M$ and
$r_{i}<R,\ \forall i\in N$, i.e., it is a competitive equilibrium. Further,
Lemma 8 shows that every competitive equilibrium prices yields a solution to
LCP (13) with $p_{j}<P,\ \forall j\in M$ and $r_{i}<R,\ \forall i\in N$.
Therefore, solutions to LCP (13) with $p_{j}<P,\ \forall j\in M$, and
$r_{i}<R,\ \forall i\in N$, exactly captures competitive equilibria up to
scaling. ∎

###  C.7 Proof of Theorem 11

We first show this theorem for the case of all bads, i.e., for LCP (14)
without (14c) and (14e).

######  Theorem 40.

In case of all bads, if the input parameters $\mathbf{D}$, $\mathbf{W}$, and
$\mathbf{L}$ have no polynomial relation among them, then every vertex of
$\mathcal{P}$ with $z>0$, $p_{j}<P,\ \forall j\in M$, and $r_{i}<R,\ \forall
i\in N$ is nondegenerate.

###### Proof.

Let
$S=(\mbox{\boldmath$p$},\mbox{\boldmath$q$},\mbox{\boldmath$r$},\mbox{\boldmath$s$},z)$
be a vertex solution to LCP (14) with $z>0$ and $p_{j}<P,\ \forall j\in M$.
For contradiction, suppose $S$ is degenerate. Then, there are at least two
double labels at $S$. Let $\mathcal{I}$ be the set of inequalities of LCP (14)
which hold with equality at $S$. Remove all zero variables and their non-
negativity conditions from $\mathcal{I}$, as well as all conditions
corresponding to double labels at $S$. Our goal is to write all non-zero
variables as linear functions of $z$, where the coefficients are in terms of
monomials of input parameters. Then, substituting these expressions into the
double labels at $S$ yields a polynomial relation among input parameters.

For forced segments, i.e., $s_{ijk}>0$, remove conditions (14d) and (14f) from
$\mathcal{I}$, and replace $f_{ijk}$ with $L_{ijk}(P-p_{j})$. For undesirable
segments, (14f) is a strict inequality and $f_{ijk}=0$. Thus, $\mathcal{I}$
contains no conditions (14d) or (14f) for undesired segments either.

Now we may write all non-zero variables as linear functions of $z$. All
remaining $f_{ijk}$ correspond to spending in flexible segments. Clearly, for
each agent $i$ and each bad $j$ only one such segment exists. To simplify
notation we relabel $f_{ijk}$ for these flexible segments as $f_{ij}$, and the
corresponding $D_{ijk}$ as $D_{ij}$.

Let $\mathcal{E}$ be the set of $(i,j)$ pairs such that agent $i$ has a
flexible segment for bad $j$, i.e., where condition (14d) holds with
$s_{ijk}=0$. Then,

$D_{ij}r_{i}-p_{j}=D_{ij}R-P.$ (30)

By considering the pairs of $\mathcal{E}$ as edges between $N$ and $M$, we
obtain a bipartite graph, say $G$. Note that $G$ is acyclic, otherwise we
obtain a polynomial relation between $D_{ij}$’s using (30) along the cycles to
eliminate the $r_{i}$’s and $p_{j}$’s.

Let $H$ be a connected component of $G$. We pick a representative bad for $H$.
If there is an undersold bad, i.e., (14b) is a strict inequality, then we pick
this item, say $b$. Observe that for any bad $j\in H$, we may write
$P-p_{j}=\frac{\phi_{1}(D)}{\phi_{2}(D)}(P-p_{b})$, where $\phi_{1}(D)$ and
$\phi_{2}(D)$ are monomials in terms of $D_{ij}^{\prime}$s. Similarly, we may
write $R-r_{i}$ in terms of monomials of $D_{ij}^{\prime}$s. Now, since (14b)
is a strict inequality for bad $b$, the complementary condition (14b’)
requires $p_{b}=0$. In addition, no other bad $j$ can be undersold in $H$,
otherwise the above steps yield a polynomial relation between the
$D_{ij}^{\prime}$s.

Suppose that for component $H$, the representative bad $b$ is not undersold,
i.e., (14b) holds with equality. Consider any leaf node $v_{0}$ of $H$, and
remove the edge incident to it in $H$, say $(v_{0},v_{1})$ to create
$H^{\prime}$. Let $H^{\prime}$ be rooted at $v_{1}$. Starting from leafs of
$H^{\prime}$ and working toward the root $v_{1}$, we can use market clearing
conditions (14b) and (14a) for bads and agents respectively, to write all
$f_{ij}^{\prime}$s for edges in $H^{\prime}$ as linear functions of $z$ and
the representative prices obtained in the first step. Market clearing
conditions give two different expressions for $f_{ij}$ on the missing edge
$(v_{0},v_{1})$. Thus, yielding a linear relation between the representative
prices and $z$. This relation is non trivial because exactly one of them must
contain a $W_{ij}$ not present in the other.

If bad $b$ is undersold, then a similar approach using $b$ as the root allows
us to write $f_{ij}^{\prime}$s as linear functions of representative prices
and $z$. This gives a system of linear equations: $p_{b}=0$ if $b$ is
undersold, and $p_{j}$ is a linear function of representative prices and $z$
otherwise. Solving this system, we obtain $p_{j}$’s as linear functions of
$z$. Substituting these expressions for representative prices in terms of $z$,
we obtain expressions for $f_{ij}$’s, $r_{i}$’s, and remaining $p_{j}$’s. We
preform the above steps for each connected component of $G$.

Finally, consider the equalities of $G$ corresponding to double labels that we
removed from $\mathcal{I}$. Replace all variables by their linear functions of
$z$. Use one double label to solve for $z$ in terms of input parameters
$\mathbf{D}$, $\mathbf{W}$, and $\mathbf{L}$. Substitute this value of $z$ in
to the other double label to get a polynomial relation among input parameters,
a contradiction. ∎

###### Proof.

(of Theorem 11) The proof closely follows that of Theorem 40. We assume for
contradiction, that the vertex is nondegenerate. Our goal is to write all non-
zero variables as linear functions of $z$, where the coefficients are in terms
of monomials of input parameters. Then, substituting these expressions into
the double labels at $S$ yields a polynomial relation between input
parameters. Notice that we may still follow the steps in Theorem 40 to solve
for $r$, as well as $p$, $f$, and $s$ for all bads $j\in M^{-}$. Thus, it
remains to solve for $p$, $f$, and $s$ for all goods $j\in M^{+}$. Using
similar arguments to the case of all bads, we find expressions for these
variables as linear functions of $z$. Substituting these expressions into the
two sets of double labels yields a polynomial relation between input
parameters. ∎

###  C.8 Proof of Theorem 12

To prove the theorem it suffices to show one to one correspondence between
solutions of LCP (13) and competitive equilibria. For this, we first show a
similar result for the case of all bads, i.e., using LCP (10).

######  Theorem 41.

If the polyhedron of LCP (10) is nondegenerate, then solutions to LCP (10)
with $p_{j}<P,\ \forall j\in M$, and $r_{i}<R,\ \forall i\in N$, are in one to
one correspondence with competitive equilibria.

###### Proof.

Due to scale invariance, it suffices to show this for the set of competitive
equilibria, say $\mathcal{E}$, where the minimum price is $-P$. In LCP (10),
we represent the equilibrium price of a bad as $p_{j}^{*}=-P+p_{j}$.
Therefore, we show a one to one correspondence between elements of
$\mathcal{E}$ and solutions to LCP (10) with $p_{j}=0$ for some bad $j$. Let
$(\mbox{\boldmath$x$}^{*},\mbox{\boldmath$p$}^{*})\in\mathcal{E}$. By Theorem
5, any competitive equilibrium
$(\mbox{\boldmath$x$}^{*},\mbox{\boldmath$p$}^{*})$ yields a solution to LCP
(10) using $\mbox{\boldmath$p$}=P+\mbox{\boldmath$p$}^{*}$, and $f$ where
$f_{ijk}=x^{*}_{ijk}(P-p_{j})$. We show that this choice of
$(\mbox{\boldmath$p$},\mbox{\boldmath$f$})$ yields exactly one solution to LCP
(10).

For contradiction, suppose not. Then, there exists different choices of $r$
and $s$ that together with $(\mbox{\boldmath$p$},\mbox{\boldmath$f$})$ solve
LCP (10). Observe that fixing $p$, $f$, and $s$ also fixes $r$. Therefore, it
must be true that for some agent, say $i$, her flexible partition, say
$Q_{i}$, is full allocated, i.e., $f_{ijk}=L_{ijk}(P-p_{j}),\forall(j,k)\in
Q_{i}$. Set $r_{i}$ so that

$\frac{1}{R-r_{i}}=\frac{D_{ijk}}{P-p_{j}},$

for some segment $(j,k)\in Q_{i}$, and set $s_{ijk}=0,\ \forall\ (j,k)\in
Q_{i}$. Set the $r$ and $s$ for all other agents similarly.

Let $C=\sum_{ij}|u_{ij}|$, be the total number of segments over all agents and
items. Observe that there are $n+m+2C$ variables in LCP (10). Further, the
solution described above gives at least $n+m+2C+2$ inequalities of LCP (10)
hold with equality: Market clearing gives (10a) $\forall i\in N$ and (10b)
$\forall j\in M$, and optimal bundles satisfies complementarity conditions
(10c’) and (10d’). Plus the requirement $p_{j}=0$ for some bad. Finally, all
segments of agent $i$’s flexible partition $Q$ satisfy both (10d) and
$s_{ijk}=0$. However, nondegeneracy of LCP (10) means at most $n+m+2C+1$
inequalities hold with equality at any vertex. ∎

###### Proof.

(Theorem 12) Showing the one to one correspondence follows from a nearly
identical argument to that of Theorem 41. The only difference is that must
consider the set of equilibria with maximum magnitude of price equal to $P$,
i.e., $p_{j}=0$ for some good or some bad. Assuming a bad has price with
maximum magnitude price $P$ and follow the same argument as Theorem 41. The
case where a good has maximum magnitude price follows from a similar argument.
∎

##  Appendix D Convergence of Algorithm 1 with All Bads

In this Section we prove that Algorithm 1 always converges to an equilibrium
in the case of all bads, $M^{+}=\emptyset$. The proofs are similar in spirit
to the mixed manna case, but there are minor differences in some details. We
still show that we the algorithm never sets a subset prices to zero, i.e.,
$p_{j}=P$, $\forall j\in\tilde{M}\subset M$, rather all prices are set to zero
simultaneously. However, we can not rely on Lemma 16 to ensure that $r_{i}=R,\
\forall i\in N$, as used in Lemma 19 which shows that the algorithm stops at
an equilibrium before setting $p_{j}=P,\ \forall j\in M$. This is the only
real difference between the proofs.

Recall LCP (10) of Section 4.1 which gives the formulation for all bads. We
require the augmented LCP which we create by adding $-z$ to the left hand side
of (10a) for all $i\in N$, yielding

$\displaystyle\forall i\in N:$ $\displaystyle\
-\sum_{j}W_{ij}p_{j}-\sum_{j,k}f_{ijk}-z\leq-P\sum_{j}W_{ij}$
$\displaystyle\perp\ \ r_{i}.$ (31)

Let $k=\arg\max_{i}\sum_{j\in M}W_{ij}$. Then we get the primary ray by
setting $z=\sum_{j\in M}W_{kj}$, and all other variables equal to 0.

We now show that Algorithm 1 never reaches a secondary ray where $p_{j}=P$ for
some subset of bads, and $z>0$, and that the algorithm never reaches the
degenerate solution where $p_{j}=P,\ \forall j\in M$, and all other variables
equal to 0.

Note that Claim 1, and Lemmas 15, and 17 still hold. Therefore, $p_{j}\leq P,\
\forall j\in M$, $r_{i}\leq R,\ \forall i\in N$, and if $p_{j}=P$ for some
$j\in M$, then $p_{j}=P,\ \forall j\in M$. Thus, the algorithm never reaches a
secondary ray where $p_{j}=P$ for some subset of bads, and $z>0$. It remains
to show that the algorithm never reaches the generate equilibrium where
$p_{j}=P,\ \forall j\in M$. The idea is similar to Lemma 19. However, we can
not use Lemma 16 to show that $p_{j}=P,\ \forall j\in M$ implies $r_{i}=R,\
\forall i\in N$.

######  Lemma 42.

Starting from the primary ray, Algorithm 1 never reaches the degenerate
solution where $p_{j}=P,\ \forall j\in M$, $r_{i}=R,\ \forall i\in N$, and all
other variables equal to zero.

###### Proof.

Let $T$ be a vertex where $p_{j}=P,\ \forall j\in M$, $S$ be the vertex that
precedes $T$, and $E$ be the edge between $S$ and $T$. At $S$, $p_{j}>0$ so
that all $p_{j}\rightarrow P$ on $E$. Therefore, complementarity condition
requires that (10b’) requires that (10b) holds with equality on $E$,
$\sum_{i,k}f_{ijk}=P-p_{j},\ \forall j\in M$. Since $p_{j}<P$ at $S$, this
requires that for each bad $j\in M$, at least on agent, say $i$, purchases
some this bad, i.e., $f_{ijk}>0$. Then complementarity condition (10c’)
requires that (10c) is tight. Observe that this implies that $r_{i}>0$,
otherwise (10c) holds with strict inequality for all segments $(i,j,k)$.
Therefore, for this agent, (31) holds with equality on $E$ by complementarity
condition (31’).

We want to argue that $r_{i}>0,\forall i\in N$. If this condition holds then
31 is tight $\forall i\in N$, and (10b) is tight $\forall j\in M$. Summing
over all of the constraints yields

$\sum_{j}P-p_{j}=\sum_{j}W_{ij}(P-p_{j})=\sum_{ijk}f_{ijk}+nz=\sum_{j}P-p_{j}+nz,$

at $S$, since $\sum_{i}W_{ij}=1$. Then, $z=0$ at $S$, which is a competitive
equilibrium by Theorem 5.

For contradiction, assume that $r_{k}>0$, for some strict subset of agents
$k\in N_{1}\subset N$. Note that for all agents $i\in N_{0}=N\setminus N_{1}$,
(10c) holds with strict inequality since $r_{i}=0$, and therefore
complementarity condition (10c’) requires that $f_{ijk}=0$ for all segments
$(j,k)$ for all $i\in N_{0}$. Further, since $p_{j}>0,\ \forall j\in M$, at
$S$ then (10b’) requires that (10b) is tight for all $j\in M$. Then, we see
that $\sum_{j,k,i\in N_{1}}f_{ijk}=\sum_{ijk}f_{ijk}=\sum_{j}(P-p_{j})$.

Next, observe that (31) is tight for all $i\in N_{1}$ by complementarity
condition (31’). Therefore, $\sum_{j,i\in N_{1}}W_{ij}(P-p_{j})=\sum_{j,k,i\in
N_{1}}f_{ijk}+|N_{1}|z$. Also, since every agent is endowed with some fraction
of at least one bad and $p_{j}<P$ at $S$, $\sum_{j,i\in
N_{1}}W_{ij}(P-p_{j})<\sum_{j}(P-p_{j})$. Combining the above results yields

$\sum_{j}(P-p_{j})>\sum_{j,i\in N_{1}}W_{ij}(P-p_{j})=\sum_{j,k,i\in
N_{1}}f_{ijk}+|N_{1}|z=\sum_{j}(P-p_{j})+|N_{1}|z,$

at $S$. Thus, we obtain a contradiction since $p_{j}<P,\ \forall j\in M$ and
$z\geq 0$ at $S$. ∎

The only remaining step to show convergence of Algorithm 1 in the case of all
bads is to show that the algorithm never reaches a secondary where
$\mbox{\boldmath$p$}<P$, and $\mbox{\boldmath$r$}<R$. However, this follows
the argument of Theorem 20, while simply ignoring the steps that relate to
goods.

Then, Lemmas 17 and 42 show that starting from the primary ray,
$\mbox{\boldmath$p$}<P$ and $\mbox{\boldmath$r$}<R$. Specifically, Algorithm 1
never reaches a secondary ray where $p_{j}=P$ for some subset of bads, and it
never reaches the degenerate solution. Theorem 20 shows that the algorithm
never reaches any other secondary ray. Therefore, eventually we reach a vertex
where $\mbox{\boldmath$p$}<P$, $\mbox{\boldmath$r$}<R$, and $z=0$, which is an
equilibrium by Theorem 5.

## References

  * [1] www.spliddit.org.
  * [2] www.mitwohnen.org.
  * [3] N. Anari, S. O. Gharan, A. Saberi, and M. Singh.  Nash Social Welfare, Matrix Permanent, and Stable Polynomials.  In 8th Innovations in Theoretical Computer Science Conference (ITCS), pages 1–12, 2017.
  * [4] N. Anari, T. Mai, S. O. Gharan, and V. V. Vazirani.  Nash social welfare for indivisible items under separable, piecewise-linear concave utilities.  In Proc. 29th Symp. Discrete Algorithms (SODA), pages 2274–2290, 2018.
  * [5] H. Aziz, I. Caragiannis, A. Igarashi, and T. Walsh.  Fair allocation of indivisible goods and chores.  In Proc. 28th Intl. Joint Conf. Artif. Intell. (IJCAI), 2019\.
  * [6] H. Aziz, H. Chan, and B. Li.  Maxmin share fair allocation of indivisible chores to asymmetric agents.  In Proc. 18th Conf. Auton. Agents and Multi-Agent Systems (AAMAS), pages 1787–1789, 2019.
  * [7] H. Aziz, H. Chan, and B. Li.  Weighted maxmin fair share allocation of indivisible chores.  In Proc. 28th Intl. Joint Conf. Artif. Intell. (IJCAI), 2019\.
  * [8] H. Aziz, G. Rauchecker, G. Schryen, and T. Walsh.  Algorithms for max-min share fair allocation of indivisible chores.  In Proc. 31st Conf. Artif. Intell. (AAAI), pages 335–341, 2017\.
  * [9] Y. Azrieli and E. Shmaya.  Rental harmony with roommates.  J. Economic Theory, 153:128–137, 2014.
  * [10] E. B. Budish and E. Cantillon.  The multi-unit assignment problem: Theory and evidence from course allocation at harvard.  American Economic Review, 102, 2010.
  * [11] S. Barman and S. K. Krishnamurthy.  Approximation algorithms for maximin fair division.  In Proc. 18th Conf. Economics and Computation (EC), pages 647–664, 2017.
  * [12] S. Barman, S. K. Krishnamurthy, and R. Vaish.  Finding fair and efficient allocations.  In Proc. 19th Conf. Economics and Computation (EC), pages 557–574, 2018.
  * [13] N. Bataille, M. Lemaître, and G. Verfaillie.  Efficiency and fairness when sharing the use of a satellite.  In Proceedings of the 5th International Symposium on Artificial Intelligence, Robotics and Automation in Space, pages 465–470, 1999.
  * [14] A. Bogomolnaia, H. Moulin, F. Sandomirskiy, and E. Yanovskaia.  Competitive division of a mixed manna.  Econometrica, 85(6):1847–1871, 2017.
  * [15] A. Bogomolnaia, H. Moulin, F. Sandomirskiy, and E. Yanovskaia.  Dividing bads under additive utilities.  Social Choice and Welfare, 52(3):395–417, 2019.
  * [16] W. Brainard and H. Scarf.  How to compute equilibrium prices in 1891.  Cowles Foundation Discussion Paper, 1270, 2000.
  * [17] S. J. Brams and A. D. Taylor.  Fair division - from cake-cutting to dispute resolution.  Cambridge University Press, 1996.
  * [18] S. Branzei and F. Sandomirskiy.  Algorithms for competitive division of chores.  arXiv:1907.01766, 2019.
  * [19] E. Budish.  The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.  J. Political Economy, 119(6):1061–1103, 2011.
  * [20] I. Caragiannis, D. Kurokawa, H. Moulin, A. Procaccia, N. Shah, and J. Wang.  The unreasonable fairness of maximum Nash welfare.  In Proc. 17th Conf. Economics and Computation (EC), pages 305–322, 2016.
  * [21] B. R. Chaudhury, Y. K. Cheung, J. Garg, N. Garg, M. Hoefer, and K. Mehlhorn.  On fair division for indivisible items.  In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS, pages 25:1–25:17, 2018\.
  * [22] B. R. Chaudhury, J. Garg, P. McGlaughlin, and R. Mehta.  Dividing bads is harder than dividing goods: On the complexity of fair and efficient division of chores.  Available at: http://jugal.ise.illinois.edu/chores.pdf, 2020.
  * [23] X. Chen, D. Dai, Y. Du, and S. Teng.  Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities.  In Proc. 50th Symp. Foundations of Computer Science (FOCS), pages 273–282, 2009.
  * [24] X. Chen, X. Deng, and S.-H. Teng.  Settling the complexity of computing two-player Nash equilibria.  J. ACM, 56(3), 2009.
  * [25] X. Chen, D. Paparas, and M. Yannakakis.  The complexity of non-monotone markets.  In Proc. 45th Symp. Theory of Computing (STOC), pages 181–190, 2013.
  * [26] X. Chen and S. Teng.  Spending is not easier than trading: On the computational equivalence of Fisher and Arrow-Debreu equilibria.  In Proc. 20th Intl. Symp. Algorithms and Computation (ISAAC), pages 647–656, 2009.
  * [27] X. Chen and S.-H. Teng.  Spending is not easier than trading: on the computational equivalence of fisher and arrow-debreu equilibria.  In International Symposium on Algorithms and Computation, pages 647–656. Springer, 2009.
  * [28] R. Cole, N. Devanur, V. Gkatzelis, K. Jain, T. Mai, V. Vazirani, and S. Yazdanbod.  Convex program duality, Fisher markets, and Nash social welfare.  In Proc. 18th Conf. Economics and Computation (EC), 2017.
  * [29] R. Cole and V. Gkatzelis.  Approximating the Nash social welfare with indivisible items.  In Proc. 47th Symp. Theory of Computing (STOC), pages 371–380, 2015.
  * [30] R. Cottle, J.-S. Pang, and R. Stone.  The Linear Complementarity Problem.  Academic Press, Boston, 1992.
  * [31] G. Dantzig.  Linear Programming and Extensions.  Princeton University Press, 1963.
  * [32] C. Daskalakis, P. Goldberg, and C. Papadimitriou.  The complexity of computing a Nash equilibrium.  SIAM J. Comput., 39(1):195–259, 2009.
  * [33] N. Devanur, J. Garg, and L. Végh.  A rational convex program for linear Arrow-Debreu markets.  ACM Trans. Econom. Comput., 5(1):6:1–6:13, 2016.
  * [34] N. Devanur and R. Kannan.  Market equilibria in polynomial time for fixed number of goods or agents.  In Proc. 49th Symp. Foundations of Computer Science (FOCS), pages 45–53, 2008.
  * [35] N. Devanur, C. Papadimitriou, A. Saberi, and V. Vazirani.  Market equilibrium via a primal–dual algorithm for a convex program.  J. ACM, 55(5), 2008.
  * [36] R. Duan, J. Garg, and K. Mehlhorn.  An improved combinatorial polynomial algorithm for the linear Arrow-Debreu market.  In Proc. 27th Symp. Discrete Algorithms (SODA), pages 90–106, 2016.
  * [37] R. Duan and K. Mehlhorn.  A combinatorial polynomial algorithm for the linear Arrow-Debreu market.  Inf. Comput., 243:112–132, 2015.
  * [38] B. C. Eaves.  A finite algorithm for the linear exchange model.  J. Math. Econom., 3:197–203, 1976.
  * [39] E. Eisenberg.  Aggregation of utility functions.  Management Sci., 7(4):337–350, 1961.
  * [40] E. Eisenberg and D. Gale.  Consensus of subjective probabilities: The Pari-Mutuel method.  Ann. Math. Stat., 30(1):165–168, 1959.
  * [41] R. Etkin, A. Parekh, and D. Tse.  Spectrum sharing for unlicensed bands.  In In Proceedings of the first IEEE Symposium on New Frontiers in Dynamic Spectrum Access Networks, 2005.
  * [42] J. Garg, M. Hoefer, and K. Mehlhorn.  Approximating the Nash social welfare with budget-additive valuations.  In Proc. 29th Symp. Discrete Algorithms (SODA), 2018.
  * [43] J. Garg and R. Kannan.  Markets with production: A polynomial time algorithm and a reduction to pure exchange.  In EC, pages 733–749, 2015.
  * [44] J. Garg, P. Kulkarni, and R. Kulkarni.  Approximating Nash social welfare under submodular valuations through (un)matchings.  In SODA, 2020.  To appear.
  * [45] J. Garg and P. McGlaughlin.  Computing competitive equilibria with mixed manna.  In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’20, Auckland, New Zealand, May 9-13, 2020, pages 420–428, 2020.
  * [46] J. Garg, R. Mehta, M. Sohoni, and V. V. Vazirani.  A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities.  SIAM J. Comput., 44(6):1820–1847, 2015.  Extended abstract appeared in STOC 2012.
  * [47] J. Garg, R. Mehta, and V. V. Vazirani.  Substitution with satiation: A new class of utility functions and a complementary pivot algorithm.  Math. Oper. Res., 43(3):996–1024, 2018.  Extended abstract appeared in STOC 2014.
  * [48] J. Garg and V. V. Vazirani.  On computability of equilibria in markets with production.  In SODA, pages 1329–1340, 2014.
  * [49] J. Garg and L. A. Végh.  A strongly polynomial algorithm for linear exchange markets.  In Proc. 51st Symp. Theory of Computing (STOC), 2019.
  * [50] A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica.  Dominant resource fairness: Fair allocation of multiple resource types.  In Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation, NSDI’11, pages 323–336, 2011.
  * [51] M. Ghodsi, M. HajiAghayi, M. Seddighin, S. Seddighin, and H. Yami.  Fair allocation of indivisible goods: Improvement and generalization.  In Proc. 19th Conf. Economics and Computation (EC), 2018.  Available on arXiv:1704.00222 since April 2017.
  * [52] J. R. Goldman and A. D. Procaccia.  Spliddit: unleashing fair division algorithms.  SIGecom Exchanges, 13(2):41–46, 2014.
  * [53] K. A. Hansen and T. B. Lund.  Computational complexity of proper equilibrium.  In Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, pages 113–130, 2018.
  * [54] X. Huang and P. Lu.  An algorithmic framework for approximating maximin share allocation of chores.  arXiv:1907.04505, 2019.
  * [55] K. Jain.  A polynomial time algorithm for computing the Arrow-Debreu market equilibrium for linear utilities.  SIAM J. Comput., 37(1):306–318, 2007.
  * [56] V. Klee and G. Minty.  How good is the Simplex algorithm?  In O. Shisha, editor, Inequalities III, pages 159–175. Academic Press, 1972.
  * [57] D. Koller, N. Megiddo, and B. von Stengel.  Fast algorithms for finding randomized strategies in game trees.  In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada, pages 750–759, 1994.
  * [58] C. Lemke and J. Howson.  Equilibrium points of bimatrix games.  SIAM J. Appl. Math., 12:413–423, 1964.
  * [59] C. E. Lemke.  Bimatrix equilibrium points and mathematical programming.  Management Science, 11(7):681–689, 1965.
  * [60] R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi.  On approximately fair allocations of indivisible goods.  In Proc. 5th Conf. Economics and Computation (EC), pages 125–131, 2004.
  * [61] H. Moulin.  Fair Division and Collective Welfare.  MIT Press, 2003.
  * [62] H. Moulin.  Fair division in the internet age.  Annual Review of Economics, 11, 2019.
  * [63] J. Orlin.  Improved algorithms for computing Fisher’s market clearing prices.  In Proc. 42nd Symp. Theory of Computing (STOC), pages 291–300, 2010.
  * [64] J. W. Pratt and R. J. Zeckhauser.  The fair and efficient division of the winsor family silver.  Management Science, 36(11):1293–1301, 1990.
  * [65] J. Robertson and W. Webb.  Cake-Cutting Algorithms: Be Fair If You Can.  AK Peters, MA, 1998.
  * [66] F. Sandomirskiy and E. Segal-Halevi.  Fair division with minimal sharing.  CoRR, abs/1908.01669, 2019.
  * [67] R. Savani and B. von Stengel.  Hard-to-solve bimatrix games.  Econometrica, 74(2):397–429, 2006.
  * [68] T. Sönmez and U. Unver.  Course bidding at business schools.  International Economic Review, 51(1):99–123, 2010.
  * [69] T. B. Sørensen.  Computing a proper equilibrium of a bimatrix game.  In Proc. 13th Conf. Economics and Computation (EC), pages 916–928, 2012.
  * [70] H. Steinhaus.  The problem of fair division.  Econometrica, 16:101–104, 1948.
  * [71] F. E. Su.  Rental harmony: Sperner’s lemma in fair division.  The American Mathematical Monthly, 106(10):930–942, 1999.
  * [72] M. Todd.  Orientation in complementary pivot algorithms.  Math. Oper. Res., 1(1):54–66, 1976.
  * [73] H. Varian.  Equity, envy and efficiency.  J. Econom. Theory, 29(2):217–244, 1974.
  * [74] V. Vazirani and M. Yannakakis.  Market equilibrium under separable, piecewise-linear, concave utilities.  J. ACM, 58(3):10, 2011.
  * [75] L. Végh.  Concave generalized flows with applications to market equilibria.  Math. Oper. Res., 39(2):573–596, 2014.
  * [76] L. A. Végh.  A strongly polynomial algorithm for generalized flow maximization.  Math. Oper. Res., 42(1):179–211, 2017.
  * [77] T. W. Vossen.  Fair allocation concepts in air traffic management.  PhD thesis, University of Maryland, College Park, 2002.
  * [78] L. Walras.  Éléments d’économie politique pure, ou théorie de la richesse sociale (Elements of Pure Economics, or the theory of social wealth).  Lausanne, Paris, 1874.  (1899, 4th ed.; 1926, rev ed., 1954, Engl. transl.).
  * [79] Y. Ye.  Exchange market equilibria with Leontief’s utility: Freedom of pricing leads to rationality.  Theoret. Comput. Sci., 378(2):134–142, 2007.