Author name cluster

Anton Likhodedov

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

AAAI Conference 2005 Conference Paper

Approximating Revenue-Maximizing Combinatorial Auctions

Anton Likhodedov

Designing revenue-maximizing combinatorial auctions (CAs) is a recognized open problem in mechanism design. It is unsolved even for two bidders and two items for sale. Rather than attempting to characterize the optimal auction, we focus on designing approximations (suboptimal auction mechanisms which yield high revenue). Our approximations belong to the family of virtual valuations combinatorial auctions (VVCA). VVCA is a Vickrey-Clarke- Groves (VCG) mechanism run on virtual valuations that are linear transformations of the bidders’ real valuations. We pursue two approaches to constructing approximately optimal CAs. The first is to construct a VVCA with worst-case and average-case performance guarantees. We give a logarithmic approximation auction for basic important special cases of the problem: 1) limited supply of items on sale with additive valuations and 2) unlimited supply. The second approach is to search the parameter space of VVCAs in order to obtain high-revenue mechanisms for the general problem. We introduce a series of increasingly sophisticated algorithms that use economic insights to guide the search and thus reduce the computational complexity. Our experiments demonstrate that in many cases these algorithms perform almost as well as the optimal VVCA, yield a substantial increase in revenue over the VCG mechanism and drastically outperform the straightforward algorithms in run-time.

PDF Details

AAAI Conference 2004 Conference Paper

Methods for Boosting Revenue in Combinatorial Auctions

Anton Likhodedov
Tuomas Sandholm

We study the recognized open problem of designing revenuemaximizing combinatorial auctions. It is unsolved even for two bidders and two items for sale. Rather than pursuing the pure economic approach of attempting to characterize the optimal auction, we explore techniques for automatically modifying existing mechanisms in a way that increase expected revenue. We introduce a general family of auctions, based on bidder weighting and allocation boosting, which we call virtual valuations combinatorial auctions (VVCA). All auctions in the family are based on the Vickrey-Clarke-Groves (VCG) mechanism, executed on virtual valuations that are linear transformations of the bidders’ real valuations. The restriction to linear transformations is motivated by incentive compatibility. The auction family is parameterized by the coefficients in the linear transformations. The problem of designing a high revenue mechanism is therefore reduced to search in the parameter space of VVCA. We analyze the complexity of the search for the optimal such mechanism and conclude that the search problem is computationally hard. Despite that, optimal parameters for VVCA can be found at least in settings with few items and bidders (the experiments show that VVCA yield a substantial increase in revenue over the traditionally used VCG). In larger auctions locally optimal parameters, which still yield an improvement over VCG, can be found.

PDF Details