Computing Approximate Pure Nash Equilibria in Digraph k-Coloring Games. Raffaello, C., MICHELE, F., & Gianpiero, M. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, (AAMAS) 2017, pages 911–919, May, 2017. ACM. abstract bibtex We investigate approximate pure Nash equilibria in digraph k-coloring games, where we are given an unweighted directed graph together with a set of k colors. Vertices represent agents and arcs capture their mutual unidirectional interests. The strategy set of each agent v consists of the k colors and the payoff of v in a given state or coloring is given by the number of outgoing neighbors with a color different from the one of v. Such games form some of the basic payoff structures in game theory, model lots of real-world scenarios with selfish agents and extend or are related to several fundamental class of games. It is known that the problem of understanding whether the game admits a pure Nash equilibrium is NP-complete. Therefore we focus on designing polynomial time algorithms that return approximate Nash equilibria. Informally, we say that a coloring is a λ-Nash equilibrium (for some λ ≥ 1) if no agent can strictly improve her payoff by a multiplicative factor of λ by changing color. We first propose a deterministic polynomial time algorithm that, for any k ≥ 3, returns a k-coloring that is a Δo(G)-Nash equilibrium, where Δo(G) is the maximum outdegree of the digraph. We then provide our two main results: i) By exploiting the constructive version of the well known Lováasz Local Lemma, we show a randomized algorithm with polynomial expected running time that, given any constant k ≥ 2, computes a constant-Nash equilibrium for a broad class of digraphs, i.e., for digraphs where, for any v ∈ V, δo/v(G) = Ω(ln Δo(G) + ln Δi(G)) where Δo(G) (resp. Δi(G)) is the maximum outgoing (resp. maximum ingoing) degree of G, and δo/v(G) is the outgoing degree of agent v. ii) For generic digraphs, we show a deterministic polynomial time algorithm that computes a (1+ε)-Nash equilibrium, for any ε > 0, by using O(log n/ε) colors.
@inproceedings{carosi_raffaello_computing_2017,
title = {Computing {Approximate} {Pure} {Nash} {Equilibria} in {Digraph} k-{Coloring} {Games}},
isbn = {978-1-5108-5507-6},
abstract = {We investigate approximate pure Nash equilibria in digraph k-coloring games, where we are given an unweighted directed graph together with a set of k colors. Vertices represent agents and arcs capture their mutual unidirectional interests. The strategy set of each agent v consists of the k colors and the payoff of v in a given state or coloring is given by the number of outgoing neighbors with a color different from the one of v. Such games form some of the basic payoff structures in game theory, model lots of real-world scenarios with selfish agents and extend or are related to several fundamental class of games. It is known that the problem of understanding whether the game admits a pure Nash equilibrium is NP-complete. Therefore we focus on designing polynomial time algorithms that return approximate Nash equilibria. Informally, we say that a coloring is a λ-Nash equilibrium (for some λ ≥ 1) if no agent can strictly improve her payoff by a multiplicative factor of λ by changing color. We first propose a deterministic polynomial time algorithm that, for any k ≥ 3, returns a k-coloring that is a Δo(G)-Nash equilibrium, where Δo(G) is the maximum outdegree of the digraph. We then provide our two main results: i) By exploiting the constructive version of the well known Lováasz Local Lemma, we show a randomized algorithm with polynomial expected running time that, given any constant k ≥ 2, computes a constant-Nash equilibrium for a broad class of digraphs, i.e., for digraphs where, for any v ∈ V, δo/v(G) = Ω(ln Δo(G) + ln Δi(G)) where Δo(G) (resp. Δi(G)) is the maximum outgoing (resp. maximum ingoing) degree of G, and δo/v(G) is the outgoing degree of agent v. ii) For generic digraphs, we show a deterministic polynomial time algorithm that computes a (1+ε)-Nash equilibrium, for any ε \> 0, by using O(log n/ε) colors.},
booktitle = {Proceedings of the 16th {Conference} on {Autonomous} {Agents} and {MultiAgent} {Systems}, ({AAMAS}) 2017},
publisher = {ACM},
author = {Carosi Raffaello and FLAMMINI MICHELE and MONACO Gianpiero},
editor = {Kate Larson Michael Winikoff Sanmay Das Edmund Durfee},
month = may,
year = {2017},
pages = {911--919},
annote = {Contributo in Atti di convegno},
}
Downloads: 0
{"_id":"4AGBPekMWFMDsTbQr","bibbaseid":"raffaello-michele-gianpiero-computingapproximatepurenashequilibriaindigraphkcoloringgames-2017","authorIDs":[],"author_short":["Raffaello, C.","MICHELE, F.","Gianpiero, M."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","title":"Computing Approximate Pure Nash Equilibria in Digraph k-Coloring Games","isbn":"978-1-5108-5507-6","abstract":"We investigate approximate pure Nash equilibria in digraph k-coloring games, where we are given an unweighted directed graph together with a set of k colors. Vertices represent agents and arcs capture their mutual unidirectional interests. The strategy set of each agent v consists of the k colors and the payoff of v in a given state or coloring is given by the number of outgoing neighbors with a color different from the one of v. Such games form some of the basic payoff structures in game theory, model lots of real-world scenarios with selfish agents and extend or are related to several fundamental class of games. It is known that the problem of understanding whether the game admits a pure Nash equilibrium is NP-complete. Therefore we focus on designing polynomial time algorithms that return approximate Nash equilibria. Informally, we say that a coloring is a λ-Nash equilibrium (for some λ ≥ 1) if no agent can strictly improve her payoff by a multiplicative factor of λ by changing color. We first propose a deterministic polynomial time algorithm that, for any k ≥ 3, returns a k-coloring that is a Δo(G)-Nash equilibrium, where Δo(G) is the maximum outdegree of the digraph. We then provide our two main results: i) By exploiting the constructive version of the well known Lováasz Local Lemma, we show a randomized algorithm with polynomial expected running time that, given any constant k ≥ 2, computes a constant-Nash equilibrium for a broad class of digraphs, i.e., for digraphs where, for any v ∈ V, δo/v(G) = Ω(ln Δo(G) + ln Δi(G)) where Δo(G) (resp. Δi(G)) is the maximum outgoing (resp. maximum ingoing) degree of G, and δo/v(G) is the outgoing degree of agent v. ii) For generic digraphs, we show a deterministic polynomial time algorithm that computes a (1+ε)-Nash equilibrium, for any ε > 0, by using O(log n/ε) colors.","booktitle":"Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, (AAMAS) 2017","publisher":"ACM","author":[{"firstnames":["Carosi"],"propositions":[],"lastnames":["Raffaello"],"suffixes":[]},{"firstnames":["FLAMMINI"],"propositions":[],"lastnames":["MICHELE"],"suffixes":[]},{"firstnames":["MONACO"],"propositions":[],"lastnames":["Gianpiero"],"suffixes":[]}],"editor":[{"firstnames":["Kate","Larson","Michael","Winikoff","Sanmay","Das","Edmund"],"propositions":[],"lastnames":["Durfee"],"suffixes":[]}],"month":"May","year":"2017","pages":"911–919","annote":"Contributo in Atti di convegno","bibtex":"@inproceedings{carosi_raffaello_computing_2017,\n\ttitle = {Computing {Approximate} {Pure} {Nash} {Equilibria} in {Digraph} k-{Coloring} {Games}},\n\tisbn = {978-1-5108-5507-6},\n\tabstract = {We investigate approximate pure Nash equilibria in digraph k-coloring games, where we are given an unweighted directed graph together with a set of k colors. Vertices represent agents and arcs capture their mutual unidirectional interests. The strategy set of each agent v consists of the k colors and the payoff of v in a given state or coloring is given by the number of outgoing neighbors with a color different from the one of v. Such games form some of the basic payoff structures in game theory, model lots of real-world scenarios with selfish agents and extend or are related to several fundamental class of games. It is known that the problem of understanding whether the game admits a pure Nash equilibrium is NP-complete. Therefore we focus on designing polynomial time algorithms that return approximate Nash equilibria. Informally, we say that a coloring is a λ-Nash equilibrium (for some λ ≥ 1) if no agent can strictly improve her payoff by a multiplicative factor of λ by changing color. We first propose a deterministic polynomial time algorithm that, for any k ≥ 3, returns a k-coloring that is a Δo(G)-Nash equilibrium, where Δo(G) is the maximum outdegree of the digraph. We then provide our two main results: i) By exploiting the constructive version of the well known Lováasz Local Lemma, we show a randomized algorithm with polynomial expected running time that, given any constant k ≥ 2, computes a constant-Nash equilibrium for a broad class of digraphs, i.e., for digraphs where, for any v ∈ V, δo/v(G) = Ω(ln Δo(G) + ln Δi(G)) where Δo(G) (resp. Δi(G)) is the maximum outgoing (resp. maximum ingoing) degree of G, and δo/v(G) is the outgoing degree of agent v. ii) For generic digraphs, we show a deterministic polynomial time algorithm that computes a (1+ε)-Nash equilibrium, for any ε \\> 0, by using O(log n/ε) colors.},\n\tbooktitle = {Proceedings of the 16th {Conference} on {Autonomous} {Agents} and {MultiAgent} {Systems}, ({AAMAS}) 2017},\n\tpublisher = {ACM},\n\tauthor = {Carosi Raffaello and FLAMMINI MICHELE and MONACO Gianpiero},\n\teditor = {Kate Larson Michael Winikoff Sanmay Das Edmund Durfee},\n\tmonth = may,\n\tyear = {2017},\n\tpages = {911--919},\n\tannote = {Contributo in Atti di convegno},\n}\n\n","author_short":["Raffaello, C.","MICHELE, F.","Gianpiero, M."],"editor_short":["Durfee, K. L. M. W. S. D. E."],"key":"carosi_raffaello_computing_2017","id":"carosi_raffaello_computing_2017","bibbaseid":"raffaello-michele-gianpiero-computingapproximatepurenashequilibriaindigraphkcoloringgames-2017","role":"author","urls":{},"downloads":0},"bibtype":"inproceedings","biburl":"https://drive.google.com/uc?export=download&id=1Yz9Tay6l8reLuIpeLRQenrn7GKZ--M4o","creationDate":"2020-11-08T19:40:44.226Z","downloads":0,"keywords":[],"search_terms":["computing","approximate","pure","nash","equilibria","digraph","coloring","games","raffaello","michele","gianpiero"],"title":"Computing Approximate Pure Nash Equilibria in Digraph k-Coloring Games","year":2017,"dataSources":["3w7wESM3KavuMMg2b"]}