An Equilibrium-Based Approach for Determining Winners in Combinatorial Auctions

Determining winners in combinatorial auctions is an NP-complete problem. Based on the idea of searching Nash Equilibria (NE), this paper presents a local search procedure to determine winners. To improve the solution quality calculated by the local search, we propose Nash Equilibrium Search Approach (NESA) to probe various NE solutions. According to the simulation results, auctioneer´s revenue in NESA is at least 1.08% and 9.10% more than that in a general GA and Casanova, respectively. A stable solution based on NESA will be obtained within 400 seconds. Moreover, simulation results show that the solution quality of NESA is near-optimal.