Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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%). –  Aaron Jun 23 '11 at 13:58
    
@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. –  Sadeq Dousti Jun 23 '11 at 14:11
    
Why shouldn't party 2 just pick $b'=0$ and win 60%? –  Ross Millikan Jun 23 '11 at 14:15
    
@Ross: That's a possibility; yet it assumes $b'$ is chosen independently of $b$. I need a proof for the optimized strategy. –  Sadeq Dousti Jun 23 '11 at 14:21
    
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$. –  Aaron Jun 23 '11 at 14:25

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.