Understanding EFX Allocations: Counting and Variants
Envy-freeness up to any good (EFX) is a popular and important fairness property in the fair allocation of indivisible goods, of which its existence in general is still an open question. In this work, we investigate the problem of determining the minimum number of EFX allocations for a given instance, arguing that this approach may yield valuable insights into the existence and computation of EFX allocations. We focus on restricted instances where the number of goods slightly exceeds the number of agents, and extend our analysis to weighted EFX (WEFX) and a novel variant of EFX for general monotone valuations, termed EFX+. In doing so, we identify the transition threshold for the existence of allocations satisfying these fairness notions. Notably, we resolve open problems regarding WEFX by proving polynomial-time computability under binary additive valuations, and establishing the first constant-factor approximation for two agents.
Code (0)
등록된 구현이 없습니다.
Tasks
FairnessMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Tree-structured Markov random fields with Poisson marginal distributions
A new family of tree-structured Markov random fields for a vector of discrete counting random variables is introduced. According to the characteristics of the family, the marginal distributions of the Markov random field…
Sequential Fair Resource Allocation under a Markov Decision Process Framework
We study the sequential decision-making problem of allocating a limited resource to agents that reveal their stochastic demands on arrival over a finite horizon. Our goal is to design fair allocation algorithms that exha…
Decision MakingFairnessSequential Decision MakingHomomorphism Expressivity of Spectral Invariant Graph Neural Networks
Graph spectra are an important class of structural features on graphs that have shown promising results in enhancing Graph Neural Networks (GNNs). Despite their widespread practical use, the theoretical understanding of …
Subgraph CountingMVP: Detection of motif-making and -breaking mutations
Background: DNA, RNA, and protein sequence motifs can be recognition sites for biological functions such as regulation, DNA base modification, and molecular binding in general. The gain and loss of such motifs can carry …
VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback
We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. On each round, a mechanism first assigns an allocation each to a set of agents and charges them a pri…