Minority-proof cheap-talk protocol

Heller, Yuval (2005): Minority-proof cheap-talk protocol.

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
• 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

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.