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

AF：小：算法博弈论和经济学中的规模、不确定性和不精确性

• 批准号: 1527568
• 负责人: Richard Cole
• 金额: $ 40万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1527568&HistoricalAwards=false
• 关键词: AF; Small; Size; Uncertainty; Imprecision

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.

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