Signal Processing - November 2016 - 111

conventional model of two-sided matchings, the preference
of each agent only depends on with whom the agent is being
matched. This matching is called matching without externalities. It means that the agents do not care about whom
the other agents are going to match with. However, there are
scenarios where it is important for an agent to know who is
matched to other agents because they may share the same
resources. This matching is called matching with externalities. For example, let's consider a user subchannel matching
in an ad hoc network with subchannels can be accessed by
multiple users. At the beginning user A may choose subchannel C as its most preferred subchannel. However, when
the network gets congested with more users allocated to
subchannel C, the interference level in this subchannel
increases, and user A may change its most preferred subchannel. In other words, the preference of user A over subchannel C depends on the choices of other users. In another
example, in the college admission problem, a student may
not only care about the quality of the college that he/she is
going to apply for but also who else is applying for the
same college.
A matching game with externalities is defined as [26]:
■ Definition 8: A matching game with externalities is represented as a tuple G = (H, E, U), where (H, E) is the set of
agents and U is a real valued function such that U (z | h)
is the utility of agent z when matching h forms.
In the assignment game [13], U (i i, p i) denotes the utility value of i i when i i and p i are matched. Now with
externalities, a generalized assignment game that includes
externalities is assumed such that for each matching A and
every (i i, p j) ! h, the amount U (i i, p j | h) denotes the utility from matching of the pair (i i, p j) at A. This matching is a
nontransferable utility game, where the utility of each agent
depends on the underlying coalition structure. Definition 8
represents the most general form of a matching game with
externalities when utility is nontransferable:
■ Definition 9: A matching game with additive externalities
is represented as a tuple G = (H, E, U), where (H, E) is
the set of agents and U is a utility function such that
U (z | i i, p j) is the utility that agent z receives from the formation of pair (i i, p j) . Given a matching h, the utility of
agent z in h is
U (z, h) =

U (i i, p j | z) .

(i i, p j) ! h

In a matching game with additive externalities, the agent's
total utility is the sum of all utilities the agent gains from its
own matches, plus the sum of all the externalities that the
agent will gain from the matchings of other agents. It is interesting to know whether or not there exists any stable matching for a given matching game with externalities and to know
how to find such stable matching if it exists. Like the general
matching definition, a matching is stable if there is no subset of agents that have incentive to reorganize and form new
matchings among themselves [27].

Given a matching game G = (H, E, U), a matching h is
corewise stable if there is no blocking coalition B 3 H , E,
such that at least one agent in B can receive a higher utility
value and no agent in B receives a lower utility value by forming new matches among themselves.
In the matching without externalities, the actions chosen
by other agents do not have any effect on other agents because
their utility depends only on whom the agent is matched with.
However, in matchings with externalities the utility of the
agents does not only depend on an agent's own action. For
example, the utility of agent i i, may depend on the other
matches involving agent p j even if (i i, p j) !
Y h. Therefore, it
is clear that the stability concepts need to take into the account
the actions chosen by other agents in K = H \B, H = H , E
after a coalition B deviates. This is because these actions will
affect the utility value of the agents in B . However, computing all the possible reactions of other agents that cause deviation is very complex because there might be a big number of
possible combinations.

Matchings with incomplete preference
lists and with ties
Another variant of matching is when an agent's preference list
is incomplete, that is, an agent may exclude some agents that
it does not want to be matched with from its preference list. In
this case, the agent i i is acceptable to agent p j if i i appears
on the preference list of p j and unacceptable otherwise. This
matching is stable if there are no two agents that prefer the
other to its current partner, or if one agent is unmatched, the
other agent has been unacceptable for it.
In some cases, ties are allowed in the preference lists, that
is, one agent can include two or more agents with the same
preference value as a tie. For this type of matching, three
notions of stability are defined: weakly stable, strongly stable,
and superstable. A more complex extension in matching that
also can happen in wireless networks is to allow both incompleteness and ties in preference lists. In the following variants,
the marriage problem is used as an example to clarify the
matching models.

Matching with incomplete preference lists
In this type of matching game, each agent's preference list
could be incomplete. In other words, some options that the
agent does not want to be matched with can be excluded from
its preference list.
If an agent i i 's list includes an agent p j, then p j is acceptable to i i . When there are incomplete lists, a matching is not
necessarily perfect. Hence, in matchings with incomplete lists
the definition of a blocking pair is extended. As was mentioned
earlier for a matching μ, (i i, p j) is a blocking pair if all the following three conditions are met:
1) n (i i) ! p j , but i i and p j are acceptable to each other
2) p j ( ii n (i i) or i i is single
3) i i ( p j n (p j) or p j is single.
An important property of stable matching with an
incomplete list is that, for example, in the marriage

IEEE Signal Processing Magazine

November 2016

111

Table of Contents for the Digital Edition of Signal Processing - November 2016