Bay Algorithmic Game Theory Symposium

Bay Algorithmic Game Theory Symposium
Meeting 3: April 20, 2007, 10am-5:30pm, Room 101, Allen Center for Integrated Systems, Stanford U.

[Home] [Schedule] [Abstracts] [Organizers] [Next Meeting]

[BAGT 1] [BAGT 2] [BAGT 3] [BAGT 4] [BAGT 5]

Schedule

10:00-10:30	Arrivals, Registration, Coffee, and Breakfast
10:30-11:00	Talk:	Constantinos Daskalakis	"Computing Approximate Equilibrium Points"
11:00-11:30	Talk:	Adam Szeidl	"Optimal Risksharing Contracts in Social Networks"
11:30-12:00	Talk:	Gagan Aggarwal	"Position-based Keyword Auctions"
12:00-1:30	Lunch (provided)
1:30-2:00	Talk:	Michael Ostrovsky	"Stability in Supply Chain Networks"
2:00-2:30	Talk:	Yoav Shoham	"Pushing the envelope: New research topics at the interface of computer science and game theory"
2:30-3:00	Mini Talks		Kenneth Judd, Hamid Nazerzadeh, Mukund Sundararajan, and Kunal Talwar
3:00-4:00	Coffee Break
4:00-4:30	Talk:	Mohammad Mahdian	"The role of compatibility in the diffusion of technologies in social networks"
4:30-5:00	Talk:	Paul Milgrom	"Incentives in Core-Selecting Mechanisms"
5:30-7:30	Dinner at local restaurants (not provided).

Abstracts

Gagan Aggarwal, "Position-based keyword auctions" [ppt]:

Based on joint work with Jon Feldman and S. Muthukrishnan.

Konstantinos Daskalakis, "Computing Approximate Equilibrium Points" [ppt]:

In view of the recent hardness results for mixed Nash equilibria, there has been increased interest in computing approximate equilibrium points, albeit progress has been slow. We will present recent developments on the subject, in particular algorithms which achieve constant factor approximations for 2-player games. Next, we will consider a very natural and important class of games, the anonymous games, in which, like in the stock market, a player is oblivious to the identities of the other players. These games or variants are often appealing models for games of many players even so because the description size that they require is polynomial in the number of players -as opposed to exponential that a normal form game would require. We will present a polynomial time approximation scheme for the anonymous setting. Mohammad Mahdian, "The role of compatibility in the diffusion of technologies in social networks" [ppt]:

Our approach builds on work on the diffusion of innovations in the economics literature, which seeks to model how a new technology A might spread through a social network of individuals who are currently users of technology B. We consider several ways of capturing the compatibility of A and B, focusing primarily on a model in which users can choose to adopt A, adopt B, or - at an extra cost - adopt both A and B. We characterize how the ability of A to spread depends on both its quality relative to B, and also this additional cost of adopting both, and find some surprising non-monotonicity properties in the dependence on these parameters: in some cases, for one technology to survive the introduction of another, the cost of adopting both technologies must be balanced within a narrow, intermediate range. We also extend the framework to the case of multiple technologies, where we find that a simple model captures the phenomenon of two firms adopting a limited "strategic alliance" to defend against a new, third technology.

Joint work with Jon Kleinberg, Nicole Immorlica, and Tom Wexler.

Paul Milgrom, "Incentives in Core-Selecting Mechanisms" [pdf]:

A "core-selecting auction mechanism" is a direct mechanism for a multi-item allocation problem that selects a core allocation with respect to the bidders' reported values and the auctioneer's exogenously given preferences. For every profile of others' reports, a bidder has a best reply that is a truncation report. For every "bidder optimal" core imputation, there exists a profile of truncation reports that is a full-information Nash equilibrium for every core-selecting auction with those payoffs. Among core-selecting auctions, the incentives to deviate from truthful reporting are minimal at every preference profile if and only if the auction always selects a bidder optimal allocation with respect to the reported preferences. Finally, a core-selecting auction that selects a minimum revenue core allocation is a bidder optimal auction and make the seller's revenue a non-decreasing function of the bids, which eliminates distortions that can otherwise occur in the process of bidder application and qualification. All these results have analogues in two-sided matching theory. Michael Ostrovsky, "Stability in Supply Chain Networks" [pdf]:

I present a theory of matching in vertical networks, generalizing the theory of matching in two-sided markets. I provide sufficient conditions guaranteeing the existence of stable networks and describe an algorithm for finding one of them. This network has a special property: it is the most preferred stable network for the agents on the "upstream" end of an industry and the least preferred one for the agents on the "downstream" end. A similar algorithm finds a network with the opposite properties. I describe how the welfare of agents in these networks changes when other agents are added to the industry. Yoav Shoham, "Pushing the envelope: New research topics at the interface of computer science and game theory" [ppt]:

For all the recent interest in game theory within computer science, the work to date has concentrated fairly narrowly. There have been three primary areas of concentration: (a) mechanism design, and auctions as a special case, (b) computational complexity of, and algorithms for, computing Nash equilibria and other solution concepts, and (c) multi-agent learning. I will try to make two points in the talk. (a) Even within the confines of these topics, there may be an overemphasis of equilibrium concepts. (b) There are several other areas that offer no less exciting opportunities. These include, but are not limited to, behavioral mechanism design, group decision making, rational programming, and programmatic rationality. Adam Szeidl, "Optimal Risksharing Contracts in Social Networks" [pdf]:

Joint paper with Attila Ambrus and Markus Mobius.

Organizers

Moshe Babaioff	UC Berkeley
Jason Hartline	Microsoft Research
Tim Roughgarden	Stanford U.
Ilya Segal	Stanford U.