Uniform Equilibrium

When studying dynamic interactions, economists like discounted games. Existence of equilibrium is assured because the payoff is a continuous function of the strategies of the players, and construction of equilibrium strategies often require ingenious tricks, and so are fun to think about and fun to read. Unfortunately in practice the discounted evaluation is often not relevant. In many cases players, like countries, firms, or even humans, do not know their discount factor. Since the discounted equilibrium strategies highly depend on the discount factor, this is a problem. In other cases, the discount factor changes over time in an unknown way. This happens, for example, when the discount factor is derived from the interest rate or the players monetary or familial situation. Are predictions and insights that we get from a model with a fixed and known discount still hold in models with changing and unknown discount factor?

To handle such situations, the concept of a uniform equilibrium was defined. A strategy vector is a uniform ε-equilibrium if it is ε-equilibrium in all discounted games, for all discount factors sufficiently close to 1 (that is, whenever the players are sufficiently patient). Thus, if a uniform ε-equilibrium exists, then the players can play an approximate equilibrium as soon as they are sufficiently patient. In our modern world, in which one can make zillions of actions in each second, the discount factor is sufficiently close to 1 for all practical purposes. A payoff vector x is a uniform equilibrium payoff if for every ε>0 there is a uniform ε-equilibrium that yields payoff that is ε-close to x.

In repeated games, the folk theorem holds for the concept of uniform equilibrium (or for the concept of uniform subgame perfect equilibrium). Indeed, given a feasible and strictly individually rational payoff x, take a sequence of actions such that the average payoff along the sequence is close to x. Let the players play repeatedly this sequence of actions while monitoring the others, and have each deviation punished by the minmax value. When the discount factor is close to 1, the discounted payoff of the sequence of actions is close to the average payoff, and therefore the discounted payoff that this strategy vector yields is close to x. If one insists on subgame perfection, then punishment is achieved by a short period of minmaxing followed by the implementation of an equilibrium payoff that yields the deviator a low payoff.

For two-player zero-sum stochastic games, Mertens and Neyman (1981) proved that the uniform value exists. Vieille (2000) showed that in two-player non-zero-sum stochastic games uniform ε-equilibria exist. Whether or not this result extends to any number of players is still an open problem.

Why do I tell you all that? This is a preparation for the next post, that will present a new and striking result by a young French Ph.D. student.

Equilibrium & Stability in Trading Networks (part 2)

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 in let and . A real valued function defined on the integer vectors of (with non-empty domain) is M -concave if for all in its domain and any index there exists an index in such that

Here is the 0-1 vector with a zero in every component except component . 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 and as being 0-1 and representing subsets of columns of some given matrix, , say. Define to be the rank of the columns in the subset associated with . What the definition of M-concavity captures is this: for any column, I remove from , that is not in and add it to , I can find (possibly) a column from (not in ) to add to 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:

If and were numbers with , then, the first term on the right represents a step from closer to and the second term is a step from closer to . M-concavity can be interpreted as a discrete analogy of this. Think of being above and to the left of . A step closer to would means one step down in the direction and a step to the right in the direction., i.e. . The vector 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 be a non-negative price vector. Let be a non-negative integer that maximizes , i.e., a utility maximizing bundle. Consider a new price vector . Then there exists a new utility maximizing bundle such that for all such that . 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 ‘s are M-concave and the ‘s are M-convex.

subject to

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, on the amount of seller ‘s good that can go to seller . 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.