COMSOC Video Seminar tomorrow: Souvik Roy and Prasanna Ramakrishnan
9 views
Skip to first unread message
Dominik Peters
Jan 6, 2026, 7:57:41 AM (7 days ago) Jan 6
to Online Social Choice and Welfare Forum
Dear all,
The COMSOC Video Seminar (https://comsocseminar.org/) is meeting tomorrow Wednesday, 2025-01-07, at 06:00 Stanford / 09:00 New York / 15:00 Paris / 19:30 India time to hear from Souvik Roy (ISI Kolkata) about strategyproof probabilistic assignment rules and from Prasanna Ramakrishnan (Stanford) about the famous paper "Six Candidates Suffice to Win a Voter Majority". You can join the zoom meeting via the link https://meeting.comsocseminar.org. Hope to see many of you there! Abstracts below:
Souvik Roy (ISI Kolkata)
A Characterization of Strategy-Proof Probabilistic Assignment Rules
We study the classical probabilistic assignment problem, where finitely many indivisible objects are to be probabilistically or proportionally assigned among an equal number of agents. Each agent has an initial deterministic endowment and a strict preference over the objects. While the deterministic version of this problem is well understood, most notably through the characterization of the Top Trading Cycles (TTC) rule by Ma (1994), much less is known in the probabilistic setting. Motivated by practical considerations, we introduce a weakened incentive requirement, namely SD-top-strategy-proofness, which precludes only those manipulations that increase the probability of an agent’s top-ranked object.
Our first main result shows that, on any free pair at the top (FPT) domain (Sen, 2011), the TTC rule is the unique probabilistic assignment rule satisfying SD–Pareto efficiency, SD–individual rationality, and SD–top-strategy-proofness. We further show that this characterization remains valid when Pareto efficiency is replaced by the weaker notion of SD–pair efficiency, provided the domain satisfies the slightly stronger free triple at the top (FTT) condition (Sen, 2011). Finally, we extend these results to the ex post notions of efficiency and individual rationality. Together, our findings generalize the classical deterministic results of Ma (1994) and Ekici (2024) along three dimensions: extending them from deterministic to probabilistic settings, from full strategy-proofness to top-strategy-proofness, and from the unrestricted domain to the more general FPT and FTT domains.
--
Prasanna Ramakrishnan (Stanford)
How to Appease a Voter Majority
In 1785, Condorcet established a frustrating property of elections and majority rule: it is possible that, no matter which candidate you pick as the winner, a majority of voters will prefer someone else. You might have the brilliant idea of picking a small set of winners instead of just one, but how do you avoid the nightmare scenario where a majority of the voters prefer some other candidate over all the ones you picked? How many candidates suffice to appease a majority of the voters? In this talk, we will explore this question. Along the way, we will roll some dice — both because the analysis involves randomness and because of a connection to the curious phenomenon of intransitive dice, that has delighted recreational and professional mathematicians alike ever since Martin Gardner popularized it in 1970.
Based on joint work with Moses Charikar, Alexandra Lassota, Adrian Vetta, and Kangning Wang
A Characterization of Strategy-Proof Probabilistic Assignment Rules
We study the classical probabilistic assignment problem, where finitely many indivisible objects are to be probabilistically or proportionally assigned among an equal number of agents. Each agent has an initial deterministic endowment and a strict preference over the objects. While the deterministic version of this problem is well understood, most notably through the characterization of the Top Trading Cycles (TTC) rule by Ma (1994), much less is known in the probabilistic setting. Motivated by practical considerations, we introduce a weakened incentive requirement, namely SD-top-strategy-proofness, which precludes only those manipulations that increase the probability of an agent’s top-ranked object.
Our first main result shows that, on any free pair at the top (FPT) domain (Sen, 2011), the TTC rule is the unique probabilistic assignment rule satisfying SD–Pareto efficiency, SD–individual rationality, and SD–top-strategy-proofness. We further show that this characterization remains valid when Pareto efficiency is replaced by the weaker notion of SD–pair efficiency, provided the domain satisfies the slightly stronger free triple at the top (FTT) condition (Sen, 2011). Finally, we extend these results to the ex post notions of efficiency and individual rationality. Together, our findings generalize the classical deterministic results of Ma (1994) and Ekici (2024) along three dimensions: extending them from deterministic to probabilistic settings, from full strategy-proofness to top-strategy-proofness, and from the unrestricted domain to the more general FPT and FTT domains.
--
Prasanna Ramakrishnan (Stanford)
How to Appease a Voter Majority
In 1785, Condorcet established a frustrating property of elections and majority rule: it is possible that, no matter which candidate you pick as the winner, a majority of voters will prefer someone else. You might have the brilliant idea of picking a small set of winners instead of just one, but how do you avoid the nightmare scenario where a majority of the voters prefer some other candidate over all the ones you picked? How many candidates suffice to appease a majority of the voters? In this talk, we will explore this question. Along the way, we will roll some dice — both because the analysis involves randomness and because of a connection to the curious phenomenon of intransitive dice, that has delighted recreational and professional mathematicians alike ever since Martin Gardner popularized it in 1970.
Based on joint work with Moses Charikar, Alexandra Lassota, Adrian Vetta, and Kangning Wang
--Best,
Dominik Peters
on behalf of the organizing committee: Florian Brandl, Clemens Puppe, Nisarg Shah, Annaëlle Wilczynski
Reply all
Reply to author
Forward
0 new messages