<p>An interesting topic that I want to understand has to do with the decentralized exchange of information among a network of agents, however there is not a specific theory to make such a mathematical model and computer science seems to have made many steps helping to make model such problems. I have the following question which arises after I have read some papers and in the last one <a href="https://halshs.archives-ouvertes.fr/halshs-00367692/document" rel="nofollow noreferrer">they refer for a first time to communication networks</a> while the previous papers where having a discussion in communication mechanisms or protocols</p>
<p>What is the difference between a communication mechanism a protocol of exchanging information and communication network of agents who act strategically based on the extraneous information that they observe before starting to communicate and the endogenous information that they acquire through the communication phase and before they make they final decisions to play in the game?</p>
<p><span class="math-container">$\textbf{Hint:}$</span> This part comes from the comments comments, If you check the model of <a href="https://mpra.ub.uni-muenchen.de/25895/1/MPRA_paper_25895.pdf" rel="nofollow noreferrer">Heller, Solan and Tomala,</a> they use the cryptographic protocols of <a href="https://www.cs.umd.edu/%7Egasarch/TOPICS/secretsharing/rabinVSS.pdf" rel="nofollow noreferrer">Rabin and Ben-Or</a> and <a href="https://d1wqtxts1xzle7.cloudfront.net/49195165/Completeness_Theorems_for_Non-Cryptograp20160928-24059-99vrjz-with-cover-page-v2.pdf?Expires=1636328836&amp;Signature=O5VYtA0EaPMwriNxjXGBR2wsIDHvz1H%7EOitp8Llz5l-TMB58IVBM2umNg477jbJ5KDJuKvP3OWSHjlSRL%7EpN-3ZzrjG8JD1iwA7ETBuBkbem4FIp59GzNEVtXnpNdTuPIZhn%7EukHCKRDYZEtFvW3bhb2SNeF15imP3cDJuafnMp2IgPo73s98zMtzfQtHoPsVEhkszbxbcu7Njs6hK-yzHwgLW6in074csybr9jP-%7EPUhZv3zbXLxCXZJjtoDK%7Esx8DLkxxaAgQJ909SIucGB3yZ23gvRN7RHylJKHoXqXoOgStoN8FyZM3SPXl0PpAGuPQ0aYYv6FsoJ0NPNUppLA__&amp;Key-Pair-Id=APKAJLOHF5GGSLRBV4ZA" rel="nofollow noreferrer">Ben-Or Goldwasser and Wigderson
</a></p>
<p>They use some properties like the secure multiparty computation protocols and authentication schemes `a la Rabin and Ben-Or. Why do we need these properties?</p>
<p>Also, these cheap-talk protocols allow players to jointly compute outputs which are polynomial functions of the profile of private inputs of players, why are polynomials? and can they be something else like exponential or linear functions? What is this that determines that them to be polynomials?</p>

CC BY-SA 4.0
2021-11-06T19:36:43.367Z
Can you clarify your question?  Do you have two studied models in mind, and you are asking how they differ?  Which models?  Can you give definitions and references for both?
Neal Young
CC BY-SA 4.0
2021-11-07T22:47:52.223Z
If you check the model of Heller, Solan and Tomala, https://mpra.ub.uni-muenchen.de/25895/1/MPRA_paper_25895.pdf they try to use the cryptographic protocols of Rabin and Ben-Or (https://www.cs.umd.edu/~gasarch/TOPICS/secretsharing/rabinVSS.pdf)  and Ben-Or Goldwasser and Wigderson
Nav89
CC BY-SA 4.0
2021-11-07T22:48:24.363Z
https://d1wqtxts1xzle7.cloudfront.net/49195165/Completeness_Theorems_for_Non-Cryptograp20160928-24059-99vrjz-with-cover-page-v2.pdf?Expires=1636328836&Signature=O5VYtA0EaPMwriNxjXGBR2wsIDHvz1H~Oitp8Llz5l-TMB58IVBM2umNg477jbJ5KDJuKvP3OWSHjlSRL~pN-3ZzrjG8JD1iwA7ETBuBkbem4FIp59GzNEVtXnpNdTuPIZhn~ukHCKRDYZEtFvW3bhb2SNeF15imP3cDJuafnMp2IgPo73s98zMtzfQtHoPsVEhkszbxbcu7Njs6hK-yzHwgLW6in074csybr9jP-~PUhZv3zbXLxCXZJjtoDK~sx8DLkxxaAgQJ909SIucGB3yZ23gvRN7RHylJKHoXqXoOgStoN8FyZM3SPXl0PpAGuPQ0aYYv6FsoJ0NPNUppLA__&Key-Pair-Id=APKAJLOHF5GGSLRBV4ZA <- the link for the Ben-Or Goldwasser and Wigderson paper
Nav89
CC BY-SA 4.0
2021-11-07T22:50:40.420Z
They use some properties like the secure multiparty computation protocols and authentication schemes `a la Rabin and Ben-Or. Why do we need these properties?
Nav89
CC BY-SA 4.0
2021-11-07T22:50:47.887Z
Also, these cheap-talk protocols allow players to jointly compute outputs which are polynomial functions of the profile of private inputs of players, why are polynomials? and can they be something else like exponential or linear functions? What is this that determines that them to be polynomials?
Nav89
<communication-complexity><gt.game-theory><network-modeling><combinatorial-game-theory>
Algorithmic game theory with decentralized mechanism of exchanging information
Nav89
# Algorithmic game theory with decentralized mechanism of exchanging information

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

An interesting topic that I want to understand has to do with the decentralized exchange of information among a network of agents, however there is not a specific theory to make such a mathematical model and computer science seems to have made many steps helping to make model such problems. I have the following question which arises after I have read some papers and in the last one [they refer for a first time to communication networks](https://halshs.archives-ouvertes.fr/halshs-00367692/document) while the previous papers where having a discussion in communication mechanisms or protocols

What is the difference between a communication mechanism a protocol of exchanging information and communication network of agents who act strategically based on the extraneous information that they observe before starting to communicate and the endogenous information that they acquire through the communication phase and before they make they final decisions to play in the game?

$\textbf{Hint:}$ This part comes from the comments comments, If you check the model of [Heller, Solan and Tomala,](https://mpra.ub.uni-muenchen.de/25895/1/MPRA_paper_25895.pdf) they use the cryptographic protocols of [Rabin and Ben-Or](https://www.cs.umd.edu/%7Egasarch/TOPICS/secretsharing/rabinVSS.pdf) and [Ben-Or Goldwasser and Wigderson](https://d1wqtxts1xzle7.cloudfront.net/49195165/Completeness_Theorems_for_Non-Cryptograp20160928-24059-99vrjz-with-cover-page-v2.pdf?Expires=1636328836&Signature=O5VYtA0EaPMwriNxjXGBR2wsIDHvz1H%7EOitp8Llz5l-TMB58IVBM2umNg477jbJ5KDJuKvP3OWSHjlSRL%7EpN-3ZzrjG8JD1iwA7ETBuBkbem4FIp59GzNEVtXnpNdTuPIZhn%7EukHCKRDYZEtFvW3bhb2SNeF15imP3cDJuafnMp2IgPo73s98zMtzfQtHoPsVEhkszbxbcu7Njs6hK-yzHwgLW6in074csybr9jP-%7EPUhZv3zbXLxCXZJjtoDK%7Esx8DLkxxaAgQJ909SIucGB3yZ23gvRN7RHylJKHoXqXoOgStoN8FyZM3SPXl0PpAGuPQ0aYYv6FsoJ0NPNUppLA__&Key-Pair-Id=APKAJLOHF5GGSLRBV4ZA)

They use some properties like the secure multiparty computation protocols and authentication schemes `a la Rabin and Ben-Or. Why do we need these properties?

Also, these cheap-talk protocols allow players to jointly compute outputs which are polynomial functions of the profile of private inputs of players, why are polynomials? and can they be something else like exponential or linear functions? What is this that determines that them to be polynomials?

**Tags:** communication-complexity, gt.game-theory, network-modeling, combinatorial-game-theory

> **Comments:**
> **username_1**: Can you clarify your question?  Do you have two studied models in mind, and you are asking how they differ?  Which models?  Can you give definitions and references for both?  
> **username_0**: If you check the model of Heller, Solan and Tomala, https://mpra.ub.uni-muenchen.de/25895/1/MPRA_paper_25895.pdf they try to use the cryptographic protocols of Rabin and Ben-Or (https://www.cs.umd.edu/~gasarch/TOPICS/secretsharing/rabinVSS.pdf)  and Ben-Or Goldwasser and Wigderson  
> **username_0**: https://d1wqtxts1xzle7.cloudfront.net/49195165/Completeness_Theorems_for_Non-Cryptograp20160928-24059-99vrjz-with-cover-page-v2.pdf?Expires=1636328836&Signature=O5VYtA0EaPMwriNxjXGBR2wsIDHvz1H~Oitp8Llz5l-TMB58IVBM2umNg477jbJ5KDJuKvP3OWSHjlSRL~pN-3ZzrjG8JD1iwA7ETBuBkbem4FIp59GzNEVtXnpNdTuPIZhn~ukHCKRDYZEtFvW3bhb2SNeF15imP3cDJuafnMp2IgPo73s98zMtzfQtHoPsVEhkszbxbcu7Njs6hK-yzHwgLW6in074csybr9jP-~PUhZv3zbXLxCXZJjtoDK~sx8DLkxxaAgQJ909SIucGB3yZ23gvRN7RHylJKHoXqXoOgStoN8FyZM3SPXl0PpAGuPQ0aYYv6FsoJ0NPNUppLA__&Key-Pair-Id=APKAJLOHF5GGSLRBV4ZA <- the link for the Ben-Or Goldwasser and Wigderson paper  
> **username_0**: They use some properties like the secure multiparty computation protocols and authentication schemes `a la Rabin and Ben-Or. Why do we need these properties?  
> **username_0**: Also, these cheap-talk protocols allow players to jointly compute outputs which are polynomial functions of the profile of private inputs of players, why are polynomials? and can they be something else like exponential or linear functions? What is this that determines that them to be polynomials?  

---

## 0 answers

