論文の概要: Understanding EFX Allocations: Counting and Variants

• arxiv url: http://arxiv.org/abs/2504.03951v1
• Date: Fri, 04 Apr 2025 21:36:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-08 14:09:27.874913
• Title: Understanding EFX Allocations: Counting and Variants
• Title（参考訳）: EFXの割り当てを理解する: カウントと変数
• Authors: Tzeh Yuan Neoh, Nicholas Teh,
• Abstract要約: 好ましくないもの(EFX)へのエンビーフリーネス(envy-freeness)は、不特定商品の公平な割り当てにおいて人気があり重要な公正性である。 このアプローチは、EFXアロケーションの存在と計算に関する貴重な洞察をもたらすかもしれない、と我々は主張する。
• 参考スコア（独自算出の注目度）: 0.8287206589886881
• License:
• Abstract: Envy-freeness up to any good (EFX) is a popular and important fairness property in the fair allocation of indivisible goods, of which its existence in general is still an open question. In this work, we investigate the problem of determining the minimum number of EFX allocations for a given instance, arguing that this approach may yield valuable insights into the existence and computation of EFX allocations. We focus on restricted instances where the number of goods slightly exceeds the number of agents, and extend our analysis to weighted EFX (WEFX) and a novel variant of EFX for general monotone valuations, termed EFX+. In doing so, we identify the transition threshold for the existence of allocations satisfying these fairness notions. Notably, we resolve open problems regarding WEFX by proving polynomial-time computability under binary additive valuations, and establishing the first constant-factor approximation for two agents.
• Abstract（参考訳）: あらゆる善(EFX)へのエンビーフリーネスは、不特定商品の公平な割り当てにおいて人気があり重要な公正性特性であり、一般にその存在は依然として明らかな問題である。 本研究では,あるインスタンスのEFXアロケーションの最小数を決定する問題について検討し,この手法がEFXアロケーションの存在と計算に関する貴重な洞察をもたらす可能性があることを論じる。 商品の数がエージェント数よりわずかに多い制限インスタンスに焦点を合わせ、分析を重み付きEFX(WEFX)に拡張し、一般的なモノトン評価のための新しいEFXの変種であるEFX+(EFX+)に拡張する。 そこで我々は,これらの公平性の概念を満たすアロケーションの存在に対する遷移しきい値を特定する。 特に、二項加法評価の下で多項式時間計算可能性を証明することにより、WEFXに関するオープンな問題を解決し、2つのエージェントに対する最初の定数近似を確立する。

関連論文リスト

• On the existence of EFX allocations in multigraphs [0.8057006406834466]
  商品の集合上で評価セット機能を持つ複数のエージェントに対して、分割不可能な商品を分割する問題について検討する。 公平に見れば、いかなる善(EFX)までうらやましくないアロケーション、すなわち、他のエージェントに与えられた商品の適切なサブセットを敵視するエージェントはいない。
  論文  参考訳（メタデータ） (2025-02-13T21:16:27Z)
• STORM: A Spatio-Temporal Factor Model Based on Dual Vector Quantized Variational Autoencoders for Financial Trading [55.02735046724146]
  金融取引では、ファクターモデルが資産の価格設定や過大なリターンの獲得に広く利用されている。 双対ベクトル量子化変分オートエンコーダを用いた時空間ファクトラーモデルSTORMを提案する。 ストームは時間的および空間的な視点からストックの特徴を抽出し、これらの特徴を微細で意味的なレベルで融合し整列させ、その要素を多次元の埋め込みとして表現する。
  論文  参考訳（メタデータ） (2024-12-12T17:15:49Z)
• Temporal Fair Division of Indivisible Items [61.235172150247614]
  分割不可能なアイテムが順次到着し,即時かつ無効に割り当てられなければならない公平な分割モデルについて検討する。 オンラインフェアディビジョンに関する以前の研究は、これらの制約の下で近似的なうらやみのない結果が得られないことを示してきた。 各ラウンドにおける累積割り当てが1項目までの時間的エンビーフリーネス(TEF1)に近似することを確実にすることを目指している。
  論文  参考訳（メタデータ） (2024-10-18T16:43:36Z)
• Pushing the Frontier on Approximate EFX Allocations [14.101164748526159]
  本研究では, 付加的評価関数を持つエージェント群に対して, 分割不可能な商品群を割り当てる問題について検討する。 正確なEFXアロケーションが存在することが分かっている設定の厳密な一般化のために、我々は存在結果を得る。 この結果から, 近似EFXアロケーションの存在と計算のフロンティアを推し進めることができた。
  論文  参考訳（メタデータ） (2024-06-18T09:01:37Z)
• Goodhart's Law Applies to NLP's Explanation Benchmarks [57.26445915212884]
  ERASER(Comprehensiveness and sufficiency)メトリクスとEVAL-X(EVAL-X)メトリクスの2つのセットを批判的に検討する。 実験結果の予測や説明を変えることなく,モデル全体の包括性と充足率を劇的に向上させることができることを示す。 我々の結果は、現在のメトリクスが説明可能性の研究をガイドする能力に疑問を呈し、これらのメトリクスが正確に捉えるものを再評価する必要性を強調します。
  論文  参考訳（メタデータ） (2023-08-28T03:03:03Z)
• EFX Allocations Exist for Binary Valuations [0.0]
  公正な分割問題と公平な基準を満たす割り当ての存在について、あらゆる項目(EFX)まで検討する。 全く異なる手法を用いることで、この存在を必ずしも部分モジュラーでない一般二項評価にまで拡張する。 EFXアロケーションを計算するための時間アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-08-10T11:28:31Z)
• Action Quality Assessment with Temporal Parsing Transformer [84.1272079121699]
  行動品質評価(AQA)は、作業の理解と解決に重要である。 本稿では,時間的部分表現に包括的特徴を分解する時間的パーシング変換器を提案する。 提案手法は,3つの公開AQAベンチマークにおける先行研究よりもかなりのマージンで優れていた。
  論文  参考訳（メタデータ） (2022-07-19T13:29:05Z)
• Robust Allocations with Diversity Constraints [65.3799850959513]
  エージェント値の積を最大化するナッシュ福祉規則は,多様性の制約が導入されたとき,一意にロバストな位置にあることを示す。 また, ナッシュ・ウェルズによる保証は, 広く研究されているアロケーション・ルールのクラスにおいて, ほぼ最適であることを示す。
  論文  参考訳（メタデータ） (2021-09-30T11:09:31Z)
• Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness [16.187873844872637]
  付加価値関数を持つ戦略エージェントの集合に、分割不可能な商品の集合をかなり割り当てるという問題を考察する。 我々の主なゴールは、全てのインスタンスに純粋なナッシュ平衡を持つメカニズムが存在するかどうかを探ることである。 対応するアロケーションは EFX だけでなく、最大シェアフェアネスも満足していることを示します。
  論文  参考訳（メタデータ） (2021-09-17T16:57:20Z)
• Universal Off-Policy Evaluation [64.02853483874334]
  ユニバーサルオフ政治推定器(UnO)への第一歩を踏み出す 我々は, 平均, 分散, 分位数/中間数, 分位数範囲, cvar, および累積分布全体の推定と同時結合に uno を用いる。
  論文  参考訳（メタデータ） (2021-04-26T18:54:31Z)
• Finding Fair and Efficient Allocations When Valuations Don't Add Up [25.962505544590947]
  エージェント評価がマトロイドのランク関数である場合、社会的に最適な(実用的社会福祉の最大化)手法は、1つの項目(EF1)までのうらやましい自由度が存在し、計算的に抽出可能であることを示す。 これは、ナッシュの福祉を最大化する割り当てがEF1であると確立された付加的評価によって仮定されない最初の評価関数クラスである。
  論文  参考訳（メタデータ） (2020-03-16T07:42:27Z)

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

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