Research map / Learning theory and algorithms / Submodular and game algorithms
An Analysis Framework for Metric Voting based on LP Duality
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (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 LP duality and construct low-cost flows instead of reasoning directly over consistent metric spaces | Metric distortion analysis · Metric voting | distortion upper bound | Helped |
| Apply the generalized preference-chain bound to Ranked Pairs | Ranked Pairs · Metric voting, n candidates | distortion: at most 2 \sqrt{2} \cdot \sqrt{n} + o(\sqrt{n}); at least \frac{\sqrt{2}}{2} \sqrt{n} | Mixed |
| Apply the generalized preference-chain bound to Schulze | Schulze · Metric voting, n candidates | distortion: at most 2 \sqrt{2} \cdot \sqrt{n} + o(\sqrt{n}); at least \frac{\sqrt{2}}{2} \sqrt{n} | Mixed |
| Require a perfect matching in each candidate-comparison bipartite graph | All Bipartite Matchings · Metric voting | distortion upper bound: 3 | Helped |
| Use preference chains of arbitrary length rather than only short majority-preference paths | Distortion bounds for candidate paths · Metric voting | distortion upper bound: 2+\sqrt{5} \approx 4.236 | Helped |
Closest papers by meaning
- Metric Distortion of Line-up Elections: The Right Person for the Right Job (AAAI 2025 · similarity 0.91)
- On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries (AAAI 2025 · similarity 0.91)
- Improved Metric Distortion via Threshold Approvals (AAAI 2024 · similarity 0.90)
- Tight Bounds on the Distortion of Randomized and Deterministic Distributed Voting (NeurIPS 2025 · similarity 0.90)
- Constant-Factor Distortion Mechanisms for k-Committee Election (AAAI 2025 · similarity 0.88)
- Independence of Irrelevant Alternatives under the Lens of Pairwise Distortion (AAAI 2024 · similarity 0.87)
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.