Preferential Romance

A certain marriage counseling service called Marriage Success, or MS for short, advises couples on how to get along better. MS’s idea is simple: Each spouse writes down his/her preferences about various criteria of common interest. “Our criteria go beyond those elements of physical appearance and passion that guide early romance and tend to blind judgment. We want to understand your values as you live day to day. The happy couple is the one whose preferences are compatible or can be made compatible.”

Here are some of the positive qualities each person might wish a spouse to have: biker (B), cultured (C), enthusiastic (E), foodie (F), hiker (H), juggler (J), kayaker (K), movies (M), organized (O), puzzles (P), rich (R), theatre (T), and windsurfer (W).

Suppose X and Y are qualities of people. X→Y implies a preference for X to Y. Preferences are transitive, so X →Y and Y→Z implies X→Z. Two people are fully compatible if their preferences are consistent. The test for consistency is that there is some list of qualities that reflects both of their preferences. If two people aren’t fully compatible, then perhaps at least they are passably compatible, which means they would be fully compatible if each spouse dropped at most one preference.

Warm-Up

Suppose Bob’s preferences are

• K→M→P, and R→T

and Alice’s preferences are

• O→P→R and W→T.

Then would they be fully compatible?

Solution to Warm-Up

Yes. Ignoring the qualities not mentioned (because they can be put anywhere), here is a consistent ordering for these preferences: KOMPRWT. This is consistent in the sense that for every preference X→Y, X comes before Y in the list. On the other hand, if Alice added the preference R→M, then the couple would not be compatible because P→R and R→M implies P→M, but Bob has M→P. If Bob drops his M→P preference, then we would be left with:

• Bob: K→P, and R→T

• Alice: O→P→R→M and W→T.

This could yield the following consistent ordering, among others: KOPRMWT. So Bob and Alice would then be passably compatible.

MS requires that each person be consistent in that he or she has no cyclic preferences of the form X is better than Y which is better than Z which is better than X. The bad news is that the real Bob and Alice are both very opinionated, so they have each listed many preferences, so many, in fact, that I have drawn Figures 1-12 and 1-13 to illustrate.

Figure 1-12: Bob’s preferences in life. Note that he has no preferences for certain qualities, e.g., he has not said whether he prefers Alice to be cultured or to be a windsurfer.

Figure 1-13: Alice’s preferences in life. Note that she has no preference about whether Bob is rich or a biker.

1. Are Bob and Alice compatible, passably compatible, or neither? After dropping the smallest number of edges in zero, one, or both spouse’s preferences, try to find a consistent ordering.

2. [For the entrepreneurial at heart] Can you describe an algorithm for the counseling company to use to help marriages in distress? That is, try to find a method so spouses have to drop as few preferences as possible.