Abstract
Consider the problem of allocating n objects to n agents who have strict ordinal preferences over the objects. We study the Random Priority (RP) mechanism, in which an ordering over the agents is selected uniformly at random; the first agent is then allocated his most-preferred object, the second agent is allocated his most-preferred object among the remaining ones, and so on. The output of this mechanism is a bi-stochastic allocation matrix, in which entry (i,a) indicates the probability that agent i obtains object a (whenever objects are indivisible), or the fraction of object a allocated to agent i (when objects are divisible). Our main result is that the allocation matrix associated with the RP mechanism is hard to compute, in a sense that can be made precise using the theory of computational complexity. An important consequence is that an efficient algorithm to compute the allocation matrix exactly is unlikely. In addition, we examine two decision problems associated with the RP allocation: deciding whether an agent gets an object with probability 1, and deciding whether an agent gets an object with positive probability. We provide a polynomial-time algorithm to solve the former and show that the latter is hard to decide. This hardness result has two strong implications. First, it is not possible to design an efficient algorithm to get a good (multiplicative) approximation to the RP allocation matrix (under suitable complexity-theoretic assumptions). Second, for an assignment problem with inadmissible objects, it is hard to decide whether or not a given subset of objects is matched in some Pareto efficient matching.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Saban, D., Sethuraman, J. (2013). The Complexity of Computing the Random Priority Allocation Matrix. In: Chen, Y., Immorlica, N. (eds) Web and Internet Economics. WINE 2013. Lecture Notes in Computer Science, vol 8289. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45046-4_34
Download citation
DOI: https://doi.org/10.1007/978-3-642-45046-4_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45045-7
Online ISBN: 978-3-642-45046-4
eBook Packages: Computer ScienceComputer Science (R0)