Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is it true that for any real number $p$ between 0 and 1, there exist finite or infinite sequences $x_m$ and $y_n$ of positive real numbers, and a finite or infinite matrix of numbers $\varphi_{mn}$ each of which is either 0 or 1, such that

1) $\sum x_m=1$

2) $\sum y_n=1$

3) $\forall n\;\sum x_m\varphi_{mn}=p$

4) $\forall m\;\sum y_n\varphi_{mn}=p$

share|improve this question

3 Answers 3

up vote 5 down vote accepted

Generalization of my previous answer. Is this right? $p$ irrational...

For $0\lt p \lt 1/2$ let $x_1(p)=y_1(p)=p$, $\varphi_{1,1}(p) = 1$, $\varphi_{1,j}(p)=\varphi_{j,1}(p)=0$ for $j>1$, $x_n(p)=(1-p)x_{n-1}(p/(1-p))$ for $n>1$. And $\varphi_{n,m}(p) = \varphi_{n-1,m-1}(p/(1-p))$. For $1/2 \lt p \lt 1$ let $x_n(p)=x_n(1-p)$ and $\varphi_{n,m}(p) = 1-\varphi_{n,m}(1-p)$.

share|improve this answer
    
I ran a computational experiment and your solution seems to check out perfectly. Thanks!! How did you arrive at it? –  Vladimir Slepnev Jun 4 '12 at 0:07
1  
Well, first was the golden section proof. That works because of special properties of that number. Then when I tried to generalize, it turned out that it would work if the transformations p/(1-p) and 1-p return to the original value in a finite number of steps. But then why does it have to be the original value? Just proceed with whatever value it is... –  Gerald Edgar Jun 4 '12 at 12:59
    
Thanks. I worked out the proofs, they're quite easy. I needed this result for a paper (about mostly unrelated topics, like computation theory). If the paper works out I will message you and put in an acknowledgement etc. I don't really know the right protocol for this though. –  Vladimir Slepnev Jun 4 '12 at 13:50

I will show the following facts:

  1. If $p\in\mathbb Q$, then your question has positive answer. (see Edit 2)
  2. For general $p$ your question has positive answer up to $\varepsilon$, for all $\varepsilon$. (see Edit 2)
  3. For general $p$ your question has positive exact answer if you allow the use of finitely additive probability measures. (see Proposition below). This is particularly motivated by the fact that, for countable games, people usually allow the use of finitely additive probability measures and not only countable additive ones.

Proposition. Let $p\in[0,1]$. There are finitely additive measures $\mu,\nu$ on the power set of $\mathbb Z$ and a countably infinite matrix $\phi_{mn}$ with entries either $0$ or $1$ such that

  1. $\int_{\mathbb Z}d\mu(m)=1$
  2. $\int_{\mathbb Z}d\nu(n)=1$
  3. For all $m\in\mathbb Z$, $\int_{\mathbb Z}\phi_{mn}d\mu(n)=p$
  4. For all $n\in\mathbb Z$,, $\int_{\mathbb Z}\phi_{mn}d\nu(m)=p$

Proof. Consider the following game. Choose $W\subseteq\mathbb Z$ having upper mean value[1] equal to $p$ and consider the following two-person game: two players choose simultaneously $m,n\in\mathbb Z$ and player 1 wins if $m+n\in\mathbb W$. Player 1's payoff function is exactly the countable infinite matrix $\phi_{mn}=\chi_W(m+n)$. Now consider the mixed extension of this game obtained by allowing the players to play all finitely additive strategies with Player 1's mixed extension payoff $$ \int\int \chi(m+n)d\mu(m)d\nu(n) $$ where $\mu,\nu$ are finitely additive strategies. By Theorem 4.1 in [2] this game has a Nash equilibrium with value exactly $p$ and obtained with translation invariant probability measures $\mu,\nu$. These two measures verify your properties. The first two because they are probability measures; the third and the fourth because they are translation invariant.

[1] The upper mean value of $W$ is the supremum of $\int\chi_W(x)d\lambda(x)$, where $\lambda$ runs over the set of translation invariant finitely additive probability measure on $G$. This set of measures is weak* compact and then the supremum is attained.

[2] Capraro V., Scarsini M., Existence of equilibria in countable games: an algebraic approach, http://arxiv.org/pdf/1203.2301.pdf

Edit. I have realized that in the proof of the proposition it is not necessary to construct the game. Just take $W$ with with upper mean value $p$, construct $\phi_{mn}=\chi_W(m+n)$ and take $\mu=\nu$ be an invariant measure that gives measure $W$ to $p$. I leave that proof since the Original Question ask explicitly for a game theoretical interpretation of the result.

Edit 2. One can get an approximative solution in countable finitely additive measures as follows. Fix $\varepsilon >0$ and take $n$ big enough such that $\mathbb Z/(n\mathbb Z)$ contains set of normalized counting measure equal to $p$ up to $\varepsilon$. Apply the construction above to get the desired result. Notice that if $p\in\mathbb Q$, then this construction can be done with $\varepsilon=0$, giving an exact solution in countably additive measures.

share|improve this answer
    
Thanks! But actually I already knew the answer for rational p, which seems to trivially imply the approximate answer for all p. The "meat" of the question is whether we can get every irrational p (or indeed any irrational p) using countably additive measures. –  Vladimir Slepnev Jun 3 '12 at 14:10
    
I have some doubt that it can be solved in c.a. measures. It seems to me that the game in consideration is: fix $A\subseteq\mathbb N\times\mathbb N$. Player 1 chooses $m\in\mathbb N$ and Player 2 chooses $n\in\mathbb N$. The first player wins 1 dollar if $(m,n)\in A$. Now, if $p\notin\mathbb Q$, the set $A$ must be quite strange: in particular, every horizontal and vertical section must contain infinitely many points and the complementary of these sections must have infinitely many points. This means (probably) that you cannot find Nash equilibria in c.a. strategies, since each player has a –  Valerio Capraro Jun 3 '12 at 18:43
    
best reply concentrated further and further away. Does it sound reasonable? I'll try to make it formal. –  Valerio Capraro Jun 3 '12 at 18:44
    
I think this argument can be made formal if one assume that $p\notin\mathbb Q$ and all $x_n,y_n\in\mathbb Q$. So maybe one should try to prove that if two sequences $x_n,y_n$ verify your properties, then there are rational sequences that still do it. It is possible that this is true, taking small perturbations. –  Valerio Capraro Jun 3 '12 at 18:50
    
That would be cool, but intuitively I don't think the argument will work. The game might well have a unique Nash equilibrium in mixed strategies. After all, some finite games do. –  Vladimir Slepnev Jun 3 '12 at 19:05

Golden Section The golden section works.

Write $u = (\sqrt{5}+1)/2$, I don't call it $\varphi$, since that symbol is already in the problem. So of course $u^m+u^{m+1}=u^{m+2}$.

Let $p=u^{-2} \approx 0.3819$. Define: $$ x_1 = u^{-2}, x_2=u^{-3}, x_3=u^{-4},\dots,x_m=u^{-m-1},\dots $$ and $y_m=x_m$. Then compute $$ \sum_{m=1}^\infty x_m = \sum_{j=2}^\infty u^{-j} = \frac{u^{-2}}{1-u^{-1}} = \frac{u^{-2}}{u^0-u^{-1}}= \frac{u^{-2}}{u^{-2}} = 1. $$ Define: $$\begin{align*} &\varphi_{1,1}=1, \qquad\varphi_{1,j}=\varphi_{j,1}=0, j>1. \cr &\varphi_{2,2} = 0,\qquad\varphi_{2,j}=\varphi_{j,2}=1, j>2. \cr &\varphi_{m,n} = \varphi_{m-2,n-2}, m,n>2. \end{align*}$$ Now by induction on $n$ we will show $\sum_{m=1}^\infty x_m\varphi_{m,n} = u^{-2} = p$ for all $n$.

For $n=1$, compute $$ \sum_{m=1}^\infty x_m \varphi_{m,1} = x_1\cdot 1 + \sum_{m=2}^\infty x_m \cdot 0 = u^{-2}. $$ For $n=2$, compute $$ \sum_{m=1}^\infty x_m \varphi_{m,2} = x_1\cdot 0 + x_2\cdot 0 + \sum_{m=3}^\infty x_m\cdot 1 = \sum_{j=4}^\infty u^{-j} = u^{-2}. $$ For $n>2$ apply the inductive hypothesis: $$\begin{align*} \sum_{m=1}^\infty x_m\varphi_{m,n} &= x_1\cdot 0 + x_2\cdot 1 + \sum_{m=3}^\infty x_m \varphi_{m-2,n-2} = u^{-3}+u^{-2}\sum_{j=1}^\infty x_j \varphi_{j,n-2} \cr &=u^{-3}+u^{-2}u^{-2}=u^{-3}+u^{-4}=u^{-2}. \end{align*}$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.