Coalition Formation in Proportionally Fair Divisible Auctions

Rajiv T. Maheswaran, M Tamer Basar

Research output: Contribution to conferencePaper

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.

Original languageEnglish (US)
Pages25-32
Number of pages8
StatePublished - Dec 1 2003
EventProceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 03 - Melbourne, Vic., Australia
Duration: Jul 14 2003Jul 18 2003

Other

OtherProceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 03
CountryAustralia
CityMelbourne, Vic.
Period7/14/037/18/03

Fingerprint

Game theory

Keywords

  • Coalition Formation
  • Divisible Auctions
  • E-Commerce
  • Game Theory
  • Market Mechanisms
  • Multiagent Systems
  • Resource Allocation
  • Software Agents

ASJC Scopus subject areas

  • Engineering(all)

Cite this

Maheswaran, R. T., & Basar, M. T. (2003). Coalition Formation in Proportionally Fair Divisible Auctions. 25-32. Paper presented at Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 03, Melbourne, Vic., Australia.

Coalition Formation in Proportionally Fair Divisible Auctions. / Maheswaran, Rajiv T.; Basar, M Tamer.

2003. 25-32 Paper presented at Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 03, Melbourne, Vic., Australia.

Research output: Contribution to conferencePaper

Maheswaran, RT & Basar, MT 2003, 'Coalition Formation in Proportionally Fair Divisible Auctions' Paper presented at Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 03, Melbourne, Vic., Australia, 7/14/03 - 7/18/03, pp. 25-32.
Maheswaran RT, Basar MT. Coalition Formation in Proportionally Fair Divisible Auctions. 2003. Paper presented at Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 03, Melbourne, Vic., Australia.
Maheswaran, Rajiv T. ; Basar, M Tamer. / Coalition Formation in Proportionally Fair Divisible Auctions. Paper presented at Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 03, Melbourne, Vic., Australia.8 p.
@conference{c8b8143138d74b59824071a20a95626d,
title = "Coalition Formation in Proportionally Fair Divisible Auctions",
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.",
keywords = "Coalition Formation, Divisible Auctions, E-Commerce, Game Theory, Market Mechanisms, Multiagent Systems, Resource Allocation, Software Agents",
author = "Maheswaran, {Rajiv T.} and Basar, {M Tamer}",
year = "2003",
month = "12",
day = "1",
language = "English (US)",
pages = "25--32",
note = "Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 03 ; Conference date: 14-07-2003 Through 18-07-2003",

}

TY - CONF

T1 - Coalition Formation in Proportionally Fair Divisible Auctions

AU - Maheswaran, Rajiv T.

AU - Basar, M Tamer

PY - 2003/12/1

Y1 - 2003/12/1

N2 - 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.

AB - 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.

KW - Coalition Formation

KW - Divisible Auctions

KW - E-Commerce

KW - Game Theory

KW - Market Mechanisms

KW - Multiagent Systems

KW - Resource Allocation

KW - Software Agents

UR - http://www.scopus.com/inward/record.url?scp=1142268801&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=1142268801&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:1142268801

SP - 25

EP - 32

ER -