Lecture notes for COMS 6998 - Social Network Economics
Fall 2013, Columbia University
by A. Chaintreau


Part B.1 - Trading with Network Constraints

All the following works are considering the question: “How is the nature and form of a network that describes constraints or influence between nodes have an impact on purchasing behavior, pricing schemes, and allocation of goods?”

They all differ according to one or several dimensions that characterize more generally multiple aspects of economic models:

Keeping the above degrees of freedom in mind, all the works that analyze how networks affect outcome of economic systems can be classified in one of two lines of work:

Allocation of fixed supply of indivisible goods

Matching Markets and Buyer-Seller Networks

In a system with fixed supply, a set of sellers (or suppliers, or owners) wish to enter a trade to sell a type of good. For indivisible goods, most of the works consider the basic situation where each seller has only one of them (that he is ready to sell at any positive price), and a set of buyers all wish to purchase one each (and may possibly value the good differently).

In the case where all sellers and buyers come to the same marketplace and are all able to enter an exchange, this case is a subset of a matching market.

Quick review of Matching Markets

Buyer-seller network: Efficiency and Stability of Allocation

Matching market with some "accessibility constraints" form a model of how choices and alternatives impact the economy. This was first studied in two economic papers at the beginning of the 2000s. Lorelai

R. E. Kranton and D. F. Minehart, “A Theory of Buyer-Seller Networks,” The American Economic Review, vol. 91, no. 3, pp. 485–508, Jun. 2001.

The main contributions of these works are:

Analysis of the ascending auctions:

Proof that dropping auction at one’s valuation is a weakly dominant strategy.

Proof that the auction results in an efficient allocation

What topological property determines the price?

R. Kranton and D. Minehart, “Competition for goods in buyer-seller networks,” Review of Economic Design, 2000.

Main contributions:

More precisely:

Bargaining in a buyer seller market:

One criticism to the work above is that the auction described runs with full information and needs to consider all subsets at a given time to operate. It motivates to understand how simpler bargaining/tatonnement dynamics among prices in a series of local markets may or may not end in such efficient operating point.

M. Corominas-Bosch, “Bargaining in a network of buyers and sellers,” Journal of Economic Theory, vol. 115, no. 1, pp. 35–77, Mar. 2004.

This paper considers a bargaining between sellers and buyers through some forms of alternating offers bargaining that was already studied in isolation in a classic 1982 paper. In the graphical version,

Trading with intermediaries

In this other paper below, a network that is related to the buyers sellers networks is shown, with an additional class of middle men (traders, or agents) that are responsible to make the price.

L. Blume, D. Easley, and J. M. Kleinberg, “Trading networks with price-setting agents,” Games and Economic Behavior, 2009. (see also Chapter~11 in Easley-Kleinberg's book for some examples (but no proof), and a previous conference version of this work at EC 2007)

In this model, Instead of being directly connected to each other, there exists a set of intermediaries (sometimes called middlemen). To quote the authors, “Individual buyers and sellers often trade through intermediaries, not all buyers and sellers have access to the same intermediaries, and not all buyers and sellers trade at the same price. Rather, the prices that each buyer and seller commands are determined in part by the range of alternatives that their respective network positions provide.” Motivating scenarios include agriculture trading in developing countries (due to geographical constraints), and financial markets (at a high level).

Summary of main contributions:

Some implications of trading network analysis:

It is also interesting to discuss the potential generalization of these results.

Overview of the proof:

Allocation of fixed supply of divisible goods

In an exchange economy, agents com to a marketplace with an endowement of goods that they wish to trade with others. Most of the work considers the case where all goods are infinitely divisible, a situation in which money or cash can be considered as a good like any other, or might even not formally exist in the first place.

Quick review of exchange economy

Let us first review a model of exchange of goods introduced by Arrow & Debreu in a famous 1954 paper.

This spectacular result, which prove that free trade can always effectively improve users’ utility generally relies on two assumptions: (i) moderate satiability} the utility a user has for a quantity of goods is always increasing, continuous and quasi concave. In a nutshell, the users always wants more, but receives a decreasing marginal return. (ii) non exclusivity, namely every user initially posesses at least a positive small quantity of each good.

Exchange economies with trading constraints**

S. Kakade, M. Kearns, L. Ortiz, R. Pemantle, and S. Suri, “Economic properties of social networks,” Advances in Neural Information Processing Systems, vol. 17, 2005.

What if consumers (which may also in this model denote institution, or countries) cannot exchange all with each others, but are restricted to trade with a set of partners that are neighbors in a graph. This question posed in the paper above poses an interesting problem as we can easily imagine situations in which all players have an interest in trading the same good \emph{at different prices} – think for instance of two entirely disconnected regions. In other words, Arrow Debreu classical case, for which a single third party can organize the exchanges of goods centrally, and would trivially generalize to various disconnected cliques, needs to be revisited as nodes need to solve the same problem locally.

This result shows that in very general terms, even in situation where traders enjoy particular dominant position, market equilibria exist that predict how much they can benefit.

Purchase Markets, and their graphical counterpart

Our previous model does not distinguish players depending on their role in the economy (individual sellers, individual consumers, small or large corporations). In fact, it does not even explicitly includes a currency. But it is general enough to include many situations where a consumers come to the market bringing his workforce or some cash in order to interact with other players. One such case is a purchase market (also known as Fischer’s model of buyer-seller market), where k indifinitely divisible goods are initially available (in quantity g1,,gk). A set of consumers enters the market with a cash endowement and various utilities for this set of goods that they can purchase. As above, an equilibrium is a set of price and consumption plans that clears this set of goods and plans represent the best bundles each consumer can purchase after selling her endowment. For linear utility, such equilibria always exists and all equilibria have the same set of unique prices. Consumption plans may not be unique, \eg for symmetry reasons.

S. Kakade, M. Kearns, L. Ortiz, and R. Pemantle, “The economics of social networks,” presented at the Advances in Neural Information Processing Systems (NIPS), 2004.,

This paper considers a \emph{graphical purchase market}, in which goods are made available by multiple sellers and buyers can only buy from a subset of them. Again the interest for this case lies in that the same good can now be traded by multiple vendors at different prices. A buyer would necessarily purchase all of her goods from the cheapest vendor she has available, but it might be in the interest of a vendor to lose a customer while making more profit on another one.

Network formation and purchase markets

E. Even-Bar, M. Kearns, and S. Suri, “A network formation game for bipartite exchange economies,” presented at the SODA ‘07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, 2007.

Focusing on the same simple case (a single good, uniform nominal cash and goods endowment among players) studies a game where the network of buyer-seller connection is not fixed, as any player can in parallel “purchases” a node for a cost α. The two decisions are made simultaneously by all players. A Nash equilibrium of this game is therefore one where all players who receives their wealth in the graph they build minus the payment of their edges. The most interesting property of this game is that the \emph{exchange subgraph} the edges on which some goods is actually purchased is entirely characterized. This graph is in fact made of several connected components called trading component: all sellers and all buyers receive the same wealth within a component (given by the ratio of their numbers). One can extract these components recursively by searching for the set of buyers U with minimal |U|/|N(U)| ratio (in other words, the most constricted set of buyers). Since by definition no subset within this one is more constricted, one can prove that sellers will end with equal wealth within it. After removing this subset, the next most constricted set can be extracted from the remaining graph to create a recursive sequence. Since these subsets are less and less constricted, sellers will have no better opportunity that when they were chosen for the first time. Buyers, on the other hand, have simply no other opportunity at all. Hence it is the equilibrium.

While it depends in general on the the value of α, one can then show that Nash equilibrium can only be of very specific types, as shown below, where we denote by (l,k) a trading component containing l buyers and k sellers.

Possible Nash Equilibria of a Network formation game for purchase market:

type                (buyer,seller) composition of trading components 

perfect matching    (1,1)

star forest         (1,k) (1,k+1) (l,1) (l+1,1) 

quasi balanced      (k-1,k) (k,k+1) (k,k-1) (k+1,k) 

Under the following necessary condition on α:

Note that perfect matching and the star forest all have exactly n edges, they hence maximize the total utility of this system, while in quasi balanced network, much more edges are needed (which is intuitively in accordance with the fact that α needs necessarily to be small). Perfect matching and quasi balanced trading components have minimum price variation. On the other hand, the star forest is extremely inegalitarian, with a few buyers and sellers receiving a very good deal.

Elastic supply: Firm competition with unequal access to market

Quick review of Bertrand competition

We have already seen that demand is "elastic", as setting prices for goods effectively remove buyers from the system. More generally, in a model of firm competition, supply is also elastic. It is typically not decided in advance as in our previous models of "sellers" but it is generally a byproduct of the demand and its sensitivity to price variations. In other words, supply is usually strategic assuming that producing a new unit of goods has a given marginal price.

Bertrand competition for firms with unequal customer access

General model of Bertrand competition:

M. Byford, “A constrained coalitional approach to price formation,” Available at SSRN 1004403, 2009.

Main contributions:

Captive markets

C. L. Guzmán, “Price Competition on Network,” working paper, 2011.

M. Babaioff, B. Lucier, and N. Nisan, “Bertrand networks,” presented at the EC ‘13: Proceedings of the fourteenth ACM conference on Electronic commerce, 2013.

This paper is a very broad generalization of the result from the previous ones.

Main contributions:

Written with StackEdit.