The general graph matching game: approximate core
From MaRDI portal
Publication:2078093
DOI10.1016/J.GEB.2022.01.017zbMATH Open1485.91014arXiv2101.07390OpenAlexW4210297752MaRDI QIDQ2078093FDOQ2078093
Authors: Vijay V. Vazirani 
Publication date: 25 February 2022
Published in: Games and Economic Behavior (Search for Journal in Brave)
Abstract: The classic paper of Shapley and Shubik cite{Shapley1971assignment} characterized the core of the assignment game using ideas from matching theory and LP-duality theory and their highly non-trivial interplay. Whereas the core of this game is always non-empty, that of the general graph matching game can be empty. This paper salvages the situation by giving an imputation in the -approximate core for the latter. This bound is best possible, since it is the integrality gap of the natural underlying LP. Our profit allocation method goes further: the multiplier on the profit of an agent is often better than and lies in the interval , depending on how severely constrained the agent is. Next, we provide new insights showing how discerning core imputations of an assignment games are by studying them via the lens of complementary slackness. We present a relationship between the competitiveness of individuals and teams of agents and the amount of profit they accrue in imputations that lie in the core, where by {em competitiveness} we mean whether an individual or a team is matched in every/some/no maximum matching. This also sheds light on the phenomenon of degeneracy in assignment games, i.e., when the maximum weight matching is not unique. The core is a quintessential solution concept in cooperative game theory. It contains all ways of distributing the total worth of a game among agents in such a way that no sub-coalition has incentive to secede from the grand coalition. Our imputation, in the -approximate core, implies that a sub-coalition will gain at most a factor by seceding, and less in typical cases.
Full work available at URL: https://arxiv.org/abs/2101.07390
Recommendations
coreassignment gameapproximate coreLP-dualitygeneral graph matching gametransferable utility (TU) market
Cites Work
- Game theoretic analysis of a bankruptcy problem from the Talmud
- The Nucleolus of a Characteristic Function Game
- Matching theory
- Geometric algorithms and combinatorial optimization
- An algorithm for finding the nucleolus of assignment games
- The assignment game. I: The core
- Strongly essential coalitions and the nucleolus of peer group games
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- College Admissions and the Stability of Marriage
- Geometric Properties of the Kernel, Nucleolus, and Related Solution Concepts
- Vertex packings: Structural properties and algorithms
- Integer Programming: Methods, Uses, Computations
- Computing solutions for matching games
- Matching Games: The Least Core and the Nucleolus
- The nucleon of cooperative games and an algorithm for matching games
- Stable outcomes of the roommate game with transferable utility
- Title not available (Why is that?)
Cited In (10)
- Computing the least-core and nucleolus for threshold cardinality matching games
- The complexity of matching games: a survey
- Population monotonicity in matching games
- The core of the matching game
- On solution concepts for matching games
- Approximate core allocations for edge cover games
- The price of optimum: complexity and approximation for a matching game
- Approximate core allocations for edge cover games
- Computing solutions for matching games
- On the population monotonicity of independent set games
This page was built for publication: The general graph matching game: approximate core
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2078093)
