At the Aladdin workshop on “Web Structure and Algorithms“, Michael Kearns is giving a more detailed presentation on part of what I reported on a few weeks ago.
He’s generalizing from general equilibrium models such as Arrow-Debreu to situations where people only exchange with people they are connected to in a newtork. As an aside, Kearns said that it has only recently been shown that there is an efficient algorithm for computing equilibrium prices, DPSV 2002. (Arrow-Debreu’s famous theorem from 1954 is that such prices always exist, if a few technical conditions are satisfied.)
Assume an undirected network restricting exchange. Assume no resale. (Could encode network in goods and utilities of standard model: virtual good is a good and an initial holder; individual utility for a virtual good is 0 if no link in the graph to the holder of the good.) Can have variation in price for the same good, because people can only get the good locally. Equilibrium prices means that each consumer satisfies *all* their demand from their neighbor with lowest price– price has to be higher if that seller wouldn’t have enough to meet your demand. Result from Kakade, Kearns, and Ortiz 04: equilibria always exist, and can compute equilibria in polynomial time (# users), exp(# goods).
Today’s subject: marrying that work with preferential attachment model for buyer-seller networks. Preferential attachment means new node’s probability of attaching to an existing node is directly proportional to the current degree of the existing node, so you get a power law of degree distribution for graph nodes. Buyers who have higher degree have more choices of trading partners, so generally have more market power, but it’s even better if you have high degree to sellers who have low degree (they’ll have no choice but to sell to you at low prices). Derives theorems about wealth distribution upper bound, price variation (as number of links per person increases, get less price variation). Simulations suggest that there is a power law distribution of wealth. (Note: not hard to derive some model that leads to power law distribution of wealth. Claim for novelty/interest here is that it’s a process that comes from some notion of rational behavior of the participants. Low degree people not just giving money to neighbors with high degree. They have less market power.) Also did a behavioral experiment with students in a class, creating a few islands that were allowed to trade only within the island, but with imbalanced numbers of buyers and sellers in each island.