Instability of matchings in decentralized markets with various preference structures

DOI10.1007/S00182-007-0081-6MaRDI QIDQ2482671zbMATH OpenOpenAlexFDO

Authors Kimmo Eriksson, Olle Häggström

Publication date 23 April 2008

Published in International Journal of Game Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00182-007-0081-6

zbMATH Keywords

Blocking pairDecentralized marketInstabilityMaximin matchingPreference structureStable matching

Mathematics Subject Classification ID

Matching models (91B68)

Review text

In this paper, the authors argue that, in a two-sided matching market, the proportion of blocking pairs among all possible pairs is usually the best measure of instability. The exception is when one wants to be able to compare instability of matchings across different preference structures, in which case the paper shows that the blocking pairs measure is biased. A way of eliminating the bias and a discussion on expected instability complete the paper.

Recommendations

• Measuring the instability in two-sided matching procedures
• Preferences and the price of stability in matching markets
• Instability in stable marriage problem: matching unequally numbered men and women
• Random Paths to Stability in Two-Sided Matching
• Jealousy graphs: structure and complexity of decentralized stable matching

Cites work

• Approximation and Online Algorithms
• College Admissions and the Stability of Marriage
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• On the survival of some unstable two-sided matching mechanisms
• Optimal Expected Rank in a Two-Sided Secretary Problem
• The Average Number of Stable Matchings
• The Dynamics of Reorganization in Matching Markets: A Laboratory Experiment Motivated by A Natural Experiments*

Cited in

(33)

• Measuring the instability in two-sided matching procedures
• Stability of matchings when individuals have preferences over colleagues
• The stochastic stability of decentralized matching on a graph
• Evolution of decisions in population games with sequentially searching individuals
• ``Almost-stable matchings in the hospitals/residents problem with couples
• Paths to stability and uniqueness in two-sided matching markets
• Preferences and the price of stability in matching markets
• Almost stable matchings by truncating the Gale-Shapley algorithm
• Stable secretaries
• Decentralized matching at senior-level: stability and incentives
• A stable marriage requires communication
• Asymmetric equilibria in dynamic two-sided matching markets with independent preferences
• Incentives in decentralized random matching markets
• Multi-agent reinforcement learning for decentralized stable matching
• Jealousy graphs: structure and complexity of decentralized stable matching
• Local matching dynamics in social networks
• Random Paths to Stability in Two-Sided Matching
• Size Versus Stability in the Marriage Problem
• Stable marriages and search frictions
• ``Almost stable matchings in the roommates problem with bounded preference lists
• How hard is it to satisfy (almost) all roommates?
• Decentralized matching markets of various sizes: similarly stable solutions with high proportions of equal splits
• scientific article; zbMATH DE number 7626775 (Why is no real title available?)
• Stable matching under forward‐induction reasoning
• Computing relaxations for the three-dimensional stable matching problem with cyclic preferences
• Distance on matchings: An axiomatic approach
• Bayesian stable states
• A characterization of absorbing sets in coalition formation games
• Max-utility matchings with popularity via critical vertices
• Minimizing blocking agents for stable matching with partial approval information
• When do reforms meet fairness concerns in school admissions?
• Size versus stability in the marriage problem
• An improved approximation lower bound for finding almost stable maximum matchings

This page was built for publication: Instability of matchings in decentralized markets with various preference structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2482671)