I was going to favor you all with a post about Java’s System.nanoTime. That post will have to wait until tomorrow. Instead, I spent the day (arguably the weekend since 3:15pm on Friday) putting in a bid on a house. I won’t bore you with the details of property, inspections, financing, etc. However, I think the details of the bidding process are quite interesting.

To quote a friend of mine, when asked how we much we should bid on the house:

In a first-price auction, there’s no dominant strategy. However, by the Law of Revenue Equivalence, the seller will, on average, get the second-highest valuation of all the bidders. So, if you think you value the house more than everyone else, all you have to do is guess what the next-best buyer would be willing to pay for it, and bid slightly more than that to win.

Yes, well, that is entirely correct, but unfortunately unhelpful. We are dealing with a non-repeating negotation (so “on average” doesn’t apply). And it’s remarkably unclear that the auction will be run according to any rules at all. Predicting the behavior of the seller and the sellers agent is quite challenging. On Saturday at brunch a different friend recommended The Strategy of Conflict by Thomas Schelling, from the era of game theory research that brought us such gems as “mutually assured destruction.” Unfortunately there wasn’t time to read it.

Obviously (obvious to anyone who hangs around certain kinds of mathematicians) the right thing is to have a Vickrey auction, where the top bidder pays the price of the second highest bid. But this is far from obvious to realtors. They treat making an offer as a very expensive operation. And counteroffers from the seller seem to be very uncommon. There is a lot of concern about “offending” or missing out on an offer. I’m not sure why. If someone wants to buy your house on Monday for $x, they probably still want to buy it on Wednesday. Unless maybe their Realtor is reading something into the delay.

One is left wondering if the world would converge on more optimal auction structure without real estate agents muddying the waters. Or if, as eBay has demonstrated, people would rather keep working in an easy to understand system over an optimal one. Unlike eBay, the current system is quite complicated, with many conventions and few rules. In the age of Redfin, Realtors have an obvious interest in preserving the status quo, since understanding the rules is the only thing they have left. In the past, they at least had priority access to listings and historical sale data. Now they are left understanding the negotiating process.

In the end we offered $410k for the house. There were 5 offers, three of them at a similar price point to ours, $10k over asking. There was one offer at $430k, so the sellers decided to accept that offer, rather than encouraging further bidding. Case closed, transaction completed, Realtor happy. Money might have been left on the table, but getting it would have required both work and risk on the part of the agent.

Researchers at the MIT OpenWetWare project are attempting to engineer Synthetic Biology, creating reusable and composable biological components that can be combined to create useful organisms. In the process, they are discovering that biological systems don’t follow the same patterns of good architecture familiar to us from software.

In software engineering, architecture is perceived as critical to the success of a large implementation project, and also to the ongoing maintenance of the code created. Since software is very expensive, there is a lot of focus on architecture, choosing the right architecture, and making sure that the architecture is faithfully executed. Some of the biggest changes in software in the last 30 years, like object oriented programming and service oriented architecture, have come about because of a need for clearer architecture in ever larger collections of software that run modern life.

Architecture analysis also extends to describing anti-patterns, those things which do not work and are to be avoided. Probably the most famous anti-pattern is the Big Ball of Mud. A big ball of mud is what you get when software has evolved for many years without any clear architecture, where all abstraction barriers and divisions of responsibility have eroded in the interest of expediency and incremental functionality. The interesting thing about big balls of mud is that as a rule they work, and they are remarkably common. It can be very difficult to maintain them, almost maddening. But as long as they are economically valuable enough to justify their care and feeding, they tend to persist.

What people fail to realize about big balls of mud is that they represent a certain kind of efficiency. Maybe not efficiency from a top down, best way to solve the problem kind of approach. But every change is efficient in its own way. Engineers, either fearful of breaking the system or just lazy, make the smallest possible modifications, or the ones they are best able to understand. Abstractions are violated, variables and identifiers are reused, values are overloaded. All of these changes represent efficiently as much as they represent “bad” software engineering.

Biological systems follow the same pattern. Because of the pressures of evolution, they are filled with abstraction violations, repurposed functionality, and tight coupling. The mechanics of genetics and evolution drive change, and generally result in the smallest possible sufficient change. Tight coupling leads to efficiency and reuse. Like a big ball of mud in software, the system is difficult to understand by decomposing it into parts. Like these software systems, complex biological systems are filled with shortcuts that work most of the time, implementation details that blossom into major behaviors.

Read Montague covers this in his recent book Your Brain is (Almost) Perfect: How We Make Decisions. The original title was the clever Why Choose This Book (bringing to mind Abbie Hoffman’s Steal This Book). While most of the narrative focused on decision making in the face of limited information, the overriding principle that Montague argues from is that biological systems favor efficiency above all else. He argues that to make more efficient computers, they will need to emulate both the frailties and the strengths of biological systems.

As a student of programming languages and programming methodology, I’m intrigued by the potential for developing software systems that are highly efficient due to their high degree of coupling. The closest thing currently available is whole program analysis like the Haskell Jhc compiler or the GCC Link Time Optimizer. However, while both of these systems consider the whole program for optimization, neither is likely to produce a highly coupled or minimal program. For that the state of the art is the superoptimizer, either the original superoptimizer from 1987 or more recent attempts like TOAST. In a superoptimizer, the entire space of potential programs is searched to find the shortest implementation of a given function. This can be very helpful in core tight loops, but exhaustive search is only helpful for very simple functions. None of these compare to the results of millions of years of evolution.

But what if we had something comparable to millions of years of evolution, but for software? For example, if we had nigh-infinite computational power available inexpensively by using cloud servers in off hours, how could we take advantage of it. To me, the interesting question is not how to build an evolution machine, but rather how to constrain it so that the result is a program you find useful.

In biology and bioengineering, the approach is called forced evolution. There are a variety of techniques, but the one I’m familiar with works for cases where you want to produce chemical X from source chemical Y. First, a bacteria is engineered by any means necessary that has a biological pathway that can survive by producing X from Y, however inefficiently. Next, all other ways for the bacteria to survive are knocked out, by disabling the genes that make those pathways work. Finally, the organism is left to reproduce and evolve in a Y-rich environment. Hopeful those organisms which best optimize the Y->X pathway are the ones that reproduce more and come to dominate in this environment. The result should be a bacteria much more efficient than could have been designed from scratch, at least using current bioengineering.

Can we use forced evolution to build better software? I think this breaks down into two parts. First, can we make this work? The place where evolution of simple bacteria has the advantage is in parallel computation. Each instance of the bacteria not only has its own variant of the software but also implements its own instance of the hardware to run it. Right now computational resources, even for simple compute jobs, are still many orders of magnitude more expensive than biological resources. That said, they are falling fast. 1 minute of compute on EC2 is fourteen-hundredths of a cent, the spot price, for low-priority computation, is a third of that, and the price of a fixed amount of computation is falling steadily. This kind of workload is quite happy to take advantage of modern parallel processors. Force evolution of computational processes might be economical before we know it.

The second questions is, assuming all that works, would we want the software it produced? Today, scientists are spending vast resources trying to understand the wetware developed by natural evolution, The worst software systems are quite simple in comparison. I would expect software created by evolution to be quite opaque. More worryingly, it might be sensitive to various characteristics of the machines or environment in which it evolved. The software would likely contain dead code, unexercised race conditions, unprotected parallel data access, and many other artifacts of unrestrained expedient modifications. A simple unit test suite, even with perfect coverage, would not be able to catch all these issues. We would need a stricter environment, a set of limitations on the solution space or tests for the result that would cull badly behaved implementations, rather than allowing them to take over.

If we could figure out how to control the correctness and environmental sensitivity of evolved software, then we could also control it for designed software. Given that most designed software rapidly trends towards big ball of mud, the most immediate benefit of any work in this area might not be controlling pseudo-biological processes, but in controlling the human driven processes, keeping them from getting out of hand.

Riding the Acela to New York yesterday, I had my first opportunity to try out the new WiFi service. I’m glad to see Acela moving into the 21st century and joining the ranks of BoltBus and LimoLiner by offering WiFi on trips to New York. It’s been a long time coming, and now that it is here I was looking forward to having good bandwidth through the swamps of Connecticut, rather than depending on my fickle EVDO card.

Unfortunately the experience was less than wonderful. Latency was about double that of EVDO, averaging 450 milliseconds with spikes to 2-3 seconds. That meant that ssh connections were difficult to type across and web browsing had a distinctly 20th century feel to it. I wasn’t able to analyze throughput because I couldn’t get most of my web-based tools to load. Suffice to say throughput was disappointing.

I did some tracerouting and analysis, and I think a lot of the problems are in the first hop. First hop latency averaged 200 milliseconds. I’m pretty sure that first hope was on the train, and means that the local 802.11 network is overloaded. I wonder what level of provisioning they planned for. Looking around on Acela it seems like well over 50% of passengers are using laptops, which is a lot of laptops together in a thin metal tube.

The second hop hits a variety of different IPs, which might relate to some kind of multiplexed EVDO connection. These are internal non-routable IPs. The first public IP comes at the third hop, and is a router on HopOne.net in their Washington, DC area data center. I suspect the second half of the bad latency comes in this WWAN connection and the routing of the messages to DC. I’m not sure how it could be done better, but one imagines it could route directly to one of the national wireless networks. The MBTA commuter rail does this with AT&T, as I understand it.

So overall, I’m glad Amtrak has implemented WiFi, and now that it’s here I hope they improve it to make it usable. I fear they will just start charging to cut down on the overload. But it would be better for the world if they do not, and simply socialize the cost over all passengers. It won’t be long before 100% of passengers have some kind of WiFi device.

It’s been a few weeks since I posted, partly because of a vacation spent in Puerto Rico. I have a few posts in the works, but before I get to those, I hope you can indulge me in a bit of travelogue.

It started with a quest. On our way to Arecibo we had seen this strange structure off in the distance, and been unable to identify what it might be. Even when we got up close, it was unclear what was going on. The possibly-associated giant stone cross only increased our curiosity.

Looking at it in Google maps we were able to identify it as part of Space Rocket Plaza, which turns out to be part of Parque de las Ciencias. Some kind of science museum in suburban San Juan? That sounds like a good combination of local culture and nerd tourism, just right for Aletta and I. And maybe there will be baby oriented things for Patrick.

When we got there, the entire facility was bizarrely deserted. We arrived 45 minutes after the park opened, and as far as we could tell we were the only guests. The parking lot was empty and there was no one around. The first three facilities we went to (planetarium, railroads, and something else) were closed for repairs. The only people we saw were involved in cleaning and maintenance of the park, mostly powerwash. As we walked further and further in we became more convinced that the park was closed or somehow shut down.

The zoo didn’t seem to be entirely empty, but was kind of strange. I don’t know what kind of zoo puts deer, peacock, and chickens in the same cage. The selection of animals was at best strange. Little did we know that it was only getting started.

The first indoor museum that was actually open turned out to be the collection of some local big game hunter. Like the zoo, there was little to no information about what we were looking at.

The most bizarre part of the park was what initially appeared to be a model town. However, it was really unclear what it was trying to model. To make the puzzle more challenging, many of the buildings had evidently had their artifacts removed.

Others contained the most bizarre displays:

Eventually we realized this “town” was a kind of museum of classic Puerto Rican television comedy. Coming in with no cultural awareness, it was definitely quite weird. I would have been interested to learn more, but of course there was no signage in English or Spanish.

The pinnacle of our Parque de las Ciencias experience was the Museo del Telefono

This museum seems to be the result of a compulsive collector who was forced to clear out his garage after some kind of family intervention. There are piles of telephone equipment, from every vintage and at every level of repair.

None of it carries any information. For example, here is a lovely pile of mobile phones. The only sign? “No Tocar” (do not touch).

Imagine the thrill of finding the first descriptive sign in English in the whole park, here in the telephone museum!

Unfortunately the sign was sitting on top of this machine, which I can only hope is so much more than a touch tone phone:

Really, that was the telephone museum. And the whole park went like this. The transportation museum, which was a barn full of old cars (and one steam engine and one lunar lander). The archeological museum, which was a random assortment of mostly undocumented bones and bits of pottery. The aero/astro museum, which was a collection of posters from space and telescope magazine, an assortment of NASA paraphernalia, and a collection of model spaceships, some real, some fictional. There are photos, but you get the idea. Actually, there is one I have to share, from a sizable anex to the air and space museum:

Yes, completing the experience of a whole series of museums that could have been eclectic personal collections, here we have the section of the air and space museum dedicated to stamp collecting.

One bright spot was the art museum. The signage and interpretation was still nonexistant, but the museum contained some quality art by mostly Puerto Rican artists, and it was nicely put together. Of course, no comparison to Museo de Arte de Puerto Rico, which we visited later in the trip.

As for Space Rocket Plaza, well, they did have some legitimate space rockets. Looks like leftovers from early NASA. Of course, in keeping with the rest of the facility, no signs or details to let me know the history of these pieces. But hey, they are rockets.

Of course the flight simulator is out of service, as it apparently has been for quite a while according to internet reviews. And the observation deck that originally attracted us to the park? Well, the road up to it from inside the park was closed. That left the elevator, on the other side of the parking lot. On our way towards its base we encountered a motley crew of park employees. None of the uniformed ticket takers or guides would admit to understanding our question about access, but one of the workmen with them offered to interpret. The question and it’s reponse was more challenging than I would have expected. Eventually we got “It’s closed” … “It’s closed, like for a wedding.” Alright, I suppose. Though 10am on a Wednesday seemed somewhat unlikely. Will it be open tomorrow, we asked. This lead to another spate of discussion, where our interpreter seemed as confused as we. “No, it is not open to public, permanently,” he eventually related.

On Tuesday January 5 Google announced the Nexus One smart phone. On Thursday January 7, my Nexus One arrived.

For context, I’ve historically been a BlackBerry user, but have been steadily driven away by the browser experience. My wife was a zero-day iPhone adopter, and I’ve spent a lot of time using an iPhone. I also own an iPod Touch which I carry every day and use regularly as a gaming/apps/media platform.

I’ve had the Nexus One for ten days, and here are my thoughts after that period:

The Negative

Less Polished than iPhone – The first and most noticable negative thing about the Nexus One is that the hardware and software are not as polished as the iPhone. It often takes two or three tries to unlock the screen, which uses a similar-to-iPhone slide-to-unlock interface. I’m not sure what is wrong with me or it, but the iPhone doesn’t have this problem.

Many of the core apps suffer from questionable UI as well. The Email and Gmail applications, for example, are very different. Not just their color scheme, but also different placement of reply/reply all, delete buttons, next/prev message, and other things. The Gmail application strangely puts delete front and center, despite delete not being a major part of Gmail usage.

Scratched Screen – Speaking of polish, after 10 days in my left pocket, side by side with my iPod Touch, the Nexus One screen has 3 small scratches. The iPod has been in that pocket 5 months, and has no scratches. Previously it was carried next to a BlackBerry Bold. I think it is a safe conclusion that the N1 screen is more scratch-prone, which is sad. I may have to look into screen protectors.

App Store is Seedier – One of the best things about Android is that the app store is much more open. As I understand it, apps are permitted by default, and have to be explicitly removed due to complaints. The result is a lot of apps that look like they are just waiting to be removed for copyright violations and similar problems. The standards for apps are overall pretty low, with many of them barely working or with reviews that complain about crashes. By contrast, most things I’ve downloaded from the Apple App Store have been reasonably functional.

Wrong Number of Buttons – The phone includes 4 buttons below the screen, a standard for Android. They are Back, Menu, Home, and Search. Unfortunately, Back and Search are often problematic for usability. This is probably the biggest usability problem on the phone, and will be difficult to remedy in future versions due to backwards compatibility concerns.

The Back button has the same problem that the Escape button did on the Blackberry: It’s unclear what kind of “back” or “undo” operation it is going to do at any time. Sometimes it returns to the home screen. Sometimes it just makes the on screen keyboard hide. Sometimes it moves backwards in the application. Sometimes moving backwards means going up a hierarchy level (like in mail), sometimes it means changing things (like in the browser). The back button is under the control of the app, if the developer takes the time to implement it. But if they do not, or if they make bad choices, then it will do something unexpected. And this leads to users, myself included, being reluctant to use the back button except when there is no other choice. This slows down the learning curve on new applications. Onscreen back buttons, like the iPhone, mean that developers have to get them right, and that users are more likely to know what is going on. Most important, it means there isn’t a back button when there is nothing to go back to.

The Search button suffers from a similar challenge. Some apps override it, others do not. Some apps contribute content to global search, others do not. A lot of this is probably due to lax standards or poor user interface guidelines. A friend who has done some development for the platform says the guidelines are somewhat lacking. On the iPhone, of course, applications would not have a search button unless they implemented a search feature.

Customer Support is Challenging – As has been reported elsewhere Google didn’t really build out a true customer support function to support the Nexus One launch. I’ve personally run into that, because I incorrectly ordered the “locked” T-mobile phone rather than the unlocked phone I should have ordered. (For your information, the phone is not locked, I’ve used it with an AT&T SIM.) T-mobile staff have been very courteous and helpful, but the current state of things is that I need to pay Google a $350 fee to make up the difference in phone price. That’s not a problem, except I can’t contact anyone at Google who can deal with this issue. Compared to T-mobile phone support, they leave a lot to be desired. A phone number to call would be a good start, rather than all communication going through form-emails.

The Positive

Search Works Better – The search functionality, unsurprisingly, is quite well integrated with the phone. Global search has the DTRT nature. Not only does it automatically search many kinds of content on the phone, but it seemlessly goes out to google to fetch additional content. And because the phone knows your geographic location, the results are informed not just by your search terms but also by your location. The result has been a series of pleasant surprises.

Open Platform – The Nexus One is a fairly open platform. I haven’t rooted my phone yet, but even without that I’m able to install a terminal emulator and get a shell on the phone. I can also ssh elsewhere from that shell. The high resolution display makes the terminal fonts quite readable.

Developer Tools – The iPhone is programmed in Objective-C using proprietary Apple development tools. Much as I like Objective-C, I think it is fair to say it’s a dated language at this point. On Android, I get to use Java, Eclipse, and an android simulator that integrates with the Eclipse debugger and other tools. Unlike the iPhone these are modern tools, and the way they are put together is not unfamiliar.

Free Software Culture – The final positive comment I want to make is about free software culture. Android does a great job demonstrating the value of a platform like Android and how free software or open source software can contribute to that value. The open source culture is pervasive, from the core product to many of the apps. Open source apps are nearly unheard of on the iPhone. Not only is the source available for Android, but so is documentation on building and maintaining the software. And it goes further, to public bug tracking and patch submission processes that allow you to participate from anywhere in the world.

Conclusion

I have basically drunk the Android koolaid. I find the platform easier to develop for, and like having a platform that is more open to development. The iPhone is a challenging environment to write software for, and a challenging business model to bet on. On the other hand, the heterogenous hardware and loose control that Google/Android have established deliver an inferior user experience, at least for now.

It is my hope that the free software option, Android, will eventually catch up to traditional commercial development. The Nexus One is a good phone, but it hasn’t caught up to the iPhone yet. Since I like the platform, and there is already an iPhone in the house and a Touch in my pocket, I’m comfortable sticking with it. I hope we see more progress in the next few years, both on the core software and also on the code and culture of the apps store.

The MIT Mystery Hunt starts this Friday at noon, and I’ll be participating seriously for about my 10th year. In the hunt, teams solve a collection of puzzles to discover the location of a gold coin hidden somewhere on campus. The puzzles may be numerous (sometimes over 100), are generally provided without instructions (except when they are provided with painfully explicit instructions), and the overall structure of the hunt is also unknown at the start. Hunt is nearly always finished before Monday, but during the 60 hours starting Friday at noon, many highly capable teams, some with several dozen members, will try their hardest to solve some very challenging puzzles.

Project Euler is a neat website that presents a series of computer science problems suitable for students and non-students to practice the skill of writing algorithms to solve numerical puzzles. It’s a great way to learn a new programming language, or just to kill time in a mentally engaging way.

Two of the peculiarities of the MIT Mystery Hunt are that the puzzles are drawn from a wide range of domains, and that there are no restrictions on what resources can be brought to bear on a puzzle. The result is both puzzles that are explicitly about software (e.g. perl program cryptograms) as well as puzzles that are best solved by writing some kind of program. Many of my favorite puzzles over the years have come from this category. Some hunts have few, some hunts have many, but every year there is a call to write some kind of software solution to a puzzle.

The programming skills required to write puzzle solving programs in high pressure situations are different from those normally required to write software, and so it can be useful to practice them. I have collected and categorized here all of the software puzzles since the 2000 hunt. In most cases, I recommend attempting to solve the puzzle, knowing that software is likely the best way. But because the solutions are available, if you are stumped it can still be interesting to read the solution and attempt to duplicate it in software. In most cases the solution is linked from the puzzle page; where it is not I have provided a link. The categories here are presented from least elegant to most elegant, in my opinion. Feel free to jump around and do puzzles which you find attractive.

Just Decompile It

A useful trick is to decompile any java applet or flash thing that you are given in a puzzle. The answer might just be in a string constant, though more likely it will just give you a different puzzle to solve.

• Maze (2005)
• String Theory (2003)
• Gnireenigne Lab (2003) This reverse engineering puzzle is pretty challenging. Only one team solved it during the longest hunt on record.
• Cubology (2002) Unfortunately decompiling this one doesn’t really help, but what the hey. (answer)
• Twisty Little Passages (2008) Not quite decompilation, but pulling the whole maze down to your local machine is the best way to handle this puzzle.

MIT Computing

• Some Trolleys Named Lust (2006) The title clues Moira, the computer system that does configuration management for MIT Athena, which has command line utilities named after characters from A Streetcar Named Desire. This puzzle contains components which are no longer online, so you are limited to reading through the solution.

Mathematical Manipulation and Brute Force Enumeration

Many search problems can be solves on modern hardware with brute force enumeration, or maybe slightly smart enumeration.

• Bars of Soap (2005) Unfortunately the puzzle isn’t available, only the solution, though it still provides a useful programming exercise.
• Ginormous (2005) Prime factorization is always a fun thing to do with numbers.
• The Road Signs Of Unspeakable Chaos (2003)
• Mathophobia (2001) (answer)

Text Manipulation

Sometimes a program is the easiest way to do a bulk text manipulation. Particularly when you need to experiment with various transforms, or might need to do them repeatedly. This includes basically all cryptograms, which I am not including here, though software often comes in handy solving them.

• Blather (2007)
• Decode This (2006)
• Long Division (2006) Not so much text manipulation as diagram manipulation, but you can get the diagram as postscript, which makes it easy to extract the data. Doesn’t help you figuring out the algorithm, but it does make trying out variations easier.
• Shotgun Wedding (2005) Gene sequencing also comes up occasionally. There are some pretty simple text matching algorithms that turn out to be critical parts of that work.
• Lost (2004)
• Reminders World (2004)
• Whoa — I have a Migraine! (2003)
• Famous First Words (2002) (answer)
• Lions and Tigers and Bears (2000) My first attempt to solve a puzzle with software, this one wasn’t very successful, partly because of the challenge of getting the grid and the source data accurately input, and partly because of a slow algorithm. The fact that computers were notably slower in 2000 might have also been relevant. I think the most powerful machine available to me was an Ultra 10. In the end people doing it by hand finished first. (answer)

File Identification and Manipulation

Many puzzles require you to identify files, or to do interesting manipulations to entire files. Often both at the same time. Sometimes the files are programs written in other languages.

• Hyperextensions (2009)
• Surgical Files (2009) This puzzle triggered a programming language race, between Perl and Haskell. The race ended in a tie, but I learned some cool Haskell tricks from a teammate in the process.
• White Noise (2006) Being able to manipulate audio files with programs or tools is also important.
• Noise in the Air (2004) Knowing your off the shelf cryptography tools (ie, openssl) is sometimes helpful
• Two-Timer (2004)
• A Problem With Printing (2003) This is probably my favorite mystery hunt software puzzle. It’s written in the postscript language, which is a great language for puzzlers to know, and makes use of the peculiarities of that language.

Programming Language Identification and Cryptograms

Many puzzles come down to identifying obscure or not very obscure programming languages. One thinng to be on the lookout for is knitting notation, which can often look like a programming language. Of course, writing programs is often still more efficient than knitting an actual object. Adding complexity, often the programs you are given are cryptograms, or otherwise obfuscated.

• Tragedy (2008)
• Badness 10000 (2006) Unfortunately no longer online, but I like the structure. You can read the solution.
• Square Mess (2005) presents you with a machine language and a set of constraints on the notation used for a program in it.
• Who’s There (2004)
• Sixty Degrees of Separation (2004)
• What Do You Do With A Genteel Sailor (2004)
• Whoa — I Know Knitting! (2003)
• A Nugget of Wisdom (2002) (answer)
• Use of Gothicism Considered Harmful (2002) (answer)

Honorable Mention

Blue Steel (2006) You can try to solve, but you probably just want to read the solution. It will remind you not to think so hard sometimes.

[Edited 2010-01-11 to add Twisty Little Passages (2008). Feel free to add other missing puzzles in the comments.]

Nearly everyone who goes to work for a startup gets options, and the first question they ask is “how much are these options really worth?” When you are considering a job offer, particularly competitive job offers, it’s important to understand the value of the whole package. Putting a value on an option grant in a pre-IPO startup is quite challenging, and there are many opinions. I’d like to share the way I think about option valuation.

The Wrong Way

First, let’s start with the wrong way to value stock options. It goes something like this:

1. Wow, I’ve got 10,000 options with a strike price of $0.70
2. The stock price at the last round of investment was $2.50
3. My options are worth 10,000 * $1.80 = $18,000

What’s wrong with this? Several things. First, your options are for common stock, while the investors were buying preferred for their $2.50. If your company did the 409A valuation correctly, then the fair market value of what you have an option on is probably right around what the strike price is. For more on 409A and how strike prices are set, see Brad Feld’s posts on 409A.

Second, the terms of investment probably include some amount of participating preferred, dilution protection, and a variety of other complicated things which protect the people who put in the millions of dollars and paid for the lawyers. If you can get them, the details of these agreements are interesting. To understand them, you’ll probably want to read Brad Feld’s posts on term sheets.

In fact, if you are interested in the details of how startups are financed, you could do worse than just read everything at Feld Thoughts. But my assumption here is you just want to know whether Company A or Company B is making a better offer. So read on.

For a contrarian perspective, you can read Venture Hacks, which disagrees with me and says you should focus on share price. They also have a whole post on analyzing startup job offers. Further evidence there are many ways to think about this.

What Really Gives Your Options Value

If you aren’t a founder or an executive, your options are like lottery tickets. This is because there are three potential outcomes for a startup: a huge win, a weak sale, or total failure. Unsurprisingly, in total failure your options won’t be worth anything. Somewhat surprisingly, you are likely at a deep disadvantage in a weak sale.

All those terms of investment to protect the people who put in millions of dollars mean that they get the lions share of the proceeds. Generally they get their original investment back, and probably a hefty share of whatever is left over. What constitutes a weak sale varies by the terms, but it is probably anything up to three times the amount of money that has been invested. In such a sale even the money that is left over may be complicated with additional terms, like earn outs or management carve outs. In a weak sale, there isn’t enough cash to make everyone happy, so people are going to be counting the pennies and taking care of their own. If you are an engineer who was late to the party, your interests will probably not be protected.

So the only situation in which you will make out well is the big win. In a big win, like an IPO or a big flashy acquisition by a public company, there is plenty of money to make everyone happy. The VCs are having the kind of result they can tell all their friends about. If the term sheets were reasonable, then all of those preferential treatments are gone and everyone is treated equally according to the fraction of the company they own. Even the little guys like you will make out OK.

Because the big win is the only situation in which you make significant money, it’s the only one you need to think about when valuing your options.

The Information You Need

Focusing on the big win, there are three pieces of information you need:

1. What fraction of the company do you own?
2. How much will the company be worth if you win big?
3. How likely is the big win and how far off?

If you knew all these things, some simple multiplication and net present value analysis would tell you what your options are worth. So how do we get this information?

What Fraction of the Company do You Own?

Any option grant is going to tell you how many shares you get. But what is really important is how large a fraction of the company those shares represent. To figure that, you need to know is how many total shares have been approved for issue. The company should be willing to tell you this. Chris Dixon has a great post about this in The one number you should know about your equity grant. That post says it better than I could: you need to know the fraction, and the company must be willing to tell you.

How Much will the Company be Worth If You Win Big?

The second term in the equation is how much the big win is worth. There are a number of ways to look at this, all of them require doing some amount of homework. I recommend collecting a variety of answers, to get a distribution and a sense of what is going on.

The first technique is simply to ask your contacts at the firm how they are thinking about exits. You probably want to preface this with an acknowledgement that you know nothing is certain, and of course they are building a company for the long term and not looking for a quick flip. On the other hand, flipping is good, and this is probably your best opportunity to learn how the management team is thinking about it.

The second is to learn more about the investors. If the company has followed a traditional VC fundraising model, without any down rounds, then you can look at the total capital invested to estimate the expected big win return. In order to invest money, each of the VC partners had to justify the potential for the investment to return five to ten times as much money back in a successful exit. To learn more about the economics behind this, see Fred Wilson’s posts on Venture Fund Economics. You can assume the investors own 50-70% of the company unless you know otherwise. So if you multiply the invested capital by 10, you get a reasonable estimate of where they thing a big win would fall.

The third is to look at historical exits in your space. There are a number of resources here. The first is google. Since you are only interested in big wins, you can look at IPOs and impressive acquisitions. For IPOs, data is easily available. For acquisitions by public companies, you sometimes have to dig to 10-K filings. There are also reports published by organizations like Software Equity Group which can help you understand the merger and acquisition activity and economics.

One possible outcome of these three techniques is that you get wildly different answers. For example, the historical exits and the invested capital might not make sense, indicating the investors are deluded or expecting something improbable. Or the management teams expectations are out of line with historical activities. None of these measurements is accurate enough for a mismatch to be a deal breaker, but it might be something to look into.

How Likely is the Big Win?

The third term is how likely your big win is. If you read the post on venture fund economics, you’ll see that the investors hopefully think it is about 33% likely, or they did when they put money in. As a new employee joining a startup, you should come to your own conclusion here.

You also need to estimate how far off the win is. This is another place where just asking your contacts at the company can be informative. One thing to note is that it takes 7 years on average for a venture-backed company to mature. Of course, there is a lot of variance here.

What to Do With This Information

Given these values, you can calculate the value of your option grant. Multiply your percent ownership by the value of a big win, multiply the result by the likelihood of the win, and then discount by 5% for each year in the future.

For example, if you are being offered 0.1% of a company with a 30% chance of a $400 million exit in 4 years, your value would be:

0.1% × $400 million × 30% × (.95 ^ 4) = $96,000

Plugging in your own numbers should get you a helpful result. If you have a variety of estimates for the values (and you should), do multiple calculations, and get a sense for the variety of results and what impacts them.

I started this post shortly after bringing my first child, Patrick Tibbetts, home from Mount Auburn Hospital. Now he is nearly eight months old, and I am finally getting around to posting it. In the interim, I have shared this advice verbally with several friends. I’ll keep it short, just three pieces of advice that I wish we had known.

For those of you that don’t know, Mount Auburn Hospital is in Cambridge, near Harvard, and is the preferred full-service birth hospital in the Cambridge/Arlington/Somerville/Belmont area. Their Bain Birthing Center is very progressive for a hospital-based center. Unfortunately it is a bit dated, which comes from having adopted many of the now-trendy features of birthing centers (big labor and delivery rooms, wood floors, real furniture, bathtubs, etc) early.

1. For birth partners (e.g. me) my first recommendation is to wear the most comfortable shoes you own, with good socks, and bring extra socks. This applies no matter where you are giving birth. The process can take a long time, and you are going to be standing or squatting or walking around with your wife the whole time. Everyone will be helping her to find comfortable positions for her and the baby. Your comfort will be somewhat less than an afterthought. Changing your socks is a good way to make yourself feel better after you’ve been on your feet for 10 hours.
2. Order food early and often. The kitchen at Mount Auburn is great. And meals for not only the mother but also her partner are included with the room. The food is great and they are very flexible about when you order things. The only problem is that the kitchen is only open 7am to 6:30pm. You will be on some night-shifted schedule and the kitchen will close before you know it. The best way to deal is to order more food than you will likely require and hang onto it until you are hungry. This also means that if you transfer to the postpartum ward after 6:30pm you will be unable to get real food until the next morning (there are some limited snacks in the postpartum kitchen). So I also recommend that you program a local food delivery place into your phone ahead of time.
3. Bring an eye mask. As previously noted, you will be really tired and on some crazy not-sleep schedule when you transfer to the postpartum ward. Unlike labor and delivery, at Mount Auburn these rooms do not have blackout curtains. If you want to sleep during the day, a good sleep mask is a must.

Obviously the comfortable shoes advice applies regardless of where you are giving birth. The other two issues are more peculiar to Mount Auburn, and really related to limitations of their facilities. If anyone from Mount Auburn is reading, I would recommend that you look into installing blackout curtains in the postpartum ward, and that you consider having a volunteer prepare a book of takeout menus to make available when people transfer after the kitchen has closed. Keeping the kitchen open 24-hours would be ideal, but I can see how that might be prohibitive.

These are of course all minor inconveniences. I cannot recommend Mount Auburn enough. Dr. Beth Hardiman is amazing, as is Arianna Stein, the midwife she works with. I also recommend our doula, Cynthia Maloney. Everyone was very helpful, and the whole process went as smoothly as I could have hoped.

As I posted in December, there is legislation afoot to ban non-compete agreements in Massachusetts, and I support it. As momentum has picked up, more discussion has ensued. On July 22 the Boston Bar Association will host Freedom To Compete? A Symposium on Bills Affecting Employee Non-Compete Agreements, but for now the discussion is occuring online.

One frequent claim is that we who oppose non-competes are only doing it to emulate California. To whit, in the comment thread of Amrith Kumar’s post “In defense of employee non-compete agreements” he claims

I also have to agree with you that the only arguments that have been advanced in favour of eliminating the non-compete are the ones that as you point out amount to “CA doesn’t have it, and Google and Facebook are in CA”.

But that is far from the only argument. In fact, Amrith immediately goes on to link to a Boston Globe article that discusses the research of Matt Marx, a recent HBS PhD and now faculty member at the MIT Sloan School, who studied non-competes and found three compelling (to me) problems with them:

First, he looked at Michigan. During the decades of that state’s greatest economic growth, from 1915 to 1985, noncompete agreements were illegal. In 1985, the law changed – and Marx found that inventors were suddenly less likely to move from one company to another, and specialized inventors were much less likely to move. (I’d observe here that the last 25 years in Michigan have not been a good era to emulate.) Marx has also surveyed inventors in the speech recognition industry around the country and found that about 25 percent of those who were bound by noncompetes often took “occupational detours’’ into other technology sectors reluctantly, to avoid getting sued.

Finally, Marx’s research has found that employees bound by noncompetes tend to take jobs with large companies rather than small start-ups – in part because they believe that a larger company might be able to defend them against a potential lawsuit. (Also, as with the Conduit example, small companies are less likely to take a risk with employees covered by noncompetes.)

There seems to be a persistent desire by defenders of the status quo to tar all supporters of change as mere California fan-boys, desperately trying to emulate a state they envy. In fact, there are many compelling reasons to be opposed to non-competes, even for a state that favors more conservative technology startups like enterprise software and biotech.

My own argument comes in three parts, none of which mention Facebook:

1. Currently the system is broken – Individuals are prevented from taking jobs, they are required to sign agreements they do not understand which limit their future potential. For engineers, this starts with their first job out of school, if not before, and likely continues through their entire career. What little understanding they have of their rights comes from anecdotes and scaremongering from their peers and the occasional human resources representative.
2. Economics is insufficient to solve the problem – Employees do not generally have collective bargaining opportunities. While it is possible to avoid non-competes, it is difficult at best and likely career limiting. Employers, on the other hand, have little incentive to reduce their use of non-competes. They could be accused of acting outside the fiduciary interest of their investors, for example. And so we have the current stable situation, where everyone requires strict non-competes, whether they have any ability to or intention of enforcing them.
3. A middle-ground cannot be created with more complex legislation – One of the biggest problem with non-competes is their chilling effect. I only know one person who ever had a non-compete legally enforced and supported in court. But no startup, and few individuals, are interested in initiating a court battle over employment. It is too distracting, too costly, and all together too risky. Legislative complexity favors organizations with large sophisticated legal teams over individuals. Adding more complexity to the legislation cannot resolve the chilling effect. We need simple legislation that all employees can understand.

The only thing I look to California for is validation that the extreme position, basically banning all non-competition agreements, does not lead to some kind of entrepreneurial apocalypse. We can see rather that non-competes are a minor aspect of the regulatory environment, when it comes to venture funding and venture success.

I hope you agree that the current system is broken, that it is not going to be solved through laissez-faire economics, and that more complex legislation is not the answer. That is why I support legislation significantly restricting the use of non-competes, to the point where every employee will be able to know and exercise their right to compete with a former employer.

In my last post, I shared benchmark data for the web browser on the iPhone versus BlackBerry. My theory is that web browser performance is critically important for smartphone user experience. Furthermore, the BlackBerry seems to be embarrassingly inferior to the iPhone in this respect. This begs the question, how do other phones stack up.

Thanks to two friends, I have SunSpider JavaScript benchmark results for the G1 and for the Palm Pre. Based on the graphs here, it’s clear that the G1 and the Pre are both considerably better than the BlackBerry Bold. Specifically, the G1 is 9.6 times faster than the Bold, and the Pre is 15 times faster.

On the other hand, the G1 and the Pre both compare unfavorably to the iPhone 3GS. The G1 is 6 times slower, as can be seen from the graph that excludes the BlackBerry. The Pre is 3.7 times slower. Neither the Pre nor the G1 achieve the performance of the first-gen iPhone.

Knowing the Android/G1 performance also helps to answer if this is a Java versus Objective C issue. Both the BlackBerry and Android are Java-based phone systems. Java puts a bigger burden on the virtual machine implementor to be responsible for performance, and has a reputation for overall worse performance than more native languages like Objective C. The G1 demonstrates that RIM could be doing a lot better with the BlackBerry.

it is also worth noting that the SunSpider benchmark was developed by the WebKit development team, and WebKit is the basis for the iPhone browser. It is unsurprising that the iPhone does well on this benchmark, it is likely used as part of the development process. However, it is still the best general JavaScript benchmark available.

The main conclusion to be drawn here is that if you want a web browser in your pocket, the BlackBerry is right out. When it comes to deciding between iPhone, Android, and Pre, it is likely that things other than JavaScript performance will drive your decision.