Introduction


In referendum elections, voters are often required vote simultaneously on multiple questions or proposals, some of which may be related to each other.  The separability problem occurs when a voter’s preference for the outcome of one or more proposals in the election depends on the possible outcomes of other proposals.  For instance, suppose a voter wants Proposal A to pass, but only if Proposal B does not pass.  This voter’s preferences would be considered nonseparable.  When election day comes and both proposals are on the same ballot, the voter will have a difficult time deciding how to vote, particularly on Proposal A.


In order to better understand the separability problem and its potential solutions, recent research has focused on the multidimensional preferences associated with voters in referendum elections.  During the 2014 REU, we will continue the work started by Beth Bjorkman and Sean Gravelle in 2013 by investigating graph theoretic models of referendum election preferences.


The main idea is to view voter preferences in an n-question election as Hamiltonian paths within graphs of order 2nWe can then consider which graphs give rise to preferences with interesting properties, such as separability.  The two extreme cases result from starting with a path of length 2n (which allows only two possible preference orders) or from starting with a complete graph (which allows any possible preference
order to be realized as a Hamiltonian path).  In between these two extreme cases is where we will find the most interesting questions.  For instance, what is the largest graph for which every Hamiltonian path corresponds to a separable preference order?  What is the smallest graph that allows all separable preference orders to be realized as Hamiltonian paths?  What interdependence structures can arise from preferences generated by a given graph?


We will explore questions like these, along with related combinatorial questions that may help us tackle some difficult counting questions pertaining to multidimensional voter preferences.


What will this research involve?


This project will involve looking at examples, finding patterns, making conjectures, and proving results.  Although the main problem has its roots in a practical application, our work will have more of a “pure math” feel to it.  Our results may or may not have applications to actual elections, but we will definitely do some interesting mathematics along the way.


Desirable experiences for applicants


Although this problem uses graph theoretic models, it is not necessary for applicants to have an extensive background in graph theory.  Some exposure to the terminology associated with graphs, and some of the more familiar examples of graphs, would be helpful.  Perhaps more important than knowledge of graph theory, however, is an ability to read and write mathematical proofs, formulate and work with precise definitions, and communicate mathematical results clearly and precisely.  The strongest applicants will have at least one proof-based mathematics course and some basic knowledge of discrete mathematics.  Students who do not have discrete mathematics experience but have taken other proof-based courses, such as abstract algebra or real analysis, are still encouraged to apply.


Further reading


For a basic survey of the separability problem in referendum elections, read this paper which appeared in the October 2011 issue of Mathematics Magazine.

 

Jonathan K. Hodge, Ph.D.

Associate Professor and Assistant Chair

Department of Mathematics

Grand Valley State University