Economic Exchange on Networks : Economic Exchange on Networks Networked Life
CSE 112
Spring 2007
Prof. Michael Kearns
Exchange Economies : Exchange Economies Suppose there are a bunch of different goods orcommodities
wheat, milk, rice, paper, raccoon pelts, matches, grain alcohol,…
no differences or distinctions within a good: rice is rice
We may all have different initial amounts or endowments
I might have 10 sacks of rice and two raccoon pelts
you might have 6 bushels of wheat, 2 boxes of matches
etc. etc. etc.
Of course, we may want to exchange some of our goods
I can’t eat 10 sacks of rice, and I need matches to light a fire
it’s getting cold and you need raccoon mittens
etc. etc. etc.
How should we engage in exchange?
What should be the rates of exchange?
how many sacks of rice per box of matches?
These are among the oldest questions in markets and economics
Cash and Prices : Cash and Prices Suppose we introduce an abstract resource called cash
no inherent value
simply meant to facilitate trade, “encode” pairwise exchange rates
And now suppose we introduce prices in cash
i.e. rates of exchange between each “real” good and cash
e.g. a racoon pelt is worth $5.25, a box of matches $1.10
Then if we all believed in cash and the prices…
we might try to sell our initial endowments for cash
then use the cash to buy exactly what we most want
But will there really be:
others who want to buy all of our endowments? (demand)
others who will be selling what we want? (supply)
Mathematical Microeconomics : Mathematical Microeconomics Have k abstract goods or commodities g1, g2, … , gk
Have n consumers or “players”
Each player has an initial endowment e = (e1,e2,…,ek) > 0
Each consumer has their own utility function:
assigns a subjective “valuation” or utility to any amounts of the k goods
e.g. if k = 4, U(x1,x2,x3,x4) = 0.2*x1 + 0.7*x2 + 0.3*x3 + 0.5*x4
here g2 is my “favorite” good --- but it might be expensive
generally assume utility functions are insatiable
always some bundle of goods you’d prefer more
utility functions not necessarily linear, though
Market Equilibrium : Market Equilibrium Suppose we announce prices p = (p1,p2,…,pk) for the k goods
Assume consumers are rational:
they will attempt to sell their endowment e at the prices p (supply)
if successful, they will get cash e*p = e1 *p1 + e2*p2 + … + ek*pk (* = times)
with this cash, they will then attempt to purchase x = (x1,x2,…,xk) that maximizes their utility U(x) subject to their budget (demand)
example:
U(x1,x2,x3,x4) = 0.2*x1 + 0.7*x2 + 0.3*x3 + 0.5*x4
p = (1.0,0.35,0.15,2.0)
look at “bang for the buck” for each good i, wi/pi:
g1: 0.2/1.0 = 0.2; g2: 0.7/0.35 = 2.0; g3: 0.3/0.15 = 2.0; g4: 0.5/2.0 = 0.25
so we will purchase as much of g2 and/or g3 as we can subject to budget
A specific mechanism: bringing your endowments to the stage
what could go wrong? 1) stuff left on stage 2) not enough stuff on stage
Say that the prices p are an equilibrium if there are exactly enough goods to accomplish all supply and demand constraints
That is, supply exactly balances demand --- market clears
Another Phone Call from Stockholm : Another Phone Call from Stockholm Arrow and Debreu, 1954:
There is always a set of equilibrium prices!
Both won Nobel prizes in Economics
Intuition: suppose p is not an equilibrium
if there is excess demand for some good at p, raise its price
if there is excess supply for some good at p, lower its price
the famed “invisible hand” of the market
The trickiness:
changing prices can radically alter consumer preferences
not necessarily a gradual process; see “bang for the buck” argument
everyone reacting/adjusting simultaneously
utility functions may be extremely complex
May also have to specify “consumption plans”:
who buys exactly what, and from whom from whom
in previous example, may have to specify how much of g2 and g3 to buy
example:
A has Fruit Loops and Lucky Charms, but wants granola
B and C have only granola, both want either FL or LC (indifferent)
need to “coordinate” B and C to buy A’s FL and LC
Remarks : Remarks A&D 1954 a mathematical tour-de-force
resolved and clarified a hundred of years of confusion
proof related to Nash’s; (n+1)-player game with “price player”
Actual markets have been around for millennia
highly structured social systems
it’s the mathematical formalism and understanding that’s new
Model abstracts away details of price adjustment/formation process
modern financial markets
pre-currency bartering and trade
auctions
etc. etc. etc.
Model can be augmented in various way:
labor as a commodity
firms producing goods from raw materials and labor
etc. etc. etc.
“Efficient markets” ~ in equilibrium (at least at any given moment)
Network Economics : Network Economics All of what we’ve said so far assumes:
that anyone can trade (buy or sell) with anyone else
equivalently, exchange takes place on a complete network
at equilibrium, global prices must emerge due to competition
But there are many economic settings in which everyone is not free to trade with everyone else
geography:
perishability: you buy groceries from local markets so it won’t spoil
labor: you purchases services from local residents
legality:
if one were to purchase drugs, it is likely to be from an acquaintance (no centralized market possible)
peer-to-peer music exchange
politics:
there may be trade embargoes between nations
regulations:
on Wall Street, certain transactions (within a firm) may be prohibited
A Network Model of Market Economies : A Network Model of Market Economies Still begin with the same framework:
k goods or commodities
n consumers, each with their own endowments and utility functions
But now assume an undirected network dictating exchange
each vertex is a consumer
edge between i and j means they are free to engage in trade
no edge between i and j: direct exchange is forbidden
Note: can “encode” network in goods and utilities
for each raw good g and consumer i, introduce virtual good (g,i)
think of (g,i) as “good g when sold by consumer i”
consumer j will have
zero utility for (g,i) if no edge between i and j
j’s original utility for g if there is an edge between i and j
Network Equilibrium : Network Equilibrium Now prices are for each (g,i), not for just raw goods
permits the possibility of variation in price for raw goods
prices of (g,i) and (g,j) may differ
what would cause such variation at equilibrium?
Each consumer must still behave rationally
attempt to sell all of initial endowment, but only to NW neighbors
attempt to purchase goods maximizing utility within budget
will only purchase g from those neighbors with minimum price for g
Market equilibrium still always exists!
set of prices (and consumptions plans) such that:
all initial endowments sold (no excess supply)
no consumer has money left over (no excess demand)
Network Structure and Outcome : Network Structure and Outcome Q: How does the structure of a network influence the prices/wealths at equilibrium?
Need to separate asymmetries of endowments & utilities from those of NW structure
We will thus consider bipartite economies
Only two kinds of players/consumers:
“Milks”: start with 1 unit of milk, but have utility only for wheat
“Wheats” start with 1 unit of wheat, but have utility only for milk
exact form of utility functions irrelevant
Equal numbers of Milks and Wheats
Network is bipartite --- only have edges between Milks and Wheats
When will such a network have variation in prices?
Slide12 : Price = amount of the other good received = wealth
Prices at opposite ends of an edge always reciprocal: p and 1/p
Checking equilibrium conditions:
only “cheapest” edges used
supply and demand balance:
a sends 1/2 each to w and y
b sends 1 to x
c sends 1/2 each to x and z
d sends 1 to z
w sends 1 to a
x sends 2/3 to b, 1/3 to c
y sends 1 to a
z sends 1/3 to c, 2/3 to b
Some edges unused at equilibrium
exchange subgraph a d c b w x y z An Example
Slide13 : Suppose we add the single green edge
Now equilibrium has no wealth variation! a d c b w x y z
A More Complex Example : A More Complex Example Solid edges:
exchange at equilibrium
Dashed edges:
competitive but unused
Dotted edges:
non-competitive prices
Note price variation
0.33 to 2.00
Degree alone does not determine price!
e.g. B2 vs. B11
e.g. S5 vs. S14
Characterizing Price Variation : Characterizing Price Variation Consider any bipartite “Milk-Wheat” network economy
again, all endowments equal to 1.0, equal numbers of Milks and Wheats
Necessary and sufficient condition for all equilibrium prices and wealths to be equal:
network has a perfect matching as a subgraph
a pairing of Milks and Wheats such that everyone has exactly one trading partner on the other side
What if there is no perfect matching subgraph? How large can the price variation be?
For any set of vertices S on one side (e.g. Milks), let N(S) be its set of neighbors on the other side
Find the S such that |S|/|N(S)| = p is maximized (here |S| is the number of vertices in S)
Then the largest price/wealth in the network will be p, and the smallest 1/p
Intuition: When S is very large but N(S) is small, consumers in S are “captives” of their neighbors N(S)
Can actually iterate: remove S and N(S) from the network, find S’ maximizing |S’|/|N(S’)|,…
Note: When network has a perfect matching, N(S) is always at least as large as S
Note: Finding the maximizing set S may involve some computation…
Now let’s examine price variation in a statistical network formation model…
A Bipartite Economy Network Formation Model : A Bipartite Economy Network Formation Model Consider economies with only two goods: milk and wheat…
…and only two kinds of players/consumers:
Milks: start with 1 unit of milk, have utility only for wheat
Wheats: start with 1 unit of wheat, have utility only for milk
exact form of utility functions irrelevant
Wheats and Milks added incrementally in pairs at each time step
Goal: bipartite network formation model interpolating between P.A. and E-R
Probabilistically generates a bipartite graph
All edges between buyers and sellers
Each new party will have n > 1 links back to extant graph
note: n = 1 generates bipartite trees
larger n generates cyclical graphs
Distribution of new buyer’s links:
with prob. 1 – a: extant seller chosen w.r.t. preferential attachment
with prob. a: extant seller chosen uniformly at random
a = 0 is pure pref. att.; a = 1 is “like” Erdos-Renyi model
So (a,n) characterizes distribution of generative model
Slide17 : Price Variation vs. a and n n = 1 n = 2 n = 250, scatter plot Exponential decrease with a; rapid decrease with n
(Statistical) Structure and Outcome : (Statistical) Structure and Outcome Wealth distribution at equilibrium:
Power law (heavy-tailed) in networks generated by preferential attachment
Sharply peaked (Poisson) in random graphs
Price variation (max/min) at equilibrium:
Grows as a root of n in preferential attachment
None in random graphs
Random graphs result in “socialist” outcomes
Despite lack of centralized formation process
Price variation in arbitrary networks:
Characterized by presence/absence of a perfect matching
Alternately: an expansion property
Theory of random walks
Economic vs. geographic isolation
Slide19 : An Amusing Case Study
Slide20 : U.N. Comtrade Data Network
Slide21 : USA: 4.42
Germany: 4.01
Italy: 3.67
France: 3.16
Japan: 2.27 sorted equilibrium prices
Slide22 : European Union Network
Slide23 : USA: 4.42
Germany: 4.01
Italy: 3.67
France: 3.16
Japan: 2.27 sorted equilibrium prices EU: 7.18
USA: 4.50
Japan: 2.96