research-article

The Complexity of Computing the Random Priority Allocation Matrix

Authors: Daniela Saban, Jay SethuramanAuthors Info & Claims

Mathematics of Operations Research, Volume 40, Issue 4

Pages 1005 - 1014

https://doi.org/10.1287/moor.2014.0707

Published: 01 October 2015 Publication History

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.

References

[1]

Abdulkadiroglu A (2005) College admissions with affirmative action. Internat. J. Game Theory 33:525–549.

[2]

Abraham DJ, Cechlarova K, Manlove DF, Mehlhorn K (2005) Pareto optimality in house allocation problems. Algorithms and Computation, Lecture Notes in Computer Science, Vol. 3341 (Springer, Berlin), 3–15.

[3]

Aziz H, Brandt F, Brill M (2013) The computational complexity of random serial dictatorship. Econom. Lett. 121(3):341–345.

[4]

Aziz H, Mestre J (2014) Parametrized algorithms for random serial dictatorship. Math. Soc. Sci. 72:1–6.

[5]

Brightwell G, Winkler P (1991) Counting linear extensions is #P-complete. Proc. 23rd Annual ACM Symp. Theory Comput. STOC ’91 (ACM, New York), 175–181.

[6]

Cechlárová K, Eirinakis P, Fleiner T, Magos D, Mourtos I, Potpinkov E (2014) Pareto optimality in many-to-many matching problems. Discrete Optim. 14:160–169.

Digital Library

[7]

Crés H, Moulin H (2001) Scheduling with opting out: Improving upon random priority. Oper. Res. 49(4):565–577.

Digital Library

[8]

Ehlers L, Hafalir I, Yenmez B, Yildirim M (2014) School choice with controlled choice constraints: Hard bounds versus soft bounds. J. Econom. Theory 153:648–683.

[9]

Haeringer G, Iehlé V (2014) Two-sided matching with one-sided preferences. Proc. Fifteenth ACM Conf. Econom. Comput., EC ’14 (ACM, New York), 353–353.

[10]

Hoeffding W (1963) Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58(301):13–30.

[11]

Horton J, Kilakos K (1993) Minimum edge dominating sets. SIAM J. Discrete Math. 6(3):375–387.

Digital Library

[12]

Jerrum M (2003) Counting, Sampling and Integrating: Algorithms and Complexity, Lectures in Mathematics ETH Zürich (Birkhäuser Basel, Basel, Switzerland).

[13]

Kavitha T, Nasre M (2009) Popular matchings with variable job capacities. Proc. 20th Internat. Sympos. Algorithms Comput. ISAAC ’09 (Springer-Verlag, Berlin), 423–433.

Digital Library

[14]

Satterthwaite MA, Sonnenschein H (1981) Strategy-proof allocation mechanisms at differentiable points. Rev. Econom. Stud. 48(4): 587–597.

[15]

Shapley L, Scarf H (1974) On cores and indivisibility. J. Math. Econom. 1(1):23–37.

[16]

Sinclair A, Jerrum M (1989) Approximate counting, uniform generation and rapidly mixing markov chains. Inform. Comput. 82(1): 93–133.

Digital Library

[17]

Toda S (1989) On the computational power of pp and (+)p. Proc. 30th Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 514–519.

Digital Library

[18]

Valiant LG (1979) The complexity of computing the permanent. Theoret. Comput. Sci. 8(2):189–201.

Cited By

Walsh TLarson K(2024)Mechanisms that play a game, not toss a coinProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/333(3005-3013)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/333
Gonczarowski YThomas CMohar BShinkar IO'Donnell R(2024)Structural Complexities of Matching MechanismsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649737(455-466)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649737
Caragiannis IHomrighausen S(2024)Estimating the Expected Social Welfare and Cost of Random Serial DictatorshipAlgorithmic Game Theory10.1007/978-3-031-71033-9_11(184-201)Online publication date: 3-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71033-9_11
Show More Cited By

Index Terms

The Complexity of Computing the Random Priority Allocation Matrix

Index terms have been assigned to the content through auto-classification.

Recommendations

The Complexity of Computing the Random Priority Allocation Matrix
WINE 2013: Proceedings of the 9th International Conference on Web and Internet Economics - Volume 8289

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 ...
Student-Project-Resource Allocation: Complexity of the Symmetric Case
PRIMA 2018: Principles and Practice of Multi-Agent Systems
Abstract
In this paper, we consider a student-project-resource allocation problem, in which students and indivisible resources are allocated to every project. The allocated resources determine endogenously the student capacity of a project. Traditionally, ...
The Landscape of Communication Complexity Classes

We prove several results which, together with prior work, provide a nearly-complete picture of the relationships among classical communication complexity classes between $${\mathsf{P}}$$P and $${\mathsf{PSPACE}}$$PSPACE, short of proving lower bounds ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematics of Operations Research

Mathematics of Operations Research Volume 40, Issue 4

November 2015

293 pages

ISSN:0364-765X

Issue’s Table of Contents

Copyright © 2015, INFORMS.

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 October 2015

Received: 18 January 2014

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Walsh TLarson K(2024)Mechanisms that play a game, not toss a coinProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/333(3005-3013)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/333
Gonczarowski YThomas CMohar BShinkar IO'Donnell R(2024)Structural Complexities of Matching MechanismsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649737(455-466)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649737
Caragiannis IHomrighausen S(2024)Estimating the Expected Social Welfare and Cost of Random Serial DictatorshipAlgorithmic Game Theory10.1007/978-3-031-71033-9_11(184-201)Online publication date: 3-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71033-9_11
Banerjee SEichhorn MKempe DLeyton-Brown KSamuelson LHartline J(2023)Allocating with Priorities and Quotas: Algorithms, Complexity, and DynamicsProceedings of the 24th ACM Conference on Economics and Computation10.1145/3580507.3597733(209-240)Online publication date: 9-Jul-2023
https://dl.acm.org/doi/10.1145/3580507.3597733
Bade S(2020)Random Serial DictatorshipMathematics of Operations Research10.1287/moor.2019.098745:1(353-368)Online publication date: 1-Feb-2020
https://dl.acm.org/doi/10.1287/moor.2019.0987

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents