The Hebrew University of Jerusalem Einstein Institute of Mathematics		The Hebrew University of Jerusalem The Rachel and Selim Benin School of Computer Science & Engineering
Center for Theoretical Computer Science and Discrete Mathematics

Lectures:      (Poster)

1. Network Games and the Price of Anarchy or Stability
   Sunday, May 23rd, 16:15-18:00    (light refreshments at 16:00)
   Eilat Hall, Feldman Building (2nd floor)

2. Price of Anarchy in Adword Auctions
   Monday, May 24th, 11:00-13:00
   Room 201, Ross Building (Engineering and Computer Science)

3. Quality of Learning Outcomes
   Wednesday, May 26th, 10:30-12:00
   Room 201, Ross Building (Engineering and Computer Science)

---

Abstracts:

Network Games and the Price of Anarchy or Stability

Network games play a fundamental role in understanding behavior in many domains, ranging from communication networks through markets to social networks. Such networks are used, and also evolve due to selfish behavior of the users and owners. In light of these competing forces, it is surprising how efficient these networks are. It is an exciting challenge to understand the operation and success of these networks in game theoretic terms: what principles of interaction lead selfish participants to form such efficient networks? We study the degradation of quality of solution caused by the selfish behavior of users.

Price of Anarchy in Adword Auctions

Generalized Second Price Auction, also known as Ad Word auction, and its variants have been the main mechanism used by search companies to auction positions for sponsored search links. In this talk we study the social welfare of the Nash equilibria of this game (both in the full information model and in the Bayesian setting) compared to the expected value of the optimal social welfare, and show that under reasonable assumption all Nash equilibria have high social welfare, i.e., the Price of Anarchy is low. Our proof exhibits a combinatorial structure of Nash equilibria and use this structure to bound the price of anarchy.
Joint work with Renato Paes Leme.

Quality of Learning Outcomes

Much of the literature on the price of anarchy studies the quality of Nash equilibria. In this talk we will focus on learning outcomes. We study the quality of outcome of the natural multiplicative-weights learning algorithm in games. Games often have a wide variety of equilibria often with vastly differing social costs. We show that in most classes of games, learning outcomes are no worse than the price of anarchy. In fact, in some classes of games, this natural learning algorithm results in vastly better social welfare than predicted by the price of anarchy.
Joint work with Georgios Piliouras and Bobby Kleinberg.