Coalition Formation in Proportionally Fair Divisible Auctions

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.