論文の概要: Regret, stability, and fairness in matching markets with bandit learners

• arxiv url: http://arxiv.org/abs/2102.06246v1
• Date: Thu, 11 Feb 2021 20:18:12 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-15 21:48:33.445494
• Title: Regret, stability, and fairness in matching markets with bandit learners
• Title（参考訳）: バンディット学習者との市場におけるレグレト、安定性、公正性
• Authors: Sarah H. Cen and Devavrat Shah
• Abstract要約: 我々は,バンディット学習者との対面マッチング市場を考える。 インセンティブ互換性,すなわち安定性,低い後悔,すなわち,$o(log(t))$ 最適後悔,(3) エージェント間の後悔の分配の公平性,(4) 高社会福祉の4つのデシデラタを同時に保証できることを示す。
• 参考スコア（独自算出の注目度）: 22.76773950247833
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the two-sided matching market with bandit learners. In the standard matching problem, users and providers are matched to ensure incentive compatibility via the notion of stability. However, contrary to the core assumption of the matching problem, users and providers do not know their true preferences a priori and must learn them. To address this assumption, recent works propose to blend the matching and multi-armed bandit problems. They establish that it is possible to assign matchings that are stable (i.e., incentive-compatible) at every time step while also allowing agents to learn enough so that the system converges to matchings that are stable under the agents' true preferences. However, while some agents may incur low regret under these matchings, others can incur high regret -- specifically, $\Omega(T)$ optimal regret where $T$ is the time horizon. In this work, we incorporate costs and transfers in the two-sided matching market with bandit learners in order to faithfully model competition between agents. We prove that, under our framework, it is possible to simultaneously guarantee four desiderata: (1) incentive compatibility, i.e., stability, (2) low regret, i.e., $O(\log(T))$ optimal regret, (3) fairness in the distribution of regret among agents, and (4) high social welfare.
• Abstract（参考訳）: 我々は,バンディット学習者との対面マッチング市場を考える。 標準マッチング問題では、ユーザとプロバイダは、安定性の概念を通じてインセンティブ互換性を確保するために一致します。 しかし、マッチング問題の根本的な仮定に反して、ユーザーとプロバイダーは彼らの真の好みを優先順位を知らないし、それらを学ばなければなりません。 この仮定に対処するため、近年の研究では、マッチングとマルチアームバンディットの問題をブレンドすることを提案する。 彼らは、エージェントの真の好みの下で安定しているマッチングにシステムが収束するように、エージェントが十分に学習できるように、各時間ステップで安定したマッチング(インセンティブ互換)を割り当てることができることを確立している。 しかし、これらのマッチングの下では低い後悔を被るエージェントもあるが、特に$T$が時空である場合、$\Omega(T)$最適な後悔を被るエージェントもいる。 本研究では,エージェント間の競争を忠実にモデル化するために,両面のマッチング市場におけるコストと移動を帯域学習者と組み合わせた。 我々は,(1)インセンティブ相反性,すなわち安定性,(2)低い後悔,すなわち$o(\log(t))$の最適後悔,(3)エージェント間の後悔の分配の公平性,(4)高い社会福祉の4つのデシデラタを同時に保証できることを証明する。

関連論文リスト

• 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)
• Improved Bandits in Many-to-one Matching Markets with Incentive Compatibility [12.05174711411919]
  両面のマッチング市場は、そのリッチな応用のために、文献で広く研究されている。 まず,1対1設定のための既存のアルゴリズムをこのより一般的な設定に拡張し,プレイヤー最適後悔に対するほぼ最適境界を実現することを示す。 本稿では,アダプティブ・サーベイ・then-deferred (AETDA) アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-01-03T03:45:35Z)
• A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning [53.83345471268163]
  非定常マルチエージェントシステムにおける平衡の学習について検討する。 単エージェント学習へのブラックボックス還元による様々な平衡の検証方法を示す。
  論文  参考訳（メタデータ） (2023-06-12T23:48:24Z)
• Decentralized Competing Bandits in Non-Stationary Matching Markets [46.13741000158631]
  非定常(動的)環境下での分散化二面マッチング市場の枠組みを紹介する。 分散非定常競合帯域(textttDNCB)を用いた分散非同期学習アルゴリズムの提案と解析を行う。 我々はこの強調探索を特徴付け、texttDNCBのサブ線形(対数的)後悔を得る。
  論文  参考訳（メタデータ） (2022-05-31T21:05:30Z)
• Learn to Match with No Regret: Reinforcement Learning in Markov Matching Markets [151.03738099494765]
  我々は、市場の両側でプランナーと戦略エージェントのセットを含むマルコフマッチング市場について検討する。 本稿では,楽観的な値反復と最大重みマッチングを組み合わせた強化学習フレームワークを提案する。 我々は,アルゴリズムがサブ線形後悔を実現することを証明した。
  論文  参考訳（メタデータ） (2022-03-07T19:51:25Z)
• Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
  不確実性の下で安定した市場成果を学習するためのフレームワークとアルゴリズムを開発する。 私たちの研究は、大規模なデータ駆動の市場において、いつ、どのように安定したマッチングが生じるかを明らかにするための第一歩を踏み出します。
  論文  参考訳（メタデータ） (2021-08-19T17:59:28Z)
• Bandit Learning in Decentralized Matching Markets [82.39061186055775]
  私たちは、一方の市場(プレーヤー)が他方の側(腕)の好みについて事前知識を持っていない両面マッチング市場を研究し、経験からその好みを学ぶ必要があります。 このモデルは、標準のマルチアームバンディットフレームワークを競合する分散型マルチプレイヤー設定に拡張します。 アームの選好が共有されるたびにアルゴリズムがインセンティブ互換であることが示されるが、選好が完全に一般的である場合には必ずしもそうではない。
  論文  参考訳（メタデータ） (2020-12-14T08:58:07Z)
• Learning Strategies in Decentralized Matching Markets under Uncertain Preferences [91.3755431537592]
  エージェントの選好が不明な場合,共有資源の不足の設定における意思決定の問題について検討する。 我々のアプローチは、再生されたカーネルヒルベルト空間における好みの表現に基づいている。 エージェントの期待した利益を最大化する最適な戦略を導出する。
  論文  参考訳（メタデータ） (2020-10-29T03:08:22Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。