2026-07-21T21:12:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:219 2024-03-06T11:06:06Z ddc:004 open_access

Local-Effect Games Leyton-Brown, Kevin Tennenholtz, Moshe compact representation of games congestion games local-effect This talk will survey two graphical models which the authors have proposed for compactly representing single-shot, finite-action games in which a large number of agents contend for scarce resources. The first model considered is Local-Effect Games (LEGs). These games often (but not always) have pure-strategy Nash equilibria. Finding a potential function is a good technique for finding such equilibria. We give a complete characterization of which LEGs have potential functions and provide the functions in each case; we also show a general case where pure-strategy equilibria exist in the absence of potential functions. Action-graph games (AGGs) are a fully expressive game representation which can compactly express both strict and context-specific independence between players' utility functions, and which generalize LEGs. We present algorithms for computing both symmetric and arbitrary equilibria of AGGs, based on a continuation method proposed by Govindan and Wilson. We analyze the worst- case cost of computing the Jacobian of the payoff function, the exponential- time bottleneck step of this algorithm, and in all cases achieve exponential speedup. When the indegree of G is bounded by a constant and the game is symmetric, the Jacobian can be computed in polynomial time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kevin Leyton-Brown and Moshe Tennenholtz 2005 Is Part Of Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.05011.11 urn:nbn:de:0030-drops-2190 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.11 eng https://creativecommons.org/licenses/by/4.0/legalcode