• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>ACM transactions on economics and computation >Distributed Protocols for Leader Election: A Game-Theoretic Perspective
【24h】

Distributed Protocols for Leader Election: A Game-Theoretic Perspective

机译：领导者选举的分布式协议：游戏理论观点

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We do a game-theoretic analysis of leader election, under the assumption that each agent prefers to have some leader than no leader at all.We show that it is possible to obtain a fair Nash equilibrium, where each agent has an equal probability of being elected leader, in a completely connected network, in a bidirectional ring, and a unidirectional ring, in the synchronous setting. In the asynchronous setting, Nash equilibrium is not quite the right solution concept. Rather, we must consider ex post Nash equilibrium; this means that we have a Nash equilibrium no matter what a scheduling adversary does.We show that ex post Nash equilibrium is attainable in the asynchronous setting in all the networks we consider, using a protocol with bounded running time. However, in the asynchronous setting, we require that n > 2. We show that we can get a fair ex post ?-Nash equilibrium if n = 2 in the asynchronous setting under some cryptographic assumptions (specifically, the existence of a one-way functions), using a commitment protocol.We then generalize these results to a setting where we can have deviations by a coalition of size k. In this case, we can get what we call a fair k-resilient equilibrium in a completely connected network if n > 2k; under the same cryptographic assumptions, we can a get a k-resilient equilibrium in a completely connected network, unidirectional ring, or bidirectional ring if n > k. Finally, we show that under minimal assumptions, not only do our protocols give a Nash equilibrium, they also give a sequential equilibrium, so players even play optimally off the equilibrium path.
机译：我们对领导者选举进行了游戏理论分析，假设每个代理人都更喜欢拥有一些领导者比根本没有领导者。在双向环和同步设置中，在双向环和单向环中选出的领导者。在异步环境中，NASH平衡并不是正确的解决方案概念。相反，我们必须考虑纳什均衡。这意味着无论调度对手做什么，我们都具有NASH平衡。我们证明，在我们考虑的所有网络中，使用具有有限运行时间的协议，可以在我们考虑的所有网络中实现Ex nash平衡。但是，在异步设置中，我们需要n>2。我们证明我们可以在某些加密假设下在异步设置中n = 2获得公平的均值？函数），使用承诺协议。然后，我们将这些结果推广到一个设置，在该设置中，我们可以通过大小为k的联盟偏离偏差。在这种情况下，如果n> 2k，我们可以在完全连接的网络中获得所谓的公平k弹性平衡。在相同的加密假设下，如果n> k，我们可以在完全连接的网络，单向环或双向环中获得k弹性平衡。最后，我们表明，在最小的假设下，我们的协议不仅给出了NASH平衡，而且还具有顺序平衡，因此玩家甚至在平衡路径上发挥最佳作用。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号