Nash Equilibria in Combinatorial Auctions with Item Bidding and Subadditive Symmetric Valuations

Hiroyuki UMEDA  Takao ASANO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.9   pp.1324-1333
Publication Date: 2018/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E101.A.1324
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
Nash equilibrium,  combinatorial auction,  price of anarchy,  social welfare problem,  subadditivity,  

Full Text: PDF(775.3KB)
>>Buy this Article


Summary: 
We discuss Nash equilibria in combinatorial auctions with item bidding. Specifically, we give a characterization for the existence of a Nash equilibrium in a combinatorial auction with item bidding when valuations by n bidders satisfy symmetric and subadditive properties. By this characterization, we can obtain an algorithm for deciding whether a Nash equilibrium exists in such a combinatorial auction.