"Overlapping Coalition Formation Games: Charting the Tractability Frontier"

Speaker: Yair Zick, Nanyang Technological University
Date: Wednesday, 21 December 2011
Time: 12noon
Place: Ross 201

Abstract:

Cooperative games with overlapping coalitions (OCF games) model
scenarios where agents can distribute their resources among several
tasks; each task generates a profit which may be freely divided among
the agents participating in the task.  The goal of this work is to
initiate a systematic investigation of algorithmic aspects of OCF
games. We propose a discretized model of overlapping coalition
formation, where each agent $i \in N$ has a weight $w_i \in \N$ and
may allocate an integer amount of resources to any task. Within this
framework, we focus on the computation of outcomes that are socially
optimal and/or stable. We discover that the algorithmic complexity of
the associated problems crucially depends on the amount of resources
that each agent possesses, the maximum coalition size, and the pattern
of interaction among the agents. We identify several constraints that
lead to tractable subclasses of OCF games, and provide efficient
algorithms for games that belong to these subclasses. We supplement
our tractability results by hardness proofs, which clarify the role of
our constraints.