6
$\begingroup$

I would like to know how the following game is known in the literature and, possibly, to have references for related papers.

Description of the game: Fix a space $X$ and two Borel probability measures $\mu$ and $\nu$ over $X$. There are two players, $A$ and $B$. They both know $\mu$ and $\nu$. Player $A$ chooses between $\mu$ and $\nu$. Player $B$ can not observe Player $A$'s choice. Say $\mu$ is chosen by $A$. Then an element $x\in X$ is randomly chosen in accordance with $\mu$. Now player $B$, looking at $x$, must guess the choice of $A$, i.e., Player $B$ must say "you piked $\mu$", or "you picked $\nu$". Player $B$ wins if their guess is correct. Player $A$ wins otherwise.

How to formalize the game:

  1. The strategies for Player $A$ can be formalized as (randomized) choices over the two element set, i.e., as elements in $[0,1]$.

  2. A strategy for Player $B$ can be formalized as a map $\sigma: X\rightarrow [0,1]$: if $x$ is the outcome, then guess $\mu$ with probability $\sigma(x)$ and $\nu$ with probability $1-\sigma(x)$.

  3. Since Player $B$ can not observe Player $A$'s choice, the game can be consider as played concurrently.

I believe the game has an optimal equilibrium and its value is a function of $\displaystyle \bigsqcup_{B\ Borel} | \mu(B) - \nu(B) |$, i.e., of the total variation distance between $\mu$ and $\nu$.

Thank you in advance for any information.

Matteo

$\endgroup$
1
  • $\begingroup$ Looks like Bayesian statistics. $\endgroup$ Apr 1, 2012 at 18:53

1 Answer 1

1
$\begingroup$

I interpret your game as follows. $A$ chooses $\alpha\in[0,1]$, $B$ chooses some measurable $\sigma:X\to[0,1]$, resulting in a probability $$u(\alpha,\sigma)=\int [\alpha(1-\sigma)\ d\mu + (1-\alpha)\sigma\ d\nu]$$ of $B$ guessing incorrectly. Here, the players move simultaneously, $A$ wants to maximize $u$ and $B$ wants to minimize $u$.

It's possible to explicitly compute a value for this game in general, but let's consider a special case (which is, in a sense, not very special) that cleans up notation, in order to specifically address the question of how the value of the game relates to total variation.

Specifically, for a given nondecreasing $f:[0,1]\to[0,2]$ with $\int_0^1 f=1$, suppose $X=[0,1]$, measure $\mu$ has Lebesgue density $f$, and $\nu$ has Lebesgue density $2-f$. Then, consider $\alpha^*:=1-\tfrac12 f(\tfrac12)$ and $\sigma^*:=\mathbf1_{[\tfrac12,1]}$. One can verify that this is a Nash equilibrium (a.k.a. saddle point): $\alpha^*$ maximizes $u(\cdot,\sigma^*)$ and $\sigma^*$ minimizes $u(\alpha^*,\cdot)$, and the value it produces is exactly $$v = \int_0^{\tfrac12}f.$$ Meanwhile, the total variation between $\mu$ and $\nu$ can be computed as $$TV = 2\int_0^1 \max\{f-1, 0\}.$$

So the question, restricted to this special case, reduces to: When looking at nondecreasing functions $f:[0,1]\to[0,2]$, can one express $\int_0^{\tfrac12}f$ as a function of $2\int_0^1 \max\{f-1, 0\}$?

If it so happens that $f(\tfrac12)=1$, then $$\tfrac12 TV=\int_0^1 \max\{f-1, 0\}=\int_{\tfrac12}^1 (f-1)=\left(\int_0^1 f \right) - \tfrac12 - \int_0^{\tfrac12} f = \tfrac12-v,$$ implying $v=\tfrac{1-TV}2$.

But, if $\int_0^1 \max\{f-1, 0\}\neq\int_{\tfrac12}^1 (f-1)$, then the above algebra shows that $v\neq\tfrac{1-TV}2$. Finally, it's easy to find two continuous, strictly increasing functions $f,\hat f:[0,1]\to[0,2]$ such that $\int_0^1 \max\{f-1, 0\}=\int_0^1 \max\{\hat f-1, 0\}$ but $f(\tfrac12)=1\neq \hat f(\tfrac12)$.

So in summary, the value cannot generally be expressed as a function of total variation. However, the original post reflected a good intuition. If we restrict to the case that there is "enough symmetry" between $\mu$ and $\nu$ that player $A$ could choose a 50/50 mixture in equilibrium, then the value is a function of total variation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.