Archive for CEREMADE

value of a chess game

Posted in pictures, Statistics, University life with tags , , , , , , , , , , , , on April 15, 2020 by xi'an

In our (internal) webinar at CEREMADE today, Miguel Oliu Barton gave a talk on the recent result his student Luc Attia and himself obtained, namely a tractable way of finding the value of a game (when minimax equals maximin), result that got recently published in PNAS:

“Stochastic games were introduced by the Nobel Memorial Prize winner Lloyd Shapley in 1953 to model dynamic interactions in which the environment changes in response to the players’ behavior. The theory of stochastic games and its applications have been studied in several scientific disciplines, including economics, operations research, evolutionary biology, and computer science. In addition, mathematical tools that were used and developed in the study of stochastic games are used by mathematicians and computer scientists in other fields. This paper contributes to the theory of stochastic games by providing a tractable formula for the value of finite competitive stochastic games. This result settles a major open problem which remained unsolved for nearly 40 years.”

While I did not see a direct consequence of this result in regular statistics, I found most interesting the comment made at one point that chess (with forced nullity after repetitions) had a value, by virtue of Zermelo’s theorem. As I had never considered the question (contrary to Shannon!). This value remains unknown.

too many marginals

Posted in Kids, Statistics with tags , , , , , , , on February 3, 2020 by xi'an

This week, the CEREMADE coffee room puzzle was about finding a joint distribution for (X,Y) such that (marginally) X and Y are both U(0,1), while X+Y is U(½,1+½). Beyond the peculiarity of the question, there is a larger scale problem, as to how many (if any) compatible marginals h¹(X,Y), h²(X,Y), h³(X,Y), …, need one constrains the distribution to reconstruct the joint. And wondering if any Gibbs-like scheme is available to simulate the joint.

Prairie chair

Posted in pictures, Statistics, University life with tags , , , , , , , , , , , on October 2, 2019 by xi'an

Today is the launching day of PRAIRIE, one of the four Instituts Interdisciplinaires d’Intelligence Artificielle (3IA) supported by the French government. Taking place in Paris Dauphine, with Yann Le Cun as guest speaker. I have been fortunate to be endowed with one of these chairs for the coming years, along with my CEREMADE colleagues Laurent Cohen and Irène Waldspurger.

Le Monde puzzle [#1075]

Posted in Books, Kids, R with tags , , , , , , , on November 22, 2018 by xi'an

A Le Monde mathematical puzzle from after the competition:

A sequence of five integers can only be modified by subtracting an integer N from two neighbours of an entry and adding 2N to the entry.  Given the configuration below, what is the minimal number of steps to reach non-negative entries everywhere? Is this feasible for any configuration?

As I quickly found a solution by hand in four steps, but missed the mathematical principle behind!, I was not very enthusiastic in trying a simulated annealing version by selecting the place to change inversely proportional to its value, but I eventually tried and also obtained the same solution:

      [,1] [,2] [,3] [,4] [,5]
   -3    1    1    1    1
    1   -1    1    1   -1
    0    1    0    1   -1
   -1    1    0    0    1
    1    0    0    0    0

But (update!) Jean-Louis Fouley came up with one step less!

      [,1] [,2] [,3] [,4] [,5]
   -3    1    1    1    1
    3   -2    1    1   -2
    2    0    0    1   -2
    1    0    0    0    0

The second part of the question is more interesting, but again without a clear mathematical lead, I could only attempt a large number of configurations and check whether all admitted “solutions”. So far none failed.

Le Monde puzzle [#1071]

Posted in Books, Kids with tags , , , , , , , , , , , on October 18, 2018 by xi'an

A “he said she said” Le Monde mathematical puzzle sixth competition problem that reminded me of the “Singapore birthday problem” (nothing to do with the original birthday problem!):

Arwen and Brandwein are privately and respectively given the day and month of Caradoc’s birthday [in the Gregorian calendar] with the information that the month number is at least the day number. Arwen starts by stating she knows Brandwein cannot deduce the birthday, followed by Brandwein who says the same about Arwen. If this “she says he says” goes on for the largest possible number of steps before Arwen says she knows, when is Caradoc’s birthday? Arwen and Brandwein are later given two numbers corresponding to Deirdre’s birthday with no indication of which one is the day and which one is the month. They know both numbers end up with the same digit and that the month number is strictly less than the day number. Arwen states she does not know the date and she knows Brandwein cannot know either. Then Brandwein says he indeed does not the date but he knows whether he got the day or the month. This prompts Arwen to conclude she knows, then Brandwein to do the same. When is Deirdre’s birthday?

Since this was a fairly easy puzzle (and since I had spent too much time debugging the previous R code!), I did not try coding this one but instead drew the possibilities and remove the impossibilities on a blackboard. The first question is quite simple actually since the day numbers stand between 1 and 12 and that each “I cannot know” excludes one of the remaining endpoints, removing first excludes 1 from both lists, then 12, then 2, then …. 8, ending up with 7. And 07/07 as Caradoc’s birthday. The second case sees 13,…,20,23,…,30 eliminated from Arwen’s numbers, then 3,…,10 as well, which eliminates the same numbers from Brandwein’s possibilities. That he knows whether it is a month or a day leaves only 1,2,21,22,31 as possible numbers. Then Arwen’s certainty reduces her numbers to be 2, 21, 22, or 31, and since Brandwein is also sure, the only possible cases are (2,22) and (22,2). Meaning Deirdre’s birthday is on 22/02. I dunno if this symmetry was to be expected! (And I cannot fathom why this puzzle is awarded so many points, when compared with the others.)