skip to main content
10.1145/860575.860580acmconferencesArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
Article

Coalition formation in proportionally fair divisible auctions

Published:14 July 2003Publication History

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.

References

  1. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  2. S. H. Clearwater, editor. Market-Based Control: A Paradigm for Distributed Resource Allocation. World Scientific, Singapore, 1996. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  4. R. J. Gibbens and F. P. Kelly. Resource pricing and the evolution of congestion control. Automatica, 35(12):1969--1985, 1999. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. J. P. Kahan and A. Rapoport. Theories of Coalition Formation. Lawrence Erlbaum Associates, Hillsdale, NJ, 1984.Google ScholarGoogle Scholar
  6. F. Kelly. Charging and rate control for elastic traffic. European Transactions on Telecommunications, 8(1):33--37, January 1997.Google ScholarGoogle ScholarCross RefCross Ref
  7. 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 ScholarGoogle ScholarCross RefCross Ref
  8. J. O. Kephart, J. E. Hanson, and A. R. Greenwald. Dynamic pricing by software agents. Computer Networks, 32(6):731--752, May 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  10. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  11. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  12. U. Maheshwari. Charge-based proportional scheduling. Technical Memorandum MIT/LCS/TM-529, MIT Laboratory for Computer Science, January 1995. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. 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 ScholarGoogle ScholarCross RefCross Ref
  14. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  15. R. T. Maheswaran and T. Bacar. Nash equilibrium and decentralized negotiation in auctioning divisible resources. Group Decision and Negotiation, 13(2), May 2003.Google ScholarGoogle Scholar
  16. G. Owen. Game Theory. Academic Press, New York, third edition, 1995.Google ScholarGoogle Scholar
  17. L. A. Petrosjan and N. A. Zenkevich. Game Theory. World Scientific, Singapore, 1996.Google ScholarGoogle ScholarCross RefCross Ref
  18. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  19. 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 ScholarGoogle Scholar
  20. 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 ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Coalition formation in proportionally fair divisible auctions

      Recommendations

      Comments

      Login options

      Check if you have access through your login credentials or your institution to get full access on this article.

      Sign in
      • Published in

        cover image ACM Conferences
        AAMAS '03: Proceedings of the second international joint conference on Autonomous agents and multiagent systems
        July 2003
        1200 pages
        ISBN:1581136838
        DOI:10.1145/860575

        Copyright © 2003 ACM

        Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        • Published: 14 July 2003

        Permissions

        Request permissions about this article.

        Request Permissions

        Check for updates

        Qualifiers

        • Article

        Acceptance Rates

        Overall Acceptance Rate1,155of5,036submissions,23%

      PDF Format

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader