资源论文Near-Optimal Approximation Mechanisms for Multi-Unit Combinatorial Auctions

Near-Optimal Approximation Mechanisms for Multi-Unit Combinatorial Auctions

2019-11-20 | |  55 |   35 |   0
Abstract We design and analyze deterministic truthful approximation mechanisms for multi-unit combinatorial auctions involving a constant number of distinct goods, each in arbitrary limited supply. Prospective buyers (bidders) have preferences over multisets of items, i.e., for more than one unit per distinct good, that are expressed through their private valuation functions. Our objective is to determine allocations of multisets that maximize the Social Welfare approximately. Despite the recent theoretical advances on the design of truthful combinatorial auctions (for multiple distinct goods in unit supply) and multi-unit auctions (for multiple units of a single good), results for the combined setting are much scarcer. We elaborate on the main developments of [Krysta et al., 2013], concerning bidders with multi-minded and submodular valuation functions, with an emphasis on the presentation of the relevant algorithmic techniques.

上一篇:Adapting to User Preference Changes in Interactive Recommendation

下一篇:Firefly Monte Carlo: Exact MCMC with Subsets of Data

用户评价
全部评价

热门资源

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to learn...

    The move from hand-designed features to learned...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...