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.
Call for Participation
One of the main purposes of this symposium is to encourage
collaboration between local researchers. Significant emphasis will be
placed on a session of mini talks. You may sign up for a ten minute
time slot by sending email to email@example.com and include a
description of the your proposed talk. The suggested format for a
mini talk is (a) description of the problem, (b) statement of results,
and (c) discussion of open research directions. There will be no time
for setting up individual laptops for the mini-talk session, instead
we will have all presentations preloaded on a computer in the
|April 17, 2009:||Registration Deadline. It is free and easy. Do it now!|
|April 17, 2009:||Deadline for submitting slides for mini-talks session (extended).|
|10:00-10:30||Arrivals, Registration, Coffee, and Breakfast|
|10:30-11:00||Talk:||Michael Schwarz||"Experts and Their Records"|
|Talk:||Michael Schapira||"VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension"|
|Talk:||Jonathan Levin||"College early admissions"|
|1:30-2:00||Talk:||Amin Saberi||"Game Dynamics, Equilibrium Selection and Network Structure"|
|2:00-2:30||Talk:||Moshe Babaioff||"Characterizing Truthful Multi-Armed Bandit Mechanisms"|
|4:00-4:30||Talk:||Nicolas Lambert||"Eliciting Probabilistic Information: From Full Distributions to Predicates on Distributions"|
|4:30-5:00||Talk:||Christos Papadimitriou||"Computing equilibria"|
|Dinner at local restaurants (not provided).|
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
Joint work with Costis Daskalakis and Mihalis Yannakakis
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
Joint work with Elchanan Mossel, Christos Papadimitriou, and Yaron Singer
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.
|Moshe Babaioff||Microsoft Research|
|Tim Roughgarden||Stanford U.|
|Amin Saberi||Stanford U.|
|Ilya Segal||Stanford U.|
|Adam Szeidl||University of California, Berkeley|