Research map / Learning theory and algorithms / Submodular and game algorithms
Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism
Haris Aziz, Alexander Lam, Mashbat Suzuki, Toby Walsh
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Random Rank, choosing a reported location uniformly by rank | Facility location · Two-location profiles | Strong Proportionality in expectation | Improved |
| Require deterministic strategyproofness together with Strong Proportionality | Deterministic facility location mechanisms · Two agents at 0 and 0.5, or at 0 and 1 | Strong Proportionality and strategyproofness | Hurt |
| Add a probability p of placing the facility at the average agent location to Random Rank | AverageOrRandomRank · Two-location profiles | Strategyproofness in expectation: p∈[0,\frac{1}{2}] | Mixed |
| Set p to 1/2 in AverageOrRandomRank | Random Rank · Three agents at 0, 0, and 1/3 | Probability of facility at the average location 1/9: 0 -> \frac{1}{2} | Improved |
| Replace universal truthfulness with strategyproofness in expectation | AverageOrRandomRank · Facility location | Ex-post fairness | Improved |
| Weaken Strong Proportionality in expectation to Proportionality in expectation | Randomized facility location mechanisms · Unit interval | Mechanism uniqueness under universal truthfulness and anonymity | Hurt |
| Weaken universal anonymity to anonymity in expectation | Randomized facility location mechanisms · Unit interval | Universal anonymity | Hurt |
| Strengthen Strong Proportionality to Strong Proportional Fairness | Random Rank · Profiles with cohesive groups at nearby locations | Strong Proportional Fairness in expectation | Improved |
Closest papers by meaning
- Strategyproof Mechanisms for Group-Fair Obnoxious Facility Location Problems (AAAI 2024 · similarity 0.89)
- Randomized Strategic Facility Location with Predictions (NeurIPS 2024 · similarity 0.87)
- On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness (NeurIPS 2025 · similarity 0.87)
- Weak Strategyproofness in Randomized Social Choice (AAAI 2025 · similarity 0.86)
- Proportional Fairness in Clustering: A Social Choice Perspective (NeurIPS 2024 · similarity 0.86)
- Facility Location Games with Optional Preferences: A Revisit (AAAI 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
