The Real-Life Tragedy of Myerson and Satterthwaite’s Impossibility Theorem: A Tale of High Drama, Intrigue, and Duplicity
[Attention conservation notice: Skip to the “Post-Mortem” for the real point of this post; the prelude is mostly for entertainment value and may be interesting to renters renegotiating their rent after the housing crash.]
When rent prices plummeted throughout New York City, we were a little galled to see a small increase in rent on our renewal lease. Were our landlords hoping we weren’t paying attention? If we moved out they’d have to accept, by our estimates, two or three hundred less in rent and/or miss multiple months of rent altogether. We made this clear to our landlords, as well as conveying how willing we were to move if we didn’t get fair rent. But this was apparently cheap talk to them. They were looking at the other side of the coin: to get a couple hundred dollars off our rent we’d have to go to the trouble of moving. So negotiations ensued.
Now to be clear, actually moving made little sense. It was an expensive and annoying proposition for both us and our landlords. And there was no reason we wouldn’t be willing to pay at least a bit more for our apartment than whoever our landlords would replace us with. In fact, if our original renewal lease had offered even a small decrease there’s little doubt we’d have just signed it. The elaborate negotiations amounted to a game of chicken where swerving was “fine, here’s your inflated rent” or “fine, we’ll take your stingy rent”. Neither of us swerving would mean moving out.
Of course to make that threat credible we had to actually start looking at other places, which we did. And it was quite a buyers’ market. Tons of vacancies, great deals, and the notorious brokers’ fees were usually being covered by the landlords. We also talked to our neighbors in our building, to compare rents (why don’t people do this more often?), and found out some of the slimy, duplicitous tactics of our landlords. The more we learned the less of a bluff our bluff was. We were quite willing to move unless our landlords offered us something close to fair market price.
We told this to our landlords, who offered a reduction of $82/month, and a one-time $100 gift certificate as a bonus. Insulting! But just to be quite certain what fair market price was, we enlisted our friends, David and Grace, who happened to be apartment hunting. They called our landlords and were referred to a slick, high-pressure broker who, well, wouldn’t quote them a price for our apartment. I took over at that point, posing as David (speaking of duplicity, but it was with David’s permission) in a long series of phone calls and emails before getting this broker to even name a price range. And sure enough — consistent with other buildings we looked at, and our neighbors in our building who moved in since the housing crash — it was a couple hundred dollars below the lowest price we as existing tenants (perfect ones, let there be no doubt!) would ever get from our landlords.
So we knew what kind of rent they should be willing to accept from us, but how to get them to do so? We did have one card up our sleeve. As the negotiations progressed, with the end of our lease less than two weeks away, the landlords threatened us with what they did (in that case without warning) to our neighbors: If we didn’t sign a renewal lease by the first of the month our rent would go up to the legal limit (literally double in our case). It was time to put our last card on the table, in the form of counter-offer to their $82/month reduction: A $200 reduction and as a bonus we’d tone down the first google hit on their name.
This got their attention. According to our access logs, they googled themselves several times that day. But they didn’t let on and they made no move to swerve from their hard line. And neither did we. We were headed for a grizzly collision. It was now within a week of the end of our lease, and we hadn’t started packing. Perhaps our landlords were observing that and thought they had us right where they wanted us. In fact, we were lining up professional movers and signing a new lease at a building down the block. With two days before our lease ended, the movers swooped in and we left the keys in the empty apartment the next day.
Post-Mortem
I said that actually moving made little sense, costing both us and our landlords a lot of time and money. So why did it happen and could we or should we have avoided it?
First, were we irrational? Not at all! Our new apartment is a much better deal and I think we did everything we could to get a fair price from our landlords. At our old landlords’ best offer, we preferred our new place.
So were our landlords irrational? Surprisingly, no. Their strategy, as much as it gets my goat, is sound. They’re engaging in a simple form of price discrimination. [1] Landlords have an extremely simple price discrimination litmus test: Do you already live there? Then you’re probably willing to pay a juicy premium to stay there. Other apartments may offer more for the money but they all have the distinct disadvantage of not having all your stuff in them. Our landlords exploited this ruthlessly. Sure, it cost them plenty in our case but as a blanket policy it probably does well. And making exceptions is dangerous, since tenants may talk to each other.
So everyone follows rational strategies and the result is a lot of needless apartment switching? Surely there’s a better way! Consider the fundamental situation: A seller (the landlords) selling something (an apartment lease) to a buyer (us). And, importantly, the most the buyer is willing to pay and the least the seller is willing to accept are private values, much as they loudly insist that they can’t possibly yield another penny. What could we do besides verbal haggling in situations like that? Lots of things, it turns out. You could have a sealed-bid auction where the buyer and seller both write down their final offers and the deal happens if and only if the offers overlap (the buyer’s number is higher than the seller’s) in which case the final price is the average of the two. This works fine but you’d be well-advised not to write down your true maximum as a buyer or minimum as a seller. And with both parties strategizing like that, there will be times when their true values overlap but the numbers they write down don’t. That is, this mechanism will sometimes say “no deal” even when there was a price everyone would’ve been happy to make the deal at.
An even simpler mechanism is the one most of us are most used to: the seller picks a single price and the buyer takes it or leaves it. Here it’s especially easy to see the problem: the seller won’t name their true rock bottom price. That means for any buyer with a maximum willingness to pay between the seller’s secret rock bottom and the posted price, the deal won’t happen.
How about a more complicated mechanism with iterative bidding or proxy bidders that bid optimally on your behalf? Alas, this is the real tragedy: Nothing will work. No possible mechanism can prevent tenants from sometimes moving out, even when there’s a price that would make both parties prefer the tenants to stay. In other words, try as we might to find a mutually agreeable price, there’s no guarantee we’ll succeed, even when such a price exists!
The Impossibility of Avoiding Grizzly Collisions (Myerson-Satterthwaite)
There’s a famous result in economics called the Coase Theorem that says that when people are free to bargain with each other, the efficient (welfare maximizing) thing will happen. But it assumes all the information is public: the tenants know exactly what the landlords will accept (as we thought we did but were obviously wrong) and vice versa. When no one can be sure if the buyer’s and the seller’s values overlap (including the buyer and seller themselves) [2] then a different theorem kicks in: the Myerson-Satterthwaite Impossibility Theorem. It states that there are three important properties [3] that you just can’t have all at once:
1. No subsidies. You can burn money but you can’t conjure it. [4]
2. No coercion (forced participation). Neither buyer nor seller, knowing their own valuation, would prefer to opt out of the mechanism altogether. [5]
3. Efficiency (welfare maximization). The seller sells the item to the buyer if and only if the buyer values it more than the seller does.
The last property — technically known as ex post efficiency — is key. It means you don’t have buyer and seller playing chicken with each other, calling bluffs that aren’t bluffs, and ending up colliding — failing to make the trade when it was in everyone’s best interest to do so.
But, tragically, since the first two properties aren’t exactly negotiable, it’s efficiency that has to give. And that’s what we told our two-year-old when she asked why we had to move.
Illustration by Kelly Savage.
Footnotes
[1] Price discrimination means charging more to people who are willing to pay more. The trick is that people who are willing to pay more don’t freely admit this. Airlines manage to discriminate by charging more if your trip doesn’t span a Saturday (since that means it’s likely a business trip and business travelers tend to be willing to pay more). Grocery stores do it with coupons (by your willingness to cut out coupons you reveal yourself to be more price sensitive). Companies often discriminate by offering two tiers of service (like Windows Professional Edition vs Windows Home Edition, or whatever). Student/senior discounts are another classic form of price discrimination (the assumption being that students and seniors tend to be more price sensitive).
[2] Technically stated, we assume that the seller’s valuation distribution is nonzero on some closed interval, as is the buyer’s, and these intervals have a non-empty intersection. We also assume that these distributions are independent. Additionally, there are two standard assumptions about the buyer and seller: Risk-neutrality and quasilinear utility.
[3] A common misconception is that one of the properties is incentive compatibility. Myerson and Satterthwaite fuel this misconception in their own statement of the result: “If [assumptions] then no incentive-compatible individually rational trading mechanism can be ex post efficient.” In fact, by the Revelation Principle, (Bayes-Nash) incentive compatibility is without loss of generality. In other words, even without imposing incentive compatibility, you can’t simultaneously achieve weak budget balance, individual rationality, and ex post efficiency.
[4] The technical term for this is weak budget balance. It’s probably a must-have mechanism property but if you did have a generous benefactor, here’s what you’d do: The buyer and seller each write down their bids. If they don’t overlap then no deal (which is good since that means the seller values it more than the buyer, if they both told the truth which it turns out they’ll want to). If they do overlap (the buyer’s bid is higher) then the buyer pays the seller’s bid and the seller receives the buyer’s bid. Of course that means the seller is getting paid more than buyer is paying, and it’s that generous benefactor that makes up the difference. The buyer now wants to say a number so high that any higher and they’d rather not buy the item. (Why not? The price doesn’t depend on their own bid.) And it’s the same for the seller, who wants to name the truly rock bottom price they could possibly accept. Everyone’s happy (except the benefactor) and the deal happens exactly when it should. This is an application of the Vickrey-Clark-Groves mechanism.
[5] The technical term for this property is interim individual rationality. What could you do if you were willing to broker a deal at gunpoint? Remember, we’re still trying to maximize welfare so we don’t want to just say “Hey, Seller, cough it up or else!” Instead we can just extract a fee from either or both of them before participating. Once we have that we can use the VCG trick without needing a “generous benefactor” (see previous footnote). The catch is that the fee would have to be so high that a rational agent would rather not play, hence the need for the gun. So this property is probably a must-have as well.
