ACM India IndiCS Winter School and Seminar

This tutorial explores an emerging and largely understudied frontier in social choice theory: probabilistic voting rules and their role in selecting fair and efficient compromises under heterogeneous preferences. While randomization—through lotteries, budget-sharing, or time-sharing—is a natural response to preference diversity in small committees, the design of principled mechanisms that achieve compelling normative guarantees remains poorly understood. Existing theory provides only limited guidance, with notable progress restricted to dichotomous preference domains, where fair mixing mechanisms have been formally characterized.

The tutorial will examine recent advances demonstrating that iterative combinations of voting by veto and random dictatorship yield a canonical spectrum of optimal worst-case guarantees for individuals, revealing a rich structure of attainable fairness outcomes. These results raise fundamental questions about strategic behavior, efficiency performance, and robustness, particularly under complete information. Beyond individual guarantees, the tutorial will investigate the feasibility and interpretation of collective (coalitional) guarantees, highlighting unresolved tensions between fairness, efficiency, and incentive compatibility.

By synthesizing these developments, the tutorial aims to bridge normative theory with mechanism design, offering a coherent framework for understanding compromise selection through probabilistic voting. It will also outline open research directions where simple, practically deployable mechanisms can be designed and rigorously evaluated, positioning probabilistic voting as a promising paradigm for equitable collective decision-making.

This tutorial will provide a brief overview of old and new results on stable matchings, emphasizing connections to linear programs and lattices. The focus will be on highlighting structural results and their implications for algorithms for various optimization problems on the class of stable matchings.

This tutorial revisits the classical problem of regulating a monopolist through optimal mechanism design, a framework that also underpins the design of procurement contracts. Departing from standard models where uncertainty arises solely from the private type of the agent, this setting incorporates an additional and economically significant source of uncertainty: the demand faced by the buyer or regulator, driven by Nature. The canonical Bayesian solution, formulated by Baron and Myerson (1982), assumes a known demand function and a common prior over the supplier’s type, yielding an elegant optimal mechanism. However, such assumptions are increasingly viewed as restrictive in environments marked by ambiguity, incomplete information, and institutional uncertainty.

Recent advances challenge the Bayesian paradigm by seeking prior-free and robustness-oriented solutions. Emerging approaches include worst-case regret minimization, undomination criteria, competitive ratio benchmarks, and minimax formulations, each offering a distinct lens on performance guarantees when priors or demand functions are unknown or misspecified. These developments reflect a broader shift toward mechanism design under ambiguity, with relevance to settings involving ambiguity-averse agents and incomplete institutional knowledge.

The tutorial will provide a unified treatment of this evolving literature. It will first present the classical Bayesian solution and its structural insights, followed by a systematic exploration of modern prior-free approaches and robustness criteria. Special attention will be devoted to open problems at the interface of economic theory and theoretical computer science, including approximate optimal mechanisms, ambiguity-robust designs, and comparative performance analysis under alternative notions of robustness. The tutorial aims to equip participants with both conceptual clarity and technical insight into one of the most actively developing frontiers in contemporary mechanism design.

This talk surveys two strands of research in voting theory. First, we revisit the Hotelling–Downs model, where voters occupy fixed positions in a political spectrum, and candidates choose positions on the spectrum to maximize their vote share. In its basic form, the model often lacks equilibrium, as candidates can always gain by repositioning. We present recent results on approximating and computing equilibria, as well as work on variants of the model.

Second, we examine mechanisms for maximizing social welfare when voters provide only ordinal rankings over candidates, rather than their (possibly unknown) cardinal utility. Welfare is measured via distortion, the worst-case ratio between the achieved and optimal cardinal welfare. We summarize tight bounds on the achievable distortion, and discuss how randomization or limited cardinal information can get past these lower bounds.

We introduce the classical setting of matchings with two-sided preferences and the GS algorithm.

We describe a simple and powerful idea of Kiraly (2011) of a multilevel GS algorithm. We illustrate the use of 2-level GS algorithm for the case when preferences are allowed to contain ties. This gives a constant factor approximation for the maximum sized weakly stable matching (Kiraly 2011).

Next we illustrate the use of 2-level GS algorithm for the case of strict lists. The algorithm outputs a maximum-sized popular matching. (Kavitha 2014). All the material up to this point is self-contained, with complete proofs.

The applications of the multi-level GS in other settings will be mentioned/discussed as time permits.