Abstract
This paper focuses on multi-agent contract formation by automated negotiation. Commonly individuals are not willing to share information or cooperate and negotiation protocols may give way to unwanted strategic behavior. Socially beneficial contract agreements require a lot of negotiation time. Furthermore, possible interdependencies of contract items lead to complex contract spaces which restrain contract agreements. Therefore, we propose a novel negotiation protocol applying combinatorial auctions for contract formation which consider interdependencies and yield a rapid decision rights allocation. Additionally, this market-based approach utilizes Vickrey-Clarkes-Groves-mechanisms which may lead to truthful preference uncovering and information sharing through bids. However, combinatorial auctions have a computational drawback: winner determination is \(\mathcal{NP}\)-hard. In simulation experiments, two approximation algorithms as well as an optimal computation are tested in comparison with an established negotiation protocol. The results show that our protocol yields an effective solution and requires very short run time.
This is a preview of subscription content, log in via an institution to check access.
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
Buer, T., Pankratz, G.: GRASP with Hybrid Path Relinking for Bi-Objective Winner Determination in Combinatorial Transportation Auctions. BuR - Business Research 3(2), 192–213 (2010)
Conitzer, V., Sandholm, T.: Self-interested Automated Mechanism Design and Implications for Optimal Combinatorial Auctions. In: Proceedings of the 5th ACM Conference on Electronic Commerce, EC 2004 (2004)
Delorme, X., Gandibleux, X., Rodriguez, J.: GRASP for Set Packing Problems. European Journal of Operational Research 153(3), 564–580 (2004)
Feo, T., Resende, M.G.C.: Greedy Randomized Adaptive Search Procedures. Journal of Global Optimization 6(2), 109–133 (1995)
Fink, A.: Supply Chain Coordination by Means of Automated Negotiations Between Autonomous Agents. In: Chaib-draa, B., Müller, J. (eds.) Multiagent based Supply Chain Management. SCI, vol. 28, pp. 351–372. Springer, Heidelberg (2006)
Jennings, N.R., Faratin, P., Lomuscio, A.R., Parsons, S., Sierra, C., Wooldridge, M.: Automated Negotiation: Prospects, Methods and Challenges. Group Decision and Negotiation 10(2), 199–215 (2001)
Klein, M., Faratin, P., Sayama, H., Bar-Yam, Y.: Negotiating Complex Contracts. Group Decision and Negotiation 12(2), 111–125 (2003)
Klein: M., Faratin, P., Sayama, H., Bar-Yam, Y.: Negotiating Complex Contracts, MIT Sloan Working Paper No. 4196-01 (2007), http://ssrn.com/paper=290147
Lehmann, D., Callaghan, L., Shoham, Y.: Truth Revelation in Approximately Efficient Combinatorial Auctions. Journal of the ACM 49(5), 577–602 (2002)
Milgrom, P.R.: Putting Auction Theory to Work. Cambridge University Press, Cambridge (2004)
Nisan, N., Ronen, A.: Algorithmic Mechanism Design. Games and Economic Behavior 35, 166–196 (2001)
Nisan, N., Ronen, A.: Computationally Feasible VCG Mechanisms. Journal of Artificial Intelligence Research 29, 19–47 (2007)
Pekec, A., Rothkopf, M.H.: Combinatorial Auction Design. Management Science 49(11), 1485–1503 (2003)
Sandholm, T.: Distributed Rational Decision Making. In: Weiβ, G. (ed.) Multiagent Systems: A Modern Introduction to Distributed Artificial Intelligence, pp. 201–258. MIT Press, Cambridge (1999)
Sandholm, T., Suri, S., Gilpin, A., Levine, D.: Winner Determination in Combinatorial Auction Generalizations. In: Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS (2002)
Vickrey, W.: Counterspeculation, Auctions, and Competitive Sealed Tenders. The Journal of Finance 16(1), 8–37 (1961)
Zurel, E., Nisan, N.: An Efficient Approximate Allocation Algorithm for Combinatorial Auctions. In: Proceedings of the 3rd ACM Conference on Electronic Commerce (EC 2001), pp. 125–136 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lang, F., Fink, A. (2011). A Combinatorial Auction Negotiation Protocol for Time-Restricted Group Decisions. In: Bouchachia, A. (eds) Adaptive and Intelligent Systems. ICAIS 2011. Lecture Notes in Computer Science(), vol 6943. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-23857-4_33
Download citation
DOI: https://doi.org/10.1007/978-3-642-23857-4_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-23856-7
Online ISBN: 978-3-642-23857-4
eBook Packages: Computer ScienceComputer Science (R0)