論文の概要: Fair Stable Matching: A Nash Social Welfare Approach
- arxiv url: http://arxiv.org/abs/2609.02354v1
- Date: Wed, 02 Sep 2026 09:26:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-03 17:53:18.215952
- Title: Fair Stable Matching: A Nash Social Welfare Approach
- Title（参考訳）: フェアステアブルマッチング : ナッシュな社会福祉アプローチ
- Abstract要約: 古典的な婚姻問題における公正目標としてのEmphNash Social welfare(NSW)の役割について検討する。
我々は、ランク誘導ユーティリティの下でのナッシュ社会福祉を最大化する安定したマッチングを求めるtextttSNSW-Algを開発した。
以上の結果から,texttSNSW-Algが生成する安定マッチングは,他の公正度尺度に基づく安定マッチングによって統計的に無害であることが示唆された。
- 参考スコア（独自算出の注目度）: 5.97827861348588
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: While traditional stable matching algorithms, such as the Gale-Shapley algorithm, prioritize stability, they may fall short of achieving equitable outcomes among participants. We study the role of \emph{Nash social welfare} (NSW) as a fairness objective in the classic \emph{stable marriage problem}. We develop \texttt{SNSW-Alg} that finds a stable matching that maximizes Nash social welfare under rank-induced utilities in $\tilde{\mathcal{O}}(n^4)$ time, where $n$ is the number of men or women. We demonstrate that \texttt{SNSW-Alg} balances equity while preserving stability. We empirically evaluate our methods across diverse preference distributions, demonstrating significant gains in fairness without substantial losses in other key measures such as regret, egalitarian criterion, and sex equality. Our findings suggest that the stable matching produced by \texttt{SNSW-Alg} is statistically Pareto-undominated by stable matchings based on other fairness measures - regret, egalitarian, and sex equality. This study offers compelling insights for designing fair-stable matching.
- Abstract（参考訳）: Gale-Shapleyアルゴリズムのような従来の安定マッチングアルゴリズムは安定性を優先するが、参加者間で同等の結果が得られない。
本研究は,古典的婚姻問題におけるフェアネスの目的としての「emph{Nash Social welfare}」(NSW)の役割について考察する。
我々は,n$が男性または女性の数である場合,$\tilde{\mathcal{O}}(n^4)$ timeにおいて,ランク付き効用下でのナッシュ社会福祉を最大化する安定なマッチングを見出す「texttt{SNSW-Alg}」を開発した。
安定性を保ちながら株式のバランスをとることを実証する。
我々は, 様々な嗜好分布にまたがる手法を実証的に評価し, 後悔, 平等主義的基準, 性平等といった他の重要な尺度において, 実質的な損失を伴わずに, 公正性の顕著な向上を示す。
以上の結果から, <texttt{SNSW-Alg} が生成する安定マッチングは, その他の公正度尺度(後悔, 平等性, 性平等)に基づいて, 統計的にパレート・アンドマイト化されていることが示唆された。
この研究は、公正なマッチングを設計するための魅力的な洞察を提供する。
関連論文リスト
- Unregularized Linear Convergence in Zero-Sum Game from Preference Feedback [50.89125374999765]
NLHFにおける最適乗算重み更新(mathtOMWU$)に対する最初の収束保証を提供する。
本分析では, 稀に発生する行動の確率が指数関数的に小さい値から指数関数的に増大する新たな限界収束挙動を同定する。
論文 参考訳（メタデータ） (2025-12-31T12:08:29Z) - Learnable Mixed Nash Equilibria are Collectively Rational [17.93053401419066]
等安定性は, 漸進的スムーズな最適応答ダイナミクスの族に対する最終点収束挙動を決定することを示す。
社会的に非効率な解に安定化できる厳密な平衡に関する力学とは異なり、混合ナッシュ平衡の近傍での個別に実用性を求める挙動は合理性をもたらす。
論文 参考訳（メタデータ） (2025-10-16T17:25:32Z) - Competing Bandits in Matching Markets via Super Stability [3.846293944458337]
両面の報酬の不確実性を伴う市場における盗賊学習について検討する。
本研究は, 正規GSアルゴリズムよりも拡張Galle-Shapley (GS) アルゴリズムが真に安定なマッチングを実現することの利点を実証する。
論文 参考訳（メタデータ） (2025-06-19T00:03:20Z) - Stable Matching with Ties: Approximation Ratios and Learning [34.58046942241621]
我々は、市場の片側で働く労働者が、彼らのマッチングユーティリティーによって決定された、仕事よりも好みに結びついている可能性がある、マッチング市場と結びつきについて研究する。
厳格な嗜好を持つ古典的な二面市場とは異なり、すべての労働者に対して実用性を最大化する単一の安定なマッチングは存在しない。
論文 参考訳（メタデータ） (2024-11-05T17:14:46Z) - Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning [14.448192914855674]
両面のマッチング市場は、市場の片側からの参加者が好みに応じて反対側からの参加者と一致しなければならない、一連の問題を記述している。
我々は安定解の構造を利用して、安定解を見つける可能性を改善するアルゴリズムを考案する。
論文 参考訳（メタデータ） (2024-10-06T06:47:53Z) - Decentralized and Uncoordinated Learning of Stable Matchings: A Game-Theoretic Approach [9.376820789668304]
分散的かつ非協調的な方法で、未知の嗜好と安定したマッチングを学習する問題を考察する。
本研究では, 指数重み学習アルゴリズムを安定マッチングゲームに適用することにより, 完全分散・非協調的な対数的後悔を実現することを示す。
また、任意に高い確率で安定なマッチングにグローバルに収束する、分散的で非協調的な学習アルゴリズムも導入する。
論文 参考訳（メタデータ） (2024-07-31T02:36:14Z) - Beyond Expectations: Learning with Stochastic Dominance Made Practical [88.06211893690964]
支配は、不確実な結果で意思決定を行うためのリスク-逆の選好をモデル化する。
理論上は魅力的だが、機械学習における優位性の応用は乏しい。
まず支配の概念を一般化し、任意の確率変数の任意のペア間の比較を可能にする。
次に、優位性の観点から最適解を見つけるための単純で効率的なアプローチを開発する。
論文 参考訳（メタデータ） (2024-02-05T03:21:23Z) - Stability and Generalization of Stochastic Compositional Gradient
Descent Algorithms [61.59448949684493]
学習例から構築した合成降下アルゴリズムの安定性と一般化解析について述べる。
SCGD と SCSC という2つの一般的な合成勾配勾配勾配アルゴリズムの均一安定性について検討した。
SCGD と SCSC の非依存的過剰リスク境界は,安定性結果と最適化誤差をトレードオフすることによって導出する。
論文 参考訳（メタデータ） (2023-07-07T02:40:09Z) - PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。
連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
論文 参考訳（メタデータ） (2023-03-02T05:08:15Z) - Proportional Fairness in Obnoxious Facility Location [70.64736616610202]
この問題に対して,距離に基づく比例フェアネスの概念の階層構造を提案する。
決定論的かつランダムなメカニズムを考察し、比例フェアネスの価格に関する厳密な境界を計算する。
モデルの拡張が2つあることを示す。
論文 参考訳（メタデータ） (2023-01-11T07:30:35Z) - On Fairness and Stability in Two-Sided Matchings [12.495879803239802]
個人に関する重要な決定を行うか、影響を及ぼすアルゴリズムが、保護されたグループを差別する結果を生み出すのではないかという懸念が高まっている。
エージェントのセットが2つあり、各エージェントは他のセットよりも好みがある。
病院の選好を公平に設定することで,Gale-Shapleyアルゴリズムが極めて不公平な結果をもたらすことを示す。
論文 参考訳（メタデータ） (2021-11-21T19:46:28Z) - Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
不確実性の下で安定した市場成果を学習するためのフレームワークとアルゴリズムを開発する。
私たちの研究は、大規模なデータ駆動の市場において、いつ、どのように安定したマッチングが生じるかを明らかにするための第一歩を踏み出します。
論文 参考訳（メタデータ） (2021-08-19T17:59:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。