The Complexity of Computing the Random Priority Allocation Matrix

References

• Abdulkadiroglu A (2005) College admissions with affirmative action. Internat. J. Game Theory 33:525–549.Crossref, Google Scholar
• 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.Crossref, Google Scholar
• Aziz H, Brandt F, Brill M (2013) The computational complexity of random serial dictatorship. Econom. Lett. 121(3):341–345.Crossref, Google Scholar
• Aziz H, Mestre J (2014) Parametrized algorithms for random serial dictatorship. Math. Soc. Sci. 72:1–6.Crossref, Google Scholar
• 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.Crossref, Google Scholar
• 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.Crossref, Google Scholar
• Crés H, Moulin H (2001) Scheduling with opting out: Improving upon random priority. Oper. Res. 49(4):565–577.Link, Google Scholar
• 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.Crossref, Google Scholar
• 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.Crossref, Google Scholar
• Hoeffding W (1963) Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58(301):13–30.Crossref, Google Scholar
• Horton J, Kilakos K (1993) Minimum edge dominating sets. SIAM J. Discrete Math. 6(3):375–387.Crossref, Google Scholar
• Jerrum M (2003) Counting, Sampling and Integrating: Algorithms and Complexity, Lectures in Mathematics ETH Zürich (Birkhäuser Basel, Basel, Switzerland).Crossref, Google Scholar
• Kavitha T, Nasre M (2009) Popular matchings with variable job capacities. Proc. 20th Internat. Sympos. Algorithms Comput. ISAAC ’09 (Springer-Verlag, Berlin), 423–433.Crossref, Google Scholar
• Satterthwaite MA, Sonnenschein H (1981) Strategy-proof allocation mechanisms at differentiable points. Rev. Econom. Stud. 48(4): 587–597.Crossref, Google Scholar
• Shapley L, Scarf H (1974) On cores and indivisibility. J. Math. Econom. 1(1):23–37.Crossref, Google Scholar
• Sinclair A, Jerrum M (1989) Approximate counting, uniform generation and rapidly mixing markov chains. Inform. Comput. 82(1): 93–133.Crossref, Google Scholar
• Toda S (1989) On the computational power of pp and (+)p. Proc. 30th Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 514–519.Crossref, Google Scholar
• Valiant LG (1979) The complexity of computing the permanent. Theoret. Comput. Sci. 8(2):189–201.Crossref, Google Scholar