Bay Algorithmic Game Theory Symposium

Bay Algorithmic Game Theory Symposium
Meeting 1: Feb. 17, 2006, 10am-5pm, Building 1, MSR-SVC, 1065 La Avenida, Mountain View, CA.

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

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

Schedule

10:00-10:30	Arrivals, Registration, Coffee, and Breakfast
10:30-11:00	Talk:	Hal Varian	"Position Auctions"
11:00-11:30	Talk:	Ramesh Johari	"Comm. Reqs. of VCG-like Mechs. in Convex Envs."
11:30-12:00	Open Problems Session
12:00-1:30	Lunch (provided)
1:30-2:00	Talk:	Eric Friedman	"On the Manipulation of Ranking and Reputation Systems"
2:00-2:30	Talk:	Kunal Talwar	"Monopolistic pricing, profit extraction, and popping balloons"
2:30-3:00	Open Problems Session
3:00-4:00	Coffee Break
4:00-4:30	Talk:	Ilya Segal	"Communication Costs of Selfishness"
4:30-5:00	Talk:	Moshe Babaioff	"Combinatorial Agency"
5:30-7:30	Dinner at local restaurants (not provided).

Abstracts

Moshe Babaioff, "Combinatorial Agency" [slides]:

combinations

which set of agents

Eric Friedman, "On the Manipulation of Ranking and Reputation Systems" [slides]:

Ranking and reputation systems have become increasingly important, from Google's pagerank to mechanisms for reducing free riding in P2P systems. However, due to user manipulations (such as google bombing and sybil attacks) many of these systems have been significantly compromised. In this talk I will discuss some recent work (theoretical and empirical) on the manipulability of such systems and the potential for making them more robust. Ramesh Johari, "Communication Requirements of VCG-like Mechanisms in Convex Environments" [slides]:

We develop VCG-like mechanisms for resource allocation environments where the players have concave utility functions, and the resource constraints can be represented through convex inequality constraints; multicommodity flow problems are a prime example. Unlike VCG mechanisms that require each player to communicate an entire utility function, our mechanisms only require each player to communicate a single scalar quantity. Despite the limited communication, we establish the existence of an efficient Nash equilibrium. Under some further assumptions, we also establish that all Nash equilibria are efficient. Our approach defines an entire family of resource allocation mechanisms; as a special case, we recover the class of mechanisms recently introduced by Yang and Hajek for a single resource. Ilya Segal, "Communication Costs of Selfishness"

(Joint work with Ronald Fadel)

Kunal Talwar, "Monopolistic pricing, profit extraction and popping balloons"

The Shapley value mechanism can extract the function f(v)=max_i iv_i (assuming the v_i's are sorted in descending order). What other functions can be extracted truthfully? We relate this question to a natural balloon-popping problem. We then show that for a suitably general class of profit extraction mechanisms, the maximum revenue extractable is at most a constant times that of the Shapley value mechanism.

(joint work with Nicole Immorlica, Anna Karlin and Mohammad Mahdian.)

Hal Varian, "Position Auctions" [slides]:

I analyze the equilibria of a game based on the ad auction used by Google and Yahoo. This auction is closely related to the assignment game studied by Shapley-Shubik, Demange-Gale-Sotomayer and Roth-Sotomayer. However, due to the special structure of preferences, the equilibria of the ad auction can be calculated explicitly and some known results can be sharpened. I provide some empirical evidence that the Nash equilibria of the position auction describe the basic properties of the prices observed in Google's ad auction reasonably accurately.

Organizers

Moshe Babaioff	UC Berkeley
Jason Hartline	Microsoft Research
Robert Kleinberg	UC Berkeley
Tim Roughgarden	Stanford U.