<p>Although there is no use of cryptographic protocols in <a href="https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.685.4204&amp;rep=rep1&amp;type=pdf" rel="noreferrer">Gossner (1998)</a>, 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.</p>
<p>The following definitions are taken from the paper of <a href="https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.685.4204&amp;rep=rep1&amp;type=pdf" rel="noreferrer">Gossner (1998)</a>. 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.</p>
<p><span class="math-container">$\textit{Definition 1:}$</span> <span class="math-container">$I$</span> is a finite set of players and and <span class="math-container">$G=((S_i)_{i=1}^I,g)$</span> is a compact game, that is given by a compact set of strategies <span class="math-container">$S_i$</span> for each player <span class="math-container">$i$</span> and by a continuous payoff function <span class="math-container">$g:S(=\times S_i) \to \mathbb{R}^{I}$</span>. Also the mixed set of strategies is defined as <span class="math-container">$\Sigma_i=\Delta(S_i)$</span> which is a standard way in game theory.</p>
<p><span class="math-container">$\textit{Definition 2:}$</span> The information structure <span class="math-container">$\mathbb{I}=((X_i)_{i=1}^{I},\mu)$</span> is given by a finite set of signals <span class="math-container">$X_i$</span> for each <span class="math-container">$i$</span> and by a probability measure <span class="math-container">$\mu$</span> over <span class="math-container">$X$</span>. When <span class="math-container">$x$</span> is drawn according to <span class="math-container">$\mu$</span>, player <span class="math-container">$i$</span> is informed about the coordinate <span class="math-container">$x_i$</span>.</p>
<p><span class="math-container">$\textit{Definition 3:}$</span> A communication mechanism is a triple <span class="math-container">$\mathbb{C}=((T_i)_{i=1}^I, (Y_i)_{i=1}^I , l )$</span>, where <span class="math-container">$T_i$</span> is <span class="math-container">$i's$</span> finite set of messages, <span class="math-container">$Y_i$</span> is <span class="math-container">$i's$</span> finite set of signals, and <span class="math-container">$l: T\to \Delta(Y)$</span> is the signal function. When <span class="math-container">$t$</span> is the profile of messages sent by the players to the mechanism, <span class="math-container">$y\in Y$</span> is drawn according to <span class="math-container">$l(\cdot|t)$</span> and player <span class="math-container">$i$</span> is informed of <span class="math-container">$y_i$</span>. <span class="math-container">$\mathbb{T}_i=\Delta(T_i)$</span> represents the set of mixed messages for player <span class="math-container">$i$</span> and <span class="math-container">$l$</span> is extended to <span class="math-container">$\mathbb{T}$</span> by <span class="math-container">$l(y|\tau)=\mathbb{E}_{\tau} l(y|t)$</span>.</p>
<p>In this place I can define the protocol</p>
<p><span class="math-container">$\textit{Definition 4:}$</span> For a given communication mechanism <span class="math-container">$\mathbb{C}$</span>, the protocol is a pair <span class="math-container">$(\tau,\phi)$</span>, such that:</p>
<ul>
<li>a translation <span class="math-container">$\phi=(\phi_i)_{i=1}^I$</span> is a family of mappings <span class="math-container">$\phi_i: Y_i\to \Delta(X_i)$</span></li>
<li>and <span class="math-container">$\tau$</span> is a profile of mixed messages</li>
</ul>
<p>In his paper Gossner proves a theorem which is his main result and it is the following</p>
<p><span class="math-container">$\textit{Theorem:}$</span> <span class="math-container">$(\tau,\phi)$</span> is secure if and only if</p>
<ul>
<li><p>For every player <span class="math-container">$i$</span> and <span class="math-container">$\tau_i^{'}\in\mathbb{T}_i$</span>, <span class="math-container">$m(\tau_i^{'})=m(\tau_i)$</span></p>
</li>
<li><p>For every player <span class="math-container">$i$</span> and <span class="math-container">$\tau_i^{'}\in\mathbb{T}_i$</span>, <span class="math-container">$\alpha_i\supset \gamma_{\tau_{i}^{'}}$</span></p>
</li>
</ul>
<p>the function <span class="math-container">$m(\tau_i^{'})$</span> denotes the marginal of <span class="math-container">$P_{(\tau_{i}^{'},\tau_{-i})}$</span> on <span class="math-container">$X_{-i}$</span> where
<span class="math-container">$$P_{(\tau_{i}^{'},\tau_{-i})}(y,x)=l(y|(\tau_{i}^{'},\tau_{-i}))\phi(x|y)$$</span>
and <span class="math-container">$m(\tau_i^{'})$</span> is the probability over players other than <span class="math-container">$i$</span>'s translated signals when they follow the protocol <span class="math-container">$(\tau,\phi)$</span> and when <span class="math-container">$i$</span>'s messages are distributed according to <span class="math-container">$\tau_{i}^{'}$</span>.</p>
<p>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 <span class="math-container">$\alpha_i\supset \gamma_{\tau_{i}^{'}}$</span> then the statistical experiment <span class="math-container">$\alpha_i$</span> is more informative than <span class="math-container">$\gamma_{\tau_{i}^{'}}$</span>.</p>
<p><span class="math-container">$\textit{Question:}$</span> Can anybody prove the theorem above?</p>
<p><span class="math-container">$\textit{Hint:}$</span> 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.</p>
<h1>References</h1>
<p><strong>Gossner (1998)</strong>. <em>Secure protocols or how communication generates correlation</em>. Journal Of economic Theory, 83(1), 69-89.</p>

CC BY-SA 4.0
2021-11-14T13:02:43.733Z
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?
Neal Young
CC BY-SA 4.0
2021-11-14T16:26:20.680Z
@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.
Nav89
CC BY-SA 4.0
2021-11-14T22:11:48.940Z
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)."
Neal Young
CC BY-SA 4.0
2021-11-15T00:28:26.327Z
@NealYoung thank you very much!
Nav89
<pr.probability><it.information-theory><quantum-information><gt.game-theory><mechanism-design>
"Looking for help understanding a proof by Gossner (1998)."
Nav89
# "Looking for help understanding a proof by Gossner (1998)."

(Asked by: username_0 on 2021-11-08)

Although there is no use of cryptographic protocols in [Gossner (1998)](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.685.4204&rep=rep1&type=pdf), 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)](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.685.4204&rep=rep1&type=pdf). 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.

**Tags:** pr.probability, it.information-theory, quantum-information, gt.game-theory, mechanism-design

> **Comments:**
> **username_1**: 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?  
> **username_0**: @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.  
> **username_1**: 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)."  
> **username_0**: @NealYoung thank you very much!  

---

## 0 answers

