Speaker: Shengyu Zhang CUHK
Time: 2010-12-16 14:00-2010-12-16 15:00
Venue: FIT 1-222
Download: Click!

Abstract:

Game theory has been an interesting and important field in applied mathematics, and the last decade witnessed a large collection of literature on quantum game theory. Despite the rapid development, almost all previous work on strategic games focus on qualitative questions on specific games of small sizes, and many of them made ad hoc assumptions in their models. In this paper, we propose a natural, simple, yet rich model to extend the notions of Nash and correlated  equilibria of (classical) strategic games to the quantum setting, in which we then study the relations between classical and quantum equilibria. Unlike the previous work, we address the following fundamental and quantitative question for general games:

How much “advantage” can playing quantum strategies provide, if any?

Two measures of the advantage are studied. 1. A natural measure is the increase of payoff. We consider natural mappings between classical and quantum states, and study how well those mappings preserve the equilibrium properties. Among other results, we exhibit correlated equilibrium p whose quantum superposition counterpart $\sum_s \sqrt{p(s)}\ket{s}$ is far from being a quantum correlated equilibrium; actually a player can increase her payoff from almost 0 to almost 1 in a [0,1]-normalized game. We achieve this by a tensor product construction on carefully designed base cases. 2. For studying the hardness of generating correlated equilibria, we propose to examine correlation complexity, a new complexity measure for correlation generation. We show that there are n-bit correlated equilibria which can be generated by only one EPR pair followed by local operation (without communication), but need at least log(n) classical shared random bits plus communication. The randomized lower bound can be improved to n, the best possible, assuming an even much weaker version of a recent conjecture in linear algebra. We believe that the correlation complexity, as a complexity-theoretical counterpart of the celebrated Bell's inequality, has independent interest in both physics and computational complexity theory and deserves more explorations.

Short Bio:

Shengyu Zhang received his B.S. in Mathematics at Fudan University in 1999, his M.S. in Computer Science at Tsinghua University in 2002, and his Ph.D. in Computer Science at Princeton University in 2006. After working in NEC Laboratories America for a summer, and in California Institute of Technology for two years as a postdoc, he joined The Chinese University of Hong Kong as an assistant professor in Department of Computer Science and Engineering. Zhang’s main research interest is quantum computing, computational complexity such as query complexity and communication complexity, and algorithm designing for networks related problems.