TY - GEN
T1 - Optimal allocation in combinatorial auctions with quadratic utility functions
AU - Shioura, Akiyoshi
AU - Suzuki, Shunya
PY - 2011/5/13
Y1 - 2011/5/13
N2 - We discuss the optimal allocation problem in combinatorial auction, where the items are allocated to bidders so that the sum of the bidders' utilities is maximized. In this paper, we consider the case where utility functions are given by quadratic functions; the class of quadratic utility functions has a succinct representation but is sufficiently general. The main aim of this paper is to show the computational complexity of the optimal allocation problem with quadratic utility functions. We consider the cases where utility functions are submodular and supermodular, and show NP-hardness and/or polynomial-time exact/approximation algorithm. These results are given by using the relationship with graph cut problems such as the min/max cut problem and the multiway cut problem.
AB - We discuss the optimal allocation problem in combinatorial auction, where the items are allocated to bidders so that the sum of the bidders' utilities is maximized. In this paper, we consider the case where utility functions are given by quadratic functions; the class of quadratic utility functions has a succinct representation but is sufficiently general. The main aim of this paper is to show the computational complexity of the optimal allocation problem with quadratic utility functions. We consider the cases where utility functions are submodular and supermodular, and show NP-hardness and/or polynomial-time exact/approximation algorithm. These results are given by using the relationship with graph cut problems such as the min/max cut problem and the multiway cut problem.
UR - http://www.scopus.com/inward/record.url?scp=79955767269&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79955767269&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-20877-5_15
DO - 10.1007/978-3-642-20877-5_15
M3 - Conference contribution
AN - SCOPUS:79955767269
SN - 9783642208768
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 142
EP - 153
BT - Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings
T2 - 8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011
Y2 - 23 May 2011 through 25 May 2011
ER -