Abstract
We consider enhancing with privacy concerns a large class of auctions, which include sealed-bid single-item auctions but also general multi-item multi-winner auctions, our assumption being that bidders primarily care about monetary payoff and secondarily worry about exposing information about their type to other players and learning information about other players’ types, that is, bidders are greedy then paranoid. To treat privacy explicitly within the game theoretic context, we put forward a novel hybrid utility model that considers both monetary and privacy components in players’ payoffs.
We show how to use rational cryptography to approximately implement any given ex interim individually strictly rational equilibrium of such an auction 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. By “approximately implement” we mean that, under cryptographic assumptions, running the protocol is a computational Nash equilibrium with a payoff profile negligibly close to the original equilibrium.
Supported by the Center for Algorithmic Game Theory, funded by The Carlsberg Foundation.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abraham, I., Dolev, D., Gonen, R., Halpern, J.: Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation. In: PODC 2006, pp. 53–62. ACM, New York (2006)
Bogetoft, P., Damgård, I., Jakobsen, T., Nielsen, K., Pagter, J., Toft, T.: A practical implementation of secure auctions based on multiparty integer computation. In: Di Crescenzo, G., Rubin, A. (eds.) FC 2006. LNCS, vol. 4107, pp. 142–147. Springer, Heidelberg (2006)
Bradford, P.G., Park, S., Rothkopf, M.H., Park, H.: Protocol completion incentive problems in cryptographic Vickrey auctions. Electronic Commerce Research 8(1-2), 57–77 (2008)
Dodis, Y., Halevi, S., Rabin, T.: A cryptographic solution to a game theoretic problem. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 112–130. Springer, Heidelberg (2000)
Escamocher, G., Miltersen, P.B., Santillan-Rodriguez, R.: Existence and computation of equilibria of first-price auctions with integral valuations and bids. In: AAMAS 2009 (2009)
Gordon, S.D., Hazay, C., Katz, J., Lindell, Y.: Complete fairness in secure two-party computation. In: STOC 2008, pp. 413–422. ACM, New York (2008)
Gordon, S.D., Katz, J.: Rational secret sharing, revisited. In: De Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 229–241. Springer, Heidelberg (2006)
Halpern, J., Pass, R.: Game theory with costly computation (manuscript) (2008)
Halpern, J., Teague, V.: Rational secret sharing and multiparty computation: extended abstract. In: STOC 2004, pp. 623–632. ACM, New York (2004)
Izmalkov, S., Lepinski, M., Micali, S.: Rational secure computation and ideal mechanism design. In: FOCS 2005, pp. 585–594. IEEE, Los Alamitos (2005)
Kol, G., Naor, M.: Cryptography and game theory: Designing protocols for exchanging information. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 320–339. Springer, Heidelberg (2008)
Kol, G., Naor, M.: Games for exchanging information. In: STOC 2008, pp. 423–432. ACM, New York (2008)
Lepinksi, M., Micali, S., shelat, a.: Collusion-free protocols. In: STOC 2005, pp. 543–552. ACM, New York (2005)
Lepinski, M., Micali, S., Peikert, C., shelat, a.: Completely fair SFE and coalition-safe cheap talk. In: PODC 2004, pp. 1–10. ACM, New York (2004)
Lindell, A.Y.: Legally-enforceable fairness in secure two-party computation. In: Malkin, T.G. (ed.) CT-RSA 2008. LNCS, vol. 4964, pp. 121–137. Springer, Heidelberg (2008)
Lysyanskaya, A., Triandopoulos, N.: Rationality and adversarial behavior in multi-party computation. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 180–197. Springer, Heidelberg (2006)
Micali, S., shelat, a.: Purely rational secret sharing (extended abstract). In: TCC 2009. LNCS, vol. 5444, pp. 54–71. Springer, Heidelberg (2009)
Naor, M., Pinkas, B., Sumner, R.: Privacy preserving auctions and mechanism design. In: 1st International Conference on Electronic Commerce, pp. 129–139. ACM, New York (1999)
Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)
Ong, S.J., Parkes, D., Rosen, A., Vadhan, S.: Fairness with an honest minority and a rational majority. In: TCC 2009. LNCS, vol. 5444, pp. 36–53. Springer, Heidelberg (2009)
Parkes, D.C., Rabin, M.O., Shieber, S.M., Thorpe, C.A.: Practical secrecy-preserving, verifiably correct and trustworthy auctions. In: 8th International Conference on Electronic Commerce, pp. 70–81. ACM, New York (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Miltersen, P.B., Nielsen, J.B., Triandopoulos, N. (2009). Privacy-Enhancing Auctions Using Rational Cryptography. In: Halevi, S. (eds) Advances in Cryptology - CRYPTO 2009. CRYPTO 2009. Lecture Notes in Computer Science, vol 5677. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03356-8_32
Download citation
DOI: https://doi.org/10.1007/978-3-642-03356-8_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03355-1
Online ISBN: 978-3-642-03356-8
eBook Packages: Computer ScienceComputer Science (R0)