8
$\begingroup$

Although there is no use of cryptographic protocols in Gossner (1998), the author refers to protocols of communication and he has a main result that I struggle to prove, because he does not use a specific way to do it. If anyone has seen the paper and could give some intuitive explanation from where to start or he\she could prove the theorem or give some steps to do so I would appreciate it.

The following definitions are taken from the paper of Gossner (1998). I want to understand how he proves the theorem that is the main result in his work. I give four definitions and the theorem which is based on them.

$\textit{Definition 1:}$ $I$ is a finite set of players and and $G=((S_i)_{i=1}^I,g)$ is a compact game, that is given by a compact set of strategies $S_i$ for each player $i$ and by a continuous payoff function $g:S(=\times S_i) \to \mathbb{R}^{I}$. Also the mixed set of strategies is defined as $\Sigma_i=\Delta(S_i)$ which is a standard way in game theory.

$\textit{Definition 2:}$ The information structure $\mathbb{I}=((X_i)_{i=1}^{I},\mu)$ is given by a finite set of signals $X_i$ for each $i$ and by a probability measure $\mu$ over $X$. When $x$ is drawn according to $\mu$, player $i$ is informed about the coordinate $x_i$.

$\textit{Definition 3:}$ A communication mechanism is a triple $\mathbb{C}=((T_i)_{i=1}^I, (Y_i)_{i=1}^I , l )$, where $T_i$ is $i's$ finite set of messages, $Y_i$ is $i's$ finite set of signals, and $l: T\to \Delta(Y)$ is the signal function. When $t$ is the profile of messages sent by the players to the mechanism, $y\in Y$ is drawn according to $l(\cdot|t)$ and player $i$ is informed of $y_i$. $\mathbb{T}_i=\Delta(T_i)$ represents the set of mixed messages for player $i$ and $l$ is extended to $\mathbb{T}$ by $l(y|\tau)=\mathbb{E}_{\tau} l(y|t)$.

In this place I can define the protocol

$\textit{Definition 4:}$ For a given communication mechanism $\mathbb{C}$, the protocol is a pair $(\tau,\phi)$, such that:

  • a translation $\phi=(\phi_i)_{i=1}^I$ is a family of mappings $\phi_i: Y_i\to \Delta(X_i)$
  • and $\tau$ is a profile of mixed messages

In his paper Gossner proves a theorem which is his main result and it is the following

$\textit{Theorem:}$ $(\tau,\phi)$ is secure if and only if

  • For every player $i$ and $\tau_i^{'}\in\mathbb{T}_i$, $m(\tau_i^{'})=m(\tau_i)$

  • For every player $i$ and $\tau_i^{'}\in\mathbb{T}_i$, $\alpha_i\supset \gamma_{\tau_{i}^{'}}$

the function $m(\tau_i^{'})$ denotes the marginal of $P_{(\tau_{i}^{'},\tau_{-i})}$ on $X_{-i}$ where $$P_{(\tau_{i}^{'},\tau_{-i})}(y,x)=l(y|(\tau_{i}^{'},\tau_{-i}))\phi(x|y)$$ and $m(\tau_i^{'})$ is the probability over players other than $i$'s translated signals when they follow the protocol $(\tau,\phi)$ and when $i$'s messages are distributed according to $\tau_{i}^{'}$.

The second bullet of the theorem refers to the comparison of statistical experiments due to Blackwell theorem in statistical experiments, in order to compare different information of a player on other's signals. It's meaning is that if $\alpha_i\supset \gamma_{\tau_{i}^{'}}$ then the statistical experiment $\alpha_i$ is more informative than $\gamma_{\tau_{i}^{'}}$.

$\textit{Question:}$ Can anybody prove the theorem above?

$\textit{Hint:}$ In order to define incentives for the players not to change their messages or compute the new messages from the communication procedure differently the author makes a comparison between the N.E. of the basic game extended by the communication mechanism with respect to the extended game by the information generated by the protocol.

References

Gossner (1998). Secure protocols or how communication generates correlation. Journal Of economic Theory, 83(1), 69-89.

$\endgroup$
4
  • $\begingroup$ But the author claims to prove the theorem in (Sections 6 and 7 of) the paper you linked to. What is wrong with the proof given there? $\endgroup$
    – Neal Young
    Nov 14, 2021 at 13:02
  • $\begingroup$ @NealYoung, to put it simply, I do not undrestand him...I can not follow his logic. He defines in the previous section $5$, some type of test game, that i can not follow its intuition and hence I can not understand the sections $6$ and $7$. I don't know if you understand him, or you have something to explain to make me fill the gaps in my understanding, but if you do so, I would be glad and I would appreciate it. $\endgroup$
    – Nav89
    Nov 14, 2021 at 16:26
  • 1
    $\begingroup$ Thanks for clarifying -- so the paper as written doesn't make much sense to you and you'd like help understanding the proof? I haven't read it myself. Maybe somebody who knows the result already can help. You might have more luck if you change the title so it references the paper in question. E.g. "Looking for help understanding a proof by Gossner (1998)." $\endgroup$
    – Neal Young
    Nov 14, 2021 at 22:11
  • $\begingroup$ @NealYoung thank you very much! $\endgroup$
    – Nav89
    Nov 15, 2021 at 0:28

0

Your Answer

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

Browse other questions tagged or ask your own question.