Epilogue

Wow! Conducting the workshop was an exhilarating experience.

Frankly, I was a bit apprehensive at the beginning about the structure and context of the workshop. Game theory is A non-trivial topic originating from economics, while the class was mainly computer science students with one from economics. Moreover, the composition of the class ranged from junior (undergrad, 3rd year) to post-doctoral students. In the end, the five day "crash" workshop on game theory from a computational perspective turned out to be a very rewarding experience. I am very happy to see that all the students who responded to the feedback felt very positively about the workshop's content and delivery.

I will sign off with a note to my workshop students...it was most exciting to meet and get to know all of you. It is really encouraging to see that you were so deeply interested in game theory and like my teaching. Wish all of you good luck and success with your career plans.

For those who are interested to delve further, I encourage to explore topics that we briefly touched on in the workshop, possibly using the "further reading" pointers given in the blog. If you want to contact me with queries related to workshop topics, my contact is given below.

Cheers!

Dr. Prithviraj (Raj) Dasgupta
Director, CMANTIC Lab (http://cmantic.unomaha.edu)
Mutual of Omaha Endowed Associate Professor of Computer Science
University of Nebraska, Omaha
6001 Dodge Street, Omaha, NE 68182, USA

E-mail: pdasgupta-at-unomaha-dot-edu
Website: https://sites.google.com/site/prithvirajdasgupta/

Working Together...

Day 5

Do people and agents always act selfishly, maximizing their own utility? While much of game theory deals with competition between agents assuming selfish behavior, coalition or cooperative game theory looks at forming coalitions or teams of people. In the morning session we reviewed the fundamental concepts of coalition games including their structure, core and Shapley value.

A very lucidly written textbook on coalitional game theory (link to Amazon Website) is Ray: A Game Theoretic Perspective on Coalition Formation

In the afternoon sessions, there were short presentations on a topic related to game theory by students. The list of presentations is below. Presentation slides (combined into one pdf) from some of the students are available here.

Sayantan Sarkar, "User Preference Aggregation using Normal Form Games," 
Srinka Basu, "Graphical Games,"
Sayantan Santra, "Cake Cutting Game,"
Iman Pal, "Pareto Optimality vs. Nash Equilibrium,"
Saptarshi Misra, "Taxation Games,"
Dipyayan Chakraborty, "Games to Graphs" Transition in Quest to Efficiency"
Sujoy Bhore, "Games on Triangulation,"
Raghu Teja B. "Security with Games,"

Mechanism Design...

Day 4

Today we covered an important aspect of game theory called mechanism design - how to design allocation and payment rules for a set of agents that are making a collective choice, while ensuring that the rules guarantee truthful revelation (incentive compatibility or IC) by every agent and  every agent plays an equilibrium strategy (individual rationality or IR). Due to time constraints, we mainly discussed the very fundamental concepts of social choice functions (scf), mechanisms and looked at simple scf-s that satisfy IC and IR along with the Vickrey-Clarkes-Grove or VCG mechanism. In the second half of today's sessions we had a brief discussion on position auctions around Hal Varian's eponymous paper and finally, we discussed an application of auctions in multi-robot task allocation. Relevant slides and pointers are below:

Mechanism Design slides

Hal Varian's paper on Position Auctions (covered partially in class): 
Varian, Hal R., 2007. "Position auctions," International Journal of Industrial Organization, Elsevier, vol. 25(6), pages 1163-1178, December.[pdf]

Related books for further reading (links to Amazon Website):

Krishna: Auction Theory 

Bergman and Morris: Robust Mechanism Design

Mas-Colell, Whinston, Green: Microeconomics Theory (chapters 21, 22 on Mechanism Design) 

More games, more types of games...

Day 3:

Today we plan to cover Bayesian games, repeated games and stochastic games. Finally, we will discuss on graphical games. I will wrap up with some research that we did on using stochastic games and graphical games for information aggregation.

Slides for Bayesian games

Slides from our paper on using partially observable stochastic game (POSG) for distributed information aggregation

Slides from our paper on using graphical games for distributed prediction markets

Digging Deeper...

Day 2

Today we went deeper into exploring some game theory concepts. We started off with revisions to some techniques learned on day 1. We then looked at minmax, maxmin strategies, minmax theorem and derived the solution of a 2-player, zero-sum game as a linear program. As an example, we solved the linear program to get the solution of the matching pennies game. 

In the second half of the workshop, we discussed two major computational techniques to find Nash equilirbria in 2-player, general sum games - the Lemke Howson algorithm and the Support Enumeration Method. We solved an example of finding the Nash equilibrium using the Lemke Howson algorithm using both the graphical or geometric construction and pivoting to solve a system of linear equations. We wrapped up with a brief discussion on extending these two algorithms to n-player, general sum games.

For further readings on these topics, check Chapter 3 of Nisan's Algorithmic Game Theory textbook (Website link under Day 1. Also, there have been two recent papers on using local search techniques for finding Nash equilibria, that are given below. Both these papers should be available on IEEE Xplore. If you are interested in presentation slides of these papers (from our lab's paper reading group presentations), send email to me at pdasgupta-at-unomaha-dot-edu

1. S. Ceppi, N. Gatti, G. Patrini and M. Rocco, "Local Search Methods for Finding a Nash Equilibrium in Two-Player Games" IAT 2010.

2. N. Gatti, G. Patrini, M. Rocco and T. Sandholm "Combining Local Search Techniques and Path Following for Bimatrix Games, UAI 2012.

We're off to a great start...

Day 1:

Very excited to start the workshop on computational aspects of game theory at ISI Kolkata today! Many thanks to Prof. Dipti Prasad Mukherjee, Head, ECSU, ISI Kolkata for helping to organize this workshop. We have about 15 students attending the workshop from different institutes from in and around Kolkata. We started off basic with introductions of everybody and set the objectives and outcomes of the workshop. We then covered basic concepts in game theory - a brief history of game theory, how to represent normal form games, how to solve normal form 2X2 games using Nash equilibrium (pure and mixed strategies) and correlated equilibrium. We solved several examples by hand to illustrate and understand these concepts. We also looked at how to use two software tools - GAMUT, for generating games and Gambit for finding Nash equilibrium and dominated strategies for some classic 2X2 games.

Here are the links to the slides for today's class:
Introduction to game theory, Nash equilibrium
Using Gamut and Gambit

Tomorrow, we will get deeper into solving for Nash equilibrium of larger games using some computational algorithms. Lot's of math tomorrow!

And, as promised, here are links to some game theory texts that I have found helpful over the past years; links are mostly from Amazon's Website:

Economics texts:
Myerson: Game Theory - Analysis of Conflict
Fudenberg and Tirole: Game Theory
Osborne:  An Introduction to Game Theory
Binmore: Playing for Real

Computer Science Texts:
Shoham & Leyton-Brown: Multi-Agent Systems
Nisan: Algorithmic Game Theory [pdf]