Temporal Fair Division of Indivisible Items

• URL: http://arxiv.org/abs/2410.14593v1
• Date: Fri, 18 Oct 2024 16:43:36 GMT
• Title: Temporal Fair Division of Indivisible Items
• Authors: Edith Elkind, Alexander Lam, Mohamad Latifian, Tzeh Yuan Neoh, Nicholas Teh,
• Abstract summary: 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. We aim to ensure that the cumulative allocation at each round satisfies approximate temporal envy-freeness up to one item (TEF1)
• Score: 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.

Related papers

• Online Combinatorial Allocations and Auctions with Few Samples [9.675397292814122]
  This paper investigates the feasibility of achieving O(1)-competitive algorithms under the realistic constraint of having access to only a limited number of samples from the underlying bidder distributions. Our first main contribution shows that a mere single sample from each bidder distribution is sufficient to yield an O(1)-competitive algorithm for submodular/XOS valuations.
  arXiv  Detail & Related papers  (2024-09-17T11:43:55Z)
• Local-Data-Hiding and Causal Inseparability: Probing Indefinite Causal Structures with Cryptographic Primitives [0.0]
  Recent studies suggest the possibility of indefiniteness in causal structure, which emerges as a novel information primitive. We show that agents embedded in an indefinite causal structure can outperform their counterparts operating in a definite causal background. We report an intriguing super-activation phenomenon, where two quantum processes, each individually not useful for the LBH task, become useful when used together.
  arXiv  Detail & Related papers  (2024-07-30T04:54:03Z)
• Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
  We consider a problem where an auctioneer sells an indivisible good to groups of buyers in every round, for a total of $T$ rounds. The auctioneer aims to maximize their discounted overall revenue while adhering to a fairness constraint that guarantees a minimum average allocation for each group.
  arXiv  Detail & Related papers  (2024-05-31T19:26:05Z)
• Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
  Longtailed distributions frequently emerge in real-world data, where a large number of minority categories contain a limited number of samples. Recent investigations have revealed that supervised contrastive learning exhibits promising potential in alleviating the data imbalance. We propose a novel probabilistic contrastive (ProCo) learning algorithm that estimates the data distribution of the samples from each class in the feature space.
  arXiv  Detail & Related papers  (2024-03-11T13:44:49Z)
• Sampling Individually-Fair Rankings that are Always Group Fair [9.333939443470944]
  A fair ranking task asks to rank a set of items to maximize utility subject to satisfying group-fairness constraints. Recent works identify uncertainty in the utilities of items as a primary cause of unfairness. We give an efficient algorithm that samples rankings from an individually-fair distribution while ensuring that every output ranking is group fair.
  arXiv  Detail & Related papers  (2023-06-21T01:26:34Z)
• FaiREE: Fair Classification with Finite-Sample and Distribution-Free Guarantee [40.10641140860374]
  FaiREE is a fair classification algorithm that can satisfy group fairness constraints with finite-sample and distribution-free theoretical guarantees. FaiREE is shown to have favorable performance over state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2022-11-28T05:16:20Z)
• Robust Allocations with Diversity Constraints [65.3799850959513]
  We show that the Nash Welfare rule that maximizes product of agent values is uniquely positioned to be robust when diversity constraints are introduced. We also show that the guarantees achieved by Nash Welfare are nearly optimal within a widely studied class of allocation rules.
  arXiv  Detail & Related papers  (2021-09-30T11:09:31Z)
• Supervised Bayesian Specification Inference from Demonstrations [11.855400596862275]
  We present a probabilistic model for inferring task specification as a temporal logic formula. We demonstrate the efficacy of our model for inferring specifications, with over 90% similarity observed between the inferred specification and the ground truth.
  arXiv  Detail & Related papers  (2021-07-06T21:16:37Z)
• Multi-Agent Reinforcement Learning with Temporal Logic Specifications [65.79056365594654]
  We study the problem of learning to satisfy temporal logic specifications with a group of agents in an unknown environment. We develop the first multi-agent reinforcement learning technique for temporal logic specifications. We provide correctness and convergence guarantees for our main algorithm.
  arXiv  Detail & Related papers  (2021-02-01T01:13:03Z)
• From Matching with Diversity Constraints to Matching with Regional Quotas [51.33676030875284]
  We present a formal connection between two important axioms on matching with distributional constraints. We show that it is NP-complete to check whether a feasible and stable outcome for (1) exists. We conclude that further developments on aspects of hospital-doctor matching with regional quotas will result in corresponding school choice with diversity.
  arXiv  Detail & Related papers  (2020-02-17T02:51:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.