of 8
Current View
Taxation and Stability in Cooperative Games
Yair Zick
School of Physical and
Mathematical Sciences
Nanyang Technological
University, Singapore
yair0001@ntu.edu.sg
Maria Polukarov
School of Electronics and
Computer Science
University of Southampton, UK
mp3@ecs.soton.ac.uk
Nicholas R. Jennings
School of Electronics and
Computer Science
University of Southampton, UK
nrj@ecs.soton.ac.uk
ABSTRACT
Cooperative games are a useful framework for modeling multi-
agent behavior in environments where agents must collabo-
rate in order to complete tasks. Having jointly completed a
task and generated revenue, agents need to agree on some
reasonable method of dividing pro ts among themselves.
One family of payo divisions that is seen as particularly
appealing is the
core
, which consists of all coalitionally ra-
tional (or, stable) payo divisions. Unfortunately, it is often
the case that the core of a game is empty, i.e. there is no pay-
o scheme guaranteeing each group of agents a total payo
higher than what they can get on their own.
As stability is a highly attractive property, there have been
various methods of achieving it proposed in the literature. In
particuar, a natural way of stabilizing a game is by taxation,
i.e. reducing the value of some coalitions in order to decrease
their bargaining power. Existing taxation methods include
the concepts of
"
-core, the least-core and several others.
However, taxing coalitions is in general undesirable: one
would not wish to overly tamper with a given coalitional
game, or overly tax the agents. Thus, in this work we study
minimal taxation policies, i.e. those minimizing the amount
of tax required in order to stabilize a given game. We show
that games that minimize the total tax are to some extent a
linear approximation of the original games, and explore their
properties. We demonstrate connections between the mini-
mal tax and the cost of stability, and characterize the types
of games for which it is possible to obtain a tax-minimizing
policy using variants of notion of the
"
-core, as well as those
for which it is possible to do so using reliability extensions.
Categories and Subject Descriptors
I.2.11 [
Distributed Arti cial Intelligence
]: Multiagent
Systems
General Terms
Theory
Keywords
Cooperative Games, Core Stability, Optimal Taxation Schemes
Appears in:
Proceedings of the 12th International Confer-
ence on Autonomous Agents and Multiagent Systems (AA-
MAS 2013)
, Ito, Jonker, Gini, and Shehory (eds.), May, 6–10, 2013,
Saint Paul, Minnesota, USA.
Copyright
c
2012, International Foundation for Autonomous Agents and
Multiagent Systems (www.ifaamas.org). All rights reserved.
1. INTRODUCTION
The theory of cooperative games with transferable utility
(TU games) has been widely used in multi-agent systems to
study scenarios where groups of agents may form coalitions
and generate pro ts. Formally, a
TU cooperative game
G
is
given by a set of agents
N
=
f
1
;:::;n
g
and a
characteris-
tic function
v
: 2
N
!
R
, assigning a value to each subset
S
N
. It is often assumed that agents will form the
grand
coalition
, i.e. the set of all agents
N
. However, in some cases
agents may form
coalition structures
[1]; that is, agents split
into disjoint coalitions, which work independently in order
to maximize total revenue. Our focus is on the former ap-
proach, where the grand coalition is formed.
1
Having formed the grand coalition, agents must decide
on some reasonable payo division. Payo division schemes
are known in the literature as
solution concepts
(see [14]
and [5] for a review of common solution concepts); a solution
concept is a mapping whose input is a cooperative game
G
,
and whose output is a set of payo divisions. The
core
[7]
is arguably the most prominent solution concept; a payo
division is said to be in the core of
G
(denoted
Core
(
G
)) if
no subset of agents can get more by leaving the group and
working on their own, i.e. the total payo to every subset of
agents
S
is at least its value
v
(
S
). Thereby, core outcomes
capture the notion of
stability
in cooperative games; this
is because under a core outcome, no subset of agents can
pro tably deviate. Unfortunately though, many cooperative
games have an empty core; this means that no matter how
agents divide their pro ts, there will always be a subset of
agents that is paid less than what it can make on its own.
1.1 Relaxing the Core Requirement
Core stability is a highly desirable, but rarely achievable,
property; thus, one would ideally like to maintain a set of
\somewhat" stable payo s when the core is empty. This can
be done via several approaches. First, one may drop the
stability requirement and focus on other types of solution
concepts, for which a payo division is guaranteed to exist.
Such solutions, in particular, include the
nucleolus
[15] and
the
bargaining set
[6], and have their own justi cations and
appeal: for example, the nucleolus of a cooperative game
is a payo division scheme that minimizes some measure of
unhappiness in the game.
An alternative approach would be to stabilize the game
1
We do not use coalition structures both for the sake of
simplicity and in order to maintain consistency with other
solution concepts, which often do not utilize coalition struc-
tures in their de nitions.

via external subsidies. Intuitively, a game is not stable since
the grand coalition is unable to generate enough revenue to
satisfy the demands of each subset of agents. An external
party that is interested in stabilizing the game provides a
subsidy to the agents if they form the grand coalition, and
thus a value of
v
(
N
) is divided among them, where
1.
Clearly, any game can be stabilized using a large enough
;
however, the external party would naturally be interested in
the
minimal subsidy
required in order to stabilize the game.
Finally, a game can be stabilized by relaxing the core con-
straints. For example, it is often reasonable to assume that
a subset of agents would not choose to deviate if the addi-
tional payment they can secure by deviating does not exceed
some
" >
0, i.e. a coalition will choose to deviate only if a
substantial gain can be made by deviating, as deviation it-
self is a costly act. Alternatively, the
"
can be thought of
as a
tax
imposed on a coalition should it choose to deviate;
again, this can be viewed as some external party wishing to
stabilize the game, but doing so via reducing the bargaining
power of subsets of
N
, rather than increasing the desirabil-
ity of
N
itself. Formally, given a game
G
, the game
G
"
has
the value of every coalition except
N
reduced by some
"
.
It is easy to see that for a large enough
"
, the game
G
"
is
stable. Note that it can also be assumed that
" <
0; that is,
if the game is stable, it may be possible to add a value of
"
to the value of each coalition
S
N
(except
N
itself), thus
increasing the bargaining power of sub-coalitions. Since our
focus in this work is on stabilizing games whose cores are
empty, we assume from now on that
"
0. Again, we are
interested in the
smallest
possible
"
for which
G
"
is stable, as
that minimal
"
corresponds to the minimal change required
in order to stabilize the game via
"
reductions. This gives
rise to the notion of the
strong least core
, which corresponds
to the
"
-core where
"
is the smallest value for which the
game
G
"
has a non-empty core. Variants of the strong-
"
core exist, each corresponding to a di erent method of tax-
ation (see Section 2 for a more detailed discussion).
The study of taxation as a method of stabilizing coop-
erative games is not recent; these notions have been rst
explored in [9], where the geometry of the least core and
its connection to the nucleolus and other solution concepts
have been established. More recently, Bejan and Gomez [4]
study the properties of individual taxation schemes. Specif-
ically, given a game
G
, they consider various ways in which
an individual taxation scheme (i.e. a mapping from a game
to a vector in
R
n
) can stabilize a game, and explore their
properties. Moreover, Bejan and Gomez show a connection
between an optimal individual taxation scheme (i.e. one
that minimizes the total amount of tax taken from individ-
uals) and the cost of stability (i.e., the minimal subsidy to
the value of the grand coalition required in order to stabi-
lize the game). The goal of their work is to provide axioms
which would hold for those taxation schemes that coincide
with the core whenever the core is not empty, i.e. taxation
schemes that do not tax individuals at all if the game is
stable to begin with. In this sense, our approach is similar:
the taxation notion we propose results in the core if this is
not empty. However, unlike Bejan and Gomez, we study
group taxation schemes
, where the value of each coalition
is reduced by a certain value, until the resulting game is
stable. As we demonstrate, taking this approach results in
signi cantly lower taxes for coalitions.
Also in this line of work, Gonzales and Grabisch [8] study a
generalization of the extended core proposed by Bejan and
Gomez [4], where a tax is only employed on coalitions of
size at most
k
. Speci cally, they look for games that min-
imize the di erence between a group taxation scheme and
an individual taxation scheme. The reasoning behind this
methodology is simple: when a tax (or a payo ) is set upon
sets rather than individuals, the sets of agents must bargain
among themselves in order to agree on the way in which the
tax should be divided. Thus, studying group taxation that
minimizes the number of taxes on sets makes sense, as it
minimizes the amount of complicated bargaining that the
agents must undergo. In contrast, in our setting, we do not
address the way in which taxes are distributed among sub-
coalition members; rather, our results show that individual
taxation does naturally arise in the setting that we propose.
In the class of games that we study, the value of a blocking
coalition is replaced by a value set by an additive vector,
whose coordinates induce an individual tax.
Independent of the previous work, Bachrach et al. [2]
study the
cost of stability
in coalitional games. The cost of
stability is the minimal external subsidy to the grand coali-
tion that is required in order to stabilize a given cooperative
game. The authors [2] provide bounds on the amount of
subsidy required for various classes of cooperative games.
Additional bounds have been recently provided by Meir et
al. [10] and Meir et al. [11]. In our work, we provide an ex-
plicit upper bound for the class of superadditive, anonymous
games, and explore its connection to the bound presented
in [2] for the same class. We show that for small enough
coalitions (namely, those whose size is at most
n
2
), an opti-
mal taxation policy is guaranteed to impose a lower tax than
that used when computing the cost of stability; moreover,
we show a relation between the amount of savings induced
and the size of a coalition, with smaller coalitions guaran-
teed better tax reductions than larger coalitions. This result
is particularly appealing, as it is often assumed that smaller
coalitions are likelier to form than larger ones, thus ensuring
a low tax on such coalitions is paramount.
As can be seen, the cost of stability, the least core, the
concepts studied by Bejan & Gomez [4] and Gonzales &
Grabisch [8] are aimed at nding the minimal amount of
change required to stabilize a given cooperative game
G
.
We continue in this line of work, with the aim of nding
the minimal amount of
taxation
required in order to achieve
core stability.
1.2 Our Contribution
Against this background, we analyze scenarios where min-
imal taxation is employed in order to achieve stability in
cooperative games. In particular, given a cooperative game
G
, we examine the set of all
stable
cooperative games that
are dominated by
G
, i.e. their characteristic functions give
a lower value to each coalition
S
N
. These games include
all games that correspond to the
"
-core of
G
and, in par-
ticular, the game corresponding to the least-core of
G
, the
notions described by Bejan and Gomez, and other notions
such as graph restrictions [12] and reliability extensions [3].
We then proceed to look at the set of games on the e-
cient face of the polytope of stable games dominated by
G
.
We give a complete characterization of these games, which
we term
maximal-stable games
; brie y, one can construct a
maximal-stable game by replacing the value of every block-
ing coalition (i.e. one violating the core constraints) by a