Skip to main navigation
Skip to Content
Computer Science
University of Toronto
U of T Portal
Student Support
Contact
About
History of U of T Computer Science
Computer Science at U of T Mississauga
Computer Science at U of T Scarborough
Employment Opportunities for Faculty/Lecturers
How to Find Us
Contact
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate Students
Current Graduate Students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
@DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> AI/Theory Seminar - July 20
About
Undergraduate
Graduate
Research
People
News & Events
AI/Theory Seminar - July 20
Event date: Friday, July 20, 2012, at 11:00 AM
Location: PT266
Speaker: Reshef Meir
Hebrew University
http://www.cs.huji.ac.il/~reshef24/
Title: Bounding the Cost of Stability in Games with Restricted Interaction
Abstract:
We study stability of cooperative games with restricted interaction, in the model that was introduced by Myerson ['77]. We show that the Cost of Stability of such games (i.e., the subsidy required to stabilize the game) can be bounded in terms of natural parameters of their interaction graphs. Specifically, we prove that if the treewidth of the interaction graph is k, then the relative cost of stability is at most k+1, and this bound is tight for all k>= 2. Also, we show that if the pathwidth of the interaction graph is k, then the relative cost of stability is at most k.
Joint work with Yair Zick, Edith Elkind, and Jeffrey S. Rosenschein.