A Game-Theoretic Approach to Self-Stabilization with Selfish Agents
Self-stabilization is an excellent approach for adding fault tolerance to a distributed multi-agent system. However, two properties of self-stabilization theory, convergence and closure, may not be satisfied if agents are selfish. To guarantee convergence, we formulate the problem as a stochastic Ba...
Gorde:
| Egile Nagusiak: | , |
|---|---|
| Formatua: | Artikulua |
| Argitaratua: |
2021
|
| Gaiak: | |
| Sarrera elektronikoa: | https://arxiv.org/abs/2108.07362 http://arxiv.org/abs/2108.07362 |
| Etiketak: |
Etiketarik gabe, Izan zaitez lehena erregistro honi etiketa jartzen!
|
| _version_ | 1879174004722368512 |
|---|---|
| author | Ramtin, Amir Reza Towsley, Don |
| author_browse | Ramtin, Amir Reza Towsley, Don |
| author_facet | Ramtin, Amir Reza Towsley, Don |
| author_sort | Ramtin, Amir Reza |
| building | arXiv |
| collection | Acceso abierto |
| description | Self-stabilization is an excellent approach for adding fault tolerance to a distributed multi-agent system. However, two properties of self-stabilization theory, convergence and closure, may not be satisfied if agents are selfish. To guarantee convergence, we formulate the problem as a stochastic Bayesian game and introduce probabilistic self-stabilization to adjust the probabilities of rules with behavior strategies. This satisfies agents' self-interests such that no agent deviates the rules. To guarantee closure in the presence of selfish agents, we propose fault-containment as a method to constrain legitimate configurations of the self-stabilizing system to be Nash equilibria. We also assume selfish agents as capable of performing unauthorized actions at any time, which threatens both properties, and present a stepwise solution to handle it. As a case study, we consider the problem of distributed clustering and propose five self-stabilizing algorithms for forming clusters. Simulation results show that our algorithms react correctly to rule deviations and outperform comparable schemes in terms of fairness and stabilization time. |
| first_indexed | 2026-10-16T00:06:17Z |
| format | Article |
| fullrecord | <oai_dc:dc xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ https://www.openarchives.org/OAI/2.0/oai_dc.xsd"><identifier>arxiv-2108.07362</identifier><datestamp>2022-09-12</datestamp>
<dc:title>A Game-Theoretic Approach to Self-Stabilization with Selfish Agents</dc:title>
<dc:creator>Ramtin, Amir Reza</dc:creator>
<dc:creator>Towsley, Don</dc:creator>
<dc:subject>Distributed, Parallel, and Cluster Computing</dc:subject>
<dc:subject>Computer Science and Game Theory</dc:subject>
<dc:description>Self-stabilization is an excellent approach for adding fault tolerance to a distributed multi-agent system. However, two properties of self-stabilization theory, convergence and closure, may not be satisfied if agents are selfish. To guarantee convergence, we formulate the problem as a stochastic Bayesian game and introduce probabilistic self-stabilization to adjust the probabilities of rules with behavior strategies. This satisfies agents' self-interests such that no agent deviates the rules. To guarantee closure in the presence of selfish agents, we propose fault-containment as a method to constrain legitimate configurations of the self-stabilizing system to be Nash equilibria. We also assume selfish agents as capable of performing unauthorized actions at any time, which threatens both properties, and present a stepwise solution to handle it. As a case study, we consider the problem of distributed clustering and propose five self-stabilizing algorithms for forming clusters. Simulation results show that our algorithms react correctly to rule deviations and outperform comparable schemes in terms of fairness and stabilization time. </dc:description>
<dc:date>2021-08-16</dc:date>
<dc:date>2022-09-08</dc:date>
<dc:type>text</dc:type>
<dc:identifier>https://arxiv.org/abs/2108.07362</dc:identifier>
<dc:identifier>http://arxiv.org/abs/2108.07362</dc:identifier>
</oai_dc:dc> |
| id | arxiv-2108.07362 |
| institution | arXiv |
| last_indexed | 2026-10-16T00:06:17Z |
| publishDate | 2021 |
| publishDateRange | 2021 |
| publishDateSort | 2021 |
| record_format | oai_dc |
| spelling | arxiv-2108.073622022-09-12 A Game-Theoretic Approach to Self-Stabilization with Selfish Agents Ramtin, Amir Reza Towsley, Don Distributed, Parallel, and Cluster Computing Computer Science and Game Theory Self-stabilization is an excellent approach for adding fault tolerance to a distributed multi-agent system. However, two properties of self-stabilization theory, convergence and closure, may not be satisfied if agents are selfish. To guarantee convergence, we formulate the problem as a stochastic Bayesian game and introduce probabilistic self-stabilization to adjust the probabilities of rules with behavior strategies. This satisfies agents' self-interests such that no agent deviates the rules. To guarantee closure in the presence of selfish agents, we propose fault-containment as a method to constrain legitimate configurations of the self-stabilizing system to be Nash equilibria. We also assume selfish agents as capable of performing unauthorized actions at any time, which threatens both properties, and present a stepwise solution to handle it. As a case study, we consider the problem of distributed clustering and propose five self-stabilizing algorithms for forming clusters. Simulation results show that our algorithms react correctly to rule deviations and outperform comparable schemes in terms of fairness and stabilization time. 2021-08-16 2022-09-08 text https://arxiv.org/abs/2108.07362 http://arxiv.org/abs/2108.07362 |
| spellingShingle | Distributed, Parallel, and Cluster Computing Computer Science and Game Theory Ramtin, Amir Reza Towsley, Don A Game-Theoretic Approach to Self-Stabilization with Selfish Agents |
| title | A Game-Theoretic Approach to Self-Stabilization with Selfish Agents |
| title_full | A Game-Theoretic Approach to Self-Stabilization with Selfish Agents |
| title_fullStr | A Game-Theoretic Approach to Self-Stabilization with Selfish Agents |
| title_full_unstemmed | A Game-Theoretic Approach to Self-Stabilization with Selfish Agents |
| title_short | A Game-Theoretic Approach to Self-Stabilization with Selfish Agents |
| title_sort | game theoretic approach to self stabilization with selfish agents |
| topic | Distributed, Parallel, and Cluster Computing Computer Science and Game Theory |
| url | https://arxiv.org/abs/2108.07362 http://arxiv.org/abs/2108.07362 |
| work_keys_str_mv | AT ramtinamirreza agametheoreticapproachtoselfstabilizationwithselfishagents AT towsleydon agametheoreticapproachtoselfstabilizationwithselfishagents AT ramtinamirreza gametheoreticapproachtoselfstabilizationwithselfishagents AT towsleydon gametheoreticapproachtoselfstabilizationwithselfishagents |