Optimal Choice Functions: A Utilitarian View
Craig Boutilier, Ioannis Caragiannis, Simi Haber, Tyler Lu, Ariel Procaccia and Or Sheffet
We adopt a utilitarian perspective on social choice, assuming that agents have (possibly latent) utility functions over some space of alternatives. For many reasons one might consider mechanisms, or social choice functions, that only have access to the ordinal rankings of alternatives by the individual agents rather than their utility functions. In this context, one possible objective for a social choice function is the maximization of (expected) social welfare relative to the information contained in these rankings. We study such optimal social choice functions under three different models, and underscore the important role played by scoring functions. In our worst-case model, no assumptions are made about the underlying distribution and we analyze the worst-case distortion—or degree to which the selected alternative does not maximize social welfare—of optimal social choice functions. In our average-case model, we derive optimal functions under neutral (or impartial culture) distributional models. Finally, a very general learning-theoretic model allows
for the computation of optimal social choice functions (i.e., that maximize expected social welfare) under arbitrary, sampleable distributions. In the latter case, we provide both algorithms and sample complexity results for the class of scoring functions, and further validate the approach empirically.
In a broader context, we view social functions (or voting aggregation schemes) as a proxy for social welfare. If we knew the true valuations of all agents to all alternatives we would pick the one alternative that maximizes the social welfare, but since we don't - we're forced to used preference ranking as our input. In spirit, this resembles the work of Balcan, Blum and Gupta, that views k-Median as a proxy for clutsering, where ideally we would cluster points according to their true label, but since we do not have this information we're forced to cluster the points according the given metric.
I (personally) find this while body of work very interesting. Often algorithms are applied under assumption that the solution retrieved has some real-life meaning, optimizes a true objective for which I have no access to, or has some structural properties. I am convinced that there are other works (aside from clustering and voting) that fall into this framework.