# Olivier Gossner - Secure Protocols or How Communication Generates Correlation

The paper of Olivier Gossner in Security Protocols in 1998 has some definitions that confuse me too much. I will cite here these definitions and my questions and I hope someone is familiar with these notions.

$$\textit{Question 1:}$$ $$I$$ is a finite set of players and and $$G=((S^i)_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, but why do we need the notion of compactness from topology?

$$\textit{Question 2:}$$ The information structure $$\mathfrak{I}=((X^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$$. Why do we need to define the information structure as a measure set which is finite and what does it mean that we now the probability measure?

$$\textit{Question 3:}$$ A communication mechanism is a triple $$\mathfrak{C}=((T_i)_i, (Y_i)_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, $$y\in Y$$ is drawn according to $$l(t)$$ and player $$i$$ is informed of $$y_i$$. $$\mathfrak{T}_i=\Delta(T_i)$$ represents the set of mixed messages for player $$i$$ and $$l$$ is extended to $$\mathfrak{T}$$ by $$l(\tau)( y)=\mathbb{E}_{\tau} l(t)( y)$$. I am totally lost in this point. What is this $$\tau$$ probability measure and what is the meaning of $$l(t)(y)$$, does this mean $$l(t,y)$$? I have never seen this symbolism $$l(t)(y)$$ again. Apparently, the way that the communication mechanism is defined comes from the measure theory, but how did he end up with the $$l$$ function defined under a $$\tau$$ probability measure?

I also struggle to understand the definitions $$2.1$$ to $$2.5$$ but I will stop here in order to find some help with the basic. Thank you in advance!

• I will try to give an explantation, however if anyone of the knows something more...please reply Sep 15, 2021 at 16:00
• Ok give it a shot... Sep 15, 2021 at 16:06

$$\textit{Question 1:}$$ As explained by Nav89, compactness of the strategy sets and continuity of the payoff function is needed to ensure equilibrium existence.

$$\textit{Question 2:}$$ I am not sure whether I truly understand your question. The assumption that the set of signals is finite is for convenience: finite probability distributions are easy to work with. A probability measure is nothing but a probability distribution. So given that I get signal $$x_i$$, I will have some belief about the signals of others $$x_{-i}$$. As defined in Section 2.2., in a game extended by an information structure, players condition their behavior in the game on the signal they get. These signals thus act like a coordination device (e.g., if the sun shines, we do XYZ...).

$$\textit{Question 3:}$$ A communication mechanism is another way of allowing players to coordinate in the game. The players send messages to the mechanism, and then the players again observe signals on which they condition their behavior (think, I see that in NYC the sun shines, you see that in LA it rains, and the mechanism will send us some information about what everyone said).

So if we send messages $$(t_1,t_2)$$, then the mechanism sends signals according to a lottery $$l(t_1,t_2)$$. Here, $$l(t_1,t_2)(x)$$ is the probability that signal profile $$x$$ is sent by the mechanism in this lottery.

Now, suppose we don't send a single message $$t_1$$ or $$t_2$$ to the mechanism, but each of us sends a mixed message $$\tau_1$$ and $$\tau_2$$ ---probability distributions over messages---to the mechanism. Then, $$l(\tau_1,\tau_2)(x)$$ is the probability that signal $$x$$ is sent back by the mechanism if I send mixed message $$\tau_1$$ and you send mixed message $$\tau_2$$.

So if $$\tau_i(t_i)$$ is the probability that $$i$$ sends $$t_i$$ in the mixed message $$\tau_i$$, then

$$l(\tau_1,\tau_2)(x)=\sum_{t_1}\sum_{t_2} \tau_1(t_1)\tau_2(t_2)l(t_1,t_2)(x).$$

• Ok, my only comment is the following...you say $l(t)(x)$, but the mechanisms says $l(t)(y)$ i think you used $x$ instead of $y$ just for your own convinience, right? If so, no need to make changes, if not then explain me what am I missing? Thank you in advance! Sep 16, 2021 at 16:48
• Yes sorry: $x$ should be $y$ in question 3. The sets $X$ and $Y$ can be different but the idea is the same. Sep 16, 2021 at 16:50
• Ok no worries. Thanks for your help! Sep 16, 2021 at 16:52

$$\textit{Question 1:}$$ The assumption of compactness is often assumed in order to guarantee existence of a solution to a problem. It is standard and as you have seen, the only thing that you need, the weakest of the assupmtions is the the finite set of strategies $$S=\Pi_{i\in I}S_i$$ (which is not necessarily finite) and the continuous function $$g$$. So these two assumptions are enough to quarantee the existence of a solution to the problem.

$$\textit{Question 2:}$$ So the information strucutre is $$\mathcal{I}=((X^i)_i,\mu)$$, where $$X_i$$ denotes the finite set of strategies of player $$i$$ and $$X=\Pi_{i\in I} X_i$$, whre this probability measure is defined from $$X$$ to $$\Delta(X)\subset[0,1]^I$$. More precisely, it holds that

$$\mu:X\to \Delta(X)\subset [0,1]^I$$

if $$x=(x^i,x^{-i})\in X$$ is drawn (which means this is a lottery) according to $$\mu$$, then player $$i$$ is informed only about his coordinate $$x^i$$. Suppose, $$I=2$$, and $$X^1=\{\text{buy}, \text{sell}\}$$ and $$X^2=\{\text{hold}, \text{sell}\}$$, then a drawn according to $$\mu$$ for both playes could be $$\mu(x^1,x^2)=\left((1/2,1/2),(3/4,1/4)\right)$$, so player $$1$$ will be infored about $$x^1$$ which means, buy with probability $$1/2$$ or sell with probability $$1/2$$ and player $$2$$ will be informed about $$x^2$$ which means hold with probablility $$3/4$$ or sell with $$1/2$$.

$$\textit{Question 3:}$$ Well a communucation mechanism is defined as a triplet $$\mathcal{C}=((T^i)_i, (Y^i)_i, l)$$ but lets make it clear what is this mechanims. Think about it like a device that takes an input this is $$T^i$$ and in returt it gives an outpout that is $$Y^i$$ and the function $$l:T\to\Delta(Y)$$ is again a lottery or better a probability distribution according to which you are taking back the message $$y\in Y$$. In other words this signal function $$l$$ tells you that if you give a message whatever this is, I can give you back an estimation, or better a probability distributuon on which you will know that something will happen with probabolity $$l(t)$$. Suppose again that $$I=2$$, $$t=(t^1,t^2)=\left(\underbrace{(\text{buy}, \text{sell})}_{t^1},\underbrace{(\text{hold}, \text{sell})}_{t^2}\right)$$. So the players decide to send this message $$t$$ in the mechanism and this in returns gives back to them $$y\in Y$$ which is, say $$l(t)=\left(\underbrace{(2/3(\text{buy}),1/3(\text{sell}))}_{y^1},\underbrace{(2/3(\text{hold}),1/3(\text{sell}))}_{y^2}\right)$$ and it is easy to understand what is the meaning of $$y$$ now. Even furhter, instead of $$T$$, you can generalize the set of finite messages sent to the communication mechanism to a mixed set of messages (generaliztaion of the $$l$$ function) s.t $$l:\mathcal{T}\to\Delta(Y)$$, where $$l(\tau)(y)$$ is again this lottery according to which the mechanism will return you $$y$$, so again it is a probability distribution or better and estimation. Thus $$l(\tau)(y)$$ denotes something like a product of vectors that give $$(\tau \times l(t))(y)$$. In other words this \tau is also a probability distribution on the space of finite messages so it can also serve as the probability measure and this is why $$l(\tau)(y)=\mathbb{E}_{\tau}l(t)(y)$$

• Oh thanks but it will take some time to check this.... Sep 15, 2021 at 16:53
• @HungerLearn no worries....I want other people here to take a look to check if I am mistaken or not....this is a difficult understanding... so maybe others could check here Sep 15, 2021 at 16:56
• well I am not sure about the last par $l(\tau)(y)$, but it seems to me as a product of the vectors from the probability distribution with the signal $y$ which comes back from the mechanism to every player. If anyone knows somthing please i would like to know it and of course endorse my answer! Thank you in advance! Sep 16, 2021 at 11:06