Signal Processing - November 2016 - 110
Table 2. The general assignment game algorithm (GA-alg).
Step 1: Initialization
1) Set t = 1, b ti, j = b min j, 6i ! P, 6j ! S .
2) Set g ti, j = 0, 6i ! P, 6j ! S .
3) Construct the list of all the sellers that are not matched denoted by
MATCHLISTs = {s j} nj = 1 (implying U t (s j) = (p 0, 0), 6s j ! S ).
Step 2: Buyer Demand of Goods or Service
1) Each s j ! MATCHLISTs announces its price-allocation number b ti, j
to all the unmatched buyers.
2) Set SLISTp = Q .
3) Each unmatched buyer p i, 6i ! P :
■
■
■
Determines its demand X i (b ti ) .
If X i (b ti ) ! Q , then p i is added to SLISTp and bids for s j
(g ti, j = 1) , where j = X i (b ti ), 6s j ! S .
Otherwise, p i does not bid, (g ti, j = 0, j ! S) and
U t (p i) = (s 0, 0).
Step 3: Sellers' Decision Making
1) For all s j ! S
■
If U t (s j) = p 0 and
t
U (s j) =
/ mi = 1
(p i l, b ti l-, j1) ,
g ti, j = 0 and b ti, j 2 b min j, 6i ! P
where
t-1
i l = random ({i * | g i*, j = 1, 6i * ! P}) .
Remove s j from MATCHLIST J .
t
Set g i l , j@ = 0 , where j @ = X i l (b it ) .
2) For all s j ! S
■
If
/ mi = 1 g ti,j 2 1,
Set b ti,+j 1 = b ti, j + e .
If s j " MATCHLISTs
sj is added to MATCHLISTs .
■
Else
/ mi = 1 g ti,j = 1,
t
U t (s j) = (p i, b ti, j) , where i = arg i* ! P g i*, j = 1.
Remove s j from MATCHLISTs .
3) For all s j ! S
■
t
If (U (s j) ! p 0 and
t+1
b i, j
=
t
b i, j, i
/ mi = 1 g ti,j = 0) or U t (s j) = (p 0, 0)
! P.
Set t = t + 1. If SLISTp ! Q , go to step 2; otherwise, go to step 4.
Step 4: End of the Algorithm
received a bid from only one buyer. In this case, the seller will
be matched with this node. The last iteration of the GA-alg is
denote by t End .
Competitive equilibrium
The requirements of a stable matching in previous sections
are defined with the general implication that none of the
two matched agents has a desire to leave their current
matching and make a new match. In the wireless networks,
if users are assumed as the agents in matching then the
focus of the network is to maximize the agents' satisfaction level. Although the final matching may be stable, it is
an important factor to investigate whether any of the
matched buyers prefer to be matched with another seller.
110
In this regard, it is convenient to present the competitive
equilibrium, defined as
■ Definition 7: The matching matrix X, and price-allocation
vector b, that are produced by the matching algorithms are
in competitive equilibrium if the following conditions
are satisfied:
1) for each s j, j ! S, if U 1 (s j) ! p 0 , then b ij $ c j
2) for each p i, i ! P, U 1 (p i) ! X i ^b i h
3) for each s j, j ! S, if U 1 (s j) = p 0, then b ij = c j,
where X i ^b i h is defined in a similar way to (3) but dropping
parameter t.
The conditions can be interpreted as follows. Condition 1
states that a matched seller always receives a nonnegative utility; condition 2 states that each buyer will be matched with the
seller that provides the highest positive utility; and condition 3
states that if a seller is not matched, then its price-allocation
number results in a zero utility. Note that based on Definition 7,
the competitive equilibrium concept is a special case of the
stable matchings.
However, the concept of competitive equilibrium needs
to be distinguished from stable matching. In stable matching there are no buyer-seller pairs who both prefer each
other over their current match, but in competitive equilibrium there is no buyer who prefers any seller over his/her current match. Competitive equilibrium is a feasible matching
outcome that guarantees that 1) there are no two agents who
are able to form a matching pair such that both would benefit better than their current state, and 2) there is no matched
agent who prefers to be unmatched. Competitive equilibrium has been widely studied in the literature [25], [26]. It
has been shown that a competitive equilibrium always exists
[26]. A competitive equilibrium can be stated by the matching matrix and the price vector. Based on this definition, the
following theorem and lemma are presented [8].
■ Theorem 3: The algorithm in Table 2 produces matching
and price-allocation matrices, which are in competitive
equilibrium for sufficiently small values of e.
Theorem 3 provides an important property of the matching algorithm, that when e is small enough, the outcome
of the algorithm will be in the competitive equilibrium.
Decreasing e will increase the number of iterations of the
matching algorithm in Table 2, so there is always a tradeoff
between the optimality and the complexity of the matching
algorithm in Table 2. The parameter e can be considered
as a controlling parameter for the network designer to balance between the convergence time and performance of the
matching algorithm.
■ Lemma 1: An algorithm that results in a competitive equilibrium also results in a stable matching.
Lemma 1 implies that competitive equilibrium covers the
stable matching. However, there are some outcomes of the
matching that are not competitive equilibrium.
Matching with externalities
In all the matching models discussed previously, the preferences of agents over each other is fixed over time. In such a
IEEE Signal Processing Magazine
|
November 2016
|
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