Uriel Feige

Uriel Feige, Assaf Fine

There are two common classes of fairness notions that are considered when allocating $m$ indivisible items to $n$ agents of equal entitlements. One is that of share-based fairness notions, with the maximin share (MMS) and its relaxations to $ρ$-MMS being prominent representatives of this class. The other is that of comparison-based fairness notions, with envy-freeness (EF) and its relaxations such as EF1 being prominent representatives of this class. In general, no class offers good guarantees for the other class. In this work, we design allocations that simultaneously satisfy notions from both classes, and specifically, are $ρ$-MMS for constant $ρ$ and EF1 (in fact, also EFL). Such results were previously known when agents have additive valuations, and we prove such results for the more general class of submodular valuations.

Moshe Babaioff, Uriel Feige

We consider fair allocation of a set $M$ of indivisible goods to $n$ equally-entitled agents, with no monetary transfers. Every agent $i$ has a valuation $v_i$ from some given class of valuation functions. A share $s$ is a function that maps a pair $(v_i,n)$ to a value, with the interpretation that if an allocation of $M$ to $n$ agents fails to give agent $i$ a bundle of value at least equal to $s(v_i,n)$, this serves as evidence that the allocation is not fair towards $i$. For such an interpretation to make sense, we would like the share to be feasible, meaning that for any valuations in the class, there is an allocation that gives every agent at least her share. The maximin share was a natural candidate for a feasible share for additive valuations. However, Kurokawa, Procaccia and Wang [2018] show that it is not feasible. We initiate a systematic study of the family of feasible shares. We say that a share is \emph{self maximizing} if truth-telling maximizes the implied guarantee. We show that every feasible share is dominated by some self-maximizing and feasible share. We seek to identify those self-maximizing feasible shares that are polynomial time computable, and offer the highest share values. We show that a SM-dominating feasible share -- one that dominates every self-maximizing (SM) feasible share -- does not exist for additive valuations (and beyond). Consequently, we relax the domination property to that of domination up to a multiplicative factor of $ρ$ (called $ρ$-dominating). For additive valuations we present shares that are feasible, self-maximizing and polynomial-time computable. For $n$ agents we present such a share that is $\frac{2n}{3n-1}$-dominating. For two agents we present such a share that is $(1 - ε)$-dominating. Moreover, for these shares we present poly-time algorithms that compute allocations that give every agent at least her share.

Uriel Feige, Vadim Grinberg

We consider allocations of a set of $m$ indivisible goods to $n$ agents of equal entitlements that have valuations from the class XOS. A previous sequence of works showed allocations that obtain an $α$-approximation for the maximin share (MMS), for values of $α$ that gradually approach $\frac{1}{4}$ from below (the currently known ratio is $\frac{4}{17}$). In this work we attempt to obtain ratios better than $\frac{1}{4}$, and manage to do so for sufficiently large $n$. Our methodology is to first investigate the gap between the anyprice share (APS) and the MMS when all agents have the same XOS valuations, for which we design an allocation algorithm and prove that each agent receives at least $α> \frac{11}{40}$ times the APS. Then, we derive inspiration from this algorithm, and modify it so that it applies also when agents have different XOS valuations. Using this modified version, we show that for some sufficiently large $n_0$, there is an $α$-MMS allocation (in fact, an $α$-APS allocation) for every $n \geq n_0$.

Moshe Babaioff, Uriel Feige, Noam Manaker Morag

We study fair allocation of indivisible goods among strategic agents with additive valuations. Motivated by impossibility results for deterministic truthful mechanisms, we focus on randomized mechanisms that are \emph{Truthful-in-Expectation (TIE)}. From a fairness perspective, we seek to guarantee every agent a large fraction of their \emph{Maximin Share (MMS)} ex-post. Among other results, Bu~and~Tao~[FOCS 2025] presented a TIE mechanism that guarantees $\frac{1}{n}$-MMS ex-post. First, we present an ordinal TIE mechanism that guarantees $\frac{1}{H_n + 2}$-MMS ex-post, where $H_n$ is the $n$-th harmonic number ($H_n \simeq \ln n$). This is nearly best possible for ordinal mechanisms, as even non-truthful ordinal allocation algorithms cannot obtain an approximation better than $\frac{1}{H_n}$. We then show that with just a small amount of additional cardinal information, the ex-post guarantee can be improved to $Ω(\frac{1}{\log\log n})$-MMS, at the cost of relaxing the incentive requirement to $(1-\varepsilon(n))$-TIE for negligible $\varepsilon(n)$. Finally, for two agents, we present a TIE mechanism that is $\frac{2}{3}$-MMS ex-post. All our mechanisms are ex-ante proportional (thus also providing ``Best-of-Both-Worlds'' results) and run in polynomial time. Moreover, all our results extend to the truncated proportional share (TPS), which is at least as large as the MMS. Our two-agent $\frac{2}{3}$-TPS result is best possible for the TPS.

Uriel Feige, Tomer Koren, Moshe Tennenholtz

We consider sequential decision making in a setting where regret is measured with respect to a set of stateful reference policies, and feedback is limited to observing the rewards of the actions performed (the so called "bandit" setting). If either the reference policies are stateless rather than stateful, or the feedback includes the rewards of all actions (the so called "expert" setting), previous work shows that the optimal regret grows like $Θ(\sqrt{T})$ in terms of the number of decision rounds $T$. The difficulty in our setting is that the decision maker unavoidably loses track of the internal states of the reference policies, and thus cannot reliably attribute rewards observed in a certain round to any of the reference policies. In fact, in this setting it is impossible for the algorithm to estimate which policy gives the highest (or even approximately highest) total reward. Nevertheless, we design an algorithm that achieves expected regret that is sublinear in $T$, of the form $O( T/\log^{1/4}{T})$. Our algorithm is based on a certain local repetition lemma that may be of independent interest. We also show that no algorithm can guarantee expected regret better than $O( T/\log^{3/2} T)$.

Uriel Feige

It is a well observed phenomenon that natural images are smooth, in the sense that nearby pixels tend to have similar values. We describe a mathematical model of images that makes no assumptions on the nature of the environment that images depict. It only assumes that images can be taken at different scales (zoom levels). We provide quantitative bounds on the smoothness of a typical image in our model, as a function of the number of available scales. These bounds can serve as a baseline against which to compare the observed smoothness of natural images.