論文の概要: Decentralized and Uncoordinated Learning of Stable Matchings: A Game-Theoretic Approach

• arxiv url: http://arxiv.org/abs/2407.21294v2
• Date: Thu, 15 Aug 2024 02:57:09 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-16 17:56:52.379452
• Title: Decentralized and Uncoordinated Learning of Stable Matchings: A Game-Theoretic Approach
• Title（参考訳）: 安定マッチングの分散学習と非協調学習--ゲーム理論によるアプローチ
• Authors: S. Rasoul Etesami, R. Srikant,
• Abstract要約: 分散的かつ非協調的な方法で、未知の嗜好と安定したマッチングを学習する問題を考察する。 本研究では, 指数重み学習アルゴリズムを安定マッチングゲームに適用することにより, 完全分散・非協調的な対数的後悔を実現することを示す。 また、任意に高い確率で安定なマッチングにグローバルに収束する、分散的で非協調的な学習アルゴリズムも導入する。
• 参考スコア（独自算出の注目度）: 9.376820789668304
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of learning stable matchings with unknown preferences in a decentralized and uncoordinated manner, where "decentralized" means that players make decisions individually without the influence of a central platform, and "uncoordinated" means that players do not need to synchronize their decisions using pre-specified rules. First, we provide a game formulation for this problem with known preferences, where the set of pure Nash equilibria (NE) coincides with the set of stable matchings, and mixed NE can be rounded to a stable matching. Then, we show that for hierarchical markets, applying the exponential weight (EXP) learning algorithm to the stable matching game achieves logarithmic regret in a fully decentralized and uncoordinated fashion. Moreover, we show that EXP converges locally and exponentially fast to a stable matching in general markets. We also introduce another decentralized and uncoordinated learning algorithm that globally converges to a stable matching with arbitrarily high probability. Finally, we provide stronger feedback conditions under which it is possible to drive the market faster toward an approximate stable matching. Our proposed game-theoretic framework bridges the discrete problem of learning stable matchings with the problem of learning NE in continuous-action games.
• Abstract（参考訳）: 分散化」とは中央プラットフォームの影響を受けずに個別に決定を下すことを意味し、「非協調」とはプレイヤーが事前に規定されたルールを用いて決定を同期する必要がないことを意味する。 まず、この問題のゲーム定式化を行い、純ナッシュ平衡(NE)の集合と安定なマッチングの集合が一致し、混合NEを安定なマッチングに丸めることができる。 そして,階層型市場において,指数重み付け学習アルゴリズムを安定マッチングゲームに適用することにより,完全分散的かつ非協調的な対数的後悔を実現することを示す。 さらに,EXPは一般市場での安定なマッチングに局所的に,指数的に高速に収束することを示す。 また、任意に高い確率で安定なマッチングにグローバルに収束する、分散的で非協調的な学習アルゴリズムも導入する。 最後に、より強力なフィードバック条件を提供することにより、市場を近似した安定したマッチングに向けてより高速に駆動することが可能となる。 提案したゲーム理論フレームワークは,安定マッチングを学習する離散的な問題を,連続アクションゲームにおけるNE学習の問題に橋渡しする。

関連論文リスト

• The equivalence of dynamic and strategic stability under regularized learning in games [33.74394172275373]
  有限ゲームにおける正規化学習の長時間動作について検討する。 戦略的安定性と動的安定性の等価性を得る。 エントロピー正則化に基づく手法は幾何速度で収束することを示す。
  論文  参考訳（メタデータ） (2023-11-04T14:07:33Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。 我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。 我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
  論文  参考訳（メタデータ） (2023-03-22T03:28:12Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。 ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。 本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
  論文  参考訳（メタデータ） (2022-11-29T05:16:41Z)
• Efficiently Computing Nash Equilibria in Adversarial Team Markov Games [19.717850955051837]
  我々は,同じプレイヤーが対戦相手と競合するゲームのクラスを紹介する。 この設定により、ゼロサムマルコフゲームの可能性ゲームの統一処理が可能になる。 我々の主な貢献は、対戦チームマルコフゲームにおける固定的な$epsilon$-approximate Nash平衡を計算するための最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2022-08-03T16:41:01Z)
• Learn to Match with No Regret: Reinforcement Learning in Markov Matching Markets [151.03738099494765]
  我々は、市場の両側でプランナーと戦略エージェントのセットを含むマルコフマッチング市場について検討する。 本稿では,楽観的な値反復と最大重みマッチングを組み合わせた強化学習フレームワークを提案する。 我々は,アルゴリズムがサブ線形後悔を実現することを証明した。
  論文  参考訳（メタデータ） (2022-03-07T19:51:25Z)
• Optimal Algorithms for Decentralized Stochastic Variational Inequalities [113.43047601775453]
  この作業は、ますます重要になるが十分に理解されていない分散的な設定に集中する。 通信と局所的な繰り返しの両方の下位境界を示し、これらの下位境界に一致する最適なアルゴリズムを構築する。 我々のアルゴリズムは、分散化されたケースだけでなく、決定論的で非分散的な文献でも利用できる。
  論文  参考訳（メタデータ） (2022-02-06T13:14:02Z)
• Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
  不確実性の下で安定した市場成果を学習するためのフレームワークとアルゴリズムを開発する。 私たちの研究は、大規模なデータ駆動の市場において、いつ、どのように安定したマッチングが生じるかを明らかにするための第一歩を踏み出します。
  論文  参考訳（メタデータ） (2021-08-19T17:59:28Z)
• Optimality and Stability in Federated Learning: A Game-theoretic Approach [0.0]
  我々は,フェデレーションエージェント(プレーヤ)の平均誤差率によって与えられる最適性の概念を動機付け,定義する。 まず、パラメータ空間のいくつかの領域に対して、すべての安定な配置が最適である(アナーキーの値が 1 に等しい)ことを示す。 しかし、これはすべての設定に当てはまるものではなく、最適よりも高いコストで安定な配置の例が存在する(AnaarchyのPrice of Anarchy larger than 1)。
  論文  参考訳（メタデータ） (2021-06-17T15:03:51Z)
• Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information [32.384868685390906]
  一般Nプレイヤーゲームにおける非回帰学習のナッシュ平衡収束特性について検討する。 ナッシュ平衡の安定性と支持との包括的な等価性を確立します。 ゲームにおける非学習の日々の行動を予測するための明確な洗練基準を提供する。
  論文  参考訳（メタデータ） (2021-01-12T18:55:11Z)
• Bandit Learning in Decentralized Matching Markets [82.39061186055775]
  私たちは、一方の市場(プレーヤー)が他方の側(腕)の好みについて事前知識を持っていない両面マッチング市場を研究し、経験からその好みを学ぶ必要があります。 このモデルは、標準のマルチアームバンディットフレームワークを競合する分散型マルチプレイヤー設定に拡張します。 アームの選好が共有されるたびにアルゴリズムがインセンティブ互換であることが示されるが、選好が完全に一般的である場合には必ずしもそうではない。
  論文  参考訳（メタデータ） (2020-12-14T08:58:07Z)

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

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