Fugu-MT 論文翻訳(概要): EFX Allocations Exist for Binary Valuations

論文の概要: 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割当を計算する多項式時間アルゴリズムを提案する。

関連論文リスト

Temporal Fair Division of Indivisible Items [61.235172150247614]
分割不可能なアイテムが順次到着し,即時かつ無効に割り当てられなければならない公平な分割モデルについて検討する。オンラインフェアディビジョンに関する以前の研究は、これらの制約の下で近似的なうらやみのない結果が得られないことを示してきた。各ラウンドにおける累積割り当てが1項目までの時間的エンビーフリーネス(TEF1)に近似することを確実にすることを目指している。
論文参考訳（メタデータ） (2024-10-18T16:43:36Z)
Online Combinatorial Allocations and Auctions with Few Samples [9.675397292814122]
本稿では,O(1)競合アルゴリズムの実現可能性について,基礎となる入札者分布から限られた数のサンプルにしかアクセスできないという現実的な制約の下で検討する。最初の主な貢献は, サブモジュール/XOS評価のためのO(1)競合アルゴリズムを得るのに, 各入札者分布からのサンプルだけで十分であることを示している。
論文参考訳（メタデータ） (2024-09-17T11:43:55Z)
Pushing the Frontier on Approximate EFX Allocations [14.101164748526159]
本研究では, 付加的評価関数を持つエージェント群に対して, 分割不可能な商品群を割り当てる問題について検討する。正確なEFXアロケーションが存在することが分かっている設定の厳密な一般化のために、我々は存在結果を得る。この結果から, 近似EFXアロケーションの存在と計算のフロンティアを推し進めることができた。
論文参考訳（メタデータ） (2024-06-18T09:01:37Z)
Mind the Gap: A Causal Perspective on Bias Amplification in Prediction & Decision-Making [58.06306331390586]
本稿では,閾値演算による予測値がS$変化の程度を測るマージン補数の概念を導入する。適切な因果仮定の下では、予測スコア$S$に対する$X$の影響は、真の結果$Y$に対する$X$の影響に等しいことを示す。
論文参考訳（メタデータ） (2024-05-24T11:22:19Z)
Distributional Reinforcement Learning with Dual Expectile-Quantile Regression [51.87411935256015]
分布RLに対する量子レグレッションアプローチは、任意の戻り分布を柔軟かつ効果的に学習する方法を提供する。我々は,分布保証が消えることを示し,推定分布が急速に崩壊して平均推定値が崩壊することを実証的に観察する。提案手法は,$L$の学習効率を生かして,返却分布の予測値と量子化値とを協調的に学習し,返却分布の完全な分布を推定し,効率的な学習を可能にするものである。
論文参考訳（メタデータ） (2023-05-26T12:30:05Z)
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)
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)
Finding Fair and Efficient Allocations When Valuations Don't Add Up [25.962505544590947]
エージェント評価がマトロイドのランク関数である場合、社会的に最適な(実用的社会福祉の最大化)手法は、1つの項目(EF1)までのうらやましい自由度が存在し、計算的に抽出可能であることを示す。これは、ナッシュの福祉を最大化する割り当てがEF1であると確立された付加的評価によって仮定されない最初の評価関数クラスである。
論文参考訳（メタデータ） (2020-03-16T07:42:27Z)

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