What strategy should Alice choose to win this game?

Question

The following game was proposed to me:

1. Alice has a coin which has a probability $p$ of landing on heads, $1-p$ of landing on tails. Alice doesn't know $p$. Alice is not allowed to lie.
2. Bob knows $p$. Bob is allowed to lie.
3. Alice tells Bob two functions $f, g: [0,1]\mapsto\mathbb R$ and asks Bob for the value of $p.$ Let Bob's answer be $\pi$.
4. Alice throws the coin. If it lands on heads, Bob is awarded $f(\pi)$ points, if it lands on tails, Bob is awarded $g(\pi)$ points.

Alice wants to find a pair of functions $f,g$ such that if Bob tries to maximize the expected value for the number of points he is awarded, then $\pi=p$.

Is there a simple way to describe the entire solution space?

Answer 1

This resembles mechanism design problems in economics. You, mechanism designer, are trying to construct a mechanism, map from answers to outcomes and transfers, such that agents participating in the mechanism have no incentive to lie about their private information.

In your context, suppose $f,g$ are already set. Then Bob, when choosing $\pi$ to answer, solves $\max_{\pi\in[0,1]}pf(\pi)+(1-p)g(\pi)$ (notice Bob knows $p$). Assume first-order conditions describe the solution to this problem. Then Bob answers $\pi$ such that $pf'(\pi)+(1-p)g'(\pi)=0$. Since your (Alice's) goal is to induce truth-telling, Alice wants to set $f$ and $g$ such that $pf'(p)+(1-p)g'(p)=0$ and since Alice does not know $p$, she wants to set $f$ and $g$ such that $pf'(p)+(1-p)g'(p)=0$ for all $p\in[0,1]$ (with the continuity, differentiability, and concavity assumptions made on the way here).

If you do not like the assumptions I made throughout since you want to describe the entire solution space, then you simply write that $f$ and $g$ constitute your solution if $p\in\arg\max_{\pi\in[0,1]}pf(\pi)+(1-p)g(\pi)$ for all $p\in[0,1]$.

Answer 2

Bob tries to maximize his win so he calculates \begin{equation} \max_{\pi \in[0,1]} [p f(\pi) + (1-p) g(\pi)] \end{equation} For the start and sake of simplicity assume that it coincides with $\frac{d}{d \pi}[p f(\pi) + (1-p) g(\pi)] = 0$. We get $q(p, \pi) = p f'(\pi) + (1-p) g'(\pi)$.

Now Alice wants to construct $q$ such that $\forall p ~ q({p,p}) = 0$.

Now comes the fun part finding a solution to $ p f'(p) + (1-p) g'(p) = 0$ We can start e.g. with $f(p) = \ln(p)-p$

then we have $ p (\frac{1}{p} -1) + (1-p) g'(p) = 0$

equivalent to $1+g'(p)=0$ so $g = -p$

Now we can check the second derivative to be sure that it is actually a maxima $p f''(\pi)+(1-p)g''(\pi) = -p\frac{1}{\pi^2}$ voila.

The whole solution space should be obtainable via

\begin{equation} -\frac{1-p}{p} g'(p) = f'(p) ~\text{with constraint}~ \forall \pi : p f''(\pi)+(1-p)g''(\pi) < 0 \end{equation}