Heller, Yuval (2005): Minorityproof cheaptalk protocol.
There is a more recent version of this item available. 

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 cheaptalk protocols. We construct a cheaptalk 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 cheaptalk. Furthermore, we demonstrate that in general there is no cheaptalk protocol that is resistant for deviations of half the players.
Item Type:  MPRA Paper 

Original Title:  Minorityproof cheaptalk protocol 
Language:  English 
Keywords:  noncooperative games; cheaptalk; correlated equilibrium; strong equilibrium; coalitionproof equilibrium; faulttolerant 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:  21. May 2015 20:28 
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 , 5362. Aumann, R., 1959. Acceptable points in general cooperative nperson games, in Kuhn, H.W., Luce, R.D. (Eds.), Contributions to the theory of games IV. Princeton University Press, N.J, pp. 287324. Aumann, R., 1974. Subjectivity and correlation in randomized strategies. J. Math. Econ. 1, 6796. Aumman, R., Hart S., 2003. Long cheap talk. Econometrica 71 (6), 16191660. Barany, I., 1992. Fair distribution protocols or how the players replace fortune. Mathematics of Operations Research. 17, 329340. BenOr, M., Goldwasser S., Wigderson A., 1988. Completeness theorems for noncryptographic faulttolerant distributed computation (extended abstract). Proc. 20 STOC, ACM, 110. BenOr M., Rabin T., 1989. Verifiable secret sharing and multiparty protocol with honest majority. In Proc. 21 STOC, 7385, ACM. BenPorath, E., 1998. Communication without mediation: expending the set of equilibrium outcomes by “cheap” preplay procedures. J. Econ. Theory 80, 108122. BenPorath, E., 2003. Cheap talk in games with incomplete information. J. Econ. Theory 108, 4571. Bernheim, B., Peleg, B., Whinston, M., 1987. Coalitionproof Nash equilibria. J. Econ. Theory 42, 112. Bloch F., Dutta B., 2008. Correlated equilibria, incomplete information and coalitional deviations. Games Econ. Behav. (forthcoming). Chaum, D., Crepeau, C., Damgard I., 1988. Multiparty unconditionally secure protocols. Proc. 20 ACM, 1119. Crawford, V., Sobel, J., 1982. Strategic information transmission. Econometrica 50, 579594. 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, NewYork and Melbourne. Eliaz K., 1999. Fault tolerant implementation. Review of Economic Studies, Vol. 69(3), 589610. Forges, F., 1990. Universal mechanisms. Econometrica 58, 13411364. Gerardi, D., 2004. Unmediated communication in games with complete and incomplete information. J. Econ. Theory 114, 104131. Gossner, A., 1998. Secure protocols or how communication generates correlation. J. Econ. Theory 83, 6989. Heller Y., 2008, A minorityproof cheaptalk protocol  an extended version, mimeo, http://www.tau.ac.il/~helleryu/minorityextended.pdf Lepinski, M., Micali, S., Peikert C., Shelat A., 2004. Completely fair SFE and coalitionsafe cheap talk. Proc. 23 ACM, 110. Milgrom, P., Roberts, J., 1996. Coalitionproofness and correlation with arbitrary communication possibilities, Games Econ. Behav. 17, 113128. Moreno, D., Wooders, J., 1996. Coalitionproof equilibrium, Games Econ. Behav. 17, 80113. MolotovRibbentrop 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. Noncooperative games. Ann. Math. 54, 286295. Ray I., 1996. Coalitionproof correlated equilibrium: a definition. Games Econ. Behav. 17, 5679. Ray, I., 1998. Correlated equilibrium as a stable standard of behavior. Rev. Econ. Design, 3, 257269. Urbano, A., Vila J.E, 2002. Computational complexity and communication: coordination in twoplayer games. Econometrica 70 (5), 18931927. 
URI:  https://mpra.ub.unimuenchen.de/id/eprint/15643 
Available Versions of this Item

A minorityproof cheaptalk protocol. (deposited 12. Mar 2008 16:21)
 Minorityproof cheaptalk protocol. (deposited 11. Aug 2009 05:40) [Currently Displayed]