論文の概要: EFX Allocations Exist for Binary Valuations
- arxiv url: http://arxiv.org/abs/2308.05503v1
- Date: Thu, 10 Aug 2023 11:28:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-11 12:50:53.899760
- Title: EFX Allocations Exist for Binary Valuations
- Title(参考訳): バイナリ値のためのEFXアロケーション
- Authors: Xiaolin Bu, Jiaxin Song and Ziqi Yu
- Abstract要約: 公正な分割問題と公平な基準を満たす割り当ての存在について、あらゆる項目(EFX)まで検討する。
全く異なる手法を用いることで、この存在を必ずしも部分モジュラーでない一般二項評価にまで拡張する。
EFXアロケーションを計算するための時間アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the fair division problem and the existence of allocations
satisfying the fairness criterion envy-freeness up to any item (EFX). The
existence of EFX allocations is a major open problem in the fair division
literature. We consider binary valuations where the marginal gain of the value
by receiving an extra item is either $0$ or $1$. Babaioff et al. [2021] proved
that EFX allocations always exist for binary and submodular valuations. In this
paper, by using completely different techniques, we extend this existence
result to general binary valuations that are not necessarily submodular, and we
present a polynomial time algorithm for computing an EFX allocation.
- Abstract(参考訳): 公平な分割問題と公平な基準を満たす割り当ての存在について,任意の項目 (EFX) まで検討する。
EFXアロケーションの存在は、フェアディビジョン文学において大きなオープンな問題である。
余分なアイテムを受け取ることでその価値の限界値が$0$または$$$であるような二元評価を考える。
Babaioffなど。
EFXアロケーションが常にバイナリとサブモジュールのバリュエーションに対して存在することを[2021] 証明しました。
本稿では,全く異なる手法を用いて,その存在を必ずしも部分モジュラーではない一般的な二項評価に拡張し,efx割当を計算する多項式時間アルゴリズムを提案する。
関連論文リスト
- Dividing Good and Better Items Among Agents with Bivalued Submodular
Valuations [20.774185319381985]
本稿では,2値のサブモジュラー評価を持つエージェント間で,分割不可能な商品の集合を適切に割り当てる問題について検討する。
我々は、レキシミンとMNWの割り当てが1つの利益まで自由になされることは保証されていないことを示す。
論文 参考訳(メタデータ) (2023-02-06T19:41:28Z) - Optimizing Two-way Partial AUC with an End-to-end Framework [154.47590401735323]
ROC曲線のエリア(AUC)は、機械学習にとって重要な指標である。
最近の研究は、TPAUCが既存のPartial AUCメトリクスと本質的に矛盾していることを示している。
本論文では,この新指標を最適化するための最初の試行について述べる。
論文 参考訳(メタデータ) (2022-06-23T12:21:30Z) - (Almost) Envy-Free, Proportional and Efficient Allocations of an
Indivisible Mixed Manna [10.933894827834825]
エージェントの集合に分割不可能な項目の集合を公平かつ効率的に割り当てることの課題について検討する。
公平性の概念として、エンビーフリーネスと比例性の最も強い緩和性を考える。
論文 参考訳(メタデータ) (2022-02-06T01:29:50Z) - Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
固有の報酬は、探検と探検のトレードオフを扱う上で中心的な役割を果たす。
楕円ボーナスを効率的に近似するためのエンファンティ集中型信頼境界を導入する。
我々は,Atariベンチマーク上での現代固有の報酬と競合する,深層強化学習のための実用的な変種を開発する。
論文 参考訳(メタデータ) (2021-10-21T15:25:15Z) - Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria
and Fairness [16.187873844872637]
付加価値関数を持つ戦略エージェントの集合に、分割不可能な商品の集合をかなり割り当てるという問題を考察する。
我々の主なゴールは、全てのインスタンスに純粋なナッシュ平衡を持つメカニズムが存在するかどうかを探ることである。
対応するアロケーションは EFX だけでなく、最大シェアフェアネスも満足していることを示します。
論文 参考訳(メタデータ) (2021-09-17T16:57:20Z) - Binary Classification from Multiple Unlabeled Datasets via Surrogate Set
Classification [94.55805516167369]
我々は m 個の U 集合を $mge2$ で二進分類する新しい手法を提案する。
我々のキーとなる考え方は、サロゲート集合分類(SSC)と呼ばれる補助的分類タスクを考えることである。
論文 参考訳(メタデータ) (2021-02-01T07:36:38Z) - Towards Fair Knowledge Transfer for Imbalanced Domain Adaptation [61.317911756566126]
本研究では,不均衡なドメイン間学習における公平性問題に対処するTowards Fair Knowledge Transferフレームワークを提案する。
具体的には、新規なクロスドメインミックスアップ生成を利用して、ターゲット情報でマイノリティソースセットを増強し、公正性を高める。
本モデルでは,2つのベンチマークで全体の精度を20%以上向上させる。
論文 参考訳(メタデータ) (2020-10-23T06:29:09Z) - Relative Deviation Margin Bounds [55.22251993239944]
我々はRademacher複雑性の観点から、分布依存と一般家庭に有効な2種類の学習境界を与える。
有限モーメントの仮定の下で、非有界な損失関数に対する分布依存的一般化境界を導出する。
論文 参考訳(メタデータ) (2020-06-26T12:37:17Z) - Envy-freeness up to one item: Shall we add or remove resources? [2.28438857884398]
フェアディビジョンモデル(EF1+-とEFX+-)におけるアロケーションに対する2つの新しい公理特性を提案する。
EF1 と EF1+- のアロケーションはしばしば存在するが、EFX+- と PO のアロケーションは、EFX と PO のアロケーションが存在しないすべてのケースに存在していると、我々の結果は主張している。
論文 参考訳(メタデータ) (2020-06-19T18:29:05Z) - Finding Fair and Efficient Allocations When Valuations Don't Add Up [25.962505544590947]
エージェント評価がマトロイドのランク関数である場合、社会的に最適な(実用的社会福祉の最大化)手法は、1つの項目(EF1)までのうらやましい自由度が存在し、計算的に抽出可能であることを示す。
これは、ナッシュの福祉を最大化する割り当てがEF1であると確立された付加的評価によって仮定されない最初の評価関数クラスである。
論文 参考訳(メタデータ) (2020-03-16T07:42:27Z) - A General Method for Robust Learning from Batches [56.59844655107251]
本稿では,バッチから頑健な学習を行う一般的なフレームワークについて考察し,連続ドメインを含む任意の領域に対する分類と分布推定の限界について考察する。
本手法は,一括分節分類,一括分節,単調,対数凹,ガウス混合分布推定のための,最初の頑健な計算効率の学習アルゴリズムを導出する。
論文 参考訳(メタデータ) (2020-02-25T18:53:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。