The Complexity of Computing the Random Priority Allocation Matrix

Daniela Saban () and Jay Sethuraman ()
Additional contact information
Daniela Saban: Graduate School of Business, Columbia University, New York, New York, 10027
Jay Sethuraman: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York, 10027

Mathematics of Operations Research, 2015, vol. 40, issue 4, 1005-1014

Abstract: The random priority (RP) mechanism is a popular way to allocate n objects to n agents with strict ordinal preferences over the objects. In the RP mechanism, 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 outcome of the mechanism is a bi-stochastic matrix in which entry ( i , a ) represents the probability that agent i is given object a . It is shown that the problem of computing the RP allocation matrix is #P-complete. Furthermore, it is NP-complete to decide if a given agent i receives a given object a with positive probability under the RP mechanism, whereas it is possible to decide in polynomial time whether or not agent i receives object a with probability 1. The implications of these results for approximating the RP allocation matrix as well as on finding constrained Pareto optimal matchings are discussed.

Keywords: networks; graphs; randomized algorithms; random priority; assignment; matching; complexity (search for similar items in EconPapers)
Date: 2015
References: Add references at CitEc
Citations View citations in EconPapers (1) Track citations by RSS feed

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2014.0707 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: http://EconPapers.repec.org/RePEc:inm:ormoor:v:40:y:2015:i:4:p:1005-1014

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Series data maintained by Mirko Janc ().