Improved equilibria via public service advertising
Improved equilibria via public service advertising
复制标题
DOI：
10.1137/1.9781611973068.80
复制
发表时间：
2009-01
期刊：
影响因子：
--
通讯作者：
Maria-Florina Balcan;Avrim Blum;Y. Mansour
中科院分区：
文献类型：
--
作者：
Maria-Florina Balcan;Avrim Blum;Y. Mansour
许多自然博弈都有高成本和低成本的纳什均衡：它们的无政府状态代价很高，但稳定代价很低。在这种情况下，人们可以通过“公共服务广告活动”鼓励参与者遵循低成本均衡，将行为从高成本均衡转移到低成本均衡，如果每个参与者都遵循建议，那么我们就完成了。然而，假设每个人都遵循指示是不现实的。一个更自然的假设是，一些玩家会跟随他们，而其他玩家不会。在本文中，我们考虑的问题，在多大程度上可以这样的广告活动导致行为从一个坏的均衡切换到一个好的，即使只有一小部分人实际上遵循给定的建议，这样做只是暂时的。与“利他主义价值”模型不同，我们假设每个人最终都会按照自己的利益行事。我们分析了这个问题的几个重要的和广泛研究的游戏类，包括网络设计与公平的成本分摊，调度与无关的机器，党的隶属关系的游戏（其中包括共识和削减游戏）。我们证明了对于其中的一些博弈（如公平成本分摊），遵循给定建议的随机α部分群体足以保证在任何α > 0的稳定性价格的O（1/α）因子内。对于其他游戏（如党派游戏），有一个严格的阈值（在这种情况下，α 1/2足以达到接近最优的行为）。最后，对于某些博弈，例如调度，α < 1是不够的。我们还考虑了一个“病毒式营销”模型，其中某些球员是专门针对性的，并分析这种针对性的影响行为使用一个小得多的目标球员的能力。
Many natural games have both high and low cost Nash equilibria: their Price of Anarchy is high and yet their Price of Stability is low. In such cases, one could hope to move behavior from a high cost equilibrium to a low cost one by a "public service advertising campaign" encouraging players to follow the low-cost equilibrium, and if every player follows the advice then we are done. However, the assumption that everyone follows instructions is unrealistic. A more natural assumption is that some players will follow them, while other players will not. In this paper we consider the question of to what extent can such an advertising campaign cause behavior to switch from a bad equilibrium to a good one even if only a fraction of people actually follow the given advice, and do so only temporarily. Unlike the "value of altruism" model, we assume everyone will ultimately act in their own interest. We analyze this question for several important and widely studied classes of games including network design with fair cost sharing, scheduling with unrelated machines, and party affiliation games (which include consensus and cut games). We show that for some of these games (such as fair cost sharing), a random α fraction of the population following the given advice is sufficient to get a guarantee within an O(1/α) factor of the price of stability for any α > 0. For other games (such as party affiliation games), there is a strict threshold (in this case, α 1/2 is enough to reach near-optimal behavior). Finally, for some games, such as scheduling, no value α < 1 is sufficient. We also consider a "viral marketing" model in which certain players are specifically targeted, and analyze the ability of such targeting to influence behavior using a much smaller number of targeted players.