Lower Bounds on Implementing Robust and Resilient Mediators
We provide new and tight lower bounds on the ability of players to implement equilibria using cheap talk, that is, just allowing communication among the players. One of our main results is that, in general, it is impossible to implement three-player Nash
- PDF / 454,785 Bytes
- 18 Pages / 430 x 660 pts Page_size
- 76 Downloads / 193 Views
Hebrew University [email protected] 2 Hebrew University [email protected] 3 Cornell University [email protected]
Abstract. We provide new and tight lower bounds on the ability of players to implement equilibria using cheap talk, that is, just allowing communication among the players. One of our main results is that, in general, it is impossible to implement three-player Nash equilibria in a bounded number of rounds. We also give the first rigorous connection between Byzantine agreement lower bounds and lower bounds on implementation. To this end we consider a number of variants of Byzantine agreement and introduce reduction arguments. We also give lower bounds on the running time of two player implementations. All our results extended to lower bounds on (k, t)-robust equilibria, a solution concept that tolerates deviations by coalitions of size up to k and deviations by up to t players with unknown utilities (who may be malicious).
1
Introduction
The question of whether a problem in a multiagent system that can be solved with a trusted mediator can be solved by just the agents in the system, without the mediator, has attracted a great deal of attention in both computer science (particularly in the cryptography community) and game theory. In cryptography, the focus on the problem has been on secure multiparty computation. Here it is assumed that each agent i has some private information xi . Fix functions f1 , . . . , fn . The goal is have agent i learn fi (x1 , . . . , xn ) without learning anything about xj for j = i beyond what is revealed by the value of fi (x1 , . . . , xn ). With a trusted mediator, this is trivial: each agent i just gives the mediator its private value xi ; the mediator then sends each agent i the value fi (x1 , . . . , xn ). Work on
Part of the work was done while the author visited Cornell university. The work was funded in part by ISF, ISOC, NSF, CCR, and AFOSR. Supported in part by NSF under grants CCR-0208535, ITR-0325453, and IIS0534064, by ONR under grant N00014-01-10-511, by the DoD Multidisciplinary University Research Initiative (MURI) program administered by the ONR under grants N00014-01-1-0795 and N00014-04-1-0725, and by AFOSR under grant FA9550-05-10055.
R. Canetti (Ed.): TCC 2008, LNCS 4948, pp. 302–319, 2008. c International Association for Cryptologic Research 2008
Lower Bounds on Implementing Robust and Resilient Mediators
303
multiparty computation (see [18] for a survey) provides conditions under which this can be done. In game theory, the focus has been on whether an equilibrium in a game with a mediator can be implemented using what is called cheap talk — that is, just by players communicating among themselves (see [28] for a survey). There is a great deal of overlap between the problems studied in computer science and game theory. But there are some significant differences. Perhaps the most significant difference is that, in the computer science literature, the interest has been in doing multiparty computation in the presence of possibly malicio
Data Loading...
