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 prots 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 Articial 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 prots. 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

protably deviate. Unfortunately though, many cooperative

games have an empty core; this means that no matter how

agents divide their prots, 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 payos 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 justications 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 denitions.

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 dierent 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

signicantly 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

. Specically, they look for games that min-

imize the dierence 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