The Stable Marriage Problem

Nope, this post isn't about my home life. :)

There's a problem in computer science called the "Stable Marriage" problem. It's about how to match one set of people other people, based on asking each of the groups what they prefer the most.

It's best known as the system used by Medical school programs to match students with programs they like. For medical school, each applicant presents a ranked list of schools they would like to attend, and each school does the same. "The Match" picks the a good global solution to satisfy all these wishes. Not perfectly, but well enough that it "maximizes happiness"...or at least the computers think so.

I've been thinking about the comparisons with housing. And rather than having academic credentials like prospective med students, buyers have money, in varying amounts.

Recently, buyers have had a multiplier on their money: the amount of risk they were willing to tolerate in toxic loans (or they were otherwise convinced they could "afford"). If you were willing to accept a negative-am loan at a variable rate, or maybe a little appraisal fraud with cash back at closing, you could afford "twice as much" house for the same monthly payment. And as we know, home prices in some areas increased by 180% from 2000 prices.

So let's follow this argument to its painful conclusion: if the MCAT administrators were to say, "As of 2004, we're doubling all the test scores! It should make everyone so much more pleased with their results! With twice the score you'll get into a much better school!" Across the board, a rising tide lifts all boats, right?

Of course, because this is a contrived example, you know that nothing at all would change except for the MCAT scores. The Match would proceed identically to the year before, with everybody ranking schools in the same order and vice-versa.

And in areas like the one I live, where almost no new housing was created in 2004-2006, this is exactly what happened.

The loan amounts doubled. For just a bit, people got a little more house than they would before--they "matched" a little higher. But after awhile, they got the same house, or a little smaller one, for twice or three times the money.

I suppose all I'm saying is that the "housing market" just does something that most people don't readily assume: prices reflect demand, not value. After you get over that, price is just a number based on what everyone else can afford.

Of course, occasionally some value was added: Los Angeles County alone kept the Viking corporation in business. But upgrades to existing structures? 5% increase in value for a 100% increase in price. Not value, demand.

I usually get out my moral indignation hat and put it on at this point in the story. It makes sense that new construction of the highest quality could cost some money. But it seriously doesn't make sense for a house that cost $15,000 when it was purchased to now cost 100x as much.

But this is apparently how markets work, and I suppose that we'll see how they work on the other side of the housing bubble as well.

the caffeine test

http://www.oneplusyou.com/q/v/caffeine

My results?

You clicked 284 times in 30 seconds.

Your caffeine level for today is:

Near Death - Delusions of Godlike power

The Spreadsheet

I took this post down for a bit, because I wrote it at 4AM. Google Reader appears to have kept it indexed, so I've just succeeded in confusing people. It's back, warts and all.

There are lots of things I don't talk about on this blog. The housing bubble has been one of these. Housing is about money, and money is like politics and religion--you don't talk about them in public so much. But since awareness of the housing issue has shifted over the last year, it's a bit easier to talk about now.

If you've asked me about housing in the past 18 months (and if I wasn't being careful because you'd just bought a house) I almost certainly talked your ear off. I know lots of statistics. Lots. I rant. I'm obsessive. Sorry.

Lorna and I have been bearishly watching the housing market in Los Angeles since late 2004. We got married in 2006 and really wanted to move out of our apartment. Our friends all say, "You have the money. Why not?" And this is why not, yet.

Lorna found Ben's Housing Bubble Blog back in the very early days (2005), and we've been hawks in places like the nerdy but wonderful Calculated Risk ever since. I'll even confess to meeting people we met on the internet to talk about this. We thought we were insane for the better part of two years.

But the Internet has very much kept us from buying a house.

The problem was that we were aware back in early 2005 that the national income-to-housing price ratios were way off, especially in California. Other than the information we found on the blogs, Shiller's "Irrational Exuberance" (the second edition) was a really early indicator. Shiller posted charts and graphs that would make you say "something is very wrong." In our area, people were frequently spending 15x their income on housing. Expert advice says 3-4x income is actually manageable for most people.

Lorna even did a tongue-in-cheek art project featuring an ad for a $2m zero-down NINJA (no income, no job, no assets) loan. Do you think she made it up? Nope, it was clipped from an actual magazine in Los Angeles.

We studied the usual spate of statistics (LA prices throughout the 1990s) and decided that at some point housing would have to return to some reasonable multiple of income. These cycles had come back to earth twice before in LA, and it made sense that it would happen again, especially because this one was so much more extreme. We knew one or two older people in LA who said, "Wait. It came down last time." Not many, though. Most were of the lemming mindset, "Buy-now-or-be-priced-out-forever."

We were both doing really well from the Google IPO, and we actually could afford to buy a house, or so we thought. We could even buy a big house, maybe in nice part of town, right?

The Spreadsheet

One night, we made The Spreadsheet.

We wrote down a number, for a reasonable house, a 3 bedroom on a modest lot, or a very nice condo. Then we looked at historical values from 1990-1995, and decided that it might depreciate 20-30% in 5 years. Then we added in closing and realtor costs (8%), and taxes (1.2% a year), and insurance. And then we looked at the total.

The Spreadsheet said we'd pay 7 times our rent to live there for 5 years, and then sell.

Double-checked the math. 

Double-checked the rates. 

Double-checked the taxes. 

Double-checked the tax deductions.

Pretended we had a discount realtor.

7 times our rent.

Oh, and the house you could rent for 7 times our rent? A mansion in Beverly Hills with 6 bedrooms (not that we needed that). A big estate on Malibu Beach.

The Spreadsheet is dangerous.

The thing that we realized is this: because housing is financed with so much leverage, nobody can afford a house if housing prices decline. The numbers are incredibly scary.

Peter Viles reported that the median house in California is falling $2788 per week. That means the $550k median house in California "costs" the equivalent of $15,000/month, in rent. That amount should get you a big mansion in Brentwood, not a condo in Inglewood. The median homeowner cannot afford $15,000/month in rent.

In Santa Monica in early 1990, if you purchased the median house, you'd have been underwater in real value for 12 years. It didn't make sense that people who still remembered this sort of thing would do it again. But they did. And the west side of LA was the worst.

I have some thoughts about how we've gotten here. And we've heard the most awful stories, of toxic loans and crazy HELOCs and bad decisions. But how do people who had paid off half their mortgage a few years ago now find themselves in foreclosure?

I believe one big flaw is in thinking about your finances in monthly payments. People who HELOC'd their family home (taking out more than they paid in the first place) simply because the payments would be low (for 2 years at least) never actually tried to imagine that they were taking on massive amounts of debt. They believed that they had earned this "value" and that the debt was secondary to the whole windfall. They didn't try to conceptualize paying it off, or what that obligation would mean to their future.

Now, we're hearing about 7-year car loans, so that quite a decent percentage of people who sell a car now are underwater in their payments. It didn't matter for the first few years, though. There are so many people with loans they can only afford in the short term.

Lorna has been reading up on studies that say that fear and depression beget short-term thinking. (Phew, that's a topic for a whole other post.) But 9/11 and the resultant fear? Perfect time for 2/28 loans. You might not live another year. Why not have a nice kitchen?

There was also a funny psychology about these gains. If you realized that you couldn't actually afford to pay for a house but bought it anyway, it was very likely with the idea that you might sell it, earning a 100% return after a couple years. Great idea, right?

Well...when you move, you pay the difference between two properties, and presuming you bought a similar (or a larger house), that difference would get larger. It seems to have occurred to nobody that you couldn't win at this game. Where would you move after you sold your house so that you could afford to live there? To Arkansas? Kentucky? Or would you just "walk away"? I've actually met some real, live people who sold and now rent, but they are an extremely tiny minority. For most people, once they buy a house, they keep buying houses.

Lottery winners are famous for ending up in bankruptcy. And the short-term mindset is exactly the same. I remember overhearing two 25-year-old guys in a restaurant in 2006. They'd bought 2-3 houses apiece, and were discussing their gains. I still remember their giddy "It's free money!" refrain. Was it, really?

I think it's actually true that many people have "trusted the system" to do what's right, and I have to agree that the system has been extremely broken. Buying junk bonds with 32x leverage is a topic for another post.

Someone told me once that "you can only call the housing market once". As much as I rue the day I committed that to memory, it has been hugely informative. Our Spreadsheet took 10 minutes to make, and it told us a huge amount about what our future held. I really wish more people had done the math. It takes perhaps 8th-grade math to make your own. No calculus or trig.

We still want to buy a house very much, but we'll wait just a bit longer...until the spreadsheet makes a little more sense.

the harmonic mean (MPG standards)

One of the bits of math that's interesting to me is the "harmonic mean". It says that in things like fuel efficiency for cars, you often pay for the worst MPG vehicle, and it doesn't really matter how efficient you make the best one.

For a simple example, we'll consider a hypothetical Range Rover (10MPG) vs. a Prius (60MPG). You might think that a Prius "cancels out" a Range Rover in a sort of fuel-consumption way. But that's not true.

For instance, you compute a "simple average" like this: 60MPG + 10MPG / 2 = 35MPG. But this math is simply wrong. In fact, you have to use the harmonic mean (average the numbers in "gallons per mile") because you really care about gallons used, not miles/gallons.

Using the harmonic mean for this? 1/(1/60 + 1/10) = 17MPG on average.

How many Priuses does it take to "cancel out" one Range Rover (achieving the 35MPG above?)

Six.

It takes six Priuses to cancel out a Range Rover.

What's important here: improving the worst vehicles on the road is more important than making the best a little bit better.

The Hybrid Chevy Tahoe is much more important in the overall scheme of things than a plugin hybrid. Improving from 60MPG to 100MPG is diminishing returns until you get the 10-20MPG cars off the road. This includes old models! Improving from 10 to 30? Really significant.

Luckily the CAFE standards take the harmonic mean into account. But understanding this math explains quite well why "fleet averages" move so slowly upwards, even as technology gives us great ways to make the "best" MPG really quite good.

It also explains why our consumption levels are still going up. It will take years and years after the CAFE standards for new cars have improved for our actual consumption to decrease.

Practical ways to "reduce our dependence on foreign oil" should take a hard look at the worst vehicles on the road today, and not always try to optimize the best for slightly better gains.

lumens/watt

Dec. 19 2007: The Energy Independence and Security Act of 2007 was signed into law. For the original text, go to p83 here: http://energy.senate.gov/public/_files/getdoc1.pdf

This law progressively outlaws low-efficiency lighting (e.g., most incandescent bulbs) for "general service" lighting (310-2600 lumens, or approximately what you'd call a 30-150W incandescent bulb in a normal socket.)

There are special purpose bulbs that are exempted, but the bill appears to try its best to prevent exemptions. Notably excluded are 3-way incandescent lamps and reflectors, but there's quite a lot of provisions: if the sale of one of the types doubles, they'll make an effort to outlaw it, fast.

I have some concerns and comments:

1. This law would be appear to me much better with a progressive tax on energy-expensive sorts of lighting, so people can gradually migrate to new form factors. I tend to dislike "prohibit the sale of X by date Y." There are always exceptions not granted by a law like this, and an economic solution would be much more appropriate. This is heavy-handed.
2. It's not clear that the technology is appropriate to the problem (and let's hope the intervening years help it somewhat). For example, the bill specifies a minimum of 80CRI. This is rather insufficient for lighting high-quality artwork and photography (where 90+CRI is preferable). While high-CRI fixtures like these are available for purchase, it isn't clear to me that they will be available to the average consumer. (Incandescents are 100 CRI, which means that they represent all colors well, not just some.)
3. Directional applications are not well covered by CFLs, as they do not have both compact and high-output configurations. A powerful CFL is a very large CFL.
4. Low-intensity dimming is also not well covered by low-energy light sources today, and the warm candle-lit 1800 Kelvin output of an incandescent when dimmed may be replaced by the sort of sickly flicker that CFL's give at the same intensity. Dimming generally is not a strength of CFLs.

At home, we have replaced most of our "general" lighting in the house with CFLs. But it's the exceptions that make the place feel like home. We have very warm lights (yes, incandescents) in the bedroom that make you feel like sleeping. There are special lights for displaying artwork, and there are dimmers.

As I recall, most energy expenditure and CO2 emissions today come from heating and cooling (primarily heating), not from household lighting.

I've even been having the following thought this past few months: is it possible that the "waste" heat from Halogens and Incandescents actually cancel out lower heating bills, when used in cool climates?

It's nice to see some movement in this direction, but I wish in many ways that it weren't so heavy-handed. There are many market forces that would make this happen regardless: price, cost, etc. It makes so much more sense to me to find an economic solution.

I don't really want the "Attorney General" involved in "prohibiting the sale" of certain devices: they're not munitions and not imminently dangerous. The problem is solvable by great technology and prices in the market. The exceptions in life make it enjoyable, and I hope this bill spurs research in lighting to develop new solutions to many of these problems.

anniversary gifts

Lorna and I have been married for a year. That means (if you look it up) that we've just had our "paper" anniversary (meaning your anniversary gift should relate to paper). Technically we're allowed to substitute "clocks" if we're modern sorts of people.

While there were other gifts that I'm not going to go into, I thought it was worth sharing the paper one.

Over the past year we've had our honeymoon slashdotted and we've been on TV for not buying a car (because they wanted fingerprints first). So apparently we have some sort of privacy theme happening, at least in public.

So we bought ourselves a lovely 15-page micro cut paper shredder. (Frank Abagnale's picture is even on the box, promising that your identity won't be stolen as often if you use it.)

We had a really fun time cleaning the house of all those credit card offers, too.

Seam carving

Shai Avidan and Ariel Shamir made a cool image resizer.
It's terrifically easy to implement the basic technique. Try this thing I made.

Took about an hour or so.

Antialiasing styles

Some debate online over Safari's antialiased text on Windows.

Maxim has a good post here: Font Rasterization (Antigrain)

But I'll point out two things missing from the discussion:

1. Yes gamma correction is very important (I use gamma=1.4, and gamma=1/1.4 depending on whether or not I'm rendering dark or light text). Safari on Windows doesn't do seem to do enough gamma correction and so the comparison of "pure vector" vs. "hinted vector/cleartype" isn't quite fair here.

2. Filtering is also important. The original freetype paper had some mention of this, but most systems do box filtering in practice. If you box filter your fonts, you will not get consistent stroke widths. For my bitmap renderer, I use Lanczos-2 sampling from a 4x4 box-filtered source. (i.e. scaled to 25% at the pixel level). If you were really clever, you could do the analytic version of this for a vector renderer.

One of my favorite filtering tests (and subpixel tracking tests) is the "horizontal crawl" - make your text animate at +1 pixel translation/second, and see if it looks solid.

Picasa's does.

firefox mis-step

I apologize for maligning firefox's startup speed. It turns out if you remove all your extensions and toolbars, it starts faster than IE again.

Went from 6 seconds to 1 second that way.

chunky vs. reusable

I was thinking about how code evolves, since I found myself saying to Ari today, "It's about composition, not derivation. Everybody wants their own widget these days." Out of context that doesn't mean much, but let me explain.

Code gets chunky over time. It gets monolithic and intertwined, and it's inefficient to avoid this. Some code will only get used for one thing, ever, and it doesn't make sense to refactor that 100 lines of really spaghetti code into 5 functions.

But at the same time, for some code (more than you think), it does make sense--you refactor to make things just a little less intertwined, just a little more general, and eventually you can use it somewhere else entirely.

Why the caution? Why not do this all the time? All the popular programming books say to...

Well I've met Java programmers who make this sort of activity into an art form, with 75 interfaces and design patterns for a tiny simple function, so that their abstraction makes useful work impossible. Understanding their code requires days of reading. Basically, it's a way for them to show off, and that's not so good. (I don't know why this kind of thing centers around the Java part of the universe, but it seems to.)

In short, refactoring in the extreme makes for complexity, not simplicity. And simplicity is really the goal.

Some code will stay chunky, and that's fine.

Somewhat related to this discussion is one of the coding laws I kinda tripped over a number of years ago, and which I consider mostly magical:

Reduce Dependencies!

If you write code that doesn't have huge dependencies, or has well thought-out ones, you'll find that you can reuse it, that you can use it for another purpose or in a whole other application, and it's not hard.

If you write code with huge dependencies, this won't happen. I really believe in "build the tools, then build the application" idea, and while you should feel great if you finish a feature that real people can use, you should feel even better if you make a feature and a bunch of reusable technologies at the same time.

speed vs. size

I was doing wall-clock timings of how long it takes to launch Firefox vs. IE a few days ago, and was surprised to find out that IE is now much much faster.

When Firefox 1.0 came out, the faster launch was a big notable thing. IE was bloated, the argument went, and so you should use Firefox instead.

But the trouble is that added features and team size actually work against you on this kind of thing. If any single checkin can break app startup time, then there are many ways for things to go wrong, and only a few ways for them to go right. Same thing with features. An "important" feature can attract a lot of attention, but it's not always clear how it interrelates with overall application performance.

We've had to build some sophisticated systems to have Picasa performance keep up as we add more background features and systems. e.g., we do a lot of work in the background, and the UI is generally as fast as Picasa 1, which did a lot less simultaneous work.

You should do performance regression tests with your app. In many ways, changes in top-line performance give you more insight than lower-level testing can. Done well, you can identify a particular changelist that caused a slowdown.

Making good tests like these, however, is very hard, and kind of ill-defined. For instance, Picasa shipped a couple versions with its image prefetcher totally broken (which makes everything feel slower), but since it only works in some circumstances anyway, nobody noticed. There wasn't a good test for it, and there still isn't.

But my advice is to measure your app's speed wherever you can, and pay attention to changes. You will find more bugs, too.

Bill and Steve

Bill and Steve meet on-stage at D, first time in......awhile.

Video of the event can be found here.

spam filtering

I've given up on my old spam-prevention system of (a) graylisting, (b) spamassassin, and (c) procmail. It was getting too hairy, and Lorna and I were both getting 20+ spams per day even after tuning all the Bayesian filters. So what to do?

It turns out that pobox.com (my longtime mail forwarder) has recently added Cloudmark support. Why is this good? Well, Cloudmark has worked fine if you're an Outlook user, or if you're a corporate user with a big domain, but it's not been so easy for the sort-of savvy single user. Pobox has been great at leading SPF and other efforts, but they haven't been 100% at stopping spam.

Pobox also recently introduced their "AllMail" feature, so you can point a whole domain at them. Now I'm able to forward all my mail through Cloudmark's spam filter, and it works so incredibly well.

IDEA - The International Dialects Of English Archive

This is really quite addicting, and if you click on it you will spend at least a few minutes listening:
IDEA - The International Dialects Of English Archive

Some observations on the thumbprint debacle

After Lorna's story was on ABC, NBC, and some local newspapers, I was starting to think about the ways people talk about privacy and security.

Some of the approaches are...funny, and others are just human nature.

Someone important told me so: If someone important says so, you tend to believe them. They are clearly important and looking out for your interests. Alternately, the Orwellian form: "This is really far above me." This was actually said to us at the dealership, and not much other information was available.

Someone with good intentions told me so: If someone who's earnest about protecting your identity is trying to do so, then they must be doing the right thing.

The problem with these sorts of things is:
1. They are the same things that got us into Iraq.
2. The people with good intentions and gray hair are often not sophisticated about information technologies.

#2 is an important point. The problem is that someone with good intentions who runs a large police organization, or who owns a billion-dollar automobile dealer network, may not be a person who understands the idea that concentrated quantities of data represent a threat to personal privacy.

People who understand these things are those who think about these things professionally. Neither Lorna and I are those sorts of people, but we know and interact with them, and we've seen them be right (when we thought they were nuts) on numerous occasions.

Technologies and centralization of information are both two-edged swords, and it is often unclear to the casual observer why exactly good intentions do not lead to good outcomes.

I think we still feel that collecting all the personal information about "people who buy BMWs" (a generally quite creditworthy bunch), including biometric data and place of employment, in a stack of file cabinets remains a problem.

Then again, I bought an Audi, and they didn't fingerprint me.

The Marriage Discount

My auto insurance company gave me $170 for getting married. Nice wedding gift, really. You are apparently a better driver just for having a wife.

So, quite self-consciously, Lorna has taken it upon herself to earn this amount.

"Don't get a speeding ticket."
"You should come to a complete stop here."
"See the cop hiding behind the gravel pile?"

Dell 600SC server case-swap (almost a minor victory)

A few years ago, I collected a bunch of basic Dell servers (because they were almost free). Stacked them full of disks and have been using them since. Of course, like most machines with moving parts, the power supplies and fans start failing after awhile (taking your whole server along with them). I'm too cheap to replace them with $1000+ servers that use the same amount of power. Of course, you can buy a new server that uses twice as much power for less than that.

The problem with basic Dell servers (like the 600SC) is that they have proprietary fans, which are very expensive to replace. The 600SC's motherboard won't boot unattended unless you plug these fans in.

So as a compromise, I've bought some Antec Sonata cases and plugged in the old Dell parts, and they work, at 1/4 the noise level. I can't do automatic reboots (have to hit a key) but that happens only once every 6 months anyway.

One of the challenging bits: on my most recent attempt, I learned that the 600SC's motherboard has a proprietary heatsink for the CPU. The motherboard tray has special holes for just this heatsink. So what to do?

It turns out that you can take some motherboard risers and snip the screws off the bottom (Lorna took a class involving metalworking, so we have all this equipment). Once you do that, it's easy to attach the heatsink. Remove the peripheral cutout, and things are working again.

No fingerprints? No car.

Lorna and I tried to buy a car. We had the price and trade-in negotiated, and were all ready to finish the paperwork.

But they wouldn't sell the car to us, unless we gave them fingerprints. Read Lorna's telling of it for more details.

Not wanting to leave our data on file for 7 years, we left.

Power efficiency at a premium

One of the servers in my house has gone flaky. I suspect the (embedded) disk controller.

So I've been looking for a replacement, and thought, I'll try again to find something power-efficient, for the box that sits in the closet with 4 disks and doesn't do much. I have an old 900MHz box that does this nicely, now.

Well, you find out that Intel in particular wants to make power-efficiency a premium product. Let's look at pricing:

Intel Celeron 335 (85W TDP, 2.8GHz): $60

Server Chips:
Intel 5110 (65W TDP, 1.6GHz): $257
Intel 5140 (65W TDP, 2.33GHz): $518
Intel 5148 (40W TDP, 2.33GHz): $608

So if all you want is a little 1GHz processor to sit in a closet, Intel makes you pay $600 to save 25W of power. Compared to their 1.6GHz model or their celeron, it takes more than 10 years to recoup the extra cost.

How can anyone afford to use these things?

On the other hand, Via's C7 uses 20W and doesn't cost much. But it is really amazingly hard to find these things in a box that you can plug lots of disks into.

Anyone have a link to help out?

Are you sure you want to read this blog post?

I was noticing a couple weeks ago that the advent of Vista (and Apple's wonderful ads poking fun at it) make a very interesting topic of discussion.

Namely, when is it actually useful to say "Are you sure you want to...?"

I believe the answer to this is much closer to "never" than "whenever somebody gets lazy." I mean this in two ways.

First, I think undo (and clear, relevant undo) is almost always the right alternative to a confirmation. Installing a program that looks dangerous? Put it in a virtual machine, don't ask. (Instead of picking a solid technical solution, Microsoft's actually outlawed running Vista in a VM at all.)

Gmail wins a gold star here, since after you delete a message, you get a yellow-but-unobtrusive notification at the top of the screen offering to undo your action. You don't even have to know an obscure keyboard combination like Ctrl-Z to undo. I want to see more of this and fewer popup "dialog" boxes.

But why are confirmations bad? Well for two reasons: first, they interrupt flow and interaction. For apps that are good enough to encourage these things, dialog boxes are an awful interruption. Secondly? Because nobody reads them, and so the default behavior gets chosen most of the time. And a third reason as well: because they often involve limitations in the software that are due to laziness. ("This is broken. Are you sure you want to do it?")

We've let this disease creep into Picasa a bit, and I intend to fix it wherever we can.