論文の概要: Multilevel Fair Allocation

• arxiv url: http://arxiv.org/abs/2512.24105v1
• Date: Tue, 30 Dec 2025 09:27:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-01 23:27:28.344919
• Title: Multilevel Fair Allocation
• Title（参考訳）: 多レベルフェアアロケーション
• Authors: Maxime Lucet, Nawal Benabbou, Aurélie Beynier, Nicolas Maudet,
• Abstract要約: エージェント間の木構造関係を持つ資源の多段階的均等割当の概念を導入する。 原則として、各中間ノードは独自のローカルアロケーション機構を持つことができる。 木の葉がマトロイドランクのユーティリティ関数を持つという仮定のもと、2つの元のアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.40948483603286223
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce the concept of multilevel fair allocation of resources with tree-structured hierarchical relations among agents. While at each level it is possible to consider the problem locally as an allocation of an agent to its children, the multilevel allocation can be seen as a trace capturing the fact that the process is iterated until the leaves of the tree. In principle, each intermediary node may have its own local allocation mechanism. The main challenge is then to design algorithms which can retain good fairness and efficiency properties. In this paper we propose two original algorithms under the assumption that leaves of the tree have matroid-rank utility functions and the utility of any internal node is the sum of the utilities of its children. The first one is a generic polynomial-time sequential algorithm that comes with theoretical guarantees in terms of efficiency and fairness. It operates in a top-down fashion -- as commonly observed in real-world applications -- and is compatible with various local algorithms. The second one extends the recently proposed General Yankee Swap to the multilevel setting. This extension comes with efficiency guarantees only, but we show that it preserves excellent fairness properties in practice.
• Abstract（参考訳）: エージェント間の木構造的階層関係を持つ資源の多レベル均等割当の概念を導入する。 各レベルでは、この問題をエージェントの子供への割り当てとしてローカルに考えることができるが、マルチレベルアロケーションは、プロセスが木の葉まで反復されているという事実を捉えたトレースと見なすことができる。 原則として、各中間ノードは独自のローカルアロケーション機構を持つことができる。 主な課題は、良好な公正性と効率性を維持できるアルゴリズムを設計することである。 本稿では,木葉がマトロイドランクのユーティリティ関数を持つことを前提に,内部ノードの効用は子どものユーティリティの総和である,という仮定のもとに,2つのオリジナルアルゴリズムを提案する。 1つは多項式時間逐次アルゴリズムで、効率性と公平性の観点から理論的に保証される。 現実世界のアプリケーションでよく見られるように、トップダウンで動作し、さまざまなローカルアルゴリズムと互換性がある。 2つ目は、最近提案されたジェネラル・ヤンキー・スワップをマルチレベル設定に拡張したものである。 この拡張は効率性のみを保証するが、実際には優れた公正性を保っていることを示す。

関連論文リスト

• TreePO: Bridging the Gap of Policy Optimization and Efficacy and Inference Efficiency with Heuristic Tree-based Modeling [65.46347858249295]
  TreePOは自己誘導型ロールアウトアルゴリズムで、シーケンス生成を木構造検索プロセスとして見る。 TreePOは基本的に、探索の多様性を保存または強化しながら、更新毎の計算負担を削減します。
  論文  参考訳（メタデータ） (2025-08-24T16:52:37Z)
• Scalable spectral representations for multi-agent reinforcement learning in network MDPs [13.782868855372774]
  マルチエージェント制御の一般的なモデルであるNetwork Markov Decision Processes (MDPs)は、効率的な学習に重大な課題をもたらす。 まず、ネットワークMDPに対してスケーラブルなスペクトル局所表現を導出し、各エージェントの局所$Q$関数に対するネットワーク線形部分空間を誘導する。 我々は,連続的な状態対応ネットワークMDPのためのスケーラブルなアルゴリズムフレームワークを設計し,アルゴリズムの収束をエンドツーエンドで保証する。
  論文  参考訳（メタデータ） (2024-10-22T17:45:45Z)
• Hierarchical Clustering via Local Search [0.0]
  階層クラスタリングのための局所探索アルゴリズムを提案する。 任意の局所最適木は少なくとも$fracn-23sum_i jw(i,j)$の収益を保証し、そこでは$n$はオブジェクトの数で、$w: [n] times [n] mathbbR+$は関連する類似関数である。
  論文  参考訳（メタデータ） (2024-05-24T23:46:24Z)
• Dynamic Perceiver for Efficient Visual Recognition [87.08210214417309]
  特徴抽出手順と早期分類タスクを分離する動的知覚器(Dyn-Perceiver)を提案する。 特徴ブランチは画像の特徴を抽出し、分類ブランチは分類タスクに割り当てられた遅延コードを処理する。 早期出口は分類枝に限られており、低レベルの特徴において線形分離性は不要である。
  論文  参考訳（メタデータ） (2023-06-20T03:00:22Z)
• Non-Linear Coordination Graphs [22.29517436920317]
  座標グラフ(CG)は、ペアのペイオフ関数を組み込んだ高次分解を表す。 CG値の分解を線形の場合を超えて拡張することにより、最初の非線形座標グラフを提案する。 提案手法は,MACOのようなマルチエージェント協調タスクにおいて,優れた性能を実現することができる。
  論文  参考訳（メタデータ） (2022-10-26T18:11:31Z)
• Yankee Swap: a Fast and Simple Fair Allocation Mechanism for Matroid Rank Valuations [16.013563937696297]
  エージェントがマトロイドランクの評価値を持つ場合、不特定商品の公平な割り当てについて検討する。 我々の主な貢献は、証明可能な公平かつ効率的なロレンツ支配割り当てを計算する単純なアルゴリズムである。
  論文  参考訳（メタデータ） (2022-06-17T00:44:11Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。 活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
  論文  参考訳（メタデータ） (2021-04-14T09:22:42Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。 提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
  論文  参考訳（メタデータ） (2020-12-04T15:46:30Z)
• Measure Inducing Classification and Regression Trees for Functional Data [0.0]
  機能的データ分析の文脈における分類と回帰問題に対する木に基づくアルゴリズムを提案する。 これは、制約付き凸最適化により重み付き汎函数 L2$ 空間を学習することで達成される。
  論文  参考訳（メタデータ） (2020-10-30T18:49:53Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。 当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
  論文  参考訳（メタデータ） (2020-07-24T17:06:55Z)

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

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