論文の概要: Finding Fair and Efficient Allocations When Valuations Don't Add Up
- arxiv url: http://arxiv.org/abs/2003.07060v4
- Date: Fri, 18 Jun 2021 05:21:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-23 03:40:39.930482
- Title: Finding Fair and Efficient Allocations When Valuations Don't Add Up
- Title（参考訳）: 評価が上がらないときに、公平で効率的なアロケーションを見つける
- Authors: Nawal Benabbou, Mithun Chakraborty, Ayumi Igarashi, Yair Zick
- Abstract要約: エージェント評価がマトロイドのランク関数である場合、社会的に最適な(実用的社会福祉の最大化)手法は、1つの項目(EF1)までのうらやましい自由度が存在し、計算的に抽出可能であることを示す。
これは、ナッシュの福祉を最大化する割り当てがEF1であると確立された付加的評価によって仮定されない最初の評価関数クラスである。
- 参考スコア（独自算出の注目度）: 25.962505544590947
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we present new results on the fair and efficient allocation of
indivisible goods to agents whose preferences correspond to {\em matroid rank
functions}. This is a versatile valuation class with several desirable
properties (such as monotonicity and submodularity), which naturally lends
itself to a number of real-world domains. We use these properties to our
advantage; first, we show that when agent valuations are matroid rank
functions, a socially optimal (i.e. utilitarian social welfare-maximizing)
allocation that achieves envy-freeness up to one item (EF1) exists and is
computationally tractable. We also prove that the Nash welfare-maximizing and
the leximin allocations both exhibit this fairness/efficiency combination, by
showing that they can be achieved by minimizing any symmetric strictly convex
function over utilitarian optimal outcomes. To the best of our knowledge, this
is the first valuation function class not subsumed by additive valuations for
which it has been established that an allocation maximizing Nash welfare is
EF1. Moreover, for a subclass of these valuation functions based on maximum
(unweighted) bipartite matching, we show that a leximin allocation can be
computed in polynomial time. Additionally, we explore possible extensions of
our results to fairness criteria other than EF1 as well as to generalizations
of the above valuation classes.
- Abstract（参考訳）: 本稿では, 選好が {\em matroid rank function} に対応するエージェントに対して, 不特定商品の公平かつ効率的な配分に関する新たな結果を示す。
これは、いくつかの望ましい性質(モノトニック性や部分モジュラリティなど)を持つ多元的評価クラスであり、自然に多くの実世界の領域に自己を与える。
まず,エージェント評価がマトロイドランク関数である場合,最大1項目(EF1)までのエンビーフリーネスを達成する社会的最適(実用的社会福祉最大化)アロケーションが存在し,計算的に抽出可能であることを示す。
また、Nashの福祉最大化とレキシミン割り当ては、実用的最適結果よりも対称的厳密凸関数を最小化することにより達成できることを示し、この公正/効率の組み合わせを示す。
我々の知る限りでは、ナッシュの福祉を最大化する割り当てがEF1であることが確立された付加的評価によって仮定されない最初の評価関数クラスである。
さらに,最大(非重み付き)二成分マッチングに基づく評価関数のサブクラスに対して,レキシミン割当を多項式時間で計算可能であることを示す。
さらに、EF1以外の公平性基準への拡張の可能性や、上記の評価クラスの一般化についても検討する。
関連論文リスト
- Statistical Inference of Optimal Allocations I: Regularities and their Implications [3.904240476752459]
まず、ソート作用素の一般性質の詳細な解析を通して、値関数のアダマール微分可能性(英語版)を導出する。
アダマール微分可能性の結果に基づいて、関数デルタ法を用いて値関数プロセスの特性を直接導出する方法を実証する。
論文 参考訳（メタデータ） (2024-03-27T04:39:13Z) - Explainable Disparity Compensation for Efficient Fair Ranking [0.3759936323189418]
意思決定システムで使用されるランク付け関数は、基礎となるデータに偏りがあるため、異なる集団に対して異なる結果をもたらすことが多い。
最近の補償策は主に、公正性を保証するためにランク関数の不透明な変換に焦点を当てている。
本稿では,ランキング関数に対するデータ駆動型補償法を提案する。
論文 参考訳（メタデータ） (2023-07-25T09:12:50Z) - Dividing Good and Better Items Among Agents with Bivalued Submodular
Valuations [20.774185319381985]
本稿では,2値のサブモジュラー評価を持つエージェント間で,分割不可能な商品の集合を適切に割り当てる問題について検討する。
我々は、レキシミンとMNWの割り当てが1つの利益まで自由になされることは保証されていないことを示す。
論文 参考訳（メタデータ） (2023-02-06T19:41:28Z) - Approximating the Shapley Value without Marginal Contributions [11.539320505465149]
協調ゲームにおいてプレイヤーに有意義な貢献価値を割り当てる最も一般的な手法であるShapley値は最近、説明可能な人工知能において集中的に使用されている。
本稿では,余剰寄与の概念から分離されたShapley値の表現に基づく2つのパラメータフリーおよびドメイン非依存近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-01T20:14:22Z) - RankFeat: Rank-1 Feature Removal for Out-of-distribution Detection [65.67315418971688]
textttRankFeat は OOD 検出のためのシンプルだが効果的な textttpost hoc アプローチである。
textttRankFeatは、Emphstate-of-the-artパフォーマンスを実現し、以前のベストメソッドと比較して平均偽陽性率(FPR95)を17.90%削減する。
論文 参考訳（メタデータ） (2022-09-18T16:01:31Z) - Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium
Learning from Offline Datasets [101.5329678997916]
両プレイヤーゼロサムマルコフゲーム(MG)をオフライン環境で研究する。
目標は、事前収集されたデータセットに基づいて、近似的なナッシュ均衡(NE)ポリシーペアを見つけることである。
論文 参考訳（メタデータ） (2022-02-15T15:39:30Z) - Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria
and Fairness [16.187873844872637]
付加価値関数を持つ戦略エージェントの集合に、分割不可能な商品の集合をかなり割り当てるという問題を考察する。
我々の主なゴールは、全てのインスタンスに純粋なナッシュ平衡を持つメカニズムが存在するかどうかを探ることである。
対応するアロケーションは EFX だけでなく、最大シェアフェアネスも満足していることを示します。
論文 参考訳（メタデータ） (2021-09-17T16:57:20Z) - Scalable Personalised Item Ranking through Parametric Density Estimation [53.44830012414444]
暗黙のフィードバックから学ぶことは、一流問題の難しい性質のために困難です。
ほとんどの従来の方法は、一級問題に対処するためにペアワイズランキングアプローチとネガティブサンプラーを使用します。
本論文では,ポイントワイズと同等の収束速度を実現する学習対ランクアプローチを提案する。
論文 参考訳（メタデータ） (2021-05-11T03:38:16Z) - Finite Sample Analysis of Minimax Offline Reinforcement Learning:
Completeness, Fast Rates and First-Order Efficiency [83.02999769628593]
強化学習におけるオフ・ポリティィ・アセスメント(OPE)の理論的特徴について述べる。
ミニマックス法により、重みと品質関数の高速収束を実現することができることを示す。
非タブラル環境における1次効率を持つ最初の有限サンプル結果を示す。
論文 参考訳（メタデータ） (2021-02-05T03:20:39Z) - Are we Forgetting about Compositional Optimisers in Bayesian
Optimisation? [66.39551991177542]
本稿では,グローバル最適化のためのサンプル手法を提案する。
この中、重要なパフォーマンス決定の自明さは、取得機能を最大化することです。
3958実験における機能最適化手法の実証的利点を強調する。
論文 参考訳（メタデータ） (2020-12-15T12:18:38Z) - Provably Efficient Reward-Agnostic Navigation with Linear Value
Iteration [143.43658264904863]
我々は、最小二乗値スタイルのアルゴリズムで一般的に使用される、より標準的なベルマン誤差の概念の下での反復が、ほぼ最適値関数の学習において強力なPAC保証を提供することを示す。
そこで本稿では,任意の(線形な)報酬関数に対して,最適に近いポリシーを学習するためにどのように使用できるかを示す。
論文 参考訳（メタデータ） (2020-08-18T04:34:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。