Stable Matching with Ties: Approximation Ratios and Learning

• URL: http://arxiv.org/abs/2411.03270v1
• Date: Tue, 05 Nov 2024 17:14:46 GMT
• Title: Stable Matching with Ties: Approximation Ratios and Learning
• Authors: Shiyun Lin, Simon Mauras, Nadav Merlis, Vianney Perchet,
• Abstract summary: We study the problem of matching markets with ties, where one side of the market does not necessarily have strict preferences over members at its other side. We aim to guarantee each worker the largest possible share from the utility in her best possible stable matching.
• Score: 20.84610303094647
• License:
• Abstract: We study the problem of matching markets with ties, where one side of the market does not necessarily have strict preferences over members at its other side. For example, workers do not always have strict preferences over jobs, students can give the same ranking for different schools and more. In particular, assume w.l.o.g. that workers' preferences are determined by their utility from being matched to each job, which might admit ties. Notably, in contrast to classical two-sided markets with strict preferences, there is no longer a single stable matching that simultaneously maximizes the utility for all workers. We aim to guarantee each worker the largest possible share from the utility in her best possible stable matching. We call the ratio between the worker's best possible stable utility and its assigned utility the \emph{Optimal Stable Share} (OSS)-ratio. We first prove that distributions over stable matchings cannot guarantee an OSS-ratio that is sublinear in the number of workers. Instead, randomizing over possibly non-stable matchings, we show how to achieve a tight logarithmic OSS-ratio. Then, we analyze the case where the real utility is not necessarily known and can only be approximated. In particular, we provide an algorithm that guarantees a similar fraction of the utility compared to the best possible utility. Finally, we move to a bandit setting, where we select a matching at each round and only observe the utilities for matches we perform. We show how to utilize our results for approximate utilities to gracefully interpolate between problems without ties and problems with statistical ties (small suboptimality gaps).

Related papers

• Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning [14.448192914855674]
  Two-sided matching markets describe a class of problems wherein participants from one side of the market must be matched to those from the other side according to their preferences. We exploit the structure of stable solutions to devise algorithms that improve the likelihood of finding stable solutions.
  arXiv  Detail & Related papers  (2024-10-06T06:47:53Z)
• A Best-of-Both Approach to Improve Match Predictions and Reciprocal Recommendations for Job Search [15.585641615174623]
  This paper introduces and demonstrates a novel and practical solution to improve reciprocal recommendations in production by leveraging pseudo-match scores. Specifically, our approach generates dense and more directly relevant pseudo-match scores by combining the true match labels with relatively inaccurate but dense match predictions. Our method can be seen as a best-of-both (BoB) approach, as it combines the high-level ideas of both direct match prediction and the two separate models approach.
  arXiv  Detail & Related papers  (2024-09-17T08:51:02Z)
• Show Your Work with Confidence: Confidence Bands for Tuning Curves [51.12106543561089]
  tuning curves plot validation performance as a function of tuning effort. We present the first method to construct valid confidence bands for tuning curves. We validate our design with ablations, analyze the effect of sample size, and provide guidance on comparing models with our method.
  arXiv  Detail & Related papers  (2023-11-16T00:50:37Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  We propose a deep learning-based graph matching framework that works for the original QAP without compromising on the matching constraints. The proposed method is evaluated on three popularly tested benchmarks (Pascal VOC, Willow Object and SPair-71k) and it outperforms all previous state-of-the-arts on all benchmarks.
  arXiv  Detail & Related papers  (2022-01-05T13:37:27Z)
• Decentralized optimization with non-identical sampling in presence of stragglers [3.04585143845864]
  We consider decentralized consensus optimization when sample data from non-identical and perform variable amounts of work due to slow nodes known as stragglers. While we conclude that the two convex methods are optimal, we also show that an optimal method does not exist.
  arXiv  Detail & Related papers  (2021-08-25T06:33:38Z)
• Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
  We develop a framework and algorithms for learning stable market outcomes under uncertainty. Our work takes a first step toward elucidating when and how stable matchings arise in large, data-driven marketplaces.
  arXiv  Detail & Related papers  (2021-08-19T17:59:28Z)
• Optimality and Stability in Federated Learning: A Game-theoretic Approach [0.0]
  We motivate and define a notion of optimality given by the average error rates among federating agents (players) First, we show that for some regions of parameter space, all stable arrangements are optimal (Price of Anarchy equal to 1). However, we show this is not true for all settings: there exist examples of stable arrangements with higher cost than optimal (Price of Anarchy greater than 1).
  arXiv  Detail & Related papers  (2021-06-17T15:03:51Z)
• Scalable Personalised Item Ranking through Parametric Density Estimation [53.44830012414444]
  Learning from implicit feedback is challenging because of the difficult nature of the one-class problem. Most conventional methods use a pairwise ranking approach and negative samplers to cope with the one-class problem. We propose a learning-to-rank approach, which achieves convergence speed comparable to the pointwise counterpart.
  arXiv  Detail & Related papers  (2021-05-11T03:38:16Z)
• Consensus-Guided Correspondence Denoising [67.35345850146393]
  We propose to denoise correspondences with a local-to-global consensus learning framework to robustly identify correspondence. A novel "pruning" block is introduced to distill reliable candidates from initial matches according to their consensus scores estimated by dynamic graphs from local to global regions. Our method outperforms state-of-the-arts on robust line fitting, wide-baseline image matching and image localization benchmarks by noticeable margins.
  arXiv  Detail & Related papers  (2021-01-03T09:10:00Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers. We propose a class of non-adaptive ranking algorithms that rely on a least-squares intrinsic optimization criterion for the estimation of qualities.
  arXiv  Detail & Related papers  (2020-02-26T16:19:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.