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: (1) We provide a set of sufficient conditions for strategyproofness. (2) We use an analytic approach to derive strategyproof mechanisms which are more competitive than all prior strategyproof mechanisms. (3) We improve the linear-program-based proof of Guo and Conitzer to show new upper bounds on competitive ratios. (4) We provide the first "mathematical" upper bound proof. For the cases with any number of items: (1) We build on the Partial Allocation mechanisms introduced by to design a strategyproof mechanism which is 0.67776-competitive, breaking the 2 3 barrier. (2) We propose a new subclass of strategyproof mechanisms called Dynamical-Increasing-Price mechanisms, where each agent purchases the items using virtual money, and the prices of the items depend on other agents' preferences.
Guo and Conitzer @cite_4 considered a sub-class of SP mechanisms called Swap-Dictatorial mechanisms, in which each agent is a with probability @math , who chooses her favourite allocation from a predefined set of allowable allocations, and the other agent is allocated the remaining items. Swap-Dictatorial mechanisms can be generalized to more than two agents, by first generating a random order of the agents, and then each agent takes turn to choose her favourite allocation. They studied two sub-classes of Swap-Dictatorial mechanisms, Increasing-Price (IP) mechanisms and Linear-Increasing-Price (LIP) mechanisms. For the case with two items, they showed that there is a LIP mechanism which is @math -competitive against the first-best mechanism; they used a linear program to show that no SP mechanism can be better than @math -competitive. They also showed that as the number of items goes to infinity, IP and LIP mechanisms have maximal competitiveness of @math .
@cite_4
49938292
We investigate the problem of allocating items (private goods) among competing agents in a setting that is both prior-free and payment-free. Specificall, we focus on allocating multiple heterogeneous items between two agents with additive valuation functions. Our objective is to design strategy-proof mechanisms that are competitive against the most efficien (first-best allocation. We introduce the family of linear increasing-price (LIP) mechanisms. The LIP mechanisms are strategy-proof, prior-free, and payment-free, and they are exactly the increasing-price mechanisms satisfying a strong responsiveness property. We show how to solve for competitive mechanisms within the LIP family. For the case of two items, we fin a LIP mechanism whose competitive ratio is near optimal (the achieved competitive ratio is 0.828, while any strategy-proof mechanism is at most 0.841-competitive). As the number of items goes to infinit, we prove a negative result that any increasing-price mechanism (linear or nonlinear) has a maximal competitive ratio of 0.5. Our results imply that in some cases, it is possible to design good allocation mechanisms without payments and without priors.