Uriel Feige

activity

20232026

collaborators

Showing cs.GTShow all

14 papers · 1 filter

cs.GT2026

On MMS allocations with few items

Uriel Feige

We consider the problem of allocating $m$ indivisible items to $n$ agents. For $n \geq 2$ , we define $μ (n)$ as the largest $m$ for which every allocation instance with $n$ agents an…

cs.GT2026

On best of both worlds allocations with subadditive valuations

Uriel Feige

We consider allocation of indivisible goods to agents with equal entitlements and subadditive valuations. As an ex-post fairness notion we consider the maximin share (MMS), and as…

cs.GT2026

A lone divider allocation algorithm with subjective divisibility

Uriel Feige

In the subjective divisibility allocation model, all goods are divisible, every agent $i$ has a non-negative additive valuation function $v_{i}$ , where for some goods $v_{i}$ is additi…

cs.GT2026

Fair Allocation with Optional Selling

Uriel Feige, Yotam Gafni

We consider fair allocation of indivisible goods in a setting in which agents have subjective valuation functions over the set of goods, and in addition, goods may be sold at given…

cs.GT2026

Simultaneous EF1 and approximate MMS allocations for submodular valuations

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…

cs.GT2026

On MMS, APS and XOS

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 allocatio…

cs.GT2026

Truthful-in-Expectation Mechanisms for MMS Approximation

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…

cs.GT2025

The residual maximin share

Uriel Feige

We consider fair allocations of indivisible goods to agents with general monotone valuations. We observe that it is useful to introduce a new share-based fairness notion, the {\em…

cs.GT2025

From multi-allocations to allocations, with subadditive valuations

Uriel Feige

We consider the problem of fair allocation of $m$ indivisible items to $n$ agents with monotone subadditive valuations. For integer $d \geq 2$ , a $d$ -multi-allocation is an allocati…

cs.GT2025

Fair allocations with subadditive and XOS valuations

Uriel Feige, Vadim Grinberg

We consider the problem of fair allocation of $m$ indivisible goods to $n$ agents with either subadditive or XOS valuations, in the arbitrary entitlement case. As fairness notions,…

cs.GT2025

Concentration and maximin fair allocations for subadditive valuations

Uriel Feige, Shengyu Huang

We consider fair allocation of $m$ indivisible items to $n$ agents of equal entitlements, with submodular valuation functions. Previously, Seddighin and Seddighin [{\em Artificial…

cs.GT2024

Low communication protocols for fair allocation of indivisible goods

Uriel Feige

We study the multi-party randomized communication complexity of computing a fair allocation of $m$ indivisible goods to $n < m$ equally entitled agents. We first consider MMS alloc…

cs.GT2024

Share-Based Fairness for Arbitrary Entitlements

Moshe Babaioff, Uriel Feige

We consider the problem of fair allocation of indivisible items to agents that have arbitrary entitlements to the items. Every agent $i$ has a valuation function $v_{i}$ and an entit…

cs.GT2023

The inversion paradox, and classification of fairness notions

Uriel Feige

Several different fairness notions have been introduced in the context of fair allocation of goods. In this manuscript, we compare between some fairness notions that are used in se…