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, 1-10

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)
http://downloads.hindawi.com/journals/JAM/2014/845071.pdf (application/pdf)
http://downloads.hindawi.com/journals/JAM/2014/845071.xml (text/xml)

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:hin:jnljam:845071

DOI: 10.1155/2014/845071

Access Statistics for this article

More articles in Journal of Applied Mathematics from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().