09:00 - 09:30 Gathering
09:30 - 10:20 Aviv Zohar (Hebrew University)
Economic aspects of the Lightning Network
10:20 - 11:10 Uri Feige (Weizmann)
Mechanism Design with Uncertain Inputs
11:10 - 11:30 Coffee
11:30 - 12:20 Tomer Ezra (Tel Aviv University)
Complement-Free Couples Must Communicate: A Hardness Result for Two-Player Combinatorial Auctions
12:20 - 13:10 Sigal Oren (Ben-Gurion University)
Combinatorial Auctions with Endowment Effect
13:10 - 14:30 Lunch
14:30 - 15:00 Rump session
Karthik C.S., Moran Koren, Priel Levy, Drew Stone
15:00 - 15:50 Reshef Meir (Technion)
Facility Location with Three Agents
15:50 - 16:10 Coffee
16:10 - 17:00 Tim Roughgarden (Columbia University)
The Complexity of Fair Division with Combinatorial Valuations
Tomer Ezra (Tel Aviv University): Complement-Free Couples Must Communicate: A Hardness Result for Two-Player Combinatorial Auctions
We study the communication complexity of welfare maximization in combinatorial auctions with m items and two subadditive bidders. A 1/2-approximation can be guaranteed by a trivial randomized protocol with zero communication, or a trivial deterministic protocol with O(1) communication. We show that outperforming these trivial protocols requires exponential communication, settling an open question of [DobzinskiNS10, Feige09].
Specifically, we show that any (randomized) protocol guaranteeing a (1/2 + 6/logm)-approximation requires communication exponential in m. This is tight even up to lower-order terms: we further present a (1/2+1/O(logm))-approximation in poly(m) communication.
To derive our results, we introduce a new class of subadditive functions that are "far from" fractionally subadditive functions, and may be of independent interest for future works. Beyond our main result, we consider the spectrum of valuations between fractionally-subadditive and subadditive via the MPH hierarchy. Finally, we discuss the implications of our results towards combinatorial auctions with strategic bidders.
Joint work with Michal Feldman, Eric Neyman, Inbal Talgam-Cohen, S. Matthew Weinberg .
Uri Feige (Weizmann): Mechanism Design with Uncertain Inputs
We consider a task of scheduling with a common deadline on a single machine. Every player reports to a scheduler the length of his job and the scheduler needs to finish as many jobs as possible by the deadline. For this simple problem, there is a truthful mechanism that achieves maximum welfare in dominant strategies. The new aspect of our work is that in our setting players are uncertain about their own job lengths, and hence are incapable of providing truthful reports (in the strict sense of the word).
For a probabilistic model for uncertainty we show that even with relatively little uncertainty, no mechanism can guarantee a constant fraction of the maximum welfare. To remedy this situation, we consider a different measure of economic efficiency, based on a notion of a fair share of a player, and design mechanisms that are $\Omega(1)$-fair. In addition to its intrinsic appeal, our notion of fairness implies good approximation of maximum welfare in several cases of interest.
Joint work with Moshe Tennenholtz (STOC 2011 / GEB 2014)
Reshef Meir (Technion): Facility Location with Three Agents
We consider the facility location problem in metric space, focusing on the case of three agents.
We show that selecting the reported location of each agent with probability proportional to the distance between the other two agents results in a mechanism that is strategyproof in expectation, and dominates the random dictator mechanism in terms of utilitarian social welfare. We further improve the upper bound for three agents on a circle to 7/6 (whereas random dictator obtains 4/3 and the previous mechanism obtains 5/4); and provide the first lower bounds for randomized strategyproof facility location, using linear programming.
Finally, we calculate the exact approximation ratio of the (deterministic and strategyproof) mechanism that selects the median on each axis in the plane.
Sigal Oren (Ben-Gurion University): Combinatorial Auctions with Endowment Effect
We consider combinatorial auctions with bidders that exhibit endowment effect. In most of the previous work on cognitive biases in algorithmic game theory (e.g., [Kleinberg and Oren, EC’14] and its follow-ups) the focus was on analyzing the implications and mitigating their negative consequences. In contrast, in this talk we will see that in some cases cognitive biases can be harnessed to obtain better outcomes. Specifically, we discuss Walrasian equilibria in combinatorial markets. It is well known that Walrasian equilibria is guaranteed to exist only in limited settings, e.g., when all valuations are gross substitutes, but fails to exist in more general settings, e.g., when the valuations are submodular.
We consider combinatorial settings in which bidders exhibit the endowment effect, that is, their value for items increases with ownership. Our main result shows that when the valuations are submodular, even a mild degree of endowment effect is sufficient to guarantee the existence of Walrasian equilibria. In fact, we show that in contrast to Walrasian equilibria with standard utility maximizing bidders – in which the equilibrium allocation must be efficient – when bidders exhibit endowment effect any local optimum can be an equilibrium allocation. We also provide lower bounds on the intensity of the endowment effect that the bidders must have in order to guarantee the existence of a Walrasian equilibrium in various settings.
Joint work with Moshe Babaioff and Shahar Dobzinski.
Tim Roughgarden (Columbia University): The Complexity of Fair Division with Combinatorial Valuations
We study the query and communication complexity of fair division with indivisible goods. We consider several notions of fairness (envy-freeness, proportionality, EFX, etc.) and classes of combinatorial valuations (general, subadditive, submodular, etc.). We identify a number of fair division problems that can be solved with polynomial complexity, and prove exponential lower bounds for a number of others.
Joint work with Ben Plaut.
Aviv Zohar (Hebrew University): Economic aspects of the Lightning Network
The lightning network is one of the systems designed for payment processing on top of the Bitcoin network. During the talk, I will overview the general operation of this network and discuss some of our ongoing research into its underlying economic incentives (Based on joint work with Simina Branzei, Erel Segal Halevi, Noa Mark & Yotam Sali).