dc.contributor.author | Feldmann, R. | en |
dc.contributor.author | Mavronicolas, Marios | en |
dc.contributor.author | Monien, Burkhard | en |
dc.creator | Feldmann, R. | en |
dc.creator | Mavronicolas, Marios | en |
dc.creator | Monien, Burkhard | en |
dc.date.accessioned | 2019-11-13T10:40:02Z | |
dc.date.available | 2019-11-13T10:40:02Z | |
dc.date.issued | 2009 | |
dc.identifier.issn | 0302-9743 | |
dc.identifier.uri | http://gnosis.library.ucy.ac.cy/handle/7/53921 | |
dc.description.abstract | In a Voronoi game, each of κ≥2 players chooses a vertex in a graph G=〈V(G), E(G)〉. The utility of a player measures her Voronoi cell: the set of vertices that are closest to her chosen vertex than to that of another player. In a Nash equilibrium, unilateral deviation of a player to another vertex is not profitable. We focus on various, symmetry-possessing classes of transitive graphs: the vertex-transitive and generously vertex-transitive graphs, and the more restricted class of friendly graphs we introduce | en |
dc.description.abstract | the latter encompasses as special cases the popular d-dimensional bipartite torus Td =Td(2p1, ⋯, 2p d) with even sides 2p1, ⋯, 2pd and dimension d≥2, and a subclass of the Johnson graphs. Would transitivity enable bypassing the explicit enumeration of Voronoi cells? To argue in favor, we resort to a technique using automorphisms, which suffices alone for generously vertex-transitive graphs with κ=2. To go beyond the case κ=2, we show the Two-Guards Theorem for Friendly Graphs: whenever two of the three players are located at an antipodal pair of vertices in a friendly graph G, the third player receives a utility of |V(G)|/4+|ω|/12, where Ω is the intersection of the three Voronoi cells. If the friendly graph G is bipartite and has odd diameter, the utility of the third player is fixed to |V(G)|/4 | en |
dc.description.abstract | this allows discarding the third player when establishing that such a triple of locations is a Nash equilibrium. Combined with appropriate automorphisms and without explicit enumeration, the Two-Guards Theorem implies the existence of a Nash equilibrium for any friendly graph G with κ=4, with colocation of players allowed | en |
dc.description.abstract | if colocation is forbidden, existence still holds under the additional assumption that G is bipartite and has odd diameter. For the case κ=3, we have been unable to bypass the explicit enumeration of Voronoi cells. Combined with appropriate automorphisms and explicit enumeration, the Two-Guards Theorem implies the existence of a Nash equilibrium for (i) the 2-dimensional torus T 2 with odd diameter ∑jε[2]Pj and κ=3, and (ii) the hypercube Hd with odd d and κ=3. In conclusion, transitivity does not seem sufficient for bypassing explicit enumeration: far-reaching challenges in combinatorial enumeration are in sight, even for values of κ as small as 3. © 2009 Springer-Verlag Berlin Heidelberg. | en |
dc.source | 5th International Workshop on Internet and Network Economics, WINE 2009 | en |
dc.source.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-76649083969&doi=10.1007%2f978-3-642-10841-9_26&partnerID=40&md5=c48bd3c10c96e6648cd738ef8939d7f4 | |
dc.subject | Internet | en |
dc.subject | Profitability | en |
dc.subject | Wine | en |
dc.subject | Automorphisms | en |
dc.subject | Nash equilibria | en |
dc.subject | Nash Equilibrium | en |
dc.subject | Colocations | en |
dc.subject | Combinatorial enumeration | en |
dc.subject | Graph G | en |
dc.subject | Hypercube | en |
dc.subject | Voronoi | en |
dc.subject | Voronoi cell | en |
dc.title | Nash equilibria for voronoi games on transitive graphs | en |
dc.type | info:eu-repo/semantics/article | |
dc.identifier.doi | 10.1007/978-3-642-10841-9_26 | |
dc.description.volume | 5929 LNCS | en |
dc.description.startingpage | 280 | |
dc.description.endingpage | 291 | |
dc.author.faculty | 002 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied Sciences | |
dc.author.department | Τμήμα Πληροφορικής / Department of Computer Science | |
dc.type.uhtype | Article | en |
dc.description.notes | <p>Cited By :7</p> | en |
dc.source.abbreviation | Lect. Notes Comput. Sci. | en |