Peter Bro Miltersen
ABSTRACT
Emek et al presented a model of probabilistic single-item second price auctions where an auctioneer who is informed about the type of an item for sale, broadcasts a signal about this type to uninformed bidders. They proved that finding the optimal (for the purpose of generating revenue) pure signaling scheme is strongly NP-hard. In contrast, we prove that finding the optimal mixed signaling scheme can be done in polynomial time using linear programming. For the proof, we show that the problem is strongly related to a problem of optimally bundling divisible goods for auctioning. We also prove that a mixed signaling scheme can in some cases generate twice as much revenue as the best pure signaling scheme and we prove a generally applicable lower bound on the revenue generated by the best mixed signaling scheme.
- Adams, W. J. and Yellen, J. L. 1976. Commodity bundling and the burden of monopoly. The Quarterly Journal of Economics 90, 3, 475--498.Google Scholar
Cross Ref
- Akerlof, G. A. 1970. The market for 'lemons': Quality uncertainty and the market mechanism. The Quarterly Journal of Economics 84, 3, 488--500.Google ScholarCross Ref
- Ausubel, L. M. and Cramton, P. 2004. Auctioning many divisible goods. Journal of the European Economics Association 2, 2--3.Google ScholarCross Ref
- Back, K. and Zender, J. F. 2001. Auctions of divisible goods with endogenous supply. Economics Letters 73, 1, 29--34.Google ScholarCross Ref
- Cramton, P., Shoham, Y., Steinberg, R., and Smith, V. 2010. Combinatorial Auctions. MIT Press. Google ScholarDigital Library
- Emek, Y., Feldman, M., Gamzu, I., and Tennenholtz, M. 2011. Revenue maximization in probabilistic single-item auctions via signaling. In Seventh Ad Auctions Workshop. Online proceedings at http://sites.google.com/site/adauctions2011/program-and-schedule.Google Scholar
- Ghosh, A., Nazerzadeh, H., and Sundararajan, M. 2007. Computing optimal bundles for sponsored search. In WINE. 576--583. Google ScholarDigital Library
- Goldberg, A. V., Hartline, J. D., Karlin, A. R., Saks, M., and Wright, A. 2006. Competitive auctions. Games and Economic Behavior 55, 2, 242 -- 269.Google ScholarCross Ref
- Iyengar, G. and Kumar, A. 2008. Optimal procurement auctions for divisible goods with capacitated suppliers. Review of Economic Design 12, 2, 129--154.Google ScholarCross Ref
- Kellerer, H., Pferschy, U., and Pisinger, D. 2004. Knapsack Problems. Springer, Berlin, Germany.Google Scholar
- Klemperer, P. 2004. Auctions: theory and practice. Toulouse lectures in economics. Princeton University Press.Google Scholar
- Mas-Colell, A., Whinston, M., Green, J., and de Ciències Econòmiques i Empresarials, U. P. F. F. 1995. Microeconomic theory. Oxford University Press New York.Google Scholar
- Myerson, R. B. 1981. Optimal auction design. Mathematics of Operations Research 6, 1, 58--73.Google ScholarDigital Library
Index Terms
- Send mixed signals: earn more, work less
Recommendations
The Impact of Discrete Bidding and Bidder Aggressiveness on Sellers' Strategies in Open English Auctions: Reserves and Covert Shilling
In practice, the rules in most open English auctions require participants to raise bids by a sizeable, discrete amount. Furthermore, some bidders are typically more aggressive in seeking to become the "current bidder" during competitive bidding. Most ...
Pricing Rule in a Clock Auction
We analyze a discrete clock auction with lowest-accepted-bid (LAB) pricing and provisional winners, as adopted by India for its 3G spectrum auction. In a perfect Bayesian equilibrium, the provisional winner shades her bid, whereas provisional losers do ...
Envy-free auctions for digital goods
EC '03: Proceedings of the 4th ACM conference on Electronic commerceWe study auctions for a commodity in unlimited supply, e.g., a digital good. In particular we consider three desirable properties for auctions: item Competitive: the auction achieves a constant fraction of the optimal revenue even on worst case inputs. ...
Comments