Computational aspects of fair social choice with incomplete information

Social choice theory is the theoretical model used to analyse how groups of individuals, each with their own personal preferences, can make collective decisions that are beneficial for the group as a whole. Many real-world scenarios, such as elections, can be modelled and analysed using social choice theory. Typically, we wish for the final outcome to treat individuals' preferences in a fair way, and so we wish for the mechanisms used to make these decisions to satisfy certain fairness properties. We can define these ideas of fairness exactly and prove that mechanisms achieve these properties. We can also analyse these mechanisms from a computational perspective; by considering voter preferences as an input and the mechanism result as an output, we can frame these mechanisms as algorithms. From there, we can consider the complexity of these algorithms, and the complexity of guaranteeing different fairness properties. The computational aspects of social choice theory have been well studied. However, the standard social choice definitions typically assume that the algorithm, and all voters, have complete information about all preferences of all voters. This is a simplifying assumption that may fail to hold true in some real-world scenarios. For example, consider a local government selecting which projects should be completed. A full referendum to elicit every voter's preferences may not be possible, but we still wish to approximately fairly represent the voters. The government could instead sample a subset of voters and run a decision mechanism just on the information from the sample. Given that the sample size is large enough to be representative, we may be able to expect the outcome to be approximately fair with respect to the whole population with high probability.

This presents us with several interesting problems:

What information should we sample from voters, how should we sample that information, and how much information should we sample?
Which decision...