論文の概要: Stable Matching with Ties: Approximation Ratios and Learning
- arxiv url: http://arxiv.org/abs/2411.03270v1
- Date: Tue, 05 Nov 2024 17:14:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-06 14:58:24.687830
- Title: Stable Matching with Ties: Approximation Ratios and Learning
- Title（参考訳）: 友人との安定したマッチング:近似比と学習
- Authors: Shiyun Lin, Simon Mauras, Nadav Merlis, Vianney Perchet,
- Abstract要約: 我々は、市場の一方が他方の会員に対して厳格な嗜好を必ずしも持たないような、市場と結びつきのある市場との整合性の問題について検討する。
我々は,各作業員が最良で安定したマッチングにおいて,ユーティリティから最大のシェアを確保できるようにすることを目標としている。
- 参考スコア（独自算出の注目度）: 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).
- Abstract（参考訳）: 我々は、市場の一方が他方の会員に対して厳格な嗜好を必ずしも持たないような、市場と結びつきのある市場との整合性の問題について検討する。
例えば、労働者は必ずしも仕事よりも厳格な好みを持っているわけではない。
特に、労働者の嗜好がそれぞれの仕事と一致しないことによって決定され、関係が認められる可能性があると仮定する。
特に、厳格な選好を持つ古典的な二面市場とは対照的に、すべての労働者の効用を同時に最大化する単一の安定なマッチングはもはや存在しない。
我々は,各作業員が最良で安定したマッチングにおいて,ユーティリティから最大のシェアを確保できるようにすることを目標としている。
私たちは、ワーカーの最も可能な安定したユーティリティと割り当てられたユーティリティの比率を、 \emph{Optimal Stable Share} (OSS)-ratioと呼びます。
まず、安定なマッチング上の分布が、ワーカ数のサブリニアであるOSS比を保証できないことを証明する。
代わりに、非安定なマッチングに対してランダム化を行い、厳密な対数的OSS比を達成する方法を示す。
そして,実効性が必ずしも分かっておらず,近似しかできない場合を分析する。
特に、最も優れたユーティリティと比較して、ユーティリティの類似部分を保証するアルゴリズムを提供する。
最後に、バンディット設定に移行し、各ラウンドでマッチングを選択し、実行するマッチのユーティリティのみを観察します。
本研究は, 関係性のない問題と統計的関係(最小限の最適性ギャップ)の問題を適切に補間するために, 近似ユーティリティに我々の結果を活用する方法を示す。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。