論文の概要: Improved Bandits in Many-to-one Matching Markets with Incentive Compatibility
- arxiv url: http://arxiv.org/abs/2401.01528v2
- Date: Sun, 2 Jun 2024 03:26:45 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-04 19:42:23.731710
- Title: Improved Bandits in Many-to-one Matching Markets with Incentive Compatibility
- Title（参考訳）: インセンティブ適合性を有する多対一マッチング市場における帯域幅の改善
- Authors: Fang Kong, Shuai Li,
- Abstract要約: 両面のマッチング市場は、そのリッチな応用のために、文献で広く研究されている。
まず,1対1設定のための既存のアルゴリズムをこのより一般的な設定に拡張し,プレイヤー最適後悔に対するほぼ最適境界を実現することを示す。
本稿では,アダプティブ・サーベイ・then-deferred (AETDA) アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 12.05174711411919
- 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. An existing work initiates the study of this problem in a many-to-one setting with responsiveness. However, their results are far from optimal and lack guarantees of incentive compatibility. We first extend an existing algorithm for the one-to-one setting to this more general setting and show it 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 a linear 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 upper bound for player-optimal stable regret while demonstrating its guarantee of incentive compatibility. To the best of our knowledge, it constitutes the first polynomial player-optimal guarantee in matching markets that offers such robust assurances without known $\Delta$, where $\Delta$ is some preference gap among players and arms. We also consider broader 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 upper bound for the player-pessimal stable regret for this setting.
- Abstract（参考訳）: 両面のマッチング市場は、そのリッチな応用のために、文献で広く研究されている。
参加者は通常、好みについて不確実であるため、最近は反復的な相互作用を通じて学習するためにオンラインアルゴリズムが採用されている。
既存の研究は、応答性のある多対一の設定でこの問題の研究を開始する。
しかし、彼らの結果は最適ではなく、インセンティブの互換性の保証が欠如している。
まず,1対1設定のための既存のアルゴリズムをこのより一般的な設定に拡張し,プレイヤー最適後悔に対するほぼ最適境界を実現することを示す。
それでも、コラボレーションのかなりの要件のため、シングルプレーヤーの偏差は、自身の累積報酬の大幅な増加と、他のプレイヤーに対する線形後悔につながる可能性がある。
本稿では,インセンティブの整合性を確保しつつ,多国間市場における後悔感を高めることを目的とする。
まず,適応探索型遅延受容アルゴリズム(AETDA)を提案する。
私たちの知る限りでは、$\Delta$を知らないような堅牢な保証を提供する市場において、プレイヤーとアームの間では、$\Delta$がある種の選好ギャップであるような、最初の多項式プレイヤー-最適保証を構成する。
また、安定なマッチングとカバー応答性の存在を保証するために、より広範な置換可能な嗜好についても検討する。
我々は,オンラインDA(ODA)アルゴリズムを考案し,この設定に対するプレイヤー・ペシシカル・ストリープの上限を確立する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。