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

非技术描述众所周知，有许多互动参与者的设置有时效果很好，例如在市场经济中，而其他时候可能会导致糟糕的结果，例如在公地悲剧中。推动这个项目的假设是，随着参与者数量的增加，如果这些参与者有不同的兴趣，那么糟糕的结果将得到缓解，即公地的悲剧变得越来越不悲惨。要做到这一点，人们需要能够量化结果的质量。一种标准的方法是衡量社会福利，社会福利只是参与者实现的价值的总和。这个项目的目的是将理想的社会福利与实际发生的社会福利进行比较。这些价值的比率被称为无政府状态的价格。目的是表明，随着参与者人数的增加，这些值将变得越来越接近，即无政府状态的价格接近理想值1。当然，只有在适当的条件下才会如此，该项目的目标之一就是确定这种条件。为什么这很有趣？首先，对于具有积极结果的设置，这将有助于解释为什么会取得良好的结果。其次，对于其他环境，这可能表明为什么可能会出现糟糕的结果。此外，它可能会建议如何设计或约束设置，以实现更好的结果。一名或多名博士生将参与该项目。此外，PI希望能让更多的初中生感兴趣。实现这一目标的一个主要手段是教授特邀本科生课程。这里的一个具体工具是创建引人注目的课程视频来补充课堂教学，这是该项目计划的一部分。当然，这样的视频本身就很有价值。技术描述这个项目的一个主要关注点是了解自利行为(也就是战略行为)共享结果。PI想要了解哪些设置以及规模和不确定性在多大程度上减少了战略行为造成的损失。这些类型的问题以前已经在经济学文献中进行了研究，但大体上，随后的结果都是限制陈述。这个项目的目的是获得量化的权衡。此外，目标是确定这些是多项式权衡的设置，这意味着在中等规模时损失减少是明显的。通过不确定性，PI不是简单地指贝叶斯设置，其中存在关于参与者的期望(效用)的不确定性-在这样的设置中，参与者的效用通过从已知分布中提取来给出。需要有更多的不确定性，无论是参与者的数量还是共享的资源。在实践中，这种信息在大环境下不会被准确知道似乎是合理的；此外，一些这样的不确定性似乎是积极结果所必需的。PI将寻求回答的具体问题包括：1.在(某些类别的)市场经济中，价格定价是一种可信的行为吗，即当经济规模较大时，战略行为的收益是否很小？一个后续的问题是，结果结果是否接近最优结果，其中可能包括微薄的战略行为。(这不是对第一个问题的正面回答的直接含义。)2.对于每件商品都有许多副本和许多买家的拍卖，不确定性是否会减少战略行为的收益，以及由此产生的结果是否接近最优？换句话说，随着背景规模的增长，这些背景下的无政府状态的价格是否趋于1？3.当背景规模较大时，包含理想化的任意可分割商品的市场经济所显示的结果是否近似延伸到不可分割商品？4.上文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.