Return to Question

added 15 characters in body

view source

edited Nov 29 2011 at 15:24

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. This 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: The In this form, the negative answer was provided by Matthew Daws in http://mathoverflow.net/questions/74387/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$).

deleted 1736 characters in body

view source

edited Nov 26 2011 at 11:54

Valerio Capraro
3,595●11●25

Well, if $W=\mathbb N$, it is easy , but a general argument looks hard, at least for me. In http://mathoverflow.net/questions/74387/do-invariant-measures-maximize-the-integral I have asked the same question... what happens for $W=2\mathbb N$?

One can look at the problem also from a different point of view, that might suggest some nice speculation.

Update: The lack of important information about the game, should be reflected negative answer was provided by Matthew Daws in the entropy of the Nash equilibriumhttp://mathoverflow.net/questions/74387/100-bounty-ended-do-invariant-measures-maximize-the-integral. Indeed, formally a Nash equilibrium There is a pair of finitely additive probability measures indeed something weird and their entropy reflects the quantitative of information that we have in hand: complete information means a pure equilibrium that means Dirac probably one has to take invariant measures , which means entropy zero. Well.. maybe it's not clear what entropy I am talking about. Let us use the following generalization of Shannon's entropy only on subgroups (as in http://mathoverflow.net/questions/70917/entropy-of-a-measure):

$happen for $E(\mu)=\sup-\sum_{i=1}^n\mu(A_i)log(\mu(A_i)), \mathbb Z=\bigcup A_iW=2\mathbb N$, A_i \text{ pairwise disjoint}$$

Added: At the beginning it was where a Nash equilibrium is not clear whether there are finitely additive non countably additive probability measures with finite entropy. As observed by Ricky Demer below, it suffices to take the measure defined realized by a non-principal ultrafilter to have an example of measure non countably additive with zero entropy: as also explained in Tao's post, in some sense the ''ultrafilter measures'' generalize the Dirac invariant measures , which are obtained by taking a principal ultrafilter. Indeed, instead of choose a singleton as a dictator, we choose a set in a coherent way - see Tao's post in the link above for (well-exposed) details).

Hence, there should be some correspondence between the best entropy Nash equilibria, the solution of the problem in the conjecture and the structure of on $W$. I don't have a very precise idea in mind\mathbb Z$, but something like: the best entropy Nash equilibria can be considered as a measure of the disorder of $W$. So a positive solution of conjecture 1 would imply a simple and natural way to look at the disorder rate of $W$: take the entropy of the solution of the game associated, which is described by a suitable invariant measures which leaves on $\chi_W$ invariant.

Well, every comment is very welcome2\mathbb Z$).

added 358 characters in body; added 152 characters in body

view source

edited Sep 30 2011 at 9:50

Valerio Capraro
3,595●11●25

(by

Added: At the way, it's beginning it was not clear whether there is are finitely additive non countably additive probability measures with finite entropy)entropy. As observed by Ricky Demer below, it suffices to take the measure defined by a non-principal ultrafilter to have an example of measure non countably additive with zero entropy: as also explained in Tao's post, in some sense the ''ultrafilter measures'' generalize the Dirac measures, which are obtained by taking a principal ultrafilter. Indeed, instead of choose a singleton as a dictator, we choose a set in a coherent way - see Tao's post in the link above for (well-exposed) details).

added 440 characters in body; added 27 characters in body

view source

edited Sep 30 2011 at 8:55

Valerio Capraro
3,595●11●25

view source

asked Sep 29 2011 at 22:21

Valerio Capraro
3,595●11●25

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

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. This 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.

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

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, but a general argument looks hard, at least for me. In http://mathoverflow.net/questions/74387/do-invariant-measures-maximize-the-integral I have asked the same question.

One can look at the problem also from a different point of view, that might suggest some nice speculation. The lack of important information about the game, should be reflected in the entropy of the Nash equilibrium. Indeed, formally a Nash equilibrium is a pair of finitely additive probability measures and their entropy reflects the quantitative of information that we have in hand: complete information means a pure equilibrium that means Dirac measures, which means entropy zero. Well.. maybe it's not clear what entropy I am talking about. Let us use the following generalization of Shannon's entropy (as in http://mathoverflow.net/questions/70917/entropy-of-a-measure):

$$ E(\mu)=\sup-\sum_{i=1}^n\mu(A_i)log(\mu(A_i)), \mathbb Z=\bigcup A_i, A_i \text{ pairwise disjoint} $$

(by the way, it's not clear whether there is finitely additive non countably additive probability measures with finite entropy).

Hence, there should be some correspondence between the best entropy Nash equilibria, the solution of the problem in the conjecture and the structure of $W$. I don't have a very precise idea in mind, but something like: the best entropy Nash equilibria can be considered as a measure of the disorder of $W$. So a positive solution of conjecture 1 would imply a simple and natural way to look at the disorder rate of $W$: take the entropy of the solution of the game associated, which is described by a suitable measures which leaves $\chi_W$ invariant.

Well, every comment is very welcome.