Time: 1:00 pm Wednesday, 22nd February 2017.
Location: SIT 459
Speaker: Jonathan Chung, University of Sydney
Title: Computing the Yolk in Spatial Voting Games
The spatial model of voting describes a set of voters with Euclidean preferences on a multidimensional space of policies. A game within this model can be played as follows: given two candidates competing for the support of these voters, the objective is to find a point on the space such that no other point is preferred by more voters. However, in most voter configurations such a point is unlikely to occur. This motivates the idea of a yolk, which is a closed ball such any point inside the ball is preferred to by more voters than any point outside it. We show in a two-dimensional setting that the yolk is deterministically computable in O(n^(4/3) log^(2/3) n) time, and propose a (1 + epsilon)-approximation that can find the yolk in O(n log^3 n) time.