Location: We meet in the Gates 4B lobby, also known as the theory lounge.
Mailing List: thseminar@cs.stanford.edu. Email shaddin to sign up.
Contact: Shaddin Dughmi (shaddin at cs dot stanford dot edu)
Food: Wendy usually choses the food at her discretion. However, the speaker may suggest a preference to Wendy for the day of their talk ahead of time.
For previous quarter schedules see here.
We investigate a fundamental (public-good) cost-sharing mechanism design problem. The goal is to implement a socially efficient solution (our objective) while recovering cost (a constraint). As participants value for service is private, we would also like incentive compatibility (another constraint). It was known previously that the problem is over constrained. We would like to investigate \emph{how} over constrained the problem is. Our proof has two phases: A. Characterizing: Using the constraints to figure out what kind of mechanisms are valid. (Almost non-existent and we will see why) B. Bounding: Using the characterization to prove a lower bound on the efficiency loss. (A fun application of Yao's Minimax principle)