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:
- Elasticity of the supply: Is the amounts of goods to allocate fixed in advance, or can they be produced by a firm? Are goods made of indivisible unit (i.e. a house) or infinitely divisible amount (i.e. electricity, services).
- Elasticity of the demand: In general all demand curve satisfies a monotonous and diminishing return property. As an individual, the utility you receive never decreases as you are allocated more goods, and the additional utility you extract from the same quantity is a non-increasing function of what you already recieve.
But is your demand fixed (you need only one good and no more), or is it more elastic? Are you ever satiated?
- Competition among firms: Is there none (the supply firm is hence a monopoly)? Are we considering any situation of competition among arbitrary firms? Are we limiting our analysis to a simple case (two or a small number of competing firms)?
- Ability to discriminate: In a public price posting scenario, the firm is only able to offer all customers a given fixed price. Otherwise, in some situation, price discrimination is possible.
- Endogenous/Exogenous networks: Sometimes the networks that define constraints or dependencies in the system is fixed (by geography, social affinity). In other cases, agents are able to act also on the network, typically by building a link up to a connection cost.
- What is the objective: Is the goal of the analysis to predict under some model how profit maximizing agents would behave? Or is the goal to relate this outcome to an ideal allocation of goods, treating price as a mean to achieve coordination?
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:
- Supply-Demand Access Restriction: In this first line of work, the network that connect some agents together represents constraints on the ability to trade. This ought to generalize the assumption that all buyers and suppliers or agents interact with each other through a single centralized marketplace. Consumption and production or ownership of goods are still defined separately for each agent according to its individual goal, but they depend on each others through these constraints that may affect prices, revenue and quantity exchange.
- Socially Dependent Consumption: In this second line of work, the behavior of agents depend on each other as they are affected indirectly by the consumption of some others (i.e. their “neighbors or friends”). A first classical lines of work considered the (global) network effect, in which each consumer is affected by the behavior of all (a particular goods may be especially valuable if it allows compatibility with many other people). Various goods exhibit a more subtle local network effect, in which each agent is only directly affected through her neighbors, although the final outcome is typically indirectly affected by all.
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
- In a matching market, consumers who need one undivisible good access a market where each seller has one good to sell. Background on matching market can be found in Easley-Kleinberg Chap.10 and multiple references, including a recent survey with lots of more recent results.
A. Abdulkadiroglu and T. Sönmez, “Matching markets: Theory and practice,” in Advances in Economics and Econometrics, vol. 1, no. 1, D. Acemoglu, M. Arellano, and E. Dekel, Eds. Cambridge University Press, 2013, pp. 3–47.
(NB: This reference was also the contents of a tutorial at EC '13.)
- Roughly speaking matching markets are more generally a subclass of assignment game (analyzed in one of founding papers of cooperative game theory, L. S. Shapley and M. Shubik, “The assignment game I: The core,” International Journal of Game Theory, vol. 1, no. 1, pp. 111–130, 1971.). This game analyzes pairwise stable matching where a set of goods are to be allocated to a set of players that value them differently.
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:
- [KT2001] Proposes an ascending auctions based on clearable set of sellers (a set C of sellers for which an allocation of the goods satisfy all buyers connected to them L(c), with the exception of the ones that already dropped from the auctions). Show that (Prop A1): (i) Dropping each auction at the true value vi of a buyer bi is an equilibrium after removing weakly dominated strategy. (Prop 1) (ii) the allocation obtained is efficient and (Prop 1) (iii) the allocation and price are pairwise stable.
- [KT2001] Show that if the network is endogenous as links are built by buyers, it leads to an efficient outcome (Prop 2). When sellers make individual strategic decisions about investing in capacity that allow each of them to produce one unit of indivisible good. But the efficient network is not always an equilibrium outcome.
Analysis of the ascending auctions:
First, We first recall the Marriage theorem, a combinatorial result on the existence of allocation that satisfies all buyers with network constraint. According to this result, there exists an allocation from sellers S so that every buyer in B receives a good if and only if: For all subset B′⊆B, the set B′ of buyers is collectively connected to at least |B′| sellers (i.e. for all B′⊆B, |L(B′)|≥|B′|). It is obviously a necessary condition (otherwise a constricted set exists), and it is also sufficient.
Second, we observe the union closeness of clearable sets of sellers (i.e. sets C such that there exists an allocation of goods from C that assigns a good to every connected buyer L(c)): if C1 and C2 are clearable, so is C1∪C2. Note that this implies that we can build at anytime a maximal clearable sets of sellers that contain all of them.
Why is that the case? We define L′2=L(C1∪C2)∩L(C1)c and C′2=C2∩Cc1. L(C1∪C2) contains L(C1), buyers that are connected to C1, and we can assign goods from sellers in C1 to satisfy all of those. All other buyers that remain to be included in L (i.e. the set L′2) by definition are not connected to anyone in C1, so they have to be connected only to sellers in C′2. Moreover, if we consider any subset of k of them, they have to be connected to k sellers within C′2. Otherwise, it would form a constricted subset that would also be a constricted subset of C2, which is impossible as C2 is clearable. The marriage theorem proves there exists an allocation to all buyers in L′2 from sellers in C′2. This completes the result.
Equipped with these definitions, we can describe the uniform ascending auctions as follows: There is an auction for each seller, (i) buyers are only allowed to exit a seller’s auction at anytime (with no possible re-entry), (ii) sellers all maintain a common price p initially set to 0 (or, which is equivalent overall, to a reserve price). Starting from the complete network, if a clearable set exists, we assign good for free to buyers in the maximal clearable subset. All other subsets of sellers are not clearable (i.e., see a larger demand than the amount they can offer) and will actively participate in the auction process.
We assume that buyers all have different valuations vi for the good, and that they drop from the auction as soon as the price reaches their valuation (they are indifferent to that choice anyway).
Proof that dropping auction at one’s valuation is a weakly dominant strategy.
Assume i decides instead to exit one auction of a seller j at price p<vi. If i receives no good, then it cannot strictly do better. Otherwise, we assume it receives it from a seller h at price p′.
Let S contains sellers clearing their auction for price at most p′, it contains h, and the associated set of buyers L(S) is composed of two sets: L1 contains all buyers that obtain a good at price at most p′ (and that should be from sellers in S), including i. L2 contains those that exited the bidding for a price at a price at most p′, which means their valuation are below p′.
Now, If i did not exit the auction of j, we will have a different set of auctions with one more edge. But since the allocation above from S to L1 satisfies all buyers in L(S) that have value at most p′, it implies that the set S clears at a price below p′ in these auctions as well. Since i has value above p′ it will receive a good in this auction for a price no more than p′.
Finally, if i exits multiple auctions at price p1≤...≤pk<vi. We can apply the argument backward to prove that without the last move, everything else being the same, i would receive the good at no larger price without exiting the last set of auctions at price pk. It would hence receive the good with no added cost if i did not exit any auction. This proves the result.
Similarly, if we consider any set of buyers following arbitrary strategy to exit auction before their valuation (or staying beyond), let us order them by the price at which they exit. The one that exits last affects no other buyer, and hence it is not better than if he follows from there the truthful strategy. Walking backward, we can eliminate all these strategies except the one where all buyers bid truthfully.
Proof that the auction results in an efficient allocation
Step 1: we have to prove the following property. Let us consider a set of sellers and the associated buyers connected to them (S,L(S)) so that no clearable subset of sellers exist (i.e. all subsets of sellers see a higher demand than they offer). Then we claim that by reducing the demand as we eliminate buyers from L(S), the first time a clearable subset C of sellers appear, then it must have a demand equal to its size.
Formally we assume there exist B⊊L(S) such that (S,B) admits a clearable subset C of sellers, and b∉B such that (S,B∪{b}) has no clearable subset of sellers. In that case, it must be that |L(C)∩B|=|C|.
Why is this true? For ease of notation, for any subset of buyers B and subset of sellers C, we denote LB(C)=L(C)∩B (i.e. the set of buyers from B that are connected to C). An allocation exists of goods from C that satisfy all buyers in LB(C) but not LB∪{b}(C). The later implies that b is connected to a seller in C, and also that a constricted set of buyers B′ exists in LB(C)∪{b}. B′ must contain b or it would be satisfiable, and it cannot be only {b} since b is connected, so B′={b,b1,…,bk} where k≥1 and bi∈LB(C). An allocation exists from sellers s1,…,sk in C to all b1,…,bk, and |B′|=k+1, so B′ can only be constricted if nodes in B′ are connected only to those k sellers. We now claim that there are not any sellers remaining in C after this k are removed. Otherwise, since neither b nor b1,…,bk are connected to the remaining ones, they would form a clearable subset of B∪{b}. This proves the theorem as we associated a buyer with each seller.
Step2: Let us now analyze the process of the auctions. In the first phase, the maximum clearable set of sellers C0 is considered and goods are allocated to all buyers B0 connected with them. Afterwards, all subset of sellers are not clearable. The price of the good increases, which lead some buyers to drop and exit the system. As a consequence, a new maximal clearable set of sellers C1 appears, which serve buyers in B1. Once the good from this set are allocated the process resumes, C2 appears etc. until all sellers are cleared after k steps. We make two important claims:
Claim1: Whenever a clearable set appears in the auction, each seller of this set provides a good to a buyer. In other words |Bi|=|Ci|.
Claim2: For any buyer b connected to a seller in Ci, one of the following is true: either (i) b∈B0∪…∪Bi (b was chosen by the auction to receive a good in round i or earlier), or (ii) vb<vi where
vi=min{vb′|b′∈Bi∪…∪Bk}.
Why is this true? Claim1 follows directly from Step1 as once the clearable set is removed with all associated buyers, the process resumes where no clearable set exists. Buyers are removed one by one according to their value, and the last one removed before the first clearable set of sellers appears play the role of b in Step 1. Claim2 follows from the mechanism of the auctions. If b is connected with a seller in Ci but does not satisfy (i) it has to exit the system by dropping all auctions before the clearable set appears, which means that its value is below any value in Bi and later.
Step3: We are now ready to show that the total value in the allocation ∑i≥1∑b∈Bivb is larger than any feasible allocation a:S→B of goods to buyers ∑i≥1∑s∈Sva(s). Let Ai=a(Ci) denotes the set of buyers receiving goods from sellers in Ci in the new allocation.
To prove the result, it is sufficient to show that for any i there exists an injective function f from
A0∪…∪Ai to B0∪…∪Bi such that
va≤vf(a), and v(a)≤vi whenever a∉B0∪…∪Bi,
Note that it is possible for i=0 since B0=L(C0) and all nodes in A0 are connected to at least one seller in C0. Assuming such a function exists for i−1, how are we to associate every a∈Ai to a different node b∈Bi such that va≤vb? We first observe that a receives a good from a seller in Ci in the new allocation, hence it is connected to Ci and must satisfy (i) or (ii) in Claim2 above. Three cases are possible
- If a satisfies (i) because a∈Bi, then we can simply define f(a)=a,
- if a satisfies (i) because a∈Bj for j≤i−1, then there may already exists a node a′∈Aj′ for j′≤i−1 such that f(a′)=a for f defined at previous step, but we can redefine a function that switch these two images, maps a to itself and a′ with a node chosen in Bi. We have va′≤vi−1 by recurrence since a′ was not in any B0∪…∪Bi−1.
so it would satisfy va′≤vb for any b∈Bi.
- Finally, if a satisfies (ii), then va≤vb for any b∈Bi.
In summary, we can construct this function for i since the allocation has at most |Ci| nodes in Ai, and every a∈Ai will use exactly one node in Bi to redefine the function.
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:
- Formalize the notion of a stable (price,allocation), that satisfies individual rationality and pairwise stability, and prove that it always result in an allocation maximizing social welfare. In other words, (p,a), where p is a price vector and a an allocation, is competitive if buyers buy from the cheaper available vendor if they value the good more, otherwise do not buy, and remaining vendors have null price. This always implies that a is efficient (i.e. no other allocations produce more utility in total).
- Show that all prices such that (p,a) is competitive follows pmin≤p≤pmax, where the extremal prices pmin, pmax are respectively the best and worst for buyers.
- Formalizes that price in such system is a sort of “alternative offer” topology that is associated with any efficient allocation a. Show that pmin and pmax can be written as value from opportunity paths which are constructed by alternating edges connecting seller-buyer that trades and those who do not trade. This captures the various aspects of supply stealing and supply freeing which govern the equilibrium of the system when an edge is added.
- Shows that the addition of an edge between b~ and s~ always improves the payoff for these two agents. (This holds as long as we operate at price q⋅pmin+(1−q)pmax for a fixed q∈[0;1]). On the other hand, the effect on other agents is not so clear. Among results
- If a buyer b is connected to b~ and not s~, then it is better off with the new edge (supply freeing), if this is the opposite it is hurt (supply stealing). A similar result exists for a seller
- If a buyer b is directly linked to s~, then the new link hurts, but if b is only linked to sellers that are all linked to b~, then it benefits from the link.
- Similarly, adding sellers (together with their edges) is always beneficial to buyers and detrimental to sellers already present.
More precisely:
For a given allocation a of goods we say that an opportunity path exists from s to b, that we denote s⇝b if we can draw a path s=s1−b2→s2−b3→s3−…−sn−1−bn=b, where s−b denotes that s and b are connected but do not exchange goods, and b→s denotes that b receives a good from s in a. An immediate consequence of the definition is that any price p that implements a stable allocation must have: p1≥p2≥...≥pn−1. Intuitively, if pi<pi+1, the buyer bi+1 that has access to both sellers will not choose to buy the good from si+1 and the allocation is not stable.
In addition, if bn ends up not receiving a good in the allocation, it has to be that no seller proposes a good at a price strictly below its valuation. Hence we have pn−1≥vn which also implies p1≥vn.
The main result is a converse statement: Opportunity paths to unsatisfied buyers are not just defining a lower bound on the price, this lower bound is attained on one of them. In other words, we have pmins=max{vb|s⇝b,b∉a(S)}. Based on an allocation a, we can begin all opportunity paths from a sellers starting with buyers it does not serve. If we find a buyer that is not satisfied we consider its values, otherwise, we follow to the associated seller of this buyer and recursively continue. When we have found all of these values, the maximum indicates the price of this good.
A similar results exists on pmax, when considering opportunity paths build from buyers to other buyers.
- Most of the further results on modification of the graph of buyer-seller are consequences of these definitions, since adding sellers, buyers and edges can be understood as the opening of new potential paths that can be opportunity paths.
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,
This paper considers a case where all buyers have value 1 for the good, and a multiple-slot bargaining process in which, if a seller-buyer pair trades at time t, the seller gets δt⋅p and the buyer δt⋅(1−p). Sellers and Buyers alternate to make offer the other can accept or reject, while time counts as some forms of utility decay.
For a pair in isolation, this corresponds to an instance of an Alternate Bargaining Offers in infinite time. The solution to this infinite horizon game was given in
A. Rubinstein, “Perfect equilibrium in a bargaining model,” Econometrica: Journal of the Econometric Society, pp. 97–109, 1982.
essentially by observing that if player 1 proposes (x,δy) and accepts no offer worse than (δx,y), while player 2 accepts no offer worse than (x,δy), and proposes (δx,y), then all threats are credible. Player 1's threat to reject anything less than δx is quite credible, since he would receive that in his subsequent offer. Similarly, player 2's request for δy is appropriate, since he would receive that in his next subsequent offer. In other words, both are indifferent and know the other will be indifferent at every period.
This implies the price will be set to p=11+δ. In this case, the seller gets δt1+δ and the buyer δt+11+δ.
The main result of this paper is that bargaining on an arbitrary network will not corresponds to the reference solution as soon as the graph is of a mixed types (some parts have a surplus of sellers, other a surplus of buyers).
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:
- Proposes a (bid,ask) price setting game primarily played by traders. Traders interact with sellers through bid offers (proposing to buy from a seller at a given price) and with buyers through ask offers (state to the buyer what they ask in return), similar to stock trading. Since buyers and sellers behave in a simple manner (they simply choose among best possible offers they receive, decided in an omniscient way by the market makers), the crux of the model is how do intermediaries decides to set up their ask-bid prices.
- Principal assumptions:
- (A1) Traders only connect to sellers and buyers and not to other traders
- (A2) Values of the good for sellers and buyers are publicly known
- (A3) Each trader can price discriminate and offers bid,ask prices that differ for various sellers and buyers.
- [Thm 2.1] Every equilibrium (subgame-perfect Nash eq.) allocates good efficiently, as an omniscient market maker maximizing the value created by exchange. This also maximizes the sum of payoff for sellers-traders-buyers.
- [Thm 2.2] For any socially optimal trade, an equilibrium exists and it has no crossing (i.e for any trader, ask(t,i,j) - bid(t,i,j)≥0.
[Thm 2.3] A trader t makes a positive profit in at least one equilibrium if and only if one of its adjacent edge (linking t to a seller or a buyer) is essential for social welfare (i.e. removing this edge alone decreases the value created by the optimal allocation).
All proofs are obtained by having equilibrium prices emerging from the dual of a linear program representing potential flows of goods in this network. This can be seen more or less as a generalization of Shapley Shubik approach to solve assignment game.
Some implications of trading network analysis:
- While the total payoff is maximize and constant, this payoff is divided among different kind of players in quite an extreme way: Typically, sellers and buyers receive nothing in case an intermediary is their unique chance to trade, but intermediaries see no revenue at all in many settings. As seen above, there exists an equilibrium where an intermediary makes a positive profit only of this intermediary possesses an “essential edge” (one connection to a buyer or seller such that, when removed, the social welfare of goods that can flow is affected). Note that an intermediary might be important as a whole but if its edges are not separately important by themselves, she might not receive any revenue.
- As shown by results above, position in the network has a critical role in revenues obtained. Adding or removing edges in this model leads to seemingly counter-intuitive behavior (it might remove a bottleneck that takes a good from a buyer to give it to another one, typically with higher value), but they can be understood in social welfare. The networks is supposed to be fixed, but in general, being able to make a profit might encourage traders to build new connections.
- The single item second price auction can be emulated simply in this model, by a set of traders associated with each bidders.
- Values are public knowledge and, since there is no clear auction to build the solutions, it's not entirely clear that the whole mechanisms can be made truthful. This is the main restriction needed in order to account for intermediaries in such constrained matching markets.
In particular, it might be more complicated in stock trading where people do their best to guess values of others (or avoid it by dark pool etc.).
It is also interesting to discuss the potential generalization of these results.
- These results apply even if each seller and buyer has different preferences over the goods (i.e. the valuation is different depending on which seller sends goods to which buyers). The model is quite general as it includes how buyers care where they get their good from but also potentially how seller care who receives their goods. As an example, in a job assignment markets, boths firms and people have specific preferences.
In another round of generalization, it’s possible to account for preferred trader (with the value depending on where the transactions was made from, even between the same seller and buyers) and obtain the same result. This accounts for a trader’s transaction costs, is also some elementary forms of production (since the trader transformation could be seen as a refinement of the seller’s goods).
For each of these, the same results can be shown (existence of intermediary prices and proof that they achieve social welfare, with intermediaries with essential edge being rewarded).
Overview of the proof:
Let us consider the situation faced by a trader t that plans on shipping a good from s to b. Doing that creates a social surplus vb−vs, which is generally positive. The choice of bid(t,s) and ask(t,b) will determine if this occurs and how this surplus is shared in various profit. In general
- a buyer sees a profit xb=vb−ask(t′,b) whenever it trades with any trader t′, 0 otherwise.
- a seller sees a profit xs=bid(t′,s)−vs whenever it trades with t′, and 0 otherwise.
- the trader extract a profit xt=ask(t,b)−bid(t,s) in the transaction.
Note that if t trades with b and s, the trader’s profit can be rewritten as xt=vb−vs−xb−xs. This intuitively makes sense; whatever profit is given to the trader is the remaining of the social surplus once profits from others are removed. Note also that if vb−vs−xb−xs>0, then xt is guaranteed a profit at least equal to this by trading on this edge. So we have xt≥vb−vs−xb−xs in general (the same equality is trivially true if the RHS is null or negative).
Like many optimization of transport and supply-demand, the core is to write two Linear Programming that will be related to (1) the social optimization of goods being transported, and (2) the profit maximizing behavior of each agent (in this case, mostly the traders).
LP1 is defined on the flow variables fe for every e=(s,b) where s and b have at least one trader adjacent to both. It is written as:
max∑e=(s,b)fe⋅(vb−vs)such that∀e,fe≥0,∀s,∑e=(s,.)fe≤1,∀b,∑e=(.,b)fe≤1.
One sees directly that this solution to this problem would create the best possible outcome in terms of maximizing the social surplus.
LP2 is more subtle and novel. It is written as if instead of setting the prices of traders, one would directly define the profits x of all agents, be it a seller, a buyers or a trader. It is generally a bit more complex, but can be written simply whenever all traders t are pair trader (they are connected to a single seller s and single buyer b, that we write t=(s,b)).
min∑i∈S∪B∪Txisuch that∀i,xi≥0,∀t=(s,b),xt≥(vb−xb)−(vs+xs)=(vb−vs)−xs−xs.
The first inequality is quite expected: no agent (no matter of what type) would ever engage in a trading that would create a negative profit. The last inequality may be rewritten xt+xs+xb≥vb−vs and simply states that a set tuple of seller-buyer-trader should collectively receive at least what the surplus of the transaction they make possible would create. If that was not the case, the trader would be able to make a deviation and generate a positive profit, as opposed to none. In other words, one directly sees that an equilibrium of the game (in terms of price set by traders etc.) has to be a feasible solution to this particular problem. The final choice that seems somewhat arbitrary is why is this second maximization problem minimizing the total sum of profit. There is no immediate concrete interpretation for that; but a fundamental consequence of choosing this objective is that with this choice LP2 becomes almost exactly the dual of LP1. To be exact, it is the dual of LP1 when one also includes the inequality ∀t=e=(s,b),ft≤1. Adding this inequality, when all traders are pair traders, affect in no way the solution of the problem.
Once this duality result is proved. The remaining of the proof derives from general duality property and its interpretation in this current model.
First of all, if one considers an equilibrium of the game, the flows fes and profits xis associated are not only two feasible solutions of dual LP problems (LP1 and LP2), but they also satisfy the complementary slackness conditions.
- These conditions, as derived from LP1 and LP2, can be written as
xs⋅(1−∑e=(s,.)fe)=0, xb⋅(1−∑e=(.,b)fe)=0, and xt⋅(1−∑e=tfe)=0, and fe=t=(s,b)⋅((vb−vs)−(xb+xs+xt))=0. The three first simply follow from the fact that no profit is made by anyone unless they trade, and the last one stipulates that if trades is made by t=(s,b), the profit each agents made in the process sums to the social surplus.
- The duality theorem implies that the two solutions are optimal for their respective problem. Hence, any equilibrium builds a flow that is optimal.
Second, one can always build an equilibrium of the games for any socially optimal flow, typically by considering the associated LP2 and computing the equilibrium’s profit first. We can then arbitrarily fixed ask/bid for all traders to i seller/buyer so the proposition is exactly proposing this profit to i.
- As a consequence of the complementary slackness condition, the proposed profit to i will necessarily be null if no trading currently occurs in this solution that involves i . Agent i is at best given an offer to participate for zero profit. A seller, a buyer or a trader will hence not benefit from engaging in new trade that are not made.
- Any buyer/seller seeing one or multiple identical offers, will not benefit from deviating from the solution proposed.
- Traders make all identical offers and, hence, they cannot change their bid/ask and extract more profits when they see any competition. On the other hand, when no competition occurs, they have one more possible deviation. Nothing prevents a solution to LP2 to potentially gives a positive profit to a seller/buyer even if it is connected to only one trader. But in that case, closer examination reveals that xt+xi always appear together as a sum in all the objectives and constraints. We can then modify the solution to have x′t=xt+xi and still have an optimal solution. When this is done for all traders,agents in this situation, traders have no more possible profitable deviation.
Third, one can connect an individual’s profit with its contribution to social outcome. Let us assume that an equilibrium exists with xt>0. Let us define LP2’ by reseting the value of the edge (s,b), from (vb−vs) to (vb−vs−xt). Considering all xi the same except for xt being set to zero provides an optimal solution to LP2’, which is hence also a optimal solution for LP1’ obtained with the same new weight on edges. Since the social welfare in the later has diminished by xt, this implies that no feasible solution to the original LP1 exists that would NOT used this edge and be within less than xt of the optimal. So xt receives at most the difference this trader makes possible in the social welfare. Inversely, if removing t makes a difference in the social welfare by w>0, it means t is used in the flow and still is when the value of the edges is less by a w amount. We can then build an optimal dual solution from it by adding w to the profit of t.
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 model includes a finite number of goods 1,2,…,k that are infinitely divisible, and a finite population of consumers who receives each a utility function ui(xi,1,…,xi,k) depending on the quantity that they possess of all goods. Each consumer initially comes with an endowement that contains an amount of goods, and hence she initially enjoys some utility for it. She may also find it advantageous to get rid of some of these goods in exchange of some others. The main question posed is whether these goods can overall be redistributed so that users enjoy a better utility.
- Arrow and Debreu’s main result is existential, it shows that under general conditions this system admits an equilibrium: A price for each good is fixed, all players initially sell entirely their endowement to a market maker in exchange of money, they buy the best possible sets of goods they each can afford as if goods were instantly and infinitely available, but nevertheless they end up consuming collectively exactly the resources that are available. In other words, some redistribution is possible: there exists an equilibrium which is a set of prices (p1,…,pk) and consumption plans (xi,j)i,j that is \emph{individually rational} (a user’s consumption plans is optimal among all the plans that satisfy her budget) and \emph{market-clearing} (for each good, summing all users’ consumption plans and users’ endowement result in the same quantity).
- One could also reason about the absolute best redistribution of goods that maximizes the total utility of this set of consumers, but such \emph{optimal} assignment has no meaning here since it’s defined independently of the initial endowment of each player. You can easily create a case where one player initially possesses all the goods and is allocated none in the socially optimum allocation.
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.
- It turned out that the existence of an equilibrium in this case is always easy to ensure. First, let us virtually redefine all k goods as n⋅k separate goods depending on the origin of the goods. If we redefine the utility function as only taking positive value for goods produced by neighbors, and otherwise be null, we can deduce the existence of a graphical equilibrium in which \emph{all markets locally clear} from the general existence result.
Two technicalities arise: the utility are not strictly increasing, and not all users have initially a positive endowement of all goods. This problem can be solved by leveraging more general result on the existence of a quasi equilibrium (one in which users who ends up initially possessing only goods with null prices are not bounded to be rational), and proving that all quasi equilibria are real equilibria. This last proof uses an interesting “propagation argument”: a user who possesses a good of positive price necessarily spends its wealth, hence one of her neighbor also possesses a good of positive price and by rationality no other proposes the same good for a null price. This shows that an equilibrium exists in any connected economy. This argument fails if not all players possess a little bit of each good.
This paper goes beyond an existential result: it shows based on previous work
X. Deng, C. Papadimitriou, and S. Safra, “On the complexity of equilibria,” presented at the STOC '02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, 2002.
that an iterative algorithm which resembles dynamic programming on a grid of price and consumption plan allows, for a given number of goods k to compute an ε-equilibrium in a time polynomial in n (number of consumers), 1/ε (accuracy), ln(e+/e−) (max imbalance of initial envowement over any goods), and d (a constant limiting the increase of utility with goods, typically fixed for polynomial ui).
This result only applies to complete graph, and trees with a fixed maximal degree. The latter case is not an application of the general reduction using nk goods, but it necessitates to exploit the graphical structure.
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.
The existence of an equilibrium is not difficult to establish as, just life for exchange market, one can build an equivalent market with no graphical constraints: we can imagine that to create virtual goods representing the same good as sold by different sellers. For a given buyer b, the good (j,s) ``for good j sold by s'' is a perfect substitute for good j if b and s are connected, otherwise it provides b with zero utility. This equivalent allows also to reuse a previous algorithm to build the equilibrium for linear utility via an ascending algorithm exploiting primal dual variables in
N. R. Devanur, C. H. Papadimitriou, A. Saberi, and V. V. Vazirani, “Market equilibrium via a primal-dual-type algorithm,” presented at the Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on, 2002, pp. 389–395.
This algorithm starts from zero price, it iteratively increases the price vector while ensuring the following saturation property: buyers have enough money to clear the markets while only purchasing goods with maximum marginal utility (\ie defined as ui,jpj where ui,j is the linear coefficient of the utility function of i for good j).
The main result on graphical purchase market in the above paper, beyond their existence, is that one can bound equilibrium prices and hence wealth received by sellers with another “propagation” argument. First, let us define a subset of the graph of seller-buyer to be seller complete if all included buyers conserve all their purchase options (if a buyer is in the set, then all her partner sellers are). One can see that the market defined by this economy creates equilibrium prices that are all non-larger than the actual overall equilibrium prices. This can be seen by setting all other buyers cash to be 0, computing the equilibrium prices and observing that this is a possible starting point of the ascending algorithm above for the original economy. This is also intuitive because seller see no diminution in their purchasing options, hence they should have a better deal. Similarly, a buyer complete set, produces a lower bound of the original equilibrium price.
One can bound price and revenue using immediate neighborhood of a nodes such as its degree. Even better, starting from a buyer or a seller, one can include all nodes at distance 1,2,… and creates an alternating sequences of prices that bound from above and below the price or revenue for this buyer in the complete economy. It is numerically shown to be increasingly accurate as distance increases. In general, simulations show that degree and price of sellers have similar distribution, but one is not a predictor for the other since it merely matters how many nodes a seller can exploit due to poor competition. For a statistical model resembling preferential attachment in bipartite graph, the imbalance of price in function of the topology can be derived (although the rigourous proof remains to be done).
Another interesting result is that in a simple symmetric case of one good with uniform cash and endowment, price variation occurs if and only if there is no perfect matching in the underlying graph. First, if a perfect matching exists, setting price uniformly to 1 and purchase plans according to this matching trivially provide an equilibrium: all local goods are purchased and no better deal can possibly be found. Another more complicated proof\footnote{which is strangely the one that was initially proposed} of this same fact use the converse: With price variations, it is easy to build a constricted set of sellers (\ie a subset S of sellers such that |N(S)|<|S|) by considering all sellers with price ps<1, or one made of buyers by considering all buyers that purchases at price pb>1. A perfect matching proves in particular trivially that no constricted set exists and hence, that such price variation is impossible. Finally, if no perfect matching exists, then from the celebrated matching theorem, a constricted set exists in the bipartite graph: without loss of generality we can assume that it is a constricted set of sellers. In that case, since all goods from this seller must be purchased by some of their neighbors (and those may not even spend their entire cash on these sellers) they cannot possibly sell it at equilibrium for a nominal price.
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 α:
- for perfect matching:
0≤α≤1
- for star forest: 1−1max(k+1,l+1)≤α≤1
- for quasi balanced:
1−min(k−1k,kk+1)≤α≤1k
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.
- In a classic monopolist situation in which a single firm can produce a good under a marginal production cost c and sees a demand for it according to a distribution of value F, that is assumed known, the firm would maximize its profit by setting the price p that maximizes:
F(p)⋅(p−c).
When two or more firms compete for customers, and each of them still retains some effect on the prices (also called market power), this situation is called a duopoly or an oligopoly. There are various models of interaction. Cournot competition and Bertrand competition (a more agressive version) are fundamental examples. They differ in their prediction radically.
In Cournot’s competition, the two firms somewhat already committed to sell at a common price, but they adapt their production so that, given the other player do the same, the overall revenue is maximum to each. In Bertrand competition, a firm that could unilaterally change its price to receive additional demand will do it.
Cournot competition ends up stating that both (or several) firms make a profit over recovering their marginal cost, whereas the aggressivity of Bertrand competition predicts that no sustainable profit exists, as the only equilibrium is one where both firms charge their marginal cost.
Bertrand competition for firms with unequal customer access
General model of Bertrand competition:
- Firms f_1,f_2,\ldots have access to various ``markets'' which denotes how many customers can buy from each of them. Let cS denotes the number of customers who can buy from a subset S of firms.
As an example, take two firms, with c1 customers that can access f1, c2 accessing f2 and c1,2 able to access both f1 and f2.
- Consumers wish to purchase one indivisible goods and have a value v that follows from a (known) distribution F. F(p) is the probability that a customer values the good more than p.
- Game is played in two stage: Stage 1: firms announce public prices (with or without discrimination among various markets). Stage 2: consumers make a purchase from the lowest price they see p with a probability F(p). (Note that in stage 1 the firms are allowed to use a mixed strategy where a randomized price pf is chosen with probability function μf.
- A firm f individually solves the following problem:
maxμfE⎡⎣⎢⎢pfF(pf)⎛⎝⎜⎜cf+∑S,f∈ScS∏f′∈S,f′≠f(1−μf′(pf))⎞⎠⎟⎟⎤⎦⎥⎥
for instance in the example above
maxμ1E[p1F(p1)(c1+c1,2(1−μ2(pf)))]
M. Byford, “A constrained coalitional approach to price formation,” Available at SSRN 1004403, 2009.
Main contributions:
- Proves (among others) a general condition for perfect competition where firms always post price equal to marginal cost: If a subset S of firms satisfies that no customer sees a unique firm within S, then for all firm in S the only mixed strategy that is an equilibrium requires them to post at marginal price.
- This automatically shows that without captive customers (who can only access a single market), the problem has no other equilibrium.
- Note that if S1 and S2 satisfies the property above, so is S1∪S2. Hence, we can in any graph consider the union of all these sets and remove these firms and all their customers from the topology, since none of these markets could be used for profit by another firm.
Captive markets
C. L. Guzmán, “Price Competition on Network,” working paper, 2011.
- Introduce a situation with captive customers, focusing mostly on the case of 2 firms with captive customers and a common market. Shows that monopolistic is the only situation with a pure Nash Equilibrium (it does not exists as soon as c1>0 and c1,2>0).
Show that the unique equilibrium of the game is mixed. Assuming C1>C2, firm 1’s payoff remains that of the captive market (essentially, the price is set so that its gain on the mobile market exactly offset the loss on the captive market), firm 2’s payoff is between its own monopoly (which could be zero or positive depending on c2) and the revenue of firm1.
More formally, the profit xj of firm j is x1=pMF(pM)c1 where pM denotes the monopolistic price. and x2=x1⋅c2+c1,2c1+c1,2.
The distribution of price is known, with firm 1 choosing with some positive probability to charge the monopoly price.
The possibility to price discriminate (firm 1 and 2 posting different price depending on the market) is individually better for a firm (it would be stronger if it is the only one that can do it), but if both discriminate, any additional profit on the mobile market is lost. Firm 1 is indifferent to this, but firm 2 would be hurt.
One can generalize the results to a series of captive markets (w.l.o.g., ordered such that c1≥c2≥...≥ck, and one global market cg). This situation somewhat reduces to the equilibrium above. The smallest firm is like firm 2, it gets additional revenue from the global market, the second smallest firm k−1 is somewhat indifferent (it gained what it lost) as in the same situation of firm 1 above. All others face a larger opportunity cost to enter the global market, and hence they do not deviate from their captive equilibria. Note that this only holds if ck−2>ck−1, otherwise the situation gets really complicated.
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:
- It focuses on a case where markets are either connected to 1 or 2 firms. This is represented in a firm-graph, with edges’s weights corresponding to the sum of the sizes of all the markets a pair of firms share. A more general model based on a hyper-graph can be defined (with utility as done above). This paper assumes for simplicity that all buyers have value 1, so monopolistic price is set to 1, as consumers always pick a good for any firm with price up to this value.
A broad existential result: A mixed equilibrium always exists, no pure equilibrium exists unless the network is trivial (i.e. as soon as the network is connected with at least two nodes and one has a captive market). Some properties are also established: no strategy put mass in atomic price except for p=1, all firms have positive utility.
This is very much a contrast with Bertrand competition: it shows that being indirectly connected to a captive market is sufficient to generate profit in any equilibrium.
- Computing and describing the equilibrium is generally very difficult. The paper presents a method that works on a tree structure when there is a unique captive market. Various results on computation of equilibrium are shown.
- Some bounds on the utility of a firm (lower bound using the distance to a captive market, upper bound using a cut from this seller to all captive markets, which goes to zero as the cut grows).
Written with StackEdit.