Rohit's Realm

// / archive / 2008 / 05 / 05 / stable-marriage-and-information-failure-in-the-social-marketplace

May 05, 2008

Stable Marriage and Information Failure in the Social Marketplace

Standing around at a bar last Friday night, sipping a dirty martini and semi-engaged in a lackluster conversation with some random woman I had met approximately ninety seconds earlier, I felt my thoughts drift almost involuntarily from trying to figure out whether she was attractive or I was hallucinating, to the Stable Marriage Algorithm and pervasive information failures in day-to-day existence. This is only one of the many reasons why I do not have a girlfriend.

The Stable Marriage Algorithm, a Primer

At the outset, it is probably necessary to explain the Stable Marriage Algorithm1 to those who do not have the great privilege of holding a degree in computer science—nor the concomitant life marked by unchecked awkwardness, universal mockery, and paralyzing sexual frustration. Wikipedia describes it as an algorithm which solves the following problem:

Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference, marry the men and women off such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are stable.

Perhaps that still does not make sense (it barely does for me). But the intuition should be clear, I hope: if everyone in a particular group ranks at a particular level of desirability vis-à-vis everyone else, the algorithm purportedly will assign you to the highest-ranked person on your list who cannot get anyone that ranks better than you on their list. In essence, the point is to make everyone settle for the least-bad person that they can get because, theoretically, if either partner in a couple could get someone better, they would do so, and thus, break the marriage. In that way, the problem tracks so-called real life very well. What is marriage2 if not settling for the least-bad person you can get given your own inevitable worthlessness. In fact, that's the best case scenario; many people settle for much worse than the least-bad they could have gotten (e.g., the foolish person I trick into marrying me).

Information Failures

Now, onto the real question: why did my thoughts drift to Stable Marriage when I should have been staring unabashedly at the woman who had made the grievous error of initiating conversation with me (and coming up with something inadvertently offensive to say that would promptly end any chance I may have had)? The answer is rather simple: interactions in bars, clubs, and the like tend to be extremely inefficient, and could be drastically improved by better application of the principles which underlie the Stable Marriage Algorithm.

To be clear, the problem is not that we do not implement stable marriage in the aforementioned social settings, only that we do a piss poor job of it. The fundamental cause of our inefficient implementation is information failure. In deciding to approach (or not approach) an acquisition target in such a setting, an individual has very little to work with to make a rational decision. In the worst case scenario, i.e., the stranger case, all that one has is physical appearance—both the individual's and the target's—which unfortunately does not comport with individual desirability ratings at any level of meaningful granularity outside of Los Angeles and South Beach (where all that matters is how hot you are). However, if there was a mechanism for disseminating even slightly better information, many inefficient transactions could be avoided.

Friday Night's Failed Transaction

An example should clarify what I mean. Returning to the bar, ninety seconds earlier, I had been paying for a round of shots when the woman in question approached. Unlike my woeful failures in the past, I was not confused as to why this approach had occurred. The conversation began with a discussion of what the shot was, what was in the shot, and how she and her friend were here to celebrate the latter's birthday. In short, the proposed transaction was a $10 drink in exchange for five minutes maximum of a moderately uninteresting conversation with a moderately attractive woman, whereupon she would thank me for the drink and excuse herself. Talk about no-value-add.

Sadly, this occurrence is one I am altogether too familiar with from my days as a corporate douche. I was not inclined to accept the entirely worthless transaction then, and I certainly was not going to do so now, when I had no steady income and an ever-increasing debt. Nevertheless, I had to expend resources, namely time, in avoiding the overture:

Moderately Attractive, Moderately Uninteresting Woman: Wow, that's a lot of shots!
Rohit: (looking up) Yeah, well, it's been a long day.
MAMUW: (laughs) What are they shots of?
R: Liquid cocaine.
MAMUW: What's that?
R: (already bored) Bacardi® 151, Goldschlager® and Jager(meister)®
MAMUW: Must have been a real long day.
R: Most days are when you hate your life as much as I do.
MAMUW: (laughing) Oh, it can't be that bad.
R: (straight faced) You have no idea.
MAMUW: (laughs again and briefly places her hand on my arm) You're funny. So, who are all these shots for?
R: (pointing vaguely to law school comrades) My friends over there.
MAMUW: Oh, I see. Yeah, I've never had a liquid cocaine shot before. I don't know if I could handle it. Are they good? I don't do that well with shots. My friend's been trying to make me take them all night. It's her birthday. She's coming over here right now. She's really hot, isn't she?
R: (handing shots to said comrades) You should buy her one. It's a good shot. Cheers!

At that point, I took the shot with my friends, and walked away. Perhaps some of you think I was a bit harsh. Then again, perhaps the same some of you are idiots. Such nonsense conversations already have a negative value; why anyone would pay to engage in them is beyond me. The larger point is that this was a lose-lose interaction. She did not get her drink, and I'll never have those two minutes of my life back. Moreover, had there not been a colossal information failure, she might have indeed met a person more amenable to paying $10 for a negligible chance at a phone number.

The information failure here was simple: this particular woman's thinly-veiled attempts to score a free drink for herself, and possibly her friend, did not comport with fundamental notions of dual income and brand management which form the basis for my ranking system; indeed, her actions flew directly in the face of the sacred criterion of dual income. So, while her mistaken belief that I was an individual willing to buy her a drink may have upped me in her ranking system for the purpose of that transaction, my steadfast commitment to not engaging freeloaders resulted in her receiving a very low rating on my list for the same transaction. Had there been a way for her to know ex ante (yes, I went there) about my commitment to dual income, this failed transaction would never have occurred, and both of us would be better off.

Then, the $64,000 question: how can we disseminate information better in the social marketplace to avoid such patently inefficient expenditures of resources? Certainly, the advent of dating websites has significantly reduced information failure in the social marketplace as a whole, but such technology has done little to address the problems faced in casual interactions. Technology may still be the answer, however. I'm thinking software running on Bluetooth-enabled smartphones that could assess basic compatibility with those individuals of the proper gender in your general vicinity, and let you know which ones are (1) compatible, and (2) available. In fact, if stable marriage could be implemented in a distributed manner, we might even be able to achieve the optimal result (the Holy Grail in both economics and engineering) for any given venue at any given time. Think of the possibilities!

Don't even think of jacking my idea! Patent pending!

^ 1 Long time (really long time) readers may recognize the Stable Marriage Algorithm. In fact, more than four years ago, I implemented this algorithm in a web application for a dating game I ran as a Resident Assistant at Unit 3 for Valentine's Day, 2004. The application assigned each resident who partook in the program with his or her most compatible mate based on answers to a survey. It was rather awesome.
^ 2 Though the algorithm name says marriage, it can be used in any instance where matching is involved. So, for instance, even if you are only looking to get paired up with someone only for the night, the algorithm, and thus, this article, would still apply to you.


Yeah, she really fucked up with that attempt. How was she ever going to find a guy in that bar willing to throw around money on shots to impress two attractive? I'm sure she lost sleep over your interaction. Next time she'll know to approach a guy ready to discuss brand management and dual income. With that said, I enjoy the exchange.

Interesting use of game theory. She has information asymmetry (not knowing whether you're the type of guy to buy drinks). The pay-outs for her are either free drink or nothing. However, you can derive all the information you need to know within the first five seconds of the interaction: that if you pay for her drink you have an infinitesimally small chance of getting her number, or you can walk away at no cost (or the cost of having an artificially constructed interaction, which is clearly dear to you). The Nash equilibrium in that scenario is exactly how it played out.

The only way to to save yourself in the future is to change her payout expectations. By calling her a skank ho, you change her outcomes to either free drink or embarrassment. She may then play the same game in the future, but will only do so if she's particularly risk-loving, or genuinely interested (which, in turn, changes your response strategies).

So the solution here could be blue-tooth communication, as you suggest. Or it could be the elimination of social graces that inhibit negative feedback mechanisms for trick-ho behavior.

Here's a thought: if a girl comes up to you in a bar, instead of concocting some elaborate theory involving both computer science and economics, perhaps you could try staring at her boobs. Now that's a value-added transaction.

I agree that very likely this girl was a skank-ho looking to score a free drink. However, the bigger problem for you is this: if she wasn't one (i.e., she was genuinely interested), you wouldn't have been able to tell, and further, would have alienated yet another woman (will the list ever end?). Think about that! What if she was the one?

I think the solution to the Stable Marriage Algorithm is incorrect, and the problem itself is not always solveable.

Here is the solution from wikipedia:
function stableMatching {
Initialize all m \in M and w \in W to free
while \exists free man m who still has a woman w to propose to {
w = m's highest ranked such woman
if w is free
(m, w) become engaged
else some pair (m', w) already exists
if w prefers m to m'
(m, w) become engaged
m' becomes free
(m', w) remain engaged

The while loop is looping on whether there are men who still have somebody left to propose to (i.e. a particular man is assumed to be desperate and just going down the list.) Remember though that the stable marriage problem's success condition is when nobody has nobody they'd rather have (or, everybody has the person they want). The stated algorithm doesn't do that. It assumes that if the woman you want is taken, you're just going to go down the list, and that's the woman you'd rather have. That's not going to get me the woman I want. That's going to make me settle.

Rohit, while smart is definitely sexy, being simultaneously nerdy and douchey is not. You should have bought her a drink for an entirely different reason than utility: joy that a moderately attractive, moderately uninteresting woman deigned to talk to your sorry ass.

When building this algorithm, don't forget the fundamental problem of online-dating: self-identification. We certainly can't rely on the masses to accurately describe their value. I suggest you start with a small test group where you categorize everyone and assess their net worth. If successful, you can spend the rest of your life rating the world population 'hot' or 'not'.

On the topic of dual income - in Germany, the tax system is set up so that if one spouse earns significantly more, the lower-salaried spouse can be in a high tax bracket and the higher-salaried spouse in a low tax bracket, thus they pay lower taxes overall. So here, even if your spouse earns less, they can still add significant value. You may have to widen your search parameters.

Add Comment





* required field

E-mail addresses will never be displayed. The following HTML tags are allowed:
a abbr acronym address big blockquote br cite del em li ol p pre q small strong sub sup ul