Approximation in Privacy-Preserving Mechanisms

06 May
05/06/2009 - 12:00pm
Distinguished Lecturer Series

Joan Feigenbaum
Yale University

Computer Science Building, Rooms 150 & 151

Gerome Miklau

In the design of incentive-compatible algorithms and protocols, a great deal of effort is devoted to incenting agents to behave truthfully, i.e., to reveal private information that mechanisms need in order to compute optimal outcomes. A much smaller body of work is devoted to the complementary goal of enabling agents not to reveal private information that mechanisms do not need in order to compute optimal outcomes. A compelling example of the benefits of privacy-preserving mechanisms was provided ten years ago by Naor, Pinkas, and Sumner: Consider a 2nd-price Vickrey auction of a used laptop, in which agent 1 bids $500, agent 2 bids $400, and all others bid less than $400; in a straightforward protocol, the auctioneer receives sealed bids from all agents and sells the laptop to agent 1 for $400. It would not be at all surprising if, in subsequent auctions of similar used laptops in which agent 1 participates, the same auctioneer set a reservation price of $499. This could be avoided if the auction protocol allowed the auctioneer to learn the fact that agent 1 was the highest bidder (something he needs to know in order to determine the outcome) but not the amount that agent 1 bid (something that he does not need to know).

One approach that has proved fruitful in the study of privacy-preserving mechanisms is the use of monochromatic tilings, which are a standard tool in communication complexity. In particular, it is known that there are basic social-choice functions for which no perfectly privacy-preserving mechanisms exist and others for which perfect privacy can be achieved only at the cost of exponential communication complexity. We continue this line of work by formulating the notions of a mechanism's worst-case and average-case privacy-approximation ratios. We illustrate the usefulness of these notions by proving bounds on approximate privacy of mechanisms for social-choice functions of interest, including the basic 2nd-price Vickrey auction.

Joint work with Aaron Jaggard and Michael Schapira.