From Cognitive Biases to the Communication Complexity of Local Search

Shahar Dobzinski - COLLOQUIUM LECTURE

Tuesday, 2.4.2019, 14:30

Room 337 Taub Bld.

In this talk I will tell you how analyzing economic markets where agents have cognitive
biases has led to better understanding of the communication complexity of local search
procedures.
We begin the talk with studying 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, we
show how cognitive biases can sometimes be harnessed to improve the outcome.
Specifically, we study Walrasian equilibria in combinatorial markets. It is well known
that a Walrasian equilibrium exists 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 here shows that when the valuations are submodular even a mild level of
endowment effect suffices to guarantee the existence of Walrasian equilibrium. In fact,
we show that in contrast to Walrasian equilibria with standard utility maximizers
bidders -- in which the equilibrium allocation must be a global optimum -- when bidders
exhibit endowment effect any local optimum can be an equilibrium allocation.
This raises the natural question of understanding the complexity of computing a local
maximum in combinatorial markets. We reduce it to the following communication variant
of local search: there is some fixed, commonly known graph G. Alice holds f_A and Bob
holds f_B, both are functions that specify a value for each vertex. The goal is to find
a local maximum of f_A+f_B, i.e., a vertex v for which f_A(v)+f_B(v) >= f_A(u)+f_B(u)
for every neighbor u of v. We prove that finding a local maximum requires polynomial
(in the number of vertices) bits of communication.
Based on joint works with Moshe Babaioff, Yakov Babichenko, Noam Nisan, and Sigal Oren.