Ramchurn, Sarvapali D., Dash, Rajdeep K., Jennings, Nick, Giovannucci, Andrea, Rodríguez-Aguilar, Juan A. and Mezzetti, Claudio (2008) Trust-based mechanisms for robust and efficient task allocation in the presence of execution uncertainty. Working Paper. Coventry: University of Warwick, Department of Economics. (Warwick economic research papers.

Preview

PDF WRAP_Dash_twerp_880.pdf - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (361Kb)

Abstract

Vickrey-Clarke-Groves (VCG) mechanisms are often used to allocate tasks to selfish and rational agents. VCG mechanisms are incentive-compatible, direct mechanisms that are efficient (i.e. maximise social utility) and individually rational (i.e. agents prefer to join rather than opt out). However, an important assumption of these mechanisms is that the agents will always successfully complete their allocated tasks. Clearly, this assumption is unrealistic in many real-world applications where agents can, and often do, fail in their endeavours. Moreover, whether an agent is deemed to have failed may be perceived differently by different agents. Such subjective perceptions about an agent’s probability of succeeding at a given task are often captured and reasoned about using the notion of trust. Given this background, in this paper, we investigate the design of novel mechanisms that take into account the trust between agents when allocating tasks. Specifically, we develop a new class of mechanisms, called trust-based mechanisms, that can take into account multiple subjective measures of the probability of an agent succeeding at a given task and produce allocations that maximise social utility, whilst ensuring that no agent obtains a negative utility. We then show that such mechanisms pose a challenging new combinatorial optimisation problem (that is NP-complete), devise a novel representation for solving the problem, and develop an effective integer programming solution (that can solve instances with about 2×105 possible allocations in 40 seconds).

Item Type:	Working or Discussion Paper (Working Paper)
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Social Sciences > Economics
Library of Congress Subject Headings (LCSH):	Mathematical sociology, Combinatorial optimization, Utilitarianism, Statistical mechanics, Assignment problems (Programming)
Series Name:	Warwick economic research papers
Publisher:	University of Warwick, Department of Economics
Place of Publication:	Coventry
Date:	2008
Number:	No.880
Number of Pages:	38
Status:	Not Peer Reviewed
Access rights to Published version:	Open Access
References:	[1] A. Archer, C. Papadimitriou, K. Talwar, and E. Tardos. An approximate truthful mechanism for combinatorial auctions with single parameter agent. Internet Mathematics, 1(2):129–150, 2003. [2] C. Berge. Graphs and Hypergraphs. North-Holland Publishing Company, 1973. [3] A. Byde. A comparison between mechanisms for sequential compute resource auctions. In Proceedings of the 5th international joint conference on Autonomous agents and multiagent systems (AAMAS06), pages 1199–1201. ACM, 2006. [4] J. Cerquides, U. Endriss, A. Giovannucci, and J. A. Rodr´ıguez-Aguilar. Bidding languages and winner determination for mixed multi-unit combinatorial auctions. In IJCAI, pages 1221– 1226, 2007. [5] P. Dasgupta. Trust as a commodity. In D. Gambetta, editor, Trust: Making and Breaking Cooperative Relations, pages 49–72. Blackwell, 1998. [6] R. K. Dash, D. C. Parkes, and N. R. Jennings. Computational mechanism design: A call to arms. IEEE Intelligent Systems, 18(6):40–47, 2003. [7] R. K. Dash, S. D. Ramchurn, and N. R. Jennings. Trust-based mechanism design. In Proceedings of the 3rd Int. Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS04), volume 2, pages 726–753, 2004. [8] C. d’Aspremont and L. A. Gerard-Varet. Incentives and incomplete information. Journal of Public Economics, 11(1):25–45, February 1979. [9] C. Dellarocas. Goodwill hunting: An economically efficient online feedback mechanism for environments with variable product quality. In Proceedings of the workshop on Agent- Mediated Electronic Commerce, pages 238–252, 2002. [10] Y. Engel, M. P. Wellman, and K.M. Lochner. Bid expressiveness and clearing algorithms in multiattribute double auctions. In Seventh ACM Conference on Electronic Commerce, pages 110–119, 2006. [11] K. Fullam, T. Klos, G. Muller, J. Sabater, Z. Topol, K. S. Barber, J. Rosenschein, and L. Vercouter. The agent reputation and trust (art) testbed architecture. In Workshop on Trust in Agent Societies at The Fourth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS05), pages 50–62, 2005. [12] J. Hershberger and S. Suri. Vickrey pricing in network routing: Fast payment computation. In In Proc. of the 42nd IEEE Symposium on Foundations of Computer Science, pages 252–259, 2001. [13] P. Jehiel and B. Moldovanu. Efficient design with interdependent valuations. Econometrica, 69(5):1237–59, 2001. [14] N. R. Jennings, P. Faratin, T. J. Norman, P. O’Brien, B. Odgers, and J. L. Alty. Implementing a business process management system using adept: A real-world case study. Int. Journal of Applied Artificial Intelligence, 14(5):421–465, 2000. [15] R. Jurca and B. Faltings. An incentive compatible reputation mechanism. In Proceedings of the IEEE Conference on E-Commerce CEC03, pages 285–292, 2003. [16] R. Jurca and B. Faltings. Minimum payments that reward honest reputation feedback. In EC ’06: Proceedings of the 7th ACM conference on Electronic commerce, pages 190–199, 2006. [17] R. Jurca and B. Faltings. Obtaining reliable feedback for sanctioning reputation mechanisms. Journal of Artificial Intelligence Research (JAIR), 29:391–419, 2007. [18] J. Kalagnanam, A. J. Davenport, and H. S. Lee. Computational aspects of clearing continuous double auctions with assignment constraints and indivisible demand. Technical report, IBM Research RC21660(97613), 2000. [19] J. Kalagnanam and D. C. Parkes. Auctions, bidding and exchange design. In David Simchi- Levi, S. David Wu, and Max Shen, editors, Handbook of Quantitative Supply Chain Analysis: Modeling in the E-Business Era, Int. Series in Operations Research and Management Science, chapter 5. Kluwer, 2004. [20] V. Krishna. Auction Theory. Academic Press, 2002. [21] A.MasColell,M.Whinston, and J.R. Green. Microeconomic Theory. Oxford University Press, 1995. [22] C. Mezzetti. Mechanism design with interdependent valuations: Efficiency. Econometrica, 72(5):1617–1626, February 2004. [23] C.Mezzetti. Mechanism design with interdependent valuations: Surplus extraction. Economic Theory, 31(3):473–488, 2007. [24] N. Miller, P. Resnick, and R. Zeckhauser. Eliciting honest feedback: The peer prediction method. Management Science, 51(9):1359–1373, 2005. [25] J.S. Milton and J. C. Arnold. Introduction to Probability and Statistics. Principles and Applications For Engineering and the Computing Sciences. McGraw-Hill Inc., 1998. [26] N. Nisan. Bidding languages for combinatorial auctions. In P. Cramton, Y. Shoham, and R. Steinberg, editors, Combinatorial Auctions, pages 215–231. MIT Press, 2006. [27] N. Nisan and A. Ronen. Computationally feasible VCG mechanisms. Journal of Artificial Intelligence Research (JAIR), 29:19–47, 2007. [28] C. H. Papadimitriou and K. Steiglitz. Combinatorial optimization: algorithms and complexity. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1982. [29] D. C. Parkes, J. R. Kalagnanam, and M. Eso. Achieving budget-balance with vickrey-based payment schemes in exchanges. In Proceedings of 17th International Joint Conference on Artificial Intelligence (IJCAI-01), pages 1161–1168, 2001. [30] D. C. Parkes and L. H. Ungar. Preventing strategic manipulation in iterative auctions: Proxy agents and price-adjustment. In Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, pages 82–89, 2000. [31] R. Porter, A. Ronen, Y. Shoham, and M. Tennenholtz. Mechanism design with execution uncertainty. In Proceedings of Uncertainty in Artificial Intelligence (UAI ’02), pages 414– 421, 2002. [32] R. Porter, A. Ronen, Y. Shoham, and M. Tennenholtz. Fault tolerant mechanism design. Artificial Intelligence, 172(15):1783–1799, 2008. [33] S. D. Ramchurn, D. Huynh, and N. R. Jennings. Trust in multi-agent systems. The Knowledge Engineering Review, 19:1–25, 2004. [34] T. Sandholm. Expressive commerce and its application to sourcing: How we conducted 35 billion of generalized combinatorial auctions. AI Magazine, 28(3):45–58, 2007. [35] T. Sandholm, S. Suri, A. Gilpin, and D. Levine. Winner determination in combinatorial auction generalizations. In Proceeding of the 1st International Joint Conference on Autonomous Agents and Multiagent Systems, pages 69–76, 2001. [36] T. W. Sandholm. An implementation of the contract net protocol based on marginal cost calculations. In Proceedings of the 12th International Workshop on Distributed Artificial Intelligence, pages 295–308, 1993. [37] W. T. L. Teacy, J. Patel, N. R. Jennings, and M. Luck. Travos: Trust and reputation in the context of inaccurate information sources. Autonomous Agents and Multi-Agent Systems, 12(2):183–198, 2006. [38] W.E. Walsh and M.P. Wellman. A market protocol for decentralized task allocation. In Proceedings of the Third International Conference on Multi-Agent Systems (ICMAS-98), 1998.
URI:	http://wrap.warwick.ac.uk/id/eprint/1337

Request changes to a record

Actions (login required)

View Item