# How is a communication protocol a mechanism?

Given a finite set $\Sigma$ and a positive integer $n$, a mechanism is a set $\{ \mu_x \vert x \in \Sigma^n \}$ such that $\mu_x$ is a probability measure on some $\sigma-$algebra for each $x$.

Now given a communication protocol $P$ between two privately coin-flipping parties $A$ and $B$ who start with the inputs $x$ and $y$ respectively one defines this quantity called the $VIEW^A_P(x,y)$ : a joint probability distribution over $x$, the transcript of the protocol $P$, private randomness of the party $A$, where the probability space is private randomness of both parties"

• What does the stuff in the quotes mean?

• Can someone help understand how is this $VIEW^A_P(x,y)$ a mechanism" as defined earlier? (For this to be a mechanism, $VIEW^A_P(x,y)$ for a fixed $x$, has to assign a probability to some set of outcomes and I am unable to see as to which set of outcomes is it assigning a probability and how)

A transcript of a protocol will be a sequence of private coin tosses and bits exchanged in every step. So if one fixes both $x$ and $y$ then I can imagine that a probability can be assigned to a protocol - which would be the probability for that sequences of coin tosses to have happened. But still whaht is an "event" here is not clear since I can't see a natural way to group together these "outcomes" (each of which is now a possible transcript when started with a $x$ and $y$).

But if one fixes only $x$ then nothing is clear to me..

• The notation suggests that you are fixing both $x$ and $y$. If you're not sure, keep on reading and see how it's used. – Yuval Filmus Jul 9 '15 at 19:58

The view of Alice is what Alice gets to see; it is a probability distribution that depends on the inputs of both players $x,y$. It is a distribution over triples $(x,\tau,r_A)$, where $x$ is Alice's input, $\tau$ is the transcript of the protocol, and $r_A$ is Alice's private randomness. This probability distribution depends both on $x$ and on Bob's input $y$.
Here is how to generate this probability distribution, given a protocol $P$ and the inputs $x,y$ of both players. Generate the shared randomness $r$ according to its distribution, and Alice's private randomness $r_A$ according to its distribution. Run $P$, obtaining a transcript $\tau$. Output $(x,\tau,r_A)$.
• (1) What do you mean by "generate the shared randomness" ? (2) If I understand you right then what we have is this : $VIEW^A_P$ is a "mechanism" because it gives a family of probability distributions $\mu_y$ indexed by the string $y$ that $B$ has. And $\mu_y$ assigns a probability to the "outcomes" indexed by the triples $(x,\tau,r_A)$ which are consistent with $A$ and $B$ starting with $x$ and $y$ respectively. Am I right? – user6818 Jul 10 '15 at 22:03
• (1) Toss an infinite sequence of coins, which will be used as the shared randomness. (2) You might be right, though the notation suggests that VIEW is a function of both $x$ and $y$. On the other hand, since $x$ is part of the domain, your interpretation also makes sense. – Yuval Filmus Jul 10 '15 at 22:04