Yuval Emek
Moshe Tennenholtz
ABSTRACT
Signaling is an important topic in the study of asymmetric information in economic settings. In particular, the transparency of information available to a seller in an auction setting is a question of major interest. We introduce the study of signaling when conducting a second price auction of a probabilistic good whose actual instantiation is known to the auctioneer but not to the bidders. This framework can be used to model impressions selling in display advertising. We establish several results within this framework. First, we study the problem of computing a signaling scheme that maximizes the auctioneer's revenue in a Bayesian setting. We show that this problem is polynomially solvable for some interesting special cases, but computationally hard in general. Second, we establish a tight bound on the minimum number of signals required to implement an optimal signaling scheme. Finally, we show that at least half of the maximum social welfare can be preserved within such a scheme.
- AKERLOF, G. A. 1970. The market for 'lemons': Quality uncertainty and the market mechanism. The Quarterly Journal of Economics 84, 3, 488--500.Google Scholar
Cross Ref
- CREMER, J. AND MCLEAN, R. P. 1985. Optimal selling strategies under uncertainty for a discriminating monopolist when demands are interdependent. Econometrica 53, 2, 345--61.Google ScholarCross Ref
- DOBZINSKI, S., FU, H., AND KLEINBERG, R. D. 2011. Optimal auctions with correlated bidders are easy. In Proceedings of the 43rd annual ACM symposium on Theory of computing. STOC '11. ACM, New York, NY, USA, 129--138. Google ScholarDigital Library
- EDELMAN, B., OSTROVSKY, M., AND SCHWARZ, M. 2007. Internet advertising and the generalized secondprice auction: Selling billions of dollars worth of keywords. American Economic Review 97, 1, 242--259.Google ScholarCross Ref
- EMEK, Y., FELDMAN, M., GAMZU, I., AND TENNENHOLTZ, M. 2011. Signaling schemes for revenue maximization. AdAuctions Workshop. Google ScholarDigital Library
- FEINBERG, Y. AND TENNENHOLTZ, M. 2005. Anonymous bidding and revenue maximization. The B.E. Journal of Theoretical Economics topics.5, 1, 2.Google Scholar
- GAREY, M. R. AND JOHNSON, D. S. 1990. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA.Google Scholar
- GHOSH, A., NAZERZADEH, H., AND SUNDARARAJAN, M. 2007. Computing optimal bundles for sponsored search. In Proceedings of the 3rd international conference on Internet and network economics. WINE'07. Springer-Verlag, Berlin, Heidelberg, 576--583. Google ScholarDigital Library
- LEVIN, J. AND MILGROM, P. 2010. Online advertising: Heterogeneity and conflation in market design. American Economic Review 100, 2, 603--07.Google ScholarCross Ref
- MILGROM, P. 2010. Simplified mechanisms with an application to sponsored-search auctions. Games and Economic Behavior 70, 1, 62--70.Google ScholarCross Ref
- MILGROM, P. R. AND WEBER, R. J. 1982. A theory of auctions and competitive bidding. Econometrica 50, 5, 1089--1122.Google ScholarCross Ref
- MILTERSEN, P. B. AND SHEFFET, O. 2012. Send mixed signals -- earn more, work less. In EC'12.Google ScholarDigital Library
- MUTHUKRISHNAN, S. 2009. Ad Exchanges: Research Issues. In Internet and Network Economics, S. Leonardi, Ed. Lecture Notes in Computer Science Series, vol. 5929. Springer Berlin / Heidelberg, Berlin, Heidelberg, Chapter 1, 1--12. Google ScholarDigital Library
- MYERSON, R. 1981. Optimal auction design. Mathematics of Operations Research 6, 1, 58--73.Google ScholarDigital Library
- PAPADIMITRIOU, C. H. AND PIERRAKOS, G. 2011. On optimal single-item auctions. In Proceedings of the 43rd annual ACM symposium on Theory of computing. STOC '11. ACM, New York, NY, USA, 119--128. Google ScholarDigital Library
- PERRY, M. AND RENY, P. J. 1999. On the failure of the linkage principle in multi-unit auctions. Econometrica 67, 4, 895--900.Google ScholarCross Ref
- SPENCE, M. 1973. Job Market Signaling. The Quarterly Journal of Economics 87, 3, 355--374.Google ScholarCross Ref
- SPENCE, M. 2002. Signaling in Retrospect and the Informational Structure of Markets. American Economic Review 92, 3, 434--459.Google ScholarCross Ref
- STANLEY, R. P. 2004. An introduction to hyperplane arrangements. In Lecture notes, IAS/Park City Mathematics Institute.Google Scholar
- THIERRY, F. AND STEFANO, L. 2003. Linkage principle, multi-dimensional signals and blind auctions. Les Cahiers de Recherche 785, HEC Paris. Aug.Google Scholar
- VARIAN, H. 2007. Position auctions. International Journal of Industrial Organization 25, 6, 1163--1178.Google ScholarCross Ref
- VICKREY, W. 1961. Counterspeculation, Auctions, and Competitive Sealed Tenders. The Journal of Finance 16, 1, 8--37.Google ScholarCross Ref
- WEBER, R. J. 2003. Auction theory: By vijay krishna. academic press, 2002. Games and Economic Behavior 45, 2, 488--497.Google ScholarCross Ref
Index Terms
- Signaling schemes for revenue maximization
Recommendations
Signaling Schemes for Revenue Maximization
Signaling is an important topic in the study of asymmetric information in economic settings. In particular, the transparency of information available to a seller in an auction setting is a question of major interest. We introduce the study of signaling ...
Constrained signaling for welfare and revenue maximization
We consider auction settings where the seller is constrained in the amount and nature of information he may reveal about the good being sold. This is encountered, for example, in online advertising auctions, where communicating precise details of every ...
Signaling Through Pricing by Service Providers with Social Preferences
In many service markets such as consulting, auto repair, financial planning, and healthcare, the service provider may have more information about the customer's problem than the customer, and different customers may impose different costs on the service ...
Comments