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.date.accessioned2019-11-13T10:40:02Z
dc.date.available2019-11-13T10:40:02Z
dc.date.issued2009
dc.identifier.issn0302-9743
dc.identifier.urihttp://gnosis.library.ucy.ac.cy/handle/7/53921
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.source.urihttps://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.subjectInterneten
dc.subjectProfitabilityen
dc.subjectWineen
dc.subjectAutomorphismsen
dc.subjectNash equilibriaen
dc.subjectNash Equilibriumen
dc.subjectColocationsen
dc.subjectCombinatorial enumerationen
dc.subjectGraph Gen
dc.subjectHypercubeen
dc.subjectVoronoien
dc.subjectVoronoi cellen
dc.titleNash equilibria for voronoi games on transitive graphsen
dc.typeinfo:eu-repo/semantics/article
dc.identifier.doi10.1007/978-3-642-10841-9_26
dc.description.volume5929 LNCSen
dc.description.startingpage280
dc.description.endingpage291
dc.author.faculty002 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied Sciences
dc.author.departmentΤμήμα Πληροφορικής / Department of Computer Science
dc.type.uhtypeArticleen
dc.description.notes<p>Cited By :7</p>en
dc.source.abbreviationLect. Notes Comput. Sci.en


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record