論文の概要: Fairness in Repeated Matching: A Maximin Perspective
- arxiv url: http://arxiv.org/abs/2510.04624v1
- Date: Mon, 06 Oct 2025 09:32:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-07 16:52:59.778169
- Title: Fairness in Repeated Matching: A Maximin Perspective
- Title（参考訳）: 反復マッチングの公正性:最大的視点
- Authors: Eugene Lim, Tzeh Yuan Neoh, Nicholas Teh,
- Abstract要約: 複数のラウンドで同じエージェントのセットにアイテムのセットが繰り返しマッチするシーケンシャルな意思決定モデルについて検討する。
目的は、全てのラウンドの終端(最適)または各ラウンドの終端(常に最適)において、最も有利でないエージェントの効用を最大化するマッチングの列を決定することである。
- 参考スコア（独自算出の注目度）: 13.603504120117016
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a sequential decision-making model where a set of items is repeatedly matched to the same set of agents over multiple rounds. The objective is to determine a sequence of matchings that either maximizes the utility of the least advantaged agent at the end of all rounds (optimal) or at the end of every individual round (anytime optimal). We investigate the computational challenges associated with finding (anytime) optimal outcomes and demonstrate that these problems are generally computationally intractable. However, we provide approximation algorithms, fixed-parameter tractable algorithms, and identify several special cases whereby the problem(s) can be solved efficiently. Along the way, we also establish characterizations of Pareto-optimal/maximum matchings, which may be of independent interest to works in matching theory and house allocation.
- Abstract（参考訳）: 複数のラウンドで同じエージェントのセットにアイテムのセットが繰り返しマッチするシーケンシャルな意思決定モデルについて検討する。
目的は、全てのラウンドの終端(最適)または各ラウンドの終端(常に最適)において、最も有利でないエージェントの効用を最大化するマッチングの列を決定することである。
最適結果の発見にかかわる計算課題について検討し、これらの問題が一般に計算に難易度があることを実証する。
しかし、近似アルゴリズム、固定パラメータ抽出可能なアルゴリズムを提供し、この問題を効率的に解決できる特別なケースをいくつか特定する。
その過程では、マッチング理論や住宅割当の研究に独立して興味を持つパレート最適/最大マッチングの特性も確立する。
関連論文リスト
- Convergence Rate of the Last Iterate of Stochastic Proximal Algorithms [8.636513507553504]
加算合成凸最適化問題を解くための2つの古典的アルゴリズムを解析する。
我々は、最後の反復収束率を得るために、一般的だが厳密な有界分散仮定に焦点を当てる。
本結果は,複数タスクおよびフェデレーション学習において発生するグラフ誘導正規化器に直接適用し,協調グラフのエッジ上の和として正規化器を分解する。
論文 参考訳（メタデータ） (2026-02-05T09:50:06Z) - Effective anytime algorithm for multiobjective combinatorial optimization problems [3.2061579211871383]
客観的な空間で十分に普及している効率的なソリューションのセットは、意思決定者に対して様々なソリューションを提供するのに好まれる。
本稿では,3つの新しいアイデアを組み合わせた多目的最適化のための新しい正確なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-02-06T11:53:44Z) - RIGA: A Regret-Based Interactive Genetic Algorithm [14.388696798649658]
そこで本研究では,多目的最適化問題を優先的精度で解くための対話型遺伝的アルゴリズムを提案する。
我々のアルゴリズムはRIGAと呼ばれ、集約関数がパラメータ内で線形であることから、任意の多目的最適化問題に適用できる。
いくつかのパフォーマンス指標(計算時間、最適性とクエリ数のギャップ)に対して、RIGAは最先端のアルゴリズムよりも優れた結果を得る。
論文 参考訳（メタデータ） (2023-11-10T13:56:15Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - Deep Probabilistic Graph Matching [72.6690550634166]
本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。
提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
論文 参考訳（メタデータ） (2022-01-05T13:37:27Z) - Optimal and Efficient Algorithms for General Mixable Losses against
Switching Oracles [0.0]
動的環境における混合損失関数のオンライン最適化について検討する。
我々の結果は、個々のシーケンス方式で強い決定論的意味を持つことが保証されている。
論文 参考訳（メタデータ） (2021-08-13T21:48:55Z) - Generalization in portfolio-based algorithm selection [97.74604695303285]
ポートフォリオベースのアルゴリズム選択に関する最初の証明可能な保証を提供する。
ポートフォリオが大きければ、非常に単純なアルゴリズムセレクタであっても、過剰適合は避けられないことを示す。
論文 参考訳（メタデータ） (2020-12-24T16:33:17Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Stochastic Optimization Forests [60.523606291705214]
標準的なランダムな森林アルゴリズムのように予測精度を向上させるために分割するのではなく、分割を選択した木を栽培し、下流の意思決定品質を直接最適化することで、森林決定政策の訓練方法を示す。
概略分割基準は、各候補分割に対して正確に最適化された森林アルゴリズムに近い性能を保ちながら、100倍のランニング時間を短縮できることを示す。
論文 参考訳（メタデータ） (2020-08-17T16:56:06Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。