Voting and historical games

Abstract/Contents

Abstract

For a group of agents to make a good decision, we must be able to choose a good decision making method. In this thesis, we first study the problem of choosing decision making methods by taking social choice functions and providing quantitative measures on how well they might perform against a population distribution. Then we study a common, possibly the most common, decision making method online: voting to rate products. In this domain, we provide a new class of models and prove that certain convergence results hold. Finally we prove a connection between this new model and traditional voting methods. In the first half of the thesis, we develop a means of comparing various social choice functions with regards to a desired axiom by quantifying how often the axiom is violated. To this end, we offer a new framework for measuring the quality of social choice functions that builds from and provides a unifying framework for previous research. This framework takes the form of what we call a "violation graph." Graph properties have natural interpretations as metrics for comparing social choice functions. Using the violation graph we present new metrics, such as the minimal domain restriction, for assessing social choice functions and provide exact and probabilistic results for voting rules including plurality, Borda, and Copeland. Motivated by the empirical results, we also prove asymptotic results for scoring voting rules. These results suggest that voting rules based on pairwise comparison (ex: Copeland) are better than scoring rules (ex: Borda count). They also suggest that although we can never fulfill our desired set of axioms, the frequency of violation is so small that with even a modest number of voters we can expect to never violate our axioms. In the second half of the thesis, we define a new class of games called historical influence games (HIGs). HIGs are infinite games in which agents take turns round-robin style iv choosing a value for a single-dimensional variable. The payoff at each stage to each agent is a monotonically decreasing function of the distance between two quantities: a weighted average of past values chosen by all agents, and some fixed ideal value personal to that agent. The overall payoff to the agent is the limit average of the stage payoffs. We show that myopic strategies form a subgame perfect Nash equilibrium in HIGs. Then we introduce certain smoothness constraints on how the impact of a given action changes over time, constraints which define the class of valid HIGs. We prove that for valid HIGs, under myopic play the limit average value converges to what we call the central value, which is the median of the agents' ideal values jointly with certain societal focal points. As a side effect, we show a polarization theorem: after a finite period, almost all agents settle on one of the extreme values. Finally, we show a tight connection between valid HIGs and the class of Moulin strategy-proof voting rules in single-peaked domains.

Description

Type of resource	text
Form	electronic; electronic resource; remote
Extent	1 online resource.
Copyright date	2011
Publication date	2010, c2011; 2010
Issuance	monographic
Language	English

Creators/Contributors

Associated with	Munie, Michael Andrew
Associated with	Stanford University, Computer Science Department
Primary advisor	Shoham, Yoav
Thesis advisor	Shoham, Yoav
Thesis advisor	Leskovec, Jurij
Thesis advisor	Segal, Ilya
Advisor	Leskovec, Jurij
Advisor	Segal, Ilya

Subjects

Genre	Theses

Bibliographic information

Statement of responsibility	Michael Andrew Munie.
Note	Submitted to the Department of Computer Science.
Thesis	Thesis (Ph.D.)--Stanford University, 2011.
Location	electronic resource

Access conditions

Copyright

© 2011 by Michael Andrew Munie

License

This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).

Also listed in

View in SearchWorks

Loading usage metrics...