Daniel Lehmann
Yoav Shoham
Abstract
Some important classical mechanisms considered in Microeconomics and Game Theory require the solution of a difficult optimization problem. This is true of mechanisms for combinatorial auctions, which have in recent years assumed practical importance, and in particular of the gold standard for combinatorial auctions, the Generalized Vickrey Auction (GVA). Traditional analysis of these mechanisms---in particular, their truth revelation properties---assumes that the optimization problems are solved precisely. In reality, these optimization problems can usually be solved only in an approximate fashion. We investigate the impact on such mechanisms of replacing exact solutions by approximate ones. Specifically, we look at a particular greedy optimization method. We show that the GVA payment scheme does not provide for a truth revealing mechanism. We introduce another scheme that does guarantee truthfulness for a restricted class of players. We demonstrate the latter property by identifying natural properties for combinatorial auctions and showing that, for our restricted class of players, they imply that truthful strategies are dominant. Those properties have applicability beyond the specific auction studied.
- Archer, A. F., and Tardos, É. 2001. Truthful mechanisms for one-parameter agents. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, Nev.). IEEE Computer Society, Los Alamitos, Calif., pp. 482--491. Google Scholar
- Bartal, Y., Gonen, R., and Nisan, N. 2002. Incentive compatible multi unit combinatorial auctions. Tech. Rep. TR-2002-36, Leibniz Center for Research in Computer Science, School of Computer Science and Engineering, Hebrew University, Jerusalem, Israel. June. (Presented at Dagstuhl workshop on Electronic Market Design.)Google Scholar
- Boutilier, C., and Hoos, H. H. 2001. Bidding languages for combinatorial auctions. In Proceedings of IJCAI'01 (Seattle, Wash.). Morgan-Kaufmann, San Mateo, Calif. Google Scholar
- Clarke, E. H. 1971. Multipart pricing of public goods. Public Choice 11, 17--33.Google Scholar
- Cramton, P. C. 1997. The FCC spectrum auction: An early assessment. J. Econ. Manage. Strat. 6, 3, 431--495.Google Scholar
- DeMartini, C., Kwasnica, A. M., Ledyard, J. O., and Porter, D. 1999. A new and improved design for multi-object iterative auctions. Social Science Working Paper 1054, California Institute of Technology, Pasadena, Calif.Google Scholar
- Fujishima, Y., Leyton-Brown, K., and Shoham, Y. 1999. Taming the computational complexity of combinatorial auctions: Optimal and approximate approaches. In Proceedings of IJCAI'99 (Stockholm, Sweden). Morgan-Kaufmann, San Mateo, Calif. Google Scholar
- Gonen, R., and Lehmann, D. 2000. Optimal solutions for multi-unit combinatorial auctions: Branch and bound heuristics. In Proceedings of the 2nd Conference on Electronic Commerce (EC'00) (Minneapolis, Minn.). ACM, New York, pp. 13--20. Google Scholar
- Groves, T. 1973. Incentives in teams. Econometrica 41, 617--631.Google Scholar
- Halldórsson, M. M. 1999. Approximation of weighted independent set and hereditary subset problems. In Proceedings of COCOON'99. Lecture Notes in Computer Science, vol. 1627. Springer-Verlag, New York.Google Scholar
- Halldórsson, M. M. 2000. Approximation of weighted independent set and hereditary subset problems. J. Graph Algori. Appl. 4, 1, 1--16.Google Scholar
- Håstad, J. 1999. Clique is hard to approximate within n1−ε. Acta Math. 182, 105--142.Google Scholar
- Jain, K., and Vazirani, V. V. 2001. Applications of approximation algorithms to cooperative games. In Proceedings of 33rd Annual ACM Symposium on Theory of Computing (Crete, Greece). ACM, New York, pp. 364--372. Google Scholar
- Karp, R. M. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds. Plenum Press, New York, pp. 85--103.Google Scholar
- Krishna, V., and Perry, M. 1998. Efficient mechanism design. Available at http://www.ma.huji.ac. il/∼motty.Google Scholar
- Lehmann, B., Lehmann, D., and Nisan, N. 2001. Combinatorial auctions with decreasing marginal utilities. In Proceedings of the 3rd Conference on Electronic Commerce EC'01 (Tampa, Fla.). Y. Shoham, Ed. ACM, New York. Google Scholar
- Lehmann, D., O'Callaghan, L. I., and Shoham, Y. 1999a. Truth revelation in rapid, approximately efficient combinatorial auctions. Tech. Note STAN-CS-TN-99-88, Stanford University, Computer Science, Robotics Lab., Stanford, Calif. Google Scholar
- Lehmann, D., O'Callaghan, L. I., and Shoham, Y. 1999b. Truth revelation in rapid, approximately efficient combinatorial auctions. In Proceedings of the 1st ACM Conference on Electronic Commerce (EC'99) (Denver, Col.). ACM, New York, pp. 96--102. Google Scholar
- MacKie-Mason, J. K., and Varian, H. R. 1994. Generalized Vickrey auctions. Working paper, Univ. Michigan. July.Google Scholar
- Mas-Colell, A., Whinston, M. D., and Green, J. R. 1995. Microeconomic Theory. Oxford University Press, New York, Oxford.Google Scholar
- McMillan, J. 1994. Selling spectrum rights. J. Econ. Pers. 68, 145--162.Google Scholar
- Milgrom, P. 2000. Putting auction theory to work: The simultaneous ascending auction. Journal of Political Economy 108, 2, 245--272.Google Scholar
- Monderer, D., Kfir-Dahav, N. E., and Tennenholtz, M. 2000. Mechanism design for resource bounded agents. In Proceedings of ICMAS-2000. Google Scholar
- Monderer, D., and Tennenholtz, M. 2000. Asymptotically optimal multi-object auctions for risk-averse agents. Available at http://ie.technion.ac.il/dov.phtml.Google Scholar
- Mu'alem, A., and Nisan, N. 2002. Truthful approximation mechanisms for restricted combinatorial auctions. In Proceedings 18th National Conference on Artificial Intelligence, AAAI'02. Edmonton, Canada. (Also presented at Dagstuhl workshop on Electronic Market Design), 379--384. Google Scholar
- Myerson, R. B. 1981. Optimal auction design. Math. Oper. Res. 6, 58--73.Google Scholar
- Nisan, N. 1999. Algorithms for selfish agents. In Symposium on Theoretical Aspects in Computer Science (Trier, Germany), 1--15.Google Scholar
- Nisan, N. 2000. Bidding and allocation in combinatorial auctions. In Proceedings of the 2nd ACM Conference on Electronic Commerce (EC'00) (Minneapolis, Minn.). ACM, New York, pp. 1--12. Google Scholar
- Nisan, N., and Ronen, A. 1999. Algorithmic mechanism design. In Proceedings of the 31st Annual Symposium on Theory of Computing. ACM, 129--140. Google Scholar
- Nisan, N., and Ronen, A. 2000. Computationally feasible VCG mechanisms. In Proceedings of the 2nd ACM Conference on Electronic Commerce (EC'00) (Minneapolis, Minn.). ACM, New York. Google Scholar
- Rothkopf, M. H. 1983. Bidding theory: the phenomena to be modeled. In Auctions, Bidding and Contracting: Uses and Theory, R. Engelbrecht-Wiggans, M. Shubik, and R. Stark, Eds. New York University Press, New York, pp. 105--120.Google Scholar
- Rothkopf, M. H., Pekeč, A., and Harstad, R. M. 1998. Computationally manageable combinatorial auctions. Manage. Sci. 44, 8, 1131--1147. Google Scholar
- Roughgarden, T., and Tardos, E. 2002. How bad is selfish routing? J. ACM 49, 2 (Mar.), 236--259. Google Scholar
- Sandholm, T. 1999. An algorithm for optimal winner determination in combinatorial auctions. In Proceedings of IJCAI'99 (Stockholm, Sweden). Morgan-Kaufmann, San Mateo, Calif., pp. 542--547. Google Scholar
- Sandholm, T. 2000. eMediator: A next generation electronic commerce server. In the International Conference on Autonomous Agents (Barcelona, Spain). 73--96. (First appeared as a Washington University, St. Louis, Dept of Computer Science technical report WUCS-99-02, January 1999.) Google Scholar
- Sandholm, T. 2002. Algorithm for optimal winner determination in combinatorial auctions. Artif. Intell. 135, 1--54. Google Scholar
- Varian, H. R. 1995. Economic mechanism design for computerized agents. In Proceedings of the 1st Usenix Conference on Electronic Commerce. New York. Google Scholar
- Vickrey, W. S. 1961. Counterspeculation, auctions and competitive sealed tenders. J. Finance 16, 8--37.Google Scholar
Index Terms
- Truth revelation in approximately efficient combinatorial auctions
Recommendations
Approximately Efficient Two-Sided Combinatorial Auctions
Special Issue on EC'17We develop and extend a line of recent work on the design of mechanisms for two-sided markets. The markets we consider consist of buyers and sellers of a number of items, and the aim of a mechanism is to improve the social welfare by arranging purchases ...
Bayesian Combinatorial Auctions
We study the following simple Bayesian auction setting: m items are sold to n selfish bidders in m independent second-price auctions. Each bidder has a private valuation function that specifies his or her complex preferences over all subsets of items. ...
Approximately Efficient Two-Sided Combinatorial Auctions
EC '17: Proceedings of the 2017 ACM Conference on Economics and ComputationWe develop and extend a line of recent work on the design of mechanisms for two-sided markets. The markets we consider consist of buyers and sellers of a number of items, and the aim of a mechanism is to improve the social welfare by arranging purchases ...
Comments