CRCS Lunch Seminar

Date: Wednesday, November 6, 2013
Time: 12:00pm – 1:30pm
Place: Maxwell Dworkin 119

Speaker: Reshef Meir, Harvard CRCS

Title: Cooperation in Social Networks, and the Cost of Stability

Abstract: Cooperative game theory is concerned with how groups of agents (people, automated agents, companies, etc.) divide profits from cooperation in a stable way. In many scenarios, the set of stable payoff allocation (the core of the game) is empty,which means that stability cannot be achieved without external subsidy. The minimal subsidy required to guaranty cooperation is known as the Cost of Stability.

Cooperative games on graphs where introduced by Myerson ['77], inspired by the observation that coalitions can only form via social connections. Several researchers thereafter showed that if the social network is a tree, then cooperation can always be achieved without subsidy.

We extend this result to general networks. We prove a tight bound on the cost of stability of any game given the tree-width of the underlying network. In other words, as a network is more similar to a tree, games played over it are inherently more stable.

Joint work with Yair Zick, Edith Elkind, and Jeffrey S. Rosenschein.

The talk is based on the following paper:
https://docs.google.com/file/d/0B6hxv6XOx1PxWjMxU2d4MEU5UnM/edit?usp=sharing

Short bio: I am a post-doctoral fellow at the Center for Research on Computation and Society (CRCS), having completed my PhD at the School of Computer Science and Engineering of The Hebrew University in Jerusalem, Israel.

My main research areas are Computational Game Theory and Mechanism Design. In particular, I study mechanisms that promote cooperation, stability, and social welfare.