Roscoff is a village at the north-west corner of France, located on a small piece of land that protrudes into the English canal. Right here, in 1548, the six-year-old Mary, Queen of Scots, having been betrothed to the Dauphin François, disembarks.
As far as I understood, the most common sights in the area are tourists and sea food. As far as I can tell, the main advantage of Roscoff is the Laboratoire Biologique, which is used to host conferences. Every now and then the French game theory group makes use of this facility and organizes a conference in this secluded place. The first week of July was one of these nows and thens. This is my third time to attend the Roscoff conference, and I enjoyed meeting colleagues, the talks, and the vegetarian food that all non-sea-food eaters got.
Here I will tell you about one of the talks by Roberto Cominetti.
Brouwer’s fixed point theorem states that every continuous function $f$ that is defined on a compact and convex subset $X$ of a Euclidean space has a fixed point. When the function $f$ is a contraction, that is, when there is $ρ ∈ [0,1)$ such that $d(f(x),f(y)) ≤ ρ d(x,y)$ for every $x,y \in X$, then Banach’s fixed point theorem tell us that there is a unique fixed point $x*$ and there is an algorithm to approximate it: choose an arbitrary point $x_0 ∈ X$ and define inductively $x_{k+1} = f(x_k)$. The sequence $(x_k)$ converges to $x*$ at an exponential rate.
When the function $f$ is non-expansive, that is, $d(f(x),f(y)) \leq d(x,y)$ for every $x,y \in X$, there may be more than a single fixed point (e.g., $f$ is the identity) and the sequence defined above need not converge to a fixed point (e.g., a rotation in the unit circle).
In his talk, Roberto talked about a procedure that does converge to a fixed point when $f$ is non-expansive. Let $(α_k)$ be a sequence of numbers in $(0,1)$. Choose $x_0 ∈ X$ in an arbitrary way and define inductively $x_{k+1} = α_{k+1} f(x_k) + (1-α_{k+1}) x_k$. Surprisingly enough, under this definition the distance $d(x_k,f(x_k))$ is bounded by
d(x_k,f(x_k)) ≤ C diameter(X) / \sqrt( α_1 (1-α_1) + α_2 (1-α_2) + … + α_n (1-α_n) ),
where C = 1/\sqrt(π).
In particular, if the denominator goes to infinity, which happens, for example, if the sequence $(α_k)$ is constant, then the sequence $(x_k)$ converges to a fixed point. Since the function that assigns to each two-player zero-sum strategic-form game its value is non-expansive, this result can become handy in various situations.
This is a good opportunity to thank the organizers of the conference, mainly Marc Quincampoix and Catherine Rainer, who made a great job in organizing the week.
3 comments
July 11, 2014 at 2:55 pm
Ali Jadbbaie
HI Ricky, I believe this is the Mann Iteration, which is a special case of the Ishikawa iteration, for finding fixed points of non-expansive maps.
W. R. Mann, Mean value methods in iteration, Proc. Amer. Math. Soc. 4 (1953), 506–510.
S. Ishikawa. “Fixed points by a new iteration method.” Proceedings of the American Mathematical Society 44, no. 1 (1974): 147-150.
July 12, 2014 at 1:05 pm
Eilon
Thanks, Ali. You are absolutely correct. As you said, it was known that this iteration converges to a fixed point. However, the rate of convergence was not known, and it was conjectured by Baillon and Bruck that the rate is $C diameter(X) / \sqrt( α_1 (1-α_1) + α_2 (1-α_2) + … + α_n (1-α_n) )$ for some fixed $C$. Roberto proved that $C$ is at most $1/sqrt(π).
Eilon
July 14, 2014 at 12:33 pm
Ali Jadbabaie
Sorry, you are right. I should have realized that rate was the main result.