LP-Based Covering Games with Low Price of Anarchy

Piliouras, Georgios; Valla, Tomáš; Végh, László
July 2015
Theory of Computing Systems;Jul2015, Vol. 57 Issue 1, p238
Academic Journal
We design a new class of vertex and set cover games, where the price of anarchy bounds match the best known constant factor approximation guarantees for the centralized optimization problems for linear and also for submodular costs. This is in contrast to all previously studied covering games, where the price of anarchy grows linearly with the size of the game. Both the game design and the price of anarchy results are based on structural properties of the linear programming relaxations. For linear costs we also exhibit simple best response dynamics that converge to Nash equilibria in linear time.


Related Articles

  • ON MINIMAL DOMINATING SETS FOR SIGNED GRAPHS. Ashraf, P. K.; Germina, K. A. // Advances & Applications in Discrete Mathematics;Apr2015, Vol. 15 Issue 2, p101 

    A graph with its edges labeled either as positive or negative is called a signed graph. Denoting N(u) to be the open neighbourhood of a vertex u, if Σ = (V, E, σ) is a signed graph, a subset D ⊆ V of vertices of Σ is a dominating set, if there exists a marking μ : V →...

  • Signed Roman $$k$$ -Domination in Graphs. Henning, Michael; Volkmann, Lutz // Graphs & Combinatorics;Jan2016, Vol. 32 Issue 1, p175 

    Let $$k\ge 1$$ be an integer, and let $$G$$ be a finite and simple graph with vertex set $$V(G)$$ . A signed Roman $$k$$ -dominating function (SRkDF) on a graph $$G$$ is a function $$f:V(G)\rightarrow \{-1,1,2\}$$ satisfying the conditions that (i) $$\sum _{x\in N[v]}f(x)\ge k$$ for each vertex...

  • On Minimally Highly Vertex-Redundantly Rigid Graphs. Kaszanitzky, Viktória; Király, Csaba // Graphs & Combinatorics;Jan2016, Vol. 32 Issue 1, p225 

    A graph $$G=(V,E)$$ is called $$k$$ -rigid in $$\mathbb {R}^{d}$$ if $$|V|\ge k+1$$ and after deleting any set of at most $$k-1$$ vertices the resulting graph is rigid in $$\mathbb {R}^{d}$$ . A $$k$$ -rigid graph $$G$$ is called minimally $$k$$ -rigid if the omission of an arbitrary edge...

  • The Relaxed Game Chromatic Number of Graphs with Cut-Vertices. Sidorowicz, Elżbieta // Graphs & Combinatorics;Nov2015, Vol. 31 Issue 6, p2381 

    In the $$(r,d)$$ -relaxed colouring game, two players, Alice and Bob alternately colour the vertices of $$G$$ , using colours from a set $$\mathcal{C}$$ , with $$|\mathcal{C}|=r$$ . A vertex $$v$$ can be coloured with $$c,c\in \mathcal{C}$$ if after colouring $$v$$ , the subgraph induced by all...

  • Network Bargaining: Using Approximate Blocking Sets to Stabilize Unstable Instances. Könemann, Jochen; Larson, Kate; Steiner, David // Theory of Computing Systems;Oct2015, Vol. 57 Issue 3, p655 

    We study a network extension to the Nash bargaining game, as introduced by Kleinberg and Tardos [], where the set of players corresponds to vertices in a graph G=( V, E) and each edge i j∈ E represents a possible deal between players i and j. We reformulate the problem as a cooperative game...

  • Successive convex approximations to cardinality-constrained convex programs: a piecewise-linear DC approach. Zheng, Xiaojin; Sun, Xiaoling; Li, Duan; Sun, Jie // Computational Optimization & Applications;Oct2014, Vol. 59 Issue 1/2, p379 

    In this paper we consider cardinality-constrained convex programs that minimize a convex function subject to a cardinality constraint and other linear constraints. This class of problems has found many applications, including portfolio selection, subset selection and compressed sensing. We...

  • Approximating the crowd. Ertekin, Şeyda; Rudin, Cynthia; Hirsh, Haym // Data Mining & Knowledge Discovery;Sep2014, Vol. 28 Issue 5/6, p1189 

    The problem of 'approximating the crowd' is that of estimating the crowd's majority opinion by querying only a subset of it. Algorithms that approximate the crowd can intelligently stretch a limited budget for a crowdsourcing task. We present an algorithm, 'CrowdSense,' that works in an online...

  • A STUDY OF UNIQUELY REMOTAL SETS. Khalil, R.; Sababheh, M. // Journal of Computational Analysis & Applications;Nov2011, Vol. 13 Issue 7, p1233 

    A well known open problem in approximation theory is whether a uniquely remotal set in a normed space is necessarily a singleton. In this article, we introduce the concept of isolated remotal points, and prove that a non singleton closed bounded set with an isolated remotal point, in any normed...

  • Approximations and locally free modules. Slávik, Alexander; Trlifaj, Jan // Bulletin of the London Mathematical Society;Feb2014, Vol. 46 Issue 1, p76 

    For any set of modules , we prove the existence of precovers (right approximations) for all classes of modules of bounded -resolution dimension, where  is the class of all -filtered modules. In contrast, we use infinite-dimensional tilting theory to show that the...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics