1
$\begingroup$

Consider the following game between party 1 and party 2. Party 1 is honest; i.e. it follows the game exactly:

Assume that party 1 flips a fair coin $b$, encrypts it to $c$, and sends $c$ to party 2. Party 2 returns a value $b'$. Finally, party 1 reveals b by decrypting c.

Party 2 wins if $b'=b$, and loses otherwise. Assume that the encryption is not perfect; therefore $c$ reveals partial information about $b$, such that party 2 learns that there's a 60% chance that $b=0$. What strategy maximizes the winning chance of party 2?

I think the problem can be symbolically denoted as follows:

  1. $\Pr[b=0] = \Pr[b=1] = 0.5$
  2. $\Pr[b=0 \mid c] = 1-\Pr[b=1 \mid c]= 0.6$

and we want to choose $\Pr[b'=0 \mid c]$ such that $\Pr[b'=b \mid c]$ is maximized.

PS: The encryption used above is in fact a commitment scheme, but let's not care about that.

  • 0
    Do you mean $Pr[b=0∣c]=1−Pr[b=1∣c]=0.6$? Also, shouldn't things depend on what $c$ is? If the probability that $b=0$ (given that you know $c$) is 60% regardless of what $c$ is, then the probability that $b=0$ (in the absence of knowing $c$ should be 60%).2011-06-23
  • 0
    @Aaron: Corrected, thanks. Regarding the second point, party 2 knows c, and given his knowledge, he wants to bias $b'$ to maximize his winning chance.2011-06-23
  • 0
    Why shouldn't party 2 just pick $b'=0$ and win 60%?2011-06-23
  • 0
    @Ross: That's a possibility; yet it assumes $b'$ is chosen independently of $b$. I need a proof for the optimized strategy.2011-06-23
  • 0
    If, given what Party 2 knows, there is a 60% chance that $b=0$, he should set $b'=0$. The prior probabilities do not enter the problem at all. So assuming there is a 60% chance of $b=0$, if he guesses 0 with probability $p$ and 1 with probability $1-p$, he will be right $.6p+.4(1-p)=.4+.2p$, which is maximized when $p=1$.2011-06-23
  • 0
    @Sadeq: you didn't say that party 2 got to choose $b'$ at will, but that is how I took it. When you ask for a strategy, that is implied. Given the 60% chance that $b=0$, and other strategy (unless you have other information) will have lower success.2011-06-23

0 Answers 0