Sina Dehghani

Postdoc

Price of Competition and Dueling Games

  Friday, 03 January 2020
  10:00 - 10:45

Abstract

We study competition in a general framework introduced by Immorlica, Kalai, Lucier, Moitra,
Postlewaite, and Tennenholtz and answer their main open question. Immorlica
et al. considered classic optimization problems in terms of competition and introduced a general
class of games called dueling games. They model this competition as a zero-sum game, where two
players are competing for a user’s satisfaction. In their main and most natural game, the ranking
duel, a user requests a webpage by submitting a query and players output an ordering over all
possible webpages based on the submitted query. The user tends to choose the ordering which
displays her requested webpage in a higher rank. The goal of both players is to maximize the
probability that her ordering beats that of her opponent and gets the user’s attention. Immorlica
et al. show this game directs both players to provide suboptimal search results. However, they
leave the following as their main open question: “does competition between algorithms improve or
degrade expected performance?" In this talk, we resolve
this question for the ranking duel and a more general class of dueling games.

Keywords

zero-sum games price of anarchy price of competition Game theory

Bio

Sina Dehghani is currently a postdoc at Mathematics department in IPM. He received his PhD in computer science from University of Maryland. He works on the boundary of computer science and economics, and on designing and analysis of algorithms and games.