Signal Processing - November 2016 - 109

in matching theory is essentially different from the normal
auction models.
Normally, in matching, the aim is to form stable matching pairs between the firms and workers. However, in the
auctions, the aim is to sell objects to the buyers. Moreover,
in more complex matching models, there are multiple buyers and multiple sellers, and each seller has a different
object to sell. Each buyer also has a specific preference
over each object. However, in the auction models normally
one seller auctions one object to multiple buyers. In some
more general auctions, multiple sellers auction the same
objects to the buyers. In matching theory, the multiple
seller-multiple buyer case is traditionally classified as an
assignment game.

Optimization problem
The maximization problem to determine the matching in the
assignment game is called the optimal assignment problem or
simply the assignment problem. In this part, a one-to-one
assignment problem is formulated as follows:
m

max /

/ a ij x ij

i=1 j=1
m

s.t. : 1) / x ij # 1, 6j ! {1, 2, ..., n}
i=1
n

2) / x ij # 1, 6i ! {1, 2, ..., m}
j=1

3) x ij ! {0, 1}, 6i ! {1, 2, ..., m} and 6j ! {1, 2, ..., n}.
(2)

Condition 1 is called the individual rationality condition
and reflects that a player may remain unmatched. Condition 2
requires that the outcome is not blocked by any pair. If condition 2 is not satisfied for some agents i and j, then they will
break up their present partnership and form a new partnership,
because both can receive higher utility value.

General distributed assignment game algorithm
The general assignment game algorithm (GA-alg) that is a
highly practical model is discussed in this section. The
purpose of the proposed algorithm is to obtain a solution
to the optimization problem in (2) in a distributive way.
The algorithm in Table 2 is a general algorithm and can be
customized for a wide range of complex scenarios in
matching games.
The specific details of the algorithm are described in Table 2,
with the notations defined below. The GA-alg consists of an
initialization stage in step 1, followed by multiple iterations. At
this part a brief description of the algorithm during iteration t
is given.
In GA-alg-Step 2, each seller that is not matched makes a
price-allocation number offer to the unmatched buyers (GAalg-Step 2-1). This price-allocation number is denoted by b ti, j
for the jth seller and ith buyer. Each buyer then determines the
seller that provides the highest positive utility (GA-alg-Step
2-2-a). For the ith buyer, this is denoted by the demand set [the
term demand set is used as it is also used in economics literature (see, e.g., [5] and [24])]:
X i (b ti)

Condition 1 guarantees that each buyer will be matched
with only one seller, condition 2 states that each seller can
be matched with only one buyer, and condition 3 guarantees
that the value of x will be one or zero. The optimization
problem in (2) is a binary linear programming problem
(BLP), which is a special case of integer programming in
which the variables can only be zero or one. The optimization problem (2) is also in the standard form of BLP problems with the set of inequality conditions on the binary
variables that is shown to be NP-hard. It has been shown
that there exists a solution of this optimization problem for
which values of x will be one or zero. A matrix X is a feasible solution for the assignment problem in (2), if it satisfies
conditions 1-3. Moreover, among all the feasible solutions,
the solution X is called the optimal solution if
m

/ / a ij x ij 2 / / a ij xlij ,

i=1 j=1

where xlij belongs to another solution Xl .
A feasible outcome X is stable if the two following conditions are satisfied:
1) u i $ 0, v i $ 0
2) u i + v i $ a ij, 6i, j.

argmax U i, j, if max U i, j H 0;
jdS

jdS

otherwise

(3)

where b ti = [ b t1, i , b 2t , i, ..., b tn, i] is the price-allocation vector at
p
stage t and U i, j is the utility function of buyer p i when it is
matched with seller s j . The demand set for p i is equal to the
index of the seller that provides the maximum utility. If the
demand set is not empty, the buyer will bid for the seller in its
demand set; otherwise, the buyer will not bid and remains
unmatched. The bid from p i to s j is denoted by g ti, j, with g ti, j
taking on the values
g ti, j = '

1, if p i bids for s j;
0, otherwise.

(4)

In GA-alg-Step 3, sellers will decide if they want to match
with the buyers. There are three possibilities. The first possibility (GA-alg-Step 3-1) is that the seller receives no bids from
buyers after increasing its price-allocation number, but in the
previous iteration, the seller had received bids from multiple
buyers. The seller will choose one of these buyers randomly to
be matched with. The second possibility is that the seller has
bids from multiple buyers (GA-alg-Step 3-2-a). The seller will
increase its price-allocation number by e for the next iteration, that, the t + 1st iteration. Note that e ! R + represents the
price-step number, which indicates the price-allocation number offer from the sellers to the source increases at each step.
The third possibility (GA-alg-Step 3-2-b) is that the seller has

IEEE Signal Processing Magazine

November 2016

109

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