Essays on evaluation qggregation, strategy-proof social choice, and myopic-farsighted ftable matching/ Madhuparna Karmokar

Thesis (Ph.D.) -Indian Statistical Institute, 2022

Includes references

On update monotone, continuous, and consistent collective evaluation rules -- A characterization of possibility domains under Pareto optimality and group
strategy-proofness -- Necessary and sufficient conditions for pairwisemajority decisions on path-connected domains -- Strategy-proof Random Voting Rules on Weak Domains -- The Structure of (Local) Ordinal Bayesian Incentive Compatible Random Rule -- Myopic-farsighted stability in many-to-one matching

Guided by Prof. Souvik Roy

The thesis comprises of six chapters on evaluation aggregation, social choice and matching. A brief
introduction to each of the six chapters is provided below.
In Chapter 2, we consider collective evaluation problems, where individual grades given to candidates
are combined to obtain a collective grade for each of these candidates. In this paper, we prove the
following two results: (i) a collective evaluation rule is update monotone and continuous if and only if it
is a min-max rule, and (ii) a collective evaluation rule is update monotone and consistent if and only if it is
an extreme min-max rule.
Chapters 3,4 and 5 deals with strategic social choice problems where a social planner needs to decide
an outcome for a society from a finite set of feasible outcomes based on the preferences of the agents in
the society. Agents preferences are their private information and agents are strategic meaning that they
manipulate the outcome by misreporting their preferences whenever that is beneficial for them. The
objective of the social planner is to design a rule that no agent can manipulate.
In Chapter 3, we consider domains that satisfy pervasiveness and top-connectedness, and we provide a
necessary and sufficient condition for the existence of non-dictatorial, Pareto optimal, and group strategy-proof choice rules on those domains.
In Chapter 4, we consider choice functions that are unanimous, anonymous, symmetric, and group strategy-proof and consider domains that are single-peaked on some tree. We prove the following three
results in this setting. First, there exists a unanimous, anonymous, symmetric, and group strategy-proof
choice function on a path-connected domain if and only if the domain is single-peaked on a tree and the
number of agents is odd. Second, a choice function is unanimous, anonymous, symmetric, and group
strategy-proof on a single-peaked domain on a tree if and only if it is the pairwise majority rule (also
known as the tree-median rule) and the number of agents is odd. Third, there exists a unanimous,
anonymous, symmetric, and strategy-proof choice function on a strongly path-connected domain if and
only if the domain is single-peaked on a tree and the number of agents is odd. As a corollary of these
results, we obtain that there exists no unanimous, anonymous, symmetric, and group strategy-proof
choice function on a path-connected domain if the number of agents is even.
In Chapter 5, we consider weak domains, that is, set of preferences that may admit indifference. We
show that every unanimous and strategy-proof random social choice function on any weak domain
containing all strict preferences is weak random dictatorial. On weak single-peaked domains, we show
that a random social choice function is Pareto optimal and strategy-proof if and only if it is an extreme
probabilistic fixed ballot rule. Next, we consider single-plateaued domains and provide the structure of
unanimous and strategy-proof random social choice functions on these domains.
Chapter 6 considers the problem of designing strategy-proof social choice rules in an incomplete
information framework. More formally, agents have beliefs about the preferences of the other agents and
they tend to manipulate whenever that improves the expected outcome according to their belief. We
explore the structure of locally ordinal Bayesian incentive compatible (LOBIC) random Bayesian rules
(RBRs). We show that under lower contour monotonicity, for almost all prior profiles (with full Lebesgue
measure), a LOBIC RBR is locally dominant strategy incentive compatible (LDSIC). We further show
that for almost all prior profiles, a unanimous and LOBIC RBR on the unrestricted domain is random
dictatorial, and thereby extend the result in [40] for Bayesian rules. Next, we provide a sufficient condition
on a domain so that for almost all prior profiles, unanimous RBRs on it are tops-only. Finally, we provide
a wide range of applications of our results on single-peaked (on arbitrary graphs), hybrid, multiple
single-peaked, single-dipped, single-crossing, multi-dimensional separable domains, and domains under
partitioning. Since OBIC implies LOBIC by definition, all our results hold for OBIC RBRs.
Chapter 7 considers the many-to-one two-sided matching problem. Agents are assumed to be heterogeneous with respect to their ability to foresee the consequences of a block, and thereby categorized as myopic and farsighted. We study the structure of stable matchings and stable sets in this setting