Microeconomics and computer science at Cornell: auctions and privacy

Gates Hall isn't a bad name for a building in which to schedule a seminar in which economics and computers are the subject...

Joint Microeconomics and Computer Science Workshop, Aaron Roth

Mon, 10/27/2014 - 4:00pm

Aaron Roth

University of Pennsylvania

310 Gates Hall

Downloads

Files: 

 Private and (Asymptotically) Truthful Combinatorial Auctions

Event Categories: Microeconomic Theory

Private and (Asymptotically) Truthful Combinatorial Auctions

Aaron Roth

Monday, October 27, 2014
4:00pm 310 Gates Hall

Abstract:

Consider the following problem: a large public electricity provider (say, in California) faces a situation where demand for electricity might, without intervention, rise above the utility's ability to generate power. Rather than resorting to rolling brown-outs, however, a forward-thinking ballot initiative has given the utility the ability to shut off the air-conditioners of individual buildings remotely. Using this ability, the utility hopes, they might be able to coordinate shut-offs so that nobody is ever uncomfortable (say, guaranteeing that every apartment's air conditioner runs during some 10 minute interval of every hour in which the apartment is occupied), but so that peak electricity usage never rises above peak power production.

While this combinatorial optimization approach to the problem might be preferable to rolling brown outs, it introduces a privacy concern: the utility will now be making decisions as a function of when customers report they are at home, which can be highly sensitive information. Is there a way to solve this problem so that no coalition of customers j != i can learn about the schedule of customer i? Moreover, can we pair such a solution with a schedule of electricity rates so that no player has more than a vanishing incentive to misreport their demands?

We show that the answer is "yes" to this problem, and to a broad class of welfare maximization problems that can be posed as convex programs. We give a method to compute near optimal solutions to such problems under the formal constraint of ``differential privacy'', while giving Walrasian-equilibrium like item/resource pricings which result in truth-telling as an asymptotically dominant strategy, as the size of the economy grows large (in a mild way).