I will present a concrete model of computation for bipartite matching problems. The model is based on the notion of "demand queries" often considered in the economics-and-computation literature, is of intermediate power between decision trees and communication complexity, and is strong enough as to implement many of the known algorithms for bipartite matching. Improved upper bounds in this model will naturally imply faster general algorithms for bipartite matching, but the concreteness of the model opens the possibility of proving lower bounds. The main result shows that parallel *deterministic* algorithms for approximating a maximum matching are significantly inferior to *randomized* ones. The main open problem is whether a perfect matching can be found in (near-) linear time in this model

In a generalized network design problem, a set of resources are assigned (non-exclusively) to multiple requests. Each request contributes its weight to the resources it uses and the total load on a resource is then translated to the cost it incurs via a resource specific cost function. Motivated by energy efficiency applications, recently, there is a growing interest in (generalized) network design using cost functions that exhibit (dis)economies of scale, namely, cost functions that appear subadditive for small loads and superadditive for larger loads.

In this talk, we discuss a new generic technique that yields improved approximation results for a wide family of requests, including routing requests and various types of Steiner tree and Steiner forest requests in both directed and undirected graphs. Our technique is based on associating each request with a strategic player, transforming the centralized optimization problem into a game, and then, obtaining the desired solution via a best response dynamics. Relying on Roughgarden’s smoothness toolbox (JACM 2015), we show that this inherently decentralized process outperforms the state-of-the-art centralized algorithms, thus demonstrating the possible usefulness of this toolbox in the area of approximation algorithms

Based on a joint work with Shay Kutten, Ron Lavi, and Yangguang Shi.

A main challenge that service providers face when managing service systems is how to generate value and regulate congestion at the same time. We consider service systems in which consumers value time in service and choose for how long to use the service. However, they dislike waiting in queue for the service. Consumers are born according to a Poisson process with a given rate and then decide whether to use the service prior to observing the queue length (unobservable queue). Consumers are heterogeneous in the duration of time they would like to use the service and this is their private information. We start by characterize the first best solution which involves letting some of the consumers use the service for their optimal time while restricting others to use it for a shorter amount of time. We then examine a service provider who may charge a fee for the service and characterize the service provider's optimal mechanism. Finally, we also examine two commonly used tools to control congestion: time limits and price per unit of time in service. We show that charging a price per unit of time is effective because of its superiority in extracting rents from heterogeneous consumers. Time limits reduce waiting times and benefit the service provider, especially when the arrival rate is high (congested service).

Joint work with Pnina Feldman

Understanding the power of truthful, computationally efficient mechanisms is one of the main goals of algorithmic mechanism design. In this talk I will survey the progress made in this front in recent years.

We consider the classic principal-agent model of contract theory [Holmstrom’79], in which a principal designs an outcome-dependent compensation scheme to incentivize an agent to take a costly and unobservable action. When all of the model parameters–including the full distribution over principal rewards resulting from each agent action–are available to the designer in extensive form, an optimal contract can be computed by linear programming. This talk will examine contract theory through the algorithmic lens, presenting two main results: First, if the principal knows only the first moment of each action’s reward distribution, we prove that linear contracts are guaranteed to be worst-case optimal, ranging over all reward distributions consistent with the given moments. This provides a new explanation for the prevalence of this class of simple contracts. Second, we consider a natural class of succinct principal-agent settings, capturing scenarios like a marketing agent whose actions lead to different probabilities of sales of various items. We show how to utilize the succinct structure by an Ellipsoid-based algorithm to obtain a near-optimal contract. We conclude by discussing the possible role of algorithms in future research on contract theory and its applications.

Joint work with Paul Duetting and Tim Roughgarden.

The endowment effect, coined by Nobel Laureate Richard Thaler, posits that people tend to inflate the value of items they own. This bias has been studied mainly using experimental methodology. Recently, Babaioff, Dobzinski and Oren proposed a specific formulation of the endowment effect in combinatorial markets, and showed that the existence of Walrasian equilibrium with respect to the endowed valuations extends from gross substitutes to submodular valuations, but provably fails to extend to XOS valuations.

We propose to harness the endowment effect further. We introduce a principle-based framework that captures a wide range of different formulations of the endowment effect. We equip our framework with a partial order over the different formulations, which ranks them from weak to strong, and provide algorithms for computing endowment equilibria with high welfare for sufficiently strong endowment effects, as well as non-existence results for weaker ones.

Our main results are the following:

(1) For markets with XOS valuations, we provide an algorithm that, for any sufficiently strong endowment effect, given an arbitrary initial allocation $S$, returns an endowment equilibrium with at least as much welfare as in $S$. Moreover, every such endowment equilibrium gives at least half of the optimal social welfare.

(2) For markets with arbitrary valuations, we show that bundling leads to a sweeping positive result. In particular, if items can be prepacked into indivisible bundles, we provide an algorithm that, for a wide range of endowment effects, given an initial allocation $S$, computes an endowment equilibrium with at least as much welfare as in $S$. The algorithm runs in poly time with poly many value (resp., demand) queries for submodular (resp., general) valuations.

Joint work with Tomer Ezra and Ophir Friedler.

The increasing reach of algorithmic classification and decision making into our daily lives — from advertising to hiring decisions to incarceration — has given rise to an explosion of research into the ethics embodied by these algorithms; in a word, are they “fair”? But what is fairness? Can we test for it? Can we achieve it? Are there limits?

The burgeoning theoretical study of algorithmic fairness attempts to tackle these challenges. This talk will survey some of this progress, drawing connections to game-theoretic notions of fair division.

Based on joint work with Michael Kim, Aleksandra Korolova and Gal Yona.