Tata Institute of Fundamental Research
Two Player Games and Playing Them in Parallel
STCS Faculty Seminar
Speaker:
Prahladh Harsha
Organiser:
Ashutosh Gupta
Date:
Friday, 29 May 2015, 16:00 to 17:00
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Consider a 2-player game defined as follows. A referee sends a pair of questions x and y to two players Alice and Bob and accepts if their answers a and b satisfy some predicate. The 2 players are not allowed to communicate once the game commences, however can share some prior randomness, quantum entanglement etc. We will begin by seeing examples of games in which the players have different optimal strategies depending on what they share: randomness, entanglement, no-signalling strategies, etc.
We will then consider the parallel repetition of games and ask if the players have an advantage over answering each of the repetitions independently. Surprisingly, we will show examples of games in which the players have an advantage by co-ordinating their answers across repetitions. Finally, we will show time permitting, we will see some applications of parallel repetition to theoretical computer science.
Image from: Andreas Winter, "Quantum mechanics: The usefulness of uselessness", Nature 466, 1053–1054, Aug 2010.
| Speaker: | Prahladh Harsha |
| Organiser: | Ashutosh Gupta |
| Date: | Friday, 29 May 2015, 16:00 to 17:00 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Consider a 2-player game defined as follows. A referee sends a pair of questions x and y to two players Alice and Bob and accepts if their answers a and b satisfy some predicate. The 2 players are not allowed to communicate once the game commences, however can share some prior randomness, quantum entanglement etc. We will begin by seeing examples of games in which the players have different optimal strategies depending on what they share: randomness, entanglement, no-signalling strategies, etc.
We will then consider the parallel repetition of games and ask if the players have an advantage over answering each of the repetitions independently. Surprisingly, we will show examples of games in which the players have an advantage by co-ordinating their answers across repetitions. Finally, we will show time permitting, we will see some applications of parallel repetition to theoretical computer science.
Image from: Andreas Winter, "Quantum mechanics: The usefulness of uselessness", Nature 466, 1053–1054, Aug 2010.
We will then consider the parallel repetition of games and ask if the players have an advantage over answering each of the repetitions independently. Surprisingly, we will show examples of games in which the players have an advantage by co-ordinating their answers across repetitions. Finally, we will show time permitting, we will see some applications of parallel repetition to theoretical computer science.
Image from: Andreas Winter, "Quantum mechanics: The usefulness of uselessness", Nature 466, 1053–1054, Aug 2010.