Computational Game Theory 2012


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:

 

 

·        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

Games Is (Mostly) Constant

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

 

Striving for Social Status:

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

FOR A FIXED NUMBER OF AGENTS:

FEDERICO ECHENIQUE, ADAM WIERMAN

 

 

Sponsored Search

 

Optimal Bidding in Multi-Item Multi-Slot Sponsored Search

Auctions:

Vibhanshu Abhishek, Kartik Hosanagar

 

Revenue Maximization (approximately) with Multiple Items

 

Approximate Revenue Maximization with Multiple

Items:

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

 

Supply Limiting Mechanisms:

TIM ROUGHGARDEN, INBAL TALGAM-COHEN, QIQI YAN,

 

Incentives among Thieves

 

On Bitcoin and Red Balloons:

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

advertising:

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

 

Communities in Social Networks

 

Finding Overlapping Communities in Social Networks: Toward a

Rigorous Approach:

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)