Simultaneous Envy and Equitability Guarantees

• URL: http://arxiv.org/abs/2608.26410v1
• Date: Wed, 26 Aug 2026 21:23:39 GMT
• Title: Simultaneous Envy and Equitability Guarantees
• Abstract summary: We study the compatibility of two fundamentally different fairness notions: envy-freeness and equitability.<n>For indivisible goods-only and chores-only settings, we study the existence and complexity of simultaneously satisfying their relaxations.
• Score: 33.11344041583124
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent work in fair division has focused on either simultaneously satisfying closely related fairness notions or achieving a single notion across the ex-ante and ex-post worlds. We study the compatibility of two fundamentally different fairness notions: envy-freeness and equitability. For indivisible goods-only and chores-only settings, we study the existence and complexity of simultaneously satisfying their relaxations, revealing sharp contrasts between the two settings. We show that EF1+EQ1 may fail to exist even for normalized, additive valuations. Our main algorithmic result computes an EF1+EQ1 allocation for normalized binary goods with at most seven agents. In sharp contrast, binary chores admit the stronger EFX+EQX guarantee for any number of agents, even without normalization. We further initiate the study of cross-notion ex-ante--ex-post guarantees, asking whether randomized allocations can provide ex-ante guarantees for one notion while preserving ex-post guarantees for another.

Related papers

• SONA: Learning Conditional, Unconditional, and Mismatching-Aware Discriminator [54.562217603802075]
  We introduce Sum of Naturalness and Alignment (SONA), which employs separate projections for naturalness (authenticity) and alignment in the final layer with an inductive bias.<n>Experiments on class-conditional generation tasks show thatSONA achieves superior sample quality and conditional alignment compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2025-10-06T08:26:06Z)
• Simultaneously Fair Allocation of Indivisible Items Across Multiple Dimensions [3.8028747063484585]
  This paper explores the fair allocation of indivisible items in a multidimensional setting.<n>It is motivated by the need to address fairness in complex environments where agents assess bundles according to multiple criteria.<n>Traditional one dimensional fairness notions fail to capture fairness across multiple attributes.
  arXiv  Detail & Related papers  (2025-06-26T19:27:22Z)
• Temporal Fair Division of Indivisible Items [61.235172150247614]
  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)
  arXiv  Detail & Related papers  (2024-10-18T16:43:36Z)
• Equal Opportunity of Coverage in Fair Regression [50.76908018786335]
  We study fair machine learning (ML) under predictive uncertainty to enable reliable and trustworthy decision-making. We propose Equal Opportunity of Coverage (EOC) that aims to achieve two properties: (1) coverage rates for different groups with similar outcomes are close, and (2) the coverage rate for the entire population remains at a predetermined level.
  arXiv  Detail & Related papers  (2023-11-03T21:19:59Z)
• First-Choice Maximality Meets Ex-ante and Ex-post Fairness [33.992491196317744]
  We design randomized mechanisms that satisfy first-choice maximality (FCM), i.e., maximizing the number of agents assigned their first choices. Our mechanisms also provide guarantees of ex-ante and ex-post fairness.
  arXiv  Detail & Related papers  (2023-05-08T09:57:30Z)
• Increasing Fairness via Combination with Learning Guarantees [8.116369626226815]
  We propose a fairness quality measure named 'discriminative risk (DR)' to reflect both individual and group fairness aspects.<n>We investigate its properties and establish the first- and second-order oracle bounds to show that fairness can be boosted via ensemble combination with theoretical learning guarantees.
  arXiv  Detail & Related papers  (2023-01-25T20:31:06Z)
• Practical Approaches for Fair Learning with Multitype and Multivariate Sensitive Attributes [70.6326967720747]
  It is important to guarantee that machine learning algorithms deployed in the real world do not result in unfairness or unintended social consequences. We introduce FairCOCCO, a fairness measure built on cross-covariance operators on reproducing kernel Hilbert Spaces. We empirically demonstrate consistent improvements against state-of-the-art techniques in balancing predictive power and fairness on real-world datasets.
  arXiv  Detail & Related papers  (2022-11-11T11:28:46Z)
• 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)
• Favoring Eagerness for Remaining Items: Achieving Efficient and Fair Assignments [34.62857280111384]
  We propose novel properties of efficiency based on a subtly different notion to favoring higher ranks. Specifically, we propose ex-post favoring-eagerness-for-remaining-items (ep-FERI) and ex-ante favoring-eagerness-for-remaining-items (ea-FERI)
  arXiv  Detail & Related papers  (2021-09-18T07:00:04Z)
• Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness [16.187873844872637]
  We consider the problem of fairly allocating a set of indivisible goods to a set of strategic agents with additive valuation functions. Our main goal is to explore whether there exist mechanisms that have pure Nash equilibria for every instance. We show that the corresponding allocations not only are EFX but also satisfy maximin share fairness, something that is not true for this algorithm in the non-strategic setting!
  arXiv  Detail & Related papers  (2021-09-17T16:57:20Z)

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.