A Game Theoretical Approach for Solving Winner Determination Problems

Chen-Kun Tsung, Hann-Jang Ho and Sing-Ling Lee

Journal of Applied Mathematics, 2014, vol. 2014, issue 1

Abstract: Determining the winners in combinatorial auctions to maximize the auctioneer′s revenue is an NP‐complete problem. Computing an optimal solution requires huge computation time in some instances. In this paper, we apply three concepts of the game theory to design an approximation algorithm: the stability of the Nash equilibrium, the self‐learning of the evolutionary game, and the mistake making of the trembling hand assumption. According to our simulation results, the proposed algorithm produces near‐optimal solutions in terms of the auctioneer′s revenue. Moreover, reasonable computation time is another advantage of applying the proposed algorithm to the real‐world services.

Date: 2014
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1155/2014/845071

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:jnljam:v:2014:y:2014:i:1:n:845071

Access Statistics for this article

More articles in Journal of Applied Mathematics from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().