Max Celebrity Games
| Autor: | Carme Àlvarez, Arnau Messegué |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Combinatorics
010201 computation theory & mathematics Best response 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing 0102 computer and information sciences 02 engineering and technology New variant Undirected graph 01 natural sciences Upper and lower bounds Mathematics |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783319497860 WAW |
| DOI: | 10.1007/978-3-319-49787-7_8 |
| Popis: | We introduce Max celebrity games a new variant of Celebrity games defined in [4]. In both models players have weights and there is a critical distance \(\beta \) as well as a link cost \(\alpha \). In the max celebrity model the cost of a player depends on the cost of establishing links to other players and on the maximum of the weights of those nodes that are farther away than \(\beta \) (instead of the sum of weights as in celebrity games). The main results for \(\beta >1\) are that: computing a best response for a player is NP-hard; the optimal social cost of a celebrity game depends on the relation between \(\alpha \) and \(w_{max}\); ne always exist and ne graphs are either connected or a set of \(r\ge 1\) connected components where at most one of them is not an isolated node; for the class of connected ne graphs we obtain a general upper bound of \(2 \beta +2\) for the diameter. We also analyze the price of anarchy (PoA) of connected ne graphs and we show that there exist games \(\varGamma \) such that \(\text {PoA} (\varGamma )=\varTheta (n/\beta )\); modifying the cost of a player we guarantee that all ne graphs are connected, but the diameter might be \(n-1\). Finally, when \(\beta =1\), computing a best response for a player is polynomial time solvable and the \(\text {PoA} = O(w_{max}/w_{min})\). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|