Connecting Voting and Market Models: A Computational Social Choice Perspective

Abstract

Social choice mechanisms are mathematical algorithms which aim to aggregate preferences of multiple rational agents over a set of alternatives into an solution that maximally satisfies their collective preferences. Many socially desirable objectives that such mechanisms try to achieve are in conflict with each other, however. In particular, one notoriously hard goal is for a socially good mechanism to be computationally fast. So far, socially efficient, truthful, and tractable mechanisms in social choice are only known for very few social choice settings, including two market models, known as the Arrow-Debreu and the Fisher models. For the setting of voting, however, tractable mechanisms satisfying truthfulness and social efficiency are unknown.

The objective of this manuscript is to set up a search for an efficient, truthful and fast voting mechanism, based on a combination of ideas from two clusters in the computational social choice literature: first, convex optimization techniques for markets, and second, pricing schemes known from both the markets and the voting literature. We provide an exposition of the relevant computational results from both literature clusters.

Finally, we provide our own model, which resembles a linear Fisher market, but with polynomial pricing of goods. This model also has a convex optimization formulation, and thus combines the two ideas mentioned above.