We here address the problem of fairly allocating indivisible goods or chores to $n$ agents with \emph{weights} that define their entitlement to the set of indivisible resources. Stemming from well-studied fairness concepts such as envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX) for agents with \textit{equal} entitlements, we present, in this study, the first set of impossibility results alongside algorithmic guarantees for fairness among agents with \textit{unequal} entitlements.

Within this paper, we expand the concept of envy-freeness up to any good or chore to the weighted context (WEFX and XWEF respectively), demonstrating that these allocations are not guaranteed to exist for two or three agents. Despite these negative results, we develop a WEFX procedure for two agents with \emph{integer} weights, and furthermore, we devise an approximate WEFX procedure for two agents with \emph{normalized} weights. We further present a polynomial-time algorithm that guarantees a weighted envy-free allocation up to one chore (1WEF) for any number of agents with additive cost functions. Our work underscores the heightened complexity of the weighted fair division problem when compared to its unweighted counterpart.

Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements

Decision trees are widely used for their low computational cost, good predictive performance, and ability to assess the importance of features. Though often used in practice for feature selection, the theoretical guarantees of these methods are not well understood. We here obtain a tight finite sample bound for the feature selection problem in linear regression using single-depth decision trees. We examine the statistical properties of these ``decision stumps" for the recovery of the $s$ active features from $p$ total features. Our analysis provides tight sample performance guarantees on high-dimensional sparse systems which align with the finite sample bound of $O(s \log p)$ as obtained by Lasso, improving upon previous bounds for both the median and optimal splitting criteria. Our results extend to the non-linear regime as well as arbitrary sub-Gaussian distributions, demonstrating that tree based methods attain strong feature selection properties under a wide variety of settings and further shedding light on the success of these methods in practice. 
  As a byproduct of our analysis, we show that we can provably guarantee recovery even when the number of active features $s$ is unknown, addressing a well-known limitation of previous results.
    We further validate our theoretical results and proof methodology using computational experiments.

Max Springer

2

2

SHORT BIO

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES