The complexity of computing the random priority allocation matrix

DOI10.1287/MOOR.2014.0707MaRDI QIDQ3465944zbMATH OpenOpenAlexFDO

Authors Daniela Saban, Jay Sethuraman

Publication date 29 January 2016

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.2014.0707

zbMATH Keywords

assignmentcomplexitygraphsmatchingnetworksrandom priorityrandomized algorithms

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matching models (91B68)

Recommendations

• The object allocation problem with random priorities
• A solution to the random assignment problem on the full preference domain
• Asymptotic Equivalence of Probabilistic Serial and Random Priority Mechanisms
• A new solution to the random assignment problem.

Cites work

• Approximate counting, uniform generation and rapidly mixing Markov chains
• College admissions with affirmative action
• Minimum Edge Dominating Sets
• On cores and indivisibility
• Parametrized algorithms for random serial dictatorship
• Pareto optimality in many-to-many matching problems
• Popular matchings with variable job capacities
• Probability Inequalities for Sums of Bounded Random Variables
• Scheduling with Opting Out: Improving upon Random Priority
• School choice with controlled choice constraints: hard bounds versus soft bounds
• Strategy-Proof Allocation Mechanisms at Differentiable Points
• The complexity of computing the permanent

Cited in

(12)

• Complexity of finding Pareto-efficient allocations of highest welfare
• A pessimist's approach to one-sided matching
• Pareto optimal allocation under uncertain preferences: uncertainty models, algorithms, and complexity
• Size versus truthfulness in the house allocation problem
• Random serial dictatorship: the one and only
• Favoring Eagerness for Remaining Items: Designing Efficient, Fair, and Strategyproof Mechanisms
• Game-theoretically secure protocols for the ordinal random assignment problem
• On Pareto optimal balanced exchanges
• Estimating the expected social welfare and cost of random serial dictatorship
• Pareto-optimal linear programming
• The strong core of housing markets with partial order preferences
• Counting houses of Pareto optimal matchings in the house allocation problem

This page was built for publication: The complexity of computing the random priority allocation matrix

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3465944)