Graphical Economies with Resale

Understanding the behaviour of markets (economies) is at the heart of many research streams in theoretical economics. Work pioneered by the $19^{\text{th}}$ century economist Léon Walras Walras (1874) has been at the epicenter since pioneering work by Arrow and Debreu (1954), which establishes the existence of equilibria in a very general model of the economy that is now known as the Arrow–Debreu (AD) market model. In the theoretical computer science community, computing equilibria in the AD model has garnered much attention. In the purely exchange setting of the AD model multiple algorithmic innovations have been made to compute equilibria, e.g. Devanur (2004); Vazirani (2010); Devanur et al. (2008); Garg and Kapoor (2006); Codenotti et al. (2005); Kakade et al. (2004a); Garg et al. (2019). The work introduced in this paper falls outside the scope of these algorithms since resale in graphical economies behaves like a special version of production in the AD model. For AD markets with production, Jain and Varadarajan (2006) and Kapoor et al. (2005) give polynomial-time algorithms for finding competitive equilibria for certain types of production and utility functions. However, resale in graphical economies falls outside the scope of production applicable to the convex program in Jain and Varadarajan (2006), and is more complicated than the production in Kapoor et al. (2005). In fact, certain forms of resale reduce to a special case of production where even approximating competitive equilibria is known to be FIXP-hard in general Garg et al. (2017, 2014).

We introduce a variant of the auction based algorithms by Garg and Kapoor (2006) and Kapoor et al. (2005) that is able to approximate competitive equilibria in graphical economies with resale, though our proofs differ substantially. By considering specific graph structures, the algorithm being introduced extends both Garg and Kapoor (2006) and Kapoor et al. (2005) to a more general class of utility functions and, in the case of Garg and Kapoor (2006), to a more general class of production functions. These auction-based algorithms have a storied history in general resource allocation and network optimization Bertsekas (1992); Lin et al. (2013); Zavlanos et al. (2008); Avasarala et al. (2006); Curescu and Nadjm-Tehrani (2008), thus generalizing these algorithms to a network market model with long range trade provides insights reaching farther than classic economics. Finally, a form of resale discussed in this paper, called credit bound resale, can be thought of as a natural extension of the spending constraint utilities introduced in Devanur (2004); Vazirani (2010) to a production-like setting.

Along with the aforementioned connections to traditional economic theory and algorithmic economics, the work presented here has deep ties to the study of economic networks more broadly. In §6.5 we discuss these connections in detail.

The Arrow–Debreu (AD) exchange economy Arrow and Debreu (1954), also known as the Walrasian model, is extremely well studied due to its central role in general equilibrium theory. The graphical economies studied here are generalizations of AD which retain AD as a special case Kakade et al. (2004a). In the language introduced above, consider a graphical economy with $m$ agents and $\ell$ goods that is embedded in a complete graph, i.e. a graphical economy where every pair of agents is able to trade with one another.

Notice that since the underlying trade graph is complete, the condition that $\boldsymbol{p}^{i}=\boldsymbol{p}^{j}$ for all $i,j\in[m]$ is without loss of generality: by allowing trade between every pair of agents, at equilibrium the local aspects of a graphical economy essentially become obsolete. To see this, note that agents can consume goods from any other agent, and thus individual rationality dictates that agents should only consume utility maximizing goods at the cheapest price in the economy. To enforce market clearing the price on a good must therefore be identical throughout the economy, meaning that prices can simply be described by a single vector. Similarly, since local prices are all the same, all that matters about the consumption plan $\boldsymbol{x}$ are the sums $\boldsymbol{d}^{i}(\boldsymbol{x})=\sum_{j\simeq i}\boldsymbol{x}^{ji}$, often called the demand vectors, specifying what each agent consumes but not from whom. After these two simplifications, we arrive at the usual definition of an AD equilibrium.

By moving from the complete graph to general graphs, and imposing a local clearing condition instead of a global one, we arrive at the notion of equilibria for graphical economies introduced by Kakade, Kearns, and Ortiz (KKO) Kakade et al. (2004a). Unlike the AD equilibrium, the KKO model allows asymmetries in trade opportunities to arise from the underlying graph, yielding local price vectors that are generally distinct among agents.

As above, one can see eq. (3) as a clearing constraint by defining the demand vector from agent $i$ by $\boldsymbol{d}^{i}(\boldsymbol{x})=\sum_{j\simeq i}\boldsymbol{x}^{ji}$. When $G$ is the complete graph, we recover the AD equilibrium.

Graphical economies such as KKO are both technically and conceptually appealing. As is often the case in computer science, designing algorithms to exploit the underlying network topology can yield more efficient algorithms; see Kakade et al. (2004a); Kakade et al. (2004b); Nisan et al. (2007), as well as §5. Conceptually, as one of the most well-studied and general mathematical models of trade, placing AD on a network provides a natural way of understanding the effects of network topology in actual economies and, more generally, resource routing problems. Studying the relationship between network structure and local equilibrium outcomes yields better understanding of the phenomena observed in data Kakade et al. (2004b).

Kakade et al. (2004a) show the existence of graphical equilibria under very general conditions, and give an algorithm to compute equilibria in polynomial time. Their algorithm follows from a novel algorithm to compute AD equilibria, together with a reduction to AD from the graphical setting by using $m\ell$ “tagged” goods which are marked according to who sold them. The model we present below will not allow such a reduction.

Motivated by the above examples, we introduce a new equilibrium concept for graphical economies which allows agents to facilitate trade between other parties without consuming any of the goods so traded; in other words, agents are allowed to resell goods. By introducing resale we are able to extend KKO equilibria to better capture the behaviour one expects in graphical economies at equilibrium. Though resale equilibria are defined as a one-shot process like the AD and KKO settings, it is intuitive to think of a resale equilibrium as proceeding in two phases: a resale phase and a purchase phase. In the resale phase, agents purchase goods from each other but immediately sell them, intuitively to arbitrage prices which differ within their neighborhood. At the end of the resale phase, the market need not clear. Next, in the purchase phase, agents sell their endowments, and then use this money, together with the profits from the first phase, to purchase goods to optimize their utility. Only after both phases do we require the market to clear at each node, in the sense that every agent holds onto a nonnegative amount of each good, and no goods are created or destroyed in the economy.

To capture resale, we track purchases for resale separately from purchases for consumption. The vector $\boldsymbol{y}^{ij}\in\mathbb{R}^{\ell}_{+}$ denotes the bundle of goods agent $i\in[m]$ purchased from agent $j\in[m]$ for resale, and as before we define $\boldsymbol{y}^{ij}=\boldsymbol{0}$ for $j\not\simeq i$. As with $\boldsymbol{x}^{i},\boldsymbol{x}$, we define $\boldsymbol{y}^{i}=\{\boldsymbol{y}^{ij}:j\in[m]\}$ and $\boldsymbol{y}=\{\boldsymbol{y}^{i}:i\in[m]\}$ to be the resale plans for an agent and for the whole economy respectively. Finally, associated with each agent $i\in[m]$ is a resale bound $b_{i}\in\mathbb{R}_{+}$ representing an exogenous limit on resale for agent $i$. The vector $\boldsymbol{b}\in\mathbb{R}^{m}_{+}$ represents the set of every agent’s resale bound. The resale limits in $\boldsymbol{b}$ have a natural interpretation as credit or capacity constraints, as we describe below.

We define equilibria in graphical economies with resale in terms of demand systems. This formalism provides an intuitive means of reasoning about graphical economies with resale in their full generality and will be particularly important for the algorithm we introduce in §5. Our use of demand systems is inspired by the recent work of Garg et al. (2019), though our algorithm differs from theirs in significant ways beyond just applying to a graphical setting with resale. Informally, demand systems encode optimal actions for agents in the economy at a given set of prices and budget. For example, in both AD and KKO equilibria, a demand system will return the set of consumption plans maximizing an agent’s utility while satisfying eqs. 2 and 4 above.

In our model each agent $i$ has two demand systems: a consumption demand system $C_{i}$ and a resale demand system $R_{i}$. For consumption, $C_{i}(\boldsymbol{p},\beta_{i})$ denotes the set of plans $\boldsymbol{x}^{i}$ that maximize agent $i$’s utility $u_{i}(\sum_{j\simeq i}\boldsymbol{x}^{ij})$ at prices $\boldsymbol{p}$ within the budget $\beta_{i}=\boldsymbol{p}^{i}\cdot\boldsymbol{e}^{i}+\sum_{j\simeq i}(\boldsymbol{p}^{i}-\boldsymbol{p}^{j})\cdot\boldsymbol{y}^{ij}$. As defined above, we have $\boldsymbol{x}^{ij}=\boldsymbol{0}$ for $j\not\simeq i$ in every consumption plan $\boldsymbol{x}^{i}\in C_{i}(\boldsymbol{p},\beta_{i})$. When an agent has linear utilities $\boldsymbol{u}^{i}$, $C_{i}(\boldsymbol{p},\beta_{i})$ will include all consumption plans $\boldsymbol{x}^{i}$ with fractional assignments of goods maximizing bang-per-buck $u^{i}_{k}/p^{j}_{k}$ with total price $\beta_{i}$. ²²2When the optimal consumption plans are unique for each set of prices and budget, these systems coincide with demand functions, which are well studied in exchange economies for certain classes of utility functions. To see the importance of considering demand systems rather than demand functions, simply note that linear utility functions often have non-unique demand sets for a given set of prices and budgets.

For resale, $R_{i}(\boldsymbol{p},b_{i})$ denotes the set of resale plans $\boldsymbol{y}^{i}$ that maximize resale profits $\sum_{j\simeq i}(\boldsymbol{p}^{i}-\boldsymbol{p}^{j})\cdot\boldsymbol{y}^{ij}$ over a set of feasible resale plans $\mathcal{Y}_{i}(\boldsymbol{p},b_{i})$. We enforce $\boldsymbol{y}^{ij}=\boldsymbol{0}$ for $j\not\simeq i$ in every $\boldsymbol{y}^{i}\in\mathcal{Y}_{i}(\boldsymbol{p},b_{i})$. While our results apply to quite general resale demand systems,³³3In fact, for the analysis in § 5, we do not even need resale demand systems to maximize resale profits. a natural and motivating example is credit bound resale, where $b_{i}$ represents the total budget or “line of credit” with which agent $i$ can purchase goods in order to resell. Formally, the credit bound resale demand system sets $\mathcal{Y}_{i}(\boldsymbol{p},b_{i})=\{\boldsymbol{y}^{i}:\sum_{j\simeq i}\boldsymbol{p}^{j}\cdot\boldsymbol{y}^{ij}\leq b_{i}\}$, so that $R_{i}(\boldsymbol{p},b_{i})$ is the set of fractional assignments of goods of total cost $b_{i}$ maximizing profit-per-credit $p^{i}_{k}/p^{j}_{k}-1$. Another natural form of resale is commodity bound resale, which maximizes resale profits subject to $\sum_{j\simeq i}\|\boldsymbol{y}^{ij}\|_{1}\leq b_{i}$. Despite its intuitive appeal, proving existence for commodity bound resale requires strengthening our assumptions, as we discuss in §6.4. Our examples throughout the paper use credit bound resale where every agent has linear utilities.

When using resale demand systems having constraints such as credit bounds, the prices can determine the feasible set of resale plans. Due to this dependence, equilibrium prices do not necessarily scale in the sense traditionally seen in AD economies. For example, in credit bound resale, equilibrium plans are preserved when scaling both equilibrium prices and credit bounds $b_{i}$. The equilibrium prices still scale in the traditional sense for commodity bound resale, as there the feasible resale plans do not depend on prices.

For credit bound resale and similar resale demand systems, we recover the KKO equilibrium concept for $\boldsymbol{b}=\boldsymbol{0}$ and the AD equilibrium for sufficiently large $\boldsymbol{b}$. To see this, for every $i\in[m]$, consider a normalized resale system $R_{i}$ that returns sets $\boldsymbol{y}^{i}$ that are increasing in $b_{i}$ when $i$ can profit. To recover KKO, we simply set $\boldsymbol{b}=\boldsymbol{0}$ to remove resale: $\boldsymbol{b}=\boldsymbol{0}$ implies $\boldsymbol{y}^{i}=\boldsymbol{0}$ for all $i$ as $R_{i}$ is normalized, and thus consumption budgets are $\boldsymbol{p}^{i}\cdot\boldsymbol{e}^{i}$ which is equivalent to eq. (4) and market clearing simply reduces to eq. (3). Conversely, let $b_{i}$ be sufficiently large for each agent. As resale is essentially unrestricted, then any difference in prices will result in large reselling. In particular, for all $i$, if $b_{i}$ is large enough⁴⁴4For credit bound resale, it suffices to set $b_{i}\geq\sum_{j\in[m],k\in[\ell]}p^{j}_{k}e^{j}_{k}~{},$ the total cost of buying all goods in the economy. for there to exist $\boldsymbol{y}^{i}\in R_{i}(\boldsymbol{p},b_{i})$ at equilibrium prices $\boldsymbol{p}$ such that $\boldsymbol{y}^{i}$ includes every good in the economy, then the market will not clear if any prices differ. Thus, for sufficiently large $\boldsymbol{b}$, we will have $\boldsymbol{p}^{i}=\boldsymbol{p}^{j}$ for all $i,j$, forcing zero profits from resale. As agents are therefore indifferent among all valid resale plans, goods can move freely throughout the graph, and we can set $\boldsymbol{y}$ to achieve any consumption plan $\boldsymbol{x}$ satisfying global market clearing, eq. (1).

We can now see how the addition of resale changes the outcome of the broker example from above. For simplicity let $R_{i}$ be a credit bound resale demand system for every agent $i\in[3]$. We will argue that, for any $0<b\leq 2$, the following prices at $\alpha=\sqrt{b/2}$ lead to a $\boldsymbol{b}$-resale equilibrium where $\boldsymbol{b}=(b,b,b)$. Dotted lines depict movement of the goods.

Let us verify the equilibrium. Agents 1 and 3 have nothing to gain from resale, so abstain from the first phase, whereas agent 2 can resell a total of $b/\alpha$ units. Agent 2 thus purchases $(b/2\alpha,0)$ and $(0,b/2\alpha)$ from agents 1 and 3, respectively, to then resell for an optimal profit of $(1-\alpha)b/\alpha$. In the second phase, agents 1 and 3 sell their endowments for a revenue of $\alpha$ and purchase $(0,\alpha)$ and $(\alpha,0)$ from agent 2, respectively, thus optimizing their utility. Agent 2 uses the profit from the first phase to purchase $(b(1-\alpha)/2\alpha^{2},0)$ and $(0,b(1-\alpha)/2\alpha^{2})$ from agents 1 and 3, respectively, at a price $\alpha$. Optimal arbitrage and individual rationality are clear; it remains to check the clearing constraint. Setting $\alpha=\sqrt{b/2}$, we now have that the goods consumed by agent 2 are $(1-\alpha,1-\alpha)$, and the goods resold are indeed consumed by agents 1 and 3.⁵⁵5Commodity bound resale offers a similar resolution to this broker example. The primary difference is that agent 2’s resale plans are not influenced by prices, and thus agent 2 will always resell $\alpha{=}b/2$ from each of the other agents.

The resolution of the broker example is intuitive: adding a small amount of resale capacity $b$ allows agent 2 to extract nearly all of the rent for the service of facilitating trade between agents 1 and 3. Specifically, the final utilities are $\sqrt{b/2}$, $2(1-\sqrt{b/2})$, and $\sqrt{b/2}$, respectively. The larger $b$ becomes, the less rent agent 2 can extract, for the simple reason that the prices for the other agents must increase for the market to clear. When $b\geq 2$, all prices become equal and the market is effectively a classic AD exchange economy as predicted in §3.1.

Finally, while this example is motivating as it yields no KKO equilibrium, and we must have $b>0$ for the same reason, we can easily take a limit as $b\to 0$ to obtain a limiting equilibrium where agent 2 extracts all the rents from its neighbors. This leads to an intuitive extension of the KKO equilibrium concept, which remains well-defined even for agents with zero endowments: a limiting equilibrium of a $\boldsymbol{b}$-resale economy as $\boldsymbol{b}\to\boldsymbol{0}$. This limiting resale equilibrium yields an efficient allocation in both this example and the modification above with $\boldsymbol{u}^{2}=(0,1)$. In contrast, the corresponding limiting $\epsilon$-KKO equilibrium as $\epsilon\to 0$ suffers from the same problem as the non-limit version: for the modified example with $\boldsymbol{u}^{2}=(0,1)$, the first good is “trapped” in a local economy regardless of $\epsilon$, and thus in the limit.

The concept of quasi-equilibria was first introduced by Debreu (1962) to do away with the assumption in Arrow and Debreu (1954) that every agent in the economy has non-zero endowments of every good. (In particular, as discussed in §3, these criticisms apply to $\epsilon$-KKO equilibria.) McKenzie (1981) gives a detailed discussion of quasi-equilibria and AD equilibria, while Maxfield (1997) shows that analogous quasi-equilibria exist in AD economies with production. Intuitively, quasi-equilibria are relaxations of equilibria: agents with wealth behave exactly as they would at equilibrium, while agents without wealth need not satisfy individual rationality. As rationality of agents with zero wealth applies only to goods with zero prices, quasi-equilibria are used as a stepping stone to ultimately rule out zero prices and/or zero wealth, in which case they coincide with the usual equilibria.

We say an agent $i$ is rational if optimal arbitrage and individual rationality (conditions 2 and 3 of Definition 3.2) are both satisfied. Our definition of $\boldsymbol{b}$-resale quasi-equilibria is equivalent to its counterpart in AD production economies.

As noted above, quasi-equilibria are a powerful tool for proving existence, for the following reasons. First, agents can only consume while being quasi-rational if some good in their neighborhood has price zero since they have no wealth. Second, if all agents are behaving rationally, then the $\boldsymbol{b}$-resale quasi-equilibrium is exactly a $\boldsymbol{b}$-resale equilibrium. These facts play a crucial role in our proof—as they did in e.g. Debreu (1962); McKenzie (1981); Maxfield (1997); Kakade et al. (2004a)—because once we know a quasi-equilibrium exists, it suffices to show that all endowed agents are rational and all non-endowed agents have strictly positive local price vectors. Given these statements, an agent either has positive wealth, and thus is rational, or is forced to consume nothing.

We now turn to the various assumptions needed to establish the general existence of $\boldsymbol{b}$-resale quasi-equilibria (Lemma 4.2). The first is a set of conditions on agents’ utility functions, which are typical in mathematical economics and match those needed in Arrow and Debreu (1954); Kakade et al. (2004a); Maxfield (1997).

The utility conditions of Assumption 1 in turn influence the agents’ consumption demand systems. As was true in Kakade et al. (2004a), Assumption 1 in the graphical setting, together with individual rationality, implies that in any $\boldsymbol{b}$-resale equilibrium agents only demand a good for consumption at the cheapest price available in their neighborhood. Stated formally, by Assumption 1 and individual rationality, for agents $i\in[m]$, $j\simeq i$, and good $k\in[\ell]$, if $x^{ij}_{k}>0$ then $p^{j}_{k}\leq p^{\hat{j}}_{k}$ for all $\hat{j}\simeq i$. In addition, non-satiability ensures every agent $i$ has at least one good $k$ that $i$ demands an infinite amount of if offered a zero price; in discussions to come, when we say $i$ is non-satiable in $k$ we are referring to this phenomenon.

Assumption 2 establishes weak conditions on resale demand systems so that satisfying optimal arbitrage behaves as we might typically expect in economic models. Firstly the assumption ensures that if an agent can resell profitably, then they do resell something without discriminating against specific goods or agents as long as it is profitable. Secondly the assumption ensures that if an agent $i$ can resell some good $k\in[\ell]$ profitably, and a neighbor is offering $k$ for free, then $R_{i}$ will be empty since no finite amount of good $k$ can saturate $i$’s credit (analogous to non-satiation in consumption). Finally, the assumption ensures that agents without the capacity to resell ($b_{i}=0$) do not resell.

Together, these assumptions imply the existence of quasi-equilibria in our setting. The proof boils down to observing that graphical economies with resale are a case of AD economies with production. From this relationship it is easy to check that the preconditions for quasi-equilibrium existence highlighted in Maxfield (1997) are satisfied.

With quasi-equilibria in hand, we turn to assumptions that ensure all agents are rational. First, every agent in the economy must be able to participate with every good in the economy.

When $\boldsymbol{b}=\boldsymbol{0}$, Assumption 3 is analogous to assumptions made in both Arrow and Debreu (1954) and Kakade et al. (2004a). When $\boldsymbol{b}>\boldsymbol{0}$, every agent has some capacity to resell, and for sufficiently small $\boldsymbol{b}$, Assumption 3 behaves like a weaker form of its counterpart in those works.⁶⁶6Both Arrow and Debreu (1954) and Kakade et al. (2004a) require that every agent is endowed with a non-zero amount of every good. When $\boldsymbol{b}>\boldsymbol{0}$, Assumption 3 allows agents to have sparse endowment vectors even when $\boldsymbol{b}$ is set to such small values that resale is virtually non-existent in the economy. This assumption can be thought of as a near-minimal requirement to participate in the economy. It may be possible to replace $\boldsymbol{e}^{i}>\boldsymbol{0}$ with $\boldsymbol{e}^{i}\neq\boldsymbol{0}$, but our current proof techniques would require strengthening Assumption 5 for technical reasons related to the propagation of non-zero prices.

Our next assumption simply guarantees that every good exists at least somewhere in the economy. Intuitively, this assumption asserts that in order for a good to influence a competitive economy it needs to exist. Together with Assumption 5 introduced below, this assumption ensures all goods in the economy play a role.

Lastly, in Assumption 5, we will enforce that the underlying economy graph is sufficiently connected in a supply-demand sense; this assumption ensures both that agents have access to goods they are non-satiable on, and that the economy can function properly if resale is not profitable. Ensuring access to desired goods is important on a technical level since otherwise clearing may be impossible, e.g., if agents spend money on goods that are unavailable to them. Similarly, absent any assumption, when agents with sparse endowment vectors are unable to profit from resale, it is possible to construct graphical economies where entire sectors of the economy behave nonsensically. An interesting corollary of Assumption 5 is that unendowed agents cannot be picky: there cannot exist goods in which only unendowed agents are non-satiable.

To formally state Assumption 5, call a path between agents $i,j\in[m]$ a trade path if every node $\hat{i}\notin\{i,j\}$ on the path has $b_{\hat{i}}>0$. We write $P(i,j)$ for the set of agents on some trade path between $i$ and $j$; by convention $i,j\in P(i,j)$, and by definition, $P(i,j)=P(j,i)$. Also, define the supply graph of $k$ as the directed graph $G^{S}_{k}=([m],E^{S}_{k})$ with $(i,j)\in E^{S}_{k}$ if $e^{i}_{k}>0$, $j$ is non-satiable in $k$, and there is a trade path between $i$ and $j$. Edges $(i,j)$ in $G^{S}_{k}$ are present whenever $i$ could directly or indirectly sell their endowment of $k$ to $j$, when price conditions allow for profitable resale in between, if applicable. Finally, let $G^{S}=([m],E^{S})$ be the (non-disjoint) union of supply graphs on all goods, with $E^{S}=\bigcup_{k\in[\ell]}E^{S}_{k}$. In graph theoretic terms, $G^{S}$ encodes all possible directed source-sink pairs in the economy, and each $G^{S}_{k}$ encodes source-sink pairs for the good $k$.

One technical interpretation of Assumption 5 is that we cannot partition any connected component of the underlying trade graph $G$ into two sets of endowed agents where one group cannot supply any good the other group wants. This assumption is very closely related to the irreducibility assumption used to prove existence of AD equilibria by McKenzie (1959, 1961). While McKenzie (1959) introduces irreducibility on the entire economy as a sufficient assumption for proving existence, our assumption need only hold on each connected component. The supply graph $G^{S}$ serves a similar purpose to the directed graphs constructed in Maxfield (1997) for proving existence, though we place weaker assumptions on consumers in exchange for slightly stronger assumptions on $G^{S}$.

Together Assumptions 1–5 provide powerful guarantees: certain non-zero prices must propagate in the presence of a rational agent (Lemma A.1), and any $\boldsymbol{b}$-resale quasi-equilibrium must have at least one endowed rational agent (Lemma A.3). We briefly sketch the argument here. Assumption 1 ensures an agent $i$ is non-satiable in some good $k$, therefore if $i$ is rational then $k$ must have a non-zero price in $i$’s neighborhood for the market to clear. If agent $i$ has $b_{i}>0$ and $p^{i}_{k}>0$ for some good $k$, then Assumption 2 implies that $k$ must have a non-zero price in $i$’s neighborhood for the same reason. Lastly, by definition quasi-equilibrium prices must have at least one non-zero price. Coupling these facts and recursively applying them ensures a non-zero price propagates along trade paths and hence throughout supply graphs—this insight plays a vital role throughout our proof of existence.

To conclude, we show that rationality propagates in connected components of graphical economies much like non-zero prices do, so long as these assumptions are satisfied.

The proof of this final lemma has a very similar intuition as the proof of Lemma A.3, but is on a grander scale. We know rationality implies non-zero prices by Assumption 1(ii), that non-zero prices propagate along trade paths by Lemma A.1, and that endowed agents are on trade paths with all other endowed agents by Assumption 5(iii). Therefore, since we know a rational agent exists by Lemma A.3, these facts combine to ensure non-zero prices propagate such that all endowed agents must be rational. In addition, Assumption 5(ii) ensures all non-endowed agents lie on a trade path with some endowed agent at the end of it for each of the goods in the economy, and from Lemma A.1 we know that non-zero prices propagate on trade paths connected to rational agents. With some bookkeeping, it follows that non-endowed agents must have strictly positive local price vectors. Thus, either the non-endowed agents are able to resell and have wealth, or they have no wealth and cannot consume anything as all prices in their neighborhood are non-zero.

Combining all five assumptions, and Lemma 4.3, we are now ready to show existence of equilibria (Theorem 4.4). It remains only to show is that Lemma 4.3 holds on each connected component of a graphical economy. By definition, if Assumptions 1, 2, 3, and 5 hold for a disconnected graphical economy with resale, then the assumptions also hold for each connected component of the graphical economy. In addition, if Assumption 4 does not hold for some connected component $C$ of the underlying trade graph $G$, then there is some $k\in[\ell]$ with $e^{i}_{k}=0$ for every $i\in C$. As Assumption 5 asserts that each $i$ has an incoming edge in $G^{S}_{k^{\prime}}$ for each $k^{\prime}\in[\ell]$ that $i$ is non-satiable in, and that $C$ is strongly connected among suppliers in $G^{S}$, it follows that there cannot exist an agent $j\in C$ that is non-satiable in $k$. Therefore, by appropriately scaling their prices, we know that goods contradicting Assumption 4 can be neglected at equilibrium in $C$, and Assumptions 1–5 hold in $C$ for the set of goods $[\ell]\setminus\{k\in[\ell]:e^{i}_{k}=0\text{ for every }i\in C\}$.

As was just discussed, each connected component $C$ of the graphical economy’s underlying trade graph $G$ satisfies Assumptions 1–5 (possibly by removing some “useless goods”). Thus, by Lemma 4.3, every agent in each connected component $C$ of the graphical economy is rational and, by definition, $C$ has its own $\boldsymbol{b}$-resale equilibrium. Finally, by definition, the union of equilibria in uncoupled graphical economies is an equilibrium of the entire economy and so we know that a $\boldsymbol{b}$-resale equilibrium exists in any graphical economy satisfying our five assumptions. Stated formally, we have the following theorem.

The conditions of Theorem 4.4 are straightforward to check. Given the utility functions, resale constraints, endowments, and underlying trade graph $G$ in standard forms (e.g. encoded in matrices), we can construct $G^{S}$ and check the conditions in Assumptions 1–5 in polynomial time using standard graph algorithms with additional bookkeeping. For example, consider checking the assumptions for the broker example in §3. Assumption 1 is easily verified for linear utilities; Assumption 2 is also easily verified for credit bound resale; Assumption 3 follows from all agents having $b_{i}>0$; Assumption 4 is satisfied by the endowments of Agents 1 and 3; Assumption 5 is satisfied as Agents 1 and 3 are intermediated by Agent 2 and so all agents have access to the goods they want, Agent 2 is on every trade path, and $G^{S}$ is connected on Agents 1 and 3.

Two additional assumptions on demand systems are needed for our algorithm. These assumptions are standard in auction-based algorithms for approximating equilibria of markets Kapoor et al. (2005); Garg and Kapoor (2006); Garg et al. (2019). First, we assume that the consumption and resale demand systems $C_{i}$ and $R_{i}$ are scale invariant for every agent $i\in[m]$, which is sufficient to guarantee that there exists an equilibrium for our algorithm to approximate for any initial prices. For example, if $\boldsymbol{p}$ is a set of prices at a $\boldsymbol{b}$-resale equilibrium, then scale invariance ensures $\alpha\boldsymbol{p}$ is also a set of equilibrium prices for all $\alpha>0$. The second assumption, weak gross substitutability, appears necessary for agents to myopically update consumption and resale plans without having to retract previous decisions.

We assume that, for every agent $i\in[m]$, the consumption demand system $C_{i}$ satisfies WGS and that the negation of the resale demand system $-R_{i}$ satisfies WGS.⁷⁷7By saying $-R_{i}$ satisfies WGS, we mean that the demand system resulting from negating every resale plan that is the output from $R_{i}$ is WGS. From the reduction in Garg and Kannan (2015), this is equilvalent to satisfying WGS for production. Intuitively, this assumption means that raising the price on a good does not decrease the consumption nor increase the resale of any other good. As such, consumption and resale demand systems that satisfy WGS ensure that local price raises do not leave agents regretting previous decisions. This property will be integral for the algorithm to find approximate equilibria efficiently since it will monotonically increase prices by regular increments. These assumptions are identical to those used in Garg et al. (2019), which introduces a different auction based algorithm for the pure exchange setting; we refer to that work for a comprehensive discussion of WGS consumption demand systems.

Throughout the algorithm, agents will consult a consumption oracle and a resale oracle, described in Definition 5.1. These oracles are algorithms that provide agents with a consumption and resale plan guaranteed to exist by the definitions of WGS demand systems. In the case of consumption, the oracle only cares about satisfying the WGS property of the consumption demand system. For resale, the oracles used in the algorithm also take into consideration an additional request vector of the form $\textbf{r}\in\mathbb{R}_{+}^{\ell}$ as input, and try to have close to $r_{k}$ of each good $k$. These resale oracles satisfy the WGS property of the negated resale demand system, and minimize $\|\textbf{r}-\sum_{j\sim i}\hat{}\boldsymbol{y}^{ij}\|_{1}$ among all negated resale plans satisfying WGS. Taking requests helps resale oracles cater to the actual consumption needs of the economy when multiple resale plans maximize profits.

Our algorithm finds solutions that satisfy relaxed versions of the requirements for $\boldsymbol{b}$-resale equilibria (Definition 3.2). We use a notion of $\left(1+\epsilon\right)$-approximate $\boldsymbol{b}$-resale equilibrium that is consistent with Garg et al. (2019), but uses the stronger notions of approximate clearing, and approximately efficient budget use, from Garg and Kapoor (2006) and Kapoor et al. (2005).

In other words, market clearing is within a multiplicative factor of $(1+\epsilon)$, budgets are all spent within a multiplicative factor of $(1+\epsilon)$, and both the consumption and resale plans are subsets of optimal plans within a multiplicative factor of $(1+\epsilon)$ of prices and budgets.

Using the ideas introduced above, our algorithm achieves the following guarantees. As is often the case in auction-based algorithms, the time complexity is expressed in terms of the largest price found by the algorithm Kapoor et al. (2005); Garg and Kapoor (2006); Garg et al. (2019), which we denote by $p_{max}$. An upper bound on $p_{max}$ can be found for specific sets of demand and resale systems, i.e. when these systems are given by explicit utility functions and resale constraints. Unfortunately, as we demonstrate in §6.2, $p_{max}$ may be super-polynomial in the input size, though in some cases the algorithm still terminates in polynomial time.

Our algorithm can be thought of as a series of localized auctions or negotiation processes, where agents simultaneously try to outbid one another for desired goods and utilize resale to leverage their position in the network (to maximize resale profits which they can use to place bids). For a fixed accuracy parameter $\epsilon>0$, playing out this process gradually increases prices monotonically by a multiplicative factor of $(1+\epsilon)$ until, at termination, the algorithm has converged on a $\left(1+\epsilon\right)$-approximate $\boldsymbol{b}$-resale equilibrium. In this section we only sketch the algorithm; the complete pseudo-code is given in Appendix B (Algorithm 1).

At initialization the parameter $\epsilon>0$ is appropriately chosen, all prices in $\boldsymbol{p}$ are set to unity, and all consumption and resale plans $\boldsymbol{x},\boldsymbol{y}$ to zero. In addition, all agents $i\in[m]$ are given an initial budget of $\boldsymbol{p}^{i}\cdot\boldsymbol{e}^{i}=\|\boldsymbol{e}^{i}\|_{1}$ since no bids have been placed and resale is not profitable yet, as prices are identical. Later, when prices differ in the economy, each agent $i\in[m]$ has a budget given by the sum of $\boldsymbol{p}^{i}\cdot\boldsymbol{e}^{i}$ with the maximum profit $i$ can make from resale for prices in its neighborhood.

A key concept is that of good being assigned. All goods are initially unassigned. As agents place bids on their neighbors’ goods according to the current prices, their neighbors will try to assign goods to the bidder from endowments or using resale. Crucially, a bid corresponds to an assignment of a good at the current price. As bids are placed and assignments made, an agent may assign their entire endowment and exhaust their resale capacity, at which point the agent realizes their good is over-demanded at the current price. In response, the agent will raise their price on over-demanded goods and will begin receiving bids at the higher price. When the process resumes and a bid is placed at the higher price, the agent will renege on assignments at the old price and make a new assignment to the agent placing the bid at the higher price. Bids are thus best understood as a “security deposit” indicating an agent’s commitment to buy the good at the current price, while assignments are best understood as first-come-first-served agreements that are only honored until a better bid comes along. Furthermore, since the price of a good is only raised when an agent has reneged on all assignments at the previous price, a price is only raised when all other options have been exhausted.

With this understanding, roughly speaking, each step in the algorithm is broken into three parts:

1. 1.

   Agents query their consumption oracle and then use any surplus budget to bid on goods in the consumption oracle’s output plan that are not currently satisfied (e.g., due to neighboring agents previously being unable to match demand).

2. 2.

   Having received bids on goods, agents try matching bids by reneging on assignments made with their endowments at the old price. If after reneging on every assignment made at the old price using its endowment the agent is still unable to match a bid, then they query their resale oracle. From the oracle’s output, they adjust their resale plans and place bids accordingly using their resale budget. Finally, if they are still unable to match requests, then the agent raises prices on over-demanded goods and broadcasts the change to their neighbors.

3. 3.

   If a reneged assignment was for consumption, then the agent’s bid is returned. Otherwise, the reneged assignment was for resale and a recursive process might ensue: the agent whose assignment was reneged has its resale bid returned and then must renege on the assignments dependant on this bid accordingly. Since goods can be resold over a long trade path in the underlying graph, this recursive reneging of assignments for resale may span the diameter of the underlying graph in the worst case.

Throughout the course of the algorithm, consumption and resale plans are constantly in flux as assignments get made and reneged on, and budgets are carefully updated whenever prices are raised and bids get placed or returned—we defer the intricacies of this process to Appendix B. The algorithm only terminates when either the market locally clears exactly for every agent or every agent’s budget is nearly spent.

In this section we give proof sketches for both the correctness and runtime of our algorithm (Theorem 5.3), with full proofs in Appendix B.2 and B.3. A crucial observation for both proofs is that, at any given point in the algorithm, a good is only ever assigned at one of two prices: its current price and its old price. To see this, recall the process highlighted in §5.2 for how prices get raised: a good’s price is raised when it is over-demanded, at which point the agent only receives bids at the new price and reneges on assignments made at the previous price as more bids arrive. As was mentioned, agents only raise prices when no assignments exist at the old price and they conclude that their good is over-demanded at the current price.

Correctness. We begin with three observations that hold for the algorithm’s entire duration: (i) Prices are monotonically raised, so a good’s current price is always higher than its old price. (ii) Each agent’s budget is computed using the current prices in their neighborhood, i.e. assuming they are selling their entire endowment and optimally reselling at the current (higher) prices. (iii) Agents bid for resale and consumption according to their respective oracle and the current budget.

Since consumption and negated resale oracles satisfy WGS, from (i) we know that price raises can never increase plans suggested by an agent’s oracles. Therefore, from (iii), it follows that approximate individual rationality and approximately optimal arbitrage hold for every agent for the entirety of the algorithm. The right inequality in approximate clearing follows from the fact that assignments are never made with goods an agent does not have on hand. Similarly, the right inequality in approximately efficient budget use follows from (ii) and (iii) since budgets are always computed at the current prices and oracles always suggest plans within the budget. The left inequality in both approximate clearing and approximately efficient budget use follow from the way termination conditions are specified for the algorithm. When the algorithm terminates because all goods clear locally in the economy, these left inequalities hold trivially; for approximate clearing it is by definition, and for approximately efficient budget use because it implies no good is over-demanded and thus budgets are used fully. For the other termination condition, when every agent’s budget is nearly spent, showing that the left inequality holds requires some careful accounting of technical details about agents’ surplus budgets (Appendix B.2).

Run-Time. To analyze the time complexity of the algorithm, we bound two quantities: (i) the number of times prices can be raised, and (ii) the number of steps between price raises before the algorithm must terminate. Using $p_{max}$ to derive (i) follows the same argument as many other auction-based algorithms Kapoor et al. (2005); Garg and Kapoor (2006). The argument notes that prices are never decreased, and prices are always increased by a factor of $(1+\epsilon)$, and thus the number of price raises is bounded by $\ell\log_{1+\epsilon}p_{max}$. Our derivation of (ii) uses a method resembling an amortized analysis and differs considerably from previous work on auction-based algorithms. We observe that goods are never assigned at an old price, and therefore the total amount of budgets being spent on bids at old prices can only decrease between price raises. Thus, by using the total amount of budgets spent on goods at their old price as a potential, we derive a bound on the amount of time before this potential reaches zero. We then argue that when the potential is zero, no goods are being assigned at their old price in the entire economy, thus either the market exactly clears or some good is over demanded and a price must get raised. Putting these bounds together, and deriving the time complexity of each sub-routine in the algorithm, yields the time complexity in Theorem 5.3. Precise details of this analysis are given in Appendix B.3.

As we saw in the broker example (§3.2), the addition of resale allows goods to move more than one hop in the network. To underscore this point, consider a natural extension of the broker example, where agents having complementary endowments and preferences are connected by some arbitrarily long chain of brokers. For the same reason as before, no equilibrium exists under the KKO model, but we would hope that with resale the market is able to move goods through the underlying network so as to match demand in maximally distant “local markets”.

As with the original broker example, it is simple to check that the conditions of Theorem 4.4 are satisfied when we set $\boldsymbol{b}=(b,\ldots,b)$ for any $b>0$. Thus, there exists a $\boldsymbol{b}$-resale equilibrium. We now argue that in any such equilibrium, some amount of good $1$ must travel all the way from agent $1$ to agent $m$, and good $2$ from agent $m$ to agent $1$. As argued in §3, consider the case where agent $2$ does not resell good $2$ to agent $1$. If agent $1$ had any budget, the market would not clear, as agent $1$ would request good $2$ from herself or from agent $2$. Thus, we must have $p^{1}_{1}=0$, but then there is no optimal consumption plan, as even with zero budget agent $2$ would request an infinite amount of good $1$ from agent $1$. By symmetry, the same applies to agents $m$ and $m-1$. We conclude that, in any $\boldsymbol{b}$-resale equilibrium in this example, goods must traverse the entire length of the network.

The runtime given in Theorem 5.3 depends linearly on $p_{max}$, so for a polynomial runtime guarantee, one may hope to prove a general polynomial upper bound on $p_{max}$. Unfortunately, the following example shows that $p_{max}$ can be exponential in the number of agents. Interestingly, the algorithm still terminates in polynomial time in this example, thus prompting the question of whether a different analysis could yield a general polynomial runtime bound.

Consider an economy where the underlying graph is a chain as in §6.1. There are $\ell=m$ goods, and each agent $i$ is endowed with one unit of good $i$ and nothing else, so that $e_{i}^{i}=1$ and $e^{i}_{j}=0$ for all $j\neq i$. Agents have utility $1$ for their own good and utility $\alpha>1$ for their right neighbor’s good: $u^{i}_{i}=1$, $u^{i}_{i+1}=\alpha$, and $u^{i}_{j}=0$ otherwise. When running the algorithm from §5 with some constant $\epsilon>0$ and agents being considered sequentially in order of $i$, the algorithm terminates in at most $m\log_{1+\epsilon}(\alpha)$ rounds despite $p_{max}=\Theta(\alpha^{m})$. To see this, observe that in the first round each agent such that $i<m$ purchases the entire endowment from $i+1$ until finally agent $m$ raises the price on their endowment since $m-1$ purchased it. After this first round agents $m$ and $m-1$ repeatedly try outbidding one another for $m$’s endowment until the price raises $\log_{1+\epsilon}(\alpha)$ times. Once $\log_{1+\epsilon}(\alpha)$ price raises occur on $m$’s endowment, $m-1$ has maximal bang-per-buck on it’s own endowment and will bid on it after each new price raise on $m$’s endowment. By a symmetric argument, after each series of $\log_{1+\epsilon}(\alpha)$ price raises on the $i^{th}$ agent’s endowment, the $(i-1)^{th}$ agent begins bidding on its own endowment, e.g. $m-2$ will begin bidding on its own endowment after $\log_{1+\epsilon}(\alpha)$ price raises on $m-1$’s endowment. As there are $m$ agents and each agent consumes their own endowment at equilibrium, there are at least $m\log_{1+\epsilon}(\alpha)$ rounds before the algorithm terminates for a total runtime of $\mathcal{O}(m^{6}\log_{1+\epsilon}(\alpha))$. Although the algorithm terminates in polynomial-time, the final price for agent $m$’s good is $p^{m}_{m}=\Theta(\alpha^{m})$.

In Section 5 we introduce an algorithm for finding approximate $\boldsymbol{b}$-resale equilibria of graphical economies with resale. In general the computation of equilibria is a computationally difficult problem (see e.g. Garg et al. (2017)). Garg and Kannan (2015) introduce an algorithm for computing exact equilibria in AD production economies with polyhedral production sets, given the number of goods in the economy as a constant. Through a simple reduction of graphical economies with resale to a classic AD economy with production (as highlighted in the proof of Lemma 4.2), we can see that the algorithm for computing exact equilibria in Garg and Kannan (2015) directly applies to our setting but that the algorithm is only polynomial time when the number of goods and agents are both constant (due to the “tagging” of goods). That said, by simply replacing the global market clearing notion that is typically used in AD economies with our local notion of market clearing in all of their arguments, their algorithm for computing exact equilibria is recovered provided the number of goods is constant in the graphical economy.

Along with the credit bound resale we used in examples throughout this paper, another natural form is commodity bound resale, where agents maximize resale profits subject to a hard constraint on the amount of goods being resold. Formally, resale demand systems $R_{i}$ now return resale plans $\boldsymbol{y}^{i}$ such that setting $\hat{}\boldsymbol{y}^{i}=\boldsymbol{y}^{i}$ maximizes $\sum_{j\simeq i}(\boldsymbol{p}^{i}-\boldsymbol{p}^{j})\cdot\hat{}\boldsymbol{y}^{ij}$ over all $\hat{}\boldsymbol{y}^{i}$ satisfying $\|\hat{}\boldsymbol{y}^{i}\|_{1}\leq b_{i}$. Commodity bounds on resale can be thought of as modeling limitations on storage or bandwidth available to agents for reselling goods.

Graphical economies with commodity bound resale have many appealing properties: they are intuitive, they have straightforward analytic solutions to the broker and market breadth (§6.1) examples, the algorithm in §5 is simple to derive, etc. Unfortunately, since they do not satisfy Assumption 2(ii), graphical economies with commodity bound resale require stronger assumptions in order to prove the general existence of equilibria,⁸⁸8Since commodity bound resale allows agents to resell a finite amount of goods when prices are zero, the propagation argument used in §4 requires unintuitive assumptions in order to ensure existence. For example, one can apply the argument to commodity bounds by appending a condition to Assumption 5 stating that for each good an agent is endowed with there is at least one adjacent neighbor with utility for the good. and fall squarely outside the scope of most existence results found in theoretical economics (e.g. Arrow and Debreu (1954); McKenzie (1981, 1961, 1959); Maxfield (1997); Walras (1874); Mas-Collel et al. (1995)).

In order to address concerns about the centralized nature of traditional economic models, several recent works have introduced models of decentralized markets. These models often place markets on a multipartite graph, where edges represent two agents being capable of trade with one another, and the agents play a specific role in buyer-seller interactions possibly facilitated by intermediaries, e.g. Blume et al. (2007); Gale and Kariv (2009); Choi et al. (2017); Han and Juarez (2018); Hinnosaar (2019). Kakade et al. (2004a) introduced a generalization of the AD exchange model to a graphical setting, enabling a robust set of interactions between agents on an arbitrary set of goods which is lacking in other economic models on networks. Unfortunately, as we have argued, the model in Kakade et al. (2004a) is “too local” and does not allow for any degree of intermediation between agents.

This paper generalizes the work in Kakade et al. (2004a) to allow for robust intermediation in graphical economies. One could therefore consider our model as a unifying generalization of many models of trade in the literature of decentralized markets. Furthermore, by presenting two modes for equating graphical economies with AD economies,⁹⁹9Kakade et al. (2004a) showed that AD exchange economies are equivalent to graphical economies with agents embedded on a complete graph. In §3 we argued that AD exchange economies are equivalent to graphical economies with a certain class of Resale demand systems and sufficiently large resale capacities. This gives two ways for graphical economies to interpolate between centralized and decentralized markets: (i) by changing the density of the underlying graph, and (ii) by changing resale capacities in the economy. we equip the study of decentralized markets with a novel and mathematically rigorous means of understanding decentralized market models within the context of competitive AD equilibria.

The example in §6.2 shows that $p_{max}$ may not be polynomially-bounded even when the algorithm terminates in polynomial time; characterizing instances for which the runtime is polynomially-bounded in the input size is an interesting open question. Another important question is to understand the relationship between the underlying graph structure and equilibrium outcomes. For instance, the broker example in §3.2 illustrates the fact that a node can extract rent solely from their position in the network—exploring a more precise connection between this advantage and graph-theoretic parameters such as degree centrality is an exciting direction for future work. Similarly, studying market breadth and depth yields a series of natural questions about graphical economies. Finally, since resale is a special case of production, it is of interest to find intuitive assumptions for guaranteeing existence in other forms of resale (e.g., commodity bound resale), and more generally, extend our model to a graphical production setting.

We thank Nehal Kamat, Camden Elliot-Williams, and Jessie Finocchiaro for detailed comments and other contributions. We are indebted to Jugal Garg, Ruta Mehta, Simina Brânzei, and Michael Kearns for crucial references and discussions. This work was supported in part from the National Science Foundation under Grant No. 1657598.