Moshe Babaioff

STOC Conference 2025 Conference Paper

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 entitlement b i , where the entitlements sum up to 1. Which allocation should one choose in situations in which agents fail to agree on one acceptable fairness notion? We study this problem in the case in which each agent focuses on the value she gets, and fairness notions are restricted to be share based . A share s is a function that maps every ( v i , b i ) to a value s ( v i , b i ), representing the minimal value i should get, and s is feasible if it is always possible to give every agent i value of at least s ( v i , b i ). Our main result is that for additive valuations over goods, there is an allocation that gives every agent at least half her share value, regardless of which feasible share-based fairness notion the agent wishes to use. Moreover, the ratio of half is best possible. More generally, we provide tight characterizations of what can be achieved, both ex-post (as single allocations) and ex-ante (as expected values of distributions of allocations), both for goods and for chores. We also show that for chores one can achieve the ex-ante and ex-post guarantees simultaneously (a “best of both world” result), whereas for goods one cannot.

AAAI Conference 2021 Conference Paper

Fair and Truthful Mechanisms for Dichotomous Valuations

• Moshe Babaioff
• Tomer Ezra
• Uriel Feige

We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, in which the added value of any item to a set is either 0 or 1, and aim to design truthful allocation mechanisms (without money) that maximize welfare and are fair. For the case that players have submodular valuations with dichotomous marginals, we design such a deterministic truthful allocation mechanism. The allocation output by our mechanism is Lorenz dominating, and consequently satisfies many desired fairness properties, such as being envy-free up to any item (EFX), and maximizing the Nash Social Welfare (NSW). We then show that our mechanism with random priorities is envy-free ex-ante, while having all the above properties expost. Furthermore, we present several impossibility results precluding similar results for the larger class of XOS valuations.

SODA Conference 2020 Conference Paper

Bulow-Klemperer-Style Results for Welfare Maximization in Two-Sided Markets

• Moshe Babaioff
• Kira Goldner
• Yannai A. Gonczarowski

NeurIPS Conference 2017 Conference Paper

Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues

• Noga Alon
• Moshe Babaioff
• Yannai A. Gonczarowski
• Yishay Mansour
• Shay Moran
• Amir Yehudayoff

In this work we derive a variant of the classic Glivenko-Cantelli Theorem, which asserts uniform convergence of the empirical Cumulative Distribution Function (CDF) to the CDF of the underlying distribution. Our variant allows for tighter convergence bounds for extreme values of the CDF. We apply our bound in the context of revenue learning, which is a well-studied problem in economics and algorithmic game theory. We derive sample-complexity bounds on the uniform convergence rate of the empirical revenues to the true revenues, assuming a bound on the k'th moment of the valuations, for any (possibly fractional) k > 1. For uniform convergence in the limit, we give a complete characterization and a zero-one law: if the first moment of the valuations is finite, then uniform convergence almost surely occurs; conversely, if the first moment is infinite, then uniform convergence almost never occurs.

STOC Conference 2017 Conference Paper

The menu-size complexity of revenue approximation

• Moshe Babaioff
• Yannai A. Gonczarowski
• Noam Nisan

We consider a monopolist that is selling n items to a single additive buyer, where the buyer's values for the items are drawn according to independent distributions F 1 , F 2 ,…, F n that possibly have unbounded support. It is well known that - unlike in the single item case - the revenue-optimal auction (a pricing scheme) may be complex, sometimes requiring a continuum of menu entries. It is also known that simple auctions with a finite bounded number of menu entries can extract a constant fraction of the optimal revenue. Nonetheless, the question of the possibility of extracting an arbitrarily high fraction of the optimal revenue via a finite menu size remained open. In this paper, we give an affirmative answer to this open question, showing that for every n and for every ε>0, there exists a complexity bound C = C ( n ,ε) such that auctions of menu size at most C suffice for obtaining a (1-ε) fraction of the optimal revenue from any F 1 ,…, F n . We prove upper and lower bounds on the revenue approximation complexity C ( n ,ε), as well as on the deterministic communication complexity required to run an auction that achieves such an approximation.

FOCS Conference 2014 Conference Paper

A Simple and Approximately Optimal Mechanism for an Additive Buyer

• Moshe Babaioff
• Nicole Immorlica
• Brendan Lucier
• S. Matthew Weinberg

We consider a monopolist seller with n heterogeneous items, facing a single buyer. The buyer hasa value for each item drawn independently according to(non-identical) distributions, and his value for a set ofitems is additive. The seller aims to maximize his revenue. It is known that an optimal mechanism in this setting maybe quite complex, requiring randomization [19] and menusof infinite size [15]. Hart and Nisan [17] have initiated astudy of two very simple pricing schemes for this setting: item pricing, in which each item is priced at its monopolyreserve; and bundle pricing, in which the entire set ofitems is priced and sold as one bundle. Hart and Nisan [17]have shown that neither scheme can guarantee more thana vanishingly small fraction of the optimal revenue. Insharp contrast, we show that for any distributions, thebetter of item and bundle pricing is a constant-factorapproximation to the optimal revenue. We further discussextensions to multiple buyers and to valuations that arecorrelated across items.

SODA Conference 2009 Conference Paper

Secretary problems: weights and discounts

• Moshe Babaioff
• Michael Dinitz
• Anupam Gupta 0001
• Nicole Immorlica
• Kunal Talwar

The classical secretary problem studies the problem of selecting online an element (a “secretary”) with maximum value in a randomly ordered sequence. The difficulty lies in the fact that an element must be either selected or discarded upon its arrival, and this decision is irrevocable. Constant-competitive algorithms are known for the classical secretary problems (see, e. g. , the survey of Freeman [7]) and several variants. We study the following two extensions of the secretary problem: • In the discounted secretary problem, there is a time-dependent “discount” factor d ( t ), and the benefit derived from selecting an element/secretary e at time t is d ( t )· v ( e ). For this problem with arbitrary (not necessarily decreasing) functions d ( t ), we show a constant-competitive algorithm when the expected optimum is known in advance. With no prior knowledge, we exhibit a lower bound of, and give a nearly-matching O (log n )-competitive algorithm. • In the weighted secretary problem, up to K secretaries can be selected; when a secretary is selected (s)he must be irrevocably assigned to one of K positions, with position k having weight w ( k ), and assigning object/secretary e to position k has benefit w ( k ) · v ( e ). The goal is to select secretaries and assign them to positions to maximize Σ e, k w ( k ) · v ( e ) · x ek where x ek is an indicator variable that secretary e is assigned position k. We give constant-competitive algorithms for this problem. Most of these results can also be extended to the matroid secretary case (Babaioff et al. [2]) for a large family of matroids with a constant-factor loss, and an O (log rank) loss for general matroids. These results are based on a reduction from various matroids to partition matroids which present a unified approach to many of the upper bounds of Babaioff et al. These problems have connections to online mechanism design (see, e. g. , Hajiaghayi et al. [9]). All our algorithms are monotone, and hence lead to truthful mechanisms for the corresponding online auction problems.

SODA Conference 2007 Conference Paper

Matroids, secretary problems, and online mechanisms

• Moshe Babaioff
• Nicole Immorlica
• Robert Kleinberg

SODA Conference 2006 Conference Paper

Single-value combinatorial auctions and implementation in undominated strategies

• Moshe Babaioff
• Ron Lavi
• Elan Pavlov

AAAI Conference 2005 Conference Paper

Mechanism Design for Single-Value Domains

• Moshe Babaioff

In “Single-Value domains”, each agent has the same private value for all desired outcomes. We formalize this notion and give new examples for such domains, including a “SAT domain” and a “single-value combinatorial auctions” domain. We study two informational models: where the set of desired outcomes is public information (the “known” case), and where it is private information (the “unknown” case). Under the “known” assumption, we present several truthful approximation mechanisms. Additionally, we suggest a general technique to convert any bitonic approximation algorithm for an unweighted domain (where agent values are either zero or one) to a truthful mechanism, with only a small approximation loss. In contrast, we show that even positive results from the “unknown single minded combinatorial auctions” literature fail to extend to the “unknown” single-value case. We give a characterization of truthfulness in this case, demonstrating that the difference is subtle and surprising.