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.