Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division

• URL: http://arxiv.org/abs/2507.14957v2
• Date: Wed, 30 Jul 2025 16:51:28 GMT
• Title: Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division
• Authors: Jarosław Byrka, Franciszek Malinka, Tomasz Ponitka,
• Abstract summary: We prove existence of fair allocations for three important special cases.<n>We show that EFX allocations exist for personalized bivalued valuations.<n>We also prove that PMMS allocations exist for binary-valued MMS-feasible valuations.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the fair division of indivisible items and provide new insights into the EFX problem, which is widely regarded as the central open question in fair division, and the PMMS problem, a strictly stronger variant of EFX. Our first result constructs a three-agent instance with two monotone valuations and one additive valuation in which no PMMS allocation exists. Since EFX allocations are known to exist under these assumptions, this establishes a formal separation between EFX and PMMS. We prove existence of fair allocations for three important special cases. We show that EFX allocations exist for personalized bivalued valuations, where for each agent $i$ there exist values $a_i > b_i$ such that agent $i$ assigns value $v_i(\{g\}) \in \{a_i, b_i\}$ to each good $g$. We establish an analogous existence result for PMMS allocations when $a_i$ is divisible by $b_i$. We also prove that PMMS allocations exist for binary-valued MMS-feasible valuations, where each bundle $S$ has value $v_i(S) \in \{0, 1\}$. Notably, this result holds even without assuming monotonicity of valuations and thus applies to the fair division of chores and mixed manna. Finally, we study a class of valuations called pair-demand valuations, which extend the well-studied unit-demand valuations to the case where each agent derives value from at most two items, and we show that PMMS allocations exist in this setting. Our proofs are constructive, and we provide polynomial-time algorithms for all three existence results.

Related papers

• Online Fair Division for Personalized $2$-Value Instances [51.278096593080456]
  We study an online fair division setting, where goods arrive one at a time and there is a fixed set of $n$ agents.<n>Once a good appears, the value each agent has for it is revealed and it must be allocated immediately and irrevocably to one of the agents.<n>We show how to obtain worst case guarantees with respect to well-known fairness notions.
  arXiv  Detail & Related papers  (2025-05-28T09:48:16Z)
• MM-IFEngine: Towards Multimodal Instruction Following [85.90027280653925]
  We present MM-IFEngine, a pipeline to generate high-quality image-instruction pairs.<n> MM-IFInstruct-23k is suitable forSupervised Fine-Tuning (SFT) and extended as MM-IFDPO-23k for Direct Preference Optimization (DPO)<n>We conduct SFT and DPO experiments and demonstrate that fine-tuning MLLMs on MM-IFInstruct-23k and MM-IFDPO-23k achieves notable gains on various IF benchmarks.
  arXiv  Detail & Related papers  (2025-04-10T17:59:12Z)
• Understanding EFX Allocations: Counting and Variants [0.8287206589886881]
  Envy-freeness up to any good (EFX) is a popular and important fairness property in the fair allocation of indivisible goods.<n>We argue that this approach may yield valuable insights into the existence and computation of EFX allocations.
  arXiv  Detail & Related papers  (2025-04-04T21:36:09Z)
• Benchmarking Multi-modal Semantic Segmentation under Sensor Failures: Missing and Noisy Modality Robustness [61.87055159919641]
  Multi-modal semantic segmentation (MMSS) addresses the limitations of single-modality data by integrating complementary information across modalities.<n>Despite notable progress, a significant gap persists between research and real-world deployment due to variability and uncertainty in multi-modal data quality.<n>We introduce a robustness benchmark that evaluates MMSS models under three scenarios: Entire-Missing Modality (EMM), Random-Missing Modality (RMM), and Noisy Modality (NM)
  arXiv  Detail & Related papers  (2025-03-24T08:46:52Z)
• FinTSB: A Comprehensive and Practical Benchmark for Financial Time Series Forecasting [58.70072722290475]
  Financial time series (FinTS) record the behavior of human-brain-augmented decision-making.<n>FinTSB is a comprehensive and practical benchmark for financial time series forecasting.
  arXiv  Detail & Related papers  (2025-02-26T05:19:16Z)
• Pushing the Frontier on Approximate EFX Allocations [14.101164748526159]
  We study the problem of allocating a set of indivisible goods to a set of agents with additive valuation functions.<n>We get existence results for strict generalizations of the settings for which exact EFX allocations are known to exist.<n>Our results push the emphfrontier of existence and computation of approximate EFX allocations.
  arXiv  Detail & Related papers  (2024-06-18T09:01:37Z)
• Mind the Gap: A Causal Perspective on Bias Amplification in Prediction & Decision-Making [58.06306331390586]
  We introduce the notion of a margin complement, which measures how much a prediction score $S$ changes due to a thresholding operation. We show that under suitable causal assumptions, the influences of $X$ on the prediction score $S$ are equal to the influences of $X$ on the true outcome $Y$.
  arXiv  Detail & Related papers  (2024-05-24T11:22:19Z)
• EFX Allocations Exist for Binary Valuations [0.0]
  We study the fair division problem and the existence of allocations satisfying the fairness criterion envy-freeness up to any item (EFX) By using completely different techniques, we extend this existence to general binary valuations that are not necessarily submodular. We present a time algorithm for computing an EFX allocation.
  arXiv  Detail & Related papers  (2023-08-10T11:28:31Z)
• Dividing Good and Better Items Among Agents with Bivalued Submodular Valuations [20.774185319381985]
  We study the problem of fairly allocating a set of indivisible goods among agents with bivalued submodular valuations. We show that neither the leximin nor the MNW allocation is guaranteed to be envy free up to one good.
  arXiv  Detail & Related papers  (2023-02-06T19:41:28Z)
• Consistent Structured Prediction with Max-Min Margin Markov Networks [84.60515484036239]
  Max-margin methods for binary classification have been extended to the structured prediction setting under the name of max-margin Markov networks ($M3N$) We overcome such limitations by defining the learning problem in terms of a "max-min" margin formulation, naming the resulting method max-min margin Markov networks ($M4N$) Experiments on multi-class classification, ordinal regression, sequence prediction and ranking demonstrate the effectiveness of the proposed method.
  arXiv  Detail & Related papers  (2020-07-02T10:48:42Z)

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.