INTRODUCTION
An auction is usually defined as a market mechanism with an explicit set of rules determining resource allocation and prices on the basis of bids from the market participants.
In the other words, auctions can be used to reach economically efficient allocations of goods, services, tasks, resources, etc. Auctions are important mechanisms for resource and task allocation. There are a lot of problems that are called task and resource allocation problems, for example, bandwidth auctions, auctions for takeoff and landing slots in an airport, purchase and supply management and so on. Auctions provide a foundation for modeling task and resource allocation problems.
In combinatorial auctions, Winner Determination Problem (WDP) is defined by
finding the revenue maximizing set of winning bids. It is well known that the
WDP is a complex computational problem and NPcomplete (Rothkopf
et al., 1998). Much of recent research on solving the WDP has been
carried out by different approaches such as optimization, intelligent search
and heuristics (Xia et al., 2004). Sandholm
(2002) developed BranchonItems and BranchonBids algorithms for solving
the WDP and gained significant popularity (Sandholm and
Suri, 2002). Mito and Fujita (2003) proposed three
heuristic bidordering schemes for solving the WDP. LeytonBrown
et al. (2000) researched and developed a method for the WDP in multiunit
combinatorial auctions. Gonen and Lehmann (2000) also,
applied the branchandbound procedure to solve the WDP as an IP problem in
multiunit combinatorial auctions. CASS, Casanova and OMAGA are also three wellknown
algorithms that implemented for WDP.
The CASS (Combinatorial Auction Structured Search) is a bruteforce approach
that followed by four improvements (Mito and Fujita, 2003).
The CASS considers fewer partial allocations than the bruteforce method because
it structures the search space to avoid considering allocations containing conflicting
bids. It also caches the results of partial searches and prunes the search tree.
Finally, it may be used as an anytime algorithm, as it tends to find good allocations
quickly. Casanova is another wellknown algorithm for the WDP that it
uses a stochastic local search algorithm for bearing a strong resemblance to
the novelty algorithm defined by Hoos and Zhang (2000).
It is based on scoring each search state using the revenue per item of the corresponding
allocation.
The OMAGA (Orthogonal MultiAgent Genetic Algorithm) is evolutionary approach
introduced lately by Zhang and Zhang (2007). It is a
genetic based algorithm that lowerlayer Orthogonal MultiAgent Genetic Algorithm
(OMAGA) is applied to searching the optimal solution of the giving combinatorial
auctions optimization problem and the upperlayer OMAGA is used for optimizing
the parameter of lowerlayer OMAGA.
In this study, we introduce a swarm based algorithm for solving the WDP. A
Quantumbehaved Particle Swarm Optimization (QPSO) is proposed by combining
the classical PSO philosophy and quantum mechanics to improve performance of
PSO. We use a discrete version of QPSO (DQPSO) for some reasons. Firstly, DQPSO
has showed better performance than other swarm algorithms such as discrete PSO
(Zhang and Zhang, 2007) and secondly, DQPSP has no setting
parameter. Since, the WDP is constraint optimization problem, penalty function
is used to overcome the constraints. We evaluated our approach in two steps.
First we showed that DQPSO is applicable to the problem. Second we compared
our approach with CASS, Casanova, GA and OMAGA on standard test. The results
showed that our approach is better than the other algorithms.
WINNER DETERMINATION PROBLEM
When there are multiple indistinguishable goods for sale, it is usually desirable
(from a bid compactness and winner determination complexity perspective) to
represent these goods as multiple units of a single item, rather than as multiple
items. Different items can have multiple units, where units of one item are
indistinguishable but units of different items are distinguishable. This representation
allows a bidder to place a single bid requesting the amount of each item that
she wants, instead of placing separate bids on the potentially enormous number
of combinations that would amount to those numbers of units of those items.
An auction that allows this type of bidding is called a multiunit combinatorial
auction. They have been used, for example, in the eMediator ecommerce server
prototype (Gonen and Lehmann, 2000) and recent research
has studied winner determination in this context (Sandholm,
2002). Multiunit auctions have many potential realworld applications including
bandwidth allocation and electric power markets. The winner determination problem
for multiunit auctions follows.
Definition: The auctioneer has a set of items, M = (1, 2, ..., m), to
sell. The auctioneer has some number of units of each item available: U = (u_{1},
u_{2} ..., u_{m}), u_{i} ∈.
The buyers submit a set of bids, B = (b_{1}, b_{2}..., b_{n})
. A bid is a tuple B_{j} (λ^{1}_{j}, λ^{2}_{j},
λ^{3}_{j}..., λ^{m}_{j}); where λ^{k}_{j}≥0
is the number of units of item k that the bid requests and p_{j}≥0
is the price. The Binary MultiUnit Combinatorial Auction Winner Determination
Problem (BMUCAWDP) is to label the bids as winning or losing so as to maximize
the auctioneer's avenue under the constraint that each unit of an item can be
allocated to at most one bidder:
This problem is intractable, it is equivalent to weighted set packing, a wellknown
NPcomplete problem. It can be solved via dynamic programming, but that takes
Ω(2^{m}) and O (3^{m}) time independent of the number of
bids, n (Rothkopf et al., 1998).
One approach is to solve the problem approximately (Hoos and Boutilier, 2000).
However, it was recently shown (via a reduction from the maximum clique problem
which is inapproximable (Rassenti et al., 1982)
that no polynomial time algorithm for the winner determination problem can guarantee
a solution that is close to optimum (Lehmann et al.,
1990). Certain special cases can be approximated slightly better, as reviewed
in (Sandholm and Suri, 2002).
The second approach is to restrict the allowable bids (Nisan,
2000). For certain restrictions, which are severe in the sense that only
a vanishingly small fraction of the combinations can be bid on, winners can
be determined in polynomial time. Restrictions on the bids give rise to the
same economic inefficiencies that prevail in noncombinatorial auctions because
bidders may not be able to bid on the combinations they prefer.
The third approach is to solve the unrestricted problem using search. This
was shown to work very well on average, scaling optimal winner determination
up to hundreds of items and thousands of bids depending on the problem instance
distribution and improvements to the algorithm have been developed since (Fujishima
et al., 1999).
DISCRETE QUANTUMBEHAVED PARTICLE SWARM OPTIMIZATION
Particle swarm optimization (PSO): The Particle Swarm Optimization (PSO)
algorithm is a populationbased evolutionary search technique that is proposed
by Kennedy and Eberhart (1995). The PSO is initialized
with a group of random particles (solutions) and then searches for the optima
by updating each generation. In each iteration, each particle is updated by
the following two best values. The first one is the local best solution a particle
has obtained so far. This value is called personal best solution (pbest). Another
best value is that the whole swarm has obtained so far. This value is called
global best solution (gbest). The philosophy behind the original PSO is to learn
from individual’s own experience (personal best solution) and the best
individual experience (global best solution) in the whole swarm.
Denote by M particle number in the swarm. Let X_{i} = (x_{i1}, x_{i2}, …, x_{iD}) be particle i with D bits, where being treated as a potential solution. Denote the velocity as V_{i} = (v_{i1}, v_{i2},…, v_{iD}). Let pbest_{i} = (pbest_{i1}, pbest_{i2},…, pbest_{iD}) be the best solution that particle i has obtained (the position giving the best fitness value). At each Iteration, each particle competes with the others in the neighborhood or in the whole population for the best particle (with best fitness value among neighborhood or the population) with best position gbest_{i} = (gbest_{i1}, gbest_{i2},…, gbest_{iD}) called global best position and then makes stochastic adjustment according to the following evolution equations:
In the above equations, c_{1} and c_{2} are positive constant; rand() and rand() are two random functions generating uniformly distributed random numbers within (0,1). Parameter w is the inertia weight introduced to accelerate the convergence speed of the PSO. At each iteration, the value of Vid is restricted in (Vmax, Vmax).
In original PSO, the particles operate in continous search space, where the
trajectories are defined as changes in positions. In discrete binary PSO (Kennedy
and Eberhart, 1997), trajectories are defined as changes in the probability
that a coordinate of the position vector will take on a value from feasible
discrete values.
Quantumbehaved particle swarm optimization: The PSO is not a global
convergenceguaranteed optimization algorithm. Therefore, Sun
et al. (2004a, b) proposed a global convergenceguaranteed
search technique, quantumbehaved particle swarm optimization algorithm (QPSO),
whose performance is superior to the PSO.
In the quantum model of a PSO, the state of a particle is depicted by wave function ø(x, t), instead of position and velocity. The dynamic behavior of the particle is widely different from that of the particle in traditional PSO systems in that the exact values of position and velocity cannot be determined simultaneously. We can only learn the probability of the particle’s appearing in position x from probability density function ψ (x, t), the form of which depends on the potential field the particle lies in. The particles move according to the following iterative equation:
Where,
and
The mbest (mean best position or mainstream thought point) is defined as the
mean value of all particles’ the best position, φ and u are random
number distributed uniformly on (0,1), respectively and m is the number of particles.
L = β.mbest_{d}x_{id} (t). 1n (1/u) can be
viewed as the strength of creativity or imagination because it characterizes
the knowledge seeking scope of the particle and therefore the larger the value
L, the more likely the particle find out new knowledge. The parameter, β,
called contractionexpansion coefficient, is the only parameter in QPSO algorithm.
From the results of stochastic simulations, QPSO has relatively better performance
by varying the value of β from 1.0 at the beginning of the search to 0.5
at the end of the search to balance the exploration and exploitation (Sun
et al., 2005).
The QPSO algorithm, kept to the philosophy of PSO, is based on Delta potential well and depicted only with the position vector without velocity vector, which is a simpler algorithm.
Discrete QPSO: The QPSO can be generalized to discrete binary search
space by redefining local attractor g_{i}, the mbest (mean best
position) and the strength of creativity L = β.mbest_{d}x_{id}
(t). 1n (1/u) in binary search space (Zhou et al.,
2007).
Firstly, we describe how to compute the local attractor for each particle in binary space. Equation 6 is used for getting the coordinate of the local attractor g_{i} for particle i in the continuous space. Therefore, g_{i} is generated through arithmetic crossover between pbest_{i} and gbest and the coordinate of g_{i} lies between pbest_{i} and gbest. In binary space, the point g_{i} can be generated through binary or discrete crossover operation like that used in Genetic Algorithm (GA) with discrete coding. That is, g_{i} is randomly selected from two offspring that are generated by exerting crossover on the two parents, pbest_{i }and gbest. In this study, uniform crossover is used to compute the local attractor.
Secondly, we describe how to compute the mbest (mean best position) in binary space. At first, DQPSO compute the center of personal best positions m_{d}:
Then the mean best position is determined by m_{d} by the following way:
•  if
m_{d} > 0.5, set mbest_{d} = 1 
•  if
m_{d} < 0.5, set mbest_{d} = 0 
•  if
m_{d} = 0.5 set mbest_{d} to be 1 or 0, with probability
0.5 for either state 
That is, if more particles take on 1 at the dth bit of their own pbests, the dth bit of mbest will be 1; otherwise the bit will be 0. However, if half of the particles take on 1 at the dth bit of their pbests, the dth bit of mbest will be set randomly to be 1 or 0, with probability 0.5 for either state.
Thirdly, we describe how to define the strength of creativity or imagination L in binary space. In the binary space, the basic operation is the bit flip and an individual moves to nearer or farther corners of the hypercube (searching space) by flipping bits in its position vector. Therefore the distance (difference) between two solutions is measured by Hamming distance. Since, an individual moves to nearer or farther corners of the hypercube (searching space) by flipping bits in its position vector, the distance vector between the mbest (mean best position) and population individual X_{i} (denoted as of the dth dimension) can be described by a vector whose bit is set to 1 if the corresponding bits of mbest and X_{i} are different and 0 otherwise. Thus, the operation mbest_{d}x_{id} (t) in Eq. 5 can be substituted with mbest_{d}⊕x_{id}, where ⊕ is the bitwise exclusiveor (XOR) operator.
For each bit, β. 1n (1/u) can be seen as the probability that a change is applied to the corresponding bit of g_{i} to produce the mutant local attractor vector, that is, β. 1n (1/u) is like the mutation probability in GA. If a bit in the distance vector is 1 and change is activated by the probability β. 1n (1/u) (that is, rand ()<β. 1n (1/u) ), the corresponding bit in the g_{i} vector will be reversed. This reverse operation is also an equivalence of the XOR operator.
Discrete QPSO can be described as follows:
Where,
And ⊕ is the bitwise and operator.
THE PROPOSED APPROACH
The fitness function and the encoding of particles are two key issues in DQPSO, which are given as follows.
In the DQPSO, a potential solution to a problem is represented as a particle having binary coordinates x = (x_{1},..., x_{n}), x_{j} ∈ (0, 1) in a ndimensional space as illustrated in Fig. 1.
For the application to WDP, x_{j} = 0 means that bid j is not selected, whereas x_{j} = 1 means that the bid j is selected. By this solution representation, we can see that such a solution might not be feasible for WDP. An infeasible solution is one for which at least one of the constraints is violated, i.e.,
A penalty function technique is normally incorporated to solve the constrained problem. Therefore, we use a penalty function f in fitness function to overcome
For the WDP problem, the fitness function is defined as:
where, m is the number of items. n is the number of bits. λ^{i}_{j} is the number of units of item i that the bid j requests.

Fig. 1:  Solution
structure of DQPSO 
p_{j} is price of bit j. ui is the number of units for item i and f is a positive linear transform function as penalty function, which is defined as:
EXPERIMENTAL STUDIES
Here, we give some empirical data in order to test the efficiency of the proposed
approach and to evaluate its performance. It is generally recognized that it
is most unfortunate that realworld test data are not available. As long as
no such test data is available. The empirical benchmarks are performed on the
same test data as was given by Sandholm (2002) and Fujishima
et al. (1999). We use these tests not because we are convinced that
they are the most relevant, but because they are the only ones for which we
have data for competing algorithms. Seven distributions were proposed in (Sandholm
and Suri, 2002), (Fujishima et al., 1999)
and (Hoos and Boutilier, 2000) that have been widely used by other researchers.
Each of these distributions may be seen as an answer to two questions: what
number of items to request in a bundle and what price to offer for a bundle.
Given a required number of items, all distributions select which items to include
in a bid uniformly at random without replacement. The following methods are
used to select the number of items in a bundle:
•  Uniform:
Uniformly distributed on (1, num_items). Normal: Normally distributed
with μ = μ_{g} and σ = σ_{g} 
•  Constant:
Fixed at constant items 
•  Decay:
Starting with 1, increment the size of the bundle until rand
(0, 1)>α. Binomial: Request n items with probability p^{n}(1p)^{num_itemsn}C(num_items,n) 
•  Exponential:
Request n items with probability Ce^{n/q} 
The following methods are used to select a price offer:
•  Fixed
Random: Uniform on [low, hi]. Linear Random: Uniform on (low.n, hi.n) 
•  Normal:
Draw from a normal distribution with μ = μ_{p} and σ
= σ_{p} 
Since, we must assign the number of units for each item in multiunit auction problem, uniform distribution is used for determination of the number of units for each item.
The seven distributions follow:
•  [D1]
Sandholm: Uniform; Fixed Random: low = 0, hi = 1 
•  [D2]
Sandholm: Uniform; Linear Random: low = 0, hi = 1. [D3] Sandholm:
Constant: constant_items = 3; Fixed Random: low = 0, hi = 1 
•  [D4]
Sandholm: Decay: α = 0.55; Linear Random: low = 0, hi = 1 
•  [D5]
Hoos and Boutilier: Normal: μ_{g} = 4, σ_{g}
= 1; Normal: μ_{p} = 16, σ_{p} = 3 
•  [D6]
Fujishima et al.: Exponential: q = 5; Linear Random: low =
0.5, hi = 1.5 
•  [D7]
Fujishima et al.: Binomial: p = 0.2; Linear Random: low = 0.5,
hi = 1.5 
To determine the efficiency of the algorithm, we run experiments on a general purpose PC (CPU: 1.2 GHZ Pentium III; Memory: 128 MB; OS: Windows XP). The algorithm is programmed in Java language and run on the seven distributions that are mentioned above. The initial populations consist of random particles and each of the experiments was repeated 30 runs.
In our proposed algorithm, the only setting parameter is contractionexpansion
coefficient (β), which was gradually decreased for the interval (1.2, 0.5)
with the number of iterations. We use the seven distributions to generate test
sets with 100 items and 1000 bids, which the number of units for each item is
determined by uniform distribution.
Present results (average of 30 running) are displayed in Fig. 2 and prove as, after the acceptable number of iterations, the processes reach stability. Then we used the information entropy to measure the similarity convergence among the particle vectors for all the seven distributions. We calculated the conditional probability that value 1 happens at the bit j given the total number of bits that take value 1 in the entire swarm as follows:
where, M is swarm size and N is particle length. Then the particle vector entropy can be defined as:
Table 1:  CASS
algorithm, Casanova algorithm, OMAGA and DQPSO on 8 test sets with different
instance 


Fig. 2:  Convergence
graph for a 10*1000 item * bid problem 

Fig. 3:  The
particle vector entropy versus the number of iterations 
If the particle vectors are highly similar to one another, the values of those
nonzero prob_{j} would be high, resulting in less entropy value. Figure
3 shows the particle vector entropy versus the number of iterations. This
is to testify that the swarm evolves to the same optimization goal and the best
solution is not obtained by chance due to a lucky particle. Obviously, this
is because each particle can adjust its direction depending on the results of
its neighbors. The results are quite promising and show that the algorithm is
applicable to nonlinear problems.
SComparisons study: Here, we compared our approach with other approaches
such as Casanova algorithm (Hoos and Boutilier, 2000), CASS algorithm (Hoos
and Boutilier, 2000), Genetic Algorithm (GA) and OMAGA (Zhang
and Zhang, 2007) under the same conditions. They were compared on fifteen
test sets introduced by Hoos and Boutilier (2000).The results are shown in Table
1. The fifteen test sets were generated according to the seven distributions.
These test sets are: UNIpg–b, Sandholm's uniform distribution where,
each instance comprises g items, b bids and each bid consists of p items; DECpgb,
Sandholm's decay distribution; EXPpgb, the exponential distribution and BINpgb,
the binomial distribution. Each of our test sets contains either 10 or 100 problem
instances drawn from the same distribution, using identical parameter values.
The initial populations of GA, OMAGA and DQSPO consist of random individuals
and each experiment (for each algorithm) was repeated 100 times with different
random seed. And the number of individuals per iteration is 20.
Table 1 compares the performance of DQPSO with CASS algorithm, Casanova algorithm, GA, OMAGA on eight test sets.
Table 1 shows that DQPSO in comparison to OMAGA is better on 10 test sets (that are showed by bold font), worse on 3 test set (that are showed by underline) and same on 2 test set.
Table 1 also shows that DQPSO in comparison to GA, Casanova and CASS is better on 15 test sets, worse on 0 test set and same on 0 test set.
CONCLUSIONS
In this study, an approach based on discrete quantumbehaved particle swarm optimization is proposed for combinatorial auction winner determination problem. And a penalty function is applied to overcome constraints. We evaluated the performance of our proposed approach and compared it with four algorithms, which have been introduced before (CASS, Casanova, GA, OMAGA), under the same condition. From the simulated experiment, the result of our proposed approach is better than others.
ACKNOWLEDGMENT
My thanks to Prof. Wang for providing me his test sets for combinatorial auction winner determination problem.