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

• arxiv url: http://arxiv.org/abs/2407.21294v1
• Date: Wed, 31 Jul 2024 02:36:14 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-01 12:56:56.779887
• 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 in a fully decentralized and uncoordinated manner. In this problem, there are $n$ men and $n$ women, each having preference over the other side. It is assumed that women know their preferences over men, but men are not aware of their preferences over women, and they only learn them if they propose and successfully get matched to women. A matching is called stable if no man and woman prefer each other over their current matches. When all the preferences are known a priori, the celebrated Deferred-Acceptance algorithm proposed by Gale and Shapley provides a decentralized and uncoordinated algorithm to obtain a stable matching. However, when the preferences are unknown, developing such an algorithm faces major challenges due to a lack of coordination. We achieve this goal by making a connection between stable matchings and learning Nash equilibria (NE) in noncooperative games. First, we provide a complete information game formulation for the stable matching problem with known preferences such that its set of pure NE coincides with the set of stable matchings, while its mixed NE can be rounded in a decentralized manner to a stable matching. Relying on such a game-theoretic formulation, we show that for hierarchical markets, adopting the exponential weight (EXP) learning algorithm for the stable matching game achieves logarithmic regret with polynomial dependence on the number of players, thus answering a question posed in previous literature. Moreover, we show that the same EXP learning algorithm converges locally and exponentially fast to a stable matching in general matching markets. We complement this result by introducing another decentralized and uncoordinated learning algorithm that globally converges to a stable matching with arbitrarily high probability, leveraging the weak acyclicity property of the stable matching game.
• Abstract（参考訳）: 我々は、完全に分散化され、協調していない方法で安定したマッチングを学習する問題を考察する。 この問題では、男性$n$と女性$n$があり、それぞれが反対側を好みます。 女性は男性よりも好みを知っていると推定されるが、男性は女性よりも好みに気付いておらず、女性に合うように提案され、成功した場合にのみ学習する。 男女が現在の試合よりもお互いを好まない場合は、マッチングは安定と呼ばれる。 全ての選好が優先的であると、Galle と Shapley が提案した有名なDedeerred-Acceptance アルゴリズムは、安定なマッチングを得るために、分散化された非協調アルゴリズムを提供する。 しかし、選好が不明な場合、協調性の欠如により、そのようなアルゴリズムの開発は大きな課題に直面している。 我々は,非協調ゲームにおいて,安定マッチングとナッシュ均衡(NE)の学習を関連付けることで,この目標を達成する。 まず, 完全情報ゲームの定式化を行い, 純NEの集合は安定マッチングの集合と一致し, 混合NEは分散的に安定マッチングに丸められるようにした。 このようなゲーム理論の定式化に基づき、階層市場において、安定マッチングゲームに指数重み(EXP)学習アルゴリズムを採用することにより、プレイヤー数に多項式依存した対数的後悔を達成し、過去の文献で提起された疑問に答えることを示す。 さらに、同じEXP学習アルゴリズムが、一般市場における安定したマッチングに局所的に、指数的に高速に収束することを示す。 我々は、この結果を補うために、安定化された非協調的な学習アルゴリズムを導入し、安定なマッチングゲームの弱い非循環性を生かして、任意に高い確率で安定なマッチングにグローバルに収束する。

関連論文リスト

• Probably Correct Optimal Stable Matching for Two-Sided Markets Under Uncertainty [5.250288418639076]
  市場左側の好ましくない条件下での安定婚姻モデルの学習課題について考察する。 我々の目的は、左サイド最適である安定したマッチングを素早く識別することであり、バンドイットフィードバックによる純粋な探索問題である。
  論文  参考訳（メタデータ） (2025-01-06T13:59:57Z)
• 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)
• 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)

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

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