論文の概要: 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$ の部分的選好が存在するかどうかを確認するために,効率的なアルゴリズムを設計する。
また,部分的選好を適応的に排除するためのオンラインアルゴリズムも検討し,その競合比の限界を証明した。
関連論文リスト
- Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳(メタデータ) (2023-12-13T11:08:25Z) - Human-in-the-loop: Provably Efficient Preference-based Reinforcement
Learning with General Function Approximation [107.54516740713969]
本研究は,RL(Human-in-the-loop reinforcement learning)を軌道的嗜好で検討する。
各ステップで数値的な報酬を受ける代わりに、エージェントは人間の監督者から軌道上のペアよりも優先される。
一般関数近似を用いたPbRLの楽観的モデルベースアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-05-23T09:03:24Z) - Deep Probabilistic Graph Matching [72.6690550634166]
本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。
提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
論文 参考訳(メタデータ) (2022-01-05T13:37:27Z) - Dynamic-K Recommendation with Personalized Decision Boundary [41.70842736417849]
ランキングと分類の目的を併せ持つ共同学習問題として動的k推薦タスクを開発した。
我々は、BPRMFとHRMの2つの最先端ランキングベースのレコメンデーション手法を対応する動的Kバージョンに拡張する。
2つのデータセットに対する実験結果から,動的Kモデルの方が従来の固定N推奨手法よりも有効であることが示された。
論文 参考訳(メタデータ) (2020-12-25T13:02:57Z) - Trustworthy Preference Completion in Social Choice [36.91054060923998]
すべての選択肢に対して線形順序を与えるようにエージェントに頼むのは非現実的であり、これらの部分的なランク付けは選好完了を行う必要がある。
信頼ベースのアンカー-kNNアルゴリズムは、信頼指向のケンダル-トー距離を持つエージェントの最も信頼できる隣人を見つけるために提案される。
最初の$k$信頼に値する隣接エージェントに対する特定の共通投票ルールは、確実性と紛争に基づいて、信頼に値する選好完了を行うために適用することができる。
論文 参考訳(メタデータ) (2020-12-14T03:03:13Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。