Bay Algorithmic Game Theory Symposium Meeting 6: May 1, 2009, 10am-5:30pm, Sibley Auditorium, Bechtel Engineering Center, UC Berkeley.

This Meeting: May 1, 2009, 10am-5:30pm, Sibley Auditorium, Bechtel Engineering Center, UC Berkeley.

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

Call for Participation

We consider a multi-round auction setting motivated by pay-per-click auctions for Internet advertising. In each round the auctioneer selects an advertiser and shows her ad, which is then either clicked or not. An advertiser derives value from clicks; the value of a click is her private information. Initially, neither the auctioneer nor the advertisers have any information about the likelihood of clicks on the advertisements. The auctioneer's goal is to design a (dominant strategies) truthful mechanism that (approximately) maximizes the social welfare.

If the advertisers bid their true private values, our problem is equivalent to the "multi-armed bandit problem", and thus can be viewed as a strategic version of the latter. In particular, for both problems the quality of an algorithm can be characterized by "regret", the difference in social welfare between the algorithm and the benchmark which always selects the same "best" advertisement. We investigate how the design of multi-armed bandit algorithms is affected by the restriction that the resulting mechanism must be truthful. We find that truthful mechanisms have certain strong structural properties -- essentially, they must separate exploration from exploitation -- and they incur much higher regret than the optimal multi-armed bandit algorithms. Moreover, we provide a truthful mechanism which (essentially) matches our lower bound on regret.

Joint work with Yogi Sharma and Alex Slivkins

We investigate the problem of eliciting probabilistic information regarding a random future event. Specifically, a principal asks an expert to report some given information on the uncertainty of a future event. To incentivize truthful answers, the principal offers a payment, whose amount is a function of the report of the expert and the outcome of the event, that the principal subsequently observes. Elicitation of full distributions was investigated already in the 1950s. More recently we looked at the elicitation of distribution parameters, such as the mean and standard deviation. In our most recent work we looked more generally at eliciting arbitrary predicates on distributions, including in particular eliciting truthful answers to questionnaires on the random event. I will survey this literature, with greater emphasis on the more recent work.

Selective colleges and universities rely heavily on early admissions. They admit early applicants at higher rates, and below the very top tier of schools, make early admission a binding commitment. Early application behavior exhibits distinct sorting patterns. We propose a game-theoretic model that can explain these facts. The key feature of the model is that colleges want to admit students who are enthusiastic about attending, and early admissions programs give students an opportunity to signal this enthusiasm. Lower-ranked schools also have a competitive motive to adopt binding early admissions.

This talk discusses recent results on the computation of game and price equilibria.

Joint work with Costis Daskalakis and Mihalis Yannakakis

Coordination games describe social or economic interactions in which the adoption of a common strategy has payoff. They are classically used to model the spread of conventions, behaviors, and technologies in societies.

Since the pioneering work of Ellison (1993), specific network structures have been shown to have dramatic influence on the convergence of such dynamics. In this talk, I will try to make these results more precise and use the intuition for designing effective algorithms.

Joint work with Andrea Montanari

The existence of incentive-compatible computationally-efficient protocols for combinatorial auctions with decent approximation ratios is the paradigmatic problem in computational mechanism design. It is believed that in many cases good approximations for combinatorial auctions may be unattainable due to an inherent clash between truthfulness and computational efficiency. However, to date, researchers lack the machinery to prove such results. We present a new approach that we believe holds great promise for making progress on this important problem. We develop new technologies for lower bounding the VC-dimension of k-tuples of disjoint sets. We apply this machinery to prove the first computational-complexity hardness results for truthful mechanisms for combinatorial auctions.

Joint work with Elchanan Mossel, Christos Papadimitriou, and Yaron Singer

Consider an environment where long-lived experts repeatedly interact with short-lived customers. In periods when an expert is hired, she chooses between providing a profitable major treatment or a less profitable minor treatment. The expert has private information about which treatment best serves the customer, but has no direct incentive to perform the appropriate one. Customers can observe the past record of each expert's actions, but never learn which actions were appropriate. We find that there exists an equilibrium in which experts always play truthfully and choose the customer's preferred treatment. The expert is rewarded for choosing the less profitable action with more future business: customers return to an expert with high probability if the previous treatment was minor, and low probability if it was major.

If experts have private information regarding both their own payoffs and about what treatment is appropriate, then there is no equilibrium with truthful play in every period. But we construct equilibria where experts are truthful arbitrarily often as their discount factor converges to one.

Joint work with Alex Frankel

Please note that food and drinks are not allowed at Sibley Auditorium. Lunch will be served at Wozniak hall.

By Public Transportation: We recommend getting to Berkeley by BART. Get off at the Downtown Berkeley BART station. You can either walk to Sibley Auditorium (a nice 20-25 minutes walk. Walk east on Center St. to Oxford St., turn left and walk north till getting to Hearst Ave. and then turn right and walk east till you get to Le Roy Ave. (see map). Then use the following instructions to get to Sibley Auditorium) or take a bus. If you decide to take the bus, walk north on Shattuck Avenue till you get to University Avenue. At the corner of Shattuck Ave. & University Ave. board AC Transit Bus #52L, see bus schedule (the bus runs every 15-20 minutes). Get Off at Hearst Ave. & Le Roy Ave.(Cost: $1.75, 5-10 minutes bus ride), and walk to Sibley Auditorium .

By Car: If you plan to get to Berkeley by car, get to UC Berkeley campus, and follow the direction to Cory Hall. The closest parking to Sibley Auditorium is the Lower Hearst Garage at Hearst Avenue & Scenic Avenue. Hourly Pay Parking at all times on Level 2 (cost of $15 for the day). For additional parking information see the parking web pages of UC Berkeley EECS , UC Berkeley , UC Berkeley Parking & Transportation and the city of Berkeley .

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