Quantitative Analysis of Milks and WheatsAnthony Curnes - [email protected] Advisor: Michael KearnsAbstractThe problem of modeling economic exchange on networks is one that has traditionallybeen examined through solving for an equilibrium set of prices. However, this methodfalls short in practice as human behavior often deviates from the assumptions that aregenerally made in order to predict an equilibrium. This paper examines the resultsof a study by Professor Kearns which augments equilibrium analysis by examininghuman interaction on networks through behavioral experiments.Specifically, we examine human subjects conducting exchange on various net-work structures, attempting to maximize their individual wealth. Experimenting onnetwork structures with high equilibrium wealth inequality tended to result in highwealth inequality between participants. Additionally, such networks produced lowersocial wealth than networks with low equilibrium wealth inequality.IntroductionThe evolution of the study of economic exchange on networks can be broken up intothree phases, each building on the previous one: equilibrium analysis, social networktheory, and behavioral network science. Developments in each phase have been drivenby the desire to understand how agents interact in real-world networks, with each leveladding sophistication to the models we use to predict such interactions.Although economists Arrow and Debreu (1954) established long ago that there isalways a set of equilibrium prices in an economy with perfect competition and rationalplayers, their framework was not successfully applied to economic interaction on net-works until a half a century later by Kakade, Kearns, and Ortiz (2004a). Their resultallowed for the application of equilibrium analysis in situations where the assumptionthat each party can trade with all other parties is not valid. In reality, this is oftenthe case, as parties choose to exchange with each other based on their knowledge ortrust of each other (in the case of individuals) or on their trade status (in the case ofnations). Kakade, Kearns, and Ortiz thus accounted for this by describing a networkwhere the vertices represented consumers and edges represented a potential tradingrelationship between consumers.As the study of economic exchange began to draw more heavily on the under-standing of networks, it eventually collided with soc ial network theory. Accordingto Kakade, Kearns, Ortiz, Pemantle, and Suri, (2004b) this is “the study of appar-ently ‘universal’ properties of natural networks . . . and statistical generative models1that explain such properties” (p. 1). Researchers realized that, in order to predicteconomic interactions in real-world markets, it was not sufficient to have a theory ofeconomic exchange on networks, but also an understanding of which types of net-works are worth modeling because of their recurrence in the real world. Kakade et al.(2004b) state that some of the characteristics of natural networks are “small diameter,local clustering of edges, and heavy-tailed degree distribution” (p. 2). In applyingequilibrium analysis to networks generated to reflect these real world properties, theyfound that a vertex’s positioning in a network can have significant influence on itswealth, adding a previously unconsidered variable to the factors used to predict anindividual’s economic standing.The most recent development in this strain of research has been to apply an insightthat has previously been applied in economics and finance - that human behavioroften differs significantly from what might b e predicted in an equilibrium analysis,for reasons ranging from irrationality to lack of information. Thus, researchers havestarted to supplement theoretical research on network science with experimentationon human subjects. In this vein, Michael Kearns and Stephen Judd recently ran abehavioral experiment on 36 Penn students based on the “Milks and Wheats” networkmodel, which I will briefly describe.Each instance of “Milks and Wheats” has the following properties. It is a bipartitegraph, similar to Figure 1, with the vertices being divided into two sets; edges are onlyallowed to connect vertices in one set to vertices in the other. An agent is assignedto each vertex and is allotted an endowment of one unit of milk (for the first set) orone unit of wheat (for the second set); the agent is assigned a preference of zero forthe good that it is allotted, and a non-zero preference for the other good. Therefore,the agent’s objective is to obtain as much of the other good as possible. This classof games was examined by Kakade et al. (2004b), who described the equilibriumcharacteristics of such a network.In adapting the “Milks and Wheats” model to an experimental setting, with twocrucial differences from the traditional model, Professor Kearns made two significantchanges that addressed some of the concerns raised by behavioral economists. First,the participants could not see the entire network structure, only who their neighborswere - this helped to better model the degree of inf ormation an agent might rea-sonably be expected to know. Second, the price negotiations happened in real time- players would make an offer consisting of price and quantity, and could see theirneighbors’ offers as well as their neighbors’ remaining endowment. Thus, unlike inthe equilibrium situation, players could exchange their goods at more than one priceand time. Additionally, there was a time limit to the negotiation, so pressure wascreated for a player to unload his goods before a competitor made a better offer ortime ran out - again, this help e d to better model the real world than a static negotia-tion setting. To incentivize the players, they were offered a cash reward proportional2to the amount of wealth they accumulated throughout the trials.Figure 1: Diagram of a simple instance of “Milks and Wheats,” with equilibrium wealths of each node. From MichaelKearns’ lecture slides, Networked Life, Spring 2007.AnalysisPreliminariesIn order to facilitate the discussion, a number of definitions are in order. Fair graphsare graphs where the equilibrium wealths are perfectly equal among all participants,for example the perfect matching and the dense preferential attachment graphs. Un-fair graphs are graphs where the equilibrium wealths differ significantly between eachother, such as in the unrewired clan graphs and the preferential