Bay Algorithmic Game Theory Symposium Meeting 5: April 11, 2008, 10am-5:30pm, Google Inc., 1300 Crittenden Lane, Mountain View, CA 94043

This Meeting: April 11, 2008, 10am-5:30pm, Google Inc., 1300 Crittenden Lane, Mountain View, CA 94043

Previous Meetings: BAGT 1, BAGT 2. BAGT 3. BAGT 4.

Call for Participation

This paper reports the results of an experimental investigation of monotone games with imperfect information. Players are located at the nodes of a network and observe the actions of other players only if they are connected by the network. These games have many sequential equilibria; nonetheless, the behavior of subjects in the laboratory is predictable. The network architecture makes some strategies salient and this in turn makes the subjects' behavior predictable and facilitates coordination on efficient outcomes. In some cases, modal behavior corresponds to the equilibrium strategies.

Joint work with Syngjoo Choi (UCL), Douglas Gale (NYU) and Tom Palfrey (Caltech).

In this talk we explore the connection between differential privacy and mechanism design, the latter interested in the design of algorithms that encourage honest participation of players. Casting privacy as one of many strategic concerns, we see that the guarantees of differential privacy extend more broadly to other forms of strategic play, and the robust privacy guarantees have game-theoretic implications for issues such as truthfulness, coalition-resilience, and repeatability of games. As examples, we present some recent results from the theory of auctions incorporating these results, giving differential privacy guarantees, but also with an increase expected revenue resulting as well.

Joint work with Kunal Talwar.

The existence of a potential function is a sufficient, but not generally necessary, condition for the existence of pure-strategy Nash equilibria.
We consider congestion games in which player payoffs are parameterized by a coalitional value function and prove a converse of sorts: the only value functions that guarantee pure equilibria across all games are those with a potential. We characterize these potentials in terms of weighted Shapley values.

Based on joint work with Ho-Lin Chen and Greg Valiant.

I investigate the procedural complexity of a choice rule as measured by the size of the minimal automaton that implements it. I first identify simple behavioral properties that determine procedural complexity. I then show that any choice rule that is procedurally simpler than utility maximization displays framing effects. Finally, I prove that choice rules that result from an optimal tradeoff between maximizing utility and minimizing procedural complexity are history-dependent satisfying procedures that exhibit primacy and recency effects, as well as a default tendency.

The paper considers the design of Bayesian incentive-compatible mechanisms for general dynamic environments in which agents receive serially correlated private information over time and decisions may be made over time. The private information is assumed independent across agents, and its distribution is allowed to depend on past allocations. We derive a dynamic revenue equivalence result showing that any two mechanisms that implement the same allocation rule must yield the same expected payoffs to the agents and hence the same expected revenue regardless of the transfer scheme and of the information disclosed by the mechanism to the agents. Using this result, the expected profits of an auctioneer are expressed as the expectation of "dynamic virtual surplus," which can be used to characterize inefficiencies arising in profit-maximizing mechanisms. In settings with linear payoffs and autoregressive values, the profit-maximizing mechanism is similar to the efficient mechanism, the only difference being that each agent's bid in each period is "handicapped", with the handicaps fully determined by the agent's first-period report. Applications include a profit-maximizing sequence of auctions when the bidders' values follow an autoregressive process or when the values are refined by consuming objects.

Joint work with Alessandro Pavan and Juuso Toikka.

We consider mechanism design problems in which agents perceive Knightian uncertainty. Uncertainty is formalized using incomplete preferences; in this model individual decisions depend on a set of beliefs, and an action is preferred to another if and only if it has larger expected utility for all beliefs in this set. We consider two natural notions of incentive compatibility in this setting: maximal incentive compatibility requires that no strategy has larger expected utility than truth-telling for all beliefs, while optimal incentive compatibility requires that truth-telling has larger expected utility than all other strategies for all beliefs. In a model with a continuum of types, we show that optimal incentive compatibility is equivalent to ex-post incentive compatibility under fairly general conditions on beliefs. In a model with a discrete type space, we characterize full extraction of rents from private information. We show that full extraction requires sufficient disagreement in beliefs across types for optimal incentive compatible mechanisms. Contrary to the standard Bayesian case, we show that full extraction in optimal incentive compatible mechanisms is not generically possible.

Joint work with G. Lopomo and L. Rigotti.

It is widely believed that the application of VCG to position auctions requires estimates of the clickthrough rates associated with each position. I show that this is not the case: as long as everyone agreeds on the desireability of the different positions, one can devise a mechanism that has the same expected revenue and expected payoffs as VCG without knowing anything about the actual clickthrough rates.

Address
1300 Crittenden Lane
Mountain View, CA 94043
Phone # 650-623-4000
Main Fax # 650-618-1499

Pre-registered attendees should make their way directly to Maxwell Tech Talk on the first floor of 1300 Crittenden. Security personnel at the Northeast entrance of the building will let you into the building. Attendees who have not pre-registered will be able to register in the lobby of 1200 Crittenden and then go to Maxwell Tech Talk. We will put up signs to help the attendees find these locations.

Map: View Map

Directions: How to get to 1300 Crittenden Lane, Mountain View, CA. ?

Driving Directions from the North:
Take 101 South
Exit Rengstorff Ave
Turn Right onto Rengstorff Ave from the off-ramp
Continue onto Amphitheatre Parkway
Turn Left on North Shorline Blvd
Turn Right on Crittenden Lane
Turn Left into the parking lot

Driving Directions from the South:
Take 101 North
Exit Shoreline Blvd
Turn Right onto Shoreline Blvd from the off-ramp
Continue onto Shoreline Blvd
Turn Right on Crittenden Lane
Turn Left into the parking lot

Parking: Please use the parking lot near 1300 Crittenden Lane, Mountain View.

Carpooling: Participants are encouraged to carpool. There is a forum for offering and asking for rides at http://groups.google.com/group/BAGT-rides/. Unless you join the group, your message posts will be delayed until a moderator confirms that they are not spam.

Organizers