基于博弈论的分布式选举协议及其纳什均衡性分析

ACM Transactions on Economics and Computation，卷。号71、第四条。出版日期：2019年2月基于博弈论的分布式选举协议ITTAI ABRAHAM，VMWARE研究丹尼·多列夫，耶路撒冷希伯来大学Joseph Y.康奈尔大学哈尔彭我们做一个博弈论分析的领导者选举，假设每个代理人更喜欢有一些领导者比没有领导者。我们表明，它是可能的，以获得一个公平的纳什均衡，其中每个代理人有一个相等的概率当选领导者，在一个完全连接的网络中，在一个双向环，和一个单向环，在同步设置。在异步设置中，纳什均衡不是完全正确的解决方案概念。相反，我们必须考虑事后纳什均衡;这意味着无论调度对手做什么，我们都有一个纳什均衡。我们表明，事后纳什均衡是可达到的异步设置在我们考虑的所有网络，使用有界的运行时间的协议。然而，在异步设置中，我们要求n>2。我们表明，我们可以得到一个公平的事后Nash-纳什均衡，如果n=2的异步设置下的一些密码学的假设（特别是，存在一个单向函数），使用承诺协议。然后，我们将这些结果推广到一个设置，我们可以有偏差的大小为k的联盟。在这种情况下，如果n>2k，我们可以在完全连通网络中得到我们所说的公平k-弹性均衡;在相同的密码学假设下，如果n>k，我们可以在完全连通网络、单向环或双向环中得到k-弹性均衡。最后，我们表明，在最小的假设下，我们的协议不仅给出了纳什均衡，他们也给出了一个顺序均衡，所以玩家甚至发挥最佳的均衡路径。CCS概念：·网络→网络协议; ·计算理论→博弈论和机制设计;其他关键词和短语：领导人选举，事后纳什均衡ACM参考格式：Ittai Abraham，Danny Dolev，and Joseph Y.哈尔彭2019年。领导者选举的分布式协议：一个博弈论的观点。ACM跨经济计算7，1，第4条（2019年2月），26页。https://doi.org/10.1145/3303712本文的初步版本发表在2013年第27届分布式计算国际研讨会论文集61比75Danny Dolev是Berthold Badler计算机科学主席。部分工作是在作者访问康奈尔大学时完成的。D. DolevJ. Y. Halpern作者Abraham，VMWARE Research，Herliya，Israel; email：ittaia@cs.huji.ac.il; D.以色列耶路撒冷希伯来大学计算机科学与工程学院;电子邮件：dolev@cs.huji.ac.il; J.Y.Halpern，计算机科学系，康奈尔大学，伊萨卡，纽约，14853，美国;电子邮件：halpern@cs.cornell.edu。允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用。必须尊重作者以外的其他人拥有的本作品组件的版权。允许使用学分进行摘要。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定许可和/或付费。从permissions@acm.org请求权限。© 2019版权归所有者/作者所有。授权给ACM的出版权。2167-8375/2019/02-ART4 $15.00https://doi.org/10.1145/33037124ACM Transactions on Economics and Computation，卷。号71、第四条。出版日期：2019年2月四：2I. Abraham等人1介绍正如经常观察到的那样，尽管分布式计算和博弈论对几乎相同的问题感兴趣-处理有许多代理的系统，面临不确定性，并且可能有不同的目标-在实践中，在这两个领域中使用的模型中存在显着差异在博弈论中，焦点一直是理性的代理人：每个代理人都被假定对结果具有效用，并且采取行动以最大化期望效用。在分布式计算中，焦点一直是这里隐含的假设是，有一个系统设计师为系统中的所有进程编写代码，但有些进程的进程可能会被对手接管，或者一些计算机可能会失败。没有被破坏的进程（无论是被对手破坏还是因为计算机故障）如下设计师的协议。其目标通常是证明系统设计者最近，人们对在假设代理是理性的并且将偏离设计者的协议的情况下检查标准分布式计算问题感兴趣如果这样做符合他们的最大利益的话。[1]Halpern和Teague（2004）可能是第一个这样做的人。 这个;他们表明（除其他外）秘密共享和多方通信不能通过具有有限运行时间的协议来完成，如果代理使用迭代容许性的解决方案概念（即，弱劣势策略的迭代删除）。从那时起，在分布式计算和博弈论的边界上进行了各种各样的工作。一方面，秘密共享和多方计算的工作仍在继续，考虑到错误和理性的行为（例如，Abraham等人（ 2006 ） 、 Dani 等 人 （ 2011 ） 、 Fuchsbauer 等 人 （ 2012 ） （ 2010 ） ， Gordon 和 Katz（2006），以及Lysyanskaya和Triandopoulos（2006））。也有关于何时以及是否可以将可以用可信第三方解决的问题转换为可以在没有第三方的情况下使用廉价谈话解决的问题的工作，这个问题也引起了博弈理论家的注意（例如，Abraham et al. （ 2006 ， 2008 ） ， Barany （ 1992 ） ， Ben-Porath （ 2003 ） ， Dodis et al.（2000）、Forges（1990）、Heller（2005）、Izmalkov等人（2011），Lepinski et al.（2004），McGrew et al.（2003）、Shoham和Tennenholtz（2005）以及Urbano和Vila（2002，2004））。这是相关的，因为有许多众所周知的分布式计算问题，可以很容易地解决的“可信”中介。例如，如果少于一半的代理被损坏，那么我们可以很容易地使用中介器进行拜占庭协议：所有代理人简单地告诉中介人他们的偏好，中介人选择偏好大多数人。另一条研究路线是由BAR模型的工作发起的（Aiyer et al.2005）-例如，参见Moscribroda et al.（2006）和Wong et al（2011）。就像亚伯拉罕的工作等人（2006，2008），BAR模型允许拜占庭（或错误）的球员和理性的球员;此外，它允许默许的球员，谁遵循推荐的协议。[2]传统的博弈论可以被视为只考虑理性的参与者，而传统的分布式计算只考虑默许的和拜占庭式的参与者。在这篇文章中，我们试图进一步了解博弈论思维对标准的影响，分布式计算中的一些问题。我们考虑在一个匿名网络（一个网络，最初，每个进程知道自己的名字，但不知道任何其他进程的名字）中选举领导者的经典分布式计算问题。Leader选举是分布式计算中的一个基本问题。毫不奇怪，针对这个问题有许多协议（例如，参见Chang和Roberts（ 1979 ） ， Dolev 等 人 ， （ 1982 ） ， Le Lann （ 1977 ） ， Lynch （ 1997 ） 和 Peterson（1982）），如果我们假设没有代理人被损坏;也有扩展处理1在本文中，我们使用2最初，“BAR”中的2011年）。用于领导者选举的分布式协议四：3ACM Transactions on Economics and Computation，卷。号71、第四条。出版日期：2019年2月（Feldman and Micali1997; Katz and Koo2006）.这项工作的大部分集中在一个环中的领导选举（例如，Chang和Roberts（1979）、Dolev等人（1982）、Le Lann（1977）、Lynch（1997）和Peterson（1982））。我们研究如果我们假设代理人是理性的会发生什么。很容易证明，如果所有代理（a）喜欢有一个领导者而不是没有领导者，并且（b）对于谁是领导者是不同的，那么所有标准的分布式计算协议都可以不加改变地工作。这可以被看作是形式化的直觉，在分布式计算的标准设置中，我们隐含地假设所有的代理共享系统设计者的偏好。但是，如果代理人对谁成为领导者有不同的偏好，会发生什么呢？例如，代理可能更喜欢他自己成为领导者，因为这可以使路由到其他代理的成本更小。在这种情况下，标准协议（通常假设每个代理人都有一个不同的id，并最终选举具有相同id的代理人或具有最高id的代理人作为领导者）不起作用;代理人有动机对他们的id撒谎。显然，如果没有其他人做任何事情，没有代理人有任何动机去做任何事情：如果没有人做任何事情，就不会有领导人当选，如果一个人投票给某个特定的领导人，情况仍然如此。我们感兴趣在获得公平的纳什均衡，其中每个代理人有一个平等的概率当选为领导人。此外，我们希望某人当选的概率为1。[3]在BAR模型的语言中，我们允许默许和理性的参与者，但不允许拜占庭式的参与者。解决分布式计算问题的一个标准方法是实现一个“可信的”中介。解决基本的领导者选举与调解人是很容易的：代理人简单地发送调解人的id，调解人随机选择一个id作为领导者，并宣布它的组。面临的挑战是在具有较弱通信原语的设置中实现此中介器。在博弈论环境中实现中介者的现有工作假设：（a）代理人具有众所周知的名称，（b）网络完全连接，以及（c）网络是同步的。在分布式计算世界中，领导者选举问题在许多环境中被研究。例如，已经研究了当代理是匿名的、当网络拓扑是受限的（例如，双向和单向环），以及当网络是异步时。本文的主要贡献之一是将博弈论中介实现框架扩展到这些更具挑战性的设置。已经有研究将博弈论思想应用于领导人选举（Altman andTennenholtz2008; Antonakopoulos2006; Gradwohl2010）;我们在下面讨论这项工作与我们的工作的关系。我们首先表明，在完全连接的网络，这是一个公平的纳什均衡，其中一个领导者被选为概率为1的情况下，在推导一个简单的协议的调解人方面的思维是有帮助的。然后，我们可以修改协议，使其在以下情况下工作：网络是一个环。我们还证明了我们的协议实际上是k-弹性的（Abraham et al.2006，2008）：只要n>k，它就可以容忍大小为k的联盟。这与拜占庭协议形成了一个有趣的对比，在拜占庭协议中，网络必须是2k+1连接才能容忍k个拜占庭故障（Dolev1982）。但是我们可以容忍k个理性参与者的联盟，即使是在一个单向环中。如果网络是同步的，则上述协议有效。在一个跨时代的环境中会发生什么？博弈论文献在很大程度上忽略了博弈论的问题;事实上，[3]如果没有最后一个条件，公平纳什均衡的存在性至少在完全连通网络的情况下是由众所周知的结果得出的我们可以将我们的故事建模为一个对称博弈，在这个博弈中，所有的代理人都有相同的行动选择，代理人的收益只取决于其他人执行了什么行动，而不是谁执行了除了证明每个博弈都有一个纳什均衡，纳什还证明了对称博弈也有一个对称纳什均衡，而对称均衡显然是公平的。然而，在对称均衡中，很可能没有选择领导者例如，在我们的博弈中，一个平凡的对称均衡是每个人都随机选择一个候选领导者但是，在大多数情况下，代理人选择不同的候选人，因此没有领导者。四：4I. Abraham等人ACM Transactions on Economics and Computation，卷。号71、第四条。出版日期：2019年2月≤我们所知道的唯一一个博弈论环境中的工作来自计算机科学方面（Antonakopoulos2006;Friedman and Shenker1998; Gradwohl2010; Monderer and Tennenholtz1999）。但在分布式计算世界中，分布式计算可能是最常见的模型，而且它肯定会出现在许多现实世界的环境中，在这些环境中，时间很重要，并且存在战略问题。仅举一个例子，区块链的标准模型不假设同步时钟，并且存在界限Δ，使得消息可能需要Δ时间步到达。因此，我们不能假设时钟是同步的，代理人不一定能告诉动作执行的顺序我们在这里考虑的解决方案概念是纳什均衡的自然变体，之前在异步设置中已经考虑过（Antonakopoulos2006; Gradwohl2010）。为了理解纳什均衡，我们必须讨论代理人在给定其他智能体的策略的情况下，如果智能体i的行动最大化了i的期望效用，那么它就是最佳对策但是要计算期望效用，我们需要一个结果的概率。通常，在异步设置中，结果可能取决于代理的调度顺序和消息传递时间。但我们没有这些概率。我们处理这些问题，在这种情况下，假设对手选择的调度和选择的消息传递时间，并试图获得无论对手怎么做都是纳什均衡的策略这种直觉产生了文献中所谓的事后纳什均衡。我们提供了一个简单的协议，给出了一个公平的事后纳什均衡的完全连接的网络在异步设置提供n>2k。在本文的初步版本中（Abraham et al.2013），我们声称提供了一个协议，在n>2k的情况下，在单向和双向环中给出了k-弹性平衡。伊夫拉赫Mansour（2018）显示，方案不正确。[4] Yifrach和Mansour还为大小为n的环提供了一个协议，该协议可以容忍大小为O（n）的联盟。一个有待解决的问题是这是可以改进的。在一个完全连接的网络中，它们不能：我们在那里是没有公平的k-弹性事后纳什均衡，如果n2k的完全连接的网络，这个界限也适用于单向和双向环。下限假设代理人没有计算上的限制。如果我们在密码学文献中做一个标准假设，即单向函数存在，那么我们可以得到在所有这些拓扑中的公平的K-K没有一组多达k个代理可以通过偏离获得超过n的收益），即使在异步设置中，只要n>k，使用承诺协议（Goldreich2001）。将我们的结果与Antonakapoulos（2006）和Gradwohl（2010）的结果进行比较是很有趣的。他们考虑了所谓的全信息模型（Ben-Or and Linial1985）。在这种模式中，非正式地，玩家轮流广播消息。所有第n轮消息在发送任何第（n+1）轮消息之前被接收;对递送的相对顺序没有任何假设（因此存在有限的延迟）。总的来说，全信息模型与我们的模型是不可比拟我们不假设广播。玩家发送点对点消息;他们可以发送给谁取决于网络拓扑。此外，在异步设置中，我们通常不能假设消息是在轮中发送的。Gradwohl考虑了高达k拜占庭的影响（即，恶意）代理和一个理性代理的完全信息模型，证明了可能性和不可能性的结果。格拉德沃尔在Abraham et al.（2006）的语言中，Gradwohl对（1，k）-鲁棒均衡感兴趣，它容忍一个理性主体和多达k个拜占庭主体; Antonakopoulos主要关注（0， 1）-鲁棒性。作为对比，我们感兴趣的是（k，0）-鲁棒均衡，容忍[4]实际上，Yifrach和Mansour用于领导者选举的分布式协议四：5ACM Transactions on Economics and Computation，卷。号71、第四条。出版日期：2019年2月−k理性代理人，但没有拜占庭代理人。（传统的纳什均衡是（1，0）-鲁棒均衡。）像我们一样，Gradwohl和Antonkaopoulos对事后均衡感兴趣，无论调度器做什么都能获得均衡（尽管他们的调度器比我们在异步设置中考虑（Altman和Tennenholtz（2008））也考虑了领导者的主动性，但他们关注的是一种不同类型的解决方案概念，即弱优势，并没有真正考虑调度器的影响。本文旨在作为一个案例研究，说明在尝试将博弈论方法应用于分布式计算问题时可能出现的一些问题我们当然没有试图看到领导者选举的所有变体都发生了什么，也没有试图获得在时间，空间或消息复杂性方面最优的协议虽然我们相信我们的领导选举技术可以用于我们所考虑的拓扑之外的拓扑，但我们也没有探索过。相反，我们的目标一直是了解的影响，处理ratio- nal，自利的代理人在分析分布式协议时出现的一些问题，如领导人选举。本文的其余部分组织如下。在第2节中，我们简要回顾了我们正在使用的模型。我们在第3节中提出了实现公平纳什均衡的协议。这些协议涉及到可以说是令人难以置信的威胁：一旦玩家发现问题，他就会拒绝选举领导者，从而惩罚自己以及问题的肇事者。然而，我们在第4节中表明，通过向效用函数添加一个合理的假设，我们的纳什均衡实际上变成了一个序列均衡（Kreps和Wilson，1982），这是一个旨在处理难以置信的威胁的解决方案概念。最后，我们将在第5节进行一些讨论。2模型我们将网络建模为有向的、简单的（使得每对节点之间最多只有一条边）、强连通的有限图。节点代表代理，边代表通信链路。我们假设网络的拓扑结构是公知的，这样代理就知道它的大小以及代理如何相互连接。例如，如果我们考虑一个完全连接的网络，所有的代理都知道网络是完全连接的，并且知道他们知道，等等;当我们考虑单向或双向环时，情况也是如此。代理也知道他们所有的传入和传出链接。偏离代理只能使用网络拓扑进行通信;不存在“带外”通信。我们假设每个代理都有一个唯一的id，这个id来自于一些众所周知的名称空间，我们可以把它看作是一组自然数。最初，代理知道他们的ID，但可能不知道任何其他代理的ID。为了方便起见，如果有n个代理，我们将其命名为1、...，n.这些名称是为了方便我们讨论协议时使用的（这样我们就可以讨论代理i）;这些名称不为代理所知。消息传递由通道（并且不受代理的控制）。代理可以识别消息来自哪个传入链接，并可以区分传出链接。当我们考虑同步系统时，我们假设代理人步调一致。这是常见的知识，当协议被启动。在轮m中，（如果m>0）在轮m1中发送的所有消息被所有代理接收之后，代理执行它们需要执行的任何内部计算（包括设置变量的值）;然后发送消息（将在第m+1轮开始时接收）。在异步设置中，代理被调度为在任意时间移动（可能是对抗性的）调度程序。当它们被调度时，它们将执行与同步情况下相同为了便于说明，我们假定消息空间是有限的。虽然我们假设所有发送的消息最终都被接收到（未损坏），但消息传递时间没有限制，消息可能会在四：6I. Abraham等人ACM Transactions on Economics and Computation，卷。号71、第四条。出版日期：2019年2月⊥⊥任意顺序（即，不一定按照它们被发送的顺序）。我们也不对一个代理相对于另一个代理可以被调度的次数做任何假设，尽管我们确实假设代理被无限频繁地调度（因此对于所有代理i和时间t，t之后将有一个时间i被调度）。由于我们对领导选举感兴趣，我们假设每个代理i都有一个变量leaderi，可以设置为某个代理如果在协议结束时，存在代理idv，使得leaderi=v，所有代理i和所有代理就哪个代理具有IDV达成一致，也就是说，在网络中存在唯一的节点，使得所有代理知道该节点具有IDV，那么我们说具有IDV的代理已经被选举为领导者。如果智能体不同意领导者的身份和位置，那么就没有领导者。在一个完整网络的情况下，知道哪个节点的id为v意味着每个代理知道他的哪条链路连接到id为v的节点。在环的情况下，这意味着每个代理都知道环的大小和他与v的偏移量。我们假设每个代理i对协议的结果都有效用。为了这项工作的目的，我们假设代理人喜欢有一个领导者而不是没有一个，在弱意义上，每个代理人i从来没有分配给一个没有领导者的结果比一个有领导者的结果更高的效用（尽管我们允许代理人在一个结果之间是无所谓的，没有领导者，有领导者的结果）。我们进一步假设一个代理i除了一个技术性的结果，我们没有假设我更喜欢哪个代理人作为领导者。虽然我可能更希望他自己成为领导者，而不是其他任何人，但我们的结果并不取决于此。然而，我们关于效用函数的假设并不能让我们表达我更喜欢一个他发送更少消息或做更少计算的协议，而不是一个他发送更多消息或做更多计算的协议（尽管事实上我们的协议是相当有效的消息，不需要太多的计算）。请注意，我们的假设意味着代理i可以用Ben-Porath（2003）的话来说，这意味着每个智能体都有一个惩罚策略。战略概况（即，每个代理人的策略或协议）是纳什均衡，如果没有代理人可以通过切换到不同的协议（假设所有其他代理人继续使用他们的协议）来单方面增加他的期望效用。很容易看出，如果所有的智能体对于谁是领导者都是无差别的（即，如果对于每个代理i，i的3各项议定书我们认为协议在三个设置：一个完全连接的网络，单向环，双向环。我们还考虑了同步情况和异步情况。3.1完全连接的网络，同步情况考虑一个完全连通网络中的领导者选举。首先假设我们有一个中介，也就是一个可信的第三方。然后似乎有一个天真的协议，可以使用：每个代理告诉中介他的id，然后中介选择最高的id，并宣布它。所有的代理商。具有此ID的代理是领导者。这个幼稚的协议有两个明显的问题。首先，由于我们假设名称空间是公知的，如果每个代理人都喜欢成为领导者（这是可能的，尽管我们不认为这是必然的情况），代理人将被诱惑对他们的id撒谎，并声称最高的id是他们的id。用于领导者选举的分布式协议四：7ACM Transactions on Economics and Computation，卷。号71、第四条。出版日期：2019年2月我⊥i=1⊥.{−}图1.一、 协议LEADcc，由每个代理i执行。我们通过让中介者随机选择一个id来解决第一个问题;我们通过让代理共享他们的id来解决第二个问题。更详细地说，我们假设在第一轮，代理人告诉对方他们的身份证。在第2轮中，每个代理告诉中介他听到的id集合关于（包括他自己的）。在第3轮中，中介器比较所有id集合。如果它们都是相同的，中介者从集合中随机选择一个idv;否则，中介者宣布“没有领导者”。如果中介者宣布v是领导者，则每个代理i设置领导者i=v;否则，领导者i是未定义的（并且没有领导者）。很容易看出，使用该协议的每个人都给出了一个纳什均衡。如果某个代理没有向每个人发送相同的id，那么中介将从不同的代理获得不同的列表，并且将没有领导者。由于领导者是随机选择的，没有人有任何动机对他的id撒谎。注意，这个协议是，在亚伯拉罕等人的语言。（2006，2008），k-弹性对于所有kn，其中n是代理的数量。<换句话说，不仅没有一个人代理人有任何偏离的动机，任何大小为k的联盟也没有。此外，由此产生的纳什均衡是公平的：每个代理人都有同样的可能性成为被选中的领导者。现在我们想用廉价的语言来实现这个协议同样，这是直截了当的。在第1轮，每个代理i向每个人发送他的id;在第2轮，i向每个代理j发送他（i）收到的id集合（包括他自己的）。如果代理i接收到的集合不完全相同，或者我没有收到来自某个代理的ID，然后我停止，因为我仍然设置为leader，所以leader选举失败。否则，设n为id集合的基数。代理i选择一个随机数Ni，{0，. . . ，n-1}，并且s将其结束到所有其他代理。 每个代理i然后计算N=。nNi（mod n）并将具有集合中第（N+1）个最高id的代理作为领导者。(If某些代理j不向i发送与其他代理相同的号码，则领导i仍被设置为。此外，如果不是所有代理都将领导者值设置为相同，则通过假设，没有选择的领导者。为代理iLEADcc调用此协议。LEADcc的伪代码如图1所示。让LEADccdei注意配置文件（LEADcciLEADcc）（我们在整个1、... ，n的文章）。显然，对于配置文件LEADcc，所有智能体都将选择同一个leader。我们也很容易看到，没有任何一个代理人（实际上，也没有任何一个规模为kn的群体）有任何偏离这种策略的动机。<下面的定理总结了前面的讨论。第3.1节. LEADcc是n个完全连通网络中的公平k代理，对于所有k2k的单向和双向环中给出了k-弹性平衡。正如Yifrach和Mansour（2018）所示，方案是不正确的。但是我们可以提供一个协议，在完全连接的异步通信中给出一个k-弹性均衡，四：12I. Abraham等人ACM Transactions on Economics and Computation，卷。号71、第四条。出版日期：2019年2月{−}∈ {−}j=1∈.⊥∈|| ≤≤|| ≤∈ileaderrALEADi||j=1网络，如果n>2k，使用安全多方计算和秘密共享的想法（Ben-Or et al. 1988年）的报告。要进行秘密共享，我们必须在有限域中工作;因此，为了便于说明，假设n是素数的幂5.与同步情况一样，代理首先将其id发送给所有其他代理，然后交换收到的id集，以便它们都同意系统中的id集。（当然，如果一个agenti没有从所有agent得到相同的id集，那么i会在leaderi=时停止，所以不会选择leader 每个代理i选择一个随机值Ni0，. ，n 1和域Fn= 0，.，n 1，使得fi（0）=Ni。然后i向每个代理j发送消息fi（j）。一旦i从所有代理j接收到fj（i）