### Abstract

We consider in this paper a simple model for human interactions as service providers of different resources over social networks, and study the dynamics of selfish behavior of such social entities using a game-theoretic model known as binary-preference capacitated selfish replication (CSR) game. It is known that such games have an associated ordinal potential function, and hence always admit a pure-strategy Nash equilibrium (NE). We study the price of anarchy of such games, and show that it is bounded above by 3; we further provide some instances for which the price of anarchy is at least 2. We also devise a quasi-polynomial algorithm O(n2+ln D) which can find, in a distributed manner, an allocation profile that is within a constant factor of the optimal allocation, and hence of any pure-strategy Nash equilibrium of the game, where the parameters n, and D denote, respectively, the number of players, and the diameter of the network. We further show that when the underlying network has a tree structure, every globally optimal allocation is a Nash equilibrium, which can be reached in only linear time.

Original language | English (US) |
---|---|

Title of host publication | 54rd IEEE Conference on Decision and Control,CDC 2015 |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 3568-3573 |

Number of pages | 6 |

ISBN (Electronic) | 9781479978861 |

DOIs | |

State | Published - Feb 8 2015 |

Event | 54th IEEE Conference on Decision and Control, CDC 2015 - Osaka, Japan Duration: Dec 15 2015 → Dec 18 2015 |

### Publication series

Name | Proceedings of the IEEE Conference on Decision and Control |
---|---|

Volume | 54rd IEEE Conference on Decision and Control,CDC 2015 |

ISSN (Print) | 0743-1546 |

### Other

Other | 54th IEEE Conference on Decision and Control, CDC 2015 |
---|---|

Country | Japan |

City | Osaka |

Period | 12/15/15 → 12/18/15 |

### Fingerprint

### Keywords

- Capacitated selfish replication game
- optimal allocation
- potential function
- price of anarchy
- pure Nash equilibrium (NE)
- quasi-polynomial algorithm

### ASJC Scopus subject areas

- Control and Systems Engineering
- Modeling and Simulation
- Control and Optimization

### Cite this

*54rd IEEE Conference on Decision and Control,CDC 2015*(pp. 3568-3573). [7402771] (Proceedings of the IEEE Conference on Decision and Control; Vol. 54rd IEEE Conference on Decision and Control,CDC 2015). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2015.7402771