# Approximating Competitive Equilibrium by Nash Welfare ††This work was
supported by the European Research Council (ERC) under the European Union’s
Horizon 2020 research and innovation programme (grant agreement no.
ScaleOpt–757481). J. Garg was supported by NSF Grant CCF-1942321. Y. Tao was
supported by Grant 2023110522 from SUFE, National Key R&D Program of China
(2023YFA1009500), NSFC grant 61932002, Innovation Program of Shanghai
Municipal Education Commission, and Fundamental Research Funds for Central
Universities. Part of the work was done while L. Végh was visiting the
Corvinus Institute for Advanced Studies, Corvinus University, Budapest,
Hungary,

Jugal Garg  University of Illinois at Urbana-Champaign, USA  Yixin Tao  ITCS,
Key Laboratory of Interdisciplinary Research of Computation and Economics
Shanghai University of Finance and Economics, China  László A. Végh  London
School of Economics and Political Science, UK

###### Abstract

We explore the relationship between two popular concepts on allocating
divisible items: competitive equilibrium (CE) and allocations with maximum
Nash welfare, i.e., allocations where the weighted geometric mean of the
utilities is maximal. When agents have homogeneous concave utility functions,
these two concepts coincide: the classical Eisenberg–Gale convex program that
maximizes Nash welfare over feasible allocations yields a competitive
equilibrium. However, these two concepts diverge for non–homogeneous
utilities. From a computational perspective, maximizing Nash welfare amounts
to solving a convex program for any concave utility functions, computing CE
becomes PPAD-hard already for separable piecewise linear concave (SPLC)
utilities.

We introduce the concept of _Gale-substitute_ utility functions, an analogue
of the weak gross substitutes (WGS) property for the so-called Gale demand
system. For Gale-substitutes utilities, we show that any allocation maximizing
Nash welfare provides an approximate-CE with surprisingly strong guarantees,
where every agent gets at least half the _maximum_ utility they can get at any
CE, and is approximately envy-free. Gale-substitutes include examples of
utilities where computing CE is PPAD hard: in particular, all separable
concave utilities, and the previously studied non-separable class of Leontief-
free utilities. We introduce a new, general class of utility functions called
_generalized network utilities_ based on the generalized flow model; this
class includes SPLC and Leontief-free utilities. We show that all such
utilities are Gale-substitutes.

Conversely, although some agents may get much higher utility at a Nash welfare
maximizing allocation than at a CE, we show a price of anarchy type result:
for general concave utilities, every CE achieves at least
$(1/\mathrm{e})^{1/\mathrm{e}}>0.69$ fraction of the maximum Nash welfare, and
this factor is tight.

##  1 Introduction

Competitive (market) equilibrium is a central solution concept in economics to
analyze and predict the outcomes of market interactions. The Fisher model is a
fundamental market model where a set of $n$ agents ${\mathcal{A}}$ arrive at
the market with a fixed supply of divisible goods ${\mathcal{M}}$. Each agent
$i$ has a fixed budget $b_{i}$ and preferences over bundles of goods given by
a utility function $u_{i}(.)$. At competitive equilibrium (CE), prices
$\mathbf{p}\in\mathbb{R}_{\geq 0}^{\mathcal{M}}$ of goods and fractional
allocation $\mathbf{x}\in\mathbb{R}_{\geq
0}^{{\mathcal{A}}\times{\mathcal{M}}}$ of goods to agents are such that each
agent $i$ gets an optimal bundle of goods, i.e., $x_{i}$ maximizes
$u_{i}(x_{i})$ subject to $\langle\mathbf{p},x_{i}\rangle\leq b_{i}$, and the
market clears, i.e., the demand of each good meets its supply.

Equilibrium allocations satisfy many desirable properties, including Pareto
optimality and the fairness guarantee of (weighted) envy-freeness. These
properties make this an attractive concept also in other settings where no
direct trade and money are involved. For example, competitive equilibrium with
equal incomes (CEEI) is a popular mechanism in fair division, where a
fictitious market is created by giving each agent the same budget, see Varian
[1974]. We note that CEEI is a special case of the Fisher model, where
$b_{i}=1$ for each agent $i\in{\mathcal{A}}$.

It is standard to assume that the utility functions $u_{i}(.)$ are monotone
non-decreasing, concave, and satisfy $u_{i}(\mathbf{0})=0$. Classical results
in mathematical economics have established the existence of an equilibrium in
the Fisher model as well as more general exchange market models, by Arrow and
Debreu [1954] and by McKenzie [1954]. These results are based on fixed point
theorems and thus do not lead to efficient computational methods. Finding an
equilibrium by efficient computation has been an important topic in economics,
optimization, and computer science over the past decades. An early such result
was a convex programming formulation by Eisenberg and Gale [1959] for CE with
linear utility functions $u_{i}(x)=\sum_{j\in{\mathcal{M}}}v_{ij}x_{j}$. This
program amounts to maximizing the weighted Nash welfare, i.e., the weighted
geometric mean of agents’ utilities over feasible allocations. That is, any
allocation maximizing $\prod_{i}u_{i}(x_{i})^{b_{i}/\sum_{i}b_{i}}$
(equivalently, $\sum_{i}b_{i}\log{u_{i}(x_{i})}$) over feasible allocations
gives a CE, where the dual solution yields the corresponding prices
$\mathbf{p}$. Eisenberg [1961] showed that the same convex program yields
competitive equilibria more generally for concave utility functions that are
positively homogeneous of degree one, i.e., $u_{i}(\alpha x_{i})=\alpha
u_{i}(x_{i})$ for any $\alpha>0$. This includes classical examples of constant
elasticity of substitution (CES), Cobb–Douglas, and Leontief utility
functions.

The term _‘Nash welfare’_ refers to the bargaining problem introduced by Nash
[1950]. Nash studied general cooperative bargaining problems where the set of
possible outcomes is a convex set $K\subseteq\mathbb{R}^{n}$ with a
disagreement point $d\in K$, and showed that maximizing the geometric mean of
the excess utilities above the disagreement utility amounts to the only
possible bargaining outcome that satisfies certain natural requirements.
Taking $K$ as the set of feasible allocations and $d=\mathbf{0}$, the Nash
bargaining solution is precisely the Nash welfare maximizing allocation in
this setting.

_Weak gross substitutes (WGS)_ utility functions present another broad class
where a CE can be computed in polynomial time. Several fast algorithms have
been designed for computing equilibria with WGS utilities Codenotti et al.
[2005c, b], Bei et al. [2019a], Garg et al. [2023]. While the WGS class
includes many homogeneous utilities, there are also non-homogeneous examples,
and the Eisenberg–Gale solution may not correspond to a competitive
equilibrium.

WGS and homogeneous utility functions cover most known cases where a CE can be
computed in polynomial time. Already for the seemingly simple case of
separable piecewise concave utility functions, computing a CE is PPAD-hard
Chen and Teng [2009]. In fact, it is PPAD hard even for bounded linear
utilities, when there is an upper bound on the utility from each good, i.e.,
$u_{i}(x)=\sum_{j\in{\mathcal{M}}}\min\\{v_{ij}x_{j},\ell_{ij}\\}$, see [Bei
et al., 2019b]. In fact, Example A.1 in this paper shows that the set of CE
can be non-convex and disconnected already for bounded linear utilities.

#### Our contributions

In this paper, we study the relationship of two fundamental concepts on fair
division of divisible goods: competitive equilibrium and maximum Nash welfare
allocations. We show that there is a close relationship between these
solutions well beyond the homogeneous case.

First, we show a ‘price of anarchy’ type result Koutsoupias and Papadimitriou
[1999], Dubey [1986]. One can interpret Nash welfare as a global measure of
social utility. In contrast, a CE can be seen as an outcome reached by
autonomous agents trying to improve their utilities individually. It turns out
that, in the general setting of concave utilities, any CE recovers at least
$(1/e)^{1/e}>0.69$ fraction of the maximum Nash welfare, and this factor is
tight (see Example A.4).

######  Theorem 1.1.

In any Fisher market instance, the Nash welfare at any CE is at least
$(1/\mathrm{e})^{1/\mathrm{e}}$ times the maximum Nash welfare.

We then study guarantees of the maximum Nash welfare solution in the context
of CE. A major advantage of maximum Nash welfare is efficient computability:
it can be arbitrarily well approximated for any concave utility functions. In
contrast, computing CE becomes PPAD-hard already in very simple cases. In this
context, our first, simple result shows that maximum Nash welfare yields an
approximate CE for all concave utility functions; we define $\alpha$-demand-
approximate CE such that every agent receives at least $1/\alpha$-fraction of
the maximum possible utility at the current prices (see Definition 2.10). As
in the case of the Eisenberg–Gale program, one can interpret the optimal
Lagrangian multipliers as prices. The result also implies approximate envy-
freeness.

######  Theorem 1.2.

For Fisher markets under concave utility functions, any Nash welfare
maximizing allocation $\mathbf{y}$, together with the dual prices
$\mathbf{q}$, form a 2-demand-approximate CE. This also implies that
$\mathbf{y}$ is half envy-free when $b_{i}$’s are identical, i.e.,
$u_{i}(y_{i})\geq\tfrac{1}{2}u_{i}(y_{k})$, for all $i,k\in{\mathcal{A}}$.

Theorem 1.2 already shows that maximum Nash welfare provides remarkable
fairness and efficiency guarantees for all concave utility functions. However,
there can be multiple equilibria, giving vastly different utilities to an
agent. In Example A.5, we show that there could be a gap of $\Omega(n)$ in
some agent’s utility between two different competitive equilibria. Hence, an
agent could be much better off in some CE than in the maximum Nash welfare
solution.

As the main contribution of the paper, we show that maximum Nash welfare
provides surprisingly strong guarantees for a broad class of utility
functions. For this, we explore the _Gale demand correspondence_ Nesterov and
Shikhman [2018], Garg et al. [2023]. For an agent $i\in{\mathcal{A}}$ with
budget $b_{i}$ and utility function $u_{i}(.)$ at prices $\mathbf{q}$, the
Gale demand correspondence comprises of the allocations $y_{i}$ that maximize
$b_{i}\log u_{i}(y_{i})-\langle\mathbf{q},y_{i}\rangle$. It follows from
Lagrangian duality that in a Nash welfare maximizing solution, every agent
receives an allocation from their Gale demand correspondence.

The reason behind the equivalence of CE and maximum Nash welfare for
homogeneous utilities is that the standard demand correspondence and the Gale
demand correspondence coincide. Nevertheless, these two demands can behave
very differently for non-homogeneous utility functions, e.g., the Gale demand
can be non-monotonic in the prices, whereas the standard demand is always
monotonic (see Example A.3).

We identify a critical property of the Gale demand correspondence that we call
_Gale-substitutes property_ (Definition 2.14). This is analogous to the weak
gross substitutes (WGS) property of the standard demand correspondence. In
particular, it asserts that if some prices decrease then the demand for goods
with unchanged prices may only decrease.

Competitive equilibrium becomes more subtle when the utility functions are
_satiable_ : there is an absolute maximum value of the utility that can be
reached, regardless the prices—bounded linear utilities mentioned above give
such an example. To accommodate satiable utilities, we also introduce a
stronger variant of the definition, called the _$\Sigma$ -Gale-substitutes
property_. We note that for _non-satiable_ utilities, the Gale-substitutes and
$\Sigma$-Gale-substitutes properties coincide.

Our main result shows that for this class of utility functions, the utility of
any agent at the Nash welfare maximizing allocation is at least half the
_maximum_ utility they may get at _any_ CE.

######  Theorem 1.3.

Consider a Fisher market instance where all utility functions are
$\Sigma$-Gale-substitutes. Then, for any competitive equilibrium
$(\mathbf{x},\mathbf{p})$ and any Nash welfare maximizing allocation
$\mathbf{y}$, $u_{i}(y_{i})\geq\frac{1}{2}u_{i}(x_{i})$ holds for every
$i\in{\mathcal{A}}$.

Thus, an allocation maximizing the Nash welfare can be seen as a suitable, and
at the same time, efficiently computable alternative to CE for
($\Sigma$-)Gale-substitutes utility functions. It establishes a strong
relationship between CE and maximum Nash welfare beyond homogeneous functions
and provides a natural candidate to the _equilibrium selection_ problem Arrow
and Hahn [1971] in this setting where multiple equilibria are possible.

The proof of Theorem 1.3 relies on arguments involving supergradients of the
utility functions and subgradients of the Lagrangian dual function. A key
ingredient of the proof is that for $\Sigma$-Gale substitute utility functions
$u(.)$, at any given prices $\mathbf{p}$ and budget $b$, and any utility
maximizing allocation $x$ subject to
$\large\langle\mathbf{p},x\large\rangle\leq b$, there exists a solution $y\leq
x$ in the Gale demand correspondence under the same budget and prices (see
Lemma 5.1).

We call a utility function $u(.)$ _separable_ if
$u(x)=\sum_{j\in{\mathcal{M}}}v_{j}(x_{j})$. This class gives an important
example of $\Sigma$-Gale-substitutes. Note that such utilities, in general,
are neither homogeneous nor WGS. As mentioned above, competitive equilibrium
computation is already PPAD-hard for the separable piecewise linear concave
(SPLC) case when each $v_{j}$ is piecewise linear. This class has attracted
significant attention on its own Vazirani and Yannakakis [2011], Chen et al.
[2009, 2013], Garg et al. [2015], Anari et al. [2018].

######  Theorem 1.4.

Every separable utility function is $\Sigma$-Gale-substitutes.

We consider two further examples of piecewise linear Gale-substitutes
utilities:

  * •

_Leontief-free (LF) utilities_ Garg et al. [2014], Goyal et al. [2023], Filos-
Ratsikas et al. [2023]: Consider a set $K$ of segments, and let
$u(x)\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\max\sum_{k\in
K}u_{k}$: $u_{k}=\sum_{j\in{\mathcal{M}}}a_{jk}z_{jk},\ \ u_{k}\leq\ell_{k};\
\forall k\in K$; $\sum_{k\in K}z_{jk}\leq x_{j}\ \forall j\in{\mathcal{M}}$;
$\mathbf{z}\geq 0$. That is, an LF function is given by a set of linear
functions $u_{k}$’s with a maximum utility limit $\ell_{k}$ on each $k\in K$.
LF captures interesting non-separable PLC functions, and includes SPLC as a
special case where each segment $k\in K$ has exactly one $j$ with $a_{jk}>0$.

  * •

_Generalized network utilities_ : We introduce a new and broad class of
utility functions defined by generalized flow instances. Here, the goods
correspond to source nodes in a flow network with supply $x_{j}$,
$j\in{\mathcal{M}}$. Each arc has a capacity and a gain factor, and the
utility $u(x)$ is the maximum flow value that can reach a designated sink node
$t$ from supplies $x$. The precise definitions are given in Section 2.1. LF
can be formulated as a special case of a network with two layers, the middle
layer between the sources and the sink corresponding to the segments $K$.

We show the following:

######  Theorem 1.5.

Generalized network utility functions are Gale-substitutes.

Generalized flows is a classical network flow model that can model commodity
transportations with losses, as well as conversions between different types of
entities such as in financial networks; see Chapter 15 in Ahuja et al. [1993]
for a description and various applications. We prove Theorem 1.5 by exhibiting
finite algorithms to transform flow solutions representing solutions in the
Gale demand correspondence. These are inspired by the literature on maximum
generalized flow algorithms. In particular, we use ideas from the classical
highest gain augmenting path algorithm by Onaga [1966]. While this does not
give a polynomial-time algorithm, it was the starting point of further such
algorithms, including Goldberg et al. [1991], Végh [2014], Olver and Végh
[2020].

Theorem 1.3 already shows that in Fisher markets with non-satiable generalized
network utilities, Nash welfare maximizing allocations give a good
approximation to utilities at competitive equilibrium. However, satiable
generalized network utilities may violate property ($\Sigma$), and the
property in Theorem 1.3 does not hold for them in general (see Example A.10).

For satiable utility functions, it is natural to look at _thrifty (strong)
equilibria_ , where each agent receives an optimal bundle at the cheapest
possible price (see Definition 2.8). An appealing property of this concept is
that thrifty equilibria are Pareto efficient, while this may not hold for
(weak) competitive equilibrium. We also show that the statement of Theorem 1.3
remains true for generalized network utilities and for thrifty equilibria.

######  Theorem 1.6.

Consider a Fisher market instance where all utility functions are generalized
network utilities. Then, for any thrifty competitive equilibrium
$(\mathbf{x},\mathbf{p})$ and any Nash welfare maximizing allocation
$\mathbf{y}$, $u_{i}(y_{i})\geq\frac{1}{2}u_{i}(x_{i})$ holds for every
$i\in{\mathcal{A}}$.

Finally, we note that the statement of Theorem 1.3 does not hold for arbitrary
concave utilities. In Example A.8, we show that without the Gale-substitutes
property, agents may get much higher utilities in CE as in the maximum Nash
welfare allocations.

###  1.1 Related work

This paper strengthens the relationship between the two fundamental concepts
of competitive equilibrium and maximum Nash welfare. Both are intensely
studied concepts with a variety of applications, so we briefly mention further
related results. As mentioned earlier, computing equilibria in Fisher markets
is polynomial time for homogeneous and WGS utility functions, and beyond that,
the problem is essentially PPAD-hard. For SPLC utilities, computing even a
$O(n^{-13})$-approximate-CE Vazirani and Yannakakis [2011], Chen and Teng
[2009] is PPAD-hard. We note that Chen and Teng [2009], Vazirani and
Yannakakis [2011] use a different definition of approximate-CE, where every
agent gets an optimal bundle but the market clears approximately. Our
approximate-CE definition also appears in several previous works, e.g., in
Codenotti et al. [2005c], Codenotti and Varadarajan [2007], Codenotti et al.
[2005b].

Fisher markets are a special case of more general Arrow-Debreu (exchange)
markets. Computing equilibria in exchange markets is polynomial time for WGS
utility functions (see, e.g., Codenotti et al. [2005c], Bei et al. [2019a],
Garg et al. [2023]) and for CES utilities with parameter $-1\leq\rho<0$
Codenotti et al. [2005a], and beyond that the problem is essentially PPAD-hard
Chen et al. [2009], even for homogeneous functions, such as Leontief and CES
with parameter $\rho<-1$ Codenotti et al. [2006], Chen et al. [2013].

The maximum Nash welfare is a classic objective for allocating goods to
agents. It has received significant attention in the literature on social
choice and fair division, see, e.g., Moulin [2003]. It provides remarkable
fairness guarantees also for indivisible goods: under additive valuations,
maximum Nash welfare allocations attain the “unreasonable” fairness guarantee
of envy-freeness up to one good (EF1) Caragiannis et al. [2019]. Furthermore,
for more general subadditive valuations, the fairness guarantee of
$\tfrac{1}{2}$-approximate envy-freeness up to any good (EFX) can be achieved
at a $\tfrac{2}{3}$-approximate maximum Nash welfare allocation Feldman et al.
[2023].

#### Overview

The rest of the paper is organized as follows. Section 2 defines all models
and definitions. Section 3 proves Theorem 1.1, showing the tight bound of
$(1/\mathrm{e})^{1/\mathrm{e}}$ on the efficiency of competitive equilibria.
Section 4 presents several properties of the Gale demand correspondence and
proves Theorem 1.2, showing that Nash welfare maximizing allocations yield
$2$-demand approximate-CE. Section 5 proves Theorem 1.3, showing the stronger
guarantees of maximum Nash welfare allocations for Gale-substitutes utility
functions. Section 6 proves Theorem 1.4, showing that separable utilities are
$\Sigma$-Gale substitutes. Section 7 considers generalized network utility
functions and proves Theorems 1.5 and Theorem 1.6. Appendix A presents all
examples mentioned in the main body, and Appendix B presents an omitted proof
from Section 7.

##  2 Preliminaries

#### Notation

For a function $f\,:\,X\to Y$, let $\operatorname{dom}(f)\subseteq X$ denote
its domain. For a vector $x\in\mathbb{R}^{n}$, we let
$\operatorname{supp}(x)=\\{i\,:\,x_{i}\neq 0\\}$ denote its support. For
$x,y\in\mathbb{R}^{n}$, we use $\large\langle x,y\large\rangle=x^{\top}y$ for
the standard scalar product.

#### Subgradients and supergradients

The functions we consider in this paper are not always differentiable. We will
use sub- and supergradients, defined as follows.

######  Definition 2.1.

Given a function $f\,:\,\mathbb{R}^{n}\to\mathbb{R}$, a vector
$\mathbf{g}\in\mathbb{R}^{n}$ is a _supergradient_ of $f$ at the point
$\mathbf{x}\in\operatorname{dom}(f)$ if for all
$\mathbf{y}\in\operatorname{dom}(f)$,
$f(\mathbf{x})+\large\langle\mathbf{g},\mathbf{y}-\mathbf{x}\large\rangle\geq
f(\mathbf{y})$. Similarly, $\mathbf{g}\in\mathbb{R}^{n}$ is a _subgradient_ of
$f$ at $\mathbf{x}\in\operatorname{dom}(f)$ if
$f(\mathbf{x})+\large\langle\mathbf{g},\mathbf{y}-\mathbf{x}\large\rangle\leq
f(\mathbf{y})$ for all $\mathbf{y}\in\operatorname{dom}(f)$. We denote the set
of all supergradients of $f$ at $\mathbf{x}$ as
$\partial^{\wedge}{f}(\mathbf{x})$, set of all subgradients as
$\partial^{\vee}{f}(\mathbf{x})$.

Thus, $\mathbf{g}$ if a supergradient of $f$ if and only if $-\mathbf{g}$ is a
subgradient of $-f$. We recall that a function $f$ is convex if and only if
$\partial^{\vee}{f}(\mathbf{x})\neq\emptyset$ for every
$\mathbf{x}\in\operatorname{dom}(f)$ and concave if and only if
$\partial^{\wedge}{f}(\mathbf{x})\neq\emptyset$ for every
$\mathbf{x}\in\operatorname{dom}(f)$. For a differentiable convex (concave)
function, the unique subgradient (supergradient) at every point is the
gradient $\nabla f(\mathbf{x})$.

###  2.1 Utility functions

Given a set ${\mathcal{M}}$ of divisible goods, we will focus on utility
functions with the following properties.

######  Definition 2.2.

A function $u(\cdot)\,,\,\mathbb{R}_{\geq 0}^{\mathcal{M}}\to\mathbb{R}$ is a
_utility function_ if $u(\mathbf{0})=0$, $u(\cdot)$ is concave, monotone non-
decreasing, and there exists an $x\in\mathbb{R}_{\geq 0}^{\mathcal{M}}$ such
that $u(x)>0$.

We say that a utility function is _separable_ if
$u(x)=\sum_{j\in{\mathcal{M}}}v_{j}(x_{j})$. We will also distinguish between
satiable and non-satiatiable utilities.

######  Definition 2.3.

A utility function $u(\cdot)$ is _non-satiable_ if and only if, for any
$x\in\mathbb{R}_{\geq 0}^{\mathcal{M}}$, one can find
$x^{\prime}\in\mathbb{R}_{\geq 0}^{\mathcal{M}}$, such that
$u(x^{\prime})>u(x)$. Otherwise, we say the utility function is _satiable_.

#### Demand correspondence and Gale demand correspondence

By a _price vector_ , we mean a vector $\mathbf{p}\in\mathbb{R}_{\geq
0}^{\mathcal{M}}$. Given prices $\mathbf{p}$ and a budget
$b\in\mathbb{R}_{\geq 0}$, we define the _demand correspondence_ as the set of
maximum utility bundles achievable at $\mathbf{p}$ and $b$:

${\mathcal{D}}^{u}(\mathbf{p},b)\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\arg\max_{x\in\mathbb{R}_{\geq
0}^{\mathcal{M}}}\left\\{u(x)\,:\,\large\langle\mathbf{p},x\large\rangle\leq
b\right\\}\,.$ (1)

Note that if $u$ is a non-satiable utility function, then
$\large\langle\mathbf{p},x\large\rangle=b$ must hold for every
$x\in{\mathcal{D}}^{u}(\mathbf{p},b)$.

${\mathcal{D}}^{u}(\mathbf{p},b)$ is always a non-empty compact set when
$\mathbf{p}>0$. However, in cases when some prices may be $0$, the supremum of
utility over the budget constraint might be $\infty$, resulting in unbounded
demand. This may happen even when the supremum value is finite, and causes
technical difficulties. To circumvent these issues, this paper adopts the
following assumption regarding the utility functions $u(\cdot)$:

######  Assumption 1.

For any $\mathbf{p}\geq 0$ and $b>0$, if there is a sequence of allocations
$\\{x^{(k)}\\}_{k=1}^{\infty}$ such that
$\large\langle\mathbf{p},x^{(k)}\large\rangle$ converges to $b$ and
$u(x^{(k)})$ converges to some finite value $M<\infty$, then there exists a
finite allocation $x^{*}\in\mathbb{R}_{\geq 0}^{\mathcal{M}}$ such that
$u(x^{*})=M$ and $\large\langle\mathbf{p},x\large\rangle\leq b$.

This assumption always holds if the set of possible allocations is restricted
to a compact domain $X\subseteq\mathbb{R}_{\geq 0}^{\mathcal{M}}$; note that
such compactness assumption is made in Nesterov and Shikhman [2018]. For the
unrestricted domain $\mathbb{R}_{\geq 0}^{\mathcal{M}}$, it can also be shown
for arbitrary piecewise linear utility functions, that includes in particular
generalized network utilities defined below. The _Gale demand correspondence_
is defined as

$\mathcal{GD}^{u}(\mathbf{p},b)\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\arg\max_{y\in\mathbb{R}_{\geq
0}^{\mathcal{M}}}b\log u(y)-\large\langle\mathbf{p},y\large\rangle\,.$ (2)

We define the domain of this function with respect to prices as

$\texttt{FQ}^{u}\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\left\\{\mathbf{q}\in\mathbb{R}_{\geq
0}^{\mathcal{M}}\leavevmode\nobreak\ :\leavevmode\nobreak\ \exists
b>0,\sup_{y\in\mathbb{R}_{\geq 0}^{\mathcal{M}}}b\log
u(y)-\large\langle\mathbf{p},y\large\rangle<+\infty\right\\}\,.$ (3)

Under Assumption 1, $\mathbf{0}\in\texttt{FQ}{}^{u}$ if and only if $u(.)$ is
satiable. Every strictly positive $\mathbf{q}>\mathbf{0}$ is in
$\texttt{FQ}{}^{u}$, and if $u$ is satiable, then
$\texttt{FQ}{}^{u}=\mathbb{R}_{\geq 0}^{\mathcal{M}}$ (see Lemma 4.2).
Additionally, if $\mathbf{p}\in\texttt{FQ}^{u}$, then
$\mathcal{GD}^{u}(\mathbf{p},b)\neq\emptyset$. In Section 4, we show the
following.

######  Lemma 2.4.

Under Assumption 1, for any $\mathbf{p}\in\texttt{FQ}^{u}$ and any $b>0$,
$\mathcal{GD}^{u}(\mathbf{p},b)\neq\emptyset$.

Gale demands may behave very differently from the standard demand
correspondence. Example A.3 shows the counter-intuitive property increasing
the prices $\mathbf{p}$ may actually increase the Gale utility value
$\max_{y\in\mathbb{R}_{\geq 0}^{\mathcal{M}}}b\log
u(y)-\large\langle\mathbf{p},y\large\rangle$.

Recall the notions of bounded linear, separable piecewise linear (SPLC) and
Leontief-free (LF) utilities defined in the introduction. We now define
generalized network utility functions.

#### Generalized network utilities

First, we introduce the generalized flow model. A _generalized flow instance_
is defined as follows. Let $G=(V,E)$ be a directed graph with a sink node
$t\in V$, a supply set $S\subseteq V\setminus\\{t\\}$, a capacity vector
$h\in\mathbb{R}_{\geq 0}^{E}$, and positive gain factors
$\gamma\in\mathbb{R}_{>0}^{E}$. We let $\partial^{\mathrm{in}}(S)$ and
$\partial^{\mathrm{out}}(S)$ denote the set of arcs entering and leaving a
subset $S\subseteq V$, respectively. For a node $v\in V$, we use
$\partial^{\mathrm{in}}(v)$ and $\partial^{\mathrm{out}}(v)$ for
$\partial^{\mathrm{in}}(\\{v\\})$ and $\partial^{\mathrm{out}}(\\{v\\})$ for
the set of incoming and outgoing arcs. Given a vector $f\in\mathbb{R}_{\geq
0}^{E}$, the _net flow_ at node $v\in V$ is defined as

$\operatorname{net}_{f}(v)\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\sum_{e\in\partial^{\mathrm{in}}(v)}\gamma_{e}f_{e}-\sum_{e\in\partial^{\mathrm{out}}(v)}f_{e}\,.$

That is, for an arc $e=(v,w)$, $f_{e}$ denotes the flow entering $e$ at node
$v$. Flow gets multiplied by the gain factor $\gamma_{e}$ while traversing the
arc, with $\gamma_{e}f_{e}$ amount reaching node $w$. Given a _supply vector_
$x\in\mathbb{R}_{\geq 0}^{S}$, we say that $f\in\mathbb{R}_{\geq 0}^{E}$ is a
_feasible generalized flow with supply $x$_ if $0\leq f\leq h$, and
$\operatorname{net}_{f}(v)\geq-x_{v}$ for all $v\in S$, and
$\operatorname{net}_{f}(v)\geq 0$ for all $v\in V\setminus(S\cup\\{t\\})$. The
_maximum generalized flow value from supply $x$_ is the maximum amount of
$\operatorname{net}_{f}(t)$ among all feasible flows with supply $x$. It
corresponds to the optimum value of the following linear program:

$\displaystyle\max\leavevmode\nobreak$
$\displaystyle\operatorname{net}_{f}(t)$ ($\operatorname{GenflowLP}(x)$)
$\displaystyle\operatorname{net}_{f}(v)$ $\displaystyle\geq-x_{v}\quad\forall
v\in S$ $\displaystyle\operatorname{net}_{f}(v)$ $\displaystyle\geq
0\quad\forall v\in V\setminus(S\cup\\{t\\})$ $\displaystyle 0$
$\displaystyle\leq f\leq h\,.$

######  Definition 2.5.

The function $u:\mathbb{R}_{\geq 0}^{\mathcal{M}}\to\mathbb{R}_{\geq 0}$ is a
_generalized network utility_ function if $u(x)$ is the maximum generalized
flow value from supply $x$ in some generalized flow instance where the supply
set is $S={\mathcal{M}}$, the maximum flow amount is finite for any supply
vector, $u(\mathbf{0})=0$, and there exists $x\in\mathbb{R}_{\geq
0}^{\mathcal{M}}$ with $u(x)>0$.

The following properties are immediate from the definition, and show that
these are indeed utility functions in accordance with Definition 2.2.

######  Proposition 2.6.

If $u:\mathbb{R}_{\geq 0}^{\mathcal{M}}\to\mathbb{R}_{\geq 0}$ is a
generalized network utility function, then $u(x)$ is monotone non-decreasing
and concave, and satisfies Assumption 1.

#### SPLC and Leontief-free as special cases

An SPLC function can be represented as a generalized network utility function
by setting $V={\mathcal{M}}\cup\\{t\\}$, and for each $j\in{\mathcal{M}}$,
adding a capacitated arcs $e=(j,t)$ for each linear segment of $v_{j}$, where
$\gamma_{e}$ is the marginal utility on this segment and $h_{e}$ the length of
the segment. Similary, we can represent a Leontief-free utility as a
generalized network utility function by setting $V={\mathcal{M}}\cup
K\cup\\{t\\}$; recall $K$ is the set of segments. For each $j\in{\mathcal{M}}$
and $k\in K$, we add an arc $e=(j,k)$ with gain factor $\gamma_{e}=a_{jk}$ and
capacity $h_{e}=\infty$. For each segment $k\in K$, we add an arc $e=(k,t)$
with $\gamma_{e}=1$ and $h_{e}=\ell_{k}$.

###  2.2 Competitive equilibrium

In a _Fisher market instance_ , given is a set of agents ${\mathcal{A}}$ and a
set of divisible goods ${\mathcal{M}}$, with one unit available from each
good. Agents have utility functions $u_{i}\,:\,\mathbb{R}_{\geq
0}^{\mathcal{M}}\to\mathbb{R}_{\geq 0}$ and budgets $b_{i}\in\mathbb{R}_{>0}$,
$i\in{\mathcal{A}}$; we denote the budget vector as
$\mathbf{b}=(b_{i})_{i\in{\mathcal{A}}}$. An allocation vector is
$\mathbf{x}\in\mathbb{R}_{\geq 0}^{{\mathcal{A}}\times{\mathcal{M}}}$, where
$x_{ij}$ denotes the amount of good $j$ allocated to agent $i$. A _price
vector_ is a vector $\mathbf{p}\in\mathbb{R}_{\geq 0}^{\mathcal{M}}$. The
demand correspondence of agent $i$ will be denoted as
${\mathcal{D}_{i}}(\mathbf{p},b_{i})$.

######  Definition 2.7 (Competitive equilibrium).

Given a Fisher market instance as above, the allocations and prices
$(\mathbf{x},\mathbf{p})$ form a _competitive (market) equilibrium_ if the
following hold:

  1. (i)

every agent gets an optimal utility at these prices:
$x_{i}\in{\mathcal{D}_{i}}(\mathbf{p},b_{i})$ for every agent
$i\in{\mathcal{A}}$

  2. (ii)

no good is oversold: $\sum_{i}x_{ij}\leq 1$ for all $j\in{\mathcal{M}}$.

  3. (iii)

every item with positive price is fully sold: $\sum_{i}x_{ij}=1$ if $p_{j}>0$.

In case there are satiable utility functions,
$\large\langle\mathbf{p},x_{i}\large\rangle<b_{i}$ may be possible. Hylland
and Zeckhauser [1979] show that competitive equilibrium may not be Pareto
Efficient because of satiable utilities. Mas-Colell [1992] strengthened the
definition of a competitive equilibrium to require that each agent chooses a
least-cost optimal plan. This is also known as a _strong equilibrium_.

######  Definition 2.8 (Thrifty competitive equilibrium).

Given a Fisher market instance, the allocations and prices
$(\mathbf{x},\mathbf{p})$ form a _thrifty competitive equilibrium_ if
$(\mathbf{x},\mathbf{p})$ is a competitive equilibrium, and moreover, for
every $i\in{\mathcal{A}}$, the allocation $x_{i}$ minimizes
$\large\langle\mathbf{p},x_{i}\large\rangle$ among all allocations
${\mathcal{D}_{i}}(\mathbf{p},b_{i})$.

######  Lemma 2.9 (Gul et al. [2022], Garg et al. [2022]).

Thrifty competitive equilibria always exist and are Pareto efficient.

Note that in case all utilities are non-satiable, competitive equilibria and
thrifty competitive equilibria coincide. The concepts of _demand-approximate
competitive equilibrium_ allows for the agents to have suboptimal bundles:

######  Definition 2.10 (Approximate competitive equilibrium).

Given a Fisher market instance and $\alpha\geq 1$, the allocations and prices
$(\mathbf{x},\mathbf{p})$ form a _$\alpha$ -demand approximate competitive
equilibrium_ if

  1. (i)

$\large\langle\mathbf{p},x_{i}\large\rangle\leq b_{i}$ for each
$i\in{\mathcal{A}}$, and $i$ gets at least $\alpha$-fraction of the optimal
utility at these prices:
$u_{i}(x_{i})\geq\frac{1}{\alpha}\max_{x_{i}\in\mathbb{R}_{\geq
0}^{\mathcal{M}}}\\{u_{i}(x_{i})\,:\,\large\langle\mathbf{p},x_{i}\large\rangle\leq
b_{i}\\}$.

  2. (ii)

no good is oversold: $\sum_{i}x_{ij}\leq 1$ for all $j\in{\mathcal{M}}$.

  3. (iii)

every item with positive price is fully sold: $\sum_{i}x_{ij}=1$ if $p_{j}>0$.

It is a well-established fact that when all $b_{i}$’s are identical, the
competitive equilibrium attains exact envy-freeness. Here, we demonstrate that
our definition of approximate competitive equilibrium also results in
approximate envy-freeness.

######  Definition 2.11.

For a given allocation $\mathbf{x}\in\mathbb{R}_{\geq
0}^{{\mathcal{A}}\times{\mathcal{M}}}$, we say it is $\beta$-envy-free if, for
any agents $i$ and $j$, the condition
$u_{i}(x_{i})\geq\frac{1}{\beta}u_{i}(x_{j})$ holds.

######  Lemma 2.12.

When $b_{i}$’s are identical, the allocation $\mathbf{x}$ of an
$\alpha$-approximate competitive equilibrium is also $\alpha$-envy-free.

###### Proof.

This follows directly from
$u_{i}(x_{i})\geq\frac{1}{\alpha}\max_{x_{i}\in\mathbb{R}_{\geq
0}^{\mathcal{M}}}\left\\{u_{i}(x_{i})\,:\,\large\langle\mathbf{p},x_{i}\large\rangle\leq
b_{i}\right\\}\geq\frac{1}{\alpha}u_{i}(x_{j})$. ∎

###  2.3 Nash welfare

######  Definition 2.13.

Given a Fisher market instance, the _Nash welfare_ of an allocation
$\mathbf{y}\in\mathbb{R}_{\geq 0}^{{\mathcal{A}}\times{\mathcal{M}}}$ is the
weighted geometric mean of their utilities, namely,

$\left(\prod_{i\in{\mathcal{A}}}u_{i}(x_{i})^{b_{i}}\right)^{\frac{1}{\sum_{i\in{\mathcal{A}}}b_{i}}}\,.$

The allocation $\mathbf{y}\in\mathbb{R}_{\geq
0}^{{\mathcal{A}}\times{\mathcal{M}}}$ _maximizes the (weighted) Nash welfare_
, if its Nash welfare is maximal along all allocations with
$\sum_{i\in{\mathcal{A}}}y_{ij}\leq 1$ for all $j\in{\mathcal{M}}$,
$\mathbf{y}\geq\mathbf{0}$.

Note that the Nash welfare maximizing allocations are precisely the optimal
solutions to the _Eisenberg–Gale convex program_ , [1959].

$\displaystyle\max$ $\displaystyle\sum_{i\in{\mathcal{A}}}b_{i}\log
u_{i}(y_{i})$ (EG) s.t. $\displaystyle\sum_{i\in{\mathcal{A}}}y_{ij}\leq
1\quad\forall j\in{\mathcal{M}}$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \mathbf{y}\geq\mathbf{0}\,.$

Let us consider the Lagrangian dual of the program (EG). The Lagrangian dual
function can be written as

$\varphi(\mathbf{q})\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\sum_{i\in{\mathcal{A}}}\max_{y_{i}\in\mathbb{R}_{\geq
0}^{{\mathcal{M}}}}\left(b_{i}\log
u_{i}(y_{i})-\large\langle\mathbf{q},y_{i}\large\rangle\right)+\sum_{j\in{\mathcal{M}}}q_{j}.$
(4)

We define the domain
$\operatorname{dom}(\varphi)\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\cap_{i\in{\mathcal{A}}}\texttt{FQ}_{i}$,
where
$\texttt{FQ}_{i}\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\texttt{FQ}^{u_{i}}$
as defined in (3). Thus, $\operatorname{dom}(\varphi)$ is the set of
nonnegative prices $\mathbf{q}$ such that $\varphi(\mathbf{q})<\infty$. Strong
duality holds and the dual optimum is taken according since Slater’s condition
holds. Consequently, the optimal Nash welfare value equals the dual optimum

$\min_{\mathbf{q}\in\operatorname{dom}(\varphi)}\varphi(\mathbf{q})\,.$ (5)

This optimum is taken (see Lemma 5.3), and we refer to the optimal
$\mathbf{q}\in\operatorname{dom}(\varphi)$ as _Gale prices_. We note that
these may not be unique. To justify this term, let us recall the definition of
the Gale demand correspondence (2). The term corresponding to agent $i$ in the
definition of $\varphi(\mathbf{q})$ is the value of the assignments in the
Gale demand correspondence of this agent at prices $\mathbf{q}$ and budget
$b_{i}$. We use the notation $\mathcal{GD}_{i}(\mathbf{q},b_{i})$ for the Gale
demand for the utility $u_{i}$, $i\in{\mathcal{A}}$.

###  2.4 Gale substitute utilities

We now define _Gale substitute_ and _$\Sigma$ -Gale substitute_ utilities, the
crucial classes where we show that the Nash welfare maximizing allocation
recovers at least half of the utility of every agent in any possible
competitive equilibrium (see Theorem 1.3).

######  Definition 2.14.

The utility function $u(\cdot)$ is _Gale-substitutes_ if it satisfies the
following properties:

  1. (i)

for any $b>0$, any $\mathbf{q},\mathbf{q}^{\prime}\in\texttt{FQ}^{u}$, and any
$y\in\mathcal{GD}^{u}(\mathbf{q},b)$, if $\mathbf{q}\geq\mathbf{q}^{\prime}$,
then there exists a $y^{\prime}\in\mathcal{GD}^{u}(\mathbf{q}^{\prime},b)$
such that $y^{\prime}_{j}\leq y_{j}$ whenever $q_{j}^{\prime}=q_{j}$;

  2. (ii)

for any $b\geq b^{\prime}>0$ and $\mathbf{q}\in\texttt{FQ}^{u}$, and for any
$y\in\mathcal{GD}^{u}(\mathbf{q},b)$, there exists a
$y^{\prime}\in\mathcal{GD}^{u}(\mathbf{q},b^{\prime})$ such that
$y^{\prime}\leq y$.

We say that $u(\cdot)$ is $\Sigma$-Gale-substitutes, if it is Gale-substitutes
and the following additional property holds:

$\mbox{if }\mathbf{0}\in\texttt{FQ}^{u}\,,\,b>0\mbox{ and
}\mathbf{q}\in\mathbb{R}_{\geq 0}^{\mathcal{M}},\mbox{ then for any
}y\in\mathcal{GD}(\mathbf{0},b),\exists
y^{\prime}\in\mathcal{GD}^{u}(\mathbf{q},b)\,:\,y^{\prime}\leq y\,.$
($\Sigma$)

##  3 The efficiency of competitive equilibria

We now show the ‘price of anarchy’ result Theorem 3.1. Its proof is inspired
by an argument in Theorem 1 in Brânzei et al. [2022]. Example A.4 shows that
the bound is tight.

######  Theorem 3.1 (Restatement of Theorem 1.1).

Given a Fisher market instance, consider any competitive equilibrium
$(\mathbf{x},\mathbf{p})$ and a Nash welfare maximizing allocation
$\mathbf{y}$. Then,

$\displaystyle\left(\prod_{i\in{\mathcal{A}}}u_{i}(x_{i})^{b_{i}}\right)^{\frac{1}{\sum_{i\in{\mathcal{A}}}b_{i}}}\geq\left(\frac{1}{\mathrm{e}}\right)^{\frac{1}{\mathrm{e}}}\left(\prod_{i\in{\mathcal{A}}}u_{i}(y_{i})^{b_{i}}\right)^{\frac{1}{\sum_{i\in{\mathcal{A}}}b_{i}}}.$

###### Proof.

Without loss of generality, we can assume $\sum_{i\in{\mathcal{A}}}b_{i}=1$.
Note that since $(\mathbf{x},\mathbf{p})$ is a competitive equilibrium, then
$u_{i}(x_{i})\geq\min\left\\{1,\frac{b_{i}}{\large\langle\mathbf{p},y_{i}\large\rangle}\right\\}u_{i}(y_{i})$,
as agent $i$ can use their budget, $b_{i}$, to buy at least
$\frac{b_{i}}{\large\langle\mathbf{p},y_{i}\large\rangle}$ fraction of
$y_{i}$. The lower bound holds because if
$b_{i}<\large\langle\mathbf{p},y_{i}\large\rangle$, then
$u_{i}\left(\frac{b_{i}}{\large\langle\mathbf{p},y_{i}\large\rangle}y_{i}\right)\geq\frac{b_{i}}{\large\langle\mathbf{p},y_{i}\large\rangle}u_{i}(y_{i})$
using concavity and $u_{i}(\mathbf{0})=0$. Thus,

$\displaystyle\sum_{i\in{\mathcal{A}}}{b_{i}}\log\frac{u_{i}(y_{i})}{u_{i}(x_{i})}\leq\sum_{i\in{\mathcal{A}}}{b_{i}}\log\max\left\\{1,\frac{\large\langle\mathbf{p},y_{i}\large\rangle}{b_{i}}\right\\}.$

Let
$b^{\prime}_{i}\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}{\large\langle\mathbf{p},y_{i}\large\rangle}$,
and let ${\mathcal{A}}^{\prime}$ be the set of agents such that
$b^{\prime}_{i}\geq b_{i}$,
$B\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\sum_{i\in\mathcal{A}^{\prime}}b_{i}$,
and
$B^{\prime}\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\sum_{i\in\mathcal{A}^{\prime}}b^{\prime}_{i}$.
Therefore, using the log sum inequality,

$\displaystyle\sum_{i\in{\mathcal{A}}}{b_{i}}\log\frac{u_{i}(y_{i})}{u_{i}(x_{i})}\leq\sum_{i\in{\mathcal{A}}^{\prime}}{b_{i}}\log\frac{b^{\prime}_{i}}{b_{i}}\leq
B\log\frac{B^{\prime}}{B}\,.$

By definition, $B\leq\sum_{i\in{\mathcal{A}}}b_{i}=1$. We also note that
$B^{\prime}\leq\sum_{i\in{\mathcal{A}}}b_{i}^{\prime}=\sum_{i\in{\mathcal{A}}}\large\langle\mathbf{p},y_{i}\large\rangle\leq\sum_{j\in{\mathcal{M}}}p_{j}=\sum_{i\in{\mathcal{A}}}b_{i}=1$.

$\displaystyle\sum_{i\in{\mathcal{A}}}{b_{i}}\log\frac{u_{i}(y_{i})}{u_{i}(x_{i})}\leq\max_{B\leq
1}B\log\frac{1}{B}\leq\frac{1}{\mathrm{e}}\,.$

The statement follows. ∎

##  4 Properties of the Gale demand correspondence

In this section, we show some simple properties of the Gale demand
correspondence, and also derive Theorem 1.2.

######  Lemma 4.1.

For a utility function $u\,:\,\mathbb{R}_{\geq
0}^{\mathcal{M}}\to\mathbb{R}_{\geq 0}$, $b>0$ and
$\mathbf{q}\in\mathbb{R}_{\geq 0}^{\mathcal{M}}$. For any
$y\in\mathbb{R}_{\geq 0}^{\mathcal{M}}$ such that
$\large\langle\mathbf{q},y\large\rangle>b$, there exists
$y^{\prime}\in\mathbb{R}_{\geq 0}^{\mathcal{M}}$ such that
$\large\langle\mathbf{q},y^{\prime}\large\rangle\leq b$ and $b\log
u(y^{\prime})-\large\langle\mathbf{q},y^{\prime}\large\rangle>b\log
u(y)-\large\langle\mathbf{q},y\large\rangle$. In particular, if
$y\in\mathcal{GD}^{u}(\mathbf{q},b)$, then,
$\large\langle\mathbf{q},y\large\rangle\leq b$.

###### Proof.

Let
$y^{\prime}\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}y\cdot\frac{b}{\large\langle\mathbf{q},y\large\rangle}$.
By concavity and $u(\mathbf{0})=0$, we get
$u(y^{\prime})\geq\frac{b}{\large\langle\mathbf{q},y\large\rangle}u(y)$. Thus,

$\displaystyle b\log
u(y^{\prime})-\large\langle\mathbf{q},y^{\prime}\large\rangle$
$\displaystyle\geq b\log
u(y)-b\log\frac{\large\langle\mathbf{q},y\large\rangle}{b}-b$
$\displaystyle>b\log
u(y)-b\left(\frac{\large\langle\mathbf{q},y\large\rangle}{b}-1\right)-b$
$\displaystyle=b\log u(y)-\large\langle\mathbf{q},y\large\rangle\,,$

where the second inequality used $\log(\alpha)<\alpha-1$ for $\alpha>1$. ∎

Next, we derive properties of the price domain $\texttt{FQ}^{u}$.

######  Lemma 4.2.

For any utility function $u\,:\,\mathbb{R}_{\geq
0}^{\mathcal{M}}\to\mathbb{R}_{\geq 0}$ and $b>0$, the following properties of
the price domain $\texttt{FQ}^{u}$ hold:

  1. (i)

for any $\mathbf{q}\in\texttt{FQ}^{u}$, $\max_{y\in\mathbb{R}_{\geq
0}^{\mathcal{M}}}b\log u(y)-\large\langle\mathbf{q},y\large\rangle<+\infty$;

  2. (ii)

$\\{\mathbf{q}\leavevmode\nobreak\ |\leavevmode\nobreak\
\mathbf{q}>0\\}\subseteq\texttt{FQ}^{u}$;

  3. (iii)

for any $\mathbf{q}\geq\mathbf{q}^{\prime}\geq 0$ such that
$\\{j:q^{\prime}_{j}=0\\}=\\{j:q_{j}=0\\}$, $\mathbf{q}\in\texttt{FQ}^{u}$
implies $\mathbf{q}^{\prime}\in\texttt{FQ}^{u}$;

  4. (iv)

for any $\mathbf{p}\geq 0$, if $\max_{\mathbf{p}^{\top}y\leq b}\log
u(y)<+\infty$, then $\mathbf{p}\in\texttt{FQ}^{u}$.

  5. (v)

for any $M>0$, if there is a convergent sequence of prices
$\mathbf{p}^{(k)}\in\texttt{FQ}^{u}$ with $\max_{y\in\mathbb{R}_{\geq
0}^{\mathcal{M}}}b\log u(y)-\large\langle\mathbf{p},y\large\rangle<M$,
$k=1,2,\ldots$ with a limit point $\mathbf{p}^{(k)}\to\bar{\mathbf{p}}$, then
$\bar{\mathbf{p}}\in\texttt{FQ}^{u}$.

###### Proof.

We first prove property (i). According to the definition of $\texttt{FQ}^{u}$,
there exists $b^{\prime}>0$ such that $\max_{y\in\mathbb{R}_{\geq
0}^{\mathcal{M}}}b^{\prime}\log
u(y)-\large\langle\mathbf{q},y^{\prime}\large\rangle<+\infty$. For any $b>0$
and for any $y\in\mathbb{R}_{\geq 0}^{\mathcal{M}}$, if
$\large\langle\mathbf{q},y\large\rangle\leq b$, then $b\log
u(y)-\large\langle\mathbf{q},y\large\rangle<\frac{b}{b^{\prime}}\left(b^{\prime}\log
u(y)-\large\langle\mathbf{q},y\large\rangle\right)+\frac{b-b^{\prime}}{b^{\prime}}\
\large\langle\mathbf{q},y\large\rangle$, which is bounded. Then, the result
follows using Lemma 4.1.

Property (ii) holds as, by Lemma 4.1, $\max_{y\in\mathbb{R}_{\geq
0}^{\mathcal{M}}}b\log u(y)-\mathbf{q}^{\top}y\leq\max_{\mathbf{q}^{\top}x\leq
b}b\log u(x)-b$, which is bounded as $x$ is bounded:
$x_{j}\leq\frac{b}{q_{j}}<\infty$.

To prove property (iii), we let
$\alpha=\min_{q_{j}>0}\\{q^{\prime}_{j}/q_{j}\\}$. Then,
$\max_{y\in\mathbb{R}_{\geq 0}^{\mathcal{M}}}(\alpha b_{i})\log
u_{i}(y_{i})-\mathbf{q}^{\prime\top}y_{i}\leq\max_{y\in\mathbb{R}_{\geq
0}^{\mathcal{M}}}(\alpha b_{i})\log
u_{i}(y_{i})-\alpha\mathbf{q}^{\top}y_{i}<+\infty$.

Property (iv) holds as, for any $y$ such that $\mathbf{p}^{\top}y\leq b$,
$b\log u(y)-\mathbf{q}^{\top}y\leq b\log u(y)<+\infty$.

Finally, let us prove (v). For a contradiction, assume
$\bar{\mathbf{p}}\notin\texttt{FQ}^{u}$, that is, $\sup_{y\in\mathbb{R}_{\geq
0}^{\mathcal{M}}}b\log
u(y)-\large\langle\bar{\mathbf{p}},y\large\rangle=\infty$. Consider a vector
$y\in\mathbb{R}_{\geq 0}^{\mathcal{M}}$ with $b\log
u(y)-\large\langle\bar{\mathbf{p}},y\large\rangle>2M$. Clearly, $y\neq 0$. Let
us select $k$ such that $\|\mathbf{p}^{(k)}-\bar{\mathbf{p}}\|<M/\|y\|$. Then,
$b\log u(y)-\large\langle\mathbf{p}^{(k)},y\large\rangle=b\log
u(y)-\large\langle\bar{\mathbf{p}},y\large\rangle+\large\langle\bar{\mathbf{p}}-\mathbf{p}^{(k)},y\large\rangle>M$,
in contradiction with the assumption on the sequence $\mathbf{p}^{(k)}$. ∎

We next prove Lemma 2.4. See 2.4

###### Proof.

Let
$M\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\sup_{y\in\mathbb{R}_{\geq
0}^{\mathcal{M}}}b\log u(y)-\large\langle\mathbf{p},y\large\rangle$, which
implies the existence of a sequence of allocation
$\\{y^{(k)}\\}_{k=1}^{\infty}$ such that $b\log
u(y^{(k)})-\large\langle\mathbf{p},y^{(k)}\large\rangle$ converges to $M$. We
aim to demonstrate the existence of an allocation $y^{*}$ satisfying $b\log
u(y^{*})-\large\langle\mathbf{p},y^{*}\large\rangle=M$.

According to Lemma 4.2(i), there exists a sequence of $\bar{y}^{(k)}$ such
that $b\log
u(\bar{y}^{(k)})-\large\langle\mathbf{p},\bar{y}^{(k)}\large\rangle$ converges
to $M$, with $0\leq\large\langle\mathbf{p},\bar{y}^{(k)}\large\rangle\leq b$
for all $k$. Thus, we can select a subsequence $\bar{y}^{(i_{k})}$ such that
$b\log
u(\bar{y}^{(i_{k})})-\large\langle\mathbf{p},\bar{y}^{(i_{k})}\large\rangle$
converges to $M$ and $\large\langle\mathbf{p},\bar{y}^{(i_{k})}\large\rangle$
converges to $b^{\prime}$ for some $b^{\prime}\in[0,b]$. Consequently, $b\log
u(x^{(i_{k})})$ converges to $M+b^{\prime}$ as
$\large\langle\mathbf{p},x^{(i_{k})}\large\rangle$ converges to $b^{\prime}$.
By Assumption 1, there exists an allocation $y^{*}$ such that $b\log
u(y^{*})=M+b^{\prime}$ and $\large\langle\mathbf{p},y^{*}\large\rangle\leq
b^{\prime}$. This completes the proof. ∎

We can use the subgradient Karush–Kuhn–Tucker (KKT) conditions to characterize
solutions in the Gale demand correspondence. We refer the reader to Lagrangian
duality and KKT conditions of nondifferentiable functions to Chapter 3 in
Ruszczyński [2011].

######  Lemma 4.3.

For a utility function $u\,:\,\mathbb{R}_{\geq
0}^{\mathcal{M}}\to\mathbb{R}_{\geq 0}$, $b>0$ and
$\mathbf{q}\in\texttt{FQ}^{u}$, let $y\in\mathcal{GD}^{u}(\mathbf{q},b)$.
Then, there exists a supergradient $\mathbf{g}\in\partial^{\wedge}u(y)$ such
that

$g_{j}\leq{q_{j}}\cdot\frac{u(y)}{b}\,,\quad\forall
j\in{\mathcal{M}}\,,\,\mbox{with equality if }y_{j}>0\,,$

Conversely, if such a $\mathbf{g}\in\partial^{\wedge}u(y)$ exists then
$y\in\mathcal{GD}^{u}(\mathbf{q},b)$.

The following lemma compares utilities in the demand correspondence and the
Gale demand correspondence and will play a key role in the proof of Theorem
1.3.

######  Lemma 4.4.

Consider a utility function $u\,:\,\mathbb{R}_{\geq
0}^{\mathcal{M}}\to\mathbb{R}_{\geq 0}$, prices
$\mathbf{p},\mathbf{q}\in\texttt{FQ}^{u}$ such that
$\mathbf{q}\leq\mathbf{p}$. Then, $u(y)\geq\frac{1}{2}u(x)$ for any
$y\in\mathcal{GD}^{u}(\mathbf{q},b)$ and
$x\in{\mathcal{D}}^{u}(\mathbf{p},b)$.

###### Proof.

By Lemma 4.3, there exists a supergradient
$\mathbf{g}\in\partial^{\wedge}u(y)$ such that $g_{j}\leq q_{j}u(y)/b$ with
equality whenever $y_{i}>0$. Therefore,

$\displaystyle u(x)$ $\displaystyle\leq
u(y)+\large\langle\mathbf{g},x-y\large\rangle\leq
u(y)+\frac{u(y)}{b}\large\langle\mathbf{q},x-y\large\rangle$
$\displaystyle\leq
u(y)\left(1+\frac{\large\langle\mathbf{q},x\large\rangle}{b}\right)\leq
u(y)\left(1+\frac{\large\langle\mathbf{p},x\large\rangle}{b}\right)\leq
2u(y)\,.\qed$

###  4.1 Nash welfare as approximate competitive equilibrium

We now derive Theorem 1.2, showing that Nash welfare maximizing allocations
can be seen as approximate competitive equilibria.

######  Theorem 4.5 (Restatement of Theorem 1.2).

Consider a Fisher market instance, and let $\mathbf{y}$ be an allocation
maximizing Nash welfare along with Gale prices $\mathbf{q}$. Then,
$(\mathbf{y},\mathbf{q})$ forms a $2$-demand-approximate competitive
equilibrium. Additionally, when all $b_{i}$’s are identical, the allocation is
$2$-envy-free.

###### Proof.

By Lemma 4.1, all agents satisfy the budget constraints. Additionally, the
market clears by the KKT conditions for (EG). For the approximate competitive
equilibrium, we only need to show
$u_{i}(y_{i})\geq\frac{1}{2}\max_{\large\langle\mathbf{q},x_{i}\large\rangle\leq
b_{i}}u_{i}(x_{i})$ for all agents.

Note that $y_{i}$ maximizes $b_{i}\log
u_{i}(y_{i})-\large\langle\mathbf{q},y_{i}\large\rangle$. By Lemma 4.3, there
is a supergradient $g_{i}$ such that $g_{ij}\leq q_{j}u_{i}(y_{i})/b_{i}$ with
equality whenever $y_{ij}>0$. Then, for any $x_{i}\in\mathbb{R}_{\geq
0}^{\mathcal{M}}$ such that $\large\langle\mathbf{q},x_{i}\large\rangle\leq
b_{i}$,

$u_{i}(x_{i})\leq u_{i}(y_{i})+\large\langle
g_{i},x_{i}-y_{i}\large\rangle\leq
u_{i}(y_{i})+\frac{u_{i}(y_{i})}{b_{i}}\large\langle\mathbf{q},x_{i}-y_{i}\large\rangle\leq\left(2-\frac{\large\langle\mathbf{q},y_{i}\large\rangle}{b_{i}}\right)u_{i}(y_{i})\leq
2u_{i}(y_{i})\,.$

This proves that $(\mathbf{y},\mathbf{q})$ forms a $2$-approximate competitive
equilibrium. Additionally, allocation is $2$-envy-free follows directly from
Lemma 2.12. ∎

##  5 Efficiency of Nash welfare for Gale-substitutes

In this section, we prove Theorem 1.3. We show that for $\Sigma$-Gale
subsitutes utility functions, given a competitive equilibrium
$(\mathbf{x},\mathbf{p})$, there are Gale prices $\mathbf{q}^{\star}$ such
that $\mathbf{q}^{\star}\leq\mathbf{p}$. The statement then follows by Lemma
4.4.

Our first lemma shows a critical property of such utility functions: for every
allocation of goods in the demand correspondence, there is a smaller or equal
allocation of goods in the Gale demand correspondence.

######  Lemma 5.1.

Let $u(\cdot)$ be a $\Sigma$-Gale-substitutes utility and let
$x\in{\mathcal{D}}^{u}(\mathbf{p},b)$ for $\mathbf{p}\in\mathbb{R}_{\geq
0}^{\mathcal{M}}$ and $b>0$. Then, $\mathbf{p}\in\texttt{FQ}^{u}$, and there
exists $y\in\mathcal{GD}^{u}(\mathbf{p},b)$ such that $y\leq x$.

###### Proof.

According to the KKT conditions, there exists $\lambda\geq 0$ and
supergradient $\mathbf{g}\in\partial^{\wedge}u(x)$ such that

$g_{j}\leq\lambda p_{j}\,,\quad\forall j\in{\mathcal{M}}\,,\,\mbox{with
equality if }x_{j}>0\,,$ (6)

and $\large\langle\mathbf{p},x\large\rangle=b$ if $\lambda>0$.

Let us first consider the case $\lambda=0$. Then, $g_{j}\leq 0$ with equality
if $x_{j}>0$, implying that $x=\arg\max_{x\in\mathbb{R}^{\mathcal{M}}}u(x)$.
Consequently, $u(.)$ is satiable; therefore, $\mathbf{0}\in\texttt{FQ}^{u}$
and $x\in\mathcal{GD}^{u}(\mathbf{0},b)$. Now, ($\Sigma$) guarantees the
existence of $y\in\mathcal{GD}^{u}(\mathbf{p},b)$, $y\leq x$. Clearly,
$\texttt{FQ}^{u}=\mathbb{R}_{\geq 0}^{\mathcal{M}}$ in this case.

Next, assume $\lambda>0$. Let us define

$\mathbf{q}\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\frac{\lambda
b}{u(x)}\cdot\mathbf{p}\,.$

Note that $\mathbf{q}\leq\mathbf{p}$. This follows since $\lambda
b=\lambda\large\langle\mathbf{p},x\large\rangle=\large\langle\mathbf{g},x\large\rangle\leq
u(x)$, where the final inequality is by concavity and $u(\mathbf{0})=0$. Thus,

$g_{j}\leq\frac{u(x)}{b}q_{j}\,,\quad\forall j\in{\mathcal{M}}\,,\,\mbox{with
equality if }x_{j}>0\,.$

According to Lemma 4.3, $x\in\mathcal{GD}^{u}(\mathbf{q},b)$.

Note that
$\mathcal{GD}^{u}(\mathbf{q},b)=\mathcal{GD}^{u}(\mathbf{p},u(x)/\lambda)$.
Utilizing Definition 2.14(ii) for
$x\in\mathcal{GD}^{u}(\mathbf{p},u(x)/\lambda)$ and $b\leq u(x)/\lambda$,
there exists $y\in\mathcal{GD}^{u}(\mathbf{p},b)$ such that $y\leq x$ as
required. ∎

We next show that for any competitive equilibrium $(\mathbf{x},\mathbf{p})$,
and any prices $\mathbf{q}\leq\mathbf{p}$, there exist an aggregate Gale
demand such that $\sum_{i\in{\mathcal{A}}}y_{ij}\leq 1$ whenever
$q_{j}=p_{j}$.

######  Lemma 5.2.

Consider a Fisher market instance such that $u_{i}(\cdot)$ is $\Sigma$-Gale-
substitute utilities for all agents. For any competitive equilibrium
$(\mathbf{x},\mathbf{p})$, for any
$\mathbf{q}\in\cap_{i\in{\mathcal{A}}}\texttt{FQ}_{i}$ such that
$\mathbf{q}\leq\mathbf{p}$, there exists
$y_{i}\in\mathcal{GD}_{i}(\mathbf{q},b_{i})$ for all $i\in{\mathcal{A}}$ and
$\sum_{i\in{\mathcal{A}}}y_{ij}\leq 1$ for all $j\in{\mathcal{M}}$ such that
$q_{j}=p_{j}$.

###### Proof.

By Lemma 5.1, there exists $\bar{y}_{i}\in\mathcal{GD}_{i}(\mathbf{p},b_{i})$
for every $i\in{\mathcal{A}}$ such that $\bar{y}_{i}\leq x_{i}$. Using
Definition 2.14(i), there exists $y_{i}\leq\bar{y}_{i}$ such that
$y_{i}\in\mathcal{GD}_{i}(\mathbf{q},b_{i})$ and $y_{ij}\leq\bar{y}_{ij}$ if
$q_{j}=p_{j}$. Thus, if $q_{j}=p_{j}$ then
$\sum_{i\in{\mathcal{A}}}y_{ij}\leq\sum_{i\in{\mathcal{A}}}\bar{y}_{ij}\leq\sum_{i\in{\mathcal{A}}}x_{ij}\leq
1$. ∎

Recall the Lagrangian dual function $\varphi$ defined in (4) on the domain
$\operatorname{dom}(\varphi)=\cap_{i\in{\mathcal{A}}}\texttt{FQ}_{i}$.

$\displaystyle\varphi(\mathbf{q})\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\sum_{i\in{\mathcal{A}}}\max_{y_{i}\in\mathbb{R}_{\geq
0}^{{\mathcal{M}}}}\left(b_{i}\log
u_{i}(y_{i})-\large\langle\mathbf{q},y_{i}\large\rangle\right)+\sum_{j\in{\mathcal{M}}}q_{j}.$

The following properties are easy to verify.

######  Lemma 5.3.

The following hold for the function $\varphi(\cdot)$.

  1. (i)

$\varphi(\mathbf{q})$ is convex.

  2. (ii)

Given $\mathbf{q}\in\operatorname{dom}(\varphi)$, let
$y_{i}\in\mathcal{GD}_{i}(\mathbf{q},b_{i})$ for all $i\in{\mathcal{A}}$.
Then,
$\mathbf{1}-\sum_{i\in{\mathcal{A}}}y_{i}\in\partial^{\vee}\varphi(\mathbf{q})$.

  3. (iii)

The optimum value of (5), that is, the infimum of $\varphi(\mathbf{q})$ is
taken in $\operatorname{dom}(\varphi)$.

###### Proof of Theorem 1.3.

Let $(\mathbf{x},\mathbf{p})$ be a competitive equilibrium solution. Consider
the dual (5) of the Eisenberg-Gale program (EG), i.e.,

$\min_{\mathbf{q}\in\operatorname{dom}(\varphi)}\varphi(\mathbf{q})\,.$

We show that this has an optimal solution with $\mathbf{q}\leq\mathbf{p}$. The
theorem then follows by Lemma 4.4. Let us take any optimal
$q^{\star}\in\operatorname{dom}(\varphi)$; we are done if
$\mathbf{q}^{\star}\leq\mathbf{p}$. Otherwise, let
$J\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\\{j\in{\mathcal{M}}\,:\,\mathbf{q}^{\star}_{j}>p_{j}\\}$,
and let us define $\bar{\mathbf{q}}\in\mathbb{R}_{\geq 0}^{\mathcal{M}}$ as

$\bar{q}_{j}\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\begin{cases}p_{j}\,,&\mbox{if
}j\in J\,,\\\ q^{\star}_{j}\,,&\mbox{if }j\notin J\,.\\\ \end{cases}$

First, assuming $\bar{\mathbf{q}}\in\operatorname{dom}(\varphi)$, we show that
$\bar{\mathbf{q}}$ is also optimal to (5) as claimed.

Let us pick an allocation $\mathbf{y}$ for the prices $\bar{\mathbf{q}}$ as
guaranteed by Lemma 5.2: $\sum_{i\in{\mathcal{A}}}y_{ij}\leq 1$ for all
$j\in{\mathcal{M}}$ with $\bar{q}_{j}=p_{j}$; in particular, for all $j\in J$.
According to Lemma 5.3(ii), we get a subgradient
$\bar{\mathbf{g}}\in\partial^{\vee}\varphi(\bar{\mathbf{q}})$ defined as
$\bar{\mathbf{g}}\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\mathbf{1}-\sum_{i\in{\mathcal{A}}}y_{i}$;
this has the property $\bar{g}_{j}\geq 0$ for all $j\in J$. We then have

$\varphi(\mathbf{q}^{\star})\geq\varphi(\bar{\mathbf{q}})+\large\langle\bar{\mathbf{g}},\mathbf{q}^{\star}-\bar{\mathbf{q}}\large\rangle=\varphi(\bar{\mathbf{q}})+\sum_{j\in
J}\bar{g}_{j}(q^{\star}_{j}-\bar{q}_{j})\geq\varphi(\bar{\mathbf{q}})\,.$

Here, the first inequality is by the definition of subgradients; the equality
uses that $q^{\star}_{j}=\bar{q}_{j}$ if $j\notin J$, and the final inequality
follows since $\bar{g}_{j}\geq 0$ and $q^{\star}_{j}>\bar{q}_{j}$ for $j\in
J$. This shows that $\bar{\mathbf{q}}$ is also an optimal solution to (5),
completing the proof assuming
$\bar{\mathbf{q}}\in\operatorname{dom}(\varphi)$.

It is left to show that $\bar{\mathbf{q}}\in\operatorname{dom}(\varphi)$. Let
$K\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\\{j\in{\mathcal{M}}\,:\,\mathbf{q}^{\star}_{j}=0<p_{j}\\}$.
Clearly, $K\cap J=\emptyset$. If $K=\emptyset$, then Lemma 4.2(iii) already
implies $\bar{\mathbf{q}}\in\texttt{FQ}^{u}$, since
$\mathbf{p}\geq\bar{\mathbf{q}}$ and
$\operatorname{supp}(\bar{\mathbf{q}})=\operatorname{supp}(\mathbf{p})$.
Otherwise, for $k=1,2,\ldots$, let us define
$\mathbf{q}^{(k)}\in\mathbb{R}_{\geq 0}^{\mathcal{M}}$ as

$q_{j}^{(k)}\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\begin{cases}p_{j}\,,&\mbox{if
}j\in J\,,\\\ \frac{p_{j}}{k}\,,&\mbox{if }j\in K\,,\\\
q^{\star}_{j}\,,&\mbox{if }j\notin J\cup K\,.\\\ \end{cases}$

We have $\mathbf{q}^{(k)}\in\texttt{FQ}^{u}$ again by Lemma 4.2(iii). As in
the first part, we take a subgradient $\mathbf{g}^{(k)}$ as guaranteed by
Lemma 5.3(ii), with the properties that $\bar{g}_{j}\geq 0$ for all $j\in J$
and also $\mathbf{g}^{(k)}\leq\mathbf{1}$. We can write

$\varphi(\mathbf{q}^{\star})\geq\varphi(\mathbf{q}^{(k)})+\large\langle\mathbf{g}^{(k)},\mathbf{q}^{\star}-\mathbf{q}^{(k)}\large\rangle=\varphi(\mathbf{q}^{(k)})+\sum_{j\in
J}\bar{g}_{j}(q^{\star}_{j}-q^{(k)}_{j})-\sum_{j\in
K}\bar{g}_{j}q^{(k)}_{j}\geq\varphi(\mathbf{q}^{(k)})-\frac{\|p\|_{\infty}}{k}\,.$

Here, we use in the first equality that $q^{\star}_{j}=q^{(k)}_{j}$ for
$j\notin J\cup K$, and $q^{\star}_{j}=0$ for $j\in K$. The last inequality
uses $\bar{g}_{j}\leq 1$ and the definition $q^{(k)}_{j}=p_{j}/(k+1)$. Thus,
Lemma 4.2(v) is applicable with
$M=\varphi(\mathbf{q}^{\star})+\|p\|_{\infty}$, using that for each
$j\in{\mathcal{M}}$, $\max_{y_{i}\in\mathbb{R}_{\geq
0}^{\mathcal{M}}}b_{i}\log
u_{i}(y_{i})-\large\langle\mathbf{q}^{(k)},y_{i}\large\rangle\leq\varphi(\mathbf{q}^{(k)})$.
This shows that $\bar{\mathbf{q}}\in\texttt{FQ}_{i}$ for all
$i\in{\mathcal{M}}$, and therefore
$\bar{\mathbf{q}}\in\operatorname{dom}(\varphi)=\cap_{i\in{\mathcal{M}}}\texttt{FQ}_{i}$.
∎

##  6 Separable utilities are $\Sigma$-Gale-substitutes

In this section, we prove Theorem 1.4. See 1.4 Recall the following simple
monotonicity property of supergradients of univariate concave functions.

######  Lemma 6.1.

Let $v\,:\,\mathbb{R}\to\mathbb{R}$ be a univariate concave function,
$\alpha,\alpha^{\prime}\in\operatorname{dom}(f)$, and
$g\in\partial^{\wedge}v(\alpha)$,
$g^{\prime}\in\partial^{\wedge}v(\alpha^{\prime})$. Then,
$\alpha<\alpha^{\prime}$ implies $g\geq g^{\prime}$. Conversely, if
$g>g^{\prime}$, then $\alpha\leq\alpha^{\prime}$.

We now adapt Lemma 4.3 to separable utilities.

######  Lemma 6.2.

Let $u(x)=\sum_{j\in{\mathcal{M}}}v_{j}(x_{j})$ be a separable utility
function. For any $b>0$, $\mathbf{q}\in\texttt{FQ}^{u}$,
$y\in\mathcal{GD}^{u}(\mathbf{q},b)$, we have $u(y)>0$. Further,
$y\in\mathcal{GD}^{u}(b,\mathbf{q})$ if and only if there exist supergradients
$g_{j}\in\partial^{\wedge}u_{j}(y_{j})$, $j\in{\mathcal{M}}$ satisfying

  1. (i)

$g_{j}\geq 0$; and

  2. (ii)

$g_{j}\leq q_{j}u(y)/b$ with equality whenever $y_{j}>0$.

The proof of Theorem 1.4 follows by the next three lemmas, that prove the
three properties in Definition 2.14 for separable utilities: property (i) in
Lemma 6.3, property (ii) in Lemma 6.4, and property ($\Sigma$) in Lemma 6.5.

######  Lemma 6.3.

Let $u(x)=\sum_{j\in{\mathcal{M}}}v_{j}(x_{j})$ be a separable utility
function, and let $b>0$, $\mathbf{q},\mathbf{q}^{\prime}\in\texttt{FQ}^{u}$
and $y\in\mathcal{GD}^{u}(\mathbf{q},b)$. If
$\mathbf{q}\geq\mathbf{q}^{\prime}$, then there exists a
$y^{\prime}\in\mathcal{GD}^{u}(\mathbf{q}^{\prime},b)$ such that
$y^{\prime}_{j}\leq y_{j}$ whenever $q_{j}^{\prime}=q_{j}$.

###### Proof.

Let
$J\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\\{j\in{\mathcal{M}}\,:\,q^{\prime}_{j}=q_{j}\\}$.
Let us select $y^{\prime}\in\mathcal{GD}^{u}(\mathbf{q}^{\prime},b)$
minimizing the potential
$\Psi(y^{\prime})\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\sum_{j\in
J}(y^{\prime}_{j}-y_{j})^{+}$. Our goal is to show $\Psi(y^{\prime})=0$.
Throughout the proof, let
$g^{\prime}_{j}\in\partial^{\wedge}v_{j}(y^{\prime}_{j})$ and
$g_{j}\in\partial^{\wedge}v_{j}(y_{j})$ as in Lemma 6.2.

First, we show $u(y^{\prime})\geq u(y)$. Since $u(y)>0$ (Lemma 6.2), there is
a good $j\in{\mathcal{M}}$ with $y_{j}>0$. Also by Lemma 6.2, for such a good
$j$ we have

$bg^{\prime}_{j}/u(y^{\prime})\leq q^{\prime}_{j}\leq q_{j}=bg_{j}/u(y)\,.$

implying the claimed $u(y^{\prime})\geq u(y)$.

Using the above, for any $j\in J$ where $y^{\prime}_{j}>0$,

$g^{\prime}_{j}=\frac{q^{\prime}_{j}}{b}u(y^{\prime})\geq\frac{q_{j}}{b}u(y)\geq
g_{j}\,.$ (7)

Let us first consider the case $u(y^{\prime})>u(y)$. For all $j\in J$ with
$q^{\prime}_{j}=q_{j}>0$, we get $g^{\prime}_{j}>g_{j}$. By Lemma 6.1,
$y^{\prime}_{j}\leq y_{j}$ follows for such goods $j$. On the other hand, if
$q^{\prime}_{j}=q_{j}=0$, then this implies $g^{\prime}_{j}=g_{j}=0$. For such
indices, if $y^{\prime}_{j}>y_{j}$, then replacing $y^{\prime}_{j}$ by $y_{j}$
results in another bundle
$y^{\prime\prime}\in\mathcal{GD}^{u}(\mathbf{q}^{\prime},b)$ with
$\Psi(y^{\prime\prime})<\Psi(y^{\prime})$, a contradiction.

For the rest of the proof, let us assume that $u(y^{\prime})=u(y)$. We next
show $y^{\prime}_{j}\geq y_{j}$ for all $j\in{\mathcal{M}}\setminus J$, that
is, for all goods with $q^{\prime}_{j}<q_{j}$. This is clearly true if
$y_{j}=0$. Whenever $y_{j}>0$ for such an index, we have

$g^{\prime}_{j}=\frac{q^{\prime}_{j}}{b}u(y^{\prime})<\frac{q_{j}}{b}u(y)=g_{j}\,,$

and therefore $y^{\prime}_{j}\geq y_{j}$ by Lemma 6.1. By monotonicity,
$v_{j}(y^{\prime}_{j})\geq v_{j}(y_{j})$ for all $j\in{\mathcal{M}}\setminus
J$. Since $u(y^{\prime})=u(y)$, we have $\sum_{j\in
J}v_{j}(y^{\prime}_{j})\leq\sum_{j\in J}v_{j}(y_{j})$.

From (7), it follows that $g^{\prime}_{j}=g_{j}$ for all $j\in J$ with
$y^{\prime}_{j}>0$. This is because the first inequality is now equality, and
the second inequality may only be strict if $y_{j}=0<y^{\prime}_{j}$. By Lemma
6.1, $g_{j}\geq g^{\prime}_{j}$ in this case, leading to a contradiction.

Assume for a contradiction $\Psi(y^{\prime})>0$, and let us select an index
$k\in J$ with $y^{\prime}_{k}>y_{k}$. If $v_{k}(y^{\prime}_{k})=v_{k}(y_{k})$,
then we get a contradiction, because changing $y^{\prime}_{k}$ to $y_{k}$
would preserve the the optimality conditions in Lemma 6.2, while decreasing
the potential $\Psi(y^{\prime})$. Thus, $v_{k}(y^{\prime}_{k})>v_{k}(y_{k})$.
By $\sum_{j\in J}v_{j}(y^{\prime}_{j})\leq\sum_{j\in J}v_{j}(y_{j})$, there
must be an index $j\in J$ with $v_{j}(y^{\prime}_{j})<v_{j}(y_{j})$. We can
now find suitable $\varepsilon_{k},\varepsilon_{j}>0$ such that
$v_{k}(y^{\prime}_{k}-\varepsilon_{k})+v_{j}(y^{\prime}_{j}+\varepsilon_{j})=v_{k}(y^{\prime}_{k})+v_{j}(y^{\prime}_{j})$,
and $y^{\prime}_{j}+\varepsilon_{j}\leq y_{j}$. This modified solution
$y^{\prime\prime}$ satisfies the optimality conditions but
$\Psi(y^{\prime\prime})<\Psi(y^{\prime})$, again leading to a contradiction. ∎

######  Lemma 6.4.

Let $u(x)=\sum_{j\in{\mathcal{M}}}v_{j}(x_{j})$ be a separable utility
function, $b>b^{\prime}>0$ and $\mathbf{q}\in\texttt{FQ}^{u}$. Then, for any
$y\in\mathcal{GD}^{u}(\mathbf{q},b)$, there exists a
$y^{\prime}\in\mathcal{GD}^{u}(\mathbf{q},b^{\prime})$ such that
$y^{\prime}\leq y$.

###### Proof.

We argue similarly as in the previous proof: we pick
$y^{\prime}\in\mathcal{GD}^{u}(\mathbf{q},b^{\prime})$ which minimizes
$\Psi(y^{\prime})\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\sum_{j\in
J}(y^{\prime}_{j}-y_{j})^{+}$, and show that $\Psi(y^{\prime})=0$.

First, we show that ${u(y)}/{b}\leq{u(y^{\prime})}/{b^{\prime}}$. For a
contradiction, suppose ${u(y)}/{b}>{u(y^{\prime})}/{b^{\prime}}$. If
$y_{j}>0$, then, by Lemma 6.2

$g_{j}=\frac{q_{j}u(y)}{b}>\frac{q_{j}u(y^{\prime})}{b^{\prime}}\geq
g^{\prime}_{j},$

which implies $v_{j}(y_{j})\leq v_{j}(y^{\prime}_{j})$ whenever $y_{j}>0$
(Lemma 6.1), and therefore, $u(y)\leq u(y^{\prime})$. Together with
$b>b^{\prime}$, this implies ${u(y)}/{b}\leq{u(y^{\prime})}/{b^{\prime}}$, a
contradiction.

Whenever $y^{\prime}_{j}>0$, we now have

$g^{\prime}_{j}=\frac{q_{j}u(y^{\prime})}{b^{\prime}}\geq\frac{q_{j}u(y)}{b}\geq
g_{j}\,.$ (8)

Assume first $u(y^{\prime})/b^{\prime}>u(y)/b$. If $q^{\prime}_{j}=q_{j}>0$,
then this inequality is strict, and therefore $y^{\prime}_{j}\leq y_{j}$ for
all $j\in{\mathcal{M}}$ follows by Lemma 6.1. If $q^{\prime}_{j}=q_{j}=0$,
then $g^{\prime}_{j}=g_{j}=0$. If $y^{\prime}_{j}>y_{j}$ for such a good $j$,
we can decrease $y^{\prime}_{j}$ to $y_{j}$ and thereby get an optimal
allocation with strictly smaller $\Psi(y^{\prime})$ value, leading to a
contradiction. This completes the proof for $u(y^{\prime})/b^{\prime}>u(y)/b$.

For the rest, we may assume $u(y^{\prime})/b^{\prime}=u(y)/b$. Now,
$g^{\prime}_{j}=g_{j}$ must hold whenever $y^{\prime}_{j}>0$. This is because
the first inequality in (8) is equality, and if the second is strict, then
$y_{j}=0<y^{\prime}_{j}$ would give a contradiction to $g^{\prime}_{j}>g_{j}$.

Assume for a contradiction $\Psi(y^{\prime})>0$, and let us pick
$k\in{\mathcal{M}}$ with $y^{\prime}_{k}>y_{k}$. The equality
$u(y^{\prime})/b^{\prime}=u(y)/b$ and $b^{\prime}<b$ gives
$u(y^{\prime})<u(y)$. We can derive a contradiction by decreasing
$y^{\prime}_{k}$ and potentially increasing an $y^{\prime}_{j}$ similarly as
in the proof of Lemma (6.3). ∎

######  Lemma 6.5.

Let $u(x)=\sum_{j\in{\mathcal{M}}}v_{j}(x_{j})$ be a separable utility
function such that $\mathbf{0}\in\texttt{FQ}^{u}$. Then, for any
$\mathbf{q}\geq 0$, $b>0$ and any $y\in\mathcal{GD}^{u}(\mathbf{0},b)$, there
exists a $y^{\prime}\in\mathcal{GD}^{u}(\mathbf{q},b)$ such that
$y^{\prime}\leq y$.

###### Proof.

$\mathbf{0}\in\texttt{FQ}^{u}$ implies $\sup_{y\in\mathbb{R}_{\geq
0}^{\mathcal{M}}}u(y)<\infty$. Therefore, $\texttt{FQ}^{u}=\mathbb{R}_{\geq
0}^{\mathcal{M}}$; in particular, $\mathbf{q}\in\texttt{FQ}^{u}$. Let us pick
$y^{\prime}\in\mathcal{GD}^{u}(\mathbf{q},b)$ such that
$\sum_{j\in{\mathcal{M}}}y^{\prime}_{j}$ is minimal.

Note that $u(y)=\sup_{y\in\mathbb{R}_{\geq 0}^{\mathcal{M}}}u(y)$. In
particular, for any $\alpha\geq y_{j}$, $v_{j}(\alpha)=v_{j}(y_{j})$. For a
contradiction, assume there exists a $k\in{\mathcal{M}}$ with
$y_{k}<y^{\prime}_{k}$. Then, reducing $y^{\prime}_{k}$ to $y_{k}$ may only
increase $b\log
u(y^{\prime})-\large\langle\mathbf{q},y^{\prime}\large\rangle$, while
decreasing $\sum_{j\in{\mathcal{M}}}y^{\prime}_{j}$. This contradicts the
choice of $y^{\prime}$. ∎

##  7 Generalized network utilities

In this section, we prove Theorem 1.5. We will first need a characterization
of subgradients by linear programming duality. We state this in a more general
form. The proof is based on LP duality and is given in Appendix B.

######  Lemma 7.1.

Let $\mathbf{A}\in\mathbb{R}^{k\times\ell}$, $\mathbf{B}\in\mathbb{R}^{k\times
m}$, $c\in\mathbb{R}^{\ell}$, $b\in\mathbb{R}^{k}$. Let
$\mathcal{D}\subseteq\mathbb{R}^{m}$ be the set of vectors
$x\in\mathbb{R}^{m}$ such that the following parametric linear program is
feasible and bounded, and let us define $\varphi:\mathcal{D}\to\mathbb{R}$
such that $\varphi(x)$ is the optimum value of this program:

$\displaystyle\max\leavevmode\nobreak$ $\displaystyle c^{\top}z$ (9)
$\displaystyle\mathbf{A}z$ $\displaystyle\leq\mathbf{B}x+b$ $\displaystyle z$
$\displaystyle\geq 0$

Then, for every $x\in\mathcal{D}$, $g\in\partial^{\wedge}\varphi(x)$ if and
only if $g=\mathbf{B}^{\top}\pi$ for an optimal solution
$\pi\in\mathbb{R}_{\geq 0}^{k}$ to the dual linear program

$\displaystyle\min\leavevmode\nobreak$ $\displaystyle
x^{\top}\mathbf{B}^{\top}\pi+b^{\top}\pi$ (10)
$\displaystyle\mathbf{A}^{\top}\pi$ $\displaystyle\geq c$ $\displaystyle\pi$
$\displaystyle\geq 0\,.$

Consider a generalized flow instance defined in a graph $G=(V,E)$, sink $t\in
V$, capacities $h\in\mathbb{R}_{\geq 0}^{E}$, gain factors
$\gamma\in\mathbb{R}_{>0}^{E}$ and supply set $S={\mathcal{M}}$. For the rest
of this section, let $u\,:\,\mathbb{R}_{\geq
0}^{\mathcal{M}}\to\mathbb{R}_{\geq 0}$ be a generalized network utility
function defined in the form $\operatorname{GenflowLP}(x)$ in Section 2.

Using Lemma 7.1 and complementary slackness, we get the following
characterization of subgradients of generalized network utility functions.
Note that for a generalized network utility function, the domain is
$\mathcal{D}=\mathbb{R}_{\geq 0}^{\mathcal{M}}$, because $f=0$ is always a
feasible solution to $\operatorname{GenflowLP}(x)$, and the definition assumes
that the objective is always bounded.

######  Lemma 7.2.

Let $u\,:\,\mathbb{R}_{\geq 0}^{\mathcal{M}}\to\mathbb{R}_{+}$ be a
generalized network utility function defined in the form
$\operatorname{GenflowLP}(x)$ for $S={\mathcal{M}}$. For a given supply vector
$x\in\mathbb{R}_{\geq 0}^{\mathcal{M}}$, let $f$ be an optimal solution to
$\operatorname{GenflowLP}(x)$. Then, $g\in\partial^{\wedge}u(x)$ if and only
if $g=\pi|_{\mathcal{M}}$ for a vector $\pi\in\mathbb{R}_{\geq 0}^{V}$ that
satisfies

$\displaystyle\gamma_{e}\pi_{w}-\pi_{v}$ $\displaystyle=0\,,\quad\forall
e=(v,w)\in E:h_{e}>f_{e}>0\,,$ (11) $\displaystyle\gamma_{e}\pi_{w}-\pi_{v}$
$\displaystyle\leq 0\,,\quad\forall e=(v,w)\in E:f_{e}=0\,,$
$\displaystyle\gamma_{e}\pi_{w}-\pi_{v}$ $\displaystyle\geq 0\,,\quad\forall
e=(v,w)\in E:f_{e}=h_{e}\,,$ $\displaystyle\pi_{v}$
$\displaystyle=0\,,\quad\forall
v\in{\mathcal{M}}:\operatorname{net}_{f}(v)>-x_{v}\mbox{ or }v\in
V\setminus({\mathcal{M}}\cup t):\operatorname{net}_{f}(v)>0\,,$
$\displaystyle\pi_{t}$ $\displaystyle=1\,,$ $\displaystyle\pi$
$\displaystyle\geq 0\,.$

In accordance with this lemma, we say that $f\in\mathbb{R}^{E}$ and
$\pi\in\mathbb{R}^{V}$ form a _fitting pair with respect to $x$_, if $f$ is a
feasible generalized flow with supply $x$, and $\pi$ satisfies (11). Note that
this implies that $f$ and $\pi$ are primal and dual optimal solutions to
$\operatorname{GenflowLP}(x)$. Further, $g\in\partial^{\wedge}u(x)$ if and
only if $g$ is the restriction of $\pi$ to ${\mathcal{M}}$ for a fitting pair
$(f,\pi)$ with respect to $x$.

For every arc $e=(v,w)\in E$, let us define the _reverse arc_
$\overleftarrow{e}=(v,w)$ with gain factor
$\gamma_{\overleftarrow{e}}=1/\gamma_{e}$. By sending $\alpha$ units of flow
on $\overleftarrow{e}$ we mean decreasing the flow value on $e$ by
$\gamma_{e}\alpha$. Given a fitting pair $(f,\pi)$ with respect to $x$, we
define the _auxiliary network_
$G^{\textrm{aux}}_{f,\pi}=(V,E^{\textrm{aux}}_{f,\pi})$ by

$E^{\textrm{aux}}_{f,\pi}\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\left\\{e=(v,w)\in
E\,:\,\gamma_{e}\pi_{w}-\pi_{v}=0\mbox{ and
}f_{e}<h_{e}\right\\}\cup\left\\{\overleftarrow{e}\,:\,e\in
E\,:\,\gamma_{e}\pi_{w}-\pi_{v}=0\mbox{ and }0<f_{e}\right\\}\,.$

In the proof of Theorem 1.5, we use two flow subroutines in the generalized
flow network. The first one starts with a fitting pair $(f,\pi)$ with respect
to a demand vector $x$, and outputs a flow $f^{\prime}$ for a decreased demand
vector $x^{\prime}$ such that the flow value
$\operatorname{net}_{f^{\prime}}(t)$ is decreased to the smallest possible
amount while maintaining $(f^{\prime},\pi)$ as a fitting pair.

Input: $x\in\mathbb{R}_{\geq 0}^{\mathcal{M}}$, and a fitting pair $(f,\pi)$
with respect to $x$

Output: A supply vector $0\leq x^{\prime}\leq x$ and a feasible generalized
flow $f^{\prime}$ such that $(f^{\prime},\pi)$ is a fitting pair with respect
to $x^{\prime}$, and subject to this, $\operatorname{net}_{f^{\prime}}(t)$ is
minimal.

Algorithm 1 Pullback-Flow

######  Lemma 7.3.

Pullback-Flow can be formulated as a linear program. For the output flow
$f^{\prime}$, the auxiliary graph $E^{\textrm{aux}}_{f^{\prime},\pi}$ does not
contain any directed paths from the sink $t$ to
$\operatorname{supp}(x^{\prime})$.

###### Proof.

When fixing $\pi$, the requirement that $(f^{\prime},\pi)$ be a fitting pair
can be formulated by linear constraints on $f^{\prime}$. For example, for
every arc $e=(v,w)$, if $\gamma_{e}\pi_{w}-\pi_{v}<0$ then we require
$f^{\prime}_{e}=0$, and if $\gamma_{e}\pi_{w}-\pi_{v}>0$ then
$f^{\prime}_{e}=h_{e}$; if $\gamma_{e}\pi_{w}-\pi_{v}=0$ then any value $0\leq
f^{\prime}_{e}\leq h_{e}$ is allowed. For the second part, assume for a
contradiction that $E^{\textrm{aux}}_{f^{\prime},\pi}$ contains a directed
path $P$ from $t$ to a node $j\in{\mathcal{M}}$ with $x^{\prime}_{j}>0$. Then,
we can send a small amount of flow along this path by maintaining the flow
balance on every intermediate node, and decreasing
$\operatorname{net}_{f^{\prime}}(t)$ and $x^{\prime}_{j}$ by positive amounts.
This contradicts the minimality of $\operatorname{net}_{f^{\prime}}(t)$. ∎

######  Remark 7.4.

Pullback-Flow can be in fact formulated as a (classical) maximum flow problem.
To see this, one can use the standard generalized flow relabelling technique,
first introduced by Glover and Klingman [1973], see also e.g., Goldberg et al.
[1991], Olver and Végh [2020]). That is, we multiply the flow at node $v$ by
$\pi_{v}$ and replacing $\gamma_{e}$ by $\gamma_{e}\pi_{w}/\pi_{v}$ for every
$e=(v,w)\in E$. On every arc, we fix $f^{\prime}_{e}$ to the upper or lower
bound unless $\gamma_{e}\pi_{w}-\pi_{v}=0$, in which case the relabelled gain
factor is 1.

Our second subroutine aims to increase the supply at a designated node
$k\in{\mathcal{M}}$ while the supply at all other goods is non-increasing, and
the flow value $\operatorname{net}_{f}(t)$ is non-decreasing. The goal is
again to maintain a fitting pair $(f^{\prime},\pi)$ for a demand vector
$x^{\prime}$.

Input: $x\in\mathbb{R}_{\geq 0}^{\mathcal{M}}$, and a fitting pair $(f,\pi)$
with respect to $x$, and a good $k\in{\mathcal{M}}$ such that $\pi_{k}>0$.

Output: A supply vector $x^{\prime}\in\mathbb{R}_{\geq 0}^{\mathcal{M}}$ such
that $x^{\prime}_{k}\geq x_{k}$ and $x^{\prime}_{j}\leq x_{j}$ if
$j\in{\mathcal{M}}\setminus\\{k\\}$, and a feasible generalized flow
$f^{\prime}$ such that $(f^{\prime},\pi)$ is a fitting pair with respect to
$x^{\prime}$,
$\operatorname{net}_{f}(t^{\prime})\geq\operatorname{net}_{f}(t)$, and subject
to this, $x^{\prime}_{k}$ is maximal.

Algorithm 2 Reroute-Flow

The following lemma can be derived similarly to Lemma 7.3.

######  Lemma 7.5.

Reroute-Flow can be formulated as a linear program. For the output flow
$f^{\prime}$, the auxiliary graph $E^{\textrm{aux}}_{f^{\prime},\pi}$ does not
contain any directed path from $k$ to the set
$(\operatorname{supp}(x^{\prime})\setminus\\{k\\})\cup\\{t\\}$.

From Lemma 4.3, we get the following.

######  Lemma 7.6.

Consider a generalized network utility function $u\,:\,\mathbb{R}_{\geq
0}^{\mathcal{M}}\to\mathbb{R}_{\geq 0}$, $b>0$ and
$\mathbf{q}\in\texttt{FQ}^{u}$, and $x\in\mathbb{R}_{\geq 0}^{\mathcal{M}}$.
Then, $x\in\mathcal{GD}^{u}(b,\mathbf{q})$ if and only if there exists a
fitting pair $(f,\pi)$ with respect to $x$ such that
$u(x)=\operatorname{net}_{f}(t)$ and

$\pi_{j}\leq\frac{q_{j}}{b}\cdot u(x)\,\quad\forall
j\in{\mathcal{M}}\,,\,\text{ with equality for }j\in\operatorname{supp}(x)\,.$
(12)

Theorem 1.5 follows by showing the two properties in Definition 2.14 in Lemmas
7.7 and Lemma 7.8 below. We start by property _(ii)_.

######  Lemma 7.7.

Let $u\,:\,\mathbb{R}_{\geq 0}^{\mathcal{M}}\to\mathbb{R}_{\geq 0}$ be a
generalized network utility function, $b>b^{\prime}>0$ and
$\mathbf{q}\in\texttt{FQ}^{u}$, and let $x\in\mathcal{GD}^{u}(b,\mathbf{q})$.
Then, there exists $x^{\prime}\in\mathcal{GD}^{u}(b^{\prime},\mathbf{q})$ such
that $x^{\prime}\leq x$.

###### Proof.

The proof is given by a finite algorithm, shown as Algorithm 3. We start from
fitting pair $(f,\pi)$ with respect to $x$ as in Lemma 7.6. Thus, the
inequality (12) holds for $\pi$, $x$, $\mathbf{q}$ and $b$. If $u(x)=0$, then
we must have $\pi_{j}=0$ for all $j\in{\mathcal{M}}$ and thus (12) holds also
when replacing $b$ by $b^{\prime}$, and therefore we can return
$x^{\prime}=x$. For the rest of the proof, let us assume $u(x)>0$. Similarly,
we can assume that $\mathbf{q}\neq\mathbf{0}$. Note that $\pi_{j}>0$ for every
$j\in\operatorname{supp}(x)\cap\operatorname{supp}(\mathbf{q})$. When
replacing $b$ by $b^{\prime}$, all inequalities with in (12) with $q_{j}>0$
become strict; the ratio of the right and left hand sides will be
$\alpha\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}b/b^{\prime}>1$
for all $j\in\operatorname{supp}(x)\cap\operatorname{supp}(\mathbf{q})$. Also,
recall $u(x)=\operatorname{net}_{f}(t)$.

Algorithm 3 alternates between two operations: changing $x$ and $f$ while
keeping $\pi$ unchanged; and changing the dual $\pi$ while keeping $x$ and $f$
unchanged. Throughout, it maintains a fitting pair with respect to a
decreasing vector $x^{\prime}$, such that the required equalities in (12) are
gradually restored.

In the first step, we call $\textnormal{{Pullback-Flow}}(x,f,\pi)$ to get
demands $x^{\prime}\leq x$ and a corresponding fitting pair
$(f^{\prime},\pi)$. We have
$u(x^{\prime})=\operatorname{net}_{f^{\prime}}(t)\leq\operatorname{net}_{f}(t)=u(x)$.
Note that $\frac{q_{j}}{b^{\prime}}u(x^{\prime})/\pi_{j}$ is the same value
$\alpha^{\prime}\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\alpha
u(x^{\prime})/u(x)$ for every
$j\in\operatorname{supp}(x^{\prime})\cap\operatorname{supp}(\mathbf{q})$.

#### Case I:

If $\alpha^{\prime}\leq 1$, then we choose
$\lambda\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}(\alpha-1)/(\alpha-\alpha^{\prime})\in[0,1]$
such that $\lambda\alpha+(1-\lambda)\alpha^{\prime}=1$. Then,
$x^{\prime\prime}\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\lambda
x^{\prime}+(1-\lambda)x$ and the flow
$f^{\prime\prime}\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\lambda
f^{\prime}+(1-\lambda)f$ satisfy that $(f^{\prime\prime},\pi)$ is a fitting
pair with respect to $x^{\prime\prime}$, and (12) holds for $\pi$,
$x^{\prime\prime}$ and $b^{\prime}$. Thus, we can terminate by outputting
$x^{\prime\prime}\in\mathcal{GD}^{u}(b^{\prime},\mathbf{q})$.

#### Case II:

If $\alpha^{\prime}>1$, then we update the dual $\pi$ to $\pi^{\prime}$ as
follows. Let $T\supseteq\operatorname{supp}(x^{\prime})$ be the set of nodes
that can reach $\operatorname{supp}(x^{\prime})$ in the auxiliary graph
$(G,E^{\textrm{aux}}_{f^{\prime},\pi})$. By Lemma 7.3, $t\notin T$. Let us
define $\pi^{\prime}$ such that
$\pi^{\prime}_{v}\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\pi_{v}$
for $v\notin T$ and
$\pi^{\prime}_{v}\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}\delta\pi_{v}$
for $v\in T$ for the largest value $1\leq\delta\leq\alpha^{\prime}$ such that
$(f^{\prime},\pi^{\prime})$ is a fitting pair.

We claim that $\delta^{\prime}>1$. Recall that fitting pairs are required to
satisfy (11). The sign of $\gamma_{e}\pi^{\prime}_{w}-\pi^{\prime}_{v}$ is the
same as the sign of $\gamma_{e}\pi_{w}-\pi_{v}$ for all arcs $e=(v,w)$ with
both endpoints inside $T$ or outside $T$. There is no arc $e=(v,w)$ entering
or leaving $T$ with $0<f^{\prime}_{e}<u_{e}$, since $e,\overleftarrow{e}\in
E^{\textrm{aux}}_{f^{\prime},\pi}$ for all such arcs. For every arc $e=(v,w)$
entering $T$ with $f^{\prime}_{e}=0$, we must have
$\gamma_{e}\pi_{w}-\pi_{v}<0$ so that $e\notin
E^{\textrm{aux}}_{f^{\prime},\pi}$. Similarly, for every arc $e=(v,w)$ leaving
$T$ with $f^{\prime}_{e}=u_{e}$, we must have $\gamma_{e}\pi_{w}-\pi_{v}>0$.
Hence, we can always choose $\delta^{\prime}>1$. If
$\delta^{\prime}=\alpha^{\prime}$, then $\pi^{\prime}$, $x^{\prime}$,
$\mathbf{q}$ and $b^{\prime}$ satisfy (12), since the right hand side for all
$j\in\operatorname{supp}(x^{\prime})$ has increased by a factor
$\alpha^{\prime}$, and therefore equality holds for all these indices. We can
therefore conclude $x^{\prime}\in\mathcal{GD}^{u}(b,\mathbf{q})$ and terminate
by outputting $x^{\prime}$.

In case $\delta^{\prime}<\alpha^{\prime}$, then (12) holds with strict
inequality for all $j$ for $\pi^{\prime}$, $x^{\prime}$, $\mathbf{q}$, and
$b^{\prime}$. Moreover, the ratio of the right hand side and the left hand
side is the same for all
$j\in\operatorname{supp}(x^{\prime})\cap\operatorname{supp}(\mathbf{q})$,
namely, $\alpha^{\prime}/\delta^{\prime}<\alpha$. We now restart the above
procedure with $(f^{\prime},\pi^{\prime})$ and $x^{\prime}$ in place of
$(f,\pi)$ and $x$.

We claim that the algorithm terminates in a finite number of iterations. This
holds because the linear program Pullback-Flow only depends on the sign
pattern of $\gamma_{e}\pi_{w}-\pi_{v}$ for the arcs $e=(w,v)$ and on
$\operatorname{supp}(x)$. There are $3^{|E|}$ possible sign patterns; the sest
$\operatorname{supp}(x)$ is monotone decreasing and therefore there are at
most $|{\mathcal{M}}|$ different possibilities. The same configuration of arc
sign patterns and $\operatorname{supp}(x)$ cannot occur twice, because
$u(x^{\prime})=\operatorname{net}_{f^{\prime}}(t)$ is strictly decreasing in
every iteration of the algorithm. Hence, after a finite number of iterations
we arrive at $\pi^{\prime}$ and $x^{\prime}$ satisfying (12) for $b^{\prime}$.
Since $x^{\prime}$ is decreasing throughout, we have $x^{\prime}\leq x$ for
the input supply vector $x$, as required. ∎

Input: $\mathbf{q}\in\texttt{FQ}{}^{u}$, $b,b^{\prime}>0$,
$x\in\mathcal{GD}^{u}(b,\mathbf{q})$.

Output: $0\leq x^{\prime}\leq x$ such that
$x^{\prime}\in\mathcal{GD}^{u}(b^{\prime},\mathbf{q})$.

1 Find a fitting pair $(f,\pi)$ with respect to $x$ such that
$u(x)=\operatorname{net}_{t}(x)$ and (12) holds;

2 if  _$u(x)=0$ or $\mathbf{q}=\mathbf{0}$_ then return _$x$_ ;

3 $\bar{x}\leftarrow x$ ; $\alpha\leftarrow b/b^{\prime}$ ;

4 while  _$\alpha >1$_ do

5 $(x^{\prime},f^{\prime})\leftarrow\textnormal{{Pullback-
Flow}}(\bar{x},f,\pi)$ ;

6 $\alpha^{\prime}\leftarrow\alpha\frac{u(x^{\prime})}{u(x)}$ ;

7 if  _$\alpha^{\prime}\leq 1$_ then

8 $\lambda\leftarrow\frac{\alpha-1}{\alpha-\alpha^{\prime}}$ ;

9
$x^{\prime\prime}\leftarrow\frac{\alpha-1}{\alpha-\alpha^{\prime}}x^{\prime}+\frac{1-\alpha^{\prime}}{\alpha-\alpha^{\prime}}\bar{x}$
;

10 return _$x^{\prime\prime}$_

11 else

12 $T\leftarrow\left\\{v\in V\,:\,v\text{ can reach
}\operatorname{supp}(x^{\prime})\text{ in
}(G,E^{\textrm{aux}}_{f^{\prime},\pi})\right\\}$ ;

13
$\delta\leftarrow\min\left\\{\alpha,\min\left\\{\frac{\gamma_{e}\pi_{w}}{\pi_{v}}\,:\,e=(v,w)\in\partial^{\mathrm{in}}(T)\right\\},\min\left\\{\frac{\pi_{v}}{\gamma_{e}\pi_{w}}\,:\,e=(v,w)\in\partial^{\mathrm{out}}(T)\right\\}\right\\}$;

14 if  _$\delta^{\prime}=\alpha^{\prime}$_ then return _$x^{\prime}$_ ;

15 for  _$v\in T$_ do $\pi_{v}\leftarrow\delta^{\prime}\pi_{v}$;

16 $\alpha\leftarrow\alpha^{\prime}/\delta^{\prime}$ ; $\bar{x}\leftarrow
x^{\prime}$ ;

17

18

Algorithm 3 Budget-Decrease

We next prove property _(i)_ in Definition 2.14.

######  Lemma 7.8.

Let $u\,:\,\mathbb{R}_{\geq 0}^{\mathcal{M}}\to\mathbb{R}_{\geq 0}$ be a
generalized network utility function and
$\mathbf{q},\mathbf{q}^{\prime}\in\texttt{FQ}^{u}$ such that
$0\leq\mathbf{q}^{\prime}\leq\mathbf{q}$, and let
$x\in\mathcal{GD}^{u}(b,\mathbf{q})$. Then, there exists
$x^{\prime}\in\mathcal{GD}^{u}(b,\mathbf{q}^{\prime})$ such that
$x^{\prime}_{j}\leq x_{j}$ whenever $q^{\prime}_{j}=q_{j}$.

###### Proof.

Clearly, it suffices to show that the statement holds when
$q^{\prime}_{k}<q_{k}$ for a single good $k\in{\mathcal{M}}$. Again, we start
from fitting pair $(f,\pi)$ with respect to $x$ as in Lemma 7.6. Similarly to
Lemma 7.7, we may assume that $u(x)>0$ and $\mathbf{q}\neq\mathbf{0}$. Let us
now replace $\mathbf{q}$ by $\mathbf{q}^{\prime}$. The condition (12) can only
be violated for $j=k$. If it is not violated, then we may return
$x^{\prime}=x$; this is always the case when $\pi_{k}=0$. For the rest of the
proof, assume that the (12) is violated for $k$ with the cost
$q^{\prime}_{k}$. Note that $\pi_{j}=\beta q^{\prime}_{j}$ for every $j\neq
k$, where
$\beta\stackrel{{\scriptstyle\scriptscriptstyle{\mathrm{def}}}}{{=}}u(x)/b$;
we now have $\pi_{k}>\beta q^{\prime}_{k}\geq 0$. This value of $\beta$ will
be fixed throughout the argument.

We first consider the case $q^{\prime}_{k}>0$. The proof uses the subroutine
$\textnormal{{Reroute-Flow}}(x,f,\pi)$ with the special node $k$. This
subroutine finds $x^{\prime}$ and $f^{\prime}$ such that $(f^{\prime},\pi)$ is
a fitting pair with respect to $x^{\prime}$, and further $x^{\prime}_{k}\geq
x_{k}$, $x^{\prime}_{j}\leq x_{j}$ for $j\neq k$, and
$u(x^{\prime})=\operatorname{net}_{f}(t^{\prime})\geq\operatorname{net}_{f}(t)=u(x)$.
Consider the set of nodes $T$ reachable from $k$ in
$E^{\textrm{aux}}_{f^{\prime},\pi}$. According to Lemma 7.5, $t\notin T$ and
$T\cap\operatorname{supp}(x^{\prime})=\\{k\\}$. Similarly as Case II in the
proof of Lemma 7.7, we can decrease $\pi_{v}$ multiplicatively on $T$ to
obtain $\pi^{\prime}$ such that $(f^{\prime},\pi^{\prime})$ is a fitting pair
with respect to $x^{\prime}$. We choose the largest multiplicative decrease
such that $(f^{\prime},\pi^{\prime})$ remains a fitting pair, and that
$\pi_{k}^{\prime}\geq\beta q_{k}^{\prime}$ is maintained. We then repeat this
procedure for $x^{\prime},f^{\prime}$, and $\pi^{\prime}$ in the place of
$x,f$, and $\pi$.

We can again argue that this algorithm terminates in a finite number of
iterations. Note that $\operatorname{supp}(x^{\prime})$ is monotone decreasing
throughout, and $\pi^{\prime}_{j}=\beta q^{\prime}_{j}$ is maintained for all
$j\in\operatorname{supp}(x^{\prime})\setminus\\{k\\}$. For goods with
$x^{\prime}_{j}=0$, $\pi^{\prime}_{j}$ may decrease, and therefore
$\pi^{\prime}_{j}\leq\beta q_{j}$ for these goods. At termination, we have
$\pi^{\prime}_{j}=\beta q^{\prime}_{j}$ for all
$j\in\operatorname{supp}(x^{\prime})$ — including $j=k$ — and
$\pi^{\prime}_{j}\leq\beta q^{\prime}_{j}$ whenever $x^{\prime}_{j}=0$.
Moreover, note that $x^{\prime}_{j}\leq x_{j}$ for all $j\neq k$.

Throughout the algorithm, $u(x^{\prime})$ is non-decreasing. Hence,
$u(x^{\prime})/b\geq\beta$ holds. By setting $\hat{b}>b$ such that
$u(x^{\prime})/\hat{b}=\beta$, (12) holds for $x^{\prime}$, $\pi^{\prime}$,
$q^{\prime}$ and $\hat{b}$. Hence,
$x^{\prime}\in\mathcal{GD}_{u}(\hat{b},\mathbf{q}^{\prime})$. Applying now
Lemma 7.7 for $x^{\prime}$, the prices $\mathbf{q}^{\prime}$ and budgets
$\hat{b}\geq b$, we can find
$x^{\prime\prime}\in\mathcal{GD}_{u}(b,\mathbf{q}^{\prime})$ such that
$x^{\prime\prime}\leq x^{\prime}$. Note that $x^{\prime\prime}_{j}\leq
x^{\prime}_{j}\leq x_{j}$ for all $j\neq k$, and therefore $x^{\prime\prime}$
satisfies the requirements of the Lemma.

Consider now the case $q^{\prime}_{k}=0$. We proceed as above, but our goal is
to eventually set $\pi^{\prime}_{k}=0$. As in the previous case, we repeatedly
call $\textnormal{{Reroute-Flow}}(x,f,\pi)$ and then decrease
$\pi^{\prime}_{v}$ multiplicatively on $T$ by the largest possible factor such
that $(f^{\prime},\pi^{\prime})$ remains a fitting pair. If this largest
factor is unbounded, then we can set $\pi^{\prime}_{v}=0$ for all $v\in T$.
Again, the algorithm should terminate in a finite number of iterations, using
also the assumption that $\mathbf{q}^{\prime}\in\texttt{FQ}^{u}$. Once
$\pi^{\prime}_{k}=0$ is reached, we again have $\pi^{\prime}_{j}=\beta
q^{\prime}_{j}$ for all $j\in\operatorname{supp}(x^{\prime})$, including
$j=k$, and $\pi^{\prime}_{j}\leq\beta q^{\prime}_{j}$ whenever
$x^{\prime}_{j}=0$. The rest of the proof is the same as in the case
$q^{\prime}_{k}>0$. ∎

This concludes the proof of Theorem 1.5, namely, that all generalized network
utilities are Gale-substitutes. Nevertheless, they are not $\Sigma$-Gale-
substitutes, and so Theorem 1.3 is only applicable in the case when the
generalized network utilities are non-satiable. Here, we also show Theorem
1.6, namely, that the desired utility bound holds for all generalized network
utilities if we consider thrifty competitive equilibria.

See 1.6

###### Proof sketch.

We only need to slightly modify the argument in Section 5. Property ($\Sigma$)
is only used in the proof of Lemma 5.1. We show that for generalized network
utilities, if $x\in{\mathcal{D}}^{u}(\mathbf{p},b)$ for
$\mathbf{p}\in\mathbb{R}_{\geq 0}^{\mathcal{M}}$ and further $x$ minimizes
$\large\langle\mathbf{p},x\large\rangle$ in ${\mathcal{D}}^{u}(\mathbf{p},b)$,
then there exists $y\in\mathcal{GD}^{u}(\mathbf{p},b)$ such that $y\leq x$.
From this property, we can derive Lemma 5.2 for thrifty competitive
equilibria; the rest of the proof remains identical to the proof of Theorem
1.3.

Consider now (6) in the proof of Lemma 5.1. If $\lambda>0$, the same argument
is applicable. Consider now the case $\lambda=0$. This means that the
constraint $\large\langle\mathbf{p},x\large\rangle\leq b$ is not active in the
program defining ${\mathcal{D}}^{u}(\mathbf{p},b)$; that is,
$\max_{z\in\mathbb{R}_{\geq
0}^{\mathcal{M}}}\\{u(z)\,:\,\large\langle\mathbf{p},z\large\rangle\leq
b\\}=\max_{z\in\mathbb{R}_{\geq 0}^{\mathcal{M}}}u(z)=v^{\star}$. In
particular, $u(x)=v^{\star}$. The budget minimization property means that $x$
is an optimal solution to the program

$\displaystyle\min\leavevmode\nobreak$ $\displaystyle\mathbf{p}^{\top}x$ (13)
$\displaystyle\operatorname{net}_{f}(t)$ $\displaystyle\geq v^{\star}$
$\displaystyle\operatorname{net}_{f}(v)$ $\displaystyle\geq-x_{v}\quad\forall
v\in S$ $\displaystyle\operatorname{net}_{f}(v)$ $\displaystyle\geq
0\quad\forall v\in V\setminus(S\cup\\{t\\})$ $\displaystyle 0$
$\displaystyle\leq f\leq h\,.$

From here, using LP duality and Lemma 7.1, we can see that there exists a
supergradient $\mathbf{g}\in\partial^{\wedge}u(x)$ and $\mu\in\mathbb{R}_{\geq
0}$ such that

$\mu g_{j}\leq p_{j}\,,\quad\forall j\in{\mathcal{M}}\,,\,\mbox{with equality
if }x_{j}>0\,.$

If $\mu>0$, then we can use the same argument for $\lambda=1/\mu$. If $\mu=0$,
given that $\mu$ acts as the dual variable of $\operatorname{net}_{f}(t)\geq
v^{\star}$, which is no longer active, the optimal value of (13) becomes $0$
since $\mathbf{0}$ is a feasible allocation of $u(\cdot)$ according to our
definition. This is a contradiction, since in Definition 2.2 we assume
$v^{\star}>0$. ∎

##  8 Discussion

In this paper, we compared competitive equilibrium and Nash welfare maximizing
solutions in the Fisher market setting. We identified Gale-substitutes as a
broad family of utility functions where the Nash welfare uniformly guarantees
every agent at least half of their maximum utility at any competitive
equilibrium. We also introduced generalized network utilities. This is a very
general class with a rich combinatorial structure and may be a relevant
example in various market and fair division settings.

Gale-substitutes may be a class of concave functions worth investigating on
its own. In the context of indivisible goods, the analogous class of gross
substitute utilities, introduced by Kelso and Crawford [1982], turned out to
be the same as the important class of $M^{\natural}$-concave utilities in
discrete convex analysis Fujishige and Yang [2003]. In particular, one may
wonder whether the Gale-substitutes property implies _submodularity_ , that
is, $u(x)+u(y)\geq u(x\vee y)+u(x\wedge y)$ for any $x,y\in\mathbb{R}_{\geq
0}^{\mathcal{M}}$, where $x\vee y$ and $x\wedge y$ denote the pointwise
maximum and minimum of the two vectors, respectively. This property trivially
holds for separable utilities and can also be shown for generalized network
utilities.

We note that one can construct an example of a concave quadratic function that
is submodular but not Gale-substitutes. On the other hand, it is unclear
whether Theorem 1.6 would remain true for submodular utilities instead of
Gale-substitutes. Another natural question related to the well-studied notion
of _weak gross substitutes (WGS)_ utilities: Gale-substitutes includes utility
functions that are not WGS, such as concave separable; but it is not clear
whether all WGS utilities are also Gale-substitutes.

Gale-substitutes utilities may also have potential algorithmic applications.
The WGS property leads to natural tâtonnement and auction mechanisms for
finding competitive equilibria, see, e.g., Arrow and Hurwicz [1960], Arrow et
al. [1959], Codenotti et al. [2005c, b], Bei et al. [2019a], Garg et al.
[2023]. The Gale-substitutes property may be useful to design simple such
mechanisms and combinatorial algorithms for solving the convex program (EG).
For the linear case, Devanur et al. [2008] gave a primal-dual algorithm that
was followed by a series of work on combinatorial algorithms for various
market settings, see. e.g., Cole and Gkatzelis [2015], Duan and Mehlhorn
[2015], Garg and Végh [2019], Chaudhury et al. [2022].

## References

  * Ahuja et al. [1993] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin.  _Network Flows: Theory, Algorithms, and Applications_.  Prentice-Hall, Inc., feb 1993.
  * Anari et al. [2018] N. Anari, T. Mai, S. O. Gharan, and V. V. Vazirani.  Nash social welfare for indivisible items under separable, piecewise-linear concave utilities.  In _Proceedings of the 29th Symposium Discrete Algorithms (SODA)_ , pages 2274–2290, 2018.
  * Arrow and Debreu [1954] K. J. Arrow and G. Debreu.  Existence of an equilibrium for a competitive economy.  _Econometrica: Journal of the Econometric Society_ , pages 265–290, 1954.
  * Arrow and Hahn [1971] K. J. Arrow and F. H. Hahn.  _Competitive Equilibrium Analysis_.  Holden-Day, 1971.
  * Arrow and Hurwicz [1960] K. J. Arrow and L. Hurwicz.  Competitive stability under weak gross substitutability: The “Euclidean distance” approach.  _International Economic Review_ , 1(1):38–49, 1960.
  * Arrow et al. [1959] K. J. Arrow, H. D. Block, and L. Hurwicz.  On the stability of the competitive equilibrium, II.  _Econometrica: Journal of the Econometric Society_ , pages 82–109, 1959.
  * Bei et al. [2019a] X. Bei, J. Garg, and M. Hoefer.  Ascending-price algorithms for unknown markets.  _ACM Transactions on Algorithms (TALG)_ , 15(3):1–33, 2019a.
  * Bei et al. [2019b] X. Bei, J. Garg, M. Hoefer, and K. Mehlhorn.  Earning and utility limits in Fisher markets.  _ACM Transactions on Economics and Computation (TEAC)_ , 7(2):1–35, 2019b.
  * Brânzei et al. [2022] S. Brânzei, V. Gkatzelis, and R. Mehta.  Nash social welfare approximation for strategic agents.  _Oper. Res._ , 70(1):402–415, 2022.
  * Caragiannis et al. [2019] I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang.  The unreasonable fairness of maximum nash welfare.  _ACM Trans. Economics and Comput._ , 7(3):12:1–12:32, 2019.
  * Chaudhury et al. [2022] B. R. Chaudhury, J. Garg, P. McGlaughlin, and R. Mehta.  Competitive equilibrium with chores: Combinatorial algorithm and hardness.  In _Proceedings of the 23rd Conference on Economics and Computation (EC)_ , pages 1106–1107, 2022.
  * Chen and Teng [2009] X. Chen and S. Teng.  Spending is not easier than trading: On the computational equivalence of Fisher and Arrow-Debreu equilibria.  In _Proceedings of the 20th International Symposium Algorithms and Computation (ISAAC)_ , pages 647–656, 2009.
  * Chen et al. [2009] X. Chen, D. Dai, Y. Du, and S. Teng.  Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities.  In _Proceedings of the 50th Symposium Foundations of Computer Science (FOCS)_ , pages 273–282, 2009.
  * Chen et al. [2013] X. Chen, D. Paparas, and M. Yannakakis.  The complexity of non-monotone markets.  In _Proceedings of the 45th Symposium Theory of Computing (STOC)_ , pages 181–190, 2013.
  * Codenotti and Varadarajan [2007] B. Codenotti and K. Varadarajan.  Computation of market equilibria by convex programming.  In N. Nisan, É. Tardos, T. Roughgarden, and V. Vazirani, editors, _Algorithmic Game Theory_ , chapter 8. Cambridge University Press, 2007.
  * Codenotti et al. [2005a] B. Codenotti, B. McCune, S. Penumatcha, and K. R. Varadarajan.  Market equilibrium for CES exchange economies: Existence, multiplicity, and computation.  In _Proceedings of the 25th Conference on Foundations of Software Tech. and Theoret. Comp. Sci. (FSTTCS)_ , pages 505–516, 2005a.
  * Codenotti et al. [2005b] B. Codenotti, B. McCune, and K. Varadarajan.  Market equilibrium via the excess demand function.  In _Proceedings of the thirty-seventh annual ACM symposium on Theory of computing_ , pages 74–83, 2005b.
  * Codenotti et al. [2005c] B. Codenotti, S. V. Pemmaraju, and K. R. Varadarajan.  On the polynomial time computation of equilibria for certain exchange economies.  In _SODA_ , volume 5, pages 72–81, 2005c.
  * Codenotti et al. [2006] B. Codenotti, A. Saberi, K. Varadarajan, and Y. Ye.  Leontief economies encode two-player zero-sum games.  In _Proceedings of the 17th Symposium Discrete Algorithms (SODA)_ , pages 659–667, 2006.
  * Cole and Gkatzelis [2015] R. Cole and V. Gkatzelis.  Approximating the Nash social welfare with indivisible items.  In _Proceedings of the 47th Symposium Theory of Computing (STOC)_ , pages 371–380, 2015.
  * Devanur et al. [2008] 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.
  * Duan and Mehlhorn [2015] R. Duan and K. Mehlhorn.  A combinatorial polynomial algorithm for the linear Arrow-Debreu market.  _Inf. Comput._ , 243:112–132, 2015.
  * Dubey [1986] P. Dubey.  Inefficiency of nash equilibria.  _Mathematics of Operations Research_ , 11(1):1–8, 1986.  ISSN 0364765X, 15265471.
  * Eisenberg [1961] E. Eisenberg.  Aggregation of utility functions.  _Management Sci._ , 7(4):337–350, 1961.
  * Eisenberg and Gale [1959] E. Eisenberg and D. Gale.  Consensus of subjective probabilities: The pari-mutuel method.  _The Annals of Mathematical Statistics_ , 30(1):165–168, 1959.
  * Feldman et al. [2023] M. Feldman, S. Mauras, and T. Ponitka.  On optimal tradeoffs between EFX and nash welfare.  2023\.
  * Filos-Ratsikas et al. [2023] A. Filos-Ratsikas, K. A. Hansen, K. Høgh, and A. Hollender.  Ppad-membership for problems with exact rational solutions: A general approach via convex optimization.  2023\.
  * Fujishige and Yang [2003] S. Fujishige and Z. Yang.  A note on Kelso and Crawford’s gross substitutes condition.  _Mathematics of Operations Research_ , 28(3):463–469, 2003.  doi: 10.1287/moor.28.3.463.16393.
  * Garg and Végh [2019] J. Garg and L. A. Végh.  A strongly polynomial algorithm for linear exchange markets.  In _Proceedings of the 51st Symposium Theory of Computing (STOC)_ , 2019.
  * Garg et al. [2014] J. Garg, R. Mehta, and V. V. Vazirani.  Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions.  In _Proceedings of the forty-sixth annual ACM symposium on Theory of computing_ , pages 525–534, 2014.
  * Garg et al. [2015] 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.
  * Garg et al. [2022] J. Garg, Y. Tao, and L. A. Végh.  Approximating equilibrium under constrained piecewise linear concave utilities with applications to matching markets.  In _Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , pages 2269–2284. SIAM, 2022.
  * Garg et al. [2023] J. Garg, E. Husić, and L. A. Végh.  An auction algorithm for market equilibrium with weak gross substitute demands.  _ACM Transactions on Economics and Computation_ , 11(3-4):1–24, 2023.
  * Glover and Klingman [1973] F. Glover and D. Klingman.  On the equivalence of some generalized network problems to pure network problems.  _Mathematical Programming_ , 4:269–278, 1973.
  * Goldberg et al. [1991] A. V. Goldberg, S. A. Plotkin, and É. Tardos.  Combinatorial algorithms for the generalized circulation problem.  _Mathematics of Operations Research_ , 16(2):351–381, 1991.
  * Goyal et al. [2023] M. Goyal, S. Sarmasarkar, and A. Goel.  A mechanism for participatory budgeting with funding constraints and project interactions.  In _Proceedings of the 19th Conference on Web and Internet Economics (WINE)_ , pages 329–347, 2023.
  * Gul et al. [2022] F. Gul, W. Pesendorfer, and M. Zhang.  The efficient allocation of indivisible goods.  _working paper_ , 2022.
  * Hylland and Zeckhauser [1979] A. Hylland and R. Zeckhauser.  The efficient allocation of individuals to positions.  _Journal of Political economy_ , 87(2):293–314, 1979.
  * Kelso and Crawford [1982] A. S. J. Kelso and V. P. Crawford.  Job matching, coalition formation, and gross substitutes.  _Econometrica: Journal of the Econometric Society_ , pages 1483–1504, 1982.  doi: 10.2307/1913392.
  * Koutsoupias and Papadimitriou [1999] E. Koutsoupias and C. Papadimitriou.  Worst-case equilibria.  In _Proceedings of the 16th Symposium Theoret. Aspects of Computer Science (STACS)_ , pages 404–413. Springer, 1999.
  * Mas-Colell [1992] A. Mas-Colell.  Equilibrium theory with possibly satiated preferences.  _Equilibrium and dynamics: Essays in honour of David Gale_ , pages 201–213, 1992.
  * McKenzie [1954] L. McKenzie.  On equilibrium in Graham’s model of world trade and other competitive systems.  _Econometrica: Journal of the Econometric Society_ , pages 147–161, 1954.
  * Moulin [2003] H. Moulin.  _Fair Division and Collective Welfare_.  MIT Press, 2003.
  * Nash [1950] J. F. Nash.  The bargaining problem,” econometrica, 18 (2), 155–162.(1953).  _Two-Person Cooperative Games,” Econometrica_ , 21(1):128–140, 1950.
  * Nesterov and Shikhman [2018] Y. Nesterov and V. Shikhman.  Computation of fisher–gale equilibrium by auction.  _Journal of the Operations Research Society of China_ , 6(3):349–389, 2018.
  * Olver and Végh [2020] N. Olver and L. A. Végh.  A simpler and faster strongly polynomial algorithm for generalized flow maximization.  _Journal of the ACM (JACM)_ , 67(2):1–26, 2020\.
  * Onaga [1966] K. Onaga.  Dynamic programming of optimum flows in lossy communication nets.  _IEEE Transactions on Circuit Theory_ , 13:308–327, 1966\.
  * Ruszczyński [2011] A. Ruszczyński.  _Nonlinear optimization_.  Princeton university press, 2011.
  * Varian [1974] H. Varian.  Equity, envy and efficiency.  _J. Econom. Theory_ , 29(2):217–244, 1974.
  * Vazirani and Yannakakis [2011] V. Vazirani and M. Yannakakis.  Market equilibrium under separable, piecewise-linear, concave utilities.  _J. ACM_ , 58(3):10, 2011.
  * Végh [2014] L. A. Végh.  Concave generalized flows with applications to market equilibria.  _Mathematics of Operations Research_ , 39(2):573–596, 2014.

##  Appendix A Examples

In this section, we present multiple examples mentioned in the paper.

###  A.1 Connectivity of equilibria with bounded linear utilities

We first investigate the (dis)connectivity of competitive equilibria with
bounded linear utilities. We begin by demonstrating that the thrifty
competitive equilibria with bounded linear utilities might not be connected.

######  Example A.1 (Disconnectivity of thrifty competitive equilibrium).

There are two agents and two goods. Each agent has a unit budget. The first
agent’s utility is $u_{1}(x_{1})=1.3\min\\{x_{11},0.8\\}+0.45x_{12}$ and the
second agent’s utility is
$u_{2}(x_{2})=0.01\min\\{x_{21},0.3\\}+2\min\\{x_{22},0.8\\}$.

First, we show there are at least two equilibria. The first equilibrium is
with $\mathbf{p}=(1,1)$. Under this price, $x_{11}=0.8$, $x_{12}=0.2$,
$x_{21}=0.2$, $x_{22}=0.8$. Another competitive equilibrium is with
$\mathbf{p}=(1.3,0.45)$. Under this price, $x_{11}=0.7$, $x_{12}=0.2$,
$x_{21}=0.3$, $x_{22}=0.8$.

Now, we show the second competitive equilibrium is isolated under the thrifty
assumption.

First, we show the price is isolated. Suppose there is a nearby price
$\mathbf{p}^{\prime}=(1.3+\epsilon_{1},0.45+\epsilon_{2})$. For this price,
the thrifty demand of the second agent remains the same: $x_{21}=0.3$,
$x_{22}=0.8$. To maintain equilibrium, the first agent should receive the same
allocation. As $1.3\times 0.7+0.45\times 0.2=1$, $\epsilon_{1}$ and
$\epsilon_{2}$ can not be both positive or negative. However, if one
$\epsilon$ is negative, the first agent will prefer this item more at
$\mathbf{p}^{\prime}$. This implies the allocation of the other item of the
first agent is $0$. This leads to a contradiction.

Second, we show the allocation is isolated. Suppose there is a nearby
equilibrium allocation of the second agent
$x^{\prime}_{2}=(x_{21}-\epsilon_{1},x_{22}-\epsilon_{2})$ with at least one
of $\epsilon_{1}$ and $\epsilon_{2}$ is strictly positive. In this case, both
agents should spend all their budgets as they are non-satiable. Therefore, the
equilibrium prices satisfy $p^{\prime}_{1}+p^{\prime}_{2}=2$. For the first
agent, the allocation is $x^{\prime}_{11}=0.7+\epsilon_{1}$,
$x^{\prime}_{12}=0.2+\epsilon_{2}$. Note that both $\epsilon_{1}$ and
$\epsilon_{2}$ are very tiny. This implies
$p^{\prime}_{1}:p^{\prime}_{2}=1.3:0.45$. Therefore,
$p^{\prime}_{1}=\frac{2}{1.3+0.45}\times 1.3$ and
$p^{\prime}_{2}=\frac{2}{1.3+0.45}\times 0.45$. However, the first agent
cannot afford these allocations under these prices.

The next example shows that competitive equilibria are not connected without
the thrifty assumption.

######  Example A.2 (Disconnectivity of competitive equilibria).

There are three agents and three goods. Each agent has a unit budget. The
first agent’s utility is $u_{1}(x_{1})=1.3\min\\{x_{11},0.8\\}+0.45x_{12}$,
the second agent’s utility is
$u_{2}(x_{2})=0.01\min\\{x_{21},0.3\\}+2\min\\{x_{22},0.8\\}+10^{-10}x_{23}$,
and the third agent’s utility is $u_{3}(x_{3})=x_{33}$.

First, we show there are at least two equilibrium. The first equilibrium is
with $\mathbf{p}=(1,1,1)$, and the allocation is $x_{1}=(0.8,0.2,0)$,
$x_{2}=(0.2,0.8,0)$, and $x_{3}=(0,0,1)$. The second equilibrium is with
$\mathbf{p}=(1.3,0.45,1.25)$ and the allocation is $x_{1}=(0.7,0.2,0)$,
$x_{2}=(0.3,0.8,0.2)$, and $x_{3}=(0,0,0.8)$.

In order to show our results, we first state the following properties: for any
equilibrium,

  1. 1.

$p_{3}>0$ as the third agent is only interested in the third good;

  2. 2.

$x_{13}=0$ as the first agent shows no interest in the third good and its
price is strictly positive;

  3. 3.

$p_{1}>0$ and $p_{2}>0$ as, otherwise, these goods will be over-demanded;

  4. 4.

$x_{31}=x_{32}=0$ as the third agent shows no interest in the first two goods
and their prices are strictly positive;

  5. 5.

$p_{1}+p_{2}+p_{3}=3$ as all agents are non-satiated.

Now, we show the second equilibrium is isolated.

First, we demonstrate that the price is isolated. Suppose there is a nearby
equilibrium price
$\mathbf{p}^{\prime}=(1.3+\epsilon_{1},0.45+\epsilon_{2},1.25+\epsilon_{3})$.
For this price, the allocation of the second agent on the first two items is
the same. Therefore, the first agent should receive the same allocation. As
$1.3\times 0.7+0.45\times 0.2=1$, $\epsilon_{1}$ and $\epsilon_{2}$ can not be
both positive or negative. Similar to the previous example, if one of
$\epsilon_{1}$ and $\epsilon_{2}$ is negative, then the first agent will
prefer this item more at this nearby price. This implies the allocation of the
other item of the first agent is $0$. This leads to the conclusion
$\epsilon_{1}=\epsilon_{2}=\epsilon_{3}=0$.

Second, we show the allocation is isolated. Suppose there is a nearby
equilibrium allocation $\mathbf{x}^{\prime}$ with the equilibrium
$\mathbf{p}^{\prime}$. As $x_{11}<0.8$,
$p^{\prime}_{1}:p^{\prime}_{2}=1.3:0.45$. 111Otherwise, the allocation of the
first agent will be changed significantly. Additionally, $p^{\prime}_{1}\times
x^{\prime}_{11}+p^{\prime}_{2}\times x^{\prime}_{12}=1$. This implies
$p_{1}^{\prime}$ is very close to $p_{1}$ and $p_{2}^{\prime}$ is very close
to $p_{2}$: if $\|x^{\prime}-x\|_{\infty}\leq\epsilon$, then
$|p_{1}^{\prime}-p_{1}|\leq O(\epsilon)$ and $|p_{2}^{\prime}-p_{2}|\leq
O(\epsilon)$. 222Note that
$p^{\prime}_{1}:p^{\prime}_{2}=1.3:0.45=p_{1}:p_{2}$. By budget constraint,
$\frac{1.3}{0.45}p^{\prime}_{2}x^{\prime}_{11}+p^{\prime}_{2}x^{\prime}_{12}=\frac{1.3}{0.45}p_{2}x_{11}+p_{2}x_{12}$.
Therefore,
$p_{2}^{\prime}-p_{2}=\frac{p^{\prime}_{2}(\frac{1.3}{0.45}(x_{11}-x^{\prime}_{11})+(x_{12}-x^{\prime}_{12}))}{\frac{1.3}{0.45}x_{11}+x_{12}}$.
We have a similar result for $p_{1}^{\prime}-p_{1}$. This also implies
$|p_{3}^{\prime}-p_{3}|\leq O(\epsilon)$ as
$p^{\prime}_{1}+p^{\prime}_{2}+p^{\prime}_{3}=3$. Since price is isolated,
$p^{\prime}_{1}=p_{1}$, $p^{\prime}_{2}=p_{2}$, and $p^{\prime}_{3}=p_{3}$.
Under this price, $\mathbf{x}$ is the only allocation.

###  A.2 Non-monotonicity of Gale Demands

The next example shows the somewhat counterintuitive property that increasing
the prices may lead to an increase in the Gale utility.

######  Example A.3 (Non-monotonicity of Gale demands).

There are two goods and a single agent $i$ with $b_{i}=1$. The agent’s utility
function is $u_{i}(x_{i})=\min\\{x_{i1}+x_{i2},2+0.1\cdot x_{i1}+0.2\cdot
x_{i2}\\}$. When $\mathbf{q}=\left(\frac{0.1}{2/0.9+0.2\cdot
0.01},\frac{0.2}{2/0.9+0.2\cdot 0.01}\right)$, the associated Gale demand is
$\mathcal{GD}_{i}(b_{i},\mathbf{q})=\\{(2/0.9,0.01)\\}$ and the utility is
$u_{i}(\mathcal{GD}_{i}(b_{i},\mathbf{q}))=2/0.9+0.2\cdot 0.01$. When
$\mathbf{q}^{\prime}=\left(\frac{1}{0.01+2/0.85},\frac{0.2}{0.01+2/0.85}\right)$,
the Gale demand becomes
$\mathcal{GD}_{i}(b_{i},\mathbf{q}^{\prime})=\\{(0.01,2/0.85)\\}$ and
$u_{i}(\mathcal{GD}_{i}(b_{i},\mathbf{q}^{\prime}))=2/0.85+0.01$. Clearly,
$\mathbf{q}<\mathbf{q}^{\prime}$, yet
$u_{i}(\mathcal{GD}_{i}(b_{i},\mathbf{q}))<u_{i}(\mathcal{GD}_{i}(b_{i},\mathbf{q}^{\prime}))$.

###  A.3 Tight Example on Price of Anarchy

The next example shows that the bound in Theorem 1.1 is tight.

######  Example A.4 (Tight Example on Price of Anarchy).

We consider the case with two agents and two goods. The first agent has a
budget of $1$, and desires the first good: $u_{1}(x_{1})=x_{11}$. The second
agent has a budget of $\mathrm{e}-1$ and has a utility function
$u_{2}(x_{2})=\varepsilon x_{21}+\min\\{x_{22},1\\}$, where $\varepsilon>0$ is
sufficiently small. There is a competitive equilibrium with prices
$p_{1}=\mathrm{e}$ and $p_{2}=0$, and allocations
$x_{1}=(\frac{1}{\mathrm{e}},0)$ and
$x_{2}=(\frac{\mathrm{e}-1}{\mathrm{e}},1)$. The Nash welfare objective for
this allocation is
$\left(\frac{1}{\mathrm{e}}(1+\varepsilon\cdot\frac{\mathrm{e}-1}{\mathrm{e}})^{\mathrm{e}-1}\right)^{\frac{1}{\mathrm{e}}}$.
In the allocation maximizing Nash welfare, we have $y_{1}=(1,0)$ and
$y_{2}=(0,1)$, where the Nash welfare objective is $1$. When
$\varepsilon\rightarrow 0$, the difference of these two scenarios converges to
$\left(\frac{1}{\mathrm{e}}\right)^{\frac{1}{\mathrm{e}}}$.

###  A.4 Utility Difference in Different Equilibria

The following example shows agents might receive significantly different
utilities in different equilibria.

######  Example A.5 (Utility Difference in Different Equilibria).

Consider a scenario involving $n$ agents and $n$ goods, where each agent has a
unit budget. For $1\leq i\leq n-1$, agent $i$’s utility is defined as
$u_{i}(x_{i})=\min\\{x_{ii},1\\}+\epsilon x_{in}$, while agent $n$’s utility
is given by $u_{i}(x_{i})=x_{nn}$. There exist at least two competitive
equilibria. In the first competitive equilibrium, all goods are priced at $1$,
and each good $i$ is allocated to agent $i$ for $1\leq i\leq n$, resulting in
a utility of $1$ for agent $n$. However, in the second competitive
equilibrium, prices are set to $0$ for the first $n-1$ goods and the price of
the $n$-th good is $n$. Consequently, goods $1$ to $n-1$ are allocated to
agents $1$ to $n-1$ respectively, while the $n$-th good is uniformly allocated
to all agents. In this equilibrium, agent $n$ can only attain a utility of
$\approx\frac{1}{n}$.

###  A.5 Tight Example on Demand-Approximate CE

The following example shows Theorem 1.2 is tight.

######  Example A.6 (Tight Example on Demand-Approximate CE).

Consider the case with two agents and one good. Both agents have unit budgets.
The first agent’s utility on this good is linear: $u_{1}(x_{1})=x_{1}$. The
second agent’s utility is defined as follows: $u_{2}(x_{2})=\alpha x_{2}$ for
$x_{2}\leq\frac{1}{\alpha}$ and $u_{2}(x_{2})=1+\beta(x_{2}-\frac{1}{\alpha})$
for $x_{2}>\frac{1}{\alpha}$, where $\alpha$ is a large number and
$\beta\leq\alpha$. When $\beta=\frac{1-\frac{1}{\alpha}}{1-\frac{2}{\alpha}}$,
the Nash welfare maximizing allocation is $x_{1}=1-\frac{1}{\alpha}$ and
$x_{2}=\frac{1}{\alpha}$, with the dual variable $q$ equal to
$\frac{1}{x_{1}}=\frac{1}{1-\frac{1}{\alpha}}$. Under this price, agent $2$
can obtain $x^{\prime}_{2}=1-\frac{1}{\alpha}$ with his/her budget, resulting
in a utility of $1+\beta(x^{\prime}_{2}-\frac{1}{\alpha})=2-\frac{1}{\alpha}$.
In contrast, in the Nash welfare maximizing allocation, agent $2$ only
receives a utility of $1$.

###  A.6 (In)-approximate Nash Welfare utility by Equilibrium utility

In this paper, we show for $\Sigma$-Gale-substitues utilities, the utility of
any agent at the Nash welfare maximizing allocation is at least half the
maximum utility they may get at any CE. It’s natural to ask, inversely, if the
utility agent can attain at any CE can approximate the utility they receive at
Nash welfare maximizing allocation. We show a constant approximation is not
achievable by providing an example in which the CE is unique and there exists
an agent whose utility at this CE is much worse than his/her utility at Nash
welfare maximizing allocation.

######  Example A.7.

Consider a scenario with $n+2$ agents and $n+1$ goods. Set $\epsilon<1$. For
$1\leq i\leq n$, let $u_{i}(x_{i})=\min\\{x_{ii},0.5\\}+\epsilon x_{i(n+1)}$.
Additionally, set $u_{n+1}(x_{n+1})=x_{(n+1)(n+1)}$ and
$u_{n+2}(x_{n+2})=\sum_{j=1}^{n}x_{ij}$. We first demonstrate the unique
competitive equilibrium is achieved when $p_{j}=\frac{2}{n}$ for $1\leq j\leq
n$ and $p_{n+1}=n$. In this equilibrium, $x_{ii}=0.5$ and
$x_{i(n+1)}=\frac{n-1}{n^{2}}$ for $1\leq i\leq n$;
$x_{(n+1)(n+1)}=\frac{1}{n}$; and $x_{(n+2)j}=0.5$ for $1\leq j\leq n$.

We now show this is the only competitive equilibrium. First, for all $j:1\leq
j\leq n$, $p_{j}>0$. Otherwise, agent $n+2$ would receive infinite goods.
Given $p_{j}>0$ for any $1\leq j\leq n$, $x_{(n+2)j}\geq 0.5$. Consequently,
the first $n$ goods share the same prices and
$0.5p_{j}n\leq\sum_{j}x_{(n+2)j}p_{j}=1$ which implies $p_{j}\leq\frac{2}{n}$.
If $p_{j}<\frac{2}{n}$ for $1\leq j\leq n$, then
$p_{n+1}=\sum_{i}b_{i}-\sum_{j}p_{j}>n$. In this case, $x_{ii}=0.5$ for $1\leq
i\leq n$ and $0.5p_{j}n=1$ for $1\leq j\leq n$, which implies the result.

Therefore, agent $n+1$ receives utility $\frac{1}{n}$ in the unique
competitive equilibrium. However, for a small enough $\epsilon$, this agent
receives $1$ in the maximal Nash welfare solution.

###  A.7 (In)-approximation for general utilities

Our next example demonstrates if the utility function is not Gale substitutes,
then agents’ competitive equilibrium utilities can be much higher than the
Nash welfare maximizing solution.

######  Example A.8.

There are three types of agents (A, B, C): $1$ type-A agent; $n^{2}$ type-B
agents; $n$ type-C agents; and four types of goods (O, P, R, S): $1$ type-O
good; $n$ type-P goods; $n^{2}$ type-R goods; $n$ type-S goods. In total,
there are $N=n^{2}+n+1$ agents and $M=n^{2}+2n+1$ goods.

The type-A agent is interested in the type-O good and type-P goods. Type-A
agent has a _bounded_ linear utility with equal preferences over these type-O
and type-P goods: $v_{ij}=1$ for $i=A$ and $j\in O\cup P$. This agent has an
upper bound of 1 on the utility of each good: $u_{A}(x_{A})=\sum_{j\in O\cup
P}\min\\{x_{Aj},1\\}$.

For type-B agents, let’s label each of these agents by $(s,t)$ for $s\in[1,n]$
and $t\in[1,n]$ and also label each of type-R goods by $(s,t)$ for $s\in[1,n]$
and $t\in[1,n]$. Agent $(s,t)$ is interested in the corresponding $(s,t)$ good
in R and the $s$-th good in P. The utility function of agent $i=(s,t)$ is
$\min\\{x_{iP_{s}}+\frac{n}{n+1},x_{iR_{s,t}}\\}$, where $x_{iP_{s}}$ is agent
$i$’s allocation of $P_{s}$ and $x_{iR_{s,t}}$ is agent $i$’s allocation of
$R_{s,t}$.

For type-C agents, the $s$-th type-C agent is only interested in the $s$-th
type-S good and all type-R good with label $(s,\cdot)$. This agent also has a
bounded linear utility with equal preference ($v_{ij}=1$) over these goods and
an upper bound, $l_{ij}=1$, on the utility of each good.

We first consider the maximal Nash welfare solution. Here, $k$ is a parameter,
which will be specified later.

The type-A agent receives type-O good and $k+\frac{1}{n+1}$ portion of type-P
goods, his/her utility will be $1+nk+\frac{n}{n+1}$.

Each type-B agent obtains $1-\frac{k}{n}$ portion of corresponding type-R good
and $\frac{1}{n+1}-\frac{k}{n}$ portion of corresponding type-P good, yielding
a utility of $1-\frac{k}{n}$.

The type-C agents receive the remaining goods, resulting in a utility of
$1+k$.

The goal is to maximize
$(1+nk+\frac{n}{n+1})(1-\frac{k}{n})^{n^{2}}(1+k)^{n}$. By calculation, the
optimal $k$ is found to be no larger than $n^{-\frac{1}{2}}$. 333First, we
take the log and calculate the gradient, which is
$\frac{n}{1+nk+\frac{n}{n+1}}+\frac{n}{1+k}-\frac{n}{1-\frac{k}{n}}$. Note
that this is a decreasing function with $k$. So, in order to show the optimal
$k$ is no larger than $n^{-\frac{1}{2}}$, we only need to show when
$k=n^{-\frac{1}{2}}$,
$\frac{n}{1+nk+\frac{n}{n+1}}+\frac{n}{1+k}\leq\frac{n}{1-\frac{k}{n}}$. This
is true as
$\frac{n}{1-\frac{k}{n}}-\frac{n}{1+k}=\frac{(n+1)k}{1+k-\frac{k}{n}-\frac{k^{2}}{n}}\geq
nk=\frac{1}{k}\geq\frac{n}{1+nk+\frac{n}{n+1}}$. Therefore, the type-A agent
receives at most $1+\sqrt{n}+\frac{n}{n+1}$ utility in the maximal Nash
welfare solution.

On the other hand, let’s consider the (thrifty) competitive equilibrium where
all agents have unit budgets.

The prices of type-O, P, and S goods are $0$. and prices of type-R goods are
$\frac{n+1}{n}$. In this case, the type-A agent will get the type-O good and
type-P goods, resulting in a utility of $n+1$. Each type-B agent receives
$\frac{n}{n+1}$ portion of the corresponding type-R good, leading to a utility
of $\frac{n}{n+1}$. The type-C agent acquires $1$ portion of the corresponding
type-S good and the rest of type-R goods, resulting in a utility of
$1+\frac{n}{n+1}$.

Comparing the type-A agent’s utility in the two scenarios, the type-A agent
achieves at most $1+\sqrt{n}+\frac{n}{n+1}$ utility in the maximal Nash
welfare solution, whereas the agent attains $n+1$ utility in the (thrifty)
competitive equilibrium.

###  A.8 Tight Example of Theorem 1.3

The following example shows the bound in Theorem 1.3 is tight.

######  Example A.9.

Consider the case that there are $n$ agents and $n$ goods. All agents have
bounded linear utilities. Additionally, all agents have the same preferences
($v_{ij}=1$) on all goods except for the first good. For the first good, only
the first agent likes the first good ($v_{11}=0$) and all other agents don’t
like this good $v_{i1}=0$ for $i\neq 1$. Additionally, we assume the upper
bound on the utility of each good of each agent is $1$, $l_{ij}=1$ for all $i$
and $j$.

In this case, for the maximal Nash welfare solution, the utilities of all
agents equal $1$. However, there exists a competitive equilibrium, at which
the price of the first good equals $0$ and the prices for all other goods
equal $\frac{n}{n-1}$. Then, the first agent can get the first good and
$\frac{n-1}{n}$ fraction of the second good, and achieve a utility of
$1+\frac{n-1}{n}$ which tends to $2$ in the case $n\rightarrow\infty$.

###  A.9 Example with Leontief-free utility functions

Not all Leontief-free utility functions satisfy property ($\Sigma$). The
subsequent example illustrates a scenario where an agent can attain
significantly more utility in competitive equilibrium compared to the Nash
welfare maximizing allocation when agents’ utilities being Leontief-free.

######  Example A.10.

Consider the scenario with $n$ goods and $n+1$ agents. Agent $i=1,2,\cdots,n$
only likes good $i$, has budget $b_{i}=1$ and a linear utility function
$u_{i}(x_{i})=x_{ii}$. Agent $n+1$ has a substantially larger budget
$b_{k+1}=B$, and a utility function
$\min\\{\sum_{i=1}^{k}x_{(n+1)i},(n-1)(1-\epsilon)\\}$ with a small
$\epsilon>0$.

There is a competitive equilibrium where the prices are $p_{1}=1$ and
$p_{2}=p_{3}=\cdot=p_{n}=\frac{1}{\epsilon}$. Agent $1$ obtains $x_{11}=1$,
the other agents get $x_{ii}=\epsilon$ for $i=2,\cdots,n$, and agent $n+1$
gets $x_{(n+1)1}=0$ and $x_{(n+1)j}=1-\epsilon$ for $j=2,\cdots,n$. The
competitive equilibrium holds if $B>\frac{(n-1)(1-\epsilon)}{\epsilon}$.

On the other hand, in the Nash welfare maximizing allocation, when $B$ is big
enough, agent $n+1$ receives (approximately) $\frac{(1-\epsilon)(n-1)}{n}$ of
each good, with the remaining goods shared among the remaining agents. Agent
$1$ receives a utility of $\epsilon+\frac{1-\epsilon}{n}$, which is
significantly less than the utility received in the competitive equilibrium.

In this case, agent $n+1$’s utility doesn’t satisfy property ($\Sigma$). When
$\mathbf{p}=\mathbf{0}$,
$x_{n+1}=(0,1-\epsilon,1-\epsilon,\cdots,1-\epsilon)\in\mathcal{GD}_{n+1}(\mathbf{p},B)$.
However, when
$\mathbf{p}=(1,\frac{1}{\epsilon},\frac{1}{\epsilon},\cdots,\frac{1}{\epsilon})$,
for any $x_{n+1}\in\mathcal{GD}_{n+1}(\mathbf{p},B)$, $x_{(n+1)1}>0$, which
violates property ($\Sigma$).

##  Appendix B Proof of Lemma 7.1

See 7.1

###### Proof.

Let $\operatorname{Primal}(x)$ and $\operatorname{Dual}(x)$ denote the primal
and dual LPs (9) and (10) for a fixed $x\in\mathbb{R}^{m}$. First, assume that
$\pi\in\mathbb{R}_{\geq 0}^{\ell}$ is an optimal solution to
$\operatorname{Dual}(x)$ for a given $x\in\mathbb{R}^{m}$. We need to show
that $g=B^{\top}\pi$ is a supergradient at $x$, that is,
$\varphi(t)\leq\varphi(x)+\large\langle g,t-x\large\rangle$ for any
$t\in\mathcal{D}$.

The programs $\operatorname{Dual}(x)$ and $\operatorname{Dual}(t)$ have the
same feasible region, with linear objective functions $\mathbf{B}x+b$ and
$\mathbf{B}t+b$, respectively. By weak duality, the cost of every feasible
dual solution is at least the primal optimum value, thus, $\varphi(t)\leq
t^{\top}\mathbf{B}\pi+b^{\top}\pi=g^{\top}t+b^{\top}\pi$. The statement
follows as

$\varphi(t)\leq
g^{\top}t+b^{\top}\pi=g^{\top}(t-x)+x^{\top}\mathbf{B}\pi+b^{\top}\pi=\varphi(x)+g^{\top}(t-x)\,,$

noting also that $\varphi(x)=x^{\top}\mathbf{B}\pi+b^{\top}\pi$ since $\pi$ is
an optimal solution to $\operatorname{Dual}(x)$, and $\varphi(x)$ is the
optimum value.

Conversely, we need to show that if $g\in\partial^{\wedge}\varphi(x)$, then
there exists a dual optimal solution $\pi$ such that $g=\mathbf{B}^{\top}\pi$.
Let $z$ be a primal optimal solution to $\operatorname{Primal}(x)$. Using
complementary slackness, we can turn $\operatorname{Dual}(x)$ into a
feasibility system. Namely, $g=\mathbf{B}^{\top}\pi$ for a dual optimal
solution if and only if

$\displaystyle\mathbf{B}^{\top}\pi$ $\displaystyle=g$ (14)
$\displaystyle\mathbf{A}_{i}^{\top}\pi$ $\displaystyle=c_{i}\,,\quad\forall
i:z_{i}>0$ $\displaystyle\mathbf{A}_{i}^{\top}\pi$ $\displaystyle\geq
c_{i}\,,\quad\forall i:z_{i}=0$ $\displaystyle\pi_{j}$
$\displaystyle=0\,,\quad\forall j:(\mathbf{A}z)_{j}<(\mathbf{B}x+b)_{j}$
$\displaystyle\pi_{j}$ $\displaystyle\geq 0,\quad\forall
j:(\mathbf{A}z)_{j}=(\mathbf{B}x+b)_{j}\,.$

Here, $\mathbf{A}_{i}$ denotes the $i$-th column of $\mathbf{A}$. By Farkas’s
lemma, if (14) is not feasible, then the following system has a feasible
solution:

$\displaystyle(\mathbf{A}w)_{j}+(\mathbf{B}r)_{j}$ $\displaystyle\leq
0\,,\quad\forall j:(\mathbf{A}z)_{j}=(\mathbf{B}x+b)_{j}$ $\displaystyle
w_{i}$ $\displaystyle\geq 0\,,\quad\forall i:z_{i}=0$ $\displaystyle
c^{\top}w+g^{\top}r$ $\displaystyle>0\,.$

For a small enough $\varepsilon>0$, $z+\varepsilon w$ is feasible to the
system $\operatorname{Primal}(x-\varepsilon r)$. Hence, for $t=x-\varepsilon
r$, $\varphi(t)\geq c^{\top}(z+\varepsilon w)=c^{\top}z+\varepsilon
c^{\top}w$. Using $c^{\top}z=\varphi(x)$ by the choice of $z$ as an optimal
solution to $\operatorname{Primal}(x)$, and the bound $c^{\top}w>-g^{\top}r$,
we get $\varphi(t)>\varphi(x)-\varepsilon g^{\top}r=\varphi(x)+\large\langle
g,t-x\large\rangle$, a contradiction to $g\in\partial^{\wedge}\varphi(x)$. ∎