AF: Small: Size, Uncertainty, and Imprecision in Algorithmic Game Theory and Economics

New York University, New York NY

Investigators

Abstract

Non-Technical Description As is well known, settings with many interacting participants sometimes work well, for example in market economies, and other times can lead to poor outcomes, as in the Tragedy of the Commons. The hypothesis driving this project is that as the number of participants increases, if these participants have varied interests, then the poor outcomes will be mitigated, i.e. the Tragedy of the Commons becomes increasingly less tragic. To make this precise, one needs to be able to quantify the quality of the outcomes. One standard approach is to measure the social welfare, which is simply the sum of the values the participants achieve. The intent in this project is to compare the ideal social welfare to the social welfare that actually occurs. The ratio of these values is called the Price of Anarchy. The aim is to show that as the number of participants increases, these values will become increasingly close, i.e. that the Price of Anarchy approaches the ideal value of 1. Of course, this is only going to be true under appropriate conditions and one of the goals of the project is to identify such conditions. Why is this interesting? First, for settings with positive results, this will help explain why good results are achieved. Second, for other settings, it may indicate why poor outcomes are likely. In addition, it may suggest how to design or constrain settings so as to achieve improved results. One or more PhD students will participate in this project. In addition, the PI hopes to interest more junior students. A prime means to this end is to teach inviting undergraduate courses. One specific tool here is to create compelling course videos to complement classroom instruction and this is part of the plan for this project. Of course, such videos are valuable in their own right. Technical Description A main concern of this project is to understand the impact of self-interested behavior (a.k.a. strategic behavior) on shared outcomes. The PI wants to understand for which settings and to what extent size and uncertainty reduce the losses due to strategic behavior. These types of questions have been previously studied in the Economics literature, but by and large the ensuing results are in-the-limit statements. The intent for this project is to obtain quantified tradeoffs. Furthermore the aim is to identify settings for which these are polynomial tradeoffs, with the implication that the loss reduction is evident at moderate sizes. By uncertainty, the PI is not simply referring to Bayesian settings, where there is uncertainty about participants' desires (utilities) -- in such settings, participants' utilities are given by draws from known distributions. There is a need for additional uncertainty, either as to the number of participants or to the resources being shared. In practice, it seems reasonable that this information would not be known exactly in large settings; furthermore, some such uncertainty appears to be necessary for positive results. Specific questions the PI will seek to answer include: 1. Is price-taking a plausible behavior in (some classes of) market economies, i.e. are the gains from strategic behavior small when the economy is large? A follow-up question is whether the resulting outcome, which may include small-gain strategic behavior, is close to the optimal outcome. (This is not an immediate implication of a positive answer to the first question.) 2. For auctions with many copies of each good and many buyers, does uncertainty reduce the gains from strategic behavior, and again, is the resulting outcome close to optimal? In other words, does the Price of Anarchy for these settings tend to 1 as the setting size grows? 3. Do results shown for market economies comprising idealized arbitrarily divisible goods extend approximately to indivisible goods, again when the setting sizes are large? 4. The outcomes being considered in 1-3 above are stable outcomes, a.k.a. equilibria, which have the property that no participant wishes they had used a different strategy. These are viewed as plausible outcomes, but leaves unanswered the question of how they are found. A natural approach is to consider dynamic behavior. Of course, this may change the ensuing outcomes. This leads to asking: for what settings do natural dynamics converge toward equilibria? Complicating matters further, one can imagine that settings change over time, leading to the question: for what not-too-rapidly changing settings can drifting (changing) equilibria be tracked? The PI will be seeking quantified relations between the rate of change and the closeness to equilibrium.