Celebrity games
| Autor: | Maria Serna, Carme Àlvarez, Amalia Duch, Maria J. Blesa, Arnau Messegué |
|---|---|
| Přispěvatelé: | Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals |
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: |
Computer Science::Computer Science and Game Theory
General Computer Science Star (game theory) Stability (learning theory) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Nash equilibrium Theoretical Computer Science Combinatorics symbols.namesake Diameter 0202 electrical engineering electronic engineering information engineering Price of anarchy Jocs Teoria de Time complexity Complexitat computacional Game theory Mathematics Network creation games Computational complexity Informàtica::Informàtica teòrica [Àrees temàtiques de la UPC] 010201 computation theory & mathematics Best response Bounded function symbols 020201 artificial intelligence & image processing Tree (set theory) |
| Zdroj: | Recercat. Dipósit de la Recerca de Catalunya instname UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC) |
| Popis: | We introduce Celebrity games, a new model of network creation games. In this model players have weights (W being the sum of all the player's weights) and there is a critical distance β as well as a link cost α. The cost incurred by a player depends on the cost of establishing links to other players and on the sum of the weights of those players that remain farther than the critical distance. Intuitively, the aim of any player is to be relatively close (at a distance less than β) from the rest of players, mainly of those having high weights. The main features of celebrity games are that: computing the best response of a player is NP-hard if β 1 and polynomial time solvable otherwise; they always have a pure Nash equilibrium; the family of celebrity games having a connected Nash equilibrium is characterized (the so called star celebrity games) and bounds on the diameter of the resulting equilibrium graphs are given; a special case of star celebrity games shares its set of Nash equilibrium profiles with the MaxBD games with uniform bounded distance β introduced in Bilo et al. 6. Moreover, we analyze the Price of Anarchy (PoA) and of Stability (PoS) of celebrity games and give several bounds. These are that: for non-star celebrity games PoA = PoS = m a x { 1 , W / α } ; for star celebrity games PoS = 1 and PoA = O ( m i n { n / β , W α } ) but if the Nash Equilibrium is a tree then the PoA is O ( 1 ) ; finally, when β = 1 the PoA is at most 2. The upper bounds on the PoA are complemented with some lower bounds for β = 2 . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|