The Real-Life Tragedy of Myerson and Satterthwaite’s Impossibility Theorem: A Tale of High Drama, Intrigue, and Duplicity

Sunday, May 24, 2009
By dreeves

[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.

Tags: , , , , , ,

• http://hanson.gmu.edu Robin Hanson

What about long term contracts? That moves the price discrimination to the early point the relation, but could still be better.

• Econominx

Pretending that there’s no regulatory framework limiting the options here…

What about contracts that are contingent on something like citywide vacancy rates? Such a contract would protect landlords from underpaying tenants in periods of high demand, protect tenants from overpaying in buyers’ markets, and protect both sides from unnecessary moving costs and unwanted periods of vacancy.

Very well written: engaging story and good punchline nicely tying theory and practice.

You alluded to one reason why the story differs a bit from the theory: your landlord is worried about his reputation in a repeated game. The theory assumes a one-shot auction where the universe ends thereafter, right?

• http://www.u.arizona.edu/~dreiley David Reiley

A timely tie-in is the credit-card regulation law that passed Congress last week. Credit-card companies have recently been jacking up their rates (i.e., prices) on customers who have accumulated a lot of debt with them. For example, a customer carrying $20K in debt, who has been paying bills on time for several years with a 12% interest rate, suddenly gets told “In six weeks we’re raising your rate to 24%. You can have us keep you on the old payment plan if you like, but if you do that, you won’t be able to make any new charges with this card.” I have a friend who rationally responded to this by saying she wanted to stay with the old plan, and by getting a new credit card. It’s clearly inefficient to have this happen. Her existing credit-card company knows how valuable a customer she is, more so that competing companies who might issue her a new card. In particular, her existing company knows her complete history of on-time payments, whereas other card companies might be scared to make her a new loan right now when many people seem at risk of defaulting on debt. She did end up finding a new card, but they didn’t give her a big enough credit limit to transfer the old debt. In the end it was OK for her – she has her old debt at the old price, and she has a new card that lets her make payments when she wants to make a new credit-card payment. But there was a lot of hassle in the meantime. She had to shop for a new card, she had to remember to convert her recurring payments to the new card, etc. And the previous credit-card company lost her as a good customer who would continue to make payments with them. This is just one example of many recent claims of card companies “gouging” their existing customers by jacking up the price, just as Dan and his family experienced with their landlord. I found it a bit puzzling that such things would start happening so much more frequently this year. I mean, if jacking up rates on existing customers is a profitable price-discrimination strategy, why didn’t they jack up to 24% on existing customers a year or two ago? The answer seems to be that competition in the credit-card market has gotten softer during the financial crisis. Usually, the threat that an existing customer would switch cards would be high enough that a company couldn’t jack up rates too much without losing the customer. But during the current credit crunch, it’s much harder for customers to switch, because so few new loans are being approved. This gives firms more market power over their existing customers than they usually do. Or so I hypothesize (thanks to Robin Lee for clarifying my thinking on this). As an aside, Coase never assumed that the parties would have perfect information about each other’s values for trading with each other. He wrote in the days before noncooperative game theory was used much, and he just made a reasonable assumption that if people had clear property rights and no transaction costs), then they would reach an efficient outcome. After his work, Rubinstein and Stahl showed that if two parties bargain over a publicly known amount of surplus in an alternating-offers game, and both agents are rational players, we should expect an efficient trade to happen right away. But Myerson and Satterthwaite showed that such efficiency couldn’t happen in the presence of private information about how much surplus might be generated for each party. (Coase contrasted property rights and low transaction costs with the opposite situation, where it’s too costly to trade. For example, think about millions of individual car drivers trying to compensate thousands of asthmatics for the reductions in air quality that they suffer as a result of the car exhaust. Conducting those billions of individual transactions is infeasible, so it doesn’t happen, and we end up with an inefficiently high level of pollution. Cap-and-trade systems are a policy attempt to assign clear property rights for pollution – or its absence – and thereby get more efficient levels of pollution.) • http://www.benmccann.com/ Ben McCann The optimal strategy in a negotiation mirroring a game of chicken is to make the other side think that you can’t chicken out. In a game of chicken between two cars, you could handcuff yourself to the steering wheel, so that the other side knows you have no possible way to bail, and they must themselves bail out. In this case, you could sign a lease at another building contingent upon your not signing a renewal at your current location with a$200/month rent reduction. Now if the landlord does not put forth a suitable offer, you will be contractually obligated to move out.

• http://cheeptalk.wordpress.com jeff

Hi, nice story.

I think you need to clarify what you mean about incentive compatibility. There are direct mechanisms that satisfy budget-balance, efficiency, and individual rationality. Here is one. If the seller’s cost is less than the buyer’s value then they trade at a price equal to the midpoint. (any price between value and cost will do.)

Of course that mechanism is not incentive compatible becuase either party would have an incentive to misreport their value/cost in order to get a more favorable price. So incentive compatibility is required for the Myerson-Satterthwaite theorem.

On the revelation principle. It does not say that incentive compatibility is without loss of generality. It says “if there is any mechanism at all that achieves your ends (under the solution concept of Bayesian Nash equilibrium) then there is a direct mechanism that is incentive compatible and achieves your ends.” The practical implication of this is that whatever impossibility result you obtain by restricting to direct, incentive-compatible mechanisms, obtains also in the more general class of mechanisms (under the solution concept of BNE.)

• http://ai.eecs.umich.edu/people/dreeves dreeves

@Robin Hanson: Maybe, though long-term contracts entail other inefficiencies.

@Economix: One problem with that is there could be idiosyncratic reasons justifying deviations from the market average — renovations, for example.

@Dave: Good point, yes, I’m not sure how much the story changes in a repeated setting.

@David Reiley: I love that credit card story (and hate credit card companies!). I may have been too glib in my comparison of Coase and Myerson-Satterthwaite. Thanks for the clarifications!

@Ben McCann: Smart! I had a similar thought involving a conditionally-refundable deposit with a moving company, ie, prove to the landlord that if they gouge us on rent then the moving expenses will become a sunk cost.

@jeff: No, your mechanism (a sealed double auction) is not efficient. I agree completely with your statement of the revelation principle though. That’s actually what I meant by “IC is WLOG”: By the revelation principle we can, WLOG, consider only IC mechanisms. Thus, IC is not needed in M-S. With or without an IC restriction, you can’t have BB+IR+EFF.

• http://cheeptalk.wordpress.com jeff

The mechanism I describe, by construction, trades the good whenever the seller’s cost is less than the buyer’s value. It is therefore efficient. (Please understand that in mechanism design, a direct-revelation mechanism is a function which maps types (here values and costs) into an outcome. A direct-revelation mechanism is defined to be efficient if that mapping always produces the efficient outcome as a function of types.)

When you say “the double auction is not efficient” what you are really saying is “when the players play a Bayesian Nash Equilibrium of a double auction, they will shade their bids and the result is inefficient.” This is equivalent to saying that the mechanism I described (which is the direct-revelation counterpart of the double auction) is not incentive compatible.

To repeat, the Myerson Satterthwaite theorem says: Any direct revelation mechanism which is IR, IC, and BB is necessarily inefficient. Dropping any of the three (IR, IC, BB) enables an efficient direct revelation mechanism.

• http://ai.eecs.umich.edu/people/dreeves dreeves

@jeff: I believe we’re just using the terms slightly differently. You’re describing a fantasy mechanism where players play irrationally. But how the players play is not part of the mechanism. The mechanism is by definition inefficient because it yields inefficient outcomes in equilibrium. In that sense I disagree with your statement of M-S. But I think with that small translation, we’re both correct.

• http://ai.eecs.umich.edu/people/dreeves dreeves

To be more clear, here’s how I would state Myerson-Satterthwaite: It’s impossible (given some reasonable assumptions) to have all three of {IR, BB, EFF}, whether or not you also impose any form of IC.

I don’t like jeff’s version because it goes without saying that if you can administer a truth serum then you can get efficiency and budget balance (and individual rationality doesn’t even make sense anymore).

• Pingback: electricity saving device

• Pingback: Full File

• Pingback: Moneylenders-SG

• Pingback: target promo code 2012 swimwear

• Pingback: bandar judi bola euro

• Pingback: شركة العزل

• Pingback: click the next site

• Pingback: roof Installed

• Pingback: liga serie a