December 2, Thursday 10:15, CRI, room 570 Education Building

Cooperation, Power and Conspiracies

Lecturer : Yoram Bachrach

Lecturer homepage : http://research.microsoft.com/en-us/people/yobach/

Affiliation : Microsoft Research, Cambridge, UK

Cooperative game theory is all about how selfish agents might agree to collaborate 
and then share their spoils. It allows answering questions such as:
Would the political power balance change if a big party decided to split 
into two smaller parties?
How might pirates share a hidden treasure when they need each other to find it?
How can several buyers get their items for cheap prices?

Cooperation can be problematic when agents collaborate to attack an economic or 
political 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. This talk examines 
computational aspects of such phenomena, focusing on collusion in auctions and 
attacks in decision making bodies.

Auctions based on the VCG mechanism are excellent in achieving truthful bids and 
an optimal allocation when agents do not collude. However, they are very susceptible 
to collusion. I will demonstrate this in multi-unit auctions and path procurement 
auctions, showing how the colluders can compute their optimal joint bidding strategy 
and reasonable agreements for sharing the gains.
I will then consider attacks in weighted voting games, a known model for cooperation 
between agents in decision-making bodies, showing how agents can compute strategies 
that increase their power. 

The analysis for both domains is based on the core and the Shapley value, prominent 
solution concepts from cooperative game theory.