19 November 2010, Computational Social Choice Seminar, Stefan Minica

Abstract

Rational interaction in social contexts is a ubiquitous phenomenon in our highly, and increasingly, connected world. Finding solutions in such scenarios becomes even more relevant when agents are competing for, and depleting, scarce or limited resources. In this context the location game (LG) is a paradigmatic example that has a simple formal representation and is relevant for a wide range of practical applications such as over-fishing the oceans, overloading communication networks, deciding on an optimal positioning on open markets or inside a spectrum of political preferences, and so on. In this talk I will discuss the Location Game played on a line. I will give a characterization of Nash equilibria with pure strategies (NE) in LG using the local properties of the game. Next, I will use an argument based on queries to an oracle of local properties to analyze the computational complexity of finding NE in LG. I will also present and discuss implementation tools used in the process.

For more information, see http://www.illc.uva.nl/~ulle/seminar/ or contact Ulle Endriss (ulle.endriss at uva.nl).