首页> 外文会议>Algorithmic Game Theory >Distributed Algorithmic Mechanism Design and Algebraic Communication Complexity
【24h】

Distributed Algorithmic Mechanism Design and Algebraic Communication Complexity

机译:分布式算法机制设计与代数通信复杂度

获取原文
获取原文并翻译 | 示例

摘要

In this paper, we introduce and develop the field of algebraic communication complexity, the theory dealing with the least number of messages to be exchanged between two players in order to compute the value of a polynomial or rational function depending on an input distributed between the two players. We define a general algebraic model, where the involved functions can be computed with the natural operations additions, multiplications and divisions and possibly with comparisons. We provide various lower bound techniques, mainly for fields of characteristic 0. We then apply this general theory to problems from distributed mechanism design, in particular to the multicast cost sharing problem, and study the number of messages that need to be exchanged to compute the outcome of the mechanism. This addresses a question raised by Feigenbaum, Papadimitriou, and Shenker [9].
机译:在本文中,我们介绍并发展了代数通信复杂性领域,该理论处理两个参与者之间交换的最少消息数,以便根据两个参与者之间分配的输入来计算多项式或有理函数的值玩家。我们定义一个通用的代数模型,其中可以使用自然运算的加法,乘法和除法以及可能的比较来计算所涉及的函数。我们提供了各种下限技术,主要针对特征0的字段。然后,将这一通用理论应用于分布式机制设计中的问题,尤其是多播成本分摊问题,并研究了需要交换的消息数量来计算机制的结果。这解决了Feigenbaum,Papadimitriou和Shenker提出的问题[9]。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号