Signal Processing - November 2016 - 108

in the following way [22]. To explain the pairwise stability
concept, the student-college example is used. In a pairwise
stable matching, the matching is not blocked by an individual student, or an individual college, or a student-school
pair. However, 1) each student i i prefers his/her matched
college, rather being unmatched; 2) each college prefers not
rejecting some of the matched students; and 3) there is no
student-college pair who are not matched but prefer to be
matched together.

Matching with transfer-assignment game
Each matching structure (one to one, one to many, and
many to many) can be further classified into a matching
with transfer or a matching without transfer depending on
if there is any transfer between the matching sides. Matchings with transfer are very common in the real world. A
simple example is the buyer-seller scenario where buyers
pay sellers in exchange for goods. After the transactions
between the sellers and buyers end, a matching outcome is
resulted. In wireless networks, the transferred item can be
the network's resources, such as subchannels, power, time
slots, and so forth. One applicable and general matching
framework with transfer is the assignment game that discusses the matching and transactions among buyers and
sellers. The assignment game has different variants used
for modeling various complex scenarios in wireless networks, for example, the scenario where primary users
(PUs) and secondary users (SUs) negotiate on spectrum
sharing in CR networks. When the items that the sellers
are selling are of different types [one has an apple, another
has an orange, etc. (simple and more tangible examples are
used here to simplify understanding the differences of the
matching models)], this is called the multiple objects
assignment game. If each seller has a number of items of
the same type (e.g., seller one has three apples, seller two
has three apples, etc.), this is called the multiple unit
assignment game. If each seller sells a combination of different objects (e.g., seller one has two apples, two oranges,
zero bananas), this becomes a heterogeneous multiple unit
assignment game. The problem becomes more interesting
if each buyer also needs a different combination of different objects. The buyers also can be limited in the amount
of money they can spend. To solve different variants of
assignment games, iterative and dynamic matching algorithms can be developed such that the assignment game
converges to the competitive equilibrium outcome. In the
competitive equilibrium, there are no two agents who can
form a matching pair in such a way that benefits both of
them more than that of their current status, and also there
is no matched agent who may prefer to be unmatched.
Competitive equilibrium is a key concept in matchings
with transfer and will be discussed in more detail in the
following sections. Because in the matching with transfers
there is some sort of transaction among the sides of the
matching, sometimes in the literature these matchings are
referred to as matching markets.
108

General assignment game model
In the general assignment game model, there could be multiple
agents in both sides of the matching, and agents from one side
have transactions with agents in the opposite side. A wellknown example for the assignment game that clearly reveals
the details of the matching procedure is the firms-workers
market in which the firms would like to find the best-matched
workers [23].
To model this market it is assumed that there are two finite disjoint sets of players, workers, denoted by P = {p 1, p 2, ..., p m},
and firms, denoted by S = {s 1, s 2, ..., s n}, containing m and
n players, respectively. Associated with each possible partnership (p i, s j) in (P # Q) there is a nonnegative real number a ij
that represents the gain of this matching.
If each worker has a reservation price of zero for working
in a firm, then rij represents firm pi's reservation price for the
service offered by worker s j to firm pi. In this case if firm pi
employs worker s j with a salary of b ij, and if no other monetary transfers are made or received by firm pi and worker sj,
then the resulting utilities of the two agents are u i = rij - b ij
and v j = b ij, respectively.
More generally, if each worker sj has a reservation price cj
and each firm pi has a reservation price rij for the service by
worker j, a ij is assumed to be the potential gains from trade
between pi and sj; that is, a ij = max [0, rij - c j] . In this case
if firm pi pays for service provided from worker sj at a salary b ij, and if no other monetary transfers are made, the utilities of firm pi and worker sj are u i = rij - b ij and vj = b ij - c j,
respectively. For technical convenience, one virtual worker, s0,
and one virtual firm, p0, are introduced. Several firms may be
matched with the virtual worker and several workers may be
matched with the virtual firm.
It should be noted that in wireless networks there are
cases where the two sets of agents do not really trade a
good, instead they exchange services. For example, a set of
agents share their resources to other agents. In a similar way
these two kinds of agents in this scenario can be regarded as
firms and workers. To facilitate the mathematical notations,
for all general types of matching, the matching index xij is
defined as
x ij = )

1, if U (p j) = i i for i ! ] H , 0, j ! ] E , 0,
0, otherwise.

(1)

The parameter X is defined as an H # E matching
matrix with the (i, j) th element denoted by xij. In the matchings without transfer there is no transaction between the two
sides of the matching, so the preferences of the members in
one side over the members of the other side do not change.
To generalize the model, in the matching literature the agents
can also be defined as buyers and sellers. For example, in
the firms-workers model, the firms who employ the workers
can be regarded as the buyers who are purchasing the workers' services. The workers who are providing services to the
firms are assumed as sellers who are selling the services to
firms. It should be mentioned that the buyers-sellers model

IEEE Signal Processing Magazine

November 2016

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