You are currently browsing the monthly archive for July 2014.

Over a lunch of burgers and envy, Mallesh Pai and discussed an odd feature of medical reidencies. This post is a summary of that discussion. It began with this question: Who should pay for the apprenticeship portion of a Doctor’s training? In the US, the apprenticeship, residency, is covered by Medicare. This was enshrined’ in the 1965 act that established Medicare:

Educational activities enhance the quality of care in an institution, and it is intended, until the community undertakes to bear such education costs in some other way, that a part of the net cost of such activities (including stipends of trainees, as well as compensation of teachers and other costs) should be borne to an appropriate extent by the hospital insurance program .

House Report, Number 213, 89th Congress, 1st session 32 (1965) and Senate Report, Number 404 Pt. 1 89th Congress 1 Session 36 (1965)).

Each year about $9.5 billion in medicare funds and another$2 billion in medicaid dollars go towards residency programs. There is also state government support (multiplied by Federal matching funds). At 100K residents a year, this translates into about about $100 K per resident. The actual amounts each program receives per resident can vary (we’ve seen figures in the range of$50K to $150K) because of the formula used to compute the subsidy. In 1997, Congress capped the amount that Medicare would provide, which results in about 30K medical school graduates competing for about 22.5K slots. Why should the costs of apprenticeship be borne by the government? Lawyers, also undertake 7 years of studies before they apprentice. The cost of their apprenticeship is borne by the organization that hires them out of law school. What makes Physicians different? Two arguments we are aware of. First, were one to rely on the market to supply physicians, it is possible that we might get to few (think of booms and busts) in some periods. Assuming sufficient risk aversion on the part of society, there will be an interest in ensuring a sufficient supply of physicians. Note similar arguments are also used to justify farm subsidies. In other words, insurance against shortfalls. Interestingly, we know of no Lawyer with the dershowitz’ to make such a claim. Perhaps, Dick the butcher (Henry VI, Part 2 Act 4) has cowed them. The second is summarized in the following from Gbadebo and Reinhardt: “Thus, it might be argued … that the complete self-financing of medical education with interest-bearing debt … would so commercialize the medical profession as to rob it of its traditional ethos to always put the interest of patients above its own. Indeed, it can be argued that even the current extent of partial financing of their education by medical students has so indebted them as to place the profession’s traditional ethos in peril.” Note, the Scottish master said as much: “We trust our health to the physician: our fortune and sometimes our life and reputation to the lawyer and attorney. Such confidence could not safely be reposed in people of a very mean or low condition. Their reward must be such, therefore, as may give them that rank in the society which so important a trust requires. The long time and the great expense which must be laid out in their education, when combined with this circumstance, necessarily enhance still further the price of their labour.” Interestingly, he includes Lawyers. If we turn the clock back to before WWII, Hospitals paid for trainees (since internships were based in hospitals, not medical schools) and recovered the costs from patient charges. Interns were inexpensive and provided cheap labor. After WWII, the GI Bill provides subsidies for graduate medical education, residency slots increased and institutions were able to pass along the costs to insurers. Medicare opened up the spigot and residencies become firmly ensconced in the system. Not only do they provide training but they allow hospitals to perform a variety of other functions such as care for the indigent at lower cost than otherwise. Ignoring the complications associated with the complementary activities that surround residency programs, who should pay for the residency? Three obvious candidates: insurers, hospitals and the doctors themselves. From Coase we know that in a world without frictions, it does not matter. With frictions, who knows? Having medicare pay makes residency slots an endowment to the institution. The slots assign to a hospital will not reflect what’s best for the intern or the healthcare system. Indeed a recent report by from the Institute of Medicine summarizes some of these distortions. However, their response to is urge for better rules governing the distribution of monies. If hospitals themselves pay, its unclear what the effect might be. For example, as residents costs less than doctors, large hospitals my bulk up of residents and reduce their reliance of doctors. However, assuming no increases in the supply of residents, wages for residents will rise etc etc. If insurers pay there might be overprovision of residents. What about doctors? To practice, a doctor must have a license. The renewal fee on a medical license is, at the top end (California), around$450 a year. In Florida it is about half that amount. There are currently about 800K active physicians in the US. To recover $10 billion (current cost of residency programs) one would have to raise the fee by a$1000 a year at least. The average annual salary for the least remunerative specialties is around $150K. At the high end about$400K. From these summary statistics, it does not appear that an extra $1K a year will break the bank, or corrupt physicians, particularly if it is pegged as a percentage rather than flat amount. The monies collected can be funneled to the program in which the physician completed his or her residency. Four agents are observing infinite streams of outcomes in ${\{S,F\}}$. None of them knows the future outcomes and as good Bayesianists they represent their beliefs about unknowns as probability distributions: • Agent 1 believes that outcomes are i.i.d. with probability ${1/2}$ of success. • Agent 2 believes that outcomes are i.i.d. with probability ${\theta}$ of success. She does not know ${\theta}$; She believes that ${\theta}$ is either ${2/3}$ or ${1/3}$, and attaches probability ${1/2}$ to each possibility. • Agent 3 believes that outcomes follow a markov process: every day’s outcome equals yesterday’s outcome with probability ${3/4}$. • Agent 4 believes that outcomes follow a markov process: every day’s outcome equals yesterday’s outcome with probability ${\theta}$. She does not know ${\theta}$; Her belief about ${\theta}$ is the uniform distribution over ${[0,1]}$. I denote by ${\mu_1,\dots,\mu_4\in\Delta\left(\{S,F\}^\mathbb{N}\right)}$ the agents’ beliefs about future outcomes. We have an intuition that Agents 2 and 4 are in a different situations from Agents 1 and 3, in the sense that are uncertain about some fundamental properties of the stochastic process they are facing. I will say that they have structural uncertainty’. The purpose of this post is to formalize this intuition. More explicitly, I am looking for a property of a belief ${\mu}$ over ${\Omega}$ that will distinguish between beliefs that reflect some structural uncertainty and beliefs that don’t. This property is ergodicity. Definition 1 Let ${\zeta_0,\zeta_1,\dots}$ be a stationary process with values in some finite set ${A}$ of outcomes. The process is ergodic if for every block ${\bar a=(a_0,\dots,a_{k})}$ of outcomes it holds that $\displaystyle \begin{array}{rcl} \lim_{n\rightarrow\infty}&\frac{\#\left\{0\le t < n|\zeta_t=a_0,\dots,\zeta_{t+k}=a_{k}\right\}}{n}=\\&\mathop{\mathbb P}(\zeta_0=a_0,\dots,\zeta_{k}=a_{k})~\text{a.s}.\end{array}$ A belief ${\mu\in \Delta(A^\mathbb{N})}$ is ergodic if it is the distribution of an ergodic process Before I explain the definition let me write the ergodicity condition for the special case of the block ${\bar a=(a)}$ for some ${a\in A}$ (this is a block of size 1): $\displaystyle \lim_{n\rightarrow\infty}\frac{\#\left\{0\le t < n|\zeta_t=a\right\}}{n}=\mathop{\mathbb P}(\zeta_0=a)~\text{a.s}.\ \ \ \ \ (1)$ In the right side of (1) we have the (subjective) probability that on day ${0}$ we will see the outcome ${a}$. Because of stationarity this is also the belief that we will see the outcome ${a}$ on every other day. In the left side of (1) we have no probabilities at all. What is written there is the frequency of appearances of the outcome ${a}$ in the realized sequence. This frequency is objective and has nothing to do with our beliefs. Therefore, the probabilities that a Bayesian agent with ergodic belief attaches to observing some outcome is a number that can be measured from the process: just observe it long enough and check the frequency in which this outcome appears. In a way, for ergodic processes the frequentist and subjective interpretations of probability coincide, but there are legitimate caveats to this statement, which I am not gonna delve into because my subject matter is not the meaning of probability. For my purpose it’s enough that ergodicity captures the intuition we have about the four agents I started with: Agents 1 and 3 both give probability ${1/2}$ to success in each day. This means that if they are sold a lottery ticket that gives a prize if there is a success at day, say, 172, they both price this lottery ticket the same way. However, Agent 1 is certain that in the long run the frequency of success will be ${1/2}$. Agent 2 is certain that it will be either ${2/3}$ or ${1/3}$. In fancy words, ${\mu_1}$ is ergodic and ${\mu_2}$ is not. So, ergodic processes capture our intuition of processes without structural uncertainty’. What about situations with uncertainty ? What mathematical creature captures this uncertainty ? Agent 2’s uncertainty seems to be captured by some probability distribution over two ergodic processes — the process “i.i.d. ${2/3}$” and the process “i.i.d. ${1/3}$”. Agent 2 is uncertain which of these processes he is facing. Agent 4’s uncertainty is captured by some probability distribution over a continuum of markov (ergodic) processes. This is a general phenomena: Theorem 2 (The ergodic decomposition theorem) Let ${\mathcal{E}}$ be the set of ergodic distributions over ${A^\mathbb{N}}$. Then for every stationary belief ${\mu\in\Delta(A^\mathbb{N})}$ there exists a unique distribution ${\lambda}$ over ${\mathcal{E}}$ such that ${\mu=\int \theta~\lambda(\text{d}\theta)}$. The probability distribution ${\lambda}$ captures uncertainty about the structure of the process. In the case that ${\mu}$ is an ergodic processes ${\lambda}$ is degenerated and there is no structural uncertainty. Two words of caution: First, my definition of ergodic processes is not the one you will see in textbooks. The equivalence to the textbook definition is an immediate consequence of the so called ergodic theorem, which is a generalization of the law of large numbers for ergodic processes. Second, my use of the word uncertainty’ is not universally accepted. The term traces back at least to Frank Knight, who made the distinction between risk or “measurable uncertainty” and what is now called “Knightian uncertainty” which cannot be measured. Since Knight wrote in English and not in Mathematish I don’t know what he meant, but modern decision theorists, mesmerized by the Ellsberg Paradox, usually interpret risk as a Bayesian situation and Knightian uncertainty, or “ambiguity”, as a situation which falls outside the Bayesian paradigm. So if I understand correctly they will view the situations of these four agents mentioned above as situations of risk only without uncertainty. The way in which I use “structural uncertainty” was used in several theory papers. See this paper of Jonathan and Nabil. And this and the paper which I am advertising in these posts, about disappearance of uncertainty over time. (I am sure there are more.) To be continued… Abraham Neyman and Sergiu Hart are two of the prominent mathematical game theorists to date. Neyman contributed immensely to the study of the Shapley value, stochastic games, and repeated games and complexity. Hart contributed significantly to the study of correlated equilibrium and adaptive processes leading to it, value theory, and formation of coalitions. Both Abraham and Sergiu will be 66 next year. To celebrate this rare occasion, the Center for the Study of Rationality at the Hebrew University of Jerusalem organizes two conferences, one in honor of each of them. The conference in honor of Abraham will be held on June 16–19, 2015, and the conference in honor of Sergiu will follow on June 21–24, 2015. Mark the dates and reserve tickets. You may have heard about ResearchGate, the so called facebook of scientists. Yes, another social network. Its structure is actually more similar to twitter: each user is a node and you can create directed edges from yourself to other users. Since I finally got rid of my facebook account (I am a Bellwether. In five years all the cool guys will not be on facebook), I decided to try ResearchGate. I wanted a stable platform to upload my preferable versions of my papers so that they will be the first to pop up on google. Also, I figured if I am returning to blogging then I need stuff to bitch about. ResearchGate only partially fulfill the first goal, but it does pretty well with the second. Last week I wrote a post about two issues with Elsevier’s e-system, which is the system that all journals run by Elsevier, including Games and Economic Behavior and Journal of Mathematical Economics, use for handling submissions: the fact that sometimes reviewers can see the blinded comments that other reviewers wrote to the editor, and the user agreement that allows Elsevier to change its terms without notifying the users. After I corresponded with the editors of Games and Economic Behavior and Journal of Mathematical Economics and with the Economics Editor of Elsevier, the reason for the privacy breach became clear: the e-system allows each editor to choose whether the blinded comments of one referee to the author and the blinded comments of one referee to the editor will be seen by other reviewers. For each type of blinded comments the editor can decide whether to show it to all reviewers or not. Each editor makes his or her own choice. I guess that often editors are not aware of this option, and they do not know what was the choice that the previous editor, or the one before him, made. Apparently, the configuration of Games and Economic Behavior was to allow reviewers to see only the blinded comments to the author, while the configuration of Journal of Mathematical Economics was to allow reviewers to see both types of blinded comments. Once the source of the problem became clear, Atsushi Kajii, the editor of Journal of Mathematical Economics decided to change the configuration, so that the blinded comments of reviewers to the editor will not be seen by other reviewers. I guess that in few days this change will become effective. Elsevier also promised to notify all of its journals, in which the configuration was like that of JME, about this privacy issue, and let the editors decide whether they want to keep this configuration or change it. In case this configuration remains, they will add a warning that warns the referee that the blinded comments can be read by other reviewers. I am happy that the privacy breach came to a good end, and that in the future the e-system will keep the privacy the referees. Regarding the second issue, Elsevier is not willing to change its user agreement. Reading the user agreements of other publishers, like Springer and INFORMS, shows that user agreements can be reasonable, and not all publishers keep the right to change the user agreement without notifying the users. The Economics Editor of Elsevier wrote: “This clause is not unreasonable as the user can choose to discontinue the services at any time.” As I already wrote in the previous post, I choose to discontinue the service. When I give a presentation about expert testing there is often a moment in which it dawns for the first time on somebody in the audience that I am not assuming that the processes are stationary or i.i.d. This is understandable. In most modeling sciences and in statistics stationarity is a natural assumption about a stochastic process and is often made without stating. In fact most processes one comes around are stationary or some derivation of a stationary process (think the white noise, or i.i.d. sampling, or markov chains in their steady state). On the other hand, most game theorists and micro-economists who work with uncertainty don’t know what is a stationary process even if they have heard the word (This is a time for you to pause and ask yourself if you know what’s stationary process). So a couple of introductory words about stationary processes is a good starting point to promote my paper with Nabil First, a definition: A stationary process is a sequence ${\zeta_0,\zeta_1,\dots}$ of random variables such that the joint distribution of ${(\zeta_n,\zeta_{n+1},\dots)}$ is the same for all ${n}$-s. More explicitly, suppose that the variables assume values in some finite set ${A}$ of outcomes. Stationarity means that for every ${a_0,\dots,a_k\in A}$, the probability ${\mathop{\mathbb P}(\zeta_n=a_0,\dots,\zeta_{n+k}=a_{n+k})}$ is independent in ${n}$. As usual, one can talk in the language of random variables or in the language of distributions, which we Bayesianists also call beliefs. A belief ${\mu\in\Delta(A^\mathbb{N})}$ about the infinite future is stationary if it is the distribution of a stationary process. Stationarity means that Bob, who starts observing the process at day ${n=0}$, does not view this specific day as having any cosmic significance. When Alice arrives two weeks later at day ${n=14}$ and starts observing the process she has the same belief about her future as Bob had when he first arrives (Note that Bob’s view at day ${n=14}$ about what comes ahead might be different from Alice’s since he has learned something meanwhile, more on that later). In other words, each agent can denote by ${0}$ the first day in which they start observing the process, but there is nothing in the process itself that day ${0}$ corresponds to. In fact, when talking about stationary processes it will clear our thinking if we think of them as having infinite past and infinite future ${\dots,\zeta_{-2},\zeta_{-1},\zeta_0,\zeta_1,\zeta_2,\dots}$. We just happen to pop up at day ${0}$. The first example of a stationary process is an i.i.d. process, such as the outcomes of repeated tossing of a coin with hsome probability ${\theta}$ of success. If the probability of success is unknown then a Bayesian agent must have some prior ${\lambda\in \Delta([0,1])}$ about ${\theta}$: The agent believes that ${\theta}$ is randomized according to ${\lambda}$ and then the outcomes are i.i.d. conditioned on ${\theta}$. A famous theorem of De-Finetti (wikipedia) characterizes all beliefs that are mixtures of i.i.d.’ in this sense. All these beliefs are stationary. Another example of stationary processes is Markov processes in their steady state. Again, we can generalize to situations in which the transition matrix is not known and one has some belief about it. Such situations are rather natural, but I don’t think there is a nice characterization of the processes that are mixtures of markov processes in this sense (that is, I don’t know of a De-Finetti Theorem for markov processes.) Still more general example is Markov process of some finite memory, for example when the outcome today depends on the history only through the outcomes of the last two days. As an example of a stationary process which is not a Markov process of any finite memory consider a Hidden Markov model, according to which the outcome at every day is a function of an underlying, unobserved Markov process. If the hidden process is stationary then so is the observed process. This is an important property of stationary processes, which is obvious from the definition: Theorem 1 Let ${\dots,\zeta_{-2},\zeta_{-1},\zeta_0,\zeta_1,\dots}$ be a stationary process with values in some finite set ${H}$. Then the process ${\dots,f(\zeta_{-2}),f(\zeta_{-1}),f(\zeta_0),f(\zeta_1),\dots}$ is stationary for every function ${f:H\rightarrow A}$. As can be seen in all these examples, when one lives in a stationary environment then one has some (possibly degenerated) uncertainty about the parameters of the process. For example we have some uncertainty about the parameter of the coin or the markov chain or the hidden markov process. I still haven’t defined however what I mean by parameters of the process; What lurks behind is the ergodic decomposition theorem, which is an analogue of De-Finetti’s Theorem for stationary processes. I will talk about it in my next post. For now, let me say a word about the implications of uncertainty about parameters in economic modeling, which may account in part for the relative rareness of stationary processes in microeconomics (I will give another reason for that misfortune later): Let Craig be a rational agent (=Bayesian expected utility maximizer) who lives in a stationary environment in which a coin is tossed every day. Craig has some uncertainty over the parameter of the coin, represented by a belief ${\lambda\in\Delta([0,1])}$. At every day, before observing the outcome of the coin, Craig takes an action. Craig’s payoff at every day depends on the action he took, the outcome of the coin, and possibly some other random objects which follow a stationary process observed by Craig. We observe the sequence of Craig’s actions. This process is not generally a stationary process. The reason is that Craig’s actions are functions of his posterior beliefs about the parameter of the coin, and this posterior belief does not follow a stationary process: as time goes by, Craig learns the parameter of the coin. His behavior in day ${0}$, when he doesn’t know the parameter is typically different from his behavior at day ${14}$ when he already has a good idea about the parameter. I said earlier that in stationarity environment, the point in time which we denote by ${0}$ does not correspond to anything about the process itself but only reflect the point in time in which we start observing the process. In this example this is indeed the case with Craig, who starts observing the coin process at time ${0}$. It is not true for us. Our subject matter is not the coin, but Craig. And time ${0}$ has a special meaning for Craig. Bottom line: Rational agents in a stationary environment will typically not behave in a stationary way. To be continued… The last of the trio, Harold Kuhn, passed away on July 2nd, 2014. Upon hearing the news, I was moved to dig up some old lecture notes of Kuhn’s in which KTK is stated an proved. I’ve been carrying them around with me since 1981. From the condition they are in, this must have been the last time I looked at them. With good reason, for as I re-read them, it dawned upon me how much of them I had absorbed and taken to be my own thoughts. Kuhn motivates the KTK theorem by replacing the non-linear functions by their first order Taylor approximations. This turns the exercise into a linear program. The LP duality theorem suggests the theorem to be proved, and the separating hyperplane theorem does the rest. For details see the relevant chapter of my book. The notes go on to describe Kuhn and Tucker’s excitement and subsequent despair as they uncover a counterexample and the need for a constraint qualification. William Karush, who passed in 1997, had arrived at the same theorem many years earlier in his 1939 University of Chicago Masters Thesis (Kuhn-Tucker is 1951). When Kuhn learned of Karush’s contribution through a reading of Takayama’s book on Mathematical Economics. Upon doing so he wrote Karush: In March I am talking at an AMS Symposium on “Nonlinear Programming – A Historical View.” Last summer I learned through reading Takayama’s Mathematical Economics of your 1939 Master’s Thesis and have obtained a copy. First, let me say that you have clear priority on the results known as the Kuhn–Tucker conditions (including the constraint qualification). I intend to set the record as straight as I can in my talk. The missive closes with this paragraph: Dick Cottle, who organized the session, has been told of my plans to rewrite history and says you must be a saint’ not to complain about the absence of recognition. Al Tucker remembers you from RAND, wonders why you never called this to his attention and sends his best regards. Karush’s reply, 6 days later, equally gracious: Thank you for your most gracious letter. I appreciate your thoughtfulness in wanting to draw attention to my early work. If you ask why I did not bring up the matter of priority before, perhaps the answer lies in what is now happening – I am not only going to get credit for my work, but I am going to crowned a “saint”. Games and Economic Behavior, Journal of Economic Theory, Journal of Mathematical Economics, and Economics Letters are four journals that publish game theoretic papers and are published by Elsevier. They all use Elsevier e-system to handle submissions. I already talked in the past about the difficulty of operating these e-systems. Rakesh discussed the boycott against Elsevier. Recently I had some experience that made me stop using the Elsevier’s system altogether, even though I serve on the editorial board of Games and Economic Behavior. I will not use Émile Zola’s everlasting words for such an earthly matter; I will simply tell my experience. 1) The e-system seems to be sometimes insecure. I was surprised when a referee with whom I consulted on the evaluation a paper (for GEB) told me that the system showed to him the private message that the other referee wrote to me, and that the same thing happened to him with JME. To prove his point, he sent to me screenshots with the private letter of the other referee for JME. 2) The user agreement of Elsevier is a contract that one should never agree to sign. I guess no one bothered to read the user agreement of Elsevier. I did. The first paragraph binds us to the agreement: This Registered User Agreement (“Agreement”) sets forth the terms and conditions governing the use of the Elsevier websites, online services and interactive applications (each, a “Service”) by registered users. By becoming a registered user, completing the online registration process and checking the box “I have read and understand the Registered User Agreement and agree to be bound by all of its terms” on the registration page, and using the Service, you agree to be bound by all of the terms and conditions of this Agreement. The fourth paragraph, titled “changes” says that any change made to the contract is effective immediately, and so it binds you. If you want to make sure they did not add some paragraph to which you disagree, you must read the whole user agreement every time you use the system. Elsevier reserves the right to update, revise, supplement and otherwise modify this Agreement from time to time. Any such changes will be effective immediately and incorporated into this Agreement. Registered users are encouraged to review the most current version of the Agreement on a periodic basis for changes. Your continued use of a Service following the posting of any changes constitutes your acceptance of those changes. I contacted Elsevier about the user agreement and got the following response: The Elsevier website terms and conditions (see http://www.elsevier.com/legal/elsevier-website-terms-and-conditions) cannot be customized upon request; however, these terms and conditions do not often change and notification would be provided via the “Last revised” date at the bottom of this page. The current terms and conditions were Last revised: 26 August 2010. Well, it is comforting that they did not make any change in the past four years, but will Elsevier’s CEO agree to open an account in a bank that has the “change” paragraph in the contract? I stopped using the e-system of Elsevier, both as a referee and as an editor. One of the most engaging books of academic politics, is C. P. Snow’s The Masters’. In it, a scene describing the debate between factions (Science and Arts) over who should be elected to a college fellowship. The master is in the Arts camp. One of the Science camp urges his candidate upon the college with these words (from memory, as my copy is beyond my reach): “He has written the absolute last word on the subject.” To which the master, responds: “Why can’t you chaps ever have the first word on the subject?” As the narrator, Eliot notes, it was an impolitic response, but recognizes that the master could not resist because it felt good on the tongue. From Swansea comes another example of the inability to resist something that felt good on the tongue. A note from the head of Swansea University’s school of management to his colleagues (do they still have those at UK universities?): Some wags call for the removal of some or all of the school’s top management team. Yes, well don’t hold your breath. Or actually, do. 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.