Signal Processing - November 2016 - 107
D
One-to-many matching
U p U ( j)j (U 1 ( j)) 1 0, where U 1 (i) = j when U (i i) = p j and
D
U 1 ( j) =
i when U (p j) = i i .
A matching U is blocked by a pair ^i i, p jh if 1) the matching is not blocked by individual i i and p j , and 2) both i i and
p j can achieve a higher utility value if they match together, as
opposed to their current matching under U [21]. This implies
that U p j (i) 2 U p j (U 1 ( j)) and U ii ( j) 2 U i i (U 1 (i)) . The
stability of a matching can be defined as
■ Definition 4: A matching U is defined as stable if it is not
blocked by any individual or any pair.
It should be noted that to achieve a stable matching, there
is no need for E = H . In one-to-many matching where a
member of H is matched with a group of E members, the
stability is different from one-to-one matching. For the oneto-many matchings the concept of group stability is used. To
define group stability, a coalition C that consists of at least one
member of H is assumed first. A matching U is blocked by a
coalition C if there exists another matching Ul such that
6i, j ! C, 1) Ul ( j) ! C; 2) U p Ul ( j) (Ul ( j)) 2 U p U( j) (U ( j));
3) U ii (Ul (i)) 2 U ii (U (i)); and 4) if u ! Ul (] H) , then
u ! C , U (] H).
Condition 1 states that all the members of H in C are
matched to a member of H in C , conditions 2 and 3 state
that all the members of H and members of E in C prefer
their current matches in Ul to their matches in U, and condition 4 states that every member of H in C can be matched
to a combination of new member of H in C or the member
of H that was matched under U. Therefore, U is blocked by
some coalition C of the member of H and E, if the member
of H and the member of E in C all find a matching preferable toU. Given the above conditions group stability is
defined as
■ Definition 5: A matching U is defined as group stable if it
is not blocked by any coalition.
1
There are many practical scenarios in which the agents
from one side of the matching are allowed to be matched
with a number of other agents from the other side of the
matching, such as when students are allocated to a college
or when doctors are allocated to a hospital. One-to-many
matching indicates that each student can be matched with
one college, although there could be multiple colleges. To
proceed with explaining one-to-many matching, a wellknown example in matching literature called college
admission is used. Let's assume there are two finite and
disjoint sets, H = {i i} i| H=|1 and E = {p j} |jE=| 1, which represent the set of colleges and students, respectively. Each student has preferences over each college, and each college
has preferences over each student.
The difference between the college admission and the
marriage model is that associated with each college i there
is a positive integer, q i ! N, called its quota, which indicates the maximum number of positions the college may fill.
An outcome of the college admission problem is a matching
of students to colleges such that each student is matched
to at most one college, and each college is matched to at
most its quota of students. A student who is not matched
to any college will be matched to himself/herself as in the
marriage model, and a college that has a certain number of
unfilled positions will be matched to itself in each of the
unfilled positions. It is notable that matching is bilateral,
in the sense that a student is admitted at a given college if
and only if the college admits that student. This matching is
stated formally as
■ Definition 3: Given two disjoint finite sets of players,
H = {i i} i| H=|1 and E = {p j} |jE=| 1, let two disjoint finite sets
of ] H = {1, f , H } and ] E = {1, f, E }, then a one-tomany matching function U: {H} , {E} " {H} , {E} is
defined such that for all i ! ] H and j ! ] E
1) U (i i) 3 {p jl ! ] H ! E} and U (i i) # q i
2) U (p j) ! {i il ! ] E ! H} and U (p j) ! {0, 1}
3) U (i i) = p j + U (p j) = i i .
This matching function U is denoted with a three-tuple
U: (H, E, q) . Condition 1 implies that each member of H can
be matched to multiple members of E, condition 2 implies that
each member of E can be matched to at most one member of
H, and condition 3 implies that if i i is matched to p j, then p j
is also matched to i i . For notational purposes, i 0 and p 0 are
defined as the dummy members of H and E, respectively. The
dummy members i 0 and p 0 can be matched to multiple members in E and H, respectively.
To formally define a stable matching, let's first define
a matching that is blocked by an individual and a matching that is blocked by a pair. The parameters i i, i ! ] H
and p j, j ! ] E are considered, such that U (i i) ! p j . A
matching U is blocked by an individual i i ^p jh if i i ^p jh
prefers to be unmatched over being matched with its current partner under U [21]. Mathematically, because the
agents have to receive nonnegative utilities, for i i , this
implies that U ii (U 1 (i)) 1 0, while for p j, this implies that
Many-to-many matching
If the number of allowable matches for the agents in both
sides of the matching is unrestricted, it is a many-to-many
matching problem.
■ Definition 6: Given two disjoint finite sets of players,
H = {i i} i| H=|1 and E = {p j} |jE=| 1, let two disjoint finite sets
of ] H = {1, f, H } and ] E = {1, f, E }, then a manyto-many matching function is defined U: {H} , {E}
" {H} , {E} such that for all i ! ] H and j ! ] E
1) n (p j) is contained in H and n (i i) is contained in E
2) U (i i) 3 {p jl ! ] H ! E} and U (i i) # q i
3) U (p j) ! {i il ! ] E ! H} and U (p j) # q p
4) U (i i) = p j + U (p j) = i i,
where q p ! N denotes the quota of E members.
In many-to-many matching models, many stability concepts can be considered depending on the number of players
who can improve their utility by matching to new partners. However, for a large number of agents, it is difficult
to identify large coalitions by considering all the possible
combinations of players. Therefore, the notion of pairwise
stability is presented and used in many-to-many matching
IEEE Signal Processing Magazine
|
November 2016
|
107
Table of Contents for the Digital Edition of Signal Processing - November 2016
Signal Processing - November 2016 - Cover1
Signal Processing - November 2016 - Cover2
Signal Processing - November 2016 - 1
Signal Processing - November 2016 - 2
Signal Processing - November 2016 - 3
Signal Processing - November 2016 - 4
Signal Processing - November 2016 - 5
Signal Processing - November 2016 - 6
Signal Processing - November 2016 - 7
Signal Processing - November 2016 - 8
Signal Processing - November 2016 - 9
Signal Processing - November 2016 - 10
Signal Processing - November 2016 - 11
Signal Processing - November 2016 - 12
Signal Processing - November 2016 - 13
Signal Processing - November 2016 - 14
Signal Processing - November 2016 - 15
Signal Processing - November 2016 - 16
Signal Processing - November 2016 - 17
Signal Processing - November 2016 - 18
Signal Processing - November 2016 - 19
Signal Processing - November 2016 - 20
Signal Processing - November 2016 - 21
Signal Processing - November 2016 - 22
Signal Processing - November 2016 - 23
Signal Processing - November 2016 - 24
Signal Processing - November 2016 - 25
Signal Processing - November 2016 - 26
Signal Processing - November 2016 - 27
Signal Processing - November 2016 - 28
Signal Processing - November 2016 - 29
Signal Processing - November 2016 - 30
Signal Processing - November 2016 - 31
Signal Processing - November 2016 - 32
Signal Processing - November 2016 - 33
Signal Processing - November 2016 - 34
Signal Processing - November 2016 - 35
Signal Processing - November 2016 - 36
Signal Processing - November 2016 - 37
Signal Processing - November 2016 - 38
Signal Processing - November 2016 - 39
Signal Processing - November 2016 - 40
Signal Processing - November 2016 - 41
Signal Processing - November 2016 - 42
Signal Processing - November 2016 - 43
Signal Processing - November 2016 - 44
Signal Processing - November 2016 - 45
Signal Processing - November 2016 - 46
Signal Processing - November 2016 - 47
Signal Processing - November 2016 - 48
Signal Processing - November 2016 - 49
Signal Processing - November 2016 - 50
Signal Processing - November 2016 - 51
Signal Processing - November 2016 - 52
Signal Processing - November 2016 - 53
Signal Processing - November 2016 - 54
Signal Processing - November 2016 - 55
Signal Processing - November 2016 - 56
Signal Processing - November 2016 - 57
Signal Processing - November 2016 - 58
Signal Processing - November 2016 - 59
Signal Processing - November 2016 - 60
Signal Processing - November 2016 - 61
Signal Processing - November 2016 - 62
Signal Processing - November 2016 - 63
Signal Processing - November 2016 - 64
Signal Processing - November 2016 - 65
Signal Processing - November 2016 - 66
Signal Processing - November 2016 - 67
Signal Processing - November 2016 - 68
Signal Processing - November 2016 - 69
Signal Processing - November 2016 - 70
Signal Processing - November 2016 - 71
Signal Processing - November 2016 - 72
Signal Processing - November 2016 - 73
Signal Processing - November 2016 - 74
Signal Processing - November 2016 - 75
Signal Processing - November 2016 - 76
Signal Processing - November 2016 - 77
Signal Processing - November 2016 - 78
Signal Processing - November 2016 - 79
Signal Processing - November 2016 - 80
Signal Processing - November 2016 - 81
Signal Processing - November 2016 - 82
Signal Processing - November 2016 - 83
Signal Processing - November 2016 - 84
Signal Processing - November 2016 - 85
Signal Processing - November 2016 - 86
Signal Processing - November 2016 - 87
Signal Processing - November 2016 - 88
Signal Processing - November 2016 - 89
Signal Processing - November 2016 - 90
Signal Processing - November 2016 - 91
Signal Processing - November 2016 - 92
Signal Processing - November 2016 - 93
Signal Processing - November 2016 - 94
Signal Processing - November 2016 - 95
Signal Processing - November 2016 - 96
Signal Processing - November 2016 - 97
Signal Processing - November 2016 - 98
Signal Processing - November 2016 - 99
Signal Processing - November 2016 - 100
Signal Processing - November 2016 - 101
Signal Processing - November 2016 - 102
Signal Processing - November 2016 - 103
Signal Processing - November 2016 - 104
Signal Processing - November 2016 - 105
Signal Processing - November 2016 - 106
Signal Processing - November 2016 - 107
Signal Processing - November 2016 - 108
Signal Processing - November 2016 - 109
Signal Processing - November 2016 - 110
Signal Processing - November 2016 - 111
Signal Processing - November 2016 - 112
Signal Processing - November 2016 - 113
Signal Processing - November 2016 - 114
Signal Processing - November 2016 - 115
Signal Processing - November 2016 - 116
Signal Processing - November 2016 - 117
Signal Processing - November 2016 - 118
Signal Processing - November 2016 - 119
Signal Processing - November 2016 - 120
Signal Processing - November 2016 - 121
Signal Processing - November 2016 - 122
Signal Processing - November 2016 - 123
Signal Processing - November 2016 - 124
Signal Processing - November 2016 - 125
Signal Processing - November 2016 - 126
Signal Processing - November 2016 - 127
Signal Processing - November 2016 - 128
Signal Processing - November 2016 - 129
Signal Processing - November 2016 - 130
Signal Processing - November 2016 - 131
Signal Processing - November 2016 - 132
Signal Processing - November 2016 - 133
Signal Processing - November 2016 - 134
Signal Processing - November 2016 - 135
Signal Processing - November 2016 - 136
Signal Processing - November 2016 - 137
Signal Processing - November 2016 - 138
Signal Processing - November 2016 - 139
Signal Processing - November 2016 - 140
Signal Processing - November 2016 - 141
Signal Processing - November 2016 - 142
Signal Processing - November 2016 - 143
Signal Processing - November 2016 - 144
Signal Processing - November 2016 - 145
Signal Processing - November 2016 - 146
Signal Processing - November 2016 - 147
Signal Processing - November 2016 - 148
Signal Processing - November 2016 - Cover3
Signal Processing - November 2016 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201809
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201807
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201805
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201803
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201801
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0917
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0717
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0517
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0317
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0916
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0716
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0516
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0316
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0915
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0715
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0515
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0315
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0914
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0714
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0514
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0314
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0913
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0713
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0513
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0313
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0912
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0712
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0512
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0312
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0911
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0711
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0511
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0311
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0910
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0710
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0510
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0310
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0909
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0709
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0509
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0309
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1108
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0908
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0708
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0508
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0308
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0108
https://www.nxtbookmedia.com