Yu Jaijin reports on the GAME 2010 summer school in AGT that was held in Shangai early this month:
The theory group at Fudan University hosted a Summer School on Algorithmic Game Theory (GAME 2010) in Shanghai from July 4th to July 15th. This was a greatly successful event that attracted more than sixty participants from China, Europe, other Asian countries, and the US. Most of them were students, but some postdocs and researchers attended as well. Nine invited speakers gave great lectures about various aspects of algorithmic game theory, and several participants presented their own research results. In addition to the enlightening lectures, the school organized an exciting excursion to EXPO 2010 and a nice banquet in a gorgeous Chinese garden restaurant. The complete schedule can be found at http://www.tcs.fudan.edu.cn/game10/program.html.
The following topics were covered in the summer school:
- Avrim Blum and Rudolf Fleischer started the summer school with an introduction into game theory and mechanism design, introducing the main concepts and giving some first examples of games and mechanisms.
- Andrei Border talked about the fascinating world of computational advertising by presenting some of its key features and comparing it to traditional advertising. His presentation included many vivid examples and figures from real world applications (like retrieving good ads in the sponsored search auction and the guaranteed delivery of display ads), and various kinds of research behind it (IR, optimization, etc.).
- Stefano Leonardi’s lectures were mostly related to the design of approximation algorithms for truthful mechanisms (like cost sharing mechanism). He taught how to adapt classic approximation algorithms to truthful ones in the utilitarian mechanism design, and presented his recent work about Pareto-optimal combinatorial auctions whose motivation came from Google TV ads.
- Kamal Jain first talked about Internet Economics. He believed search engines collected intentions from users and sold them to advertisers, which were on an atomic scale, while in traditional advertising aggregate interests are sold. He then presented two of his interesting recent research results. The first one was how to decide the existence of a matching in some lopsided bipartite graph, coming from the context of matching targets for display ads. The other one was about market equilibria in a market where agents are both consumers and producers of the content that belongs to one of several categories.
- Maria Florina Balcan talked about fundamental connections between learning theory and game theory. She first gave a tutorial about online learning and regret minimization and taught the Weighted Majority Algorithm and its randomized version (RWM). She then showed a simple proof of the famous Minmax Theorem in zero-sum games based on guarantees of the RWM algorithm. She also talked about games with many players games with interesting structure, namely about potential games. In addition to presenting basic properties of such games, she talked about some recent research about leading dynamics to good behavior in games with a huge gap between the quality of the best and the worst Nash equilibrium. For example she showed that in cost sharing games if only a small fraction number of the agents followed the good advice proposed by a central authority, then within polynomialnumber of steps the game will converge to a state with good social welfare. Finally, she also presented recent work about learning submodular functions in a setting similar to the traditional PAC model.
- Avrim Blum gave lectures about game theory, mechanism design, machine learning, and pricing problems. He first introduced the concept of internal/swap regret and showed that if players use no internal-regret strategies, the empirical distribution of the game will be a correlated equilibrium. He then talked about two interesting applications of machine learning techniques for designing incentive compatible mechanisms for revenue maximization in unlimited supply settings. The first one concerned the online digital good auction: how to adapt pricing for a single digital good to achieve performance matching the best fixed price in hindsight. He also showed how to use ideas from machine learning to convert batch optimization algorithms into incentive-compatible mechanisms with performance close to the best pricing function in some class of pricing functions. Finally, we also talked about about some interesting algorithmic pricing problems in this setting as well.
- Eva Tardos’s lectures were mostly related to the price of anarchy. She first gave a very gentle introduction of congestion games in atomic and non-atomic settings. Then she taught a technique called (λ, μ) – smoothness that can prove stronger bounds of PoA for non-atomic games. She also presented the work about some multiplicative update learning process that will converge to a weakly Nash equilibrium in polynomial time. At last she talked about a recent work of PoA in GSP auction. Using some combinatorial structures in the auction, they could show a constant bound of PoA of pure Nash, mixed Nash, and Bayesian-Nash in GSP auctions.
- Xiaotie Deng gave a proof sketch of the celebrated result concerning the PPAD-completeness of finding mixed Nash equilibria in 2-player game. After introducing the PPAD class, he showed the reduction in the following way: 2D Another End of Lines => 2D Sperner Problem => 2D Discrete Fixed Point Problem => 2-player Nash Equilibrium Problem.
- Ning Chen covered several important known results on stable matchings and its Pareto-optimal extensions, including the GS algorithm, the Roth-Vande Vate Algorithm that solved Knuth’s local search problem, and some extensions like having partial orders or ties in the preference lists. Ning Chen and Xiaotie Deng then presented together their recent work about market equilibria in the advertising business. They gave a polynomial time algorithm that found the minimum market equilibrium price where agents had budget constraints.