Skip navigation
Please use this identifier to cite or link to this item:
Title: Connecting Voting and Market Models: A Computational Social Choice Perspective
Authors: Noarov, Georgy
Advisors: Braverman, Mark
Department: Mathematics
Class Year: 2020
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.
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Mathematics, 1934-2020

Files in This Item:
File Description SizeFormat 
NOAROV-GEORGY-THESIS.pdf452.94 kBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.