In Israel, when a graduate student completes writing his thesis, the thesis is sent to several referees, and based on their reports the university decides whether to grant the Ph.D. degree to the student.
France has a different system. Two referees provide reports that determine whether the student is allowed to defend his thesis. During the defense, a jury made of three judges, the two referees, and the Ph.D. adviser listen to the student’s talk and decides whether to grant the Ph.D. degree to the student or not. Given that the student’s family makes up the majority of the audience, and given that they already prepared a banquet in the adjacent room, the outcome is pretty obvious. I guess that 100 years ago when commuting was more difficult and the student’s family was not in the audience, the outcome varied more than today.
I was invited by Jerome Renault from the University of Toulouse to be a referee of the thesis of his student, Xavier Venel. My description of the French system is based on this experience; I apologize if I made incorrect generalizations. Nicolas Vieille, the second referee and an old friend and co-author, told me that in fact being a referee has also its legal duties: if the thesis is found to be wrong, then the French government might come after you, since they awarded a Ph.D. degree to someone who should not have received it based on your incorrect assessment. I have no idea whether Nicolas was kidding or not, and I do not want to have the French police behind my back, so I read the thesis carefully. To ensure that the jury is in a good mood during the defense, Jerome Renault invited the jury for lunch at Michel Sarran Restaurant, two stars in Michelin. When you visit Toulouse next time, make sure to reserve a table and enjoy lunch between visiting the Cathédrale St. Étienne and the Basilique St. Sernin.
Xavier Venel’s thesis is about Markov decision processes and repeated games. It is very impressive and includes quite a few innovative ideas and new results. Here I would like to share with you one idea.
To prove the existence of an equilibrium we usually employ a fixed point argument. The most commonly used fixed point argument is Brouwer’s Theorem, which states that every continuous function from a compact and convex (and nonempty) set in a finite dimensional space into itself has a fixed point. Consider now a dynamic games in which the state space if of the cardinality of the continuum and the state variable changes from stage to stage. The total payoff to a player, which may be the discounted sum of his stage payoffs or a terminal payoff determined at the end of the game, usually depends on the sequence of states the play visits. It is therefore useful if the following nonexpansiveness condition holds: denoting by q(s,a) the state in the following state when the current state is s and the players played the action vector a, then the distance between q(s1,a) and q(s2,a) is at most the distance between s1 and s2, for every two states s1 and s2 and every action vector a (here it is impliccitly assumed that transitions are deterministic). This condition ensures that if one perturbs slightly the initial state, but keeps fixed the actions chosen by the players, then the perturbed realized play remains close to the original play ad infinitum. It is easy to see how this condition implies nice regularity conditions, and helps proving the existence of an equilibrium.
Let us now consider a specific model: a Markov decision problem with imperfect observation of the state. There are finitely many states of nature and a single player. The true state of nature is chosen at the outset of the game according to a known probability distribution and is not told to the player. At every period the player chooses an action, receives a stage payoff (that he does not observe), and also receives a signal that depends the state of nature and on his action. He can then update his belief on the state of the nature using Bayes rule. The game then continues to the following stage. To transform this problem into the previous setup, define the belief of the player over the set of states of nature as the state variable. This is a simplex, so it is a set of the cardinality of the continuum. Every time the player chooses an action, his belief changes, and with it changes the state variable.The set of probability measures over a compact set K if compact in the weak-* topology, and the topology is metrizable by the Wasserstein’s metric: the distance between two probability measures p1 and p2 is the supremum over all 1-Lipschitz functions f of ∫f(dp1-dp2). The function that assigns to each probability measure and each subset A of K the conditional measure over A is not nonexapnsive: there might be nearby probability measures over K such that, their conditional measures over some set A is far. Xavier Venel noticed that these bad instances do not arise in game situations: when one restricts the functions f to the set of functions that can arise from games, and considers only posterior beliefs that arise in games in which the transition is controlled by one player, then the function that assigns to each prior belief and each signal a posterior belief is nonexapnsive. This allowed Xavier Venel to prove the existence of the uniform value in a much larger class of games than those studied so far. I believe that this new metric on probability measures will prove useful for solving additional problems in the area of repeated games.
After the jury heard Xavier Venel’s talk and asked various questions, it convened to decide of the outcome. Then, in front of Xavier’s family, the head of the jury, Sylvain Sorin, who is the father of the French game theory community, summarized the merits of the candidate and his work, and informed Xavier that the jury found that he deserves the Ph.D. degree and is happy to have him join the clan of game theorists. Next year Xavier will be a post doc at the School of Mathematical Sciences in Tel Aviv University. I am happy that the distance between him and the group in Tel Aviv will shrink.