Score:1

Algorithmic game theory and protocol design for communication

ua flag

There is a field of exchanging information that combines cryptography and game theory. I am interested in understanding this field, but it's a little complex for me. To begin with there is a paper of Barany which shows that instead of having a centralized mechanism of information where a mediator can inform the players about what strategy to follow, the players instead can replace the mediator with a decentralized exchange of information if they are more than four. This has generated the idea to design a protocol of communication which has some properties and rules as well, that are followed by the players in order to exchange information which is going to give at least the same outcomes with the centralized mechanism with the mediator. However this paper is a little old and not clear for how to construct these protocols. Even further, there are two other papers, Heller et al and Forges where they simulate a cheap talk phase for the protocol of information exchange, however I can not understand many notions that they use. For example:

  1. secure multiparty computation - why do they need this? for my understanding every player is a receiver and a sender of a message either this is simultaneous or they send a message the one other the other. Let us assume that we have the four players of Barany, then player $1$ will send a message to the other three players, that is $s_{1\to-1}$, however she will also receive messages from the other players that is $r_{-1\to 1}$ and they send these messages in private, however they can broadcast a public announcement, that is for players $1$ a message that was send to her by the other players and maybe this serves as some kind of verification if the messages that they send follow some verification rule. So, does multiparty computation has to do with this part of exchange of messages and the existence of some rule that verifies if the players are telling the truth at some point?

  2. broadcast and secret sharing schemes, seem to be a part of the secure multiparty computation as well, but the fact that sharing a secret privately with each one it makes me confused as an idea to model it especially when I read that such schemes are using some polynomial interpolation. Let me be more clear, suppose that the messages, namely the information that they share are things about their wealth which are modelled usually as random variables. Agents have a type in economic models and this type may be restricted in some random variable $s_i\sim N(\mu_{s_i},\sigma_{s_i}^2)$ for every $i$ or their position in the market, which is usually a sum of random variables. In this case, how can we say that the players will share this secret $s=(s_1,s_2,s_3,s_4)$? How are they going to share their ``type" with the others or even the information about their whole wealth and without telling a lie to each other? I think that is why they use punishment strategies in the cheap talk phase, aren't they?

  3. Also these games assume that they have a monitor phase which denoted with a history of the game which is a cylinder or product $\sigma$-algebra of the previous stages of the game.

  4. Do we want to prove the secure protocol design in order to prove that the mechanism can not be manipulated? Namely is this something like the incentive compatibility criteria that are used by Myerson, Kreps etc in game theory?

To sum up, all these are part of the so-called theory of implementation and there are too many issues that I also can not understand like immune protocol to deviations or lies and how the messages that are shared privately are encrypted-decrypted with permutation etc but my questions are not going to end. What I want is to understand why do we need these features and I find a simple paper that says the properties that a protocol of communication must have when no mediator exists?

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.