Don’t Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond

DOI10.1137/23m1545677arXiv2203.01872MaRDI QIDQ6195958

Georgios Amanatidis, Aris Filos-Ratsikas, Alexandros A. Voudouris, Georgios Birmpas

Publication date: 14 March 2024

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2203.01872

zbMATH Keywords

matchingdistortionsocial choicequeriesgraph problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Voting theory (91B12) Approximation algorithms (68W25) Social choice (91B14) Matching models (91B68)

Cites Work

• Unnamed Item
• Unnamed Item
• Approximating optimal social choice under metric preferences
• Awareness of voter passion greatly improves the distortion of metric social choice
• Optimal social choice functions: a utilitarian view
• Ordinal approximation for social choice, matching, and facility location problems given candidate positions
• Peeking behind the ordinal curtain: improving distortion via cardinal queries
• Truthful Approximations to Range Voting
• Social Welfare in One-Sided Matchings: Random Priority and Beyond
• Subset Selection Via Implicit Utilitarian Voting
• Truthful Facility Assignment with Resource Augmentation: An Exact Analysis of Serial Dictatorship
• Randomized Social Choice Functions Under Metric Preferences
• A Few Queries Go a Long Way: Information-Distortion Tradeoffs in Matching
• Approximately stable committee selection
• Tradeoffs between information and ordinal approximation for bipartite matching
• College Admissions and the Stability of Marriage
• The distortion of distributed metric social choice
• The distortion of distributed voting

This page was built for publication: Don’t Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond