論文の概要: Temporal Fair Division of Indivisible Items

• arxiv url: http://arxiv.org/abs/2410.14593v1
• Date: Fri, 18 Oct 2024 16:43:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-21 14:24:31.599530
• Title: Temporal Fair Division of Indivisible Items
• Title（参考訳）: 不特定項目の時間的公正区分
• Authors: Edith Elkind, Alexander Lam, Mohamad Latifian, Tzeh Yuan Neoh, Nicholas Teh,
• Abstract要約: 分割不可能なアイテムが順次到着し,即時かつ無効に割り当てられなければならない公平な分割モデルについて検討する。 オンラインフェアディビジョンに関する以前の研究は、これらの制約の下で近似的なうらやみのない結果が得られないことを示してきた。 各ラウンドにおける累積割り当てが1項目までの時間的エンビーフリーネス(TEF1)に近似することを確実にすることを目指している。
• 参考スコア（独自算出の注目度）: 61.235172150247614
• License:
• Abstract: We study a fair division model where indivisible items arrive sequentially, and must be allocated immediately and irrevocably. Previous work on online fair division has shown impossibility results in achieving approximate envy-freeness under these constraints. In contrast, we consider an informed setting where the algorithm has complete knowledge of future items, and aim to ensure that the cumulative allocation at each round satisfies approximate envy-freeness -- which we define as temporal envy-freeness up to one item (TEF1). We focus on settings where items can be exclusively goods or exclusively chores. For goods, while TEF1 allocations may not always exist, we identify several special cases where they do -- two agents, two item types, generalized binary valuations, unimodal preferences -- and provide polynomial-time algorithms for these cases. We also prove that determining the existence of a TEF1 allocation is NP-hard. For chores, we establish analogous results for the special cases, but present a slightly weaker intractability result. We also establish the incompatibility between TEF1 and Pareto-optimality, with the implication that it is intractable to find a TEF1 allocation that maximizes any $p$-mean welfare, even for two agents.
• Abstract（参考訳）: 分割不可能なアイテムが順次到着し,即時かつ無効に割り当てられなければならない公平な分割モデルについて検討する。 オンラインフェアディビジョンに関する以前の研究は、これらの制約の下で近似的なうらやみのない結果が得られないことを示してきた。 対照的に、アルゴリズムが将来の項目について完全な知識を持つ情報的設定を考察し、各ラウンドにおける累積割り当てが、時間的エンビーフリーネスを最大1項目まで定義する近似的エンビーフリーネス(TEF1)を満たすことを目指している。 アイテムを独占的に商品や雑用できるような設定に重点を置いています。 商品の場合、EF1アロケーションが常に存在するとは限らないが、2つのエージェント、2つのアイテムタイプ、一般化されたバイナリバリュエーション、アンモダルな選好といった特別なケースを特定し、これらのケースに対して多項式時間アルゴリズムを提供する。 また、TEF1アロケーションの存在を決定することはNPハードであることも証明する。 補聴器では, 特別な症例に対して類似した結果が得られたが, 難易度はわずかに低下した。 また,TEF1 と Pareto-optimality の適合性も確立し,TEF1 のアロケーションが2つのエージェントに対しても最大で$p$-mean の福祉を最大化できることが示唆された。

関連論文リスト

• Online Combinatorial Allocations and Auctions with Few Samples [9.675397292814122]
  本稿では,O(1)競合アルゴリズムの実現可能性について,基礎となる入札者分布から限られた数のサンプルにしかアクセスできないという現実的な制約の下で検討する。 最初の主な貢献は, サブモジュール/XOS評価のためのO(1)競合アルゴリズムを得るのに, 各入札者分布からのサンプルだけで十分であることを示している。
  論文  参考訳（メタデータ） (2024-09-17T11:43:55Z)
• Local-Data-Hiding and Causal Inseparability: Probing Indefinite Causal Structures with Cryptographic Primitives [0.0]
  近年の研究では、新しい情報プリミティブとして現れる因果構造における不確定性の可能性が示唆されている。 本研究では,不定因果構造に埋め込まれたエージェントが,特定の因果的背景下で動作しているエージェントよりも優れていることを示す。 本稿では、LBHタスクにそれぞれ役に立たない2つの量子プロセスが一緒に使われる際に有用となる、興味深いスーパーアクティベーション現象を報告する。
  論文  参考訳（メタデータ） (2024-07-30T04:54:03Z)
• Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
  競売業者が各ラウンドの買い手グループに、合計で$T$で分けない商品を販売している問題を考える。 競売人は、各グループの最低平均配分を保証する公正な制約に固執しつつ、割引された全体の収益を最大化することを目的としている。
  論文  参考訳（メタデータ） (2024-05-31T19:26:05Z)
• Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
  細長い分布は、少数の少数派が限られた数のサンプルを含む実世界のデータにしばしば現れる。 近年の研究では、教師付きコントラスト学習がデータ不均衡を緩和する有望な可能性を示していることが明らかになっている。 本稿では,特徴空間の各クラスからのサンプルデータ分布を推定する確率論的コントラスト学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-11T13:44:49Z)
• Sampling Individually-Fair Rankings that are Always Group Fair [9.333939443470944]
  公正ランキングタスクは、グループフェアネスの制約を満たすために、実用性を最大化するために一連のアイテムをランク付けするよう要求する。 近年の研究では、品物の効用の不確かさが不公平の原因となっている。 我々は,各アウトプットランキングがグループフェアであることを保証しながら,個別のフェア分布からランキングを抽出する効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-21T01:26:34Z)
• FaiREE: Fair Classification with Finite-Sample and Distribution-Free Guarantee [40.10641140860374]
  FaiREE は群フェアネス制約を有限サンプルと分布自由な理論保証で満たす公平な分類アルゴリズムである。 FaiREEは最先端のアルゴリズムよりも優れた性能を示した。
  論文  参考訳（メタデータ） (2022-11-28T05:16:20Z)
• Robust Allocations with Diversity Constraints [65.3799850959513]
  エージェント値の積を最大化するナッシュ福祉規則は,多様性の制約が導入されたとき,一意にロバストな位置にあることを示す。 また, ナッシュ・ウェルズによる保証は, 広く研究されているアロケーション・ルールのクラスにおいて, ほぼ最適であることを示す。
  論文  参考訳（メタデータ） (2021-09-30T11:09:31Z)
• Supervised Bayesian Specification Inference from Demonstrations [11.855400596862275]
  本稿では,時間論理式としてタスク仕様を推論する確率モデルを提案する。 提案手法は,提案仕様と基礎的真理との間に90%以上の類似性を観測し,提案手法の有効性を実証する。
  論文  参考訳（メタデータ） (2021-07-06T21:16:37Z)
• Multi-Agent Reinforcement Learning with Temporal Logic Specifications [65.79056365594654]
  本研究では,時間論理仕様を満たすための学習課題を,未知の環境下でエージェントのグループで検討する。 我々は、時間論理仕様のための最初のマルチエージェント強化学習手法を開発した。 主アルゴリズムの正確性と収束性を保証する。
  論文  参考訳（メタデータ） (2021-02-01T01:13:03Z)
• From Matching with Diversity Constraints to Matching with Regional Quotas [51.33676030875284]
  分布制約に適合する2つの重要な公理の間の公式な関係を示す。 1)に対する実現可能かつ安定な結果が存在するかどうかを確認することはNP完全であることを示す。 病院医師と地域基準との整合性に関するさらなる発展が,学校選択と多様性の両立につながると結論づける。
  論文  参考訳（メタデータ） (2020-02-17T02:51:46Z)

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

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