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

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

Index Terms

The Complexity of Computing the Random Priority Allocation Matrix
1. Applied computing

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

3
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents