2008.10.28 | Troels Bjerre Sørensen

Title: Privacy-enhancing first-price auctions using rational cryptography
Speaker: Jesper Buus Nielsen
Time: Tue Nov 18th 2008, 14:15-16:00
Location: Turing-014
Abstract: TBA

We consider enhancing a sealed-bid single-item auction with privacy concerns, our assumption being that bidders primarily care about monetary payoff and secondarily worry about exposing information about their type toother players and learning information about other playerstypes. To treat privacy explicitly within the game theoretic context, we put forward a novel hybrid utility model that considers both fiscal and privacy components in the players payoffs.
We show how to use rational cryptography to approximately implement a given ex interim indi- vidually strictly rational equilibrium of such an auction (or any gamewith a winner) without a trusted mediator through a cryptographic protocol that uses only point-to-point authenticated channels between the players. By ex interim individually strictly rational we mean that, given its type and before making its move, each player has a strictly positive expected utility, i.e., it becomes the winner of the auction with positive probability. By approximately implement we mean that, under cryptographic assump- tions, running the protocol is a computational Nash equilibrium with a payoff profile negligibly close to the original equilibrium.

In addition the protocol has the stronger property that no collusion, of any size, can obtain more by deviating in the implementation than by deviating in the ideal mediated setting which the mechanism was designed in. Also, despite the non-symmetric payoffs profile, the protocol always correctly terminates.

Joint work with Nikolaos Triandopoulos and Peter Bro Miltersen.