Amos Fiat (fiat@tau.ac.il)

2nd Semester, 2011/12 - Wednesday 1300-1600, Dan David 106

Template
for scribe notes here.

Register
for scribe notes here.

In
State of Flux:

- Slides 1: Introduction
- Slides 2: Machine scheduling
price of anarchy/stability
- Slides 3: Potential
games/Congestion games
- Slides 4: Robust POA
- Slides 5: Mechanisms,
Arrows Theorem, Gibbard-Satterthwaite, VCG+CPP
- Slides 6: General Mechanisms,
Revelation Principle, Weak Monotonicity
- Slides 7: Revenue
Optimal Auctions

·
Lecture 1 scribe here. Eran Nir
& Yael Amsterdamer

·
Lecture 2 scribe
here. Hadas Zur
& Alon Ardenboim

·
Lecture 3 scribe
here. Nir Shabat
& Erez Shabat

·
Lecture 4 scribe
here. Gil Tamir & Orit Moskovich

·
Lecture 5 scribe
here. Miki Shifman & Eldad Rubinstein

·
Lecture 11 scribe
here. Lucas Majerowicz, Sharon
Kotler Pikaz & Yaron Velner

·
Lecture 13 scribe
here. Alex Fonar & Eyal Dushkin & Slava Novgorodov

Projects:

Alon Ardenboim**:** Smoothness Theorem
for Incomplete Information Games with Altruistic Players, pre project
presentation here

Eyal Dushkin**:**** **Approximate
Equilibria in unweighted
Congestion Games.

Lucas Majerowicz**:**** **Improvements
upon Bitcoin and Red Balloons.

Yael Amsterdamer**:**** **Dominant
Resource Fairness, pre project presentation here

Alex Fonar
& Slava Novgorodov**:**** **Economics of Cookie Matching,
4 node extension here

Eldad Rubinstein**:**** **Communities in Social Networks, Python code here,
pre project presentation here

Erez Shabat: *The nth voter utility in sequential voting with
externalities model*, pre project presentation here

Nir Shabat: *Approximate Revenue Maximization with Multiple Items*,
pre project presentation here

Miki Shifman: *Basic Network Creation Games*, pre project
presentation here.

Yaron Welner: *The Complexity of Alternating Move Games*, pre
project presentation ?.

Itzik Malkiel: *The Price of Anarchy in Network
Creation Games is (Mostly) Constant*, pre project presentation
?.

Choose paper (for purposes of presentation and problems) here.

It seems we’ll have a long long
day of presentations on Wednesday July 4 (US independence day).
If you absolutely cannot make it July 4 we’ll also have a meeting on the
proceeding Friday June 29.

Please let me know who prefers what using this
Doodle form.

**Research Papers to read: **

**All EC-12 papers ****here****.**

**POA: Network Creation Games**

**Basic
Network Creation Games**: Many *many* open
problems,

Noga Alon, Erik D. Demaine,
MohammadTaghi Hajiaghayi,
Tom Leighton

See also:

**The
Price of Anarchy in Network Creation**

Mat´uˇs Mihal´ak and Jan Christoph Schlegel

**Mechanism Design without Money**

**Mechanism
Design on Discrete Structures: **

Elad Dokowy, Michal Feldman, Reshef Meirz,

Ilan Nehamaz

**Voting**

**OPTIMAL SOCIAL
CHOICE FUNCTIONS: A UTILITARIAN VIEW**:

CRAIG BOUTILIER, IOANNIS CARAGIANNIS, SIMI
HABER, TYLER LU, ARIEL D. PROCACCIA, OR SHEFFET

**Sequential
Voting with Externalities: Herding in Social Networks**:

Noga Alon, Moshe Babaioff,
Ron Karidi, Ron Lavi, Moshe
Tennenholtz

**Equilibria**** Notions**

Nicole Immorlica,
Rachel Kranton, Greg Stoddard

**The
Price of Anarchy in Games of Incomplete Information**:

TIM ROUGHGARDEN

**Complexity of Nash and Walras**

**Approximate Pure Nash Equilibria
in Weighted Congestion Games:**

**Existence,
Efficient Computation, and Structure**:

Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, Alexander Skopalik

**FINDING
A WALRASIAN EQUILIBRIUM IS EASY**

FEDERICO ECHENIQUE, ADAM WIERMAN

**Sponsored Search**

**Optimal Bidding in Multi-Item Multi-Slot Sponsored Search**

Vibhanshu Abhishek, Kartik
Hosanagar

**Revenue Maximization (approximately) with Multiple
Items**

**Approximate Revenue Maximization with Multiple**

Sergiu Hart, Noam Nisan

**More approximate Revenue Maximization**

**The Simple Economics of Approximately Optimal Auctions**

Saeed Alaei Hu Fu Nima
Haghpanah Jason Hartline Azarakhsh
Malekian

**Aspects of limited supply**

**Dynamic Pricing with Limited Supply**:

Moshe Babaioff, Shaddin Dughmi, Robert Kleinberg,
Aleksandrs Slivkins

TIM ROUGHGARDEN, INBAL TALGAM-COHEN, QIQI YAN,

**Incentives among Thieves**

Moshe Babaioff, Shahar Dobzinski, Sigal Oren, Aviv Zohar

**Simple
Sybil-Proof Mechanisms for Multi-Level Marketing**:

Fabio Drucker, Lisa
Fleischer

**Truthful Reporting**

**Peer
Prediction without a Common Prior**:

JENS WITKOWSKI, DAVID C. PARKES

**Coalitional Bargaining **

**Coalitional
Bargaining in Networks**:

Th`anh Nguyen

**Cookie Matching (advertising)**

__To match or not to match: Economics of cookie matching in
online __

Arpita Ghosh, Mohammad Mahdian,
R. Preston McAfee, Sergei Vassilvitskii

**Communities in Social Networks**

__Finding Overlapping Communities in Social Networks:
Toward a __

Sanjeev Arora, Rong
Ge†, Sushant Sachdeva, Grant Schoenebeck

**Dominant Resource Fairness**

** Dominant Resource
Fairness: Fair Allocation of Multiple Resource Types**:

Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker, Ion Stoica

**Excellent classes
on similar subjects (unfortunately given elsewhere or the lecturer is
missing/abroad/etc.): **

Constantinos Daskalakis : (Class at MIT, 2011)

Paul W. Goldberg, Liverpool: Introduction to PPAD

Adam Tauman Kalai 2008: Game Theory and Computer Science (Class at Georgia Tech)

Yishay Mansour 2004: Computational Game Theory (Class at TAU)

Yishay Mansour 2006: Computational Game Theory (Class at TAU)

Tim Roughgarden and Jason Hartline 2005: Topics in Algorithmic Game Theory (Class at Stanford)

New: Survey of Algorithmic Game Theory, Tim Roughgarden, Stanford.

Vincent Conitzer 2006: Computational Game Theory and Mechanism Design (Class at Duke)

Michael Kearns, 2003 (Class at Penn)

Eva Tardos, 2004: Algorithmic Game Theory (Class at Cornell)

Joan Feigenbaum, 2006: Economics and Computation (Class at Yale)

David C. Parkes, 2007: Computational Mechanism Design (Class at Harvard)

Noam Nisan, 2007: Foundations of Electronic Commerce (Class at HU)

- The class will cover all or part of the above classes
and chapters from

"THE BOOK": Algorithmic Game Theory, Edited by Nisan, Rounghgarden, Tardos and Vazirani. - Very Important: you must go to
Noam Nisan's homepage and
read everything linked from there.