From Cognitive Biases to the Communication Complexity of Local Search

24/05/2018 - 12:00

In this talk I will tell you how analyzing economic markets where agents have cognitive biases has lead to a 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.