Heller, Yuval (2005): Minority-proof cheap-talk protocol.
![Warning](/style/images/warning.png)
Preview |
PDF
MPRA_paper_15643.pdf Download (232kB) | Preview |
Abstract
This paper analyzes the implementation of correlated equilibria that are immune to joint deviations of coalitions by cheap-talk protocols. We construct a cheap-talk protocol that is resistant to deviations of fewer than half the players, and using it, we show that a large set of correlated equilibria can be implemented as Nash equilibria in the extended game with cheap-talk. Furthermore, we demonstrate that in general there is no cheap-talk protocol that is resistant for deviations of half the players.
Item Type: | MPRA Paper |
---|---|
Original Title: | Minority-proof cheap-talk protocol |
Language: | English |
Keywords: | non-cooperative games; cheap-talk; correlated equilibrium; strong equilibrium; coalition-proof equilibrium; fault-tolerant distributed computation |
Subjects: | C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C72 - Noncooperative Games |
Item ID: | 15643 |
Depositing User: | Yuval Heller |
Date Deposited: | 11 Aug 2009 05:40 |
Last Modified: | 04 Oct 2019 00:43 |
References: | Abraham I., Dolev D., Gonen R., Halpern J., 2006.Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation. Proc. 25 ACM , 53-62. Aumann, R., 1959. Acceptable points in general cooperative n-person games, in Kuhn, H.W., Luce, R.D. (Eds.), Contributions to the theory of games IV. Princeton University Press, N.J, pp. 287-324. Aumann, R., 1974. Subjectivity and correlation in randomized strategies. J. Math. Econ. 1, 67-96. Aumman, R., Hart S., 2003. Long cheap talk. Econometrica 71 (6), 1619-1660. Barany, I., 1992. Fair distribution protocols or how the players replace fortune. Mathematics of Operations Research. 17, 329-340. Ben-Or, M., Goldwasser S., Wigderson A., 1988. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). Proc. 20 STOC, ACM, 1-10. Ben-Or M., Rabin T., 1989. Verifiable secret sharing and multiparty protocol with honest majority. In Proc. 21 STOC, 73-85, ACM. Ben-Porath, E., 1998. Communication without mediation: expending the set of equilibrium outcomes by “cheap” pre-play procedures. J. Econ. Theory 80, 108-122. Ben-Porath, E., 2003. Cheap talk in games with incomplete information. J. Econ. Theory 108, 45-71. Bernheim, B., Peleg, B., Whinston, M., 1987. Coalition-proof Nash equilibria. J. Econ. Theory 42, 1-12. Bloch F., Dutta B., 2008. Correlated equilibria, incomplete information and coalitional deviations. Games Econ. Behav. (forthcoming). Chaum, D., Crepeau, C., Damgard I., 1988. Multi-party unconditionally secure protocols. Proc. 20 ACM, 11-19. Crawford, V., Sobel, J., 1982. Strategic information transmission. Econometrica 50, 579-594. Einy, E., Peleg B., 1995. Coalition proof communication equilibria. In: Social Choice, Welfare & Ethics (W. Barnett, H. Moulin, M. Salles and N. Schofield, eds.), Cambridge, New-York and Melbourne. Eliaz K., 1999. Fault tolerant implementation. Review of Economic Studies, Vol. 69(3), 589-610. Forges, F., 1990. Universal mechanisms. Econometrica 58, 1341-1364. Gerardi, D., 2004. Unmediated communication in games with complete and incomplete information. J. Econ. Theory 114, 104-131. Gossner, A., 1998. Secure protocols or how communication generates correlation. J. Econ. Theory 83, 69-89. Heller Y., 2008, A minority-proof cheap-talk protocol - an extended version, mimeo, http://www.tau.ac.il/~helleryu/minority-extended.pdf Lepinski, M., Micali, S., Peikert C., Shelat A., 2004. Completely fair SFE and coalition-safe cheap talk. Proc. 23 ACM, 1-10. Milgrom, P., Roberts, J., 1996. Coalition-proofness and correlation with arbitrary communication possibilities, Games Econ. Behav. 17, 113-128. Moreno, D., Wooders, J., 1996. Coalition-proof equilibrium, Games Econ. Behav. 17, 80-113. Molotov-Ribbentrop Pact, 1939. Modern history sourcebook edited by Paul Halsall (1997), http://www.fordham.edu/halsall/mod/1939pact.html (visited in November 2008). Nash, J.F., 1951. Non-cooperative games. Ann. Math. 54, 286-295. Ray I., 1996. Coalition-proof correlated equilibrium: a definition. Games Econ. Behav. 17, 56-79. Ray, I., 1998. Correlated equilibrium as a stable standard of behavior. Rev. Econ. Design, 3, 257-269. Urbano, A., Vila J.E, 2002. Computational complexity and communication: coordination in two-player games. Econometrica 70 (5), 1893-1927. |
URI: | https://mpra.ub.uni-muenchen.de/id/eprint/15643 |
Available Versions of this Item
-
A minority-proof cheap-talk protocol. (deposited 12 Mar 2008 16:21)
- Minority-proof cheap-talk protocol. (deposited 11 Aug 2009 05:40) [Currently Displayed]