
Bay Algorithmic Game Theory Symposium
Meeting 4: October 12, 2007, 10am5: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
Abstracts
Arpita Ghosh , Charity Auctions on Social Networks :
Charitable giving is influenced by many social, psychological, and
economic factors. One common way to encourage individuals to donate
to charities is by offering to match their contribution (often by
their employer or by the government). Conitzer and Sandholm introduced the idea of
using auctions to allow individuals to offer to match the contribution of others.
We explore this idea in a social network setting, where individuals
care about the contribution of their neighbors, and are allowed to
specify contributions that are conditional on the contribution of
their neighbors.
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
fullinformation 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 nonzero 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 :
Ilan Kremer, On Hannan and Blackwell's Approachability and Options  A Game Theoretic Approach for Option Pricing :
We study the link between the game theoretic notion of approachability or "regret minimization" and robust option pricing. We demonstrate how trading strategies that are based on approachability and minimize regret over finite horizon also imply robust upper bounds for the prices of European call options. These bounds are based on no arbitrage and are robust in that they require only minimal assumptions regarding the stock price process. We then focus on the optimal bounds and solve for the optimal volatilitybased bounds in closedform, which in turn implies the optimal regretminimizing trading strategy. The bounds we obtain seem to be empirically relevant as they resemble option price patterns observed in practice.
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 :
Jean Walrand, Network Neutrality and Provider Investment Incentives :
This talk develops and analyzes a game theoretic model to study how the network regime (neutral or
nonneutral) affects provider investment incentives, network quality and user prices. We formulate the
conditions under which a nonneutral network is more favorable for providers and users. Our results
indicate that the nonneutral regime is more favorable when the ratio between parameters characterizing
advertising rates and user price sensitivity is either low or high. When the ratio is in the intermediate
range, the neutral regime can be preferable (in terms of social welfare). The degree by which the neutral
regime is preferable increases with the number of transit providers.
Joint with J. Musacchio (UCSC), G. Schwartz (UCB), and J. Walrand (UCB).
Organizers
Local arrangements are being made by Ofer Mendelevitch and Trina Escartin (Yahoo! Inc.).