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