Computational social choice is a relatively new discipline that explores issues at the intersection of social choice theory and computer science. Designing a protocol for collective decision-making is made difficult by the possibility of manipulation through insincere voting. In approval voting systems, voters decide whether to approve or disapprove available alternatives; however, the specific nature of rational approval strategies has not been adequately studied. This research explores aspects of strategy under three different approval systems, from chiefly a computational viewpoint.
While traditional voting systems elicit only the outcome of a voter’s strategic thinking, a Declared-Strategy Voting (DSV) system accepts such strategies directly and applies them according to the voter’s preferences over the available alternatives. Ideally, when rational strategies are employed on behalf of the voters, voters are discouraged from expressing insincere preferences. Approval voting is a natural fit for use with DSV, but, unlike for the common plurality voting system, there is no extant theory regarding the most effective approval strategies in a DSV context. We propose such a theory.
Approval-rating polls already serve an important role in assaying the views of an electorate on some subject of interest. Sites such as Rotten Tomatoes and Metacritic.com collect and display the results of approval-rating polls for movies and games. Moreover, sites such as Amazon and eBay collect approval ratings to estimate the worthiness of their buyers and sellers. In these polls, a rational voter’s approval or disapproval will sometimes be insincere so as to move the result in a desired direction. A nonmanipulable protocol would allow indication of a voter’s ideal outcome and would never reward an insincere such indication. We present and analyze a large new class of such nonmanipulable protocols motivated by the DSV concept.
The minimax procedure is a multiwinner form of approval voting that aims to maximize the satisfaction with the outcome of the least satisfied voter. Unfortunately, computing the minimax winner set is computationally hard. We propose an approximation algorithm for this problem, a framework for polynomial-time heuristics that perform very well in practice, and a preliminary analysis of strategic voting under minimax.
","abstract_html":"<p>Computational social choice is a relatively new discipline that explores issues at the intersection of social choice theory and computer science. Designing a protocol for collective decision-making is made difficult by the possibility of manipulation through insincere voting. In approval voting systems, voters decide whether to approve or disapprove available alternatives; however, the specific nature of rational approval strategies has not been adequately studied. This research explores aspects of strategy under three different approval systems, from chiefly a computational viewpoint.</p> <p>While traditional voting systems elicit only the outcome of a voter’s strategic thinking, a Declared-Strategy Voting (DSV) system accepts such strategies directly and applies them according to the voter’s preferences over the available alternatives. Ideally, when rational strategies are employed on behalf of the voters, voters are discouraged from expressing insincere preferences. Approval voting is a natural fit for use with DSV, but, unlike for the common plurality voting system, there is no extant theory regarding the most effective approval strategies in a DSV context. We propose such a theory.</p> <p>Approval-rating polls already serve an important role in assaying the views of an electorate on some subject of interest. Sites such as Rotten Tomatoes and Metacritic.com collect and display the results of approval-rating polls for movies and games. Moreover, sites such as Amazon and eBay collect approval ratings to estimate the worthiness of their buyers and sellers. In these polls, a rational voter’s approval or disapproval will sometimes be insincere so as to move the result in a desired direction. A nonmanipulable protocol would allow indication of a voter’s ideal outcome and would never reward an insincere such indication. We present and analyze a large new class of such nonmanipulable protocols motivated by the DSV concept.</p> <p>The minimax procedure is a multiwinner form of approval voting that aims to maximize the satisfaction with the outcome of the least satisfied voter. Unfortunately, computing the minimax winner set is computationally hard. We propose an approximation algorithm for this problem, a framework for polynomial-time heuristics that perform very well in practice, and a preliminary analysis of strategic voting under minimax.</p>","abstract_has_math":false,"creators":["LeGrand, Robert Hampton, III"],"institution":null,"degree_name":"Doctor of Philosophy (PhD)","degree_level":"Dissertation","degree_discipline":"Computer Science & Engineering","degree_department":null,"school":null,"contributors":["Ron K. Cytron","Steven Brams, Jeremy Buhler, Robert Pless, Itai Sened, Aaron Stump"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2008,"date_issued":"2008-05-01T07:00:00Z","date_published":"2008-05-01T07:00:00Z","updated_at":"2026-07-24T06:13:14Z","subjects":["Computer Engineering","Engineering"],"languages":["English (en)"],"rights":["I have not registered my thesis with the U.S. Copyright Office, and do not intend to."],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["https://openscholarship.wustl.edu/eng_etds/1221"],"render_values":[{"text":"https://openscholarship.wustl.edu/eng_etds/1221","href":"https://openscholarship.wustl.edu/eng_etds/1221","code":true}]}]},"links":{"outbound_url":"https://doi.org/10.7936/57eq-1r65","outbound_label":"DOI","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Ron K. Cytron","Steven Brams, Jeremy Buhler, Robert Pless, Itai Sened, Aaron Stump"]},{"key":"dc:creator","label":"Author","values":["LeGrand, Robert Hampton, III"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2025-06-20T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science & Engineering","McKelvey School of Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy (PhD)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Engineering","Engineering"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English (en)"]},{"key":"dc:rights","label":"Dc Rights","values":["I have not registered my thesis with the U.S. Copyright Office, and do not intend to."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://doi.org/10.7936/57eq-1r65","https://openscholarship.wustl.edu/eng_etds/1221"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Computational social choice is a relatively new discipline that explores issues at the intersection of social choice theory and computer science. Designing a protocol for collective decision-making is made difficult by the possibility of manipulation through insincere voting. In approval voting systems, voters decide whether to approve or disapprove available alternatives; however, the specific nature of rational approval strategies has not been adequately studied. This research explores aspects of strategy under three different approval systems, from chiefly a computational viewpoint.
While traditional voting systems elicit only the outcome of a voter’s strategic thinking, a Declared-Strategy Voting (DSV) system accepts such strategies directly and applies them according to the voter’s preferences over the available alternatives. Ideally, when rational strategies are employed on behalf of the voters, voters are discouraged from expressing insincere preferences. Approval voting is a natural fit for use with DSV, but, unlike for the common plurality voting system, there is no extant theory regarding the most effective approval strategies in a DSV context. We propose such a theory.
Approval-rating polls already serve an important role in assaying the views of an electorate on some subject of interest. Sites such as Rotten Tomatoes and Metacritic.com collect and display the results of approval-rating polls for movies and games. Moreover, sites such as Amazon and eBay collect approval ratings to estimate the worthiness of their buyers and sellers. In these polls, a rational voter’s approval or disapproval will sometimes be insincere so as to move the result in a desired direction. A nonmanipulable protocol would allow indication of a voter’s ideal outcome and would never reward an insincere such indication. We present and analyze a large new class of such nonmanipulable protocols motivated by the DSV concept.
The minimax procedure is a multiwinner form of approval voting that aims to maximize the satisfaction with the outcome of the least satisfied voter. Unfortunately, computing the minimax winner set is computationally hard. We propose an approximation algorithm for this problem, a framework for polynomial-time heuristics that perform very well in practice, and a preliminary analysis of strategic voting under minimax.
"]},{"key":"dc:title","label":"Title","values":["Computational Aspects of Approval Voting and Declared-Strategy Voting"]}]}],"canonical_facts":{"dc:contributor":["Ron K. Cytron","Steven Brams, Jeremy Buhler, Robert Pless, Itai Sened, Aaron Stump"],"dc:creator":["LeGrand, Robert Hampton, III"],"dc:date.available":["2025-06-20T07:00:00Z"],"dc:description.abstract":["Computational social choice is a relatively new discipline that explores issues at the intersection of social choice theory and computer science. Designing a protocol for collective decision-making is made difficult by the possibility of manipulation through insincere voting. In approval voting systems, voters decide whether to approve or disapprove available alternatives; however, the specific nature of rational approval strategies has not been adequately studied. This research explores aspects of strategy under three different approval systems, from chiefly a computational viewpoint.
While traditional voting systems elicit only the outcome of a voter’s strategic thinking, a Declared-Strategy Voting (DSV) system accepts such strategies directly and applies them according to the voter’s preferences over the available alternatives. Ideally, when rational strategies are employed on behalf of the voters, voters are discouraged from expressing insincere preferences. Approval voting is a natural fit for use with DSV, but, unlike for the common plurality voting system, there is no extant theory regarding the most effective approval strategies in a DSV context. We propose such a theory.
Approval-rating polls already serve an important role in assaying the views of an electorate on some subject of interest. Sites such as Rotten Tomatoes and Metacritic.com collect and display the results of approval-rating polls for movies and games. Moreover, sites such as Amazon and eBay collect approval ratings to estimate the worthiness of their buyers and sellers. In these polls, a rational voter’s approval or disapproval will sometimes be insincere so as to move the result in a desired direction. A nonmanipulable protocol would allow indication of a voter’s ideal outcome and would never reward an insincere such indication. We present and analyze a large new class of such nonmanipulable protocols motivated by the DSV concept.
The minimax procedure is a multiwinner form of approval voting that aims to maximize the satisfaction with the outcome of the least satisfied voter. Unfortunately, computing the minimax winner set is computationally hard. We propose an approximation algorithm for this problem, a framework for polynomial-time heuristics that perform very well in practice, and a preliminary analysis of strategic voting under minimax.
"],"dc:identifier":["https://doi.org/10.7936/57eq-1r65","https://openscholarship.wustl.edu/eng_etds/1221"],"dc:language":["English (en)"],"dc:rights":["I have not registered my thesis with the U.S. Copyright Office, and do not intend to."],"dc:subject":["Computer Engineering","Engineering"],"dc:title":["Computational Aspects of Approval Voting and Declared-Strategy Voting"],"thesis:degree_discipline":["Computer Science & Engineering","McKelvey School of Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Doctor of Philosophy (PhD)"]},"updated_at":"2026-07-24T06:13:14Z"}