ABSTRACT
One method for agents to improve their performance is to form coalitions with other agents. One reason why this might occur is because different agents could have been created by the same owner so an incentive to cooperate naturally exists. Competing agents can also choose to coordinate their actions when there is a mutually beneficial result. The emergence and effects of cooperation depend on the structure of the game being played. In this paper, we study a proportionally fair divisible auction to manage agents bidding for service from network and computational resources. We first show that cooperation is a dominant strategy against any fixed level of competition. We then investigate whether collusion can undermine a noncooperative equilibrium solution, i.e. allow an agent priced out of the noncooperative game to enter the game by teaming with other agents. We are able to show that agents not receiving service after a bid equilibrium is reached cannot obtain service by forming coalitions. However, cooperation does allow the possibility that agents with positive allocations can improve their performance. To know whether or not to cooperate with another agent, one must devise a way of assigning a value to every coalition. In classical cooperative game theory, the value of a team is the total utility of the team under the worst case response of all other agents, as a coalition is viewed as a threat by the remaining agents. We show that this analysis is not appropriate in our case. The formation of a coalition under a proportionally fair divisible auction improves the performance of those outside the coalition. This then creates an incentive structure where team play is encouraged.
- J. Q. Cheng and M. P. Wellman. The WALRAS algorithm: a convergent distributed implementation of general equilibrium outcomes. Journal of Computational Economics, 12:1--23, 1998. Google ScholarDigital Library
- S. H. Clearwater, editor. Market-Based Control: A Paradigm for Distributed Resource Allocation. World Scientific, Singapore, 1996. Google ScholarDigital Library
- R. A. Gagliano, M. D. Fraser, and M. E. Schaefer. Auction allocation for computing resources. Communications of the ACM, 38(6):88--102, June 1995. Google ScholarDigital Library
- R. J. Gibbens and F. P. Kelly. Resource pricing and the evolution of congestion control. Automatica, 35(12):1969--1985, 1999. Google ScholarDigital Library
- J. P. Kahan and A. Rapoport. Theories of Coalition Formation. Lawrence Erlbaum Associates, Hillsdale, NJ, 1984.Google Scholar
- F. Kelly. Charging and rate control for elastic traffic. European Transactions on Telecommunications, 8(1):33--37, January 1997.Google ScholarCross Ref
- F. Kelly, A. Maulloo, and D. Tan. Rate control for communication networks: shadow prices, proportional fairness and stability. Journal of the Operations Research Society, 49(3):237--252, March 1998.Google ScholarCross Ref
- J. O. Kephart, J. E. Hanson, and A. R. Greenwald. Dynamic pricing by software agents. Computer Networks, 32(6):731--752, May 2000. Google ScholarDigital Library
- T. W. Sandholm V. R. Lesser. Coalition formation among bounded rational agents. In 14th International Joint Conference on Artificial Intelligence, pages 662--669, Montreal, Canada, August 1996. Google ScholarDigital Library
- P. Stone M. P. Wellman, A. Greenwald and P. R. Wurman. The 2001 trading agent competition. In 14th Conference on Innovative Applications of Artificial Intelligence, pages 935--941, Edmonton, 2002. Google ScholarDigital Library
- J. K. MacKie-Mason and H. R. Varian. Pricing the internet. In Public Access to the Internet, JFK School of Government, May 26--27 1993. Google ScholarDigital Library
- U. Maheshwari. Charge-based proportional scheduling. Technical Memorandum MIT/LCS/TM-529, MIT Laboratory for Computer Science, January 1995. Google ScholarDigital Library
- R. T. Maheswaran and T. Bacar. Decentralized network resource allocation as a repeated noncooperative market game. In Proceedings of the 40th IEEE Conference on Decision and Control, pages 4565--4570, Orlando, FL, December 4--7 2001.Google ScholarCross Ref
- R. T. Maheswaran and T. Bacar. Auctions for divisible resources: price functions, nash equilibria and decentralized update schemes. In AAMAS 2002: Workshop on Agent-Mediated Electronic Commerce IV, Bologna, Italy, July 2002. Google ScholarDigital Library
- R. T. Maheswaran and T. Bacar. Nash equilibrium and decentralized negotiation in auctioning divisible resources. Group Decision and Negotiation, 13(2), May 2003.Google Scholar
- G. Owen. Game Theory. Academic Press, New York, third edition, 1995.Google Scholar
- L. A. Petrosjan and N. A. Zenkevich. Game Theory. World Scientific, Singapore, 1996.Google ScholarCross Ref
- O. Regev and N. Nisan. The popcorn market: An online market for computational resources. In Proceedings of the 1st International Conference on Information and Computational Economies, pages 148--157, Charleston, SC, October 1998. Google ScholarDigital Library
- T. W. Sandholm. Limitations of the Vickrey auction in computational multiagent systems. In Proceedings of the 2nd International conference on Multi-Agent Systems, pages 299--306, Kyoto, Japan, December 1996.Google Scholar
- I. Stoica, H. Abdel-Wahab, K. Jeffay, S. K. Baruah, J. E. Gehrke, and C. G. Plaxton. A proportional share resource allocation algorithm for real-time time-shared systems. In Proceedings of the 17th IEEE Real-Time Systems Symposium, pages 288--299, Washington, D.C., December 1996. Google ScholarDigital Library
Index Terms
Coalition formation in proportionally fair divisible auctions
Recommendations
Coalition Formation Strategies for Multiagent Hedonic Games
ICTAI '10: Proceedings of the 2010 22nd IEEE International Conference on Tools with Artificial Intelligence - Volume 01In a multiagent system, coalition formation is a coordination method for agents aiming to form groups of interest. In this paper, we focus on the particular context of hedonic games. In hedonic games, the objective of the agents is to form coalitions, ...
Coalition Formation: From Software Agents to Robots
A problem that has recently attracted the attention of the research community is the autonomous formation of robot teams to perform complex multi-robot tasks. The corresponding problem for software agents is also known in the multi-agent community as ...
Combinatorial Coalition Formation for multi-item group-buying with heterogeneous customers
A group-buying market may offer multiple items with non-additive values (i.e., items may be complementary or substitutable), to buyers who are often heterogeneous in their item valuations. In such a situation, the formation of buying groups should ...
Comments