Abstract

Cooperative game theory is all about how selfish agents might agree to collaborate and then share their spoils. It allows answering questions such as: - Can a political party increase its influence by splitting into two parties? - How would owners of compute clusters agree to share the gains from running a task in the cloud? - What conspiracies could allow advertisers on our Bing platform to lower their costs at our expense?

Cooperation can be problematic when agents collaborate to attack a political or economic system. For example, agents participating in an auction can coordinate their bids in order to pay less for obtaining their items and political parties may strategically merge or split to increase their influence. In weighted voting games, a known model for decision-making bodies, false-name attacks where agents merge and split can dramatically influence the distribution of power. Similarly, auctions based on the VCG mechanism are excellent in achieving truthful bids and an optimal allocation when agents do not cooperate, but are very susceptible to collusion. I will demonstrate such attacks in political systems and multi-unit auctions, showing how the colluders can find their optimal joint attack strategies and reasonable agreements for sharing the gains. The analysis for both domains is based on the core and the Shapley value, prominent solution concepts from cooperative game theory.

Finally, I will consider the implications of such attacks for cloud computing environments and sponsored search auctions on Bing.