Nous Avons un Problème

A couple of weeks ago Fred Benenson and the folks at Kickstarter shared their version of Lunch Roulette. They have put it into the wild, it’s written in Ruby, and has some really neat features.

What I also really appreciated about the description of their approach was the deep dive into the ‘kind of problem’ that this is which, shame on me, I had not previously bothered to do.

Turns out, this is a problem in mathematics called the ‘maximally diverse grouping problem’ (MDGP) which consists of grouping a set of M elements into G mutually disjoint groups in such a way that the diversity among the elements in each group is maximized. This problem is NP-hard, but there are a number of interesting heuristics that can be applied. You can read more about this all here.

I started following Mr. Benenson on Twitter and saw this reflection on a conversation with his Father:

The problème des ménages is a combinatorial problem, framed as an exercise in seating a dinner party and that “asks for the number of different ways in which it is possible to seat a set of male-female couples at a dining table so that men and women alternate and nobody sits next to his or her partner.”

With me so far? Good.

There are a whole host of approaches and methods applied to this problem but, curiously, the creation of the proof of a solution may have been hampered by approaching the solution, starting with seating Women (or Men for that matter) first. A non-sexist solution can be found here. This particular ‘non-sexist’ approach, was described by James Gleick in a New York Times article in 1986 ‘MATH + SEXISM: A PROBLEM’, who sums it up quite nicely:

“Only by overcoming that habit of thinking - a habit that may or may not have any relation to social convention - does it become possible to solve the Menage Problem with the most elegance.”

Sometimes it’s important to take a moment and think about, deeply, the kind of problem you’re actually thinking about. Because there’s usually super smart people who made some contribution before you.

Thanks for listening.



Now read this

Deep Learning and Systemic Insight

A number of months ago, I staked the following claim: Through a combination of thoughtful physical space planning coupled with elements of rich mobile, network, and sensor data we can engineer the randomness of human interaction, in the... Continue →