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

非技术描述众所周知，有许多相互作用的参与者的环境有时工作得很好，例如在市场经济中，而其他时候可能导致糟糕的结果，例如在公地悲剧中。推动这个项目的假设是，随着参与者数量的增加，如果这些参与者有不同的利益，那么不良结果将得到缓解，即公地悲剧变得越来越不悲惨。为了做到这一点，人们需要能够量化结果的质量。一种标准的方法是衡量社会福利，即参与者实现的价值的总和。这个项目的目的是比较理想的社会福利和实际发生的社会福利。这些价值的比率被称为无政府状态的代价。其目的是表明，随着参与者数量的增加，这些值将变得越来越接近，即无政府状态的价格接近理想值1。当然，这只有在适当的条件下才能实现，而项目的目标之一就是确定这些条件。为什么这很有趣？首先，对于具有积极结果的设置，这将有助于解释为什么会取得良好结果。其次，在其他情况下，它可能表明为什么可能出现糟糕的结果。此外，它可能建议如何设计或约束设置，以达到改进的结果。一名或多名博士生将参与该项目。此外，PI希望引起更多初中生的兴趣。实现这一目标的主要手段是开设吸引人的本科课程。一个具体的工具是制作引人注目的课程视频来补充课堂教学，这是这个项目计划的一部分。当然，这样的视频本身就很有价值。技术描述本项目的一个主要关注点是了解自利行为（又名战略行为）对共享结果的影响。PI想要了解哪种设置以及在多大程度上大小和不确定性可以减少由于战略行为造成的损失。这些类型的问题之前已经在经济学文献中进行了研究，但总的来说，随后的结果是极限陈述。这个项目的目的是获得量化的权衡。此外，目的是确定这些是多项式权衡的设置，这意味着在中等大小下损失减少是明显的。通过不确定性，PI不只是指贝叶斯设置，其中参与者的欲望（效用）存在不确定性-在这种设置中，参与者的效用是由已知分布的抽取给出的。需要有更多的不确定性，无论是参与者的数量还是正在共享的资源。实际上，在大型环境中，这些信息不被准确地了解似乎是合理的；此外，这种不确定性似乎是取得积极成果所必需的。PI将寻求回答的具体问题包括：1。在（某些类别的）市场经济中，定价是一种合理的行为吗？也就是说，当经济规模较大时，战略行为的收益是否较小？接下来的问题是，最终结果（可能包括小收益战略行为）是否接近最优结果。（这并不是对第一个问题的肯定回答的直接暗示。）对于每件商品都有许多副本和许多买家的拍卖，不确定性是否会减少战略行为的收益，以及最终结果是否接近最优？换句话说，这些设置的混乱价格是否会随着设置规模的增长而趋于1 ？由理想的任意可分商品组成的市场经济的结果是否近似地扩展到不可分商品，当设置尺寸很大时？上述1-3所考虑的结果都是稳定的结果，即均衡，其特点是没有参与者希望自己使用了不同的策略。这些结果被认为是合理的，但它们是如何被发现的问题没有得到回答。一种自然的方法是考虑动态行为。当然，这可能会改变随后的结果。这就引出了一个问题：在什么情况下，自然动态会趋于平衡？更复杂的是，我们可以想象环境会随着时间的推移而改变，这就引出了一个问题：对于那些不太快速变化的环境，我们能够追踪到漂移（变化）平衡吗？PI将寻求变化率和接近平衡之间的量化关系。

Non-Technical DescriptionAs 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 DescriptionA 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.