3 papers
cs.GT2026
Stable Voting Rules on the Edge of Optimal Metric Distortion
Ziyi Cai, Moses Charikar, Jabari Hastings +3
We prove the existence of a randomized voting rule with metric distortion at most , within of the lower bound of . Our rule comes from a generalization of…
cs.DS2026
Dense Language Generation Made Simple: Deterministic, Randomized, and Multi-Order Algorithms
Ziyi Cai, Shuangping Li, Yiheng Shen +2
Language generation in the limit is a theoretical framework for studying how a generator can learn to produce new valid strings from a stream of positive examples. In this model, a…
cs.GT2026
Distortion of Metric Voting with Bounded Randomness
Ziyi Cai, D. D. Gao, Prasanna Ramakrishnan +1
We study the design of voting rules in the metric distortion framework. It is known that any deterministic rule suffers distortion of at least , and that randomized rules can ac…