On amending the sufficient conditions for Nash implementation

Wu, Haoyang (2011): On amending the sufficient conditions for Nash implementation.

Abstract

Mechanism design, a reverse problem of game theory, is an important branch of economics. Nash implementation is the cornerstone of the theory of mechanism design. The well-known Maskin's theorem describes the sufficient conditions for Nash implementation when the number of agents are at least three. A recent work [H. Wu, Quantum mechanism helps agents combat ``bad'' social choice rules. International Journal of Quantum Information, 2010 (accepted) http://arxiv.org/abs/1002.4294 ] shows that when an additional condition is satisfied, the Maskin's theorem will no longer hold by using a quantum mechanism. Although quantum mechanisms are theoretically feasible, agents cannot benefit from them immediately due to the restriction of current experimental technologies. In this paper, we will go beyond the obstacle of how to realize quantum mechanisms, and propose an algorithmic mechanism which leads to the same results as quantum mechanisms do. Consequently, the sufficent conditions for Nash implementation are amended not only in the quantum world, but also in the real world.

• Item Type: MPRA Paper
• Language: English
• Keywords: Quantum computing; Mechanism design; Nash implementation
• Subjects: D - Microeconomics > D7 - Analysis of Collective Decision-Making > D71 - Social Choice ; Clubs ; Committees ; Associations

References

1. P.W. Shor, Algorithms for quantum computation: discrete logorithms and factoring. \emph{Proceedings of the 35th Annual Symposium on Foundation of Computer Science}, 124-134 (IEEE Comp. Soc. Press, Los Alamitos, CA, 1994).

2. P.W. Shor, Polynomial-time algorithms for prime factorization and discrete logorithms on a quantum computer, \emph{SIAM J. Computing} \textbf{26} (1997) 1484-1509.

3. L.K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the 28th Annual ACM Symposium on Theory of Computing, Philadelphia, PA, USA, 1996, 212-219.

4. L.K. Grover, Quantum mechanics helps in searching for a needle in a haystack, \emph{Phys. Rev. Lett.}, \textbf{79} (1997) 325-328.

5. J. Eisert, M. Wilkens and M. Lewenstein, Quantum games and quantum strategies, \emph{Phys. Rev. Lett.} \textbf{83} (1999) 3077-3080.

6. E. Maskin, Nash equilibrium and welfare optimality, \emph{Rev. Econom. Stud.} \textbf{66} (1999) 23-38.

7. H. Wu, Quantum mechanism helps agents combat ``bad'' social choice rules. \emph{International Journal of Quantum Information}, 2010 (accepted). \\ http://arxiv.org/abs/1002.4294

8. T.D. Ladd, F. Jelezko, R. Laflamme, Y. Nakamura, C. Monroe and J.L. O'Brien, Quantum computers, \emph{Nature}, \textbf{464} (2010) 45-53.

9. R. Serrano, The theory of implementation of social choice rules, \emph{SIAM Review} \textbf{46} (2004) 377-414.

10. A.P. Flitney and L.C.L. Hollenberg, Nash equilibria in quantum games with generalized two-parameter strategies, \emph{Phys. Lett. A} \textbf{363} (2007) 381-388.