Abstract
In a combinatorial auction problem bidders are allowed to bid on a bundle of items. The auctioneer has to select a subset of the bids so as to maximize the price it gets, and of course making sure that it does not accept multiple bids that have the same item as each item can be sold only once. In this paper we show how the combinatorial auction problem and many of its extensions can be expressed in logic programming based systems such as Smodels and dlv. We propose this as an alternative to the standard syntax specific specialized implementations that are much harder to modify and extend when faced with generalizations and additional constraints.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
T. Eiter, N. Leone, C. Mateis, G. Pfeifer, and F. Scarcello. A deductive system for nonmonotonic reasoning. In Proc. of KR 98, pages 406–417, 1998. 187, 190
Y. Fujisima, K. Leyton-Brown, and Y. Shoham. Taming the computational complexity of combinatorial auctions. In Proc. of IJCAI 99, pages 548–553, 1999. 186, 187, 188, 191
M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. In R. Kowalski and K. Bowen, editors, Logic Programming: Proc. of the Fifth Int’l Conf. and Symp., pages 1070–1080. MIT Press, 1988. 187
H. Hoos and C. Boutilier. Solving combinatorial auctions using stochastic local search. In Proc. of AAAI’00, 2000. 186, 187, 191, 198
H. Kautz and B. Selman. Planning as satisfiability. In Proc. of ECAI-92, pages 359–363, 1992. 187
K. Leyton-Brown, Y. Shoham, and M. Tennenholtz. An algorithm for multi-unit combinatorial auctions. In Proc. of AAAI’00, 2000. 186, 187, 188, 198
D. Monderer and M. Tennenholtz. Optimal auctions revisited. Artificial Intelligence, 2000. 186
I. Niemela and P. Simons. Smodels-an implementation of the stable model and well-founded semantics for normal logic programs. In Proc. 4th international conference on Logic programming and non-monotonic reasoning, pages 420–429, 1997. 187, 198
S. Rassenti, V. Smith, and R. Bulfin. A combinatorial auction mechanism for airport time slot allocation. Bell J. of Economics, 13:402–417, 1982. 186
M. Rothkopf, A. Pekec, and R. Harstad. Computationally manageable combinatorial auctions. Management Science, 44(8):1131–1147, 1998. 186, 187
T. Sandholm. An implementation of the contract net protocol based on marginal cost calculations. In Proc. of AAAI 93, pages 256–262, 1993. 186
T. Sandholm. An algorithm for optimal winner determination in combinatorial auctions. In Proc. of IJCAI 99, pages 542–547, 1999. 186, 187, 188, 198
T. Sandholm and S. Suri. Improved algorithms for optimal winner determination in combinatorial auctions and generalizations. In Proc. of AAAI’00, 2000. 186, 187, 188, 190, 194, 195, 196, 198
P. Simons. Extending the stable model semantics with more expressive rules. In Proc. of International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR’99, 1999. 187, 189, 198
M. Tennenholtz. Some tractable combinatorial auctions. In Proc. of AAAI’00, 2000. 186, 187
M. Wellman, W. Walsh, P. Wurman, and J. Mackie-Mason. Auction protocols for decentralized scheduling. Games and Economic bahavior, 1999. 186
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Baral, C., Uyan, C. (2001). Declarative Specification and Solution of Combinatorial Auctions Using Logic Programming. In: Eiter, T., Faber, W., Truszczyński, M.l. (eds) Logic Programming and Nonmotonic Reasoning. LPNMR 2001. Lecture Notes in Computer Science(), vol 2173. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45402-0_14
Download citation
DOI: https://doi.org/10.1007/3-540-45402-0_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42593-9
Online ISBN: 978-3-540-45402-1
eBook Packages: Springer Book Archive