Cover Image

Distortion of Metric Voting with Bounded Randomness

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cai, Ziyi, Gao, D. D., Ramakrishnan, Prasanna, Wang, Kangning
Format:	Preprint
Published:	2026
Subjects:	Computer Science and Game Theory 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

Breaking the Metric Voting Distortion Barrier
by: Charikar, Moses, et al.
Published: (2023)

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)

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

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

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

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)

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

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

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)

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

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

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)

Nearly Tight Bounds on Testing of Metric Properties
by: Bao, Yiqiao, et al.
Published: (2024)

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

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

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

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)

Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
by: Grohe, Martin, et al.
Published: (2023)

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

Tight Bounds for Sparsifying Random CSPs
by: Brakensiek, Joshua, et al.
Published: (2025)

An $Ω(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces
by: Arndt, Stephen, et al.
Published: (2026)

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

Efficient Online Random Sampling via Randomness Recycling
by: Draper, Thomas L., et al.
Published: (2025)

Aligning Multiple Inhomogeneous Random Graphs: Fundamental Limits of Exact Recovery
by: Ameen, Taha, et al.
Published: (2024)

Hop-Constrained Metric Embeddings and their Applications
by: Filtser, Arnold
Published: (2021)

Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric
by: Bhattacharya, Sudatta, et al.
Published: (2025)

Cutwidth Bounds via Vertex Partitions
by: Amarilli, Antoine, et al.
Published: (2025)

Temporal Graph Realization With Bounded Stretch
by: Mertzios, George B., et al.
Published: (2025)

Optimal Padded Decomposition For Bounded Treewidth Graphs
by: Filtser, Arnold, et al.
Published: (2024)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
by: Fei, Yumou, et al.
Published: (2025)

Weighted Envy Freeness With Bounded Subsidies
by: Elmalem, Noga Klein, et al.
Published: (2024)

Bounding $\varepsilon$-scatter dimension via metric sparsity
by: Bourneuf, Romain, et al.
Published: (2024)