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$
  • $\begingroup$ Looks like Bayesian statistics. $\endgroup$ – Gerald Edgar Apr 1 '12 at 18:53
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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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