Voting and historical games
- 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.
|Type of resource
|electronic; electronic resource; remote
|1 online resource.
|2010, c2011; 2010
|Munie, Michael Andrew
|Stanford University, Computer Science Department
|Statement of responsibility
|Michael Andrew Munie.
|Submitted to the Department of Computer Science.
|Thesis (Ph.D.)--Stanford University, 2011.
- © 2011 by Michael Andrew Munie
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...