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 dierent

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 Articial 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 aect 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 dierent 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 dened 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 Denition 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-

ticial 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 denitions of stability could

incorporate dierent layers of deviators, such as agents who

perform the deviation and agents who agree to it without ac-

tively participating. However, such denitions can be prob-

lematic, and require specifying which agents are identied

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 eect 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.