A society is a geometric space with a collection of subsets that represent voter preferences. We call this space the spectrum and these preference sets approval sets. The agreement proportion is the largest fraction of approval sets that intersect in a common point. Klawe et al. considered linear societies where approval sets are the disjoint union of two intervals, or double intervals. We examine arc-shaped double intervals on circular societies. We consider the case of pairwise-intersecting intervals of equal length and call these double-n circular societies. What is the minimal agreement proportion for double-n societies? We show that the asymptotic agreement proportion is bounded between 0.3333 and 0.3529and conjecture that the proportion approaches 1/3.

An Analogue of the Median Voter Theorem for Approval Voting

Students: Ethan Bush, Kyle Duke, Miles Stevens

Abstract:

The Median Voter Theorem is a well-known result in social choice theory for majority-rule elections. We develop an analogue in the context of approval voting. We consider voters to have preference sets that are intervals on a line, called approval sets, and the approval winner is a point on the line that is contained in the most approval sets. We define median voter by considering the left and right end points of each voters approval sets. We consider the case where approval sets are equal length. We show that if the pairwise agreement proportion is at least 3/4, then the median voter interval will contain the approval winner. We also prove that under an alternate geometric condition, the median voter interval will contain the approval winner, and we investigate variants of this result

A Matroid Generalization of Sperner’s Lemma

Students: Gabriel Andrade, Andres Rodriguez Rey, Alberto Ruiz

Abstract:

In a 1980 paper, Lov´asz generalized Sperner’s lemma for matroids. He claimed that a triangulation of a d-simplex labeled with elements of a matroid M must contain at least one “basis simplex”. We present a counterexample to Lov´asz’s claim when the matroid contains singleton dependent sets and provide an additional sufficient condition that corrects Lov´asz’s result. Furthermore, we show that under some conditions on the matroids, there is an improved lower bound on the number of basis simplices. We present further work to sharpen this lower bound by looking at M’s lattice of flats and by proving that there exists a group action on the simplex labeled by M with Sn.

Committee Selection with Approval Voting and Hypercubes

Students: Caleb Bugg, Gabriel Elvin

Abstract:

In this paper we will examine elections of the following form: a committee of size k is to be elected with two candidates running for each position. Each voter submits a ballot with his or her ideal committee, which generates their approval set. The approval sets of voters consist of committees that are “close” to their ideal preference. We define this notion of closeness with Hamming distance in a hypercube: the number of candidates by which a particular committee differs from a voter’s ideal preference. We establish a tight lower bound for the popularity of the most approved committee and consider restrictions on voter preferences that may increase that popularity. Our approach considers both the combinatorial and geometric aspects of these elections.

The Banquet Seating Problem

Students: Michelle Rosado Perez, Ashley Scruse, A.J. Torre

Abstract:

Suppose you want to seat n = mk people around k tables with m people at each table. Each person gives you a list of j people next to whom they would enjoy sitting. What is the smallest j for which you can always make a seating arrangement that would seat each person next to one of the people on their list? In this paper we show that j must be strictly more than half of n, the total number of people. Our key tool is a particular ‘blue-green-red’ lemma that helps us construct ‘worst-case scenario’ seating arrangements. We consider cases with two tables and more than two tables and explore seating arrangements with particular kinds of preferences.

A Volume Argument for Tucker’s Lemma

Students: Beauttie Kuture, Oscar Leong, Christopher Loa

Abstract:

Sperner’s lemma is a statement about labeled triangulations of a simplex. McLennan and Tourky (2007) provided a novel proof of Sperner’s Lemma using a volume argument and a piecewise linear deformation of a triangulation. We adapt a similar argument to prove Tucker’s Lemma on a triangulated cross-polytope P in the 2-dimensional case where vertices of P have different labels. The McLennan-Tourky technique would not directly apply because the natural deformation distorts the volume of P; we remedy this by inscribing P in its dual polytope, triangulating it, and considering how the volumes of deformed simplices behave.

MSRI-UP 2015: Research Projects

MSRI-UP 2015: Geometric Combinatorics Motivated by the Social Sciences