Computation in Games and Networks

游戏和网络中的计算

• 批准号: 288334-2012
• 负责人: Vetta, Adrian
• 金额: $ 3.06万
• 依托单位: McGill University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=571396
• 关键词: Computation; Games; Networks

The aim of this proposal is to provide quantitative analyses of decision making, where decision makers may be single authorities, such as a network operator attempting to minimize traffic congestion, or participants in multi-agent systems such as auctions or social networks. In practice all decision makers are computationally bounded. Thus, for multi-agent systems, we need to know how computational considerations affect game-play; despite its widespread applicability and importance, there is currently little understanding with respect to this question. Furthermore, an agent's choice of action may be heavily influenced by mechanistic restrictions within the system, for example, the actual pricing mechanism used within a market or the actual routing protocol used within a network. Consequently, this proposal focuses on the implications of computational and mechanistic constraints on decision making, with a particular emphasis on applications related to networks. Thus, at a high level, we are interested in the following type of question. Can we build a cheap but functionally effective network? Can we design a market mechanism that leads to high social welfare? What are the dynamics and quality of outcomes produced by specific game-playing strategies (in particular, strategies that agents actually use rather than those prescribed by theoretical behavioural assumptions)? What are the effects of an intervention into a system? Clearly, to model and answer such questions we require tools from a wide range of areas. Towards this end, we utilize techniques from algorithm design and analysis, optimization, game theory, behavioural economics, graph theory, and causal inference.

该提案的目的是提供决策的定量分析，其中决策者可以是单一权威机构，例如试图最大程度地减少交通拥堵的网络运营商，或多代理系统（例如拍卖或社交网络）的参与者。 实际上，所有决策者都受到计算的限制。因此，对于多智能体系统，我们需要知道计算因素如何影响游戏玩法；尽管这个问题具有广泛的适用性和重要性，但目前人们对这个问题的了解还很少。此外，代理的行动选择可能会受到系统内的机械限制的严重影响，例如，市场内使用的实际定价机制或网络内使用的实际路由协议。因此，该提案重点关注计算和机械约束对决策的影响，特别强调与网络相关的应用。 因此，在较高的层面上，我们对以下类型的问题感兴趣。我们能否建立一个廉价但功能有效的网络？我们能否设计一个带来高社会福利的市场机制？特定的游戏策略（特别是主体实际使用的策略，而不是理论行为假设规定的策略）产生的结果的动态和质量是什么？干预系统会产生什么影响？显然，为了建模和回答这些问题，我们需要来自广泛领域的工具。为此，我们利用算法设计和分析、优化、博弈论、行为经济学、图论和因果推理等技术。