PURE SECRET CORRELATION AND FINITE AUTOMATA (JOINT WORK WITH OLIVIER GOSSNER)

AbstractIn this paper we study the conditions in which a team guarantees a successful coordination against a similar opponent. We consider a dynamical situation of a 3-players game in which each player is iden- tied by his ability to implement strategies. If the team payo is the opposite to its opponent one, the optimal coordination is character- ized by the value in correlated strategies of the zero-sum game. The ability of each player i is related to the number of states of thesmall-est machine which implements a strategy of player i, i.e.: mi. The main result states that if the ability of the team is large enough with respect to the ability of his adversary, there exists pure strategies that guarantee the value in correlated strategies. Therefore the pair of pure strategies blocks any strategy of the opponent with the strongest level of punishment. Formally, let G be a 3-player game with nite actions sets A1, A2 and A3 and payo function g for player 3. Let v be the minmax in correlated strategies for player 3. Let A(mi) be the set of automata for player i of size mi. An automaton of player i inputs at each stage an element of Aj Ak, and outputs an element of Ai. An oblivi- ous automaton is an automaton which transitions are independent of the other player's actions. A triple of automata (A(1);A(2);A(3)) 2A(m1) A(m2) A(m3) induces an eventually periodic sequence of actions, and let (A(1);A(2);A(3)) be the average payo of player 3 over a period of this sequence. A consequence of Ben-Porath 1993 is that whenever m3 is subex- ponential in m1 and in m2, there exists correlated automata of 1 and2 against which it cannot be obtained significantly more than v. Fur- thermore, the correlated strategies in the proposition may have sup- port the set of oblivious automata of players 1 and 2.When players 1 and 2 are limited to rely on pure strategies and m3 is very small compared to m1 and m2 (min(m1;m2) >> m3 logm3) , the minmax in pure strategies converges as well to v. This result obtains a consequence of Neyman 1997. Furthermore, the automata of players 1 and 2 can be chosen to be oblivious.Our result, which strengthens the previous one, states that the minmax in pure strategies converges to v but when (min(m1;m2) >> m3. The automata of players 1 and 2 we design in the proof of this result are not oblivious, but are oblivious to player 3. The construc- tion of the strategies of players 1 and 2 rely on techniques introduced in Gossner and Hernandez 2003, and the proof that player 3 cannot obtain significantly more than v on large deviation techniques as in Neyman 1997.

Location: 
Elath Hall, 2nd floor, Feldman Building, Edmond J. Safra Campus
Dates: 
Sunday, May 27, 2007 - 16:15 to 18:00
Old Lecturers: 
PENELOPE HERNANDEZ
Old Lecturers University: 
UNIVERSIDAD DE VALENCIA