Show simple item record

dc.contributor.authorFeldmann, R.en
dc.contributor.authorMavronicolas, Mariosen
dc.contributor.authorMonien, Burkharden
dc.creatorFeldmann, R.en
dc.creatorMavronicolas, Mariosen
dc.creatorMonien, Burkharden
dc.description.abstractIn 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 introduceen
dc.description.abstractthe 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)|/4en
dc.description.abstractthis 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 alloweden
dc.description.abstractif 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.source5th International Workshop on Internet and Network Economics, WINE 2009en
dc.subjectNash equilibriaen
dc.subjectNash Equilibriumen
dc.subjectCombinatorial enumerationen
dc.subjectGraph Gen
dc.subjectVoronoi cellen
dc.titleNash equilibria for voronoi games on transitive graphsen
dc.description.volume5929 LNCSen
dc.description.endingpage291 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.description.notes<p>Cited By :7</p>en
dc.source.abbreviationLect. Notes Comput. Sci.en

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record