Sahasrajit Sarmasarkar

Mohak Goyal, Sahasrajit Sarmasarkar

Metric distortion in social choice is a framework for evaluating how well voting rules minimize social cost when both voters and candidates exist in a shared metric space, with a voter's cost defined by their distance to a candidate. Voters submit rankings, and the rule aggregates these rankings to determine a winner. We extend this framework to incorporate probabilistic voting, recognizing that real-world voters exhibit randomness in how they vote. Our extension includes various probability functions, notably the widely studied Plackett-Luce (PL) model. We show that the distortion results under probabilistic voting better correspond with conventional intuitions regarding popular voting rules such as \textsc{Plurality}, \textsc{Copeland}, \textsc{Random Dictator} and \textsc{Borda} than those under deterministic voting. For example, in the PL model with candidate strength inversely proportional to the square of their metric distance from a voter, we show that \textsc{Copeland}'s distortion is at most 2, whereas that of \textsc{RandomDictator} is $Ω(\sqrt{m})$ in large elections (i.e., number of voters $n \rightarrow \infty$), where $m$ is the number of candidates. This contrasts sharply with the classical model, where \textsc{RandomDictator} beats \textsc{Copeland} with a distortion of 3 versus 5. In the PL model where the candidate strength is inversely proportional to the distance raised to power $θ$, the distortion under \textsc{Borda} is $Θ(m^{1-2/θ})$ when $θ>2$ and $Θ(1)$ otherwise. This generalizes the classical deterministic voting model where the distortion of \textsc{Borda} is $2m-1$. The proof uses a novel variant of asymptotic duality where we choose the Lagrange multiplier via asymptotically maximizing the derivative of the objective function. Overall, our work opens a new frontier for analyzing voting rules.

Sahasrajit Sarmasarkar, Kota Srinivas Reddy, Nikhil Karamchandani

We consider the problem of identifying the subset $\mathcal{S}^γ_{\mathcal{P}}$ of elements in the support of an underlying distribution $\mathcal{P}$ whose probability value is larger than a given threshold $γ$, by actively querying an oracle to gain information about a sequence $X_1, X_2, \ldots$ of $i.i.d.$ samples drawn from $\mathcal{P}$. We consider two query models: $(a)$ each query is an index $i$ and the oracle return the value $X_i$ and $(b)$ each query is a pair $(i,j)$ and the oracle gives a binary answer confirming if $X_i = X_j$ or not. For each of these query models, we design sequential estimation algorithms which at each round, either decide what query to send to the oracle depending on the entire history of responses or decide to stop and output an estimate of $\mathcal{S}^γ_{\mathcal{P}}$, which is required to be correct with some pre-specified large probability. We provide upper bounds on the query complexity of the algorithms for any distribution $\mathcal{P}$ and also derive lower bounds on the optimal query complexity under the two query models. We also consider noisy versions of the two query models and propose robust estimators which can effectively counter the noise in the oracle responses.