You are currently browsing the category archive for the ‘equilibria’ category.

Volume 42 of the AER, published in 1952, contains an article by Paul Samuelson entitled Spatial Price Equilibrium and Linear Programming’. In it, Samuelson uses a model of Enke (1951) as a vehicle to introduce the usefulness of linear programming techniques to Economists. The second paragraph of the paper is as follows:

In recent years economists have begun to hear about a new type of theory called linear programming. Developed by such mathematicians as G. B. Dantzig, J. v. Neumann, A. W. Tucker, and G. W. Brown, and by such economists as R. Dorfman, T. C. Koopmans, W. Leontief, and others, this field admirably illustrates the failure of marginal equalization as a rule for defining equilibrium. A number of books and articles on this subject are beginning to appear. It is the modest purpose of the following discussion to present a classical economics problem which illustrates many of the characteristics of linear programming. However, the problem is of economic interest for its own sake and because of its ancient heritage.

Of interest are the 5 reasons that Samuelson gives for why readers of the AER should care.

1. This viewpoint might aid in the choice of convergent numerical iterations to a solution.

2. From the extensive theory of maxima, it enables us immediately to evaluate the sign of various comparative-statics changes. (E.g., an increase in net supply at any point can never in a stable system decrease the region’s exports.)

3. By establishing an equivalence between the Enke problem and a maximum problem, we may be able to use the known electric devices for solving the former to solve still other maximum problems, and perhaps some of the linear programming type.

4. The maximum problem under consideration is of interest because of its unusual type: it involves in an essential way such non-analytic functions as absolute value of X, which has a discontinuous derivative and a corner; this makes it different from the conventionally studied types and somewhat similar to the inequality problems met with in linear programming.

5. Finally, there is general methodological and mathematical interest in the question of the conditions under which a given equilibrium problem can be significantly related to a maximum or minimum problem.

There is a test for smarts’ that Sir Peter Medawar was fond of. I often think of it when teaching equilibrium.

If you have ever seen an El Greco, you will notice that the figures and faces are excessively elongated. Here is an example.The eye surgeon Patrick Trevor-Roper, brother to the historian Hugh offered an explanation. Readers of  certain vintage will recall the long running feud between Hugh Trevor-Roper and Evelyn Waugh. Waugh said that the best thing Hugh Trevor-Roper could do would be to change his name and leave Oxford for Cambridge. Hugh Trevor-Roper eventually  became Lord Dacre and left Oxford for Cambridge. But, I digress.

Returning to Patrick, he suggested that El Greco had a form of astigmatism, which distorted his vision and led to elongated images forming on his retina. Medawar’s question was simple: was Patrick Trevor-Roper correct?

General equilibrium! Crown jewel of micro-economic theory. Arrow and Hahn give the best justification:

“There is by now a long and fairly imposing line of economists from Adam Smith to the present who have sought to show that a decentralized economy motivated by self-interest and guided by price signals would be compatible with a coherent disposition of economic resources that could be regarded, in a well defined sense, as superior to a large class of possible alternative dispositions. Moreover the price signals would operate in a way to establish this degree of coherence. It is important to understand how surprising this claim must be to anyone not exposed to the tradition. The immediate common sense’ answer to the question What will an economy motivated by individual greed and controlled by a very large number of different agents look like?’ is probably: There will be chaos. That quite a different answer has long been claimed true and has permeated the economic thinking of a large number of people who are in no way economists is itself sufficient ground for investigating it seriously. The proposition having been put forward and very seriously
entertained, it is important to know not only whether it is true, but whether it could be true.”

But how to make it come alive for my students? When first I came to this subject it was in furious debates over central planning vs. the market. Gosplan, the commanding heights, indicative planning were as familiar in our mouths as Harry the King, Bedford and Exeter, Warwick and Talbot, Salisbury and Gloucester….England, on the eve of a general election was poised to leave all this behind. The question, as posed by Arrow and Hahn, captured the essence of the matter.

Those times have passed, and I chose instead to motivate the simple exchange economy by posing the question of how a sharing economy might work. Starting with two agents endowed with a positive quantity of each of two goods, and given their utility functions, I asked for trades that would leave each of them better off. Not only did such trades exist, there were more than one. Which one to pick? What if there were many agents and many goods? Would bilateral trades suffice to find mutually beneficial trading opportunities? Tri-lateral? The point of this thought experiment was to show how in the absence of prices, mutually improving trades might be very hard to find.

Next, introduce prices, and compute demands. Observed that demands in this world could increase with prices and offered an explanation. Suggested that this put existence of market clearing prices in doubt. Somehow, in the context of example this all works out. Hand waved about intermediate value theorem before asserting existence in general.

On to the so what. Why should one prefer the outcomes obtained under a Walrasian equilibrium to other outcomes? Notion of Pareto optimality and first welfare theorem. Highlighted weakness of Pareto notion, but emphasized how little information each agent needed other than price, own preferences and endowment to determine what they would sell and consume. Amazingly, prices coordinate everyone’s actions. Yes, but how do we arrive at them? Noted and swept under the rug, why spoil a good story just yet?

Gasp! Did not cover Edgeworth boxes.

Went on to introduce production. Spent some time explaining why the factories had to be owned by the consumers. Owners must eat as well. However it also sets up an interesting circularity in that in small models, the employee of the factory is also the major consumer of its output! Its not often that a firm’s employers are also a major fraction of their consumers.

Closed with, how in Walrasian equilibrium, output is produced at minimum total cost. Snuck in the central planner, who solves the problem of finding the minimum cost production levels to meet a specified demand. Point out that we can implement the same solution using prices that come from the Lagrange multiplier of the central planners demand constraint. Ended by coming back full circle, why bother with prices, why not just let the central planner have his way?

Starr’s ’69 paper considered Walrasian equilibria in exchange economies with non-convex preferences i.e., upper contour sets of utility functions are non-convex. Suppose ${n}$ agents and ${m}$ goods with ${n \geq m}$. Starr identified a price vector ${p^*}$ and a feasible allocation with the property that at most ${m}$ agents did not receiving a utility maximizing bundle at the price vector ${p^*}$.

A poetic interlude. Arrow and Hahn’s book has a chapter that describes Starr’s work and closes with a couple of lines of Milton:

A gulf profound as that Serbonian Bog
Betwixt Damiata and Mount Casius old,
Where Armies whole have sunk.

Milton uses the word concave a couple of times in Paradise Lost to refer to the vault of heaven. Indeed the OED lists this as one of the poetic uses of concavity.

Now, back to brass tacks. Suppose ${u_i}$ is agent ${i}$‘s utility function. Replace the upper contour sets associated with ${u_i}$ for each ${i}$ by its convex hull. Let ${u^*_i}$ be the concave utility function associated with the convex hulls. Let ${p^*}$ be the Walrasian equilibrium prices wrt ${\{u^*_i\}_{i=1}^n}$. Let ${x^*_i}$ be the allocation to agent ${i}$ in the associated Walrasian equilibrium.

For each agent ${i}$ let

$\displaystyle S^i = \arg \max \{u_i(x): p^* \cdot x \leq p^*\cdot e^i\}$

where ${e^i}$ is agent ${i}$‘s endowment. Denote by ${w}$ the vector of total endowments and let ${S^{n+1} = \{-w\}}$.

Let ${z^* = \sum_{i=1}^nx^*_i - w = 0}$ be the excess demand with respect to ${p^*}$ and ${\{u^*_i\}_{i=1}^n}$. Notice that ${z^*}$ is in the convex hull of the Minkowski sum of ${\{S^1, \ldots, S^n, S^{n+1}\}}$. By the Shapley-Folkman-Starr lemma we can find ${x_i \in conv(S^i)}$ for ${i = 1, \ldots, n}$, such that ${|\{i: x_i \in S^i\}| \geq n - m}$ and ${0 = z^* = \sum_{i=1}^nx_i - w}$.

When one recalls, that Walrasian equilibria can also be determined by maximizing a suitable weighted (the Negishi weights) sum of utilities over the set of feasible allocations, Starr’s result can be interpreted as a statement about approximating an optimization problem. I believe this was first articulated by Aubin and Elkeland (see their ’76 paper in Math of OR). As an illustration, consider the following problem :

$\displaystyle \max \sum_{j=1}^nf_j(y_j)$

subject to

$\displaystyle Ay = b$

$\displaystyle y \geq 0$

Call this problem ${P}$. Here ${A}$ is an ${m \times n}$ matrix with ${n > m}$.

For each ${j}$ let ${f^*_j(\cdot)}$ be the smallest concave function such that ${f^*_j(t) \geq f_j(t)}$ for all ${t \geq 0}$ (probably quasi-concave will do). Instead of solving problem ${P}$, solve problem ${P^*}$ instead:

$\displaystyle \max \sum_{j=1}^nf^*_j(y_j)$

subject to

$\displaystyle Ay = b$

$\displaystyle y \geq 0$

The obvious question to be answered is how good an approximation is the solution to ${P^*}$ to problem ${P}$. To answer it, let ${e_j = \sup_t [f_j^*(t) - f_j(t)]}$ (where I leave you, the reader, to fill in the blanks about the appropriate domain). Each ${e_j}$ measures how close ${f_j^*}$ is to ${f_j}$. Sort the ${e_j}$‘s in decreasing orders. If ${y^*}$ is an optimal solution to ${P^*}$, then following the idea in Starr’s ’69 paper we get:

$\displaystyle \sum_{j=1}^nf_j(y^*_j) \geq \sum_{j=1}^nf^*_j(y^*_j)- \sum_{j=1}^me_j$

Bertrand, Cournot and Hotelling was on the menu. In addition to covering the mechanics of computing equilibria, spent time trying to motivate each model. Cournot is, I think, the hardest. The short version of the story I gave was this. Firms choose their capacities/quantities, then go to a middleman (should have said platform, so much sexier these days) who auctions of their joint output via a uniform price auction. Wholesale electricity markets come close to this story, which allows one to use Cournot to convey the idea of supply (demand) reduction and the scandal of the California power markets.

Hotelling is easier to motivate, and is a useful vehicle to illustrate why they should always break’ a model to learn something about it. In the standard Hotelling setup, no reservation price is specified for the buyers. Now, allow the two firms to merge and act like a monopolist. The monopolist’s profit function is unbounded! However, you can still write down a first order condition and solve it. Thus, it is also a useful reminder of the dangers of blindly differentiating and setting to zero.

Contrasted Cournot with Hotelling, for example, the effect on consumer surplus when a merger results in a cost reduction for the merged firm. Also provided an opportunity to remind the class about monopoly and evaluating consumer surplus.

Concluded the module on imperfect competition by applying what  had been discussed to Amazon vs. Apple vs the publishers. Another opportunity to walk down memory lane with double marginalization and then add a wrinkle involving competition in the downstream market.

I had the opportunity to participate in a delightful workshop on mechanism design and the informed principal organized by Thomas Troeger and Tymofiy Mylovavnov. The setting was a charming schloss‘ (manse rather than castle)  an hour and half outside of Mannheim. They had gathered together a murderer’s row of speakers and auditors. Suffice it to say I was the infimum of the group and lucky to be there.

One (among many) remarkable talks was given by Roger Myerson on his 1983 paper entitled Mechanism Design by an Informed Principal‘. Kudos to Thomas and Tymofiy for coming up with the idea of doing this. It brought to mind some couplets from Locksley Hall:

When the centuries behind me like a fruitful land reposed;
When I clung to all the present for the promise that it closed:

When I dipt into the future far as human eye could see;
Saw the Vision of the world and all the wonder that would be.—

By the way, the last pair of lines appears on the dedication plaque that graces the USS Voyager (of the Star Trek franchise).

What did Roger do? He tried as best as possible, given the gulf of time, to explain why he had chosen the tack that he did in the paper (axiomatic) and his hope for how it would influence research on the subject.

A principal with private information must propose a mechanism to an agent. However, the choice of mechanism will reveal something of the principal’s private information to the agent. Thus, the problem of mechanism design in this setting is not a straight optimization problem. It is, at a high level, a signaling game. The signals are the set of mechanisms that the principal can propose. Thus, one seeks an equilibrium of this game. But which equilibrium?

In section 7 of the paper, Roger approaches the question axiomatically in the spirit of Nash bargaining. Indeed, Roger made just such an analogy in his talk. Nash did not have in mind any particular bargaining protocol, but a conviction that any reasonable protocol must satisfy some natural invariance conditions. Some decades later Rubinstein arrives with a bargaining protocol to justify Nash’s conviction. So, Roger sought the same here and expressed the wish to see this year a vindication of his hopes.

Lest you think the audience accepted Roger’s axioms uncritically, Thomas Troeger, pointed out Roger’s axiom 1 ruled out some possibly natural settings like Rothschild & Stiglitz. Roger argued that it was right and proper to rule this out and battle joined!

This is the second posts about stability and equilibrium in trading networks. The first post may be found here. In it I assumed a single homogenous divisble good being traded by agents with quasi-linear preferences. Each agent was associated with a vertex of a graph and the edges represented pairs of agents who were permitted to trade with each other. Furthermore, each agent was designated the role of buyer and seller. Buyers could only trade with sellers and vice-versa. This meant the underlying graph was bipartite. In this post I will drop the assumption that they trade a homogenous good and that it is dvisible.

As noted in the earlier post, when the utility of buyers and the costs of sellers are linear in quantity, total unimodularity of the underlying constraint matrix is sufficient to ensure the existence of Walrasian prices that support an efficient allocation that is integral. If buyer utility functions become concave or sellers’s cost functions become convex, this is no longer true.

Suppose instead that the buyers utility functions are M${^{\#}}$-concave and seller’s cost functions are M${^{\#}}$-convex (object to be defined soon), then, the efficient allocation (the precise formulation will appear below) is indeed integer valued and supporting Walrasian prices exist. The corresponding allocations and prices can be interpreted as stable outcomes which cannot be blocked. This result was established by Murota and Tamura (2001).

I’ll define M${^{\#}}$-concavity. For any integer valued vector ${x}$ in ${\Re^n}$ let ${supp^+(x) = \{i: x_i > 0\}}$ and ${supp^-(x) = \{i : x_i < 0\}}$. A real valued function ${f}$ defined on the integer vectors of ${\Re^n}$ (with non-empty domain) is M${^{\#}}$ -concave if for all ${x, y}$ in its domain and any index ${u \in supp^+(x-y)}$ there exists an index ${v}$ in ${\{0\} \cup supp^{-}(x-y)}$ such that

$\displaystyle f(x) + f(y) \leq f(x - \chi_u + \chi_v) + f(y + \chi_u - \chi_v).$

Here ${\chi_i}$ is the 0-1 vector with a zero in every component except component ${i}$. I describe three different ways one might interpret this notion.

First, one can think of M${^{\#}}$-concavity as trying to capture an essential feature of the basis exchange property of matroids. If you don’t know what a matroid is, skip to the next paragraph. Think of the vectors ${x}$ and ${y}$ as being 0-1 and representing subsets of columns of some given matrix, ${A}$, say. Define ${f(x)}$ to be the rank of the columns in the subset associated with ${x}$. What the definition of M${^{\#}}$-concavity captures is this: for any column, ${u}$ I remove from ${x}$, that is not in ${y}$ and add it to ${y}$, I can find (possibly) a column from ${y}$ (not in ${x}$) to add to ${x}$ and not diminish the sum of the ranks of the two sets. The argument is straightforward.

A second interpretation is to be had by comparing the definition of M${^{\#}}$-concavity to the following way of stating concavity of a function:

$\displaystyle f(x) + f(y) \leq f(x - \frac{x-y}{2}) + f(y + \frac{x-y}{2})$

If ${x}$ and ${y}$ were numbers with ${x > y}$, then, the first term on the right represents a step from ${x}$ closer to ${y}$ and the second term is a step from ${y}$ closer to ${x}$. M${^{\#}}$-concavity can be interpreted as a discrete analogy of this. Think of ${x}$ being above and to the left of ${y}$. A step closer to ${y}$ would means one step down in the ${u}$ direction and a step to the right in the ${v}$ direction., i.e. ${x - \chi_u + \chi_v}$. The vector ${y + \chi_u - \chi_v}$ has a similar interpretation.

The third interpretation comes from an equivalent definition of M${^{\#}}$-concavity, one that shows that it is identical to the notion of gross substitutes proposed by Kelso and Crawford (1982). Let ${p \in \Re^n}$ be a non-negative price vector. Let ${x}$ be a non-negative integer that maximizes ${f(x) - p \cdot x}$, i.e., a utility maximizing bundle. Consider a new price vector ${p' \geq p}$. Then there exists a new utility maximizing bundle ${y}$ such that ${y_i \geq x_i}$ for all ${i}$ such that ${p_i = q_i}$. In words, the demand for goods whose price did not change cannot go down.

The key result of Murota and Tamura is that the following linear program has an integer optimal solution when the ${U_i}$‘s are M${^{\#}}$-concave and the ${C_j}$‘s are M${^{\#}}$-convex.

$\displaystyle \max \sum_{i \in B}U_i(x_{ij}:\{j: (i,j) \in E\}) - \sum_{j \in S}C_j(x_{ij}: \{i:(i,j) \in E\})$

subject to

$\displaystyle 0 \leq x_{ij} \leq d_{ij}\,\, \forall (i,j) \in E$

Notice, that buyer’s utilities do not necessarily depend on the total amount consumed. They can depend on the vector of inflows from the various sellers (similarly for the sellers). We can interpret this to mean that the sellers sell different goods which are substitutes for each other and there is an upper limit, ${d_{ij}}$ on the amount of seller ${j}$‘s good that can go to seller ${i}$. Such a bound is necessary to make sure the problem is well defined. Consider the case when utilities and costs are linear in quantity. The problem could be unbounded then. A second interpretation is that seller’s sell the same good but under different contractual terms (payment plan, delivery date etc.) which make them, in the buyer’s eyes, imperfect substitutes. The only element of the contract not fixed is the price and that is what is determined in equilibrium.

This is the first of a series of posts about stability and equilibrium in trading networks. I will review and recall established results from network flows and point out how they immediately yield results about equilibria, stability and the core of matching markets with quasi-linear utility. It presumes familiarity with optimization and the recent spate of papers on matchings with contracts.

The simplest trading network one might imagine would involve buyers (${B}$) and sellers (${S}$) of a homogenous good and a set of edges ${E}$ between them. No edges between sellers and no edges between buyers. The absence of an edge in ${E}$ linking ${i \in B}$ and ${j \in S}$ means that ${i}$ and ${j}$ cannot trade directly. Suppose buyer ${i \in B}$ has a constant marginal value of ${v_i}$ upto some amount ${d_i}$ and zero thereafter. Seller ${j \in S}$ has a constant marginal cost of ${c_j}$ upto some capacity ${s_j}$ and infinity thereafter.

Under the quasi-linear assumption, the problem of finding the efficient set of trades to execute can be formulated as a linear program. Let ${x_{ij}}$ for ${(i,j) \in E}$ denote the amount of the good purchased by buyer ${i \in B}$ from seller ${j \in S}$. Then, the following program identifies the efficient allocation:

$\displaystyle \max \sum_{(i,j) \in E} (v_i - c_j)x_{ij}$

subject to

$\displaystyle \sum_{j \in S: (i,j) \in E}x_{ij} \leq d_i\,\, \forall i \in B$

$\displaystyle \sum_{i \in B:(i,j) \in E}x_{ij} \leq s_j\,\, \forall j \in S$

$\displaystyle x_{ij} \geq 0\,\, (i,j) \in E$

This is, of course, an instance of the (discrete) transportation problem. The general version of the transportation problem can be obtained by replacing each coefficient of the objective function by arbitrary numbers ${w_{ij}}$. This version of the transportation problem is credited to the mathematician F. J. Hitchcock and published in 1941. Hitchcock’s most famous student is Claude Shannon.

The continuous’ version of the transportation problem was formulated by Gaspard Monge and described in his 1781 paper on the subject. His problem was to split two equally large volumes (representing the initial location and the final location of the earth to be shipped) into infinitely many small particles and then match them with each other so that the sum of the products of the lengths of the paths used by the particles and the volume of the particles is minimized. The ${w_{ij}}$‘s in Monge’s problem have a property since called the Monge property, that is the same as submodularity/supermodularity. This paper describes the property and some of its algorithmic implications. Monge’s formulation was subsequently picked up by Kantorovich and the study of it blossomed into the specialty now called optimal transport with applications to PDEs and concentration of measure. That is not the thread I will follow here.

Returning to the Hitchcock, or rather discrete, formulation of the transportation problem let ${p_j}$ be the dual variables associated with the first set of constraints (the supply side) and ${\lambda_i}$ the dual variables associated with the second or demand set of constraints. The dual is

$\displaystyle \min \sum_{j \in S} s_jp_j + \sum_{i \in B}d_i\lambda_i$

subject to

$\displaystyle p_j + \lambda_i \geq [v_i-c_j]\,\, \forall (i,j) \in E$

$\displaystyle p_j, \lambda_i \geq 0\,\, \forall j \in S, i \in B$

We can interpret ${p_j}$ as the unit price of the good sourced from seller ${j}$ and ${\lambda_i}$ as the surplus that buyer ${i}$ will enjoy at prices ${\{p_j\}_{j \in S}}$. Three things are immediate from the duality theorem, complementary slackness and dual feasibility.

1. If ${x^*}$ is a solution to the primal and ${(p^*, \lambda^*)}$ an optimal solution to the dual, then, the pair ${(x^*, p^*)}$ form a Walrasian equilibrium.
2. The set of optimal dual prices, i.e., Walrasian prices live in a lattice.
3. The dual is a (compact) representation of the TU (transferable utility) core of the co-operative game associated with this economy.
4. Suppose the only bilateral contracts we allow between buyer ${i}$ and seller ${j}$ are when ${(i,j) \in E}$. Furthermore, a contract can specify only a quantity to be shipped and price to be paid. Then, we can interpret the set of optimal primal and dual solutions to be the set of contracts that cannot be blocked (suitably defined) by any buyer seller pair ${(i,j) \in E}$.
5. Because the constraint matrix of the transportation problem is totally unimodular, the previous statements hold even if the goods are indivisible.

As these are standard, I will not reprove them here. Note also, that none of these conclusions depend upon the particular form of the coefficients in the objective function of the primal. We could replace ${[v_i - c_j]}$ by ${w_{ij}}$ where we interpret ${w_{ij}}$ to be the joint gain gains from trade (per unit) to be shared by buyer ${i}$ and seller ${j}$.

Now, suppose we replace constant marginal values by increasing concave utility functions, ${\{U_i(\cdot)\}_{i \in B}}$ and constant marginal costs by ${\{C_j (\cdot)\}_{j \in S}}$? The problem of finding the efficient allocation becomes:

$\displaystyle \max \sum_{i \in B}U_i(\sum_{j: (i,j) \in E}x_{ij}) - \sum_{j \in S}C_j(\sum_{i: (i,j) \in E}x_{ij})$

subject to

$\displaystyle \sum_{j \in S: (i,j) \in E}x_{ij} \leq d_i\,\, \forall i \in B$

$\displaystyle \sum_{i \in B:(i,j) \in E}x_{ij} \leq s_j\,\, \forall j \in S$

$\displaystyle x_{ij} \geq 0\,\, (i,j) \in E$

This is an instance of a concave flow problem. The Kuhn-Tucker-Karush conditions yield the following:

1. If ${x^*}$ is a solution to the primal and ${(p^*, \lambda^*)}$ an optimal Lagrangean, then, the pair ${(x^*, p^*)}$ form a Walrasian equilibrium.
2. The set of optimal Lagrange prices, i.e., Walrasian prices live in a lattice.
3. Suppose the only bilateral contracts we allow between buyer ${i}$ and seller ${j}$ are when ${(i,j) \in E}$. Furthermore, a contract can specify only a quantity to be shipped and price to be paid. Then, we can interpret the set of optimal primal and dual solutions to be the set of contracts that cannot be blocked (suitably defined) by any buyer seller pair ${(i,j) \in E}$.

Notice, we lose the extension to indivisibility. As the objective function in the primal is now concave, an optimal solution to the primal may occur in the interior of the feasible region rather than at an extreme point. To recover integrality’ we need to impose a stronger condition on ${\{U_i\}_{i \in B}}$ and ${\{C_j\}_{j \in S}}$, specifically, they be ${M}$-concave and convex respectively. This is a condition tied closely to the gross substitutes condition. More on this in a subsequent post.