MSRI-UP

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 pairwiseintersecting 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.

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 investigatevariants of this result.

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 su⇤cient 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.

In this paper we will examine elections of the following form: a committee of size k is to be electedwith 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 di

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.

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. TheMcLennan-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.