A solution to the random assignment problem on the full preference domain

DOI10.1016/j.jet.2005.05.001zbMath1142.90481DBLPjournals/jet/KattaS06OpenAlexW2106897266WikidataQ28112248 ScholiaQ28112248MaRDI QIDQ860356

Akshay-Kumar Katta, Jay Sethuraman

Publication date: 9 January 2007

Published in: Journal of Economic Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jet.2005.05.001

zbMATH Keywords

fairnessrandomizationassignmentstrategy-proofnessenvy-freenessmaximum flowsindifferencesordinal efficiency

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Matching models (91B68)

Related Items (57)

Favoring Eagerness for Remaining Items: Designing Efficient, Fair, and Strategyproof Mechanisms ⋮ A graph theoretic approach to the slot allocation problem ⋮ The generalized random priority mechanism with budgets ⋮ Convex strategyproofness with an application to the probabilistic serial mechanism ⋮ Why do popular mechanisms lack efficiency in random environments? ⋮ Incentives in the probabilistic serial mechanism ⋮ An equilibrium analysis of the probabilistic serial mechanism ⋮ Probabilistic assignment: an extension approach ⋮ Constrained random matching ⋮ On the tradeoff between efficiency and strategyproofness ⋮ The object allocation problem with random priorities ⋮ Fairness in Influence Maximization through Randomization ⋮ Multi-unit assignment under dichotomous preferences ⋮ Probabilistic assignment of indivisible objects when agents have the same preferences except the ordinal ranking of one object ⋮ Computational aspects of assigning agents to a line ⋮ Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design ⋮ The vigilant eating rule: a general approach for probabilistic economic design with constraints ⋮ Multi resource allocation with partial preferences ⋮ Random assignments with uniform preferences: an impossibility result ⋮ Random assignment: redefining the serial rule ⋮ Fair assignment of indivisible objects under ordinal preferences ⋮ Bounded incentives in manipulating the probabilistic serial rule ⋮ Ordinal Bayesian incentive compatibility in random assignment model ⋮ On existence of truthful fair cake cutting mechanisms ⋮ Strategy-proof and envy-free random assignment ⋮ Impossibilities for probabilistic assignment ⋮ Simultaneous eating algorithm and greedy algorithm in assignment problems ⋮ House allocation with fractional endowments ⋮ On mechanisms eliciting ordinal preferences ⋮ A note on object allocation under lexicographic preferences ⋮ Assigning papers to referees ⋮ Assignment Mechanisms Under Distributional Constraints ⋮ Probabilistic assignment problem with multi-unit demands: a generalization of the serial rule and its characterization ⋮ Probabilistic assignment of indivisible goods with single-peaked preferences ⋮ The extended serial correspondence on a rich preference domain ⋮ Assigning agents to a line ⋮ A constructive proof of the ordinal efficiency welfare theorem ⋮ A characterization of the extended serial correspondence ⋮ When is the probabilistic serial assignment uniquely efficient and envy-free? ⋮ Extended random assignment mechanisms on a family of good sets ⋮ A new ex-ante efficiency criterion and implications for the probabilistic serial mechanism ⋮ Random serial dictatorship and ordinally efficient contracts ⋮ Popular mixed matchings ⋮ Efficiency under a combination of ordinal and cardinal information on preferences ⋮ A note on the assignment problem with uniform preferences ⋮ Incompatibility of efficiency and strategyproofness in the random assignment setting with indifferences ⋮ Efficiency and stability of probabilistic assignments in marriage problems ⋮ Incentive properties for ordinal mechanisms ⋮ Random assignment of multiple indivisible objects ⋮ Universal Pareto dominance and welfare for plausible utility functions ⋮ Social Welfare in One-Sided Matching Markets without Money ⋮ Short trading cycles: paired kidney exchange with strict ordinal preferences ⋮ Random assignment under weak preferences ⋮ Submodular optimization views on the random assignment problem ⋮ Popularity, Mixed Matchings, and Self-Duality ⋮ Efficient rules for probabilistic assignment ⋮ Size versus fairness in the assignment problem

Cites Work

• Unnamed Item
• Ordinal efficiency and the polyhedral separating hyperplane theorem
• A simple random assignment problem with a unique solution
• Incentive compatibility in a market with indivisible goods
• Weak versus strong domination in a market with indivisible goods
• Queue allocation of indivisible goods
• Ordinal efficiency and dominated sets of assignments.
• On cores and indivisibility
• On a conjecture by Gale about one-sided matching problems
• Strategy-proof assignment on the full preference domain
• Strategy-proof allocation of indivisible goods
• Scheduling with Opting Out: Improving upon Random Priority
• Scheduling transmissions in a network
• Optimal sharing
• Optimal flows in networks with multiple sources and sinks
• A good algorithm for lexicographically optimal flows in multi-terminal networks
• The Sharing Problem
• Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
• A Fast Parametric Maximum Flow Algorithm and Applications
• Random Matching Under Dichotomous Preferences
• A new solution to the random assignment problem.

This page was built for publication: A solution to the random assignment problem on the full preference domain