News Archives

[Colloquium] Fear in Mediation, Exploiting the Windfall of Malice

October 9, 2009

Watch Colloquium: 

Quicktime file(390 MB)
AVI file (511 MB)


  • Date: Friday, October 9th, 2009 
  • Time: 12 pm — 12:50 pm 
  • Place: Centennial Engineering Center, Room 1041

Jared Saia 
Associate Professor
Department of Computer Science University of New Mexico

Abstract: In this talk, we consider a problem at the intersection of game theory and algorithms. Recent results show that the existence of malicious players in a game can, somewhat surprisingly, actually improve social welfare. This phenomena has been called the “windfall of malice”. We ask: “Is it possible to achieve the windfall of malice, even without the actual existence of malicious players?” Surprisingly, we are able to show, that in some cases, the answer is yes. How can we achieve the beneficial impact of malicious players without their actual presence? Our approach is based on the concept of a mediator. Informally, a mediator is a trusted third party that suggests actions to each player. The players retain free will and can ignore the mediator’s suggestions. The mediator proposes actions privately to each player, but the algorithm the mediator uses to decide what to propose is public knowledge. Surprisingly, it is possible to simulate a mediator, without the need of a trusted third party, through the technique of “cheap talk”. This technique also applies to our own approach.

My talk will describe three results. First, we introduce a general method for designing mediators that is inspired by careful study of the windfall of malice effect. Second, we show the applicability of our approach by using it to design mediators for two particular games. Finally, we show the limits of our technique by proving an impossibility result that shows that for a large class of games, no mediator will improve the social welfare over the best Nash Equilibria.

Bio: Jared Saia is an Associate Professor at the University of New Mexico. His broad research interests are in theory and algorithms with a focus on designing distributed algorithms that are robust against a computationally unbounded adversary. He is the recipient of several grants and awards including an NSF CAREER award and School of Engineering Faculty Research Excellence award.