of 8
Current View
Matchings with Externalities and Attitudes
Simina Brânzei
Aarhus University
simina@cs.au.dk
Tomasz Michalak
Oxford University and Warsaw University
tomasz.michalak@cs.ox.ac.uk
Talal Rahwan
University of Southampton
tr@ecs.soton.ac.uk
Kate Larson
University of Waterloo
klarson@cs.uwaterloo.ca
Nicholas R. Jennings
University of Southampton
nrj@cs.soton.ac.uk
\A pessimist sees the diculty in every opportunity; an
optimist sees the opportunity in every diculty."
Winston Churchill (1874{1965)
ABSTRACT
Two-sided matchings are an important theoretical tool used
to model markets and social interactions. In many real-life
problems the utility of an agent is in uenced not only by
their own choices, but also by the choices that other agents
make. Such an in uence is called an externality. Whereas
fully expressive representations of externalities in matchings
require exponential space, in this paper we propose a com-
pact model of externalities, in which the in uence of a match
on each agent is computed additively. Under this framework,
we analyze many-to-many matchings and one-to-one match-
ings where agents take di erent
attitudes
when reasoning
about the actions of others. In particular, we study opti-
mistic, neutral and pessimistic attitudes and provide both
computational hardness results and polynomial-time algo-
rithms for computing stable outcomes.
Keywords
Matchings, Externalities, Coalitional Games
General Terms
Algorithms, Economics, Theory
Categories and Subject Descriptors
I.2.11 [
Distributed Arti cial Intelligence
]: Multiagent
Systems; J.4 [
Social and Behavioral Sciences
]: Eco-
nomics
1. INTRODUCTION
Matching games are an important theoretical abstraction
which have been extensively studied in several elds, includ-
ing economics, combinatorial optimization and computer sci-
ence. Matchings are often used to model markets, and exam-
ples include the classic marriage problem, rms and workers,
schools and students, hospitals and medical interns [4].
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.
Previous matching literature has focused primarily on one-
to-one and one-to-many models [14]. More recently, how-
ever, attention is being paid to more complex models of
many-to-many matchings due to their relevance to real-world
situations [6, 11]. For example, most labour markets in-
volve at least a few many-to-many contracts [6]. More re-
alistic matching models should take into account the fact
that in many settings the utility of an agent is in uenced
not only by their own choices, but also by the choices that
other agents make. Such an in uence is called an externality.
For instance, companies care not only about the employees
they hire themselves, but also about the employees hired
by other companies. This aspect is crucial to how compet-
itive a company is in the market, and so externalities must
be considered in order to completely understand such situa-
tions. While researchers have looked at externalities in one-
to-one matchings (
e.g.
[9, 15]) and one-to-many matchings
(
e.g.
[5]), typically fully expressive respresentations for the
externalities were assumed.
1
Modelling matchings with ex-
ternalities is computationally challenging, as fully expressive
representations require exponential space. This motivates
the search for compact representations of externalities.
One of the central questions in matching games is stabil-
ity [14], which informally means that no group of agents can
modify the matching and improve the outcome for them-
selves. In the presence of externalities, stability becomes a
highly complex and challenging phenomenon due to the fact
that a deviation by some agents can a ect the utilities of
all other agents in the system. This can invoke a response
that can change the worth of the original deviation dra-
matically, and so any group considering a deviation should
consider all possible responses that can be taken by the re-
maining agents. Evaluating these may be infeasible, par-
ticularly for agents with computational limitations or who
have bounds on their rationality. Motivated by both the co-
operative game theory literature (
e.g.
[12, 13]), and work on
models of bounded rationality [8], we argue that agents will
use
heuristics
, which are based on their
attitudes
(
i.e.
opti-
mistic, neutral, or pessimistic), to reason about the actions
taken by others.
Our contributions in this paper can be summarized as fol-
lows. We formulate a compact model of externalities for
matchings, in which the in uence of matches on agents is
computed additively. Second, we consider key stability con-
1
An interesting exception is work by Bodine-Baron
et
al.
which looked at a one-to-many matching problem where
externalities were derived from an underlying social net-
work [2].
cepts for matching, under optimistic, neutral and pessimistic
attitudes. We study the computational properties of these
stability concepts, provide both hardness results and poly-
nomial algorithms where applicable, and show how the sta-
bility concepts under di erent attitudes are related to each
other.
2. THE MODEL
Let
N
=
M
[
W
be the set of agents, where
M
=
f
m
1
;
:::; m
j
M
j
g
and
W
=
f
w
1
; :::; w
j
W
j
g
are disjoint. A
match
,
(
m;w
), is an edge between two agents
m
2
M
and
w
2
W
. We let a matching,
A
, be a set of all matches. If the
number of allowable matches any agent can participate in is
unrestricted then we say we have a
many-to-many matching
problem
, while if each agent can participate in at most one
match then we have a
one-to-one matching problem
. We
assume the formation of a match requires the consent of
both parties, while severing a match can be done unilaterally
by any of its endpoints. The
empty matching
contains no
matches, while the
complete matching
contains all possible
matches. A matching game with externalities is de ned as
follows:
Definition
1.
A
matching game with externalities
is rep-
resented as a tuple
G
= (
M;W;
)
, where
(
M;W
)
is the set
of agents and
is a real valued function such that
(
Aj
z
)
is the utility of agent
z
when matching
A
forms.
We make no assumptions as to whether the utility of the
agents is transferrable or not and thus De nition 1 can be
viewed as a generalization of assignment games with exter-
nalities [15]. We are interested in settings where an agent's
utility is formed by additive externalities.
Definition
2.
A
matching game with additive external-
ities
is represented as a tuple
G
= (
M;W;
)
, where
(
M;W
)
is the set of agents and
is a real valued function such that
(
m;w
j
z
)
is the value that agent
z
receives from the forma-
tion of match
(
m;w
)
. Given a matching
A
over
N
, the
util-
ity
of an agent
z
in
A
is:
u
(
z;
A
) =
P
(
m;w
)
2A
(
m;w
j
z
)
.
Thus, in a matching game with additive externalities, an
agent's utility is the sum of values it receives from matches
it participates in, along with the sum of all externalities
that arise due to the matchings of other agents. We study
additive externalities since they are a conceptually straight-
forward compact representation and assumptions about ad-
ditive utility functions are wide spread throughout the ar-
ti cial intelligence and algorithmic game theory literature
(
e.g.
[1, 2, 3] ).
2.1 Stability Concepts
We are interested in whether matchings are
stable
and
whether there exist stable matchings given a particular match-
ing game,
G
. In general, a matching is stable if no subset of
agents has any incentive to reorganize and form new match-
ings amongst themselves. We distinguish between three
standard stability concepts which commonly appear in the
matching literature. The rst, setwise stability, is the most
general and encompasses the other two (corewise stability
and pairwise stability). Unless otherwise noted, the stabil-
ity concept used in this paper is setwise stability, which we
interchangeably refer to as set stability.
Definition
3.
Given a matching game
G
= (
M;W;
)
,
a matching
A
of
G
is
setwise stable
if there does not exist
a set of agents
B
N
, which can improve the utility of at
least one member of
B
while not degrading the others by:
rearranging the matches among themselves
deleting a (possibly empty) subset of the matches with
agents in
N
n
B
.
If such a coalition
B
, exists, it is called a
blocking coalition
.
Definition
4.
Given a matching game
G
= (
M;W;
)
,
a matching
A
of
G
is
corewise stable
if there does not exist
a set of agents
B
N
, which can improve the utility of at
least one member of
B
while not degrading the others by:
rearranging the matches among themselves
deleting all the matches with agents in
N
n
B
.
Definition
5.
Given a matching game
G
= (
M;W;
)
and a matching
A
,
A
is
pairwise stable
if there does not
exist a blocking coalition of size one or two.
Pairwise stability is most interesting for one-to-one match-
ings. In the context of one-to-one matchings, a blocking
coalition of size one is equivalent to one agent that can im-
prove utility by cutting its matches. A blocking coalition
of size two is equivalent to two agents that can form a new
match with each other while possibly cutting their previous
match (if any), or who can coordinate to cut their existing
matches without forming a new match with each other.
Finally, we note that each member of a blocking coalition
B
is required to perform at least one action, by severing a
match with another agent in
N
, or by forming a new match
with another agent in
B
. Other de nitions of stability could
incorporate di erent layers of deviators, such as agents who
perform the deviation and agents who agree to it without ac-
tively participating. However, such de nitions can be prob-
lematic, and require specifying which agents are identi ed
as deviators and how they should be treated depending on
their role. For this reason, in this paper we only consider
one type of deviators, those who are required to perform at
least one action.
2.2 Agents’ Attitudes
In matching games without externalities, the actions taken
by other agents have only a limited e ect on an agent { its
utility depends solely on who it is matched with, and does
not depend on matches involving others. However, if there
are externalities then this is no longer true. The utility of
agent
m
, for example, can depend on the matches involving
agent
w
even if (
m;w
)
62A
. Therefore, we argue, the stabil-
ity concepts need to account for the actions taken by agents
in
N
n
B
after a deviation by coalition
B
. However, it may
be hard to compute the possible reactions to a deviation
since there are potentially an exponential number (
i.e.
all
possible matchings amongst agents in
N
n
B
). Instead, in
this paper we consider several natural heuristics, based on
agents'
attitudes
, that members of
B
use to reason about,
and approximate, the reactions to their deviations.
Neutral Attitude:
Agents in blocking coalition
B
have a
neutral
attitude if they assume that agents in
N
n
B
will not react to the deviation. All existing matches
amongst non-deviating agents will remain and no new
matches will form.