論文の概要: 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（参考訳）: 複数のラウンドで同じエージェントのセットにアイテムのセットが繰り返しマッチするシーケンシャルな意思決定モデルについて検討する。
目的は、全てのラウンドの終端(最適)または各ラウンドの終端(常に最適)において、最も有利でないエージェントの効用を最大化するマッチングの列を決定することである。
最適結果の発見にかかわる計算課題について検討し、これらの問題が一般に計算に難易度があることを実証する。
しかし、近似アルゴリズム、固定パラメータ抽出可能なアルゴリズムを提供し、この問題を効率的に解決できる特別なケースをいくつか特定する。
その過程では、マッチング理論や住宅割当の研究に独立して興味を持つパレート最適/最大マッチングの特性も確立する。
関連論文リスト
- 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) - Generalization in portfolio-based algorithm selection [97.74604695303285]
ポートフォリオベースのアルゴリズム選択に関する最初の証明可能な保証を提供する。
ポートフォリオが大きければ、非常に単純なアルゴリズムセレクタであっても、過剰適合は避けられないことを示す。
論文 参考訳（メタデータ） (2020-12-24T16:33:17Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。