# The Cross-Entropy Method for the Winner Determination Problem in Combinatorial Auctions

Authors: Hanmi Lin; Yongqiang Chen; Changping Liu; Jie Xie; Baixiu Ni
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

The combinatorial auction is one of the important methods used for multi-item auctions, and the solution to the winner determination problem (WDP) is the key factor in the widespread application of combinatorial auctions. This paper explores the use of the cross-entropy method to solve the WDP, which is an NP problem. The performance of the proposed approach is evaluated on the basis of two well-known benchmark test cases. The experimental results show that, compared with the genetic algorithm and the particle swarm optimization algorithm, the cross-entropy（CE）method has the advantages of a higher success rate and a shorter time for solving the WDP. Therefore, the CE method provides a high-quality solution for the effective solution of the problem of determining winning bids in combined auctions.


---

## Body

## 1. Introduction

Combinatorial auctions, also called bundled auctions or packaged auctions, are a type of multi-item auctions that allow the bidders to bid on a combination of multiple items [1]. In multi-item auctions, bidders and the auctioneer can achieve a win-win situation through the combinatorial auction approach. On the one hand, bidders can express their preference, including complementarity and substitutability, as well as reducing the risks of bidding. On the other hand, the auctioneer can increase the economic revenue. Since the development of combinatorial auctions, they have been widely used in the real world, and the most well-known case is the spectrum licenses auction of America’s Federal Communications Commissions [2]. In addition, the combinatorial auction approach has also been applied to a variety of resource allocation issues, such as transportation capacity resources [3], transportation line resources [4], airport time resources [5], logistics resources [6], industrial procurement resources [7], supply chain formation [8], collaborative rescue service resources [9], cloud computing service resources [10], and network technology service resources [11].The study of combinatorial auctions is a comprehensive application of interdisciplinary approaches, such as economics, game theory, operations research, computer science, and artificial intelligence. Experts and scholars in these fields have mainly focused on three core issues: combinatorial auctions-bidding language [12, 13], mechanism design [14–21], and the winner determination problem. In this paper, we will mainly discuss the issue of winner determination. According to the previous literature, approaches to the solution of the winner determination problem (WDP) generally use exact or inexact methods. Researchers [22–24] who use exact methods to solve the WDP have the advantage of being able to find the optimal solution and to prove its optimality. However, the shortcoming of the exact method is that it requires a large amount of calculations, and a huge amount of storage space is consumed in the calculation process. Therefore, in cases involving a large amount of data, the exact method may take a long time to find the optimal solution, which would introduce certain difficulties in real-world applications. In contrast, using inexact methods to solve the WDP can find a local optimal solution within a certain period although they are unable to prove whether their solution has global optimality. In short, inexact methods are based on heuristics or metaheuristics, which help to find the optimal solution in the case of large amounts of data. In the past ten years, the inexact methods used in solving the WDP include the hybrid simulated annealing algorithm [25], the local search algorithm [26], the random local search algorithm [27], the memetic algorithm [28], the differential evolution algorithm [29], the biased random-key genetic algorithm [30], the discrete particle swarm algorithm [31], the ant colony algorithm and the graph-based ant colony algorithm [32, 33], and the deep-learning intelligent algorithm [34].In this paper, the cross-entropy (CE) method is used to solve the WDP in combinatorial auctions. The advantage of CE is that it can not only estimate the probability of rare events but also can solve combinatorial optimization problems. This algorithm has a wide range of applications in computer science [35], mathematics [36], control science and engineering [37], mechanical engineering [38], and management science and engineering [39], among others.The rest of this paper is organized into the following sections: Section2 describes the WDP formulation. Section 3 introduces the CE algorithm. Section 4 gives the procedure of solving the WDP based on the CE algorithm. Section 5 reports experimental results, and the work is concluded in Section 6.


## 2. The Winner Determination Problem

The WDP refers to finding the winning bid that maximizes the revenue of the auctioneer under the constraint that each item is allocated to at most one bidder [29]. To what extent the solution of the WDP can guarantee quality and speed not only affects the final result of the auction but also affects the practicality of combinatorial auctions. The WDP is a complex combinatorial optimization problem, which has been proved to be an NP-complete problem, a weighted set packing problem [40].The optimization of the WDP in combinatorial auctions can be stated as follows.Suppose there is a setA comprised by a items, such that A can be stated as A=1,2,…,a. B is a set of b bids, such that B can be stated as B=B1,B2,…,Bb. Each bid Bi is a tuple Si,Pi where Si is a subset of items and Pi is the price of bid Sii≥0. M is an a×b binary matrix where Mji=1 if the object j∈Si, otherwiseMji=0. Finally, we can obtain the decision variable as follows: xi=1 if Bi is accepted, and xi=0 otherwise.Then, the optimal WDP in combinatorial auctions can be stated as the following integer programming model:(1)maxFx=∑i=1bPi⋅xi,(2)s.t.∑i=1bMji⋅xi≤1;j∈1,…,a;xi∈0,1.


## 3. The Cross-Entropy Method

In 1997, Israeli professor Reuven Y. Rubinstein proposed the cross-entropy (CE) method [41]. This method was first used to estimate rare-event probability and was later extended to solve optimization problems. The main idea is to transform the “deterministic” optimization problem into a related “random” optimization problem (accompanied by the stochastic optimization problem) and then to use the random simulation technology of rare-event simulation (importance sampling, IP) to solve this “random” optimization problem.The framework of the cross-entropy method for solving an optimization problem can be described as follows.Let us structure a general 0-1 integer maximization problem:(3)maxSx:X∈Rn⟶R,estimation problem. Let us denote probability distribution density functions f⋅;v,v∈V and indicator functions ISX≥γ on X; when u∈V, the corresponding auxiliary stochastic optimization problem can be stated as follows:(4)lγ=PuSX≥γ=∑XISX≥γ⋅fx;u=EuISX≥γ,where Eu is the expectation operator, γ is the level parameter, and I=1 when SX≥γ, otherwise I=0.SX≥γ is a rare event, and only when the sample size is large enough, can formula (4) be solved by the Monte Carlo method. Therefore, the CE algorithm usually uses importance sampling with density gx to reduce the number of samples; then formula (4) is transformed into(5)lγ=1N∑i=1NISxi≥γfxi;ugxi;V,where xi is a random sampling of gx;v.In order to obtain the optimal densityg∗x of importance sampling, the CE introduces the Kullback–Leibler divergence to measure the distance between the two densities. Such that the optimal density g∗x is obtained through minimizing the Kullback–Leibler divergence, and formula (6) expresses the maximization problem as follows:(6)maxv1N∑i=1NISxi≥γlnfxi;v.The main steps of the cross-entropy method can be summarized as follows:Step 1: the parameters are set and initialized.Step 2: a random sample is chosen according to the sampling distribution.Step 3: the probability distribution parameters are modified on the basis of the so-called elite samples (the best scoring samples). The CE distance is involved in this step.Step 4: The optimal probability distribution parameters are output, as long as the iteration termination conditions have been met, if not, return to Step 2.


## 4. The CE Method for Solving the WDP

### 4.1. Constraint Handling and Evaluation Function Construction

In order to use CE to solve the WDP, we use the penalty method to transform the constrained optimization problem described in equations (1) and (2) into an unconstrained optimization problem and construct the function which evaluates the pros and cons of the individual samples of CE as follows:(7)maxFx=∑i=1bPi⋅xi1+S,in which S is the penalty factor, whose definition is as follows:(8)S=∑j=1a∑i=1bMji⋅xi−1+,in which x+=x，when x>0；otherwise，x+=0. It can be seen that if the constraints are met, then(9)∑j=1a∑i=1bMji⋅xi≤1.This meansS=0, and no penalty will be imposed on the evaluation function. If the constraint conditions are not met, then(10)∑j=1a∑i=1bMji⋅xi>1,and penalties are imposed on all the items which exceed 1.


### 4.2. The CE Method for Solving the WDP

The following main steps make up the process by which the CE method is used to solve the WDP problem:Step 1: setting sample sizeN, the elite samples ratio ρ, adaptive parameters α, the maximum number of iterations T, and parameter space dimension n.Step 2: initializing probability distribution parameterp0 and number of iterations t = 0.Step 3: according to probability distribution, parameterspt randomly choose sample vectors Xi=x1,x2,…,xn∼Berpt，i=1,2,…,N，such that its probability distribution density function can be stated as follows:(11)fX;pt=∏i=1nptXi1−pt1−Xi.Step 4: evaluating all samples and sorting them to get the elite sample set and computing the meansvj of the elite samples Xe according to the following formula:(12)vj=∑s=1ρNxjsρN,j=1,…,n.Step 5: using adaptive smoothing technology to modify probability distribution parameterspt. Formula (13) is obtained as follows:(13)pjt=αvj+1−αpjt−1,j=1,…,n.Step 6: settingt = t+ 1, checking whether to stop irritating (t < T), and outputting the optimal probability distribution parameter p∗=pt when the criterion is met, otherwise return to Step 3.


## 4.1. Constraint Handling and Evaluation Function Construction

In order to use CE to solve the WDP, we use the penalty method to transform the constrained optimization problem described in equations (1) and (2) into an unconstrained optimization problem and construct the function which evaluates the pros and cons of the individual samples of CE as follows:(7)maxFx=∑i=1bPi⋅xi1+S,in which S is the penalty factor, whose definition is as follows:(8)S=∑j=1a∑i=1bMji⋅xi−1+,in which x+=x，when x>0；otherwise，x+=0. It can be seen that if the constraints are met, then(9)∑j=1a∑i=1bMji⋅xi≤1.This meansS=0, and no penalty will be imposed on the evaluation function. If the constraint conditions are not met, then(10)∑j=1a∑i=1bMji⋅xi>1,and penalties are imposed on all the items which exceed 1.


## 4.2. The CE Method for Solving the WDP

The following main steps make up the process by which the CE method is used to solve the WDP problem:Step 1: setting sample sizeN, the elite samples ratio ρ, adaptive parameters α, the maximum number of iterations T, and parameter space dimension n.Step 2: initializing probability distribution parameterp0 and number of iterations t = 0.Step 3: according to probability distribution, parameterspt randomly choose sample vectors Xi=x1,x2,…,xn∼Berpt，i=1,2,…,N，such that its probability distribution density function can be stated as follows:(11)fX;pt=∏i=1nptXi1−pt1−Xi.Step 4: evaluating all samples and sorting them to get the elite sample set and computing the meansvj of the elite samples Xe according to the following formula:(12)vj=∑s=1ρNxjsρN,j=1,…,n.Step 5: using adaptive smoothing technology to modify probability distribution parameterspt. Formula (13) is obtained as follows:(13)pjt=αvj+1−αpjt−1,j=1,…,n.Step 6: settingt = t+ 1, checking whether to stop irritating (t < T), and outputting the optimal probability distribution parameter p∗=pt when the criterion is met, otherwise return to Step 3.


## 5. Experiments of the Data Sets

### 5.1. Descriptions of the Test Cases

In order to verify the performance of CE on the WDP, this paper selects two classic sets of data for testing [42, 43]. Test Case 1 is derived from a combined auction containing 10 bidders, 8 bids, and 30 bids. Its serial numbers, bids, and biddings are shown in Table 1.Table 1
Data of Test Case 1.
Serial numberBidsBiddingSerial numberBidsBidding12, 4, 8240116890322, 4, 6204217327034840181, 4, 5165844, 6, 82305194, 5151652, 4, 61996201, 267766533211, 756974, 6, 8222822110984, 61411235, 6114596, 81472244, 81793104826252, 61300112, 4, 52135266, 71032125629272, 41479134, 7, 82095281, 4937147421273, 41075153, 5, 81881302608Test Case 2 is derived from a combined auction containing 10 bidders, 10 bids, and 30 bids. Its serial numbers, bids, and biddings are shown in Table2.Table 2
Data of Test Case 2.
Serial numberBidsBiddingSerial numberBidsBidding1(B, D, H)2407.1916(F, J)1410.362（F, H, I)2309.0017(C, I)1135.493(F, H, J)2224.4318(F, G)1022.734（B, D, E)2145.0619(A, D)943.725(G, I, J)2067.0120(H)906.366(B, D, F)2040.4821(I)840.5687(B, F, I)1998.8022(D)827.868(C, E, H)1881.2223(J)771.949(H, I)1798.2824(E)626.5010(A, D, E)1652.1625(B)607.2311(C, F, J)1646.9226(A, G)566.8712(B, F, G)1620.6827(F)531.8913(E, I)1518.7728(G)415.2614(F, H)1478.8129(C)273.9715(B, J)1469.6830(A)101.12


### 5.2. Experimental Setup

Experimental hardware environment used was Intel(R) Core(TM) i3 CPU M2.27 GHz, 2 GB RAM. Experimental software environment used was MATLAB 2018a. In order to evaluate the performance of CE on the WDP, we selected two classic algorithms: genetic algorithm (GA) [44] and particle swarm optimization algorithm (PSO) [45] for comparison.The population size of the three algorithms is 1000, and the total number of valid bids was 30 in both test cases. The maximum number of iterations of Test Cases 1 and 2 is 200 and 500, respectively, and other related parameter settings are shown in Table3, which determines the dimensionality n of the search space.Table 3
Parameter setting of GA, PSO, and CE for solving the winner determination problem (WDP).
AlgorithmParameter descriptionSymbolValueGACrossover percentagepc0.8Mutation percentagepm0.3Mutation ratemu0.02PSOMax inertia weightwmax0.9Min inertia weightwmin0.4Acceleration coefficientc1, c22CERarity parameterρ0.01Smoothing parameterα0.7Number of elitesNe20


### 5.3. Results and Analysis

We used CE, GA, and PSO to solve Test Cases 1 and 2, respectively. Tables4 and 5 give the statistical results of 30 independent experiments of the two test cases, respectively.Table 4
Comparison of results from 30 experiments for Test Case 1.
The optimal solutionAlgorithmAverage of time (s)The best resultThe worst resultAverage of resultsSuccess rate (%)4590GA6.19459045584578.8753.33PSO1.30459044724575.0766.67CE1.26459045014584.3086.67Table 5
Comparison of results from 30 experiments for Test Case 2.
The optimal solutionAlgorithmAverage of time (s)The best resultThe worst resultAverage of resultsSuccess rate (%)6216.82GA15.666216.826141.246181.8923.33PSO3.506216.826120.076186.7120.00CE3.316216.826134.106202.5453.33The numerical results in Table4 and 5 show that CE can solve the WDP of combinatorial auctions. Compared with the genetic algorithm and the particle swarm optimization algorithm, CE can not only obtain the optimal solution consistent with them, but also obtain a larger average return than them, which verifies that CE is effective in solving the WDP. It can also be seen that CE is the fastest algorithm, and CE outperforms GA and PSO in terms of success rate. Above all, CE always outperforms GA and PSO in both solution quality and efficiency.Figures1 and 2 show the average change of the objective function during the 30 experimental iterations of the three algorithms to solve Test Cases 1 and 2, that is, the convergence process of the three algorithms. It is found from the two figures that CE has the fastest convergence speed, followed by PSO, and GA is the slowest. Because the time running cost of CE is a linear function of the dimensionality of the search space, it is advantageous to use the CE algorithm to solve large-scale (large total number of quotes) WDP problems.Figure 1
Comparison of the convergence characteristics of the three algorithms on Test Case 1.Figure 2
Comparison of the convergence characteristics of the three algorithms on Test Case 2.


## 5.1. Descriptions of the Test Cases

In order to verify the performance of CE on the WDP, this paper selects two classic sets of data for testing [42, 43]. Test Case 1 is derived from a combined auction containing 10 bidders, 8 bids, and 30 bids. Its serial numbers, bids, and biddings are shown in Table 1.Table 1
Data of Test Case 1.
Serial numberBidsBiddingSerial numberBidsBidding12, 4, 8240116890322, 4, 6204217327034840181, 4, 5165844, 6, 82305194, 5151652, 4, 61996201, 267766533211, 756974, 6, 8222822110984, 61411235, 6114596, 81472244, 81793104826252, 61300112, 4, 52135266, 71032125629272, 41479134, 7, 82095281, 4937147421273, 41075153, 5, 81881302608Test Case 2 is derived from a combined auction containing 10 bidders, 10 bids, and 30 bids. Its serial numbers, bids, and biddings are shown in Table2.Table 2
Data of Test Case 2.
Serial numberBidsBiddingSerial numberBidsBidding1(B, D, H)2407.1916(F, J)1410.362（F, H, I)2309.0017(C, I)1135.493(F, H, J)2224.4318(F, G)1022.734（B, D, E)2145.0619(A, D)943.725(G, I, J)2067.0120(H)906.366(B, D, F)2040.4821(I)840.5687(B, F, I)1998.8022(D)827.868(C, E, H)1881.2223(J)771.949(H, I)1798.2824(E)626.5010(A, D, E)1652.1625(B)607.2311(C, F, J)1646.9226(A, G)566.8712(B, F, G)1620.6827(F)531.8913(E, I)1518.7728(G)415.2614(F, H)1478.8129(C)273.9715(B, J)1469.6830(A)101.12


## 5.2. Experimental Setup

Experimental hardware environment used was Intel(R) Core(TM) i3 CPU M2.27 GHz, 2 GB RAM. Experimental software environment used was MATLAB 2018a. In order to evaluate the performance of CE on the WDP, we selected two classic algorithms: genetic algorithm (GA) [44] and particle swarm optimization algorithm (PSO) [45] for comparison.The population size of the three algorithms is 1000, and the total number of valid bids was 30 in both test cases. The maximum number of iterations of Test Cases 1 and 2 is 200 and 500, respectively, and other related parameter settings are shown in Table3, which determines the dimensionality n of the search space.Table 3
Parameter setting of GA, PSO, and CE for solving the winner determination problem (WDP).
AlgorithmParameter descriptionSymbolValueGACrossover percentagepc0.8Mutation percentagepm0.3Mutation ratemu0.02PSOMax inertia weightwmax0.9Min inertia weightwmin0.4Acceleration coefficientc1, c22CERarity parameterρ0.01Smoothing parameterα0.7Number of elitesNe20


## 5.3. Results and Analysis

We used CE, GA, and PSO to solve Test Cases 1 and 2, respectively. Tables4 and 5 give the statistical results of 30 independent experiments of the two test cases, respectively.Table 4
Comparison of results from 30 experiments for Test Case 1.
The optimal solutionAlgorithmAverage of time (s)The best resultThe worst resultAverage of resultsSuccess rate (%)4590GA6.19459045584578.8753.33PSO1.30459044724575.0766.67CE1.26459045014584.3086.67Table 5
Comparison of results from 30 experiments for Test Case 2.
The optimal solutionAlgorithmAverage of time (s)The best resultThe worst resultAverage of resultsSuccess rate (%)6216.82GA15.666216.826141.246181.8923.33PSO3.506216.826120.076186.7120.00CE3.316216.826134.106202.5453.33The numerical results in Table4 and 5 show that CE can solve the WDP of combinatorial auctions. Compared with the genetic algorithm and the particle swarm optimization algorithm, CE can not only obtain the optimal solution consistent with them, but also obtain a larger average return than them, which verifies that CE is effective in solving the WDP. It can also be seen that CE is the fastest algorithm, and CE outperforms GA and PSO in terms of success rate. Above all, CE always outperforms GA and PSO in both solution quality and efficiency.Figures1 and 2 show the average change of the objective function during the 30 experimental iterations of the three algorithms to solve Test Cases 1 and 2, that is, the convergence process of the three algorithms. It is found from the two figures that CE has the fastest convergence speed, followed by PSO, and GA is the slowest. Because the time running cost of CE is a linear function of the dimensionality of the search space, it is advantageous to use the CE algorithm to solve large-scale (large total number of quotes) WDP problems.Figure 1
Comparison of the convergence characteristics of the three algorithms on Test Case 1.Figure 2
Comparison of the convergence characteristics of the three algorithms on Test Case 2.


## 6. Conclusion

This paper attempts to use CE to solve the WDP of large-scale combinatorial auctions and uses the elite strategy and the importance sampling method to reduce the number of samples and speed up convergence. The proposed method was evaluated on two test data samples and compared with GA and PSO. The numerical results show that the CE method always outperforms the GA and PSO methods in both solution quality and efficiency. It is therefore advantageous to use CE to solve large-scale (large total number of quotes) WDP problems. All in all, the CE method provides a high-quality and effective solution of the WDP.



---

*Source: 5691719-2020-10-12.xml*