# Group Theory, Game Theory, a bit of Philosophy and a post in Tao's blog

I've decided to write this post after reading the incredibly beautiful and highly recomended post by Terence Tao http://terrytao.wordpress.com/2007/06/25/ultrafilters-nonstandard-analysis-and-epsilon-management

Added: I'd like to try to explain why I think that some things should be true, because it seems to me a nice example of how mathematical properties can be argued from a very different field, using some ''philosophically evident principles''. If the reader does not like motivations/speculations, (s)he can also skip directly to the Conjecture and the Main Question which are mathematically self-contained.

Let's make a bit of warm-up playing the following game: I choose an integer number $x$ and you choose another integer number $y$. If $x+y$ is even, I win and you give me one dollar; otherwise you win and I give you one dollar.

This situation is very easy, since the natural way to play for each player is to choose with probability $\frac{1}{2}$ an even number and with the same probability an odd number. These strategies turn out to be a Nash equilibrium. It is also clear what is happening from a philophical point of view: the two players use the information about the winning set, the set of even numbers, to reduce the problem in $\mathbb Z/2\mathbb Z$. At this point they do not have any other information and so they choose casually an element in this quotient.

Now let's consider a bit more complicated situation: this time I win if $x+y>0$. Now, there is no possible reduction to a finite quotient, but the structure of the winning set still carries some information. The natural way to play is that I choose a very big positive number and you choose a very big (in absolute value) negative number. What we are doing is just using the information carried by the winning set to restrict our possible moves. Now we have no other information and so we choose casually (i.e. uniformly) in this reduced set. Here come up the problems. I have certainly read somewhere (for instance, more or less explicitly, in Tao's post) and it is my convinction that finitely additive translation invariant probability measures generalize the notion of uniformity. So, putting together this general notion of uniformity and the fact that the unique information that we handle is that the winning set is $\mathbb N$, it seems that the natural way to play for me would be to use a finitely additive probability measure $\lambda^+$ which gives measure $1$ to the natural numbers inside the integers and such that $\lambda^+(\mathbb N+n)=\lambda^+(\mathbb N)$, for all $n$; your natural way to play would be to use a finitely additive probability measure $\lambda^-$ which gives measure $0$ to the $\mathbb N$, leaving its measure invariant by translations. Now, there is a (quite discussed) philophical principle which states that human beings are enough smart to play Nash equilibria. So, the philophical theorem would be that a Nash equilibrium is indeed given by the previous measures.

Before passing to mathematics, let me explain why I wrote also Group Theory in the title. Simply because it is clear that these are just examples of a more general situation: one can replace $\mathbb Z$ with any amenable group and consider as a winning set any subset of $G$. So, the following mathematical discussion is exactly the same replacing $\mathbb Z$ with $G$ and $\mathbb N$ with $W\subseteq G$.

Coming back to our game, the philophical theorem is clear and I think that everyone agrees that it has to be right, in some sense or in the other. So let us try to prove it: I have to prove that $f(\lambda^+,\lambda^-)\geq f(\mu,\lambda^-)$, for all finitely additive probability measures $\mu$, where

$$f(\mu,\nu)=\int_{\mathbb Z^2} \chi_{\mathbb N}(x+y)d(\mu\times\nu)(x,y)$$

Ops, here is the first problem! Who is $\mu\times\nu$? They are indeed just finitely additive probability measures, so there is no a unique extension of the product measure to the whole $\mathbb Z^2$. Well.. we like philosophy and the choice of a particular rule of extension should not affect the result. So, let us decide for the first order of integration. The problem is then reduced to the following

Conjecture: Let $M$ be the set of finitely additive probability measures on $\mathbb Z$ and $I_W$ be the set of the ones which leave the measure of $W$ invariant under translation and let $\lambda\in I_W$ be fixed. Then the mapping

$$\mu\in M\rightarrow \int\int\chi_{W}(x+y)d\mu(x)d\lambda(y)$$

attains its maximum in an element in $I_W$.

Well, if $W=\mathbb N$, it is easy ... what happens for $W=2\mathbb N$?

Main question: Is the conjecture above true?

Update: In this form, the negative answer was provided by Matthew Daws in 100€ bounty ended: Do invariant measures maximize the integral?. There is indeed something weird and probably one has to take invariant measures only on subgroups (as happen for $W=2\mathbb N$, where a Nash equilibrium is not realized by invariant measures on $\mathbb Z$, but by invariant measures on $2\mathbb Z$).

-
Every non-principal ultrafilter on $\mathbb{N}$ induces a "finitely additive non countably additive probability measure" with zero entropy. – Ricky Demer Sep 29 '11 at 23:14
I don't think MathOverflow is the right place for "posts" on which you ask people to "comment". Certainly the software functions in ways like a group blog, but we mostly try to keep MO focused on being a Q&A site. That said, I do like long questions with lots of background and motivation. Can I ask you to revise your question a bit to make it more skimmable for an answerable question? Good formatting often includes headers and putting the question either at the top or bottom, set in a blockquote. – Theo Johnson-Freyd Sep 30 '11 at 3:11
Questions at the bottom?! What's the meaning of that? In Europe we still like to travel, see mountains, hills, fawns... well, it's the old continent... but anyway, maybe you skipped to quickly, because it seems to me that the question is block-quoted and self-contained. – Valerio Capraro Sep 30 '11 at 7:16
Dear Valerio. The tone of Theo's comment was maybe a little bit harsh. However, I mostly agree with him. As I was reading your question, I tried to find the question mark sign (there is only one question mark sign in you post, at the end of the sentence "Who is μ×ν?", that's probably not your main question). You should make it clear what your question is. – André Henriques Sep 30 '11 at 8:19
The first game you describe is just a fancy rewriting of the 2x2-game known as "matching pennies", game with a unique equilibrium that is in mixed strategies. The second game you describe shares nothing with the first game. It is a game that is well known for having no Nash equilibrium (when mixed strategies are countably additive). The intuition is straightforward, it always pays to shift probability mass to higher numbers. I don't know much about purely finitely additive measures, but I see no intuition whatsoever why choosing numbers uniformly should be a good choice. – Michael Greinecker Sep 30 '11 at 10:25