論文の概要: Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning
- arxiv url: http://arxiv.org/abs/2410.04376v1
- Date: Mon, 14 Oct 2024 23:37:37 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-02 08:10:32.592274
- Title: Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning
- Title(参考訳): Gale & Shapley を仕事に適用する - 学習による安定性の確保
- Authors: Hadi Hosseini, Sanjukta Roy, Duohan Zhang,
- Abstract要約: 両面のマッチング市場は、市場の片側からの参加者が好みに応じて反対側からの参加者と一致しなければならない、一連の問題を記述している。
我々は安定解の構造を利用して、安定解を見つける可能性を改善するアルゴリズムを考案する。
- 参考スコア(独自算出の注目度): 14.448192914855674
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Two-sided matching markets describe a large class of problems wherein participants from one side of the market must be matched to those from the other side according to their preferences. In many real-world applications (e.g. content matching or online labor markets), the knowledge about preferences may not be readily available and must be learned, i.e., one side of the market (aka agents) may not know their preferences over the other side (aka arms). Recent research on online settings has focused primarily on welfare optimization aspects (i.e. minimizing the overall regret) while paying little attention to the game-theoretic properties such as the stability of the final matching. In this paper, we exploit the structure of stable solutions to devise algorithms that improve the likelihood of finding stable solutions. We initiate the study of the sample complexity of finding a stable matching, and provide theoretical bounds on the number of samples needed to reach a stable matching with high probability. Finally, our empirical results demonstrate intriguing tradeoffs between stability and optimality of the proposed algorithms, further complementing our theoretical findings.
- Abstract(参考訳): 両面のマッチング市場は、市場の片側からの参加者が好みに応じて反対側からの参加者と一致しなければならないという、大きな種類の問題を表現している。
多くの現実世界のアプリケーション(例えば、コンテンツマッチングやオンライン労働市場)では、嗜好に関する知識はすぐには得られず、学習されなければならない。
オンライン・セッティングに関する最近の研究は、主に福祉最適化の側面(全体的な後悔の最小化)に焦点を当て、最終マッチングの安定性のようなゲーム理論的な性質にはほとんど注意を払っていない。
本稿では,安定解を見つける可能性を高めるアルゴリズムを考案するために,安定解の構造を利用する。
安定なマッチングを見つけるためのサンプルの複雑さの研究を開始し、高い確率で安定なマッチングに到達するために必要なサンプルの数に関する理論的境界を与える。
最後に,提案アルゴリズムの安定性と最適性の間には,興味深いトレードオフがみられ,さらに理論的な知見を補完する。
関連論文リスト
- Fair Reciprocal Recommendation in Matching Markets [0.8287206589886881]
エージェント間の双方向のマッチング市場における相互推薦について検討する。
我々のモデルでは、双方の個人が互いに関心を抱いている場合にのみ、マッチが成功すると考えられる。
フェアディビジョン理論の観点から、そのフェアネス基準、うらやましい自由さを導入する。
論文 参考訳(メタデータ) (2024-09-01T13:33:41Z) - Fully Stochastic Trust-Region Sequential Quadratic Programming for
Equality-Constrained Optimization Problems [62.83783246648714]
目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。
アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
論文 参考訳(メタデータ) (2022-11-29T05:52:17Z) - Learn to Match with No Regret: Reinforcement Learning in Markov Matching
Markets [151.03738099494765]
我々は、市場の両側でプランナーと戦略エージェントのセットを含むマルコフマッチング市場について検討する。
本稿では,楽観的な値反復と最大重みマッチングを組み合わせた強化学習フレームワークを提案する。
我々は,アルゴリズムがサブ線形後悔を実現することを証明した。
論文 参考訳(メタデータ) (2022-03-07T19:51:25Z) - 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) - 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) - Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online
Algorithms [85.97516436641533]
機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。
目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。
機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
論文 参考訳(メタデータ) (2020-10-22T04:51:01Z) - Algorithmic Stability in Fair Allocation of Indivisible Goods Among Two
Agents [8.66798555194688]
正当性の概念や近似効率の弱さとともに、正確な安定性を達成することは不可能であることを示す。
本稿では,安定性,すなわち近似安定性と弱近似安定性の2つの緩和法を提案する。
本稿では、ペアワイズ最大値の割り当てに関する一般的な特徴付けを行い、それを用いてほぼ安定なアルゴリズムを設計する。
論文 参考訳(メタデータ) (2020-07-30T03:09:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。