On a conjecture by Gale about one-sided matching problems
From MaRDI portal
Publication:2277345
Matching problems are decision problems involving the assignment of n objects to n agents. A mechanism is a rule for making such matching and matchings are allowed to be a probability distribution over pure matchings. This paper shows that for \(n\geq 3\), there exists no mechanism which satisfies symmetry, Pareto optimality and strategy-proofness. Some extensions of this result to more general matching problems are also considered.
Recommendations
- A one-sided many-to-many matching problem
- Pareto stable matchings under one-sided matroid constraints
- On the completeness of a generalized matching problem
- Envy-free matchings with one-sided preferences and matroid constraints
- On the uniqueness and numerical approximations for a matching problem
- scientific article; zbMATH DE number 1033855
- Matching theory and Barnette's conjecture
- Maximum stable matching with one-sided ties of bounded length
- Maximum stable matching with one-sided ties of bounded length
Cites work
- College Admissions and the Stability of Marriage
- scientific article; zbMATH DE number 3231692 (Why is no real title available?)
- scientific article; zbMATH DE number 3095897 (Why is no real title available?)
- Manipulation of Voting Schemes: A General Result
- Optimal Allocation of Public Goods: A Solution to the "Free Rider" Problem
- Straightforwardness of Game Forms with Lotteries as Outcomes
Cited in
(94)- Random assignment under weak preferences
- The Becker-Brock efficient matching theorem with a supermodular technology defined on an \(n\)-lattice
- A tale of two mechanisms: Student placement
- Top dominance and the possibility of strategy-proof stable solutions to matching problems
- Ordinal efficiency and dominated sets of assignments.
- Consistency in house allocation problems
- The generalized random priority mechanism with budgets
- Probabilistic assignment: an extension approach
- The object allocation problem with random priorities
- Lone wolves in infinite, discrete matching markets
- Computational aspects of assigning agents to a line
- Impossibilities for probabilistic assignment
- Efficient and fair assignment mechanisms are strongly group manipulable
- Designing mechanisms to focalize welfare-improving strategies
- A note on the assignment problem with uniform preferences
- House allocation with existing tenants
- Strategy-proofness and population-monotonicity for house allocation problems
- Conditions for incentive compatibility in models with multidimensional allocation functions and one-dimensional types
- Assigning papers to referees
- Upper-contour strategy-proofness in the probabilistic assignment problem
- Partial strategyproofness: relaxing strategyproofness for the random assignment problem
- Fairness and efficiency for allocations with participation constraints
- Ex-post favoring ranks: a fairness notion for the random assignment problem
- On the complexity of fair house allocation
- A pessimist's approach to one-sided matching
- Decision-making with reference information
- Matching and scheduling of student-company-talks for a university it-speed dating event
- Continuity and incentive compatibility in cardinal mechanisms
- On endowments and indivisibility: partial ownership in the Shapley-Scarf model
- Matching inequality and strategic behavior under the Boston mechanism: evidence from China's college admissions
- Inefficiencies on linking decisions
- The impossibility of strategy-proof, Pareto efficient, and individually rational rules for fractional matching
- When are efficient and fair assignment mechanisms group strategy-proof?
- Size versus truthfulness in the house allocation problem
- Envy-freeness in house allocation problems
- Fairness and efficiency in strategy-proof object allocation mechanisms
- Efficient lottery design
- House allocation with existing tenants: an equivalence
- Matching with quorums
- Matching mechanisms and matching quality: evidence from a top university in China
- Serial dictatorship and Pareto optimality
- Reducing rank-maximal to maximum weight matching
- Characterizations of the optimal stable allocation mechanism
- Welfare and stability in senior matching markets
- On one-sided versus two-sided matching games
- Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design
- Robust ex-post Pareto efficiency and fairness in random assignments: two impossibility results
- Multi resource allocation with partial preferences
- Strategy-proof allocation with outside option
- Profile-based optimal matchings in the student/project allocation problem
- Social welfare in one-sided matching markets without money
- Bounded Unpopularity Matchings
- Strategy-proof stochastic assignment
- The Pareto-dominant strategy-proof and fair rule for problems with indivisible goods
- Probabilistic assignment of objects: characterizing the serial rule
- On mechanisms eliciting ordinal preferences
- Probabilistic assignment problem with multi-unit demands: a generalization of the serial rule and its characterization
- Assigning agents to a line
- Strategic issues in one-to-one matching with externalities
- Pareto optimal matchings in many-to-many markets with ties
- Smoothed and average-case approximation ratios of mechanisms: beyond the worst-case analysis
- Evaluating assignment without transfers: a market perspective
- Popular mixed matchings
- Weighted popular matchings
- Favoring Eagerness for Remaining Items: Designing Efficient, Fair, and Strategyproof Mechanisms
- A new solution to the random assignment problem.
- House allocation with transfers
- Review of the theory of stable matchings and contract systems
- The object allocation problem with favoring upper ranks
- Optimal assignment mechanisms with imperfect verification
- Strategy-proof and envy-free mechanisms for house allocation
- Inefficiency of random serial dictatorship under incomplete information
- On wastefulness of random assignments in discrete allocation problems
- Bounded incentives in manipulating the probabilistic serial rule
- On existence of truthful fair cake cutting mechanisms
- Strategy-proofness in linear production economies with homothetic or quasi-linear preferences
- A new impossibility result for random assignments
- Strategy-proofness in private good economies with linear preferences: an impossibility result
- Bounded unpopularity matchings
- A Lattice Linear Predicate Parallel Algorithm for the Housing Market Problem
- Game-theoretically secure protocols for the ordinal random assignment problem
- The price of anarchy of probabilistic serial in one-sided allocation problems
- Ordinal efficiency and the polyhedral separating hyperplane theorem
- On (constrained) efficiency of strategy-proof random assignment
- Randomized strategyproof mechanisms with best of both worlds fairness and efficiency
- Note on Gale's conjecture in one-sided matching problems
- Envy-free House allocation with minimum subsidy
- Transversals, systems of distinct representatives, mechanism design, and matching
- Strategy-proofness and the core in house allocation problems
- Consistency in the probabilistic assignment model
- Why do popular mechanisms lack efficiency in random environments?
- A solution to the random assignment problem on the full preference domain
- The probabilistic serial mechanism with private endowments
- An impossibility theorem for matching problems
This page was built for publication: On a conjecture by Gale about one-sided matching problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2277345)
