Simultaneously Fair Allocation of Indivisible Items Across Multiple Dimensions

• URL: http://arxiv.org/abs/2506.21727v1
• Date: Thu, 26 Jun 2025 19:27:22 GMT
• Title: Simultaneously Fair Allocation of Indivisible Items Across Multiple Dimensions
• Authors: Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin Sanpui,
• Abstract summary: 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.
• Score: 3.8028747063484585
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper explores the fair allocation of indivisible items in a multidimensional setting, motivated by the need to address fairness in complex environments where agents assess bundles according to multiple criteria. Such multidimensional settings are not merely of theoretical interest but are central to many real-world applications. For example, cloud computing resources are evaluated based on multiple criteria such as CPU cores, memory, and network bandwidth. In such cases, traditional one dimensional fairness notions fail to capture fairness across multiple attributes. To address these challenges, we study two relaxed variants of envy-freeness: weak simultaneously envy-free up to c goods (weak sEFc) and strong simultaneously envy-free up to c goods (strong sEFc), which accommodate the multidimensionality of agents' preferences. Under the weak notion, for every pair of agents and for each dimension, any perceived envy can be eliminated by removing, if necessary, a different set of goods from the envied agent's allocation. In contrast, the strong version requires selecting a single set of goods whose removal from the envied bundle simultaneously eliminates envy in every dimension. We provide upper and lower bounds on the relaxation parameter c that guarantee the existence of weak or strong sEFc allocations, where these bounds are independent of the total number of items. In addition, we present algorithms for checking whether a weak or strong sEFc allocation exists. Moreover, we establish NP-hardness results for checking the existence of weak sEF1 and strong sEF1 allocations.

Related papers

• Principled Multimodal Representation Learning [70.60542106731813]
  Multimodal representation learning seeks to create a unified representation space by integrating diverse data modalities.<n>Recent advances have investigated the simultaneous alignment of multiple modalities, yet several challenges remain.<n>We propose Principled Multimodal Representation Learning (PMRL), a novel framework that achieves simultaneous alignment of multiple modalities.
  arXiv  Detail & Related papers  (2025-07-23T09:12:25Z)
• UC-MOA: Utility-Conditioned Multi-Objective Alignment for Distributional Pareto-Optimality [52.49062565901046]
  Reinforcement Learning from Human Feedback (RLHF) has become a cornerstone for aligning large language models with human values.<n>Existing approaches struggle to capture the multi-dimensional, distributional nuances of human preferences.<n>We introduce Utility-Conditioned Multi-Objective Alignment (UC-MOA), a novel framework that overcomes these limitations.
  arXiv  Detail & Related papers  (2025-03-10T09:52:42Z)
• 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)
• Magic Tokens: Select Diverse Tokens for Multi-modal Object Re-Identification [64.36210786350568]
  We propose a novel learning framework named textbfEDITOR to select diverse tokens from vision Transformers for multi-modal object ReID. Our framework can generate more discriminative features for multi-modal object ReID.
  arXiv  Detail & Related papers  (2024-03-15T12:44:35Z)
• Flexible and Robust Counterfactual Explanations with Minimal Satisfiable Perturbations [56.941276017696076]
  We propose a conceptually simple yet effective solution named Counterfactual Explanations with Minimal Satisfiable Perturbations (CEMSP) CEMSP constrains changing values of abnormal features with the help of their semantically meaningful normal ranges. Compared to existing methods, we conduct comprehensive experiments on both synthetic and real-world datasets to demonstrate that our method provides more robust explanations while preserving flexibility.
  arXiv  Detail & Related papers  (2023-09-09T04:05:56Z)
• Doubly Constrained Fair Clustering [11.11449872883085]
  Group Fairness (GF) and Diversity in Center Selection (DS) are two most prominent demographic representation fairness notions in clustering. We show that given a constant approximation algorithm for one constraint (GF or DS only) we can obtain a constant approximation solution that satisfies both constraints simultaneously. We show that both GF and DS are incompatible with a collection of other distance-based fairness notions.
  arXiv  Detail & Related papers  (2023-05-31T01:04:55Z)
• Optimal Condition Training for Target Source Separation [56.86138859538063]
  We propose a new optimal condition training method for single-channel target source separation. We show that the complementary information carried by the diverse semantic concepts significantly helps to disentangle and isolate sources of interest.
  arXiv  Detail & Related papers  (2022-11-11T00:04:55Z)
• 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)
• Probabilistic Serial Mechanism for Multi-Type Resource Allocation [32.93710648011737]
  We show that the existing multi-type probabilistic serial (MPS) mechanism satisfies the stronger efficiency notion of lexi-efficiency. We also prove that MPS can be characterized both by leximin-ptimality and by item-wise ordinal fairness.
  arXiv  Detail & Related papers  (2020-04-25T05:38:06Z)

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.