論文の概要: 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つのデシデラタを同時に保証できることを証明する。

関連論文リスト

• 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)
• Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
  オンライン学習の課題として,意思決定者が,リソース制約の有限セットに違反することなく,期待する報酬を最大化したい,という課題を提起する。 当社のフレームワークは,意思決定者がそのエビデンスを柔軟かつコスト論的に扱えるようにします。
  論文  参考訳（メタデータ） (2022-02-28T12:10:48Z)
• The Dichotomous Affiliate Stable Matching Problem: Approval-Based Matching with Applicant-Employer Relations [27.388757379210034]
  本稿では,DASM問題(Dichotomous Affiliate Stable Matching)について紹介する。 その結果は,(1)実世界のマッチングランキングが仮定された評価関数に従うことを示すために人間による研究,(2)そのような解を見つけるための効率的で実装が容易なアルゴリズムを提供することによって,常に安定した解が存在することを証明し,(3)線形プログラミングに基づくアプローチと比較して,アルゴリズムの有効性を実験的に検証する。
  論文  参考訳（メタデータ） (2022-02-22T18:56:21Z)
• 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)

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

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