The Role of A-priori Information in Networks of Rational Agents
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2019
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911509714567168 |
|---|---|
| author | Afek, Yehuda Mansour, Yishay Rafaeli, Shaked Sulamy, Moshe |
| author_facet | Afek, Yehuda Mansour, Yishay Rafaeli, Shaked Sulamy, Moshe |
| contents | Until now, distributed algorithms for rational agents have assumed a-priori knowledge of $n$, the size of the network. This assumption is challenged here by proving how much a-priori knowledge is necessary for equilibrium in different distributed computing problems. Duplication - pretending to be more than one agent - is the main tool used by agents to deviate and increase their utility when not enough knowledge about $n$ is given. The a-priori knowledge of $n$ is formalized as a Bayesian setting where at the beginning of the algorithm agents only know a prior $σ$, a distribution from which they know $n$ originates. We begin by providing new algorithms for the Knowledge Sharing and Coloring problems when $n$ is a-priori known to all agents. We then prove that when agents have no a-priori knowledge of $n$, i.e., the support for $σ$ is infinite, equilibrium is impossible for the Knowledge Sharing problem. Finally, we consider priors with finite support and find bounds on the necessary interval $[α,β]$ that contains the support of $σ$, i.e., $α\leq n \leq β$, for which we have an equilibrium. When possible, we extend these bounds to hold for any possible protocol. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1910_02239 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | The Role of A-priori Information in Networks of Rational Agents Afek, Yehuda Mansour, Yishay Rafaeli, Shaked Sulamy, Moshe Distributed, Parallel, and Cluster Computing Until now, distributed algorithms for rational agents have assumed a-priori knowledge of $n$, the size of the network. This assumption is challenged here by proving how much a-priori knowledge is necessary for equilibrium in different distributed computing problems. Duplication - pretending to be more than one agent - is the main tool used by agents to deviate and increase their utility when not enough knowledge about $n$ is given. The a-priori knowledge of $n$ is formalized as a Bayesian setting where at the beginning of the algorithm agents only know a prior $σ$, a distribution from which they know $n$ originates. We begin by providing new algorithms for the Knowledge Sharing and Coloring problems when $n$ is a-priori known to all agents. We then prove that when agents have no a-priori knowledge of $n$, i.e., the support for $σ$ is infinite, equilibrium is impossible for the Knowledge Sharing problem. Finally, we consider priors with finite support and find bounds on the necessary interval $[α,β]$ that contains the support of $σ$, i.e., $α\leq n \leq β$, for which we have an equilibrium. When possible, we extend these bounds to hold for any possible protocol. |
| title | The Role of A-priori Information in Networks of Rational Agents |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/1910.02239 |