Algorithmic and game-theoretic analysis of network design

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

• 批准号: 262124-2012
• 负责人: Karakostas, George
• 金额: $ 1.24万
• 依托单位: McMaster University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2013
• 资助国家: 加拿大
• 起止时间: 2013-01-01 至 2014-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=525506
• 关键词: 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.

网络运营商有没有可能通过长时间对网络用户撒谎来引诱他们进入某种行为，特别是当他们是自动化的时候？我们能否延长用于让出行汽车连接到互联网的太阳能可再生电池的寿命？铺设高速公路的最好方式是什么，这样我们平均可以用已经建成的道路尽快连接城市？这些是在网络的建模、建设、运行和使用过程中出现的一些问题。在本提案中，通过使用算法博弈论中的工具并通过设计高效的近似算法来解决这些问题，当这些问题被证明是计算困难的时候。