Back to search

University of Waterloo

Vertex Stabilizers for Network Bargaining Games

Abstract

dc:description.abstract

Network bargaining games form a prominent class of examples of game theory problems defined on graphs, where vertices represent players, and edges represent their possible interactions. An instance of a \emph{network bargaining game} is given by a graph $G = (V, E)$ with edge weights w \in \mathbb{R}E+ and vertex capacities c \in \mathbb{Z}V+. A \emph{solution} to an instance $(G, w, c)$ of a network bargaining game is data $(M, z)$, where $M \subset E$ is a $c$-matching, and z \in \mathbb{R}2E\geq 0 is a vector which assigns each edge $uv \in E$ a pair of values zuv and zvu, such that zuv + zvu = wuv if $uv \in M$, and zuv = zvu = 0 otherwise. An instance $(G, w, c)$ is said to be \emph{stable} if it admits a so-called `stable' solution, which represents a solution where a player has no incentive to deviate. Not all instances of a network bargaining game have a stable solution, and this naturally motivates the problem of how to modify the underlying graph such that the instance becomes stable. In recent years, researchers have investigated various modifications, typically by adding or removing edges or vertices. The natural algorithmic question which stems from this is whether these modifications can be performed efficiently. The answer varies, depending on the modification in question, and on whether the edges/vertices have been restricted to be unit weight/capacity. In this work, we consider the vertex-removal setting for a general instance $(G, w, c)$ of a network bargaining game. A set of vertices whose deletion from $G$ results in a stable instance of the induced network bargaining game is called a \emph{vertex stabilizer}. We demonstrate in this work that the algorithmic problem of finding a minimum cardinality vertex stabilizer is $NP$-complete, and give an efficient $2$-approximation algorithm. Further, we show that no efficient (2 - ε)-approximation for this problem exists for any ε > 0, assuming the Unique Games Conjecture holds. These results hold even in the case when all edges are of unit-weight. In contrast, if we are given an instance $(G, w, c)$ together with a maximum weight $c$-matching $M$, we show that the problem of finding a minimum cardinality vertex stabilizer that avoids $M$ can be solved efficiently. We provide a polynomial time algorithm for solving this problem.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gerstbrein, Matthew
Advisors dc:contributor.advisor
  • Sanità, Laura
  • Koenemann, Jochen

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/18093

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Gerstbrein, Matthew. Vertex Stabilizers for Network Bargaining Games. University of Waterloo, 2022. http://hdl.handle.net/10012/18093