Bay Algorithmic Game Theory Symposium

Bay Algorithmic Game Theory Symposium
Meeting 4: October 12, 2007, 10am-5:30pm, Yahoo!'s Headquarters, 701 First Avenue, Sunnyvale, 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:	Preston McAfee	"Revisiting the Secretary Problem"
11:00-11:30	Talk:	Ilan Kremer	"On Hannan and Blackwell's Approachability and Options - A Game Theoretic Approach for Option Pricing"
11:30-12:00	Mini Talks 1		TBD
12:00-1:30	Lunch (provided)
1:30-2:00	Talk:	Jean Walrand	"Network Neutrality and Provider Investment Incentives"
2:00-2:30	Talk:	Arpita Ghosh	"Charity Auctions on Social Networks"
2:30-3:00	Mini Talks 2		TBD
3:00-4:00	Coffee Break
4:00-4:30	Talk:	John Morgan	"Brand and Price Advertising in Online Markets"
4:30-5:00	Talk:	Jason Hartline	"Implementation and Money Burning"
5:30-7:30	Dinner at local restaurants (not provided).

Abstracts

Arpita Ghosh , Charity Auctions on Social Networks :

We give a mechanism for this setting that raises the largest individually rational contributions given the conditional bids, and analyze the equilibria of this mechanism in the case of linear utilities. We show that if the social network is strongly connected, the mechanism always has an equilibrium that raises the maximum total contribution (which is the contribution computed according to the true utilities); in other words, the price of stability of the game defined by this mechanism is one. Interestingly, although the mechanism is {\em not} dominant strategy truthful (and in fact, truthful reporting need not even be a Nash equilibrium of this game), this result shows that the mechanism always has a full-information equilibrium which achieves the same outcome as in the truthful scenario. Of course, there exist cases where the maximum total contribution even with true utilities is zero: we show that the existence of non-zero equilibria can be characterized exactly in terms of the largest eigenvalue of the utility matrix associated with the social network.

Joint work with Mohammad Mahdian.

Jason Hartline, Implementation and Money Burning :

Joint with Tim Roughgarden

Ilan Kremer, On Hannan and Blackwell's Approachability and Options - A Game Theoretic Approach for Option Pricing :

Joint with Peter M. DeMarzo, and Yishay Mansour

Preston McAfee, Revisiting the Secretary Problem :

The classic results on the secretary problem suggest using 37% of the available candidates for learning about the distribution, and a 37% failure to accept any candidate. Both of these conclusions seem excessive, and amendments in two different environments are presented, connecting optimal search to optimal experimentation. In the first environment, a secretary is hired for the duration of the project; hiring delay reduces the utility of the secretary. In this case 20% of the data is used to learn the distribution, rather than 37%. In the second environment, a common hazard rate (log concavity of one minus the cdf) is imposed; in this case at most 1/Log(n) of n data points are used to learn the distribution. John Morgan, Brand and Price Advertising in Online Markets :

Joint with Michael R. Baye (Indiana University).

Jean Walrand, Network Neutrality and Provider Investment Incentives :

Joint with J. Musacchio (UCSC), G. Schwartz (UCB), and J. Walrand (UCB).

Organizers

Moshe Babaioff	Microsoft Research
Jason Hartline	Microsoft Research
Tim Roughgarden	Stanford U.
Amin Saberi	Stanford U.
Ilya Segal	Stanford U.

Local arrangements are being made by Ofer Mendelevitch and Trina Escartin (Yahoo! Inc.).