論文の概要: Necessarily Optimal One-Sided Matchings
- arxiv url: http://arxiv.org/abs/2007.09079v3
- Date: Tue, 13 Apr 2021 21:45:37 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-09 14:42:18.590440
- Title: Necessarily Optimal One-Sided Matchings
- Title（参考訳）: 必要な一方向マッチング
- Authors: Hadi Hosseini, Vijay Menon, Nisarg Shah, Sujoy Sikdar
- Abstract要約: 我々は、$n$エージェントと$n$オブジェクトとをマッチングする古典的な問題について研究する。
エージェントに完全な選好を報告させる代わりに、私たちのゴールは部分的な選好から望ましいマッチングを学ぶことです。
我々は,与えられたマッチングが NPO か NRM かを確認し,そのようなマッチングが与えられたトップ$k$ の部分的選好が存在するかどうかを確認するために,効率的なアルゴリズムを設計する。
- 参考スコア（独自算出の注目度）: 49.0517583218216
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the classical problem of matching $n$ agents to $n$ objects, where
the agents have ranked preferences over the objects. We focus on two popular
desiderata from the matching literature: Pareto optimality and rank-maximality.
Instead of asking the agents to report their complete preferences, our goal is
to learn a desirable matching from partial preferences, specifically a matching
that is necessarily Pareto optimal (NPO) or necessarily rank-maximal (NRM)
under any completion of the partial preferences. We focus on the top-$k$ model
in which agents reveal a prefix of their preference rankings. We design
efficient algorithms to check if a given matching is NPO or NRM, and to check
whether such a matching exists given top-$k$ partial preferences. We also study
online algorithms for eliciting partial preferences adaptively, and prove
bounds on their competitive ratio.
- Abstract（参考訳）: 我々は,$n$ エージェントを $n$ オブジェクトにマッチングする古典的な問題を研究し,エージェントがオブジェクトに対する好みをランク付けする。
我々はパレート最適性とランク最大性という2つの文学からの人気デシデラタに注目した。
エージェントに完全な選好を報告させる代わりに、我々のゴールは部分選好、特に、部分選好の完了時に必ずしもパレート最適(NPO)または必然的にランク最大(NRM)であるマッチングから望ましいマッチングを学ぶことである。
我々は、エージェントが優先ランクのプレフィックスを明らかにする、上位$kのモデルに焦点を当てる。
我々は,与えられたマッチングが NPO か NRM かを確認し,そのようなマッチングが与えられたトップ$k$ の部分的選好が存在するかどうかを確認するために,効率的なアルゴリズムを設計する。
また,部分的選好を適応的に排除するためのオンラインアルゴリズムも検討し,その競合比の限界を証明した。
関連論文リスト
- Calibrated Multi-Preference Optimization for Aligning Diffusion Models [92.90660301195396]
Calibrated Preference Optimization (CaPO) は、テキスト・ツー・イメージ(T2I)拡散モデルを調整する新しい手法である。
CaPOは、人間の注釈のない複数の報酬モデルからの一般的な好みを取り入れている。
実験結果から, CaPOは従来法よりも常に優れていたことが示唆された。
論文 参考訳（メタデータ） (2025-02-04T18:59:23Z) - A Best-of-Both Approach to Improve Match Predictions and Reciprocal Recommendations for Job Search [15.585641615174623]
本稿では、擬似マッチスコアを利用して、生産における相互推薦を改善するための、新規で実用的なソリューションを紹介し、実証する。
具体的には、実際のマッチングラベルと比較的不正確だが密なマッチング予測を組み合わせることで、より密で直接的な擬似マッチスコアを生成する。
我々の手法は、直接マッチング予測と2つの異なるモデルアプローチの両方の高レベルなアイデアを組み合わせることで、ベスト・オブ・ボス(BoB)アプローチと見なすことができる。
論文 参考訳（メタデータ） (2024-09-17T08:51:02Z) - Comparing Bad Apples to Good Oranges: Aligning Large Language Models via Joint Preference Optimization [105.3612692153615]
命令応答対に対して協調的に好みを抽出する新しい軸を提案する。
命令と応答ペアを併用することで、大きな言語モデルのアライメントを大幅に向上させることができる。
論文 参考訳（メタデータ） (2024-03-31T02:05:40Z) - Deep Probabilistic Graph Matching [72.6690550634166]
本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。
提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
論文 参考訳（メタデータ） (2022-01-05T13:37:27Z) - Improving Welfare in One-sided Matching using Simple Threshold Queries [9.270928705464193]
我々は、$n$エージェントが$m$オブジェクトよりも好みを持つ一方的なマッチング問題を研究する。
簡単なしきい値クエリを使って、彼らの基準的嗜好についてもっと学ぶことに集中する。
論文 参考訳（メタデータ） (2020-11-27T20:02:57Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z) - SetRank: A Setwise Bayesian Approach for Collaborative Ranking from
Implicit Feedback [50.13745601531148]
提案手法は,提案システムにおける暗黙的フィードバックの特性に対応するために,協調的ランキング(SeetRank)のためのセッティングワイドベイズ的手法を提案する。
具体的には、SetRankは、新しい設定された選好比較の後方確率を最大化することを目的としている。
また、SetRankの理論解析により、余剰リスクの境界が$sqrtM/N$に比例できることを示す。
論文 参考訳（メタデータ） (2020-02-23T06:40:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。