Auctions, Market Mechanisms and Their Applications. First International ICST Conference, AMMA 2009, Boston, MA, USA, May 8-9, 2009, Revised Selected Papers

Research Article

Fair Package Assignment

Download269 downloads
  • @INPROCEEDINGS{10.1007/978-3-642-03821-1_14,
        author={S\^{e}bastien Lahaie and David Parkes},
        title={Fair Package Assignment},
        proceedings={Auctions, Market Mechanisms and Their Applications. First International ICST Conference, AMMA 2009, Boston, MA, USA, May 8-9, 2009, Revised Selected Papers},
        proceedings_a={AMMA},
        year={2012},
        month={5},
        keywords={},
        doi={10.1007/978-3-642-03821-1_14}
    }
    
  • Sébastien Lahaie
    David Parkes
    Year: 2012
    Fair Package Assignment
    AMMA
    Springer
    DOI: 10.1007/978-3-642-03821-1_14
Sébastien Lahaie1,*, David Parkes2,*
  • 1: Yahoo Research
  • 2: Harvard University
*Contact email: lahaies@yahoo-inc.com, parkes@eecs.harvard.edu

Abstract

We consider the problem of fair allocation in the package assignment model, where a set of indivisible items, held by single seller, must be efficiently allocated to agents with quasi-linear utilities. A fair assignment is one that is efficient and envy-free. We consider a model where bidders have superadditive valuations, meaning that items are pure complements. Our central result is that core outcomes are fair and even coalition-fair over this domain, while fair distributions may not even exist for general valuations. Of relevance to auction design, we also establish that the core is equivalent to the set of anonymous-price competitive equilibria, and that superadditive valuations are a maximal domain that guarantees the existence of anonymous-price competitive equilibrium. Our results are analogs of core equivalence results for linear prices in the standard assignment model, and for nonlinear, non-anonymous prices in the package assignment model with general valuations.