Search Mailing List Archives
[theory-seminar] Theory Seminar (10/8): Shahar Dobzinski
ofirgeri at stanford.edu
Fri Oct 5 18:18:23 PDT 2018
On Monday (10/8) Shahar Dobzinski from Weizmann will give a theory seminar talk: From Cognitive Biases to the Communication Complexity of Local Search (abstract below). The talk will be at 3:00 PM in Gates 463A.
Please note the non-standard day for the talk. We will have another theory seminar at a non-standard time next week: Juba Ziani will be speaking on Thursday (10/11) at 4:15 PM (and there will be no talk on Friday).
For the snacks, if anyone has any restrictions/allergies (or requests), please let me know.
Hope to see you there!
>From Cognitive Biases to the Communication Complexity of Local Search
Speaker: Shahar Dobzinski (Weizmann)
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 Walrsian 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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the theory-seminar