Game Theory and Voting Systems

Latest papers

• When Is Deletion Ordering Tractable? From Update Dynamics to Permutation Structure

  Xinyu Wang, Ziyu Zhao, Yixuan He, Xiaowen Chang Alex Smola · 2 October 2026

  Given a fixed set of pending deletion requests, retraining from scratch after each request is prohibitive, so a prescribed request-wise policy processes them sequentially. The resulting terminal model can depend on their order. Rather than prescribing an ordering rule, we study the permutation objec…

• Outer Diversity of Condorcet Domains

  Piotr Faliszewski, Jan Jabrocki, Mateusz S{\l}uszniak, Krzysztof Sornat, Stanis{\l}aw Szufa, Tomasz W\k{a}s · 2 October 2026

  A Condorcet domain is a set of rankings over a given candidate set, such that every election that consists only of (an odd number of) votes from the domain has a transitive majority relation. We study outer diversity of Condorcet domains, i.e., a measure that quantifies expected swap distance from a…

• Query-efficient winner prediction in district-based elections

  Koustav De, Debajyoti Kar, Swagato Sanyal · 2 October 2026

  In a district-based election, N voters are partitioned into k districts, and each voter votes for one of m candidates. Each district elects a winner using the plurality rule (i.e. the candidate getting the largest number of votes is declared the winner, breaking ties as per some fixed rule), and the…

• From Discovery to Decision: Finite-Budget Recoverability in LLM Voting

  Shaoang Li, Jian Li · 2 October 2026

  Voting over multiple LLM responses is a common primitive in test-time scaling and ensemble inference. Collecting more responses can expand the candidate pool and increase the chance that a correct answer is discovered. Under a fixed call budget, a discovered answer still needs to accumulate enough s…

• Rank Confidence Sequences:Anytime-valid Leaderboards

  Hamed Khosravi, Xiaoming Huo · 29 September 2026

  Leaderboards rank models by their average scores on benchmark items, and they are consulted repeatedly while the evaluation is still running. Existing confidence intervals for a model's rank control their error rate only if they are computed once, after a number of items chosen in advance. If they a…

• When Pair Count Is Not the Sample Size: What All-Pairs Agent Comparisons Estimate

  Wei-Jung Huang · 29 September 2026

  When an agent benchmark compares every pair of leaderboard entries, the number of comparisons can look much larger than the independent evidence behind them: A versus B and A versus C both reuse A. Whether this reuse affects inference depends on what the analysis is meant to describe. If the board a…

• Proportional Representation in Temporal Voting with Ranked Preferences

  Noam Hazon, Leora Schmerler, Nicholas Teh · 28 September 2026

  We study proportional representation in temporal voting, where one candidate is selected in each round. While prior work has focused on approval ballots, we consider ranked preferences, which may change over time. A natural approach treats each voter's top candidates as approved, but the right cutof…

• Multi-Dimensional Matching

  Irene Aldridge · 25 September 2026

  We study a matching mechanism where agents and objects are described by features rather than complete rankings. A single spectral projection reduces the problem to a one-dimensional sort, computable in O(N log N) time. We prove that on descaled features and preferences, our algorithm obtains the exa…

• Decoupled Learning and Selection in Slate Recommendation for Privacy and Stability Under Noisy Scores

  Sam Urmian, Qinyi Liu, Mohammad Khalil · 25 September 2026

  We formalize slate recommendation as a randomized score learner followed by deterministic selection. First, an appropriately scoped differential-privacy guarantee passes through selection and its audit trace by post-processing. End-to-end privacy holds only when selector inputs are public or indepen…

• Fair Feed Ranking for Participatory Budgeting

  Carina I. Hausladen · 25 September 2026

  In large-scale participatory budgeting, citizens cannot inspect the full proposal pool, so the order in which proposals are shown becomes a form of agenda-setting power. We argue that fair exposure should therefore be treated as a democratic-design goal. We study Consul Democracy, a widely deployed …

• Do Electromagnetic Side-Channel Attacks Threaten Electronic Polling Stations? Scenarios and Recommendations

  Lucas Brito, Leonardo Teodoro, Pedro Tomaz, Alyson Isaluski, Leandro Hyeda, Antonio Oliveira-Jr, Saulo Queiroz · 24 September 2026

  This paper investigates the threat to ballot secrecy in the Brazilian electronic voting machine (UEB) posed by electromagnetic side-channel attacks, also known as TEMPEST attacks. In these attacks, screen content can be reconstructed remotely by intercepting electromagnetic emanations associated w…

• Understanding Human Perception of Representation in Citizens' Assemblies: An Empirical Study

  Yusuf Hakan Kalayci, Vasilis Varsamis, Nick Gill, Evi Micha · 24 September 2026

  Citizens' assemblies are deliberative bodies intended to form a microcosm of the population. Organizers rely on quota-based stratification and must decide which attributes define resemblance to the public. Yet meeting every quota can still leave a dimension citizens value unrepresented. We study thi…

• Error Bounds for Statistical Estimators in BTL Model with Parametric Multivariate Utility Functions

  Yicheng Li, Huifu Xu · 23 September 2026

  We study preference elicitation under the Bradley-Terry-Luce (BTL) model where the true partworth vector is unknown and has to be estimated as a parameter with elicited preference information. The set of selected pairwise queries is non-uniform, deterministic, and arbitrary over a collection of alte…

• Unanimity Without Persuasion: A Single Round of Debate Erases the Disagreement That Verification Needs

  Yang Shu · 23 September 2026

  A debate panel can become unanimous without becoming more correct. This is dangerous for downstream safeguards: a substituted verification ballot can change only narrow-margin votes, while richer arbiters lose disagreement as a natural targeting signal. We show that one debate round can erase that r…

• When Verifiers Vote Backwards under Verdict Substitution: Signed Pivotal Value in Correlated Self-Consistency

  Yang Shu · 23 September 2026

  Replacing one ballot can change a majority decision only on queries decided by a single vote; this structural fact requires no independence assumption. We study the sign of that change using a labeled, verdict-style intervention: one correctness signal replaces one correctness-indicator ballot in $k…

• Independence-System Realisations in Single-Source Unsplittable Flow

  Koyar Afrasyab · 17 September 2026

  Additive-congestion constraints in single-source unsplittable flow can enforce stable-set structure. This note isolates and generalises that mechanism. We introduce a path-closed notion of realising an independence system by the zero-cost choices of primary terminals in a directed acyclic flow insta…

• On the disintegration of the stochastic majority vote: From PAC-Bayesian bounds to a self-bounding algorithm

  Julien Bastian (LabHC), Benjamin Leblanc (LabHC, UJM, MALICE), Pascal Germain (LabHC, UJM, MALICE), Amaury Habrard (LabHC, UJM, MALICE), Guillaume Metzler (ERIC), Emilie Morvant (LabHC), Paul Viallard (MALT) · 16 September 2026

  Weighted majority votes are central to many successful ensemble methods. PAC-Bayesian theory provides tight generalization guarantees for such models by analyzing the expected risk of stochastic classifiers, while analyzing the risk of deterministic majority votes relies on surrogate bounds. To avoi…

• Equity Promotion in Online Resource Allocation

  Pan Xu, Yifan Xu · 10 September 2026

  We consider online resource allocation under a typical non-profit setting, where limited or even scarce resources are administered by a not-for-profit organization like a government. We focus on the internal-equity by assuming that arriving requesters are homogeneous in terms of their external facto…

• Endorsement Without New Evidence: How Sequential Voting Inflates Mandates in Online Community Governance

  Zihan Chen, Lei Nico Zheng, Di Zhu · 10 September 2026

  Online communities often treat large support margins in public elections as strong mandates. We argue that such margins can overstate the independent scrutiny behind a decision. Using 198,275 free-text rationales from Wikipedia admin elections, we introduce vote-text divergence, a measure that flags…

• Toward Collective-Centric Evaluation of Preference Inference for Participatory Democracy

  Pierre-Antoine Lequeu, Salim Hafid, Paul Lerner, Nazanin Shafiabadi, Laur\`ene Cave, David Mas, Jean-Philippe Cointet, Benjamin Piwowarski, Fran\c{c}ois Yvon · 4 September 2026

  To scale up collective decision-making, participatory democracy platforms such as Polis and Remesh enable online deliberation among thousands of participants. However, at this scale, participants cannot review every opinion submitted by others, producing highly sparse voting data that misrepresent p…

• Fair Stable Matching: A Nash Social Welfare Approach

  Parth Desai, Rasheed M, Ganesh Ghalme, Sujit Gujar · 3 September 2026

  While traditional stable matching algorithms, such as the Gale-Shapley algorithm, prioritize stability, they may fall short of achieving equitable outcomes among participants. We study the role of \emph{Nash social welfare} (NSW) as a fairness objective in the classic \emph{stable marriage problem}.…

• Advantage Weighted Matching: Aligning RL with Pretraining in Diffusion Models

  Shuchen Xue, Chongjian Ge, Shilong Zhang, Yichen Li, Zhi-Ming Ma · 2 September 2026

  Reinforcement Learning (RL) has emerged as a central paradigm for advancing Large Language Models (LLMs), where both pre-training and RL post-training stages are grounded in the same log-likelihood formulation. In contrast, recent RL approaches for diffusion models, most notably Denoising Diffusion …

• Simultaneous Envy and Equitability Guarantees

  Hadi Hosseini, Shraddha Pathak, Lirong Xia, Chengkai Zhang · 28 August 2026

  Recent work in fair division has focused on either simultaneously satisfying closely related fairness notions or achieving a single notion across the ex-ante and ex-post worlds. We study the compatibility of two fundamentally different fairness notions: envy-freeness and equitability. For indivisibl…

• Multilevel Fair Allocation under Additive Preferences

  Maxime Lucet, Nawal Benabbou, Aur\'elie Beynier, Nicolas Maudet · 26 August 2026

  We study multilevel fair resource allocation with tree-structured hierarchical relations among agents. At each level, the problem can be viewed locally as allocating an agent's bundle to its children, the overall allocation being a trace of this process iterated down to the leaves. Assuming that int…

• Algorithmic Impact Reveals the Hidden Social Choice Structure of Alignment

  Zachary Wojtowicz, Michelle Si, Finale Doshi-Velez, Ariel Procaccia · 26 August 2026

  When an AI algorithm makes decisions that affect more than one person, aligning it becomes a problem of social choice: how should people's divergent preferences about system behavior be reconciled and aggregated into a single coherent model? The standard approach to aligning frontier AI models$\unic…