11institutetext: Stanford University, Stanford CA 94305, USA
11email<EMAIL_ADDRESS>22institutetext: The Hong Kong
University of Science and Technology, Hong Kong
22email<EMAIL_ADDRESS>

# Markets for Efficient Public Good Allocation with Social Distancing

Devansh Jalota 11 Qi Qi 22 Marco Pavone 11 Yinyu Ye 11

###### Abstract

Public goods are often either over-consumed in the absence of regulatory
mechanisms, or remain completely unused, as in the Covid-19 pandemic, where
social distance constraints are enforced to limit the number of people who can
share public spaces. In this work, we plug this gap through market based
mechanisms designed to efficiently allocate capacity constrained public goods.
To design these mechanisms, we leverage the theory of Fisher markets, wherein
each agent in the economy is endowed with an artificial currency budget that
they can spend to avail public goods. While Fisher markets provide a strong
methodological backbone to model resource allocation problems, their
applicability is limited to settings involving two types of constraints -
budgets of individual buyers and capacities of goods. Thus, we introduce a
modified Fisher market, where each individual may have additional physical
constraints, characterize its solution properties and establish the existence
of a market equilibrium. Furthermore, to account for additional constraints we
introduce a social convex optimization problem where we perturb the budgets of
agents such that the KKT conditions of the perturbed social problem
establishes equilibrium prices. Finally, to compute the budget perturbations
we present a fixed point scheme and illustrate convergence guarantees through
numerical experiments. Thus, our mechanism, both theoretically and
computationally, overcomes a fundamental limitation of classical Fisher
markets, which only consider capacity and budget constraints.

###### Keywords:

Social Distancing Covid-19 Fisher Markets Market Equilibrium Resource
Allocation

##  1 Introduction

A public good is a product that an individual can consume without reducing its
availability to others and of which no one is deprived. These properties are
defining features of pure public goods, examples of which include law
enforcement, national defense, sewer systems, public parks, and the air we
breathe. In reality, almost no good can satisfy the precise definitions of
both non-rivalry and non-excludability [1], as these goods often suffer from
over consumption [2], which leads to a decreased utility for consumers. This
phenomena becomes more so during the Covid-19 pandemic, where social distance
constraints are enforced so that only a limited number of people can share
public spaces [3]. A consequence of such constraints is that it results in
completely closing parks or beaches [4], which leads to goods becoming non-
public. Thus, on one hand public goods may no longer satisfy the non-rivalry
and non-excludability properties associated with these resources while on the
other hand the lack of regulation of public goods results in the consumers
behaving in their own selfish interests when using these goods, which leads to
the overuse of such shared resources, i.e., tragedy of the commons. In
particular, Figure 1 illustrates these two contrasting outcomes and highlights
the need for regulatory mechanisms that impose restrictions on usage of shared
resources.

Figure 1: The current scenario involving either an overcrowded beach (left) or
a completely unused beach (right) generating no value to society.

In this paper, we attempt to achieve an intermediate between these opposing
and undesirable outcomes through market mechanisms to efficiently allocate
shared resources. To achieve such a balance, we study capacity constrained
public resources, which helps prevent the overcrowding concerns associated
with public goods and is in line with situations when strict capacity
constraints in the use of public spaces are necessitated. In our work, we
leverage the presence of alternatives in the case of many public goods, which
enables us to distribute the consumer load over these resources. Examples of
such alternatives include myriad local grocery stores and restaurants as well
as multiple options for recreational use such as parks and beaches. As demand
often outweighs supply of public goods, we need to make decisions on who gets
preference to use capacity constrained public spaces. These allocation
decisions are facilitated through a pricing mechanism that ensures the
formation of a market equilibrium, i.e., each agent purchases their most
preferred bundle of goods affordable under the set prices. The pricing
decisions must be made with fairness considerations, as public goods are by
design available to all individuals and of which no person is deprived. We
ensure fairness of our mechanism through two methods. First, we endow agents
with artificial currency budgets and charge customers this currency for the
use of public spaces. The non-monetary transfers ensure that allocation
decisions are not biased towards those with higher incomes. Second, when
making pricing decisions we simultaneously take into account individual
consumer preferences, i.e., each agent’s utilities for using public goods,
while ensuring that resulting allocations are beneficial for society.

To study our resource allocation problem under capacity constraints while
considering both individual agent preferences and societal benefit, we resort
to the canonical model of Fisher markets. In a Fisher market, consumers spend
their budget of money (or artificial currency) to buy goods that maximize
their individual utilities, while producers sell capacity constrained goods in
exchange for currency. A key property of interest with Fisher markets is the
formation of an equilibrium when the market clears, i.e. all budgets are spent
and all goods are sold. At this market equilibrium, buyers get their most
preferred bundle of goods, while a social objective is maximized.

We first describe each agent’s individual optimization problem in Fisher
markets. In this framework, the decision variable for agent $i$ is the
quantity of each good $j$ they wish to purchase and is represented by
$x_{ij}$. We denote the allocation vector for agent $i$ as
$\mathbf{x}_{i}\in\mathbb{R}^{m}$, when there are $m$ goods in the market. A
key assumption of Fisher markets is that goods are divisible and so fractional
allocations are possible, and so we interpret $x_{ij}$ as the probability that
agent $i$ is allocated to good $j$. Finally, denoting $w_{i}$ as the budget of
agent $i$, $u_{i}(\mathbf{x}_{i})$ as the utility of agent $i$ as a concave
function of their allocation and $\mathbf{p}\in\mathbb{R}_{\geq 0}^{m}$ as the
vector of prices for the goods, individual decision making in Fisher markets
can be modelled as the following optimization problem:

$\displaystyle\underset{\displaystyle\mathbf{x}_{i}\in\mathbb{R}^{m}}{\mathrm{max}}\quad
u_{i}(\mathbf{x}_{i})$ (1a)
$\displaystyle\mathmakebox[\widthof{$\underset{\displaystyle\phantom{\mathbf{x}_{i}\in\mathbb{R}^{m}}}{\mathrm{max}}$}][c]{\mathmakebox[\widthof{$\mathrm{max}$}][l]{\mathrm{\kern
1.00006pts.t.}}}\quad$ $\displaystyle\mathbf{p}^{T}\mathbf{x}_{i}\leq w_{i}$
(1b) $\displaystyle\mathbf{x}_{i}\geq\mathbf{0}$ (1c)

Here agent $i$ has a budget constraint (1b) and a non-negativity constraint
(1c) on the allocations.

The vector of prices $\mathbf{p}\in\mathbb{R}_{\geq 0}^{m}$ that each agent
observes are computed through the solution of a social optimization problem
that aggregates the utilities of all agents. The social objective function
used in the Fisher market literature is one wherein the optimal allocation
maximizes the budget weighted geometric mean of the buyer’s utilities. The
choice of the social objective is such that under certain conditions on the
utility function, there exists an equilibrium price vector defined as:

###### Definition 1

A vector $\mathbf{p}\in\mathbb{R}_{\geq 0}^{m}$ is an equilibrium price vector
if $\sum_{i=1}^{n}x_{ij}^{*}(p_{j})=\bar{s}_{j}$, $\forall j$, i.e., all the
goods are sold, where each resource $j$ has a price $p_{j}$ and has a strict
capacity constraint of $\bar{s}_{j}\geq 0$, and
$\sum_{j=1}^{m}p_{j}x_{ij}^{*}(p_{j})=w_{i}$, $\forall i$, i.e., budgets of
all agents are completely used. Furthermore,
$x^{*}(\mathbf{p})_{i}\in\mathbb{R}^{m}$ is an optimal solution of the
individual optimization problem (1a)-(1c) for all agents $i$.

This price vector is computed as the dual variables of the capacity constraint
(2b) in the following social optimization problem:

$\displaystyle\underset{\displaystyle\mathbf{x}_{i}\in\mathbb{R}^{m},\forall
i\in[n]}{\mathrm{max}}\quad
u(\mathbf{x}_{1},...,\mathbf{x}_{n})=\sum_{i=1}^{n}w_{i}\log(u_{i}(\mathbf{x}_{i}))$
(2a)
$\displaystyle\mathmakebox[\widthof{$\underset{\displaystyle\phantom{\mathbf{x}_{i}\in\mathbb{R}^{m},\forall
i\in[n]}}{\mathrm{max}}$}][c]{\mathmakebox[\widthof{$\mathrm{max}$}][l]{\mathrm{\kern
1.00006pts.t.}}}\quad$ $\displaystyle\sum_{i=1}^{n}x_{ij}=\bar{s}_{j},\forall
j\in[m]$ (2b) $\displaystyle x_{ij}\geq 0,\forall i,j$ (2c)

where there are $n$ agents in the economy and $m$ shared resources. We denote
$[a]$ as the set $\small\\{1,2,...,a\small\\}$.

Since both the individual and social problems are convex optimization
problems, the equivalence of their first order KKT conditions is necessary and
sufficient at the equilibrium price condition. This establishes that under the
prices set through the solution of the social optimization problem each agent
receives their most favourable bundle of goods [5].

While these appealing properties of Fisher markets have been leveraged with
great success in applications including online advertising [6] as well as in
revenue optimization [7], there is a fundamental limitation with the Fisher
market framework that limits its practical use in public goods allocation
problems. This limitation stems from the consideration of only two types of
constraints - budgets of buyers and capacities of goods - in the Fisher market
model. In many public goods allocation problems, the availability of
substitutes imposes additional physical constraints that are necessary to
consider for the resulting allocation to be meaningful. To model the
availability of public good alternatives, we pool together public goods
serving similar functionality into their own resource types. For instance, if
we had multiple grocery stores and parks in a neighborhood, we could pool them
into two different resource types. We provide further examples of resource
types and delve into further detail on the constraints associated with these
resource types in sections 4.2 and 5, where we elucidate the real world
applications and practical implementation of this work.

The presence of these additional constraints raises the question of whether we
can still find appropriate market clearing prices while retaining the
desirable properties of the Fisher market framework. This question leads us to
the main focus of this paper, which is to:

Design a market based mechanism that achieves the same properties as Fisher
markets while also supporting additional physical constraints.

###  1.1 Our Contributions

In our pursuit of such a mechanism, we start by defining each agent’s
individual optimization problem (IOP) with the addition of physical
constraints. The properties of this problem IOP turn out to be fundamentally
different from the traditional Fisher markets with linear utilities, as we no
longer have guarantees on the existence and uniqueness of a market
equilibrium. However, we derive a technical condition to overcome the question
of the existence of a market equilibrium and provide a thorough
characterization of the optimal solution of IOP.

Having established the existence of a market equilibrium, we then turn to
deriving market clearing prices in the addition of physical constraints. We
first show that market clearing conditions fail to hold under a natural
extension of Fisher markets, wherein we add physical constraints to the social
optimization problem (2a)-(2c) and derive prices using this constraint
augmented problem (denoted as SOP1). This negative result points towards a
formulation of a new social optimization problem (denoted as BP-SOP) wherein
we perturb the budgets of agents by constants that depend on the dual
variables of the physical constraints. We then show the following properties
of BP-SOP:

  * •

Market Clearing: The budget perturbation constants are chosen such that the
market clears under the prices set corresponding to the dual variables of the
capacity constraint of BP-SOP.

  * •

Economic Relevance of Solution: A consequence of the market clearing property
is that the prices are set appropriately so that each agent maximizes their
utility subject to the set prices.

  * •

Computational Feasibility: We present a fixed point scheme to determine the
perturbation constants and establish its convergence through numerical
experiments.

We note that the physical constraints we consider extend beyond public goods
allocation, as such constraints arise on the buyer’s side in retail,
e-commerce and the AdWords market, as buyers have restrictions on the amount
of goods they can purchase and advertisers on the number of people in each
demographic class that they can target. In addition, such constraints help in
achieving fairness by restricting the purchase of certain goods by individual
agents to enable wider access.

###  1.2 Related Work

Setting appropriate market clearing prices has been a prominent topic of
research at the intersection of economic and optimization theory. While Walras
[8] was the first to question whether goods could be priced in a $n$ buyer $m$
good market such that each person receives a bundle of goods to maximize their
utilities, it was Arrow and Debreu who established the existence of such a
market equilibrium under mild conditions on the utility function of buyers
[9]. However, it was not until Fisher that there was an algorithm to compute
equilibrium prices and the distribution of the $m$ goods amongst the $n$
buyers in the market [10]. Later Eisenberg and Gale formulated Fisher’s
original problem with linear utilities as a convex optimization problem that
could be solved in polynomial time [11, 12].

While Fisher markets have since been studied extensively in the computer
science and algorithmic game theory communities, there has been recent
interest in considering settings when additional constraints are added to the
traditional Fisher market framework. For instance, Bei et al. [13] impose
limits on how much sellers can earn and question the assumption that utilities
of buyers strictly increase in the amount of the good allocated. A different
generalization of Fisher markets is considered by Vazirani [6], Devanur et al.
[14] and Birnbaum et al. [15], wherein utilities of buyers depend on prices of
goods through spending constraints. Yet another generalization has been
considered by Devanur et al. [16] in which goods can be left unsold as sellers
declare an upper bound on the money they wish to earn and budgets can be left
unused as buyers declare an upper bound on the utility they wish to derive.
Along similar lines Chen et al. [17] study equilibrium properties when agents
keep unused budget for use in the future. These generalizations of Fisher
markets are primarily associated with spending constraints of buyers and
earning constraints of sellers; however, to the best of our knowledge there
has been no generalization of Fisher markets to the case of additional
physical constraints, which are prevalent in public goods allocation problems
as well as other applications.

While such physical constraints have not been studied in the Fisher market
literature, there have been other market equilibrium characterizations that
take into account such constraints. One notable such work is that on the
Combinatorial Assignment problem by Budish [18] wherein a market based
mechanism is used to assign students to courses while respecting student’s
schedule constraints. In Budish’s framework, courses have strict capacity
constraints and students are endowed with budgets and must submit their
preferences to a centralized mechanism that provides approximately efficient
allocations provided that budgets of students are not all exactly equal. We
study the problem of allocating public goods under physical constraints from a
different perspective than that considered by Budish. In particular, we
approach the public goods allocation problem from the standpoint of setting
equilibrium prices that are obtained through the maximization of a societal
objective whilst also maximizing individual utilities subject to those prices.

Finally, since we are allocating public goods that are designed to be
available to all individuals such that no one can be deprived of them, we must
take the fairness of the resulting allocation into account. A popular method
to achieve an equal playing ground for all agents has been the use of
artificial currencies. For instance, Gorokh et al. established how artificial
currencies can be equally distributed to agents to achieve fairness [19]. We
follow a similar idea in our work by endowing agents with artificial currency
budgets that they can spend, which helps overcome concerns of priced
mechanisms, e.g., congestion pricing, in regulating the use of public
resources.

The rest of this paper is organized as follows. We first present the
individual optimization problem IOP and study properties of the corresponding
market equilibrium in section 2. Then, in section 3, we provide a motivation
for why modifying Fisher markets is necessary to guarantee market clearing
properties with the addition of physical constraints and propose a new budget
perturbed social optimization problem that guarantees a market equilibrium. As
the budget perturbed problem involves setting the perturbation constants as
the dual variables of the added constraints, we present a fixed point
iterative procedure to compute these constants in section 4. Finally, in
section 5 we lay out a real world implementation plan of our mechanism and
conclude the paper in section 6.

##  2 Properties of the Individual Optimization Problem

In this section, we study the individual optimization problem of agents in the
addition of physical constraints that are not considered in the Fisher market
framework. We start by defining a new individual optimization problem IOP in
section 2.1 and study properties regarding the existence and non-uniqueness of
a market equilibrium in sections 2.2-2.4. Finally, we close this section
through a characterization of the optimal solution of IOP in section 2.5.

###  2.1 Modelling Framework for Individual Optimization Problem

As in Fisher markets, we model agents as utility maximizers and in this work,
each agent’s utility function is assumed to be linear in the allocations,
which is a common utility function used in the Fisher market literature [11,
20]. We model the preference of an agent $i$ for one unit of good $j$ through
the utility $u_{ij}$. Furthermore, we extend the Fisher market framework
through the consideration of each agent’s physical constraints. To model this
physical constraint we consider each public good $j$ as belonging to exactly
one resource type, with the the set of all resource types denoted as $T$. We
further let $T_{i}\subseteq T$ denote the resource types that each agent $i$
is interested in consuming and for the ease of exposition we normalize each
agent’s constraints such that each agent would like to obtain at most one unit
of goods in each resource type. These physical constraints are specified by a
matrix $A^{(i)}\in\mathbb{R}^{m\times l_{i}}$, where $l_{i}=|T_{i}|$.
Furthermore, the row corresponding to resource type $t\in T_{i}$ is
represented as a row vector $A_{t}^{(i)}$. Using our earlier defined notation
to specify budgets and prices, we have the following individual optimization
problem (IOP):

$\displaystyle\underset{\displaystyle\mathbf{x}_{i}\in\mathbb{R}^{m}}{\mathrm{max}}\quad
u_{i}(\mathbf{x}_{i})=\sum_{j=1}^{m}u_{ij}x_{ij}$ (3a)
$\displaystyle\mathmakebox[\widthof{$\underset{\displaystyle\phantom{\mathbf{x}_{i}\in\mathbb{R}^{m}}}{\mathrm{max}}$}][c]{\mathmakebox[\widthof{$\mathrm{max}$}][l]{\mathrm{\kern
1.00006pts.t.}}}\quad$ $\displaystyle\mathbf{p}^{T}\mathbf{x}_{i}\leq w_{i}$
(3b) $\displaystyle A_{t}^{(i)}\mathbf{x}_{i}\leq 1,\forall t\in T_{i}$ (3c)
$\displaystyle\mathbf{x}_{i}\geq\mathbf{0}$ (3d)

where we have a budget constraint (3b), physical constraints (3c) and non-
negativity constraint (3d). We note that $A_{t}^{(i)}\mathbf{x}_{i}\leq 1$ is
identical to $\sum_{j\in t}x_{ij}\leq 1$, as each agent consumes at most one
unit of goods in each resource type. We now turn to studying the market
equilibrium properties of IOP.

###  2.2 Market Equilibrium may not Exist

In the traditional Fisher market framework with linear utilities, there exists
a unique market equilibrium under mild assumptions [21]. However, in the
presence of additional physical constraints, as in the individual optimization
problem (3a)-(3d), an equilibrium price is not guaranteed to exist. In
particular, we elucidate the non-existence of a market equilibrium through the
following proposition.

######  Proposition 1 ()

There exists a market wherein each good $j\in[m]$ has a potential buyer
$i\in[n]$, i.e., $u_{ij}>0$, but no equilibrium for IOP exists.

To establish Proposition 1, we provide a counterexample presented in Appendix
section 7.1.

###  2.3 Condition to Guarantee Existence of Market Equilibrium

While Proposition 1 indicates that in general we cannot expect a market
equilibrium to exist for IOP, we now show that under a mild condition the
market equilibrium is in fact guaranteed to exist. This condition arises from
the fact that there may be instances, as in the case of the counterexample to
prove Proposition 1, when agents cannot spend all of their budget. To
guarantee that agents completely spend their budget, we must ensure that there
is a good that is not restrained by physical constraints in the market so that
agents can purchase more units of it to spend their entire budget. We
formalize this notion by establishing the following theorem:

######  Theorem 2.1 ()

There exists a market equilibrium if for any agent $i$, there exists a good
$j$, such that $j$ does not belong to any type, i.e., it is not associated
with any physical constraints, and $i$ has positive utility for all goods,
i.e., $u_{ij}>0$, $\forall j$.

###### Proof

We normalize the capacities of each good and the total budget of all agents to
$1$, and consider an excess demand function
$f_{j}(\mathbf{p})=\sum_{i=1}^{n}x_{ij}(p_{j})-1$ for
$\mathbf{p}\in\Delta_{m}$, where $\Delta_{m}$ is a standard simplex. Next, we
define a coloring function $c:\mathbf{p}\mapsto\small\\{1,...,m\small\\}$,
such that $c(\mathbf{p})=j$ if $f_{j}(\mathbf{p})\leq 0$ and $p_{j}\neq 0$.
Such a coloring function on the standard simplex satisfies Sperner’s lemma,
which implies that we can find a $\mathbf{p}^{*}$, such that
$f_{j}(\mathbf{p}^{*})\leq 0$, $\forall j$, showing $\forall j$ that
$\sum_{i=1}^{n}x_{ij}(p_{j}^{*})\leq 1$.

To prove that the above inequality is an equality, we suppose that $\exists
j$, such that $\sum_{i=1}^{n}x_{ij}(p_{j}^{*})<1$. Then we consider two cases:
i) $p_{j}>0$ and ii) $p_{j}=0$. For both cases we find contradictions and
prove the strict inequality is impossible under the condition that there
exists a good $j$ without any physical constraints. This establishes our claim
that $\mathbf{p}^{*}$ is the equilibrium price vector.

A detailed proof of this theorem is presented in Appendix section 7.2. We also
note the technical assumption is not very demanding. This is because we can
achieve the requisite condition by introducing a good, such as “real” money
that is available in sufficient quantity and for which each agent in the
economy has a strictly positive value. Another method in which this can be
achieved is by allowing agents to keep unused budget for use in the future, in
which case we can treat budget as a good, which has been considered and
analyzed in [17].

###  2.4 Market Equilibrium may not be Unique

We now show that even if the market equilibrium exists, it may be that the
equilibrium is not unique, which further establishes that the problem of
determining a market equilibrium under the addition of physical constraints is
fundamentally different from the traditional Fisher market framework. In
particular, we establish non-uniqueness of the market equilibrium through the
following proposition.

######  Proposition 2 ()

The market equilibrium for IOP may not be unique.

We use a counterexample presented in the Appendix section 7.3 to establish the
non-uniqueness of the market equilibrium in the addition of physical
constraints.

###  2.5 Characterizing Optimal Solution of IOP

Having established the conditions for the existence of a market equilibrium
and that one cannot expect the resulting equilibrium to be unique, we now turn
to characterizing the optimal solution of the IOP. In traditional Fisher
markets, each agent purchases the goods $j^{*}$ corresponding to the highest
bang-per-buck ratio, i.e., agents purchase goods such that:
$j^{*}=\operatorname*{arg\,max}_{j}\left\\{\frac{u_{ij}}{p_{j}}\right\\}$.
However, in the presence of physical constraints, when a buyer observes a
price vector $\mathbf{p}$, which goods will they purchase in each resource
type and how many different goods will they purchase in each type?

To answer these questions, we study the influence of the physical constraints
on an agent’s decision making problem through the consideration of a feasible
solution set for buyer $i$ and resource type $t\in T_{i}$ as follows:

###### Definition 2

(Feasible Set). Given a price vector $\mathbf{p}\in\mathbb{R}_{\geq 0}^{m}$, a
feasible solution set for buyer $i$ and resource type $t$ is given by:

$S_{t}=\left\\{(u_{t},w_{t})|\exists\left\\{x_{ij}\right\\}_{j\in
t},\sum_{j\in t}x_{ij}\leq 1,x_{ij}\geq 0,\forall j\in t,u_{t}=\sum_{j\in
t}u_{ij}x_{ij},w_{t}=\sum_{j\in t}x_{ij}p_{j}\right\\}$

The above definition specifies the utility and budget of agent $i$ when
consuming type $t$.

Next, we observe that the solution set $S_{t}$ can be viewed as lying in the
convex hull of the points defined by $(u_{ij},p_{ij})$, $j\in t$ and the
origin in the price-utility plane, as shown by the enclosed region in Figure
2. The lower frontier of this convex hull, as shown in bold, from the origin
to $(u_{ij_{\max}},p_{j_{\max}})$, where
$j_{\max}=\operatorname*{arg\,max}_{j\in t}\left\\{u_{ij}\right\\}$, is piece-
wise linear and is characterised by slopes
$\theta^{t}=(\theta_{1}^{t},\theta_{2}^{t},...,\theta_{k_{t}}^{t})$. As shown
on the right in Figure 2, given a fixed budget $w_{t}$ for type $t$, the
maximal utility that can be obtained from type $t$ must be the intersection of
the line $p=w_{t}$ and the lower frontier of the convex hull when $w_{t}\leq
p_{j_{\max}}$. Otherwise the maximal utility obtained is $u_{ij_{\max}}$.
Therefore, an optimal solution of IOP must lie on the lower frontier, with
endpoints of the line segments corresponding to goods and line segments
corresponding to virtual products. Each virtual product is characterized by
its two endpoints, defined as:

###### Definition 3

(Virtual Product). A virtual product is characterized by its two endpoints
$A=(u_{ij_{1}},p_{j_{1}})$ and $B=(u_{ij_{2}},p_{j_{2}})$ with a slope
$\theta_{j_{1}j_{2}}=\frac{p_{j_{2}}-p_{j_{1}}}{u_{ij_{2}}-u_{ij_{1}}}$. Then
its bang-per-buck
$=\frac{1}{\theta_{j_{1}j_{2}}}=\frac{u_{ij_{2}}-u_{ij_{1}}}{p_{j_{2}}-p_{j_{1}}}$.

Figure 2: The enclosed region represents the convex hull corresponding to the
solution set $S_{t}$. The vertices on the lower frontier (in bold) correspond
to the goods and the segments correspond to virtual products. The figure on
the right shows that any optimal solution must lie on the lower frontier of
the convex hull, as indicated by the point $C$.

While in Fisher markets, buyers purchase goods that maximize their bang-per-
buck ratios, in the presence of physical constraints, we show that agents
purchase goods in the descending order of the virtual products’ bang-per-buck
ratios by establishing the following theorem:

######  Theorem 2.2 ()

Given a price vector $\mathbf{p}\in\mathbb{R}_{\geq 0}^{m}$, agent $i$ can
obtain their optimal solution $\mathbf{x}_{i}^{*}\in\mathbb{R}^{m}$ of the IOP
by mixing all virtual products from different types together and spending
their budget $w_{i}$ in the descending order of the virtual products’ bang-
per-buck. Furthermore, at most one unit of each virtual product can be
purchased by agent $i$.

Note that when two virtual products have the same slope, irrespective of
whether they are in the same type or different types, ties can be broken
arbitrarily. Further, an immediate corollary follows, which answers the
question of how many different goods an agent will purchase in each type.

######  Corollary 1 ()

For any agent $i$, there exists an optimal solution
$\mathbf{x}_{i}^{*}\in\mathbb{R}^{m}$, such that $i$ purchases two different
goods in at most one resource type. For all other resource types, agent $i$
buys at most one good.

A detailed proof of Theorem 2.2 and Corollary 1 are presented in Appendix
sections 7.4 and 7.5 respectively. We note that the optimal solution
$\mathbf{x}_{i}^{*}$ is the optimal solution for IOP given any price vector
$\mathbf{p}$, which may not be the equilibrium price. The optimal solution may
not be unique and Corollary 1 states there exists such an optimal solution but
this does not imply all solutions must satisfy these conditions. Furthermore,
note that these results can easily be extended to the case when there exists
some product that does not have any physical constraint. The detailed
discussion and interpretation by examples of the optimal solution of the IOP
are presented in Appendix sections 7.6 and 7.7. Having established properties
of the IOP, we now turn to the problem of deriving equilibrium prices in the
market in the addition of physical constraints.

##  3 Generalizing the Fisher Social Optimization Problem to Accommodate
Physical Constraints

A desirable property of a Fisher market is that the market equilibrium outcome
maximizes a social objective while individuals receive their most favoured
bundle of goods given the set prices. As this property of Fisher markets holds
when we consider budget and capacity constraints, a natural question to ask is
whether we can still achieve this property under the addition of the physical
constraints (3c). We start by showing that the addition of these constraints
and under no further modifications to Fisher markets, market clearing
conditions fail to hold. To do this we define the social optimization problem
(SOP1) with additional constraints in section 3.1 and then compare the KKT
conditions of the two problems (IOP and SOP1) to establish that a market
clearing outcome does not hold in section 3.2.

We then address this negative result by defining a perturbed social
optimization problem (BP-SOP) in section 3.3 in which we adjust the budgets of
the agents. Then, in section 3.4, we show how to choose these budget
perturbations to guarantee the equivalence of its KKT conditions with that of
the IOP when prices are set based on the dual variables of BP-SOPs capacity
constraints. Finally, we provide an economic interpretation of our budget
perturbed formulation in section 3.5.

###  3.1 A Social Optimization Problem with Additional Constraints

We first define the natural extension of the Fisher market social optimization
problem (2a)-(2c) with the addition of physical constraints (3c). We note that
barring the additional constraints, the following problem (4a)-(4d) (SOP1) is
identical to the Fisher market social optimization problem.

$\displaystyle\underset{\displaystyle\mathbf{x}_{i}\in\mathbb{R}^{m},\forall
i\in[n]}{\mathrm{max}}\quad
u(\mathbf{x}_{1},...,\mathbf{x}_{n})=\sum_{i=1}^{n}w_{i}\log\left(\sum_{j=1}^{m}u_{ij}x_{ij}\right)$
(4a)
$\displaystyle\mathmakebox[\widthof{$\underset{\displaystyle\phantom{\mathbf{x}_{i}\in\mathbb{R}^{m},\forall
i\in[n]}}{\mathrm{max}}$}][c]{\mathmakebox[\widthof{$\mathrm{max}$}][l]{\mathrm{\kern
1.00006pts.t.}}}\quad$ $\displaystyle\sum_{i=1}^{n}x_{ij}=\bar{s}_{j},\forall
j\in[m]$ (4b) $\displaystyle A_{t}^{(i)}\mathbf{x}_{i}\leq 1,\forall t\in
T_{i},\forall i\in[n]$ (4c) $\displaystyle x_{ij}\geq 0,\forall i,j$ (4d)

###  3.2 A KKT Comparison of IOP and SOP1

In the original Fisher Market formulation, the equilibrium price vector
corresponds to the dual variables of the capacity constraints of the social
optimization problem, and at this equilibrium price, the KKT conditions of the
individual and social optimization problems are equivalent [5]. We follow a
similar approach when considering the individual and social optimization
problems with additional constraints (IOP and SOP1 respectively) and show that
market clearing conditions fail to exist by establishing the following result.

######  Theorem 3.1 ()

The price vector $\mathbf{p}\in\mathbb{R}_{\geq 0}^{m}$ corresponding to the
optimal dual variables of the capacity constraint (4b) of SOP1 is not an
equilibrium price, i.e., the market clearing KKT conditions of IOP and SOP1
are not equivalent.

###### Proof

We derive the first order necessary and sufficient KKT conditions of the
social optimization problem SOP1 and show that under the optimal price vector
corresponding to the dual variables of the capacity constraint, the budgets of
the agents will not be completely used up. As a result, a market clearing
equilibrium cannot hold.

A detailed proof of this claim is presented in the Appendix section 7.8. This
result establishes that the prices a social planner would set through the
solution of SOP1 does not guarantee a market clearing outcome, as there would
be agents with unused budgets. We now address this negative result through a
modification to SOP1 that will enable us to set market clearing prices under
the addition of physical constraints.

###  3.3 A Budget Perturbed Social Optimization Problem

We present a reformulated social optimization problem in which we modify the
budget of agents through a variable $\lambda_{i}$ for each agent $i$. This
variable is introduced because of the additional physical constraints that are
not present in the original Fisher market problem. The exact value that
$\lambda_{i}$ should take so that the the market clears is derived in detail
in the KKT analysis in section 3.4. The Budget Perturbed Social Optimization
Problem (BP-SOP) is represented as:

$\displaystyle\underset{\displaystyle\mathbf{x}_{i}\in\mathbb{R}^{m},\forall
i\in[n]}{\mathrm{max}}\quad
u(\mathbf{x}_{1},...,\mathbf{x}_{n})=\sum_{i=1}^{n}(w_{i}+\lambda_{i})\log\left(\sum_{j=1}^{m}u_{ij}x_{ij}\right)$
(5a)
$\displaystyle\mathmakebox[\widthof{$\underset{\displaystyle\phantom{\mathbf{x}_{i}\in\mathbb{R}^{m},\forall
i\in[n]}}{\mathrm{max}}$}][c]{\mathmakebox[\widthof{$\mathrm{max}$}][l]{\mathrm{\kern
1.00006pts.t.}}}\quad$ $\displaystyle\sum_{i=1}^{n}x_{ij}=\bar{s}_{j},\forall
j$ (5b) $\displaystyle A_{t}^{(i)}\mathbf{x}_{i}\leq 1,\forall t\in
T_{i},\forall i\in[n]$ (5c) $\displaystyle x_{ij}\geq 0,\forall i,j$ (5d)

with capacity constraints (5b), physical constraints (5c) and non-negativity
constraints (5d).

###  3.4 Deriving Perturbation Constants Using KKT Conditions

We now show that under an appropriate choice of the $\lambda_{i}$
perturbations for all agents $i$, the KKT conditions of BP-SOP and IOP are
equivalent when prices are set in the market through the dual variables of the
capacity constraints (5b). Observing that for any choice of
$\lambda=(\lambda_{1},...,\lambda_{n})$, BP-SOP remains a convex optimization
problem, it is necessary and sufficient to verify the first order KKT
conditions for BP-SOP and IOP. To establish the first order KKT equivalence
between the two problems, we first define $r_{it}$ as the dual variable
associated with the allocation constraint (5c) associated with agent $i$ and
good type $t$. Further, we define a fixed point of the problem BP-SOP as one
when $\lambda_{i}=\sum_{t=1}^{l_{i}}r_{it}$, where $l_{i}=|T_{i}|$. The
reasons for this choice of a fixed point is its use in establishing the market
equilibrium through the following theorem:

######  Theorem 3.2 ()

There is a one-to-one correspondence of the equilibrium price vector
$\mathbf{p}\in\mathbb{R}_{\geq 0}^{m}$ and a fixed point solution of BP-SOP,
i.e., $\lambda_{i}=\sum_{t=1}^{l_{i}}r_{it}$, $\forall i$, where $r_{it}$ is
the optimal dual multiplier of the constraint $A_{t}^{(i)}\mathbf{x}_{i}\leq
1$ in BP-SOP.

The above theorem states in one direction that the market clearing KKT
conditions of BP-SOP are equivalent to that of the IOP if for each agent $i$,
the budget perturbation constant $\lambda_{i}=\sum_{t=1}^{l_{i}}r_{it}$.
Furthermore, the above theorem also states the converse, i.e., any equilibrium
price in the market for the social optimization problem BP-SOP must correspond
to a fixed point, i.e., $\lambda_{i}=\sum_{t=1}^{l_{i}}r_{it}$. We now present
a proof sketch of Theorem 3.2 and show the complete derivation in Appendix
section 7.9.

###### Proof

We first derive the necessary and sufficient first order KKT conditions for
the BP-SOP and IOP. The forward direction of our claim follows from
considering a market equilibrium of the IOP and using this to show that
$\lambda_{i}=\sum_{t=1}^{l_{i}}r_{it}$, $\forall i$ is the fixed point of BP-
SOP. For the converse, we can show that if we set
$\lambda_{i}=\sum_{t=1}^{l_{i}}r_{it}$, $\forall i$, then each agent
completely uses up their budget, while all the goods are sold to capacity.

The above result implies that the prices a social planner would set through
the solution of BP-SOP would guarantee a market clearing outcome. However, we
note that for this mechanism to be implementable we need to determine the
exact budget perturbation parameters which depend on the dual variables of the
capacity constraint of BP-SOP, which we do not have knowledge of. This issue
is addressed through a fixed point iterative procedure in section 4.

###  3.5 Economic Relevance of Solution of BP-SOP

Having established a one-to-one correspondence between the equilibrium price
vector and the fixed point solution of BP-SOP, we now show the economic
relevance of the resulting allocations under the appropriately chosen budget
perturbation constants. We first observe that due to the KKT equivalence of
BP-SOP and IOP at the equilibrium price and the corresponding fixed point, we
have that each agent obtains their most preferred bundle of goods under the
set prices.

We now interpret the dual variable $r_{it}$ of the physical constraint as the
price that agent $i$ must pay to purchase good type $t$. Hence, the total
price that a buyer must pay to purchase goods $j$ belonging to type $t$ is
$\sum_{j\in t}p_{j}x_{ij}+r_{it}$; however, the buyer only observes the price
$p_{j}$ for good $j$ in the IOP. Thus, to reconcile the price difference the
buyer observes and that in BP-SOP, we need to pay the additional price
$\sum_{t}r_{it}$ for buying goods in the different types by augmenting agents’
budgets. Further, buyers are no longer purchasing goods with the highest bang-
per-buck, and under the adjusted price set $p_{j}^{\prime}=p_{j}+r_{it}$,
where one unit of good $j$ is purchased and $j\in t$, agents are purchasing
goods with the highest “adjusted” bang-per-buck. Finally, we observe that more
constrained agents have larger weights $\lambda_{i}$ than less constrained
agents, ensuring more constrained agents have “higher priorities” and thus an
allocation that lies within their feasible constraint set.

##  4 Fixed Point Scheme to determine Perturbation Constants

In the above budget perturbed social optimization formulation, we required
that $\lambda_{i}=\sum_{t=1}^{l_{i}}r_{it}$, i.e., $\lambda_{i}$ depends on
the dual variables of the problem, which we have no knowledge of apriori. In
this section, we show how to compute the appropriate value of $\lambda_{i}$
through the means of a fixed point iteration in section 4.1 and numerically
establish its convergence through experiments in section 4.2.

###  4.1 Fixed Point Iteration Algorithm

To determine the true value of the perturbation parameters specified by the
vector $\lambda\in\mathbb{R}_{\geq 0}^{n}$, we consider an iterative scheme of
the form
$G\left(\lambda_{1}^{(k)},...,\lambda_{n}^{(k)}\right)=\left(\mathbf{r}_{1}^{(k)},...,\mathbf{r}_{n}^{(k)}\right)$,
where we update our perturbation parameters as:
$\left(\lambda_{1}^{(k+1)},...,\lambda_{n}^{(k+1)}\right)=\left(\sum_{t=1}^{l_{i}}r_{1t}^{(k)},...,\sum_{t=1}^{l_{i}}r_{nt}^{(k)}\right)$.
Here $G$ is a function that takes in the $k^{th}$ iterate $\lambda_{i}^{(k)}$
for all agents $i$, solves the corresponding social optimization problem BP-
SOP and returns the dual variables, $\mathbf{r}_{i}^{(k)}\in\mathbb{R}_{\geq
0}^{l_{i}}$, corresponding to the physical constraints.

The following algorithm depicts the fixed point iterative scheme, where,
$\lambda=(\lambda_{1},...,\lambda_{n})$, and
$\mathbf{R}=(\mathbf{r}_{1},...,\mathbf{r}_{n})$, the dual variables
corresponding to the physical constraints in BP-SOP.

Input : Tolerance $\epsilon$, Function $G(\cdot)$ to calculate dual variables
of physical constraints of BP-SOP

Output : Budget Perturbation Parameters $\lambda$

$\lambda\leftarrow\mathbf{0}$ ;

$\mathbf{R}\leftarrow G(\lambda)$ ;

$q_{i}\leftarrow\sum_{t=1}^{l_{i}}r_{it}$, $\forall i$ ;

while  _$\left\lVert\lambda-\mathbf{q}\right\rVert_{2} >\epsilon$_ do

$\lambda_{i}\leftarrow\sum_{t=1}^{l_{i}}r_{it}$, $\forall i$ ;

$\mathbf{R}\leftarrow G(\lambda)$ ;

$q_{i}\leftarrow\sum_{t=1}^{l_{i}}r_{it}$, $\forall i$ ;

end while

Algorithm 1 Fixed Point Scheme

###  4.2 Numerical Experiments with Iterative Scheme

We now numerically evaluate the convergence of the iterative scheme for BP-SOP
through the implementation of Algorithm 1 to the allocate agents to public
spaces.

We consider a neighborhood with a population of $n=200$ people and $m=6$
public spaces, with three resource types including two grocery stores, two
parks, and two beaches. The capacities of the public spaces are
$\bar{s}_{j}=100$, $\forall j\in[m]$ and the physical constraint used in this
numerical experiment is that each individual would not want to go to more than
one of the public spaces within the same resource type over the course of a
day, defining three identical physical constraints for each person.

Further, we consider an economy where each person $i$ is endowed with a budget
$w_{i}$ through electronic coupons that they can spend over a time horizon of
a day to use these public spaces. In this experiment, we endow agents with
random budgets, although these could be assigned differently including giving
each person equal budgets. Finally, the people have different values for the
public spaces, and their preferences are captured through their utilities for
availing each of these public spaces. This can depend on a range of factors
including their proximity to the public space and quality of service of a
given public space within a certain type relative to other public spaces
within the same type. For the purposes of this analysis, the utilities
$u_{ij}$, $\forall i,j$, are randomly generated.

On the above defined problem instance, we run Algorithm 1, wherein we
terminate when
$\left\lVert\lambda^{(k)}-\sum_{t=1}^{3}\mathbf{r}_{t}^{(k)}\right\rVert\leq\epsilon$,
where $\lambda^{(k)}=\left(\lambda_{1}^{(k)},...,\lambda_{n}^{(k)}\right)$ and
$\mathbf{r}_{t}^{(k)}=\left(r_{1t}^{(k)},...,r_{nt}^{(k)}\right)$, where
$r_{it}^{(k)}$ is the dual variable of the optimization problem at iteration
$k$, and $n$ is the total number of people, which is 200 for our problem
instance. The experiment confirmed that for the above public goods allocation
problem (as well as for other tested problem instances) that the iterative
scheme converges in fewer than 40 iterations to a fixed point as can be
observed in Figure 3, highlighting the computational feasibility of our
mechanism for large problem instances. Furthermore, we did not require any
structure on the budgets and utilities, as these were randomly chosen, to
observe convergence.

Figure 3: Numerical Convergence of fixed point iterative scheme with 200
people, 6 goods and 3 types of goods. The budgets and utilities were assigned
randomly to agents, and the convergence is observed after about 40 iterations.

We note that the numerical experiments confirmed the feasibility of the
allocations with each good being used to capacity. In particular, for each
agent the sum of their allocations within each resource type, i.e., grocery
stores, parks and beaches, is exactly one, indicating feasibility with respect
to the added physical constraints. We note that in the absence of the physical
constraint, if we used the pure Fisher market framework then an individual
could have received a highly undesirable allocation. For instance, the pure
Fisher market framework without these physical constraints may allocate a
certain agent to only grocery stores, if the agent had the highest utility to
price ratio for grocery stores as compared to other public resources. Our
mechanism overcomes this problem by accounting for these physical constraints
whilst guaranteeing a socially beneficial allocation.

##  5 Implementation of Mechanism

In this section, we demonstrate how our proposed budget adjustment mechanism
could be implemented in the real world. In particular, we elucidate the
details of the implementation of our mechanism to efficiently allocate “time
of use” permits for a public space, such as a beach. Our public goods are the
different blocks of time that people can use the beach with the physical
constraint that people can use the beach at most once per day, i.e., the
resource types are the days an agent is interested in using the beach. We
first highlight the broad implementation plan of our mechanism in setting
prices to allocate “time of use” permits to people using a beach:

  1. 1.

As a first step, we will need to create a schedule for the usage of the beach,
i.e., we need to divide the day into different blocks of time, each of which
corresponds to a public good.

  2. 2.

We will set non-monetary prices for the different times of use through our
market mechanism.

  3. 3.

Finally, the budgets of individuals can be allocated through electronic
coupons, which can then be used to purchase “time of use” permits priced in
non-monetary units.

However, in real world implementation, there is an additional hurdle in
setting appropriate prices, as the market does not have information on the
utilities of buyers, which serve as inputs to BP-SOP. Thus, we propose the
following methodology to set market clearing prices using our mechanism while
learning information on the utilities of buyers over time:

  1. 1.

We classify people into different groups based on parameters such as their
income level and demographic information, so that we can assign all members
within a group the same utility coefficients. This helps in reducing the
computational complexity of the problem.

  2. 2.

We initialize a price for the different “times of use” by running our market
mechanism with some prior on the utilities of the agents, which can be
obtained through data on prior customer demands or just be assigned uniformly
amongst all agent groups for all goods.

  3. 3.

Based on the set prices, people will purchase “time of use” permits. We will
observe the “buying-behavior” of these different groups of individuals through
a comparison between the demand of people at the set prices and the supply of
these goods, i.e., the good capacities.

  4. 4.

This observed discrepancy between the capacities of the beach and the
corresponding demand can be used to re-calibrate the utility coefficients
(e.g., through non-parametric statistical estimation of observed demands) and
adjust prices in the market.

  5. 5.

We can continue this utility and price adjustment process iteratively until we
have that the capacities of the beach at each “time of use” closely matches
the demand of the good.

Through this adaptive learning process, we will be able to learn each agent’s
utility coefficients and set appropriate prices (evaluated through the dual
variables of our proposed Fisher market mechanism) to achieve the desired
market clearing outcome. In particular, employing “time of use” permits (at
three hour intervals) that are priced according to our mechanism will help
achieve an intermediate outcome between the two extremes of an overused and an
underused beach presented in Figure 1. We depict such an intermediate market
outcome in Figure 4.

Figure 4: Our market outcome that will achieve an intermediate between an
overcrowded and an underused beach. Through our pricing mechanism, customers
will purchase time of use permits (in this case at 3 hour intervals) in a
“controlled” manner resulting in neither overcrowded or underused public
resources.

##  6 Conclusions and Future Work

In this work, we have developed market based mechanisms to more efficiently
allocate capacity constrained public goods that are priced in non-monetary
units. We defined a new individual optimization problem IOP in the presence of
physical constraints and established market equilibrium properties of this
problem, including existence, non-uniqueness and thoroughly characterized its
optimal solution. Even though the properties of IOP are fundamentally
different from that of the individual optimization problem in Fisher markets,
we proposed a mechanism to derive a market equilibrium in the presence of
physical constraints, thereby generalizing the Fisher market framework. In
particular, we reformulated the Fisher market setup to account for additional
physical constraints by perturbing the budgets of agents and defining a new
social optimization problem BP-SOP. We then showed a one-to-one correspondence
between the equilibrium price vector and a fixed point solution of BP-SOP
through the verification of KKT conditions. Next, we established the
significance of the budget perturbation constants and that under the
appropriate choice of these constants, a market equilibrium is attained such
that under the set prices each agent’s individual utilities are maximized. To
obtain the right budget perturbation parameters, we used a fixed point
iteration scheme for the reformulated social optimization problem and
numerically showed the convergence of this iterative procedure indicating the
applicability of our mechanism for real world problem instances.

There are various interesting directions of future research that warrant more
study. First, the allocations provided by our market mechanism are fractional,
and as we would like to make discrete allocations, it would be interesting to
investigate the loss in social efficiency under integral constraints.
Furthermore, while we have numerically shown convergence guarantees of our
iterative scheme, it would be beneficial to theoretically understand the
convergence to the fixed point as well as the rate of convergence of our
procedure. Next, we believe that a stronger characterization of the
computational complexity of this problem would provide a more nuanced
appreciation of whether computing the exact fixed point is feasible in
polynomial time. Finally, an interesting area of research is generalizing this
framework to an online setting in which customers arrive in the market
platform sequentially and an irrevocable decision needs to be made about the
prices that should be set in the market while still achieving a socially
efficient allocation.

## References

  * [1] Wolfgang Blümel, Rüdiger Pethig, and Oskar von dem Hagen.  The theory of public goods : A survey of recent issues.  Journal of Institutional and Theoretical Economics (JITE) / Zeitschrift für die gesamte Staatswissenschaft, 142(2):241–309, 1986.
  * [2] Toshio Yamagishi and Kaori Sato.  Motivational bases of the public goods problem.  Journal of Personality and Social Psychology, 50(1):67–73, 1986\.
  * [3] Anna Goldfarb.  How to navigate public spaces and more, 2020.
  * [4] Coronavirus disease (covid-19) advice for the public, 2020.
  * [5] Nikhil R. Devanur, Christos Papadimitriou, Amin Saberi, and Vijay V. Vazirani.  Market equilibrium via a primal–dual algorithm for a convex program.  Journal of the ACM, 55(5), 2008.
  * [6] Vijay V. Vazirani.  Spending constraint utilities with applications to the adwords market.  Mathematics of Operations Research, 35(2):458–478, 2010.
  * [7] Jugal Garg, Martin Hoefer, and Kurt Mehlhorn.  Approximating the nash social welfare with budget-additive valuations.  In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2326–2340, 2018.
  * [8] Léon Walras.  Elements of Pure Economics: Or, The Theory of Social Wealth.  American Economic Association. Translation series. American Economic Association, 1954.
  * [9] Kenneth J. Arrow and Gerard Debreu.  Existence of an equilibrium for a competitive economy.  Econometrica, 22(3):265–290, 1954.
  * [10] William C. Brainard and Herbert E. Scarf.  How to compute equilibrium prices in 1891.  American Journal of Economics and Sociology, 64(1):57–83, 2005\.
  * [11] Edmund Eisenberg and David Gale.  Consensus of subjective probabilities: The pari-mutuel method.  The Annals of Mathematical Statistics, 30(1):165–168, 1959.
  * [12] David Gale.  The Theory of Linear Economic Models.  The University of Chicago Press, 1960.
  * [13] Xiaohui Bei, Jugal Garg, Martin Hoefer, and Kurt Mehlhorn.  Earning limits in fisher markets with spending-constraint utilities.  In Algorithmic Game Theory, pages 67–79, Cham, 2017. Springer International Publishing.
  * [14] Nikhil R. Devanur.  The spending constraint model for market equilibrium: Algorithmic, existence and uniqueness results.  In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’04, page 519–528, New York, NY, USA, 2004. Association for Computing Machinery.
  * [15] Benjamin Birnbaum, Nikhil R. Devanur, and Lin Xiao.  New convex programs and distributed algorithms for fisher markets with linear and spending constraint utilities.  2010\.
  * [16] Nikhil R. Devanur, Kamal Jain, Tung Mai, Vijay V. Vazirani, and Sadra Yazdanbod.  New convex programs for fisher’s market model and its generalizations.  CoRR, abs/1603.01257, 2016.
  * [17] Lihua Chen, Yinyu Ye, and Jiawei Zhang.  A note on equilibrium pricing as convex optimization.  Internet and Network Economics, 2007.
  * [18] Eric Budish.  The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.  Journal of Political Economy, 119(6):1061–1103, 2011.
  * [19] Artur Gorokh, Siddhartha Banerjee, and Krishnamurthy Iyer.  Near-efficient allocation using artificial currency in repeated settings.  Social Science Research Network, 2016.
  * [20] Benjamin Birnbaum, Nikhil R. Devanur, and Lin Xiao.  Distributed algorithms via gradient descent for fisher markets.  In Proceedings of the 12th ACM conference on Electronic commerce, pages 127–136, 2011.
  * [21] Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani.  Algorithmic Game Theory.  Cambridge University Press, 2007.

##  7 APPENDIX

###  7.1 Proof of Proposition 1

We now restate and proceed to prove Proposition 1.

See 1

###### Proof

Consider a market with two buyers and two goods, with capacities
$\bar{s}_{1}=1.5$ and $\bar{s}_{2}=0.5$, and utilities and budgets as
specified in Table 1.

Table 1: Utilities and Budgets of two Buyers in a two buyer, two good market | Utility for Good 1 | Utility for Good 2 | Budget
---|---|---|---
Buyer 1 | 200 | 0.1 | 15
Buyer 2 | 100 | 1.1 | 5

Denoting $x_{ij}$ as the amount of good $j$ that buyer $i$ purchases, we
consider the following physical constraints: $x_{11}+x_{12}\leq 1$ and
$x_{21}+x_{22}\leq 1$ for buyer’s 1 and 2 respectively.

To show that no equilibrium exists in this market, we consider the following
two cases:

  1. 1.

$p_{1}>10$: From the physical constraint, buyer 1 can buy at most one unit of
good 1 and buyer 2 cannot afford 0.5 units of good 1 and so it follows that
$\sum_{i=1}^{2}x_{ij}(p_{1})<\bar{s}_{1}=1.5$, establishing that good 1 cannot
be cleared. Thus, $p_{1}>10$ cannot be a market clearing price.

  2. 2.

$p_{1}\leq 10$: Since the utilities of both buyers is higher for good 1 than
for good 2, it must be that the price for good 1 must be higher than the price
for good 2. However, this implies that $p_{2}\leq p_{1}\leq 10$, which implies
that buyer 1 cannot use up their budget, since the buyer can purchase at most
one unit of both goods combined. Thus, $p_{1}\leq 10$ cannot be a market
clearing price.

The two cases above establish that for this example a market equilibrium fails
to exist in the presence of additional physical constraints not considered in
the Fisher market framework.

###  7.2 Proof of Theorem 1

We now restate and proceed to prove Theorem 2.1.

See 2.1

###### Proof

We start by normalizing the capacities of each good to $1$, i.e.,
$\bar{s}_{j}=1$ $\forall j$, and normalizing the total budget of all agents to
1, i.e., $\sum_{i=1}^{n}w_{i}=1$.

Next, we define an excess demand function
$f_{j}(\mathbf{p}^{*})=\sum_{i=1}^{n}x_{ij}(p_{j}^{*})-1$ and use Sperner’s
lemma to prove the existence of an equilibrium price vector
$\mathbf{p}^{*}=(p_{1}^{*},p_{2}^{*},...,p_{m}^{*})\in\Delta_{m}$, where
$\Delta_{m}$ is the standard simplex, such that for all goods $j$, the excess
demand function $f_{j}(\mathbf{p}^{*})=\sum_{i=1}^{n}x_{ij}(p_{j}^{*})-1=0$.

Next, for any $\mathbf{p}\in\Delta_{m}$, we define a coloring function
$c:\mathbf{p}\mapsto\small\\{1,...,m\small\\}$, such that $c(\mathbf{p})=j$ if
$f_{j}(\mathbf{p})\leq 0$ and $p_{j}\neq 0$. We claim that such a coloring
satisfies Sperner’s lemma.

To see this, we first note that all the $m$ corner points of the simplex must
be colored with different colors, as at each of the corner points $k$ exactly
one entry $p_{k}=1\neq 0$. In fact when $p_{k}=1$, as the budgets are
normalized to $1$, it must be that $f_{k}(\mathbf{p})\leq 0$, as at most one
unit of good $k$ can be purchased by all agents collectively. Thus, we have
that all the corner points of the simplex must be colored with a different
color. For any other bounding vertex there must exist $j$, such that
$p_{j}\neq 0$ and $f_{j}(\mathbf{p})\leq 0$. This is because if for all $j$,
such that $p_{j}\neq 0$, we have that $f_{j}(\mathbf{p})>0$ then
$\sum_{i=1}^{n}\sum_{j=1}^{m}p_{j}x_{ij}>1=\sum_{i=1}^{n}w_{i}$, a
contradiction. Thus, we have a valid coloring, which satisfies the condition
of Sperner’s lemma.

Next, by Sperner’s lemma we have that there must exist a base simplex such
that each of its corner points have distinct colors. Taking finer and finer
triangulations and using that the demand function is continuous, we can find a
$\mathbf{p}^{*}$, such that $f_{j}(\mathbf{p}^{*})\leq 0$, $\forall j$, as
each subsequent triangulation still lies on the standard simplex. Thus, we
have shown $\forall j$ that $\sum_{i=1}^{n}x_{ij}(p_{j}^{*})\leq 1$.

Now to prove that the above inequality is in fact an equality, we proceed by
contradiction. In particular, we suppose that if $\exists j$ with $p_{j}>0$,
such that $\sum_{i=1}^{n}x_{ij}(p_{j}^{*})<1$, then clearly there must exist
some buyer $i$ whose budget was not used up since
$\sum_{i=1}^{n}\sum_{j=1}^{m}p_{j}x_{ij}<1=\sum_{i=1}^{n}w_{i}$. However, by
the condition that for all agents $i$ there exists a good $j$ without physical
constraints, $i$ can buy more units of good $j$ (and gain a strictly positive
utility), giving us our desired contradiction. Thus, $\mathbf{p}^{*}$ is an
equilibrium price vector.

Next, suppose that $\exists j$ with $p_{j}=0$, such that
$\sum_{i=1}^{n}x_{ij}(p_{j}^{*})<1$ and assume that $j\in t$, i.e., good $j$
belongs to good type $t$. Then we must have that for all agents $i$, the
physical constraint $\sum_{j\in t}x_{ij}=1$, i.e., it is tight, as otherwise
$i$ can buy more of good $j$ at $p_{j}=0$ to increase his/her utility. We
assume that type $t$ has $k$ products and the physical constraints for type
$t$ are such that $x_{ij}+\sum_{h\in t,h\neq j}x_{ih}\leq t_{i}$ for all
agents $i$, where $t_{i}$ must be such that $\sum_{i=1}^{n}t_{i}\geq k$ to to
ensure a feasible solution for the problem. This is because otherwise there
must exist some product that cannot be sold out. Now, since physical
constraints for all agents for good type $t$ are tight, we have that
$\sum_{i=1}^{n}\left(x_{ij}+\sum_{h\in t,h\neq
j}x_{ih}\right)=\sum_{i=1}^{n}t_{i}\geq k$. However, since type $t$ has $k$
products it must be that $\sum_{i=1}^{n}\left(x_{ij}+\sum_{h\in t,h\neq
j}x_{ih}\right)=k$, which implies that the product is sold to capacity. Since
we normalized the capacities of all products to one unit, it follows that
$\sum_{i=1}^{n}x_{ij}(p_{j}^{*})=1$, a contradiction. This again establishes
that $\mathbf{p}^{*}$ is an equilibrium price vector.

Having considered both cases of $p_{j}=0$ and $p_{j}>0$, we have established
that for all $j$ that $\sum_{i=1}^{n}x_{ij}(p_{j}^{*})=1$, with each agent’s
budget being completely used up, establishing that $\mathbf{p}^{*}$ is the
equilibrium price vector, and so a market equilibrium exists.

###  7.3 Proof of Proposition 2

We now restate and proceed to prove Proposition 2.

See 2

###### Proof

To establish that the market equilibrium may not be unique, we consider the
example of three buyers and three goods, with capacities
$\bar{s}_{1}=1,\bar{s}_{2}=2$ and $\bar{s}_{3}=1$ respectively and utilities
and budgets as specified in Table 2. Next, denoting $x_{ij}$ as the amount of
good $j$ that buyer $i$ purchases, we consider the following physical
constraints: $x_{11}+x_{12}\leq 1$, $x_{21}+x_{22}\leq 1$ and
$x_{31}+x_{32}\leq 1$ for buyer’s 1, 2 and 3 respectively, with buyers 1, 2
and 3 being able to purchase any amount of good 3.

Table 2: Utilities and Budgets of three Buyers in a three buyer, three good market | Utility for Good 1 | Utility for Good 2 | Utility for Good 3 | Budget
---|---|---|---|---
Buyer 1 | 100 | 1 | 2 | 20
Buyer 2 | 1 | 100 | 1 | 10
Buyer 3 | 1 | 100 | 1 | 10

We observe that if we set prices $\mathbf{p}=(11,10,9)$ or
$\mathbf{p}=(10,10,10)$ that the resulting allocation will be $x_{11}=1$,
$x_{13}=1$, $x_{22}=1$ and $x_{32}=1$. We note that under these prices and
allocations, each agent’s budgets are completely used up and each of the goods
are sold to capacity, establishing that both these price vectors are
equilibrium price vectors. Thus, we have shown that the equilibrium market
price may not necessarily be unique.

###  7.4 Proof of Theorem 2.2

We now restate and proceed to prove Theorem 2.2.

See 2.2

###### Proof

From Definition 2, we know for all resource types $t$ that $u_{t}=\sum_{j\in
t}u_{ij}x_{ij}^{*},w_{t}=\sum_{j\in t}x_{ij}^{*}p_{j}$.

Since $\mathbf{x}_{i}^{*}$ is an optimal solution, it must be that
$(\mathbf{x}_{i}^{*})_{j\in t}$, i.e., the restriction of $\mathbf{x}_{i}^{*}$
to the goods in resource type $t$, is an optimal solution to the following
problem:

$\displaystyle\underset{\displaystyle\left\\{x_{ij}\right\\}_{j\in
t}}{\mathrm{max}}\quad\sum_{j\in t}u_{ij}x_{ij}$ (6a)
$\displaystyle\mathmakebox[\widthof{$\underset{\displaystyle\phantom{\left\\{x_{ij}\right\\}_{j\in
t}}}{\mathrm{max}}$}][c]{\mathmakebox[\widthof{$\mathrm{max}$}][l]{\mathrm{\kern
1.00006pts.t.}}}\quad$ $\displaystyle\sum_{j\in t}x_{ij}p_{j}\leq w_{t}$ (6b)
$\displaystyle\sum_{j\in t}x_{ij}\leq 1,$ (6c) $\displaystyle x_{ij}\geq
0,\forall j\in t$ (6d)

The optimal solution $\left\\{x_{ij}^{*}\right\\}_{j\in t}$ corresponds to
some point $C$ (as depicted in Figure 2) in the lower frontier of the convex
hull $S_{t}$ from $(0,0)$ to $(u_{ij_{\max}},p_{j_{\max}})$, where
$j_{\max}=\operatorname*{arg\,max}_{j\in t}u_{ij}$. Thus, such a solution
$\left\\{x_{ij}^{*}\right\\}_{j\in t}$ can be viewed as purchasing virtual
products given by the different slopes $\theta$ in the descending order of
their bang-per-buck, which is equivalent to the ascending order of the slopes
$\theta$. In particular, one needs to purchase virtual products in the
descending order from the origin to the point $C$ (as depicted in Figure 2).

Having established that agent $i$ purchases goods in the descending order of
their bang-per-buck within each good type, we now show that agent $i$ in fact
purchases goods in the descending order of their bang-per-buck amongst all
good types. Thus, consider two different good types, $t$, $t^{\prime}$ and
suppose for contradiction that agent $i$ does not purchase goods in the
descending order of their bang-per-buck. Thus, it must be that $\exists$
$\theta_{a}\in t$ and $\theta_{b}\in t^{\prime}$, such that
$\theta_{a}<\theta_{b}$, where some amount of $\theta_{b}$ is bought but
$\theta_{a}$ is not completely purchased, i.e., strictly less than one unit of
it is bought.

Without loss of generality, assume that $\theta_{a}$ is defined by two goods
$j_{1},j_{2}\in t$ (with $u_{ij_{1}}<u_{ij_{2}}$) and $\theta_{b}$ is defined
by two goods $j_{3},j_{4}\in t^{\prime}$ (with $u_{ij_{3}}<u_{ij_{4}}$), as
depicted in Figure 5. Next, suppose that we have an optimal solution for these
four goods given by
$(x_{ij_{1}}^{*},x_{ij_{2}}^{*},x_{ij_{3}}^{*},x_{ij_{4}}^{*})$.

Figure 5: Goods $j_{1}$ and $j_{2}$ belong to type $t$ and goods $j_{3}$ and
$j_{4}$ belong to type $t^{\prime}$. The amount of virtual product consumed
lies somewhere along the line segment denoted by $A$ and $B$ for resource
types $t$ and $t^{\prime}$ respectively. We further have that
$\theta_{a}<\theta_{b}$.

Next, let $x_{ij_{4}}^{{}^{\prime}}=x_{ij_{4}}^{*}-\epsilon$ and
$x_{ij_{3}}^{{}^{\prime}}=x_{ij_{3}}^{*}+\epsilon$. We now observe that since
$(x_{ij_{3}}^{*},x_{ij_{4}}^{*})$ is feasible with respect to the physical
constraint, so is $(x_{ij_{3}}^{{}^{\prime}},x_{ij_{4}}^{{}^{\prime}})$. Next,
we observe that as we shift from the allocation
$(x_{ij_{3}}^{*},x_{ij_{4}}^{*})$ to
$(x_{ij_{3}}^{{}^{\prime}},x_{ij_{4}}^{{}^{\prime}})$, we “save” money given
by $\epsilon(p_{j_{4}}-p_{j_{3}})$, but also reduce utility by
$\epsilon(u_{ij_{4}}-u_{ij_{3}})$. But, now, we can use this “saved” money to
purchase $\theta_{a}$.

So consider, $(x_{ij_{1}}^{{}^{\prime}},x_{ij_{2}}^{{}^{\prime}})$, such that
$x_{ij_{2}}^{{}^{\prime}}=x_{ij_{2}}^{*}-\tau$ and
$x_{ij_{1}}^{{}^{\prime}}=x_{ij_{1}}^{*}+\tau$, where $\tau$ satisfies
$\tau(p_{j_{2}}-p_{j_{1}})=\epsilon(p_{j_{4}}-p_{j_{3}})$, i.e., we use our
unspent or “saved” money. As a result we gain a utility given by
$\tau(u_{ij_{2}}-u_{ij_{1}})$. Then we have that the change in the utility of
the agents is given by:

$u_{i}^{{}^{\prime}}-u_{i}^{*}=\tau(u_{ij_{2}}-u_{ij_{1}})-\epsilon(u_{ij_{4}}-u_{ij_{3}})=\epsilon(u_{ij_{4}}-u_{ij_{3}})\cdot\left(\frac{\tau}{\epsilon}\cdot\frac{u_{ij_{2}}-u_{ij_{1}}}{u_{ij_{4}}-u_{ij_{3}}}-1\right)$

Here, we have taken $u_{i}^{{}^{\prime}}$ as the utility corresponding to the
allocation
$(x_{ij_{1}}^{{}^{\prime}},x_{ij_{2}}^{{}^{\prime}},x_{ij_{3}}^{{}^{\prime}},x_{ij_{4}}^{{}^{\prime}})$
and $u_{i}^{*}$ as the utility corresponding to the allocation
$(x_{ij_{1}}^{*},x_{ij_{2}}^{*},x_{ij_{3}}^{*},x_{ij_{4}}^{*})$. Next, since
we have that $\tau(p_{j_{2}}-p_{j_{1}})=\epsilon(p_{j_{4}}-p_{j_{3}})$, it
follows that:

$u_{i}^{{}^{\prime}}-u_{i}^{*}=\epsilon(u_{ij_{4}}-u_{ij_{3}})\cdot\left(\frac{p_{j_{4}}-p_{j_{3}}}{p_{j_{2}}-p_{j_{1}}}\cdot\frac{u_{ij_{2}}-u_{ij_{1}}}{u_{ij_{4}}-u_{ij_{3}}}-1\right)=\epsilon(u_{ij_{4}}-u_{ij_{3}})\cdot\left(\frac{\theta_{b}}{\theta_{a}}-1\right)>0$

This establishes that
$(x_{ij_{1}}^{*},x_{ij_{2}}^{*},x_{ij_{3}}^{*},x_{ij_{4}}^{*})$ cannot be
optimal and so we have a contradiction. Thus, our claim follows.

###  7.5 Proof of Corollary 1

We now restate and proceed to prove Corollary 1.

See 1

###### Proof

An agent $i$ purchases virtual products until their budget is completely used
up or all the virtual products are bought, which implies that it is just the
last virtual product that the agent purchases, which may be bought for less
than one unit. As the remaining virtual products are all purchased completely,
these correspond to endpoints of the line segments of the lower frontier of
the convex hull of the solution set $S_{t}$. This indicates that agent $i$
either does not buy any good (if we are at the origin in Figure 2) or buys one
unit of one good only corresponding to an end point of one of the line
segments characterizing the lower frontier of the convex hull. Since the last
virtual product that the agent purchases may be bought for less than one unit,
this corresponds any point on the lower frontier of the convex hull. In
particular, if such a point lies in the middle of a line segment on the lower
frontier of the convex hull then we have that the agent buys a corresponding
fraction of two goods (associated with the line segment) within that resource
type.

###  7.6 Remark on Optimal Solution of IOP

The optimal solution of the IOP can also be characterized for goods that do
not have any physical constraints. For such a product $j$ without physical
constraints, we can define the value $\theta_{j}=\frac{p_{j}}{u_{ij}}$ and
augment this to the list of the $\theta$ values for each of the virtual
products. As we ordered the virtual products in the descending order of their
bang-per-buck $=\frac{1}{\theta_{j_{1}j_{2}}}$ for virtual products
corresponding to goods $j_{1}$ and $j_{2}$, we can do the same for this new
list of $\theta$ values that includes $\theta_{j}$.

Now buyer $i$ will purchase goods in the ascending order of the $\theta$
values that includes $\theta_{j}$ analogous to the result in Theorem 2.2. As
in Corollary 1, at most one unit of each virtual product can be purchased;
however, any amount of good $j$ (the good without physical constraints) can be
purchased. Thus, if agent $i$ still has budget at $\theta_{j}$, then the
remaining budget will be used to purchase product $j$.

###  7.7 Examples of Optimal Solution of IOP

We provide two examples to illustrate the use of virtual products in
characterizing the optimal solution of the IOP. For both examples, we consider
the market with $6$ products and an agent $i$. Furthermore, we denote the
utilities of the agent for each of the products as:
$u_{i1}=1,u_{i2}=2,u_{i3}=3,u_{i4}=4,u_{i5}=5,u_{i6}=6$ and the price that the
agent observes in the market as:
$p_{1}=0.1,p_{2}=0.4,p_{3}=0.7,p_{4}=1.2,p_{5}=1.7,p_{6}=2.4$. The difference
between the two examples we consider for this market will be in terms of the
physical constraints and budgets. In particular, the first example we consider
will be one wherein each of the goods in the market has physical constraints
and the second example will be one in which one of the goods, i.e., good $5$,
will not have any physical constraint.

Example 1 (All goods have Physical constraints): We endow agent $i$ with a
budget of $w_{i}=2.4$, and consider the following physical constraint for type
1 goods: $x_{i1}+x_{i3}+x_{i5}\leq 1$, and for type 2 goods:
$x_{i2}+x_{i4}+x_{i6}\leq 1$.

Given the price and the utilities, we can derive the $\theta$ values for the
virtual products by calculating the slopes of the lower frontier of the convex
hull in Figure 6, giving
$\theta_{1}=0.1,\theta_{2}=0.2,\theta_{3}=0.3,\theta_{4}=0.4,\theta_{5}=0.5,\theta_{6}=0.6$.

Figure 6: The solution set of the goods in example 1 for both the resource
types are depicted along with their corresponding $\theta$ values, i.e., the
slope of the line segments on the lower frontier of the convex hull (shown in
bold).

We also note that for a virtual product corresponding to points
$A=(u_{ij_{1}},p_{j_{1}})$ and $B=(u_{ij_{2}},p_{j_{2}})$, the price is
$p_{j_{2}}-p_{j_{1}}$ and the utility is $u_{ij_{2}}-u_{ij_{1}}$, with slope
$\theta_{j_{1}j_{2}}=\frac{p_{j_{2}}-p_{j_{1}}}{u_{ij_{2}}-u_{ij_{1}}}$.

Now, as the agent will buy products in the ascending order of the $\theta$
values until the agent’s budget is exhausted by Theorem 2.2, we will have that
the buyer purchases the following virtual products:

  * •

1 unit of $\theta_{1}$, with a total cost of $0.1$

  * •

1 unit of $\theta_{2}$, with a total cost of $0.4$

  * •

1 unit of $\theta_{3}$, with a total cost of $0.6$

  * •

1 unit of $\theta_{4}$, with a total cost of $0.8$

  * •

0.5 units of $\theta_{5}$, with a total cost of $0.5$

Mapping the purchase of these products to Figure 6, we observe that since both
$\theta_{2}$ and $\theta_{4}$ are bought 1 unit, we have that this corresponds
to the point on the lower frontier of the convex hull corresponding to good 4
and so $x_{4}^{*}=1$. Furthermore, since $0.5$ units of $\theta_{5}$ are
purchased, this maps to a point on the line segment corresponding to good 3
and good 5. Thus, we have that $x_{3}^{*}=0.5$ and $x_{5}^{*}=0.5$. Thus, the
final allocations for the agent are:
$x_{1}^{*}=0,x_{2}^{*}=0,x_{3}^{*}=0.5,x_{4}^{*}=1,x_{5}^{*}=0.5,x_{6}^{*}=0$.

We also note that these allocations confirm the claim of Corollary 1.

Example 2 (Good 5 has no Physical constraints): We endow agent $i$ with a
budget of $w_{i}=4.5$, and consider the following physical constraint for type
1 goods: $x_{i1}+x_{i3}\leq 1$, and for type 2 goods:
$x_{i2}+x_{i4}+x_{i6}\leq 1$. Good $5$ does not have any physical constraints.

The calculations of the $\theta$ values of all products other than
$\theta_{5}$ remain the same. We calculate $\theta_{5}$ as mentioned in the
remark in Appendix section 7.6, and so $\theta_{5}=\frac{1.7}{5}=0.34$.

Now, as the agent will buy products in the ascending order of the $\theta$
values until the agent’s budget is exhausted by Theorem 2.2, we will have that
the buyer purchases the following virtual products:

  * •

1 unit of $\theta_{1}$, with a total cost of $0.1$

  * •

1 unit of $\theta_{2}$, with a total cost of $0.4$

  * •

1 unit of $\theta_{3}$, with a total cost of $0.6$

  * •

2 units of $\theta_{5}$, with a total cost of $3.4$

The buyer purchases $\theta_{5}$ before $\theta_{4}$, as
$\theta_{5}=0.34<0.4=\theta_{4}$. Further, since good 5 does not have any
physical constraint, as mentioned in Appendix section 7.6, the buyer can
purchase an arbitrary amount of the good 5 until their budget is exhausted.

We observe that since both $\theta_{1}$ and $\theta_{3}$ are bought 1 unit, we
have that this corresponds to the point on the lower frontier of the convex
hull (for type 1 goods) corresponding to good 3 and so $x_{3}^{*}=1$. Next,
since one unit of $\theta_{2}$ is bought and no units of $\theta_{4}$ are
bought, we have that $x_{2}^{*}=1$. Finally, since $2$ units of $\theta_{5}$
are purchased, as this good does not correspond to any physical constraints,
we have $x_{5}^{*}=2$.

Thus, the final allocations for the agent are:
$x_{1}^{*}=0,x_{2}^{*}=1,x_{3}^{*}=1,x_{4}^{*}=0,x_{5}^{*}=2,x_{6}^{*}=0$. We
note that this allocation is in line with the remark in Appendix section 7.6.

###  7.8 Proof of Theorem 3.1

We now restate and proceed to prove Theorem 3.1.

See 3.1

To prove Theorem 3.1 we need to compare the KKT conditions of the individual
and social optimization problems. As in the proof sketch, we only derive the
KKT conditions of the social optimization problem SOP1 and show that the
budgets of agents will in general not be completely used up and thus a market
clearing equilibrium cannot hold.

####  7.8.1 KKT conditions of Social Optimization Problem SOP1

We now derive the first order necessary and sufficient KKT conditions for
SOP1. To do so, we introduce the dual variables $\mathbf{p}\in\mathbb{R}_{\geq
0}^{m}$ for constraint (4b), $\mathbf{r}_{i}\in\mathbb{R}_{\geq
0}^{l_{i}},\forall i$ for each of the constraints in (4c) and $s_{ij}\leq
0,\forall i,j$ for each of the non-negativity constraints (4d). Next, we
derive the Lagrangian of this problem as:

$\displaystyle\mathcal{L}=\sum_{i=1}^{n}w_{i}\log\left(\sum_{j=1}^{m}u_{ij}x_{ij}\right)-\sum_{j=1}^{m}p_{j}\left(\sum_{i}x_{ij}-\bar{s}_{j}\right)-\sum_{i=1}^{n}\sum_{t=1}^{l_{i}}r_{it}\left(\sum_{j=1}^{m}A_{tj}^{(i)}x_{ij}-1\right)-\sum_{i=1}^{n}\sum_{j=1}^{m}s_{ij}x_{ij}$
(7)

The first order derivative condition is found by taking the derivative of the
Lagrangian with respect to $x_{ij}$:

$\displaystyle\frac{w_{i}}{\sum_{j=1}^{m}u_{ij}x_{ij}}u_{ij}-p_{j}-\sum_{t=1}^{l_{i}}r_{it}A_{tj}^{(i)}\leq
0$ (8)

Next, the complimentary slackness condition for this problem can be derived by
multiplying (8) by $x_{ij}$:

$\displaystyle\frac{w_{i}}{\sum_{j=1}^{m}u_{ij}x_{ij}}u_{ij}x_{ij}-p_{j}x_{ij}-\sum_{t=1}^{l_{i}}r_{it}A_{tj}^{(i)}x_{ij}=0$
(9)

Thus, the KKT conditions of the social optimization problem are given by
equations (4b)-(4d), (8), (9) and the sign constraints of the dual variables.

####  7.8.2 Establishing Theorem 3.1

We now use the above derivations of the first order necessary and sufficient
KKT conditions to complete the proof of Theorem 3.1.

###### Proof

We observe that at the market clearing outcome, it must be that the budgets of
all agents must be entirely used up. We now show that this will in general not
be true. To see this, consider the KKT condition in equation (9) of the social
optimization problem. If we sum over $j$, we observe that this equation can be
expressed as:

$\displaystyle w_{i}-\sum_{j=1}^{m}p_{j}x_{ij}-\sum_{t=1}^{l_{i}}r_{it}=0$
(10)

However, the above constraint implies that the only way
$w_{i}=\sum_{j=1}^{m}p_{j}x_{ij}$ is if $\sum_{t=1}^{l_{i}}r_{it}=0$, which
implies that $r_{it}=0$ $\forall i,t$, as each $r_{it}\geq 0$. However, this
in general cannot be expected, as at the market clearing outcome the physical
constraint (4c) may be met with equality for some or all agents (as was
observed in the examples in Appendix sections 7.1, 7.3 and 7.7). In
particular, $r_{it}=0$ $\forall i,t$ implies that if we loosen any of the
physical constraints then the objective function value will remain unchanged.
However, if there is a difference between agent’s utilities between goods then
for the type of goods for which the physical constraint is loosened at least
one person will be better off as they have higher utilities and so the
objective function must increase. As a result, in general the scenario
$r_{it}=0$ $\forall i,t$ is not possible, particularly in cases when physical
constraints are met with equality, which may be the case for many markets.
Thus, we have that the market clearing KKT conditions of the social and
individual optimization problems are not necessarily the same, establishing
our claim.

###  7.9 Proof of Theorem 3.2

We now restate and proceed to prove Theorem 3.2.

See 3.2

We now derive the KKT conditions for the budget perturbed social optimization
problem BP-SOP and individual optimization problem IOP that are used in the
derivation of Theorem 3.2.

####  7.9.1 Derivation of KKT Conditions for Social Optimization Problem BP-
SOP

To establish the equivalence between individual optimization problem (3a)-(3d)
and the perturbed social optimization problem BP-SOP, we start by deriving the
first order necessary and sufficient KKT conditions for the problem (5a)-(5d).
To do so, we introduce the dual variables $\mathbf{p}\in\mathbb{R}_{\geq
0}^{m}$ for constraint (5b), $\mathbf{r}_{i}\in\mathbb{R}_{\geq
0}^{l_{i}},\forall i$ for each of the constraints in (5c) and $s_{ij}\leq
0,\forall i,j$ for each of the non-negativity constraints (5d). Next, we
derive the Lagrangian of this problem as:

$\displaystyle\mathcal{L}=\sum_{i=1}^{n}(w_{i}+\lambda_{i})\log\left(\sum_{j=1}^{m}u_{ij}x_{ij}\right)-\sum_{j=1}^{m}p_{j}\left(\sum_{i}x_{ij}-\bar{s}_{j}\right)-\sum_{i=1}^{n}\sum_{t=1}^{l_{i}}r_{it}\left(\sum_{j=1}^{m}A_{tj}^{(i)}x_{ij}-1\right)-\sum_{i=1}^{n}\sum_{j=1}^{m}s_{ij}x_{ij}$
(11)

The first order derivative condition is found by taking the derivative of the
Lagrangian with respect to $x_{ij}$:

$\displaystyle\frac{w_{i}+\lambda_{i}}{\sum_{j=1}^{m}u_{ij}x_{ij}}u_{ij}-p_{j}-\sum_{t=1}^{l_{i}}r_{it}A_{tj}^{(i)}\leq
0$ (12)

Next, the complimentary slackness condition for this problem can be derived by
multiplying (12) by $x_{ij}$:

$\displaystyle\frac{w_{i}+\lambda_{i}}{\sum_{j=1}^{m}u_{ij}x_{ij}}u_{ij}x_{ij}-p_{j}x_{ij}-\sum_{t=1}^{l_{i}}r_{it}A_{tj}^{(i)}x_{ij}=0$
(13)

Thus, the KKT conditions of the social optimization problem BP-SOP are given
by equations (5b)-(5d), (12), (13) and the sign constraints of the dual
variables.

####  7.9.2 KKT conditions of Individual Optimization Problem IOP

We now derive the KKT conditions of IOP by formulating a Lagrangian and
introducing the dual variable $y_{i}\geq 0$ for (3b),
$\mathbf{\tilde{r}}_{i}\in\mathbb{R}_{\geq 0}^{l_{i}}$ for each of the
constraints in (3c) and $\tilde{s}_{ij}\leq 0,\forall j$ for each of the non-
negativity constraints (3d). Thus, our Lagrangian is:

$\displaystyle\mathcal{L}(\mathbf{x}_{i},y_{i},\mathbf{r}_{i},\mathbf{s})=\sum_{j=1}^{m}u_{ij}x_{ij}-y_{i}\left(\sum_{j=1}^{m}p_{j}x_{ij}-w_{i}\right)-\sum_{t=1}^{l_{i}}\tilde{r}_{it}\left(\sum_{j=1}^{m}A_{tj}^{(i)}x_{ij}-1\right)-\sum_{j=1}^{m}\tilde{s}_{ij}x_{ij}$
(14)

The first order constraint for this problem is found by taking the derivative
of our Lagrangian with respect to $x_{ij}$ and noting that $\tilde{s}_{ij}\leq
0$:

$\displaystyle
u_{ij}-y_{i}p_{j}-\sum_{t=1}^{l_{i}}\tilde{r}_{it}A_{tj}^{(i)}\leq 0$ (15)

Next, we derive the complimentary slackness condition for this problem by
multiplying (15) by $x_{ij}$:

$\displaystyle
u_{ij}x_{ij}-y_{i}p_{j}x_{ij}-\sum_{t=1}^{l_{i}}\tilde{r}_{it}A_{tj}^{(i)}x_{ij}=0$
(16)

Thus, the final KKT conditions for our problem are given by equations (3b),
(3c), (3d), (15) and (16), and the sign constraints on the dual variables.
Furthermore, at equilibrium conditions, it must hold that the goods must be
sold to capacity, which is given by: $\sum_{i=1}^{n}x_{ij}=\bar{s}_{j},\forall
j$.

We use the derived KKT conditions of the individual and social optimization
problems to prove our theorem in the analysis that follows.

###### Proof

($\Rightarrow$) To prove the forward direction of our claim, we need to show
that given a market equilibrium $(\mathbf{x}_{i},\mathbf{p})$, $\forall i$ of
the IOP, we can construct $\lambda_{i}$, such that
$\lambda_{i}=\sum_{t=1}^{l_{i}}r_{it}$, $\forall i$.

We proceed by considering two cases, (i) when $y_{i}>0$ and (ii) when
$y_{i}=0$, where $y_{i}$ is the dual variable of the budget constraint in the
IOP. We first note at equilibrium conditions
$\sum_{i=1}^{n}x_{ij}=\bar{s}_{j},\forall j\in[m]$ and that the constraints of
the individual optimization problem IOP already implies the other constraints
of BP-SOP, i.e., the constraints (5c) and (5d). Thus, all we need to do is
check the lagrangian derivative condition (12), complementary slackness
condition (13) and dual multiplier sign constraints.

Case 1 ($y_{i}>0$): When we sum over all goods $j$, we have from the
complimentary slackness condition (16) that:

$\displaystyle\sum_{j=1}^{m}u_{ij}x_{ij}=y_{i}\sum_{j=1}^{m}p_{j}x_{ij}+\sum_{j=1}^{m}\sum_{t=1}^{l_{i}}\tilde{r}_{it}A_{tj}^{(i)}x_{ij}=y_{i}w_{i}+\sum_{t=1}^{l_{i}}\tilde{r}_{it}$
(17)

The second equality follows from the complimentary slackness condition for the
budget and physical constraints.

Next, using the Lagrangian derivative condition (15), and taking
$r_{it}=\frac{\tilde{r}_{it}}{y_{i}}$ we have that:

$\displaystyle\frac{1}{y_{i}}\leq\frac{p_{j}+\sum_{t=1}^{l_{i}}r_{it}A_{tj}^{(i)}}{u_{ij}},\forall
j$ (18)

Now setting
$\lambda_{i}=\sum_{t=1}^{l_{i}}r_{it}=\frac{\sum_{t=1}^{l_{i}}\tilde{r}_{it}}{y_{i}}$,
we obtain that:

$\displaystyle\frac{w_{i}+\lambda_{i}}{\sum_{j=1}^{m}u_{ij}x_{ij}}=\frac{1}{y_{i}}\cdot\frac{\left(y_{i}w_{i}+\sum_{t=1}^{l_{i}}\tilde{r}_{it}\right)}{\sum_{j=1}^{m}u_{ij}x_{ij}}$
(19)

Now observing Equation (17) and using the inequality (18), we can rewrite the
above expression as:

$\displaystyle\frac{w_{i}+\lambda_{i}}{\sum_{j=1}^{m}u_{ij}x_{ij}}=\frac{1}{y_{i}}\leq\frac{p_{j}+\sum_{t=1}^{l_{i}}r_{it}A_{tj}^{(i)}}{u_{ij}},\forall
j$ (20)

This is exactly the first order derivative condition of the BP-SOP as in
Equation (12). Multiplying Equation (20) by $x_{ij}$, we obtain by
complimentary slackness the condition in equation (13).

Finally, since we have that all the dual variables in IOP are scaled by a
positive constant, as $y_{i}>0$ the corresponding signs of the dual variables
in BP-SOP remain intact. Thus, we have shown that when $y_{i}>0$ and when we
set $\lambda_{i}=\sum_{t=1}^{l_{i}}r_{it}$, $\forall i$ then the market
equilibrium KKT conditions of the IOP are the same as that of BP-SOP.

Case 2 ($y_{i}=0$): We start by introducing some necessary notation. From
Theorem 2.2, we define $\alpha_{i}^{*}$ to be the slope of buyer $i$’s last
bought virtual product, i.e., with the maximal slope, and let
$\lambda_{i}=\alpha_{i}^{*}(\sum_{j=1}^{m}u_{ij}x_{ij})-w_{i}$.

Finally, for good $j$ belonging to type $t$, we define
$\sum_{t^{\prime}=1}^{l_{i}}r_{it^{\prime}}A_{t^{\prime}j}^{(i)}=r_{it}=\alpha_{i}^{*}u_{ij}-p_{j}$
for $x_{ij}>0$, which follows as $A_{tj}^{(i)}=1$ for a unique type $t$ for
each good $j$. Then, we obtain that:

$\displaystyle\frac{w_{i}+\lambda_{i}}{\sum_{j=1}^{m}u_{ij}x_{ij}}=\alpha_{i}^{*}=\frac{p_{j}+\sum_{t^{\prime}=1}^{l_{i}}r_{it^{\prime}}A_{t^{\prime}j}^{(i)}}{u_{ij}},\forall
j\text{ s.t. }x_{ij}>0$ (21)

On the other hand if $x_{ij}=0$, we have that
$\frac{p_{j_{1}}-p_{j}}{u_{ij_{1}}-u_{ij}}=\theta_{t}\leq\alpha_{i}^{*}$,
which implies that:
$\alpha_{i}^{*}u_{ij}-p_{j}\leq\alpha_{i}^{*}u_{ij_{1}}-p_{j_{1}}=r_{it}=\sum_{t^{\prime}=1}^{l_{i}}r_{it^{\prime}}A_{t^{\prime}j}^{(i)}$,
where $j,j_{1}\in t$.

Using this relationship, we observe that:

$\displaystyle\frac{w_{i}+\lambda_{i}}{\sum_{j=1}^{m}u_{ij}x_{ij}}=\alpha_{i}^{*}\leq\frac{p_{j}+\sum_{t^{\prime}=1}^{l_{i}}r_{it^{\prime}}A_{t^{\prime}j}^{(i)}}{u_{ij}},\forall
j\text{ s.t. }x_{ij}=0$ (22)

This is exactly the first order derivative condition of the BP-SOP as in
Equation (12). Multiplying Equation (20) by $x_{ij}$, we obtain by
complimentary slackness the condition in equation (13).

We now note that to show $\lambda_{i}=\sum_{t=1}^{l_{i}}r_{it}$, we multiply
the equation
$\sum_{t^{\prime}=1}^{l_{i}}r_{it^{\prime}}A_{t^{\prime}j}^{(i)}=r_{it}=\alpha_{i}^{*}u_{ij}-p_{j}$
with $x_{ij}$ and sum over all goods $j$ to get:

$\displaystyle\sum_{j=1}^{m}\sum_{t^{\prime}=1}^{l_{i}}r_{it^{\prime}}A_{t^{\prime}j}^{(i)}x_{ij}=\sum_{j=1}^{m}\alpha_{i}^{*}u_{ij}x_{ij}-\sum_{j=1}^{m}p_{j}x_{ij}$
(23)

Then by complimentary slackness we get that:

$\displaystyle\sum_{t^{\prime}=1}^{l_{i}}r_{it^{\prime}}=\sum_{j=1}^{m}\alpha_{i}^{*}u_{ij}x_{ij}-\sum_{j=1}^{m}p_{j}x_{ij}=\alpha_{i}^{*}\sum_{j=1}^{m}u_{ij}x_{ij}-w_{i}=\lambda_{i}$
(24)

Next, we observe that since $\alpha_{i}^{*}$ is the maximal $\theta$, we must
have that $\alpha_{i}^{*}\geq\frac{p_{j}}{u_{ij}}$ which implies that
$\alpha_{i}^{*}u_{ij}-p_{j}\geq 0$ giving us that $r_{it}\geq 0$.

Finally, both $r_{it}\geq 0$, $\forall i,t$ and $p_{j}\geq 0$, $\forall j$ and
so the signs of the dual variables in BP-SOP remain intact. Thus, we have
shown that when $y_{i}=0$ and when we set
$\lambda_{i}=\sum_{t=1}^{l_{i}}r_{it}$, $\forall i$ then the market
equilibrium KKT conditions of the IOP are the same as that of BP-SOP.

($\Leftarrow$) To establish the converse of the theorem, we first note that
the constraints of the social optimization problem already implies that
$\forall j$, good $j$ is sold to capacity if $p_{j}>0$. If on the other hand
$p_{j_{1}}=0$ for some good $j_{1}\in t$, i.e., good $j_{1}$ belongs to good
type $t$ and $\sum_{i}x_{ij_{1}}<\bar{s}_{j_{1}}$ then it must follow that
$\forall i$, $\sum_{j\in t}x_{ij}=1$, as agents can always buy more units of
good type $j_{1}$ to increase their utility. Without loss of generality,
suppose that all agents are interested in consuming goods from resource type
$t$, so that $t\in T_{i}$, $\forall i$. Thus, we have that:
$n=\sum_{i=1}^{n}\sum_{j\in t}x_{ij}=\sum_{j\in
t}\sum_{i=1}^{n}x_{ij}<\sum_{j\in t}\bar{s}_{j}$, as
$\sum_{i}x_{ij_{1}}<\bar{s}_{j_{1}}$ by assumption. However, for BP-SOP to
have a feasible solution it must be that $\sum_{j\in t}\bar{s}_{j}\leq n$.
Combining this with the above inequality we get that $n<n$, a contradiction.
Thus, we must have that $\sum_{i}x_{ij_{1}}=\bar{s}_{j_{1}}$. As a result, we
have established that $\forall j$, good $j$ is sold to capacity.

The constraints of the social optimization problem also imply the IOP
constraints (3c) and (3d). Next, we use the notation and equations in appendix
section 7.9.1 and the corresponding KKT conditions of BP-SOP and IOP.
If we divide (12) and (13) by
$\frac{w_{i}+\lambda_{i}}{\sum_{j=1}^{m}u_{ij}x_{ij}}$, then these equations
map respectively to the Lagrangian derivative equation (15) and complimentary
slackness equation (16) of the individual optimization problem. We show this
by denoting $\mathbf{p}\in\mathbb{R}_{\geq 0}^{m}$ as the dual variable for
the capacity constraint, i.e., $p_{j}$ is the dual variable corresponding to
the capacity constraint for good $j$, and then we have that (12) becomes:

$\displaystyle
u_{ij}-\frac{\sum_{j=1}^{m}u_{ij}x_{ij}}{w_{i}+\lambda_{i}}p_{j}-\sum_{t=1}^{l_{1}}\frac{\sum_{j=1}^{m}u_{ij}x_{ij}}{w_{i}+\lambda_{i}}r_{it}A_{tj}^{(i)}\leq
0$ (25)

The above equation is equivalent to (15), where
$y_{i}=\frac{\sum_{j=1}^{m}u_{ij}x_{ij}}{w_{i}+\lambda_{i}}\geq 0$,
$\tilde{r}_{it}=\frac{\sum_{j=1}^{m}u_{ij}x_{ij}}{w_{i}+\lambda_{i}}r_{it}\geq
0$. The same analysis holds for the complementary slackness condition
equivalence in the two problems.

Now, all it remains for us to satisfy is the IOP constraint (3b). To do this,
we use the complementary slackness condition in equation (13) and sum over
$j$. Then realizing that $r_{it}\sum_{j=1}^{m}A_{tj}^{(i)}x_{ij}=r_{it}$ by
complimentary slackness we get:

$\displaystyle
w_{i}+\lambda_{i}-\sum_{j=1}^{m}p_{j}x_{ij}-\sum_{t=1}^{l_{i}}r_{it}=0$ (26)

Thus, if we set $\lambda_{i}=\sum_{t=1}^{l_{i}}r_{it}$ as in the statement of
the theorem, we obtain that the budget constraint condition (3b) is satisfied
with equality. This implies that we have a market clearing outcome, as the
budgets are completely used and the goods are sold to capacity, while the KKT
conditions of the two problems are equivalent at market clearing conditions.
This establishes our claim.