論文の概要: Improved Bandits in Many-to-one Matching Markets with Incentive
Compatibility
- arxiv url: http://arxiv.org/abs/2401.01528v1
- Date: Wed, 3 Jan 2024 03:45:35 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-04 15:24:45.895889
- Title: Improved Bandits in Many-to-one Matching Markets with Incentive
Compatibility
- Title（参考訳）: インセンティブ互換性のある多対一マッチング市場におけるバンディットの改善
- Authors: Fang Kong, Shuai Li
- Abstract要約: 両面のマッチング市場は、そのリッチな応用のために、文献で広く研究されている。
本稿では,インセンティブの整合性を確保しつつ,多国間市場における後悔感を高めることを目的とする。
我々は、オンラインDA(ODA)アルゴリズムを考案し、この設定に対して$O(NKlog T/Delta2)$ player-pessimal stable regret boundを定めている。
- 参考スコア（独自算出の注目度）: 14.237542701166037
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Two-sided matching markets have been widely studied in the literature due to
their rich applications. Since participants are usually uncertain about their
preferences, online algorithms have recently been adopted to learn them through
iterative interactions. \citet{wang2022bandit} initiate the study of this
problem in a many-to-one setting with \textit{responsiveness}. However, their
results are far from optimal and lack guarantees of incentive compatibility. An
extension of \citet{kong2023player} to this more general setting achieves a
near-optimal bound for player-optimal regret. Nevertheless, due to the
substantial requirement for collaboration, a single player's deviation could
lead to a huge increase in its own cumulative rewards and an $O(T)$ regret for
others. In this paper, we aim to enhance the regret bound in many-to-one
markets while ensuring incentive compatibility. We first propose the adaptively
explore-then-deferred-acceptance (AETDA) algorithm for responsiveness setting
and derive an $O(N\min\left\{N,K\right\}C\log T/\Delta^2)$ upper bound for
player-optimal stable regret while demonstrating its guarantee of incentive
compatibility, where $N$ represents the number of players, $K$ is the number of
arms, $T$ denotes the time horizon, $C$ is arms' total capacities and $\Delta$
signifies the minimum preference gap among players. This result is a
significant improvement over \citet{wang2022bandit}. And to the best of our
knowledge, it constitutes the first player-optimal guarantee in matching
markets that offers such robust assurances. We also consider broader
\textit{substitutable} preferences, one of the most general conditions to
ensure the existence of a stable matching and cover responsiveness. We devise
an online DA (ODA) algorithm and establish an $O(NK\log T/\Delta^2)$
player-pessimal stable regret bound for this setting.
- Abstract（参考訳）: 両面のマッチング市場は、リッチな応用のために文献で広く研究されている。
参加者は通常、好みについて不確実であるため、最近は反復的な相互作用を通じて学習するためにオンラインアルゴリズムが採用されている。
\citet{wang2022bandit} は \textit{responsiveness} を持つ多対一の設定でこの問題の研究を開始する。
しかし、彼らの結果は最適ではなく、インセンティブの互換性の保証がない。
より一般的な設定への \citet{kong2023player} の拡張は、プレイヤー-最適後悔に対するほぼ最適境界を達成する。
それでも、コラボレーションのかなりの要件のため、シングルプレーヤーの偏差は、自身の累積報酬の大幅な増加と、他者への後悔の意を表す$O(T)$である。
本稿では,インセンティブ互換性を確保しつつ,多対一市場における後悔感を高めることを目的とする。
最初に、応答性設定のための適応的に探索する-then-deferred-acceptance (aetda) アルゴリズムを提案し、プレイヤー-オプティカルな後悔の上限として$o(n\min\left\{n,k\right\}c\log t/\delta^2)$を導出し、インセンティブ互換性の保証を示す一方で、$n$はプレイヤーの数を表し、$k$はアームの数、$t$は時刻の地平線を表し、$c$はアームの総容量、$\delta$はプレイヤー間の最小の好みギャップを示す。
この結果は \citet{wang2022bandit} を大幅に改善した。
そして、私たちの知る限りでは、このような堅牢な保証を提供するマッチングマーケットにおける、最初のプレイヤー最適保証を構成する。
また、より広範な \textit{substitutable} の選好についても検討し、安定なマッチングとカバー応答性を保証するための最も一般的な条件の1つである。
オンラインDA(ODA)アルゴリズムを考案し,$O(NK\log T/\Delta^2)$ player-pessimal stable regret bound for this set。
関連論文リスト
- Competing Bandits in Decentralized Large Contextual Matching Markets [13.313881962771777]
我々は、需要側(プレイヤーまたはエージェント)が大きな供給側(腕)と競合する二面的マッチング市場における分散学習を研究する。
提案アルゴリズムは,腕の数によらず,インスタンス依存の対数的後悔を実現する。
論文 参考訳（メタデータ） (2024-11-18T18:08:05Z) - Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning [14.448192914855674]
両面のマッチング市場は、市場の片側からの参加者が好みに応じて反対側からの参加者と一致しなければならない、一連の問題を記述している。
我々は安定解の構造を利用して、安定解を見つける可能性を改善するアルゴリズムを考案する。
論文 参考訳（メタデータ） (2024-10-06T06:47:53Z) - Player-optimal Stable Regret for Bandit Learning in Matching Markets [12.54215178882448]
ここでは、各プレイヤーの最適な安定な後悔は、$O(Klog T/Delta2)$、$K$は腕の数、$T$は地平線、$Delta$は、最初の$N+1$の腕の中でプレイヤーの最小の好みの差であることを示す。
我々の研究は、プレイヤー・ペシミカルの安定したマッチング目標がより弱かったり、特別な仮定を持った市場のみに適用されたりした以前の作品を大幅に改善する。
論文 参考訳（メタデータ） (2023-07-20T14:10:33Z) - Two-sided Competing Matching Recommendation Markets With Quota and Complementary Preferences Constraints [13.069703665055084]
本稿では,両面のオンラインマッチング市場において,補完的な嗜好とクォータ制約を伴う問題に対処する新しい推奨アルゴリズムを提案する。
混合クォータと相補的な選好制約の存在は、マッチングプロセスの不安定性を引き起こす。
バンドレート学習の枠組みとしてこの問題を定式化し,マルチエージェント多型トンプソンサンプリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-24T18:54:29Z) - Incentive-Aware Recommender Systems in Two-Sided Markets [49.692453629365204]
最適性能を達成しつつエージェントのインセンティブと整合する新しいレコメンデータシステムを提案する。
我々のフレームワークは、このインセンティブを意識したシステムを、両側市場におけるマルチエージェントバンディット問題としてモデル化する。
どちらのアルゴリズムも、エージェントが過剰な露出から保護する、ポストフェアネス基準を満たす。
論文 参考訳（メタデータ） (2022-11-23T22:20:12Z) - Provably Efficient Fictitious Play Policy Optimization for Zero-Sum
Markov Games with Structured Transitions [145.54544979467872]
本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。
我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。
提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
論文 参考訳（メタデータ） (2022-07-25T18:29:16Z) - Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
不確実性の下で安定した市場成果を学習するためのフレームワークとアルゴリズムを開発する。
私たちの研究は、大規模なデータ駆動の市場において、いつ、どのように安定したマッチングが生じるかを明らかにするための第一歩を踏み出します。
論文 参考訳（メタデータ） (2021-08-19T17:59:28Z) - Regret, stability, and fairness in matching markets with bandit learners [22.76773950247833]
我々は,バンディット学習者との対面マッチング市場を考える。
インセンティブ互換性,すなわち安定性,低い後悔,すなわち,$o(log(t))$ 最適後悔,(3) エージェント間の後悔の分配の公平性,(4) 高社会福祉の4つのデシデラタを同時に保証できることを示す。
論文 参考訳（メタデータ） (2021-02-11T20:18:12Z) - Bandit Learning in Decentralized Matching Markets [82.39061186055775]
私たちは、一方の市場(プレーヤー)が他方の側(腕)の好みについて事前知識を持っていない両面マッチング市場を研究し、経験からその好みを学ぶ必要があります。
このモデルは、標準のマルチアームバンディットフレームワークを競合する分散型マルチプレイヤー設定に拡張します。
アームの選好が共有されるたびにアルゴリズムがインセンティブ互換であることが示されるが、選好が完全に一般的である場合には必ずしもそうではない。
論文 参考訳（メタデータ） (2020-12-14T08:58:07Z) - Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。
アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。
我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文 参考訳（メタデータ） (2020-08-10T08:30:52Z) - SetRank: A Setwise Bayesian Approach for Collaborative Ranking from
Implicit Feedback [50.13745601531148]
提案手法は,提案システムにおける暗黙的フィードバックの特性に対応するために,協調的ランキング(SeetRank)のためのセッティングワイドベイズ的手法を提案する。
具体的には、SetRankは、新しい設定された選好比較の後方確率を最大化することを目的としている。
また、SetRankの理論解析により、余剰リスクの境界が$sqrtM/N$に比例できることを示す。
論文 参考訳（メタデータ） (2020-02-23T06:40:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。