Voting in Agreeable Societies

“This is a mathematical statement,” Harvey Mudd College professor and MAA President-Elect Francis Su said, referring to Helly’s theorem, “but it has a social interpretation.”

Su has a penchant for connecting mathematics to the social sciences, and he did so in his public lecture at the MAA Carriage House on May 14. “Voting in Agreeable Societies” showed both that social problems can motivate interesting mathematics and that mathematics can model—and shed light on—questions in the social sciences.

Discovered by Eduard Helly in 1913, Helly’s theorem is a classical result from discrete geometry that describes how convex sets may intersect. A set is convex, remember, if for any pair of points in the set, the straight line between them is in the set.

Helly’s theorem says that in a finite family of convex sets in d-dimensional space, if every d+1 sets intersect mutually, then all the sets have a point in common.

Now for the promised social interpretation. Suppose you share living quarters with several roommates and need to set the thermostat. To each resident corresponds a range of acceptable temperatures. These temperature ranges are convex sets in one-dimensional space.

So, Su noted, “if you live in a house where every two people can agree on a temperature, then there’s a temperature that makes everybody happy.”

Of course there are weightier differences of opinion in the world than those about how high to crank the air conditioner. Su, for instance, hoped to apply Helly’s theorem or variants to electoral politics.

Though political elections in the United States permit each voter to select only one candidate, approval voting allows you to vote for as many candidates as you want. Under such a system, your approval set—the set of platforms you could support or candidates you wouldn’t mind seeing in office—is an interval on a political spectrum.  

Su calls a society linear if its political spectrum is a line and super-agreeable if it has the (admittedly “very strong”) condition that every pair of people can agree on a candidate.

According to Helly, then, a super-agreeable, linear society would have a candidate all voters would approve.

If this sounds too good to be true, that’s because it is.

“We don’t have any society that’s super-agreeable on any issue,” Su conceded. And the conclusion, too, is stronger than necessary or realistic. “We don’t actually necessarily care if everybody’s happy,” he said. “Often we just care if we’re making a majority happy.”

So Su and a student set about weakening the result into something meaningful.

They showed that if a society is such that among every three voters some pair of them can agree on a candidate—they called such a society agreeable—then there is a candidate approved by a majority.

Then, generalizing, Su et al. defined a (k, m)-agreeable society as one where, among every m voters, some k of them can agree on a platform. Definition in hand, they proved what they dubbed “the agreeable society theorem”: In a (k,m)-agreeable linear society, there exists a candidate that (k-1)/(m-1) of the voters would approve.

For the proof, Su and his collaborators pulled one of mathematicians’ favorite tricks. They converted the problem at hand into another problem, one more amenable to solution.

Su et al. constructed what they call an “agreement graph” G. They represented voters by dots and connect two dots with an edge if the preferences of the two voters overlapped. They were able to argue that cliques (or complete subgraphs) in G correspond to intersections of approval sets. Further, if voters whose preferences overlap must be different colors, the minimum number of colors required to color the agreement graph of a linear society equals the size of the largest clique.    

Not all societies are linear, of course, and Su concluded his talk by touching on ways to extend the work he had presented into multiple dimensions.

A political spectrum might be circular, for example, with leftist radicals and right-wing reactionaries resembling each other. Or voters’ preferences might not be connected intervals.

And you don’t even need to care about politics to see the relevance of Su’s results or the value of generalizing them to higher dimensions.

“I was hunting around and . . . I found a 29-dimensional example. A 29-dimensional example that millions of people actually care about,” Su said. “It’s called eHarmony [online dating site]. And the point is to land in lots of people’s approval sets.”—Katharine Merow

 Listen to Su's lecture (mp3)