| DATE: | Monday, August 4th |
| TIME: | 4:00 PM - 5:00 PM |
| PLACE: | McConnell 103 |
| TITLE: | Fair cost allocations under conflicts |
| SPEAKER: | Yoshio Okamoto (ETH Zurich) |
We study the cost allocation problem when the players are involved in a
conflict situation from the game-theoretic point of view. More formally,
we investigate some algorithmic aspects of a minimum coloring game
introduced by Deng, Ibaraki & Nagamochi. In this talk, we will start with
basic definitions from cooperative game theory and give an overview of the
known results (about the cores) on minimum coloring games. Then we will
look at new results obtained by the speaker concerning with the core, the
tau-value, the nucleolus and the Shapley value on some classes of graphs.
The investigation gives several insights to the relationship of algorithm
theory with cooperative games. The talk should not require a particular
familiarity with game theory.