Stabilizing network bargaining games by blocking players

Sara Ahmadian, Hamideh Hosseinzadeh, Laura Sanità

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)

Abstract

Cooperative matching games (Shapley and Shubik) and Network bargaining games (Kleinberg and Tardos) are games described by an undirected graph, where the vertices represent players. An important role in such games is played by stable graphs, that are graphs whose set of inessential vertices (those that are exposed by at least one maximum matching) are pairwise non adjacent. In fact, stable graphs characterize instances of such games that admit the existence of stable outcomes. In this paper, we focus on stabilizing instances of the above games by blocking as few players as possible. Formally, given a graph G we want to find a minimum cardinality set of vertices such that its removal from G yields a stable graph. We give a combinatorial polynomial-time algorithm for this problem, and develop approximation algorithms for some NP-hard weighted variants, where each vertex has an associated non-negative weight. Our approximation algorithms are LP-based, and we show that our analysis are almost tight by giving suitable lower bounds on the integrality gap of the used LP relaxations.

Original languageEnglish
Pages (from-to)249-275
Number of pages27
JournalMathematical Programming
Volume172
Issue number1-2
DOIs
Publication statusPublished - 1 Nov 2018
Externally publishedYes

Fingerprint Dive into the research topics of 'Stabilizing network bargaining games by blocking players'. Together they form a unique fingerprint.

Cite this