The general graph matching game: approximate core
From MaRDI portal
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 6472650 (Why is no real title available?)
- An algorithm for finding the nucleolus of assignment 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
- Computing solutions for matching games
- Game theoretic analysis of a bankruptcy problem from the Talmud
- Geometric Properties of the Kernel, Nucleolus, and Related Solution Concepts
- Geometric algorithms and combinatorial optimization
- Integer Programming: Methods, Uses, Computations
- Matching Games: The Least Core and the Nucleolus
- Matching theory
- Stable outcomes of the roommate game with transferable utility
- Strongly essential coalitions and the nucleolus of peer group games
- The Nucleolus of a Characteristic Function Game
- The assignment game. I: The core
- The nucleon of cooperative games and an algorithm for matching games
- Vertex packings: Structural properties and algorithms
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
- Computing solutions for matching games
- Approximate core allocations for edge cover 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)
