論文の概要: Stable Matching with Ties: Approximation Ratios and Learning
- arxiv url: http://arxiv.org/abs/2411.03270v2
- Date: Wed, 22 Oct 2025 08:45:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-25 03:08:02.7325
- Title: Stable Matching with Ties: Approximation Ratios and Learning
- Title（参考訳）: 友人との安定したマッチング:近似比と学習
- Authors: Shiyun Lin, Simon Mauras, Nadav Merlis, Vianney Perchet,
- Abstract要約: 我々は、市場の片側で働く労働者が、彼らのマッチングユーティリティーによって決定された、仕事よりも好みに結びついている可能性がある、マッチング市場と結びつきについて研究する。
厳格な嗜好を持つ古典的な二面市場とは異なり、すべての労働者に対して実用性を最大化する単一の安定なマッチングは存在しない。
- 参考スコア（独自算出の注目度）: 34.58046942241621
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study matching markets with ties, where workers on one side of the market may have tied preferences over jobs, determined by their matching utilities. Unlike classical two-sided markets with strict preferences, no single stable matching exists that is utility-maximizing for all workers. To address this challenge, we introduce the \emph{Optimal Stable Share} (OSS)-ratio, which measures the ratio of a worker's maximum achievable utility in any stable matching to their utility in a given matching. We prove that distributions over only stable matchings can incur linear utility losses, i.e., an $\Omega (N)$ OSS-ratio, where $N$ is the number of workers. To overcome this, we design an algorithm that efficiently computes a distribution over (possibly non-stable) matchings, achieving an asymptotically tight $O (\log N)$ OSS-ratio. When exact utilities are unknown, our second algorithm guarantees workers a logarithmic approximation of their optimal utility under bounded instability. Finally, we extend our offline approximation results to a bandit learning setting where utilities are only observed for matched pairs. In this setting, we consider worker-optimal stable regret, design an adaptive algorithm that smoothly interpolates between markets with strict preferences and those with statistical ties, and establish a lower bound revealing the fundamental trade-off between strict and tied preference regimes.
- Abstract（参考訳）: 我々は、市場の片側で働く労働者が、彼らのマッチングユーティリティーによって決定された、仕事よりも好みに結びついている可能性がある、マッチング市場と結びつきについて研究する。
厳格な嗜好を持つ古典的な二面市場とは異なり、すべての労働者に対して実用性を最大化する単一の安定なマッチングは存在しない。
この課題に対処するために、労働者の最大達成可能なユーティリティの比率を、所定のマッチングで彼らのユーティリティと安定したマッチングで測定する \emph{Optimal Stable Share} (OSS)-ratio を導入する。
安定マッチングのみ上の分布は線形効用損失(例えば$\Omega (N)$ OSS-ratio)を生じさせる。
これを解決するために,我々は,確率的に厳密な$O(\log N)=OSS-ratioを達成するアルゴリズムを設計した。
正確なユーティリティが不明な場合、第2のアルゴリズムは、バウンダリ不安定下での最適ユーティリティの対数近似を保証する。
最後に、オフライン近似結果を、一致したペアに対してのみユーティリティが観測される帯域学習環境に拡張する。
この設定では、労働者最適の安定な後悔を考慮し、厳密な嗜好を持つ市場と統計的な結びつきを持つ市場を円滑に補間する適応的アルゴリズムを設計し、厳密な選好と結びついた選好体制の基本的なトレードオフを明らかにするための低い境界を確立する。
関連論文リスト
- Probably Correct Optimal Stable Matching for Two-Sided Markets Under Uncertainty [5.250288418639076]
市場左側の好ましくない条件下での安定婚姻モデルの学習課題について考察する。
我々の目的は、左サイド最適である安定したマッチングを素早く識別することであり、バンドイットフィードバックによる純粋な探索問題である。
論文 参考訳（メタデータ） (2025-01-06T13:59:57Z) - GS-Matching: Reconsidering Feature Matching task in Point Cloud Registration [7.315456136190114]
本稿では,Gale-ShapleyアルゴリズムにインスパイアされたGSマッチング方式を提案する。
提案手法は, 高い重なり合い条件下で効率よく動作し, より非反復的不整合を求めることができる。
論文 参考訳（メタデータ） (2024-12-06T08:47:14Z) - Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning [14.448192914855674]
両面のマッチング市場は、市場の片側からの参加者が好みに応じて反対側からの参加者と一致しなければならない、一連の問題を記述している。
我々は安定解の構造を利用して、安定解を見つける可能性を改善するアルゴリズムを考案する。
論文 参考訳（メタデータ） (2024-10-06T06:47:53Z) - A Best-of-Both Approach to Improve Match Predictions and Reciprocal Recommendations for Job Search [15.585641615174623]
本稿では、擬似マッチスコアを利用して、生産における相互推薦を改善するための、新規で実用的なソリューションを紹介し、実証する。
具体的には、実際のマッチングラベルと比較的不正確だが密なマッチング予測を組み合わせることで、より密で直接的な擬似マッチスコアを生成する。
我々の手法は、直接マッチング予測と2つの異なるモデルアプローチの両方の高レベルなアイデアを組み合わせることで、ベスト・オブ・ボス(BoB)アプローチと見なすことができる。
論文 参考訳（メタデータ） (2024-09-17T08:51:02Z) - Show Your Work with Confidence: Confidence Bands for Tuning Curves [51.12106543561089]
チューニング作業の関数としての曲線プロット検証性能。
そこで我々は,曲線のチューニングに有効な信頼帯域を構築するための最初の方法を提案する。
提案手法と比較し,提案手法の有効性を検証し,サンプルサイズの影響を解析し,モデルの比較に関するガイダンスを提供する。
論文 参考訳（メタデータ） (2023-11-16T00:50:37Z) - Deep Probabilistic Graph Matching [72.6690550634166]
本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。
提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
論文 参考訳（メタデータ） (2022-01-05T13:37:27Z) - Decentralized optimization with non-identical sampling in presence of
stragglers [3.04585143845864]
非同一データからのサンプルデータを分散したコンセンサス最適化を考慮し、トラグラーとして知られる遅いノードによる可変量の作業を行う。
2つの凸法が最適であると結論づける一方で、最適解が存在しないことも示す。
論文 参考訳（メタデータ） (2021-08-25T06:33:38Z) - Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
不確実性の下で安定した市場成果を学習するためのフレームワークとアルゴリズムを開発する。
私たちの研究は、大規模なデータ駆動の市場において、いつ、どのように安定したマッチングが生じるかを明らかにするための第一歩を踏み出します。
論文 参考訳（メタデータ） (2021-08-19T17:59:28Z) - Optimality and Stability in Federated Learning: A Game-theoretic
Approach [0.0]
我々は,フェデレーションエージェント(プレーヤ)の平均誤差率によって与えられる最適性の概念を動機付け,定義する。
まず、パラメータ空間のいくつかの領域に対して、すべての安定な配置が最適である(アナーキーの値が 1 に等しい)ことを示す。
しかし、これはすべての設定に当てはまるものではなく、最適よりも高いコストで安定な配置の例が存在する(AnaarchyのPrice of Anarchy larger than 1)。
論文 参考訳（メタデータ） (2021-06-17T15:03:51Z) - Scalable Personalised Item Ranking through Parametric Density Estimation [53.44830012414444]
暗黙のフィードバックから学ぶことは、一流問題の難しい性質のために困難です。
ほとんどの従来の方法は、一級問題に対処するためにペアワイズランキングアプローチとネガティブサンプラーを使用します。
本論文では,ポイントワイズと同等の収束速度を実現する学習対ランクアプローチを提案する。
論文 参考訳（メタデータ） (2021-05-11T03:38:16Z) - Consensus-Guided Correspondence Denoising [67.35345850146393]
本稿では,地域間コンセンサス学習フレームワークと対応関係を異色化し,対応関係をロバストに識別する。
ローカル地域からグローバル地域への動的グラフから推定されるコンセンサススコアに基づいて,信頼度の高い候補を初期マッチングから蒸留する新しい「プルーニング」ブロックを導入した。
本手法は、堅牢なラインフィッティング、ワイドベースライン画像マッチング、画像ローカリゼーションベンチマークを顕著なマージンで上回る。
論文 参考訳（メタデータ） (2021-01-03T09:10:00Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。