Cover Image

Breaking the Metric Voting Distortion Barrier

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Charikar, Moses, Ramakrishnan, Prasanna, Wang, Kangning, Wu, Hongxun
Format:	Preprint
Published:	2023
Subjects:	Computer Science and Game Theory Artificial Intelligence Discrete Mathematics Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Distortion of Metric Voting with Bounded Randomness
by: Cai, Ziyi, et al.
Published: (2026)

Approximately Dominating Sets in Elections
by: Charikar, Moses, et al.
Published: (2025)

Six Candidates Suffice to Win a Voter Majority
by: Charikar, Moses, et al.
Published: (2024)

Metric Distortion for Tournament Voting and Beyond
by: Charikar, Moses, et al.
Published: (2025)

Non-Exclusive Notifications for Ride-Hailing at Lyft I: Single-Cycle Approximation Algorithms
by: Ekbatani, Farbod, et al.
Published: (2026)

Monotone Randomized Apportionment
by: Correa, José, et al.
Published: (2024)

Some variations of the secretary problem
by: Agrawal, Sarthak, et al.
Published: (2026)

Approximately Envy-free and Equitable Allocations of Indivisible Items for Non-monotone Valuations
by: Bilò, Vittorio, et al.
Published: (2025)

Unbalanced Random Matching Markets with Partial Preferences
by: Potukuchi, Aditya, et al.
Published: (2024)

The Popular Dimension of Matchings
by: Connor, Frank, et al.
Published: (2025)

A Unified Model of Congestion Games with Priorities: Two-Sided Markets with Ties, Finite and Non-Affine Delay Functions, and Pure Nash Equilibria
by: Takazawa, Kenjiro
Published: (2024)

Stationary Online Contention Resolution Schemes
by: Aminian, Mohammad Reza, et al.
Published: (2026)

A Simple 1.5-Approximation Algorithm for a Wide Range of Max-SMTI Problems
by: Csáji, Gergely
Published: (2023)

Generalized Nash Equilibrium Problems with Mixed-Integer Variables
by: Harks, Tobias, et al.
Published: (2021)

Primal-Dual Algorithms with Predictions for Online Bounded Allocation and Ad-Auctions Problems
by: Kevi, Eniko, et al.
Published: (2024)

Extending Stable and Popular Matching Algorithms from Bipartite to Arbitrary Instances
by: Csáji, Gergely
Published: (2024)

Combinatorial Bernoulli Factories
by: Niazadeh, Rad, et al.
Published: (2020)

Bi-Criteria Metric Distortion
by: Banihashem, Kiarash, et al.
Published: (2024)

The Secretary Problem with Predictions and a Chosen Order
by: Karisani, Helia, et al.
Published: (2026)

Metric Distortion of Line-up Elections: The Right Person for the Right Job
by: Jerrett, Christopher, et al.
Published: (2024)

SAT Encoding of Partial Ordering Models for Graph Coloring Problems
by: Faber, Daniel, et al.
Published: (2024)

Dynamic Necklace Splitting
by: Advani, Rishi, et al.
Published: (2025)

$σ$-Maximal Ancestral Graphs
by: Yao, Binghua, et al.
Published: (2025)

Additively Competitive Secretaries
by: Mahdian, Mohammad, et al.
Published: (2026)

Tightest Admissible Shortest Path
by: Weiss, Eyal, et al.
Published: (2023)

Computing and Learning on Combinatorial Data
by: Zhang, Simon
Published: (2025)

Query Complexity of Tournament Solutions
by: Maiti, Arnab, et al.
Published: (2016)

A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates
by: Weiss, Eyal, et al.
Published: (2022)

Condorcet Winners and Anscombes Paradox Under Weighted Binary Voting
by: Baharav, Carmel, et al.
Published: (2025)

An $O(\log \log n)$-approximate budget feasible mechanism for subadditive valuations
by: Neogi, Rian, et al.
Published: (2025)

The Distortion of Prior-Independent b-Matching Mechanisms
by: Caragiannis, Ioannis, et al.
Published: (2026)

Beyond the worst case: Distortion in impartial culture electorates
by: Caragiannis, Ioannis, et al.
Published: (2023)

Replication-proof Bandit Mechanism Design with Bayesian Agents
by: Shin, Suho, et al.
Published: (2023)

Couples can be tractable: New algorithms and hardness results for the Hospitals / Residents problem with Couples
by: Csáji, Gergely, et al.
Published: (2023)

Gerrymandering Planar Graphs
by: Dippel, Jack, et al.
Published: (2023)

Efficiency of Proportional Mechanisms in Online Auto-Bidding Advertising
by: Thang, Nguyen Kim
Published: (2026)

Facility Location Games Beyond Single-Peakedness: the Entrance Fee Model
by: Ma, Mengfan, et al.
Published: (2022)

Covering a Few Submodular Constraints and Applications
by: Bajpai, Tanvi, et al.
Published: (2025)

Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division
by: Byrka, Jarosław, et al.
Published: (2025)

From Width-Based Model Checking to Width-Based Automated Theorem Proving
by: Oliveira, Mateus de Oliveira, et al.
Published: (2022)