资源论文Better Strategyproof Mechanisms without Payments or Prior — An Analytic Approach

Better Strategyproof Mechanisms without Payments or Prior — An Analytic Approach

2019-11-22 | |  71 |   63 |   0
Abstract We revisit the problem of designing strategyproof mechanisms for allocating divisible items among two agents who have linear utilities, where payments are disallowed and there is no prior information on the agents’ preferences. The objective is to design strategyproof mechanisms which are competitive against the most efficient (but not strategyproof) mechanism. For the case with two items: • We provide a set of sufficient conditions for strategyproofness. • We use an analytic approach to derive strategyproof mechanisms which are more competitive than all prior strategyproof mechanisms. • We improve the linear-program-based proof of Guo and Conitzer [2010] to show new upper bounds on competitive ratios. • We provide the first compact proof on upper bound of competitiveness. For the cases with any number of items, we build on the Partial Allocation mechanisms introduced by Cole et al. [2013a; 2013b] to design a strategyproof mechanism which is 0.67776-competitive, breaking the 23 barrier. We also propose a new sub-class of strategyproof mechanisms for any numbers of agents and items, which we call it Dynamic-Increasing-Price mechanisms, where each agent purchases the items using virtual money, and the prices of the items depend on other agents’ preferences.

上一篇:Truthfulness of a Proportional Sharing Mechanism in Resource Exchange

下一篇:Approximating Value Equivalence in Interactive Dynamic Influence Diagrams Using Behavioral Coverage

用户评价
全部评价

热门资源

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • A Mathematical Mo...

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

  • Rating-Boosted La...

    The performance of a recommendation system reli...