Trade of a problem-solving task

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Trade of a problem-solving task

Full text

Pdf (303 KB)

Source

International Conference on Autonomous Agents archive
Proceedings of the second international joint conference on Autonomous agents and multiagent systems table of contents

Melbourne, Australia

SESSION: Game theory (II) table of contents

Pages: 257 - 264

Year of Publication: 2003

ISBN:1-58113-683-8

Author

Shigeo Matsubara

NTT Communication Science Laboratories, NTT Corporation, Kyoto, Japan

Sponsors

SIGART: ACM Special Interest Group on Artificial Intelligence
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 21, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/860575.860617 What is a DOI?

ABSTRACT

This paper focuses on a task allocation problem, particularly in cases where the task is to find a solution to a search problem or a constraint satisfaction problem. If the search problem is difficult to solve, a contractor may fail to find a solution. Here, the more computational resources, such as the CPU time, the contractor invests in solving the search problem, the more likely a solution will be found. This brings about a new problem in which a contractee has to find an appropriate quality level in task achievement as well as to efficiently allocate a task among contractors. For example, if the contractee asks the contractor to find a solution with certainty, the payment from the contractee to the contractor may exceed the contractee's benefit from obtaining a solution, which discourages the contractee from trading a task. However, it is difficult to solve this problem because the contractee cannot ascertain the contractor's problem-solving ability such as the amount of available resources and knowledge (e.g. algorithms, heuristics) nor monitor how many resources are actually invested in solving the allocated task. To solve this problem, we propose a task allocation mechanism that is able to choose an appropriate quality level in task achievement and prove that this mechanism guarantees that each contractor reveals its true information. Moreover, we show that our mechanism can increase the contractee's utility compared with a simple auction mechanism by using computer simulations.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	L. M. Ausubel and P. Cramton. Demand reduction and inefficiency in multi-unit auctions. Working Paper, 1998.
	2	Yuzo Fujishima , David McAdams , Yoav Shoham, Speeding Up Ascending-Bid Auctions, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.554-563, July 31-August 06, 1999
	3	Tad Hogg , Colin P. Williams, The hardest constraint problems: a double phase transition, Artificial Intelligence, v.69 n.1-2, p.359-377, Sept. 1994 [doi>10.1016/0004-3702(94)90088-4]
	4	J.-J. Laffont and J. Tirole. Auctioning incentive contracts. Journal of Political Economy, 95(5):921--937, 1987.
	5	Kate Larson , Tuomas Sandholm, Bargaining with limited computation: deliberation equilibrium, Artificial Intelligence, v.132 n.2, p.183-217, November 2001 [doi>10.1016/S0004-3702(01)00132-1]
	6	S. Matsubara and M. Yokoo. Defection-free exchange mechanisms based on an entry fee imposition. Artificial Intelligence Journal, 142(2):265--286, 2002.
	7	R. P. McAfee and J. McMilan. Bidding for contracts: a principal-agent analysis. Rand Journal of Economics, 17(3):326--338, 1986.
	8	D. G. Mitchell, B. Selman, and H. J. Levesque. Hard and easy distributions of SAT problems. In Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI-92), pages 459--465, 1992.
	9	D. C. Parkes, J. Kalagnanam, and M. Eso. Achieving budget-balance with Vickrey-based payment schemes in exchanges. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI-01), pages 1161--1168, 2001.
	10	R. Porter, A. Ronen, Y. Shoham, and M. Tennenholtz. Mechanism design with execution uncertainty. In Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence (UAI-02), 2002.
	11	E. Rasmusen. Games and Information: an introduction to game theory. Blackwell Publishers, 3rd edition, 2001.
	12	B. Salanié. The Economics of Contracts. MIT Press, 1997.
	13	T. W. Sandholm. Limitation of the Vickrey auction in computational multiagent systems. In Proceedings of the Second International Conference on Multi-Agent Systems (ICMAS-96), pages 299--306, 1996.
	14	D. E. M. Sappington. Incentives in principal-agent relationships. Journal of Economic Perspectives, 5(2):45--66, 1991.
	15	M. P. Wellman, W. E. Walsh, P. R. Wurman, and J. K. MacKie-Mason. Auction protocols for decentralized scheduling. Games and Economic Behavior, 35(1):271--303, 2001.
	16	Makoto Yokoo , Yuko Sakurai , Shigeo Matsubara, Robust combinatorial auction protocol against false-name bids., Artificial Intelligence, v.130 n.2, p.167-181, 08/01/2001 [doi>10.1016/S0004-3702(01)00077-7]