論文の概要: Learning Equilibria in Matching Markets from Bandit Feedback

• arxiv url: http://arxiv.org/abs/2108.08843v1
• Date: Thu, 19 Aug 2021 17:59:28 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-20 14:38:00.249953
• Title: Learning Equilibria in Matching Markets from Bandit Feedback
• Title（参考訳）: バンディットフィードバックによるマッチング市場における学習平衡
• Authors: Meena Jagadeesan, Alexander Wei, Yixin Wang, Michael I. Jordan, Jacob Steinhardt
• Abstract要約: 不確実性の下で安定した市場成果を学習するためのフレームワークとアルゴリズムを開発する。 私たちの研究は、大規模なデータ駆動の市場において、いつ、どのように安定したマッチングが生じるかを明らかにするための第一歩を踏み出します。
• 参考スコア（独自算出の注目度）: 139.29934476625488
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large-scale, two-sided matching platforms must find market outcomes that align with user preferences while simultaneously learning these preferences from data. However, since preferences are inherently uncertain during learning, the classical notion of stability (Gale and Shapley, 1962; Shapley and Shubik, 1971) is unattainable in these settings. To bridge this gap, we develop a framework and algorithms for learning stable market outcomes under uncertainty. Our primary setting is matching with transferable utilities, where the platform both matches agents and sets monetary transfers between them. We design an incentive-aware learning objective that captures the distance of a market outcome from equilibrium. Using this objective, we analyze the complexity of learning as a function of preference structure, casting learning as a stochastic multi-armed bandit problem. Algorithmically, we show that "optimism in the face of uncertainty," the principle underlying many bandit algorithms, applies to a primal-dual formulation of matching with transfers and leads to near-optimal regret bounds. Our work takes a first step toward elucidating when and how stable matchings arise in large, data-driven marketplaces.
• Abstract（参考訳）: 大規模で双方向のマッチングプラットフォームは、ユーザの好みに合わせて、これらの好みをデータから同時に学習する市場結果を見つけなければなりません。 しかし、学習中の選好は本質的に不確実であるため、古典的安定性の概念(gale and shapley, 1962; shapley and shubik, 1971)はこれらの設定では達成できない。 このギャップを埋めるために,不確実性下で安定した市場成果を学習するためのフレームワークとアルゴリズムを開発した。 私たちの主要な設定は転送可能なユーティリティと一致し、プラットフォームはエージェントにマッチし、それらの間の金銭的移動を設定する。 市場の結果から均衡までの距離を捉えるインセンティブを意識した学習目標をデザインする。 この目的を用いて,選好構造として学習の複雑さを分析し,確率的多腕バンディット問題として学習をキャスティングする。 アルゴリズム学的には、多くのバンディットアルゴリズムの基礎となる「不確実性に直面した最適主義」は、伝達とのマッチングの原始双対的定式化に適用され、ほぼ最適の後悔の境界となる。 当社の作業は、大規模なデータ駆動市場において、いつ、どのように安定したマッチングが発生するかを明らかにするための第一歩です。

関連論文リスト

• Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning [14.448192914855674]
  両面のマッチング市場は、市場の片側からの参加者が好みに応じて反対側からの参加者と一致しなければならない、一連の問題を記述している。 我々は安定解の構造を利用して、安定解を見つける可能性を改善するアルゴリズムを考案する。
  論文  参考訳（メタデータ） (2024-10-06T06:47:53Z)
• Deviations from the Nash equilibrium and emergence of tacit collusion in a two-player optimal execution game with reinforcement learning [0.9208007322096533]
  2つの自律的エージェントが市場の影響下で同じ資産を最適に清算することを学習するシナリオについて検討する。 その結果,エージェントが学んだ戦略は,対応する市場影響ゲームのナッシュ均衡から大きく逸脱していることがわかった。 市場のボラティリティの異なるレベルがエージェントのパフォーマンスと彼らが発見する均衡にどのように影響するかを考察する。
  論文  参考訳（メタデータ） (2024-08-21T16:54:53Z)
• Decentralized and Uncoordinated Learning of Stable Matchings: A Game-Theoretic Approach [9.376820789668304]
  分散的かつ非協調的な方法で、未知の嗜好と安定したマッチングを学習する問題を考察する。 本研究では, 指数重み学習アルゴリズムを安定マッチングゲームに適用することにより, 完全分散・非協調的な対数的後悔を実現することを示す。 また、任意に高い確率で安定なマッチングにグローバルに収束する、分散的で非協調的な学習アルゴリズムも導入する。
  論文  参考訳（メタデータ） (2024-07-31T02:36:14Z)
• Fairness in Matching under Uncertainty [78.39459690570531]
  アルゴリズム的な二面市場は、こうした設定における公平性の問題に注意を向けている。 我々は、利益の不確実性を尊重する両面の市場設定において、個々人の公正性の概念を公理化する。 そこで我々は,配当よりも公平なユーティリティ最大化分布を求めるために,線形プログラミングフレームワークを設計する。
  論文  参考訳（メタデータ） (2023-02-08T00:30:32Z)
• Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets [2.9833943723592764]
  両面マッチング市場における競争環境におけるオンライン学習の問題について検討する。 本稿では、エージェントが安定したマッチングに到達できるように、分散化、通信、調整不要なアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2022-06-06T04:08:04Z)
• Learn to Match with No Regret: Reinforcement Learning in Markov Matching Markets [151.03738099494765]
  我々は、市場の両側でプランナーと戦略エージェントのセットを含むマルコフマッチング市場について検討する。 本稿では,楽観的な値反復と最大重みマッチングを組み合わせた強化学習フレームワークを提案する。 我々は,アルゴリズムがサブ線形後悔を実現することを証明した。
  論文  参考訳（メタデータ） (2022-03-07T19:51:25Z)
• Can Active Learning Preemptively Mitigate Fairness Issues? [66.84854430781097]
  データセットバイアスは、機械学習における不公平な原因の1つです。 不確実性に基づくALで訓練されたモデルが保護クラスの決定において公平であるかどうかを検討する。 また,勾配反転(GRAD)やBALDなどのアルゴリズム的公正性手法の相互作用についても検討する。
  論文  参考訳（メタデータ） (2021-04-14T14:20:22Z)
• Multi-Stage Decentralized Matching Markets: Uncertain Preferences and Strategic Behaviors [91.3755431537592]
  本稿では、現実世界のマッチング市場で最適な戦略を学ぶためのフレームワークを開発する。 我々は,不確実性レベルが特徴の福祉対フェアネストレードオフが存在することを示す。 シングルステージマッチングと比較して、マルチステージマッチングで参加者がより良くなることを証明します。
  論文  参考訳（メタデータ） (2021-02-13T19:25:52Z)
• Learning Strategies in Decentralized Matching Markets under Uncertain Preferences [91.3755431537592]
  エージェントの選好が不明な場合,共有資源の不足の設定における意思決定の問題について検討する。 我々のアプローチは、再生されたカーネルヒルベルト空間における好みの表現に基づいている。 エージェントの期待した利益を最大化する最適な戦略を導出する。
  論文  参考訳（メタデータ） (2020-10-29T03:08:22Z)

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

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