Algorithmic and game-theoretic analysis of network design

网络设计的算法和博弈论分析

• 批准号: 262124-2012
• 负责人: Karakostas, George
• 金额: $ 1.24万
• 依托单位: McMaster 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=571240
• 关键词: Algorithmic; game; theoretic; analysis; network

Is it possible for a network operator to lure network users into a certain behavior by lying to them for a very long time, especially when they are automated? Can we extend the lifetime of a solar-renewable battery used to keep traveling cars connected to the Internet? What is the best way to lay highways so that we can use the roads already built to connect cities as soon as possible on average? These are some of the problems arising during the modelling, construction, operation, and use of networks. They are addressed in this proposal by using tools from algorithmic game theory and by designing efficient approximation algorithms when those problems are proven to be computationally hard. The use of game-theoretical concepts to model environments with competitive entities has been the field of economists for many years. Algorithmic game theory is particularly suited for studying networks of selfish users and/or operators. The proposed work aspires to a paradigm shift in the use of algorithmic game theory from one-shot games to repeated games that now include a history of previous plays. We propose to do that by exploiting the constraints imposed on the players due to their automated (algorithmic) nature. Hence, the proposed work should reveal new connections between computer science and economics through the big volume of work already done by economists on repeated games and reputation effects. On a more practical level, the proposal introduces a new set of problems in approximation algorithms that are related to energy conservation and infrastructure construction in networks. Although more limited in scope than the objectives above, they nevertheless present us with the opportunity of immediate impact on the environment (by, for example, the clever scheduling of energy dispensation used for data transmission) or the cost of network infrastructure (by, for example, the time-efficient scheduling of building new roads). Such problems are usually hard to solve exactly, and, therefore, we propose the development of algorithms that produce provably good approximate solutions.

网络运营商是否有可能通过长时间欺骗网络用户，特别是在自动化的情况下，诱使他们采取某种行为？我们能延长用于保持旅行汽车连接到互联网的太阳能可再生电池的寿命吗？铺设高速公路的最佳方式是什么，使我们能够利用已经建成的道路，平均尽快将城市连接起来？这些是在网络的建模、构建、操作和使用过程中出现的一些问题。在这个建议中，他们使用算法博弈论的工具，并通过设计有效的近似算法时，这些问题被证明是计算困难的。 使用博弈论的概念来模拟具有竞争性实体的环境，多年来一直是经济学家的研究领域。博弈论特别适合于研究自私用户和/或运营商的网络。拟议的工作渴望在使用算法博弈论的范式转变，从一次性游戏到重复的游戏，现在包括以前的游戏的历史。我们建议这样做，利用强加给球员的限制，由于其自动化（算法）的性质。因此，拟议的工作应该揭示计算机科学和经济学之间的新联系，通过大量的工作已经做了经济学家对重复博弈和声誉效应。 在更实际的层面上，该提案引入了一组新的近似算法问题，这些问题与网络中的节能和基础设施建设有关。尽管其范围比上述目标更为有限，但它们仍然为我们提供了对环境产生直接影响的机会（例如，通过巧妙地安排用于数据传输的能源分配）或降低网络基础设施的成本（例如，通过及时有效地安排建造新建道路）。这样的问题通常很难精确解决，因此，我们提出了算法的发展，产生可证明良好的近似解。