Google’s Bid-for-placement Patent Settlement Cover-up

When Google acquired blogging startup Blogger in February 2003, nobody foresaw that two years later Google will earn the ignominious distinction of being one of the first corporations to fire an employee for blogging. In January of this year, Mark Jen a new Google hire was sent packing for a blogging offense. Mark Jen writes in his blog:

“I was terminated from google. either directly or indirectly, my blog was the reason. this came as a great shock to me because two days ago we had looked at my blog and removed all inappropriate content – the comments on financial performance and future products. for my next entries, I was very cognizant of my blogging content, making sure to stay away from these topics. I mean, as much as I like to be open and honest about communicating to users and customers, i’m not insubordinate. if I was told to shut down this blog, I would have.”

Mark Jen is justly irate about the harsh treatment. Google did not have a blogging policy at the time, and Mark did his best to comply with the wishes of his superiors. Furthermore, Mark Jen was not a high ranking Google manager with important information to disclose; he had only just started work at Google. If Google’s management wanted to avoid making an incidence of the Mark Jen case, it had plenty of options, but Google’s management willingly embraced bad PR and proceeded with a response disproportionate to the offense.

(Update: July 10, 2008
In retrospect, I feel I exercised bad judgement in connecting Mark Jen’s firing to Google’s cover-up of its patent settlement with Yahoo. In fact, this article as originally published in April 2005 did not contain any reference to Mark Jens’ firing, but I subsequently added the material. Mark Jen’s firing was suspicious and made no sense, and it may have been prompted by motives I outlined in this article; however, I have no evidence that the firing was linked to Google’s cover-up of its Yahoo deal.)

It turns out there was a very good reason for management’s bizarre behavior. At the time of Mark Jen’s dismissal, Google’s management was playing a game of deceit to mask an ugly but not so well-kept secret. Management wanted employees to keep their mouths shut and firing Mark Jen, a new hire, was a convenient way of conveying the message without ruffling many feathers.

Google’s ugly secret has quite a bit of history. The trouble started with Google’s push for profitability. Google owned excellent search engine indexing technology all along, but it lacked a business model to extract profits from search traffic. Google’s solution to the problem was the AdWords business model. The AdWords business model combines Google’s search technology, text ads, and an ad-placement mechanism that allows advertisers to bid for the placement of ads (the bid-for-placement mechanism).

The bid-for-placement mechanism is a very important component of the AdWords business model. In the absence of the bid-for-placement mechanism, ad pricing can at best be inefficient. The bid-for-placement mechanism frees up extensive resources that would otherwise be required to set ad prices, and it allows Google to charge ad sponsors in proportion to the value Google is delivering to the sponsors. Thus, from a profitability perspective, the bid-for-placement mechanism is as valuable as Google’s indexing technology. Unfortunately, Google did not own the rights to this important mechanism when it adopted the AdWords business model.

Overture Inc. a paid search specialist pioneered the bid-for-placement mechanism. In July 2001, the US patent office issued Overture a patent for the mechanism. Patent 6,269,361; also known as the ‘361 patent, essentially covered all AdWords like business models. Google needed access to the ‘361 patent in order to use AdWords, but it never managed to negotiate a licensing agreement with Overture. Consequently, in April 2002 Overture sued Google over patent infringement. Google was now operating with a loaded gun pointed to its head.

Overture started life as a paid listing search engine. The company was known as GoTo.com when it first began operations. Advertisers placed ads with GoTo.com and in response to queries the GoTo.com website produced a listing of ads ranked by the ad sponsors’ bids for the search keywords. The GoTo.com website never made it big, and the company was forced to pitch the idea of bid-for-placement to outside search engines. The company even changed its name to Overture to better reflect its new business model.

Overture had a bit more success with this new business model. Under this new business model Overture signed up affiliates and managed their ad sales via its bid-for-placement system. Overture recognized the ad sales of its affiliates as revenue on its books and recorded the portion of ad sales that went to its affiliates as traffic acquisition costs.

The paid-search market took off in 2001, and Overture prospered in the rapidly growing market for a while. Overture earned $73 million on revenues of $667 million in 2002, but then a disturbing trend became apparent: Overture’s traffic acquisition costs started spiraling out of control. Overture’s traffic acquisition costs grew from 53 percent of revenue to over 62 percent of revenue in just the last three quarters of 2002.

Even after handing over 62 percent to affiliates, a 38 percent cut of ad sales for providing access to the bid-for-placement mechanism is hardly unimpressive, and reflects the revenue generating power of the bid-for-placement mechanism. Unfortunately, the 38 percent number was just an average, and not every affiliate was paying the same amount to Overture. Overture was increasingly growing dependent on fewer and fewer affiliates for more and more of its revenue. Overture’s smaller customers were in decline as advertisers were concentrating primarily on highly trafficked websites. Overture’s 2002 annual report reveals that Microsoft and Yahoo were responsible for 60 percent of Overture’s revenue that year. This dependency allowed the big affiliates to claim bigger and bigger chunks of ad sales as their share of the pie.

The ‘361 patent was certainly very valuable, but the patent had not been tested in court. If either Yahoo or Microsoft walked, Overture could expect major layoffs and a severely weakened bargaining position with the rest of its affiliates. Additionally, one big setback in court could end Overture’s game for good. Such risks implied a vulnerable market position, and pushed Overture’s management towards seeking a buyer for the company. A company with well-diversified sources of revenue was Overture’s best option. Such a company could handle setbacks in courts and bargain better with affiliates on account of its stronger finances.

Microsoft made a lot of sense as Microsoft was well-diversified and loaded with cash. There was some enthusiasm for acquiring Overture inside of Microsoft as well. According to Fortune Magazine, Chris Payne, a Microsoft manager, tried to convince Bill Gates to proceed with an Overture acquisition; however, Bill Gates did not see sufficient value in Overture and rejected the acquisition. Overture’s value lay in its patent portfolio, and Bill Gates must have miscalculated the strategic importance of Overture’s patent portfolio.

Yahoo was Overture’s backup choice and it too made a lot of sense. Yahoo handled more web-traffic than anyone else, and with Overture’s patent portfolio Yahoo could become what Overture wanted to be, but without the handicap of having to hand over vast chunks of revenue to affiliates.

Unlike Bill Gates, Yahoo was aware of Overture’s potential. Yahoo had always outsourced its search functionality to outside search engines. With Google gaining prominence and no new search contenders on the horizon, Yahoo was in a tight spot. Yahoo realized that to be competitive in the search engine arena, it needed access to Google’s intellectual property. Overture’s claim on the core of Google’s business model was just the bargaining chip Yahoo needed.

In July 2003 Yahoo acquired Overture in a mostly stock deal valued at $1.63 billion. This was an expensive deal as Yahoo’s stock was not flying very high at the time. Also, Overture did not have anything valuable apart from the ‘361 patent. Yahoo and Microsoft counted for the bulk of Overture’s revenue, and were it not for the ‘361 patent, Microsoft would have certainly walked. The deal was terrible news for Google as Yahoo was now in a position to cut a very tough bargain with Google.

Google and Yahoo settled the ‘361 patent dispute in August 2004. Google disclosed the settlement in an SEC filing just before its initial public offering (IPO). The relevant excerpt from Google’s SEC filing states:

Overture will dismiss its patent lawsuit against us and has granted us a fully-paid, perpetual license to the patent that was the subject of the lawsuit and several related patent applications held by Overture. The parties also mutually released any claims against each other concerning the warrant dispute. In connection with the settlement of these two disputes, we issued to Yahoo 2,700,000 shares of Class A common stock.

At the time of the patent settlement disclosure, 2.7 million shares of Google represented roughly 1 percent of the company. Google estimated that the shares were worth somewhere between $260 and $290 million. This estimate was based on Google’s proposed IPO price range of $108 to $135 a share, which was subsequently lowered to $85 a share. Interestingly, even the $290 million number does not represent any sort of adequate return on Yahoo’s $1.63 billion Overture investment. Yahoo was licensing critical patents to Google at a critical time for less than one fifth of what it paid to acquire them.

Interestingly, Google never paid anything even remotely close to $290 million for the patents. Google quite successfully managed to muddle up the math by jumbling together the numbers of the patent licensing settlement with the settlement of a separate second dispute with Yahoo.

In the second dispute, Yahoo claimed a warrant it held in connection with a June 2000 services agreement between the two companies entitled it to 3.7 million Google shares. Google had issued 1.2 million shares in June 2003 to settle Yahoo’s claims, but Yahoo wanted an additional 2.5 million shares.

Google’s 2004 annual report has the settlement value pinned down to $229.5 million, and it sheds some light on how much was paid for what. The section about the Yahoo settlement states:

In the year ended December 31, 2004, the Company [Google] recognized the $201.0 million non-recurring charge related to the settlement of the warrant dispute [with Yahoo] and other items. The non-cash charge associated with these shares was required because the shares were issued after the warrant was converted. The Company realized a related income tax benefit of $82.0 million. The Company also capitalized $28.5 million related to certain intangible assets obtained in this settlement.

In the IPO filing the focus was on the patent dispute, but here the emphasis is clearly on the non-recurring charge related to the warrant dispute and “other items”. Interestingly, the “other items” mentioned above do not include patent licenses (explanation follows), so out of the $228.5 million settlement $201 million had absolutely nothing to do with the patent settlement.

US corporations are required by law to follow generally accepted accounting principles (GAAP) put forth by the Financial Accounting Standards Board (FASB), and compliance to this requirement is assured by independent auditors. One fundamental component of GAAP is the matching principle. This principle requires revenues to be matched with the expenses it took to generate them, i.e., expenses relevant to the revenues reported are recognized in the same period as the revenues. Often matching expenses with revenue is not straightforward, and then the matching principle reduces to recognizing expenses when resources are utilized as opposed to when resources are paid-for or acquired.

For instance, if a corporation pays for a one year insurance contract at the start of its fiscal year, the corporation can not record the total cost of the insurance contract as an expense in its first quarter. The corporation will be availing of the insurance company’s services over one year, so the insurance expense has to be spread over that time frame. To accomplish this the corporation capitalizes the insurance contract, i.e., the corporation records the insurance contract as an asset, prepaid insurance, on its books. Afterwards, the corporation records insurance expense in four subsequent quarters to write-off the prepaid insurance asset.

A patent license is conceptually somewhat similar to an insurance contract. A typical patent license grants the licensee the right to use a patent for a number of years, and if the licensee prepays for the license then it makes sense to capitalize the cost of the license. In fact, GAAP requires prepaid patent licenses to be capitalized. Google too was required to capitalize the patent license it acquired from Yahoo and expense it over time. However, the $201 million one time charge was something that was not capitalized; therefore, it had no relevance to the patent licenses Google acquired.

A $201 million payment for the warrant dispute makes perfect sense as this amount represents 2.36 million Google shares which is fairly close to the 2.5 million shares Yahoo wanted. Yahoo had zero incentive to compromise on its demands with Google’s IPO so close, and Google’s financial statements clearly indicate that Yahoo got what it wanted. Google recorded the rest $28.5 million as intangible assets on its books. Patents are capitalized as intangible assets; therefore, $28.5 million is all Google paid for the patent licenses it acquired from Yahoo.

Yahoo was also a participant in the patent licensing transaction, and it too was required to report the transaction. Yahoo needed to recognize revenue and under GAAP revenue is reported in accordance with the revenue recognition principle. This principle requires revenue attributed to a product/service to be recognized in the same period in which the product/service was sold/rendered, regardless of the exchange of cash. Under this principle, prepayments for services are recorded as liabilities and revenue is recognized against these liabilities when the relevant services are rendered.

The patent licenses Google acquired counted as service agreements under GAAP. Google prepaid for the patent licenses, so Yahoo was required to report the prepayment as deferred revenue, a liability. Yahoo’s 2004 annual report states:

“The Company [Yahoo] agreed to dismiss the 361 patent lawsuits and has granted to Google a fully-paid license to the 361 patent as well as several related patent applications held by Overture. The Company allocated the 2.7 million shares between the two disputes, based on the relative fair values of the two disputes, including consideration of a valuation performed by a third party. A portion of the shares allocated to the patent dispute has been recorded as an adjustment to goodwill for the period that the patents were in effect prior to Overture’s acquisition by the Company. The portion of the shares received for the settlement of the patent dispute which has been allocated to future periods has been recorded in deferred revenue on the consolidated balance sheets and will be recognized as fees revenues over the remaining life of the patent, approximately 12 years.”

Yahoo divided the proceeds of patent licensing agreements amongst the goodwill and deferred revenue accounts. The twelve year remaining life of the patent mentioned in the annual report implies Yahoo allocated most of the proceeds from the licensing agreement to its deferred revenue account. Consequently, Yahoo’s deferred revenue account ought to show a big spike if the proceeds from the patent agreement were substantial.

Yahoo reported deferred revenue of $224 million, an increase of $11 million over the prior quarter, in its Q3 2004 (3rd quarter of fiscal 2004). This was the quarter in which the settlement took place, and a substantial increase in deferred revenue was anticipated. Yahoo’s deferred revenue was $192 million, $201 million, and $213 million in Q4 2003, Q1 2004, and Q2 2004, respectively. Considering these numbers, the $11 million increase in the Q3 2004 in no way represents a break from the obvious trend in Yahoo’s deferred revenue account. The patent settlement value has to be insubstantial as there is no spike in Yahoo’s deferred revenue.

Both Google and Yahoo’s financial statements indicate that the patent licensing portion of the $229.5 settlement was no bigger than $28.5 million. Spread over the life of the patent the licensing fees are paltry, and it is simply inconceivable how Yahoo agreed to license its billion dollar patents for such a ridiculous sum.

Patent litigation is extremely expensive and Yahoo must have spent a good chunk of $28.5 million on legal expenses by the time of the settlement. This suggests the $28.5 million covers Yahoo’s legal expenses associated with the patent litigation and does not represent any payment for patent licenses. Google compensated Yahoo for the patent licenses in some other way, and the company is not being forthright about the settlement terms.

Yahoo craved Google’s intellectual property, but the terms of the settlement make no mention of Yahoo licensing any of Google’s patents. Google could not expect to get away with hiding an IP licensing agreement with its biggest competitor; therefore, it is reasonable to assume that Yahoo did not get such an agreement. However, Yahoo had an indirect way of achieving access to Google’s intellectual property.

Google’s SEC filings mention a “fully-paid, perpetual license,” but they omit the word non-revocable. Patent license terms often include non-revocable in addition to perpetual. Perpetual seems to indicate non-revocability but it really does not. It is unreasonable to expect Google’s high-powered lawyers to miss the word non-revocable, so Google’s license to the ‘361 patent is revocable.

Now all that remains is the question of the terms which if violated cause Google’s patent license to become revocable. The only obvious term that makes sense was for Yahoo to have conditioned the revocability of Google’s patent license on Google’s not litigating against Yahoo. Such a condition puts Google on a leash, and effectively grants Yahoo the authority to use Google’s patents with complete immunity. Of course, there are other possibilities, but again there was no reason for Yahoo to settle for anything less than unhindered access to Google’s patent portfolio.

Settling on onerous terms with a competitor is not a crime, and Google did nothing wrong by settling with Yahoo. If Google had reported the transaction honestly there would be no problem at all, but Google didn’t do that.

US regulations require corporations to disclose all significant business risks to investors. Before the settlement, Overture’s patent litigation posed a threat to Google’s business and Google did disclose that. The settlement removed the risk of litigation but by giving away the company’s technical superiority it created a new risk. Google essentially traded one type of risk for another, and was bound to disclose the nature of the new risk. Google never did that, and in doing so ran afoul of US regulations.

Google’s patent settlement disclosure on August 9 2004 was immediately followed by an IPO auction on August 13. Typically, investors don’t care too much about pending patent litigation when investing in IPOs, but the timing of Google’s patent settlement suggests Google’s IPO was the motivation for the settlement and the ensuing cover-up.

US regulations prohibit companies from aggressively marketing their IPOs and compliance is assured by forcing companies into a quiet period. In the quiet period a company can disclose information about its business activities only via an SEC filing known as the company’s prospectus. The goal being to prevent unsound businesses from pitching themselves to investors. This results in a substantial handicap. Additionally, new businesses have the problem of being restricted to raising funds from retail investors (individuals who buy/sell securities for their personal account) on account of their limited contacts. Retail investors constitute a small portion of the trading activity in the stock market, and are only willing to invest small amounts in speculative ventures. To raise a billion dollar or more a company might need to sell its IPO shares to tens if not hundreds of thousands of retail investors which is impractical at best.

Fortunately, companies going for IPOs don’t have to worry about such problems; instead, they hire investment banks as underwriters and relegate these problems to investment bankers. Most of the big money in the stock market is controlled by institutional investors such as mutual funds, endowment funds, pension funds and hedge funds. Investment bankers deal with large institutional investors on an everyday basis and are able to market IPOs to such investors. In addition, they help companies price their IPOs by assessing demand and obtaining commitments from investors.

Investment bankers typically collect seven percent of IPO proceeds for their effort. Even better, investment bankers get to allocate IPO shares. As IPO shares are almost always underpriced and often experience a pop of 15 percent on the first day of trading, IPO allocation privileges are very valuable and enable investment bankers to handsomely reward their favored clients. This means the direct and indirect payoff to investment bankers totals around 20 percent of the value of IPO proceeds.

Google’s IPO was atypical. Instead of letting its investment bankers control its IPO, Google tried to price and allocate IPO shares by an auction. Additionally, Google’s investment bankers received only 2.8 percent of IPO proceeds instead of the usual 7 percent. Google’s IPO was a very bad deal for investment bankers, but that was not the end of it. Google’s IPO was the IPO event of 2004; the success of Google’s IPO auction would have turned the IPO underwriting business upside down. It would have caused a flood of companies to embrace IPO auctions, and in the process threatened the very livelihood of IPO underwriters. Consequently, Google’s investment bankers had powerful incentives to do their utmost best to sabotage Google’s IPO auction.

Google’s IPO auction turned out to be a complete rout. Towards the end of its IPO auction Google simply gave up and allowed its IPO underwriters to run the show like a traditional IPO and price its IPO offering. The company not only sold its IPO shares at $85 a share, well below the $108-$135 pricing range, but also reduced the number of shares it was planning to offer to 19.6 million from 25.7 million.

Google’s investment bankers had to play a balancing game; they needed to sabotage Google’s IPO auction but they also needed to preserve their credibility. This suggests, Google’s IPO underwriters discreetly high-lighted risks stated in Google’s prospectus to institutional investors. Google’s Overture troubles were mentioned in Google’s preliminary prospectus and constituted convenient ammunition. It must have been a straightforward job to hype Google’s patent litigation risks to institutional investors, and scare them into seeking assurances as to an amicable settlement with Yahoo and steep discounts on Google’s IPO auction pricing range.

Once the institutional investors became wary of Google’s patent troubles, Google had to settle and cover-up in order to proceed with its IPO. There was no other option. The investment bankers couldn’t have helped, as they couldn’t simply tell their clients that they exaggerated Google’s troubles and investing in Google was safe. Disclosure of the unfavorable terms was not a choice either, as that would have scared institutional investors even more.

Google’s choice of proceeding with its IPO was suicidal. The patent settlement cover-up was always going to be an open secret. Mark Jen’s wrongful termination suggests the details of the cover-up were widely known inside of Google, and Yahoo’s managers knew of the cover-up from the start.

Google’s future prospects are not good. By hiding risks from investors Google has exposed itself to shareholder lawsuits. Google can only hope that its stock doesn’t take a nosedive; otherwise, Google can expect shareholder lawsuit hell. Shareholders are going to claim Google intentionally hid potential risks, and they are going to be right about that.

US securities regulators are a much graver threat to Google. Google flouted US securities regulations right under the noses of SEC lawyers, and SEC lawyers are not going to find that amusing in the least. Google’s top management and its directors obviously knew about the cover-up, and regulators are not likely to want to miss a chance to fry some really big fish.

Interestingly, Google had no need to go through an IPO. Even before its IPO Google was profitable, and had access to all the capital it needed to expand operations. By simply staying private Google could have avoided the whole mess. Under this scenario, Google would have no obligation to disclose settlement terms. Even better it would have no incentive to rush the settlement in the first place. Google could have simply held-out for better terms. The pressure for an IPO was coming from the venture capitalists and employees. The VCs wanted to show impressive gains on their Google investments, and the employees wanted to cash out their stock options. Petty greed combined with extreme naivete and hubris seems to have led Google’s management on the path to ruin.


LAST UPDATED by Usman Latif  [May 31, 2005]


Updates:
9 March 2006: Edited for clarity
31 May 2005: This document has gone through a number of revisions, and the original version as well as an older revision to the original are also accessible.

What Microsoft Wants from Yahoo

Microsoft’s now retracted acquisition bid for Yahoo has been endlessly analysed in the media and myriad explanations have been offered for Microsoft’s interest in Yahoo. Analysts have generally assumed the obvious that Microsoft made the bid in order to acquire Yahoo. Yahoo CEO Jerry Yang, though, does not agree with this assumption. He has publicly claimed that Microsoft did not intend to acquire Yahoo. Some analysts have dismissed Jerry Yang’s claim as self-serving, but this can not be so. As part of ongoing shareholder litigation, Jerry Yang may need to defend this claim in a court of law and could not have made the claim lightly. Besides, there is plenty of evidence that supports Jerry Yang’s claim.

Microsoft’s $31 a share bid came just one day after Yahoo’s share price hit a four-and-a-half year low of $19.05. Yahoo shares closed at $31.36 on November 05, 2007; less than three months before the Microsoft bid. Yahoo had not reported a major downturn in its operations in the months leading to decline of the stock from above $30, and Yahoo’s share price exhibits considerable volatility. Share prices on a particular day are meaningless anyway as prices can move drastically even on the basis of insignificant trading volume. This suggests that Yahoo’s $19.18 a share closing price on January 31, 2008 was uncharacteristically low, and did not reflect a realistic valuation of Yahoo. Considering this the much touted 60 percent premium Microsoft offered over Yahoo’s closing price on January 31st appears to be mostly a well-planned and cleverly executed public relations coup.

The Microsoft bid never made sense from a business perspective either. Yahoo has always had stale search offerings, second rate search technology, and a mediocre unmotivated workforce. Yahoo derives its value primarily from the massive web-traffic the company controls, but the cost of controlling this web-traffic is likely to be prohibitive for Microsoft. In case of an acquisition, Microsoft needs to assimilate Yahoo’s 10,000 employee workforce into its corporate culture, and it is questionable if the “synergies” Microsoft is after outweigh the inefficiencies that will result from having to take on an army of sub-par and unmotivated employees.

Interestingly, Microsoft’s Yahoo bid does not make sense even after assuming a strong business case for a Microsoft Yahoo merger. Had Yahoo’s board accepted Microsoft’s $31 a share bid, the deal still could not have gone through because of antitrust issues. A Microsoft Yahoo merger is not a problem for anyone in search but it is a massive threat to Adobe Systems and its dominant rich internet application (RIA) development platform: Flash. Microsoft’s RIA platform, Microsoft Silverlight, competes directly against Flash and in the case Microsoft acquires Yahoo, Silverlight will get a hold over some of the web’s most popular websites and more than 50 percent of the webmail market. Consequently, any Microsoft attempt to acquire Yahoo is bound to be challenged by Adobe on antitrust grounds. More than that, because of Adobe’s legitimate concerns, Microsoft has to accommodate Adobe, which it can not do without divesting most of Yahoo’s valuable web-assets.

Evidently, Microsoft’s bid for Yahoo had no realistic chance of being successful. But why did Microsoft bid at all? Microsoft’s bid has to be an unconventional tactic for putting pressure on Yahoo, but to what end?

The precise nature of Microsoft’s interest in Yahoo has been clear for years. Even before Microsoft’s acquisition bid for Yahoo the two companies had been talking for years. Back in 2006, in an interview with New Yorker journalist Ken Auletta (video of interview no longer available), then Yahoo CEO Terry Semel publicly acknowledged that Microsoft and Yahoo were talking. In the interview Terry Semel said, “Microsoft taking over Yahoo — that conversation has never come up,” Terry continued, “[We discussed] search, and Microsoft co-owning some of our search. I will not sell a piece of search. It is like selling your right arm while keeping your left — it does not make any sense.”

The idea of a competitor co-owning Yahoo’s core business is extremely odd if not outright nonsensical, and Terry Semel rightly spurned Microsoft. However, Terry Semel did not stop at not wanting to sell anything to Microsoft, but made an astonishing remark that received extensive media coverage at that time. He said, “My impartial advice to Microsoft is that you have no chance. The search business has been formed.”

The above remark was all the more surprising as Yahoo was not even close to being dominant in the search market at the time. In fact, in the very same interview Terry Semel admits to Yahoo not even being in the search business just 2-3 years back. Terry Semel further credits Yahoo’s June 2003 acquisition of paid search specialist Overture Services in getting it into search. He says of the Overture Services acquisition, “Turns out we earned over $200 million that year (from Overture) and that was the start of search”

Yahoo’s Overture Services acquisition is the crucial link between Yahoo and Microsoft and is the key to understanding Terry Semel’s Microsoft comments. Yahoo’s Overture acquisition was not about search technology even though Overture owned the AltaVista and AllTheWeb search engines. By the time of the Overture acquisition, Yahoo already owned search technology via its acquisition of the Inktomi search engine in December 2002. Overture Services specialized in paid search. Overture Services’ 2002 annual report reads:

Overture Services, Inc. is the global leader in Pay-For-Performance search (also known as paid search) on the Internet. Overture’s search service is comprised of advertiser’s listings, which are screened for relevance and accessed by consumers and businesses through Overture’s affiliates, a network of Web properties that have integrated Overture’s search service into their sites or that direct user traffic to Overture’s own site. In some cases, consumers and businesses access our search listings directly at our site. The search listings are ranked by the advertisers’ bid; the higher the bid, the higher the ranking. Advertisers pay Overture the bid price for clicks on the advertisers’ search listing (also known as a paid introduction, click-through or a paid click).

The above reads like a description of the Google AdSense and AdWords paid-search solutions and it is. Google is generally credited with pioneering the paid-search text ad, but it was Overture that originally came up with the idea. Overture not only pioneered the paid search business model but it also managed to patent the core ideas behind paid-search. In July 2001, the US patent office granted Overture US patent number 6,269,361. Also known as the ‘361 patent, it covered the basic paid-search bid-for-placement advertising model. The ‘361 patent effectively granted Overture the right to monopolize the lucrative US paid-search market and subsequently dictated the evolution of the global paid-search market.

After getting the ‘361 patent, Overture wasted no time going after its paid-search competitors and quickly mobilized its lawyers to corner the paid-search market. Initially, Microsoft, Yahoo, and most of the other paid search players chose to license the ‘361 patent. However, Google and Miva (a small paid search operator formerly known as FindWhat) chose to challenge the patent in court, and subsequently got sued by Overture for patent infringement.

Google and Miva accused Overture of inequitable conduct in the filing of ‘361 patent. Inequitable conduct is a legal term that implies noncompliance with patent filing procedures or misdirection in the filing of the patent application. Google and Miva contended that Overture filed the patent application for ‘361 patent more than a year after releasing a product based on the ideas for which it was seeking patent protection. Under US patent law, companies have one year to file patent applications after they disclose their inventions, and Overture missed the one year window. Google and Miva effectively claimed that Overture lied to the US patent office in order to obtain the ‘361 patent.

Challenging the ‘361 patent made a lot of sense as Overture was demanding hefty fees for the patent’s use. Overture’s financial statements from 2002 indicate that the company on average retained 38 percent of ad revenue generated by its paid search ads at customer websites. Microsoft and Yahoo were two of Overture’s biggest customers in 2002 and were responsible for 60 percent of Overture’s revenue that year.

Overture reported sizable growth in 2002, but also started looking for a buyer. By that time, Google was taking over paid search via its in-house paid search solutions and Overture must have anticipated Yahoo and Microsoft bypassing it and rolling out paid-search solutions of their own. Overture did own ‘361 patent and could use it to block Yahoo and Microsoft but the patent was being challenged in court. Any setback in court would have devastated Overture, and on account of the questions surrounding the ‘361 patent filing, the company had good reasons to expect a less than favorable outcome in court.

Overture initially tried to market itself to Microsoft. There was enthusiasm for acquiring Overture inside of Microsoft too. According to Fortune magazine, Chris Payne, a Microsoft manager, wanted Bill Gates to go ahead with an Overture acquisition. The deal made sense for both companies. Overture needed to hedge against setbacks in court and Microsoft needed to get into paid-search. Surprisingly, Bill Gates rejected the deal. Bill Gates must have seen the Overture deal primarily as a patent play and realized that Microsoft could not afford to enforce the ‘361 patent because of antitrust issues. However, Microsoft needed the patent for itself too and this is where Bill Gates miscalculated.

With Microsoft out, Overture was practically driven into Yahoo’s arms. Terry Semel at Yahoo had no qualms about enforcing patents, so he was able to justify a higher valuation for Overture than Bill Gates. In July 2003 Yahoo acquired Overture in a mostly stock deal valued at $1.63 billion. The purchase price amounted to more than 8.5 percent of Yahoo’s valuation at that time, but from Terry Semel’s perspective this was a sweet bargain for a chance to control the paid search market and make Yahoo relevant again.

Yahoo’s Overture acquisition completely cornered Microsoft in the paid-search market. Microsoft had been licensing the ‘361 patent and in doing so it had admitted to the patent being valid. Microsoft could still challenge the patent in court but it did not have a good case. Yahoo now effectively dictated what Microsoft could and could not do in the paid-search market. Microsoft’s only hope was the challenge to the ‘361 patent by Google and Miva.

The subsequent resolution of the ‘361 patent litigation did not lead to a favorable change in Microsoft’s position. In a very shady deal just before its IPO (more on this ahead), Google chose to settle with Yahoo. Google claimed to have won royalty free use of Yahoo’s paid search patents for around $300 million in stock, but Google’s own financial statements contradict this and suggest that of the $300 million settlement only around $30 million was for settling Yahoo’s patent claims. The rest of the money was compensation for settling a completely separate dispute.

Miva, the other ‘361 patent litigant, persisted with the litigation, and the case eventually went to trial in April 2005. In May 2005, the case resulted in a mistrial after a jury failed to reach a verdict. The marketing portal ClickZ reports on the Yahoo Miva trial:

A jury was unable to reach a verdict after deliberating since Friday in the U.S. District Court trial in California. The jury did find that FindWhat [Miva] infringed on 18 claims within the patent held by Yahoo Search Marketing (formerly Overture). They also found that FindWhat had proven six of those claims invalid during the trial, but they were unable to reach a decision on the 12 other claims.

The ClickZ report continues:

Judge Cormac J. Carney has scheduled a hearing for June 24, 2005. At that time, he may rule on the issue of inequitable conduct, and he could potentially enter the parts of the jury’s verdict where a decision was reached into the record, though he is not required to do so. The judge will not have a set time limit to make his decision, but he has generally tried to keep the trial moving quickly.

The jury found invalid two of the main claims in the patent describing the overall method of selling bid-for-placement search ads. If the judge accepts the jury’s decisions on those two claims, FindWhat, and the industry in general, will score a big win. Most of the remaining issues relate to lesser issues that could force FindWhat and others to alter the way they do business without changing it completely.

The above seems to be a middling outcome for both sides, but this is not so. Judge Cormac was in a position to dismiss the major claims of ‘361 patent, and there were reports in the media that he was inclined to do just that. Additionally, Judge Cormac was reported as favoring Miva in the inequitable conduct dispute about the ‘361 patent. Yahoo could have appealed an unfavorable ruling but such a ruling would have been a massive setback nevertheless.

Inexplicably, Yahoo pushed the Miva patent litigation to trial and was itself responsible for the ensuing fiasco. After settling with Google, Yahoo had patent licensing deals with all significant paid-search operators, and there was no obvious rationale for going after, at best, a marginal player.

Unsurprisingly, with the threat of a potentially devastating setback just around the corner, Yahoo relented and settled with Miva. Miva ended up paying Yahoo $8 million in cash and undisclosed royalties. Again, inexplicably, Yahoo insisted on getting royalties from a marginal player when it allowed Google to use the ‘361 patent royalty free.

The Miva settlement is all the more interesting because it directly contradicts Google’s claims of having settled with Yahoo for $300 million in stock with no ongoing royalties. (The settlement amounted to roughly $30 million according to Google’s own financial statements.) Both companies’ business models depended on having access to ‘361 patent, but Miva’s was less dependent on account of its having acquired paid-search assets overseas where the ‘361 patent could not be enforced. More importantly, Miva settled from a position of strength as Yahoo could not afford to have major claims of the ‘361 patent dismissed, but Google settled from a position of weakness as its IPO was at stake when it settled. Even ignoring the massive competitive threat Google posed to Yahoo, Google’s settlement should have been at least two orders of magnitude bigger than Miva’s on account of Google’s size, growth potential, and weak bargaining position.

The Miva settlement consolidated Yahoo’s control over Microsoft’s paid-search business. Microsoft’s subsequent experience with its adCenter paid-search product outlines just how extreme and damaging Yahoo’s control over paid-search became. An article published in May 2006 by The Register says:

Microsoft is taking on the great Google Money Machine with an inhouse answer to Google Adwords.

Step forward Microsoft adCenter, launched yesterday to pump out all-paid search traffic on MSN and other Microsoft online properties in the US. Microsoft’s adCenter replaces Yahoo!’s Overture as the paid-for search engine on MSN. The only surprise is how long it took Microsoft to make the switcheroo — predicted ever since Yahoo! bought Overture in 2003 — and confirmed this time last year by Microsoft at its annual MSN Strategic Account Summit.

Microsoft adCenter is already running in Singapore and France and will trial in the UK with select advertisers in June.

The Register reporter is unclear as to the reason for Microsoft adCenter roll out delay, but there was an obvious reason for the delay: Yahoo refused to license the ‘361 patent to Microsoft on terms agreeable to Microsoft. Typically US companies launch their products first in the US and then elsewhere but due to Yahoo’s persistent stalling Microsoft launched adCenter outside the US first where the ‘361 patent is not enforceable.

Microsoft’s launch of adCenter in the US does not imply that it managed to buy its way out of Yahoo’s influence. In fact, it did not. Terry Semel’s “I will not sell a piece of search” and “My impartial advice to Microsoft is that you have no chance” comments came less than ten days after Microsoft adCenter’s US debut. The timing of Terry Semel’s comments unequivocally conveys the information that the Microsoft Yahoo negotiations Terry Semel talked about in the New Yorker interview concerned Microsoft adCenter. The comments further suggest that Microsoft failed to win any concessions in the negotiations and Microsoft’s paid search operations are severely handicapped because of Yahoo imposed restrictions and licensing fees.

The paid search situation for Microsoft has not changed since then. Microsoft is still chafing under Yahoo’s influence and is desperate for unfettered access to the ‘361 patent. It is quite possible that the size of the royalties Microsoft is paying to Yahoo are forcing Microsoft to neglect its paid search operations in order to minimize payments to Yahoo, and to minimize the size of an eventual settlement with Yahoo.

Microsoft has kept on negotiating with Yahoo since Terry Semel’s interview back in 2006, and details of talks between the two companies have emerged from time to time. The peculiar thing about Microsoft Yahoo negotiations is Microsoft’s insistence on owning/co-owning Yahoo’s paid-search assets. This is odd as Microsoft only needs access to Yahoo’s paid-search patent portfolio. Microsoft has not stopped eyeing Yahoo’s paid-search assets even after the withdrawl of its acquisition bid for Yahoo, and recently Microsoft proposed yet again to buy Yahoo’s paid-search assets. The latest proposed deal asked for Yahoo to accept a $8 billion stock investment and $1 billion in cash from Microsoft in exchange for Yahoo’s paid-search assets.

As previously discussed the idea of Yahoo letting a competitor control Yahoo’s paid-search operations is nonsensical. In the latest proposal, Microsoft is spinning the idea as being beneficial to Yahoo. Microsoft is claiming that Yahoo can improve returns for its search operations by selling and out-sourcing all its paid-search operations to Microsoft. This rationale holds absolutely no water. It is like Toyota wanting to takeover General Motors’s manufacturing in order to improve margins for General Motors. Microsoft’s rationale is even more incomprehensible as Toyota can be relied on to deliver gains for General Motors, but Microsoft is itself struggling in paid-search and can not possibly deliver any long term gains to Yahoo. The whole gains argument is a recent invention anyway, and can not explain why Microsoft has been trying to co-own Yahoo’s paid-search operations since even before its in-house paid-search infrastructure was operational.

Yahoo had little choice but to reject Microsoft’s terms. The money Microsoft offered may have been good in the short-term but it was questionable if Yahoo could have stayed independent after losing its search assets. Additionally, Yahoo managed to arrange a better deal with Google that does not involve Google co-owning/buying Yahoo’s paid-search assets and actually improves Yahoo’s paid-search monetization. Surprisingly, Microsoft instead of proposing a more competitive deal has been busy trying to subvert the Yahoo Google deal by raising antitrust concerns, and even seems to have succeeded at getting the US Department of Justice to investigate the Yahoo Google ad deal.

Microsoft is completely aware of the ludicrousness of its attempts to buy Yahoo’s paid-search assets and Microsoft’s earlier acquisition bid seems to have been an attempt to soften up Yahoo’s opposition to a paid-search asset acquisition. Microsoft’s publicized $31 a share bid was preceded by an unpublicized $40 a share bid in January of 2007. The initial $40 bid seems to have conveyed the message that if Yahoo refuses to let Microsoft co-own paid search, it can expect a public bid from Microsoft at some inopportune time, and consequent trouble from share-holders and corporate raiders. Yahoo responded to the threat by handing over the CEO job to Jerry Yang, a founder and a major shareholder, and attempting to shore up its share price by cost-cutting. Of course, this did not help and eventually Yahoo’s share price fell to a point where Microsoft felt that it could make a safe play for Yahoo’s paid search assets.

Microsoft’s $31 a share bid could not have gone through, so it was no surprise it got retracted. However, this was not the end of Microsoft’s play for Yahoo’s paid search assets. Microsoft seems to have waited for corporate raider Carl Icahn to buy into Yahoo before retracting its bid. Additionally, Microsoft disclosed the terms of its made-to-be-rejected $9 billion offer for Yahoo’s paid-search assets after Yahoo declined the offer. This particular action can only be interpreted as a thinly veiled invitation for corporate raiders to target Yahoo. The idea at Microsoft seems to be to dangle carrots in front of corporate raiders to get them to buy large chunks of Yahoo and force changes in the composition of Yahoo’s management. Microsoft is hoping that eventually the composition of Yahoo’s management will change enough that Microsoft will be able to push the paid-search asset acquisition deal it wants.

Interestingly, Yahoo’s refusal to sell paid-search assets is perfectly understandable, but its persistent refusal to license its paid-search portfolio to Microsoft is not. Microsoft is a distant third in the paid-search market, and it is not obvious why Yahoo doesn’t get Microsoft and the Microsoft sponsored corporate raiders off its back by licensing Microsoft the paid-search patents it needs. After all Microsoft only needs Yahoo’s paid-search portfolio and can do without Yahoo’s paid-search assets. Also, didn’t Yahoo grant its biggest competitor Google a royalty free license to its paid-search patents for a mere pittance?

Actually, Yahoo has gotten into a situation where it would be happy to license Microsoft the patents it wants, but it can not do that. Relenting on patent licensing terms is not an option for Yahoo. Remember Miva? Miva was the niche paid-search operator who almost prevailed in court but even then Yahoo insisted on collecting patent royalties from it. The reason for Yahoo’s obstinance with licensing terms is obvious: it can not give anyone a good patent licensing deal in isolation. Giving someone a good deal will trigger an escape clause in a lucrative patent licensing agreement with a big fish third-party, allowing that patent licensee the better terms as well.

Microsoft is perfectly aware of Yahoo’s constraints. Microsoft knows who the big fish is and understands that it cannot compensate Yahoo for the loss that would result from Yahoo giving Microsoft good paid-search patent licensing terms, so it is not even proposing to license Yahoo’s patents. Instead, it is proposing to buy/co-own Yahoo’s paid-search operations. The motivation behind such a convoluted structuring of what could have been a simple patent licensing agreement is to subvert escape clauses in Yahoo’s lucrative patent licensing with its big fish patent licensee.

There is another reason for structuring the deal that way. Microsoft believes that by being clever about the deal terms Microsoft can practically get Yahoo’s big fish patent licensee to fully reimburse Microsoft for whatever Microsoft pays for Yahoo’s paid search assets.

So, who is Yahoo’s big fish patent licensee, and why would it compensate Microsoft for buying Yahoo’s assets? There are only three major paid-search players: Yahoo, Microsoft, and Google. Clearly, the big fish is one of them, and it is not Yahoo. It can not be Microsoft either. By simple elimination it has to be Google. Google though claims to have obtained a perpetual royalty-free license to Yahoo’s paid-search patents for a one-time payment. Surely, Google can not be the big fish?

Google may have done a lot of things right but its paid-search patent settlement with Yahoo is not one of them. Too many fingers point to Google hiding a monster of a bad deal from the public. First, Google was evasive about its paid search patent settlement with Yahoo and tried to pass-off the impression that it paid $300 million in stock for licensing Yahoo’s paid-search patents; however, Google’s own financial statements contradict this and prove that Google only paid an unbelievable $30 million or so in stock for Yahoo’s patents. Second, Yahoo’s financial statements confirm that Google only paid around $30 million as payment for patent licenses. Third, even the $300 million Google says it paid for patent-licensing was too low in the context of the Miva settlement. Fourth, the control Yahoo exercised over Microsoft’s paid-search operations and Terry Semel’s comments clearly indicate that Yahoo did not grant a good patent licensing deal to anyone. Fifth, Microsoft is willing to spend billions to secure access to the very same patents that Google says it got for next to nothing.

Google does have a perpetual royalty-free license, but $30 million was not all Google paid for the license. Evidently, Google is hiding some material terms of its patent settlement with Yahoo from the general public and its investors. Google had a legal obligation to disclose anything material that was likely to influence its future business operations, but Google’s management subverted that obligation. It seems that the terms Google did not disclose were covered by a “grace period” of several years during which Google got free use of the patent, and escape clauses; so back in 2004, Google’s management under pressure of an imminent IPO convinced itself that the terms covered by the grace period were unlikely if ever to come into play even after the grace period ended, and so were immaterial and did not need to be disclosed. The thinking at Google must have been that either the ‘361 patent is not going to hold-up in court, or Miva is going to extract a good settlement out of Yahoo triggering escape clauses in the agreement, or somebody else is going to get a good deal out of Yahoo.

Google may have been helped in its decision not to disclose all the terms of the deal by Yahoo. Yahoo was patent trolling, and must have wanted to avoid scrutiny of its patent licensing deals. Additionally, Yahoo may have wanted to avoid disclosure of the escape clauses and the grace period in order to keep this information secret from its other patent licensees.

Yahoo may have had legitimate reasons for keeping the settlement terms secret but Google didn’t. Google’s rationale was just self-serving thinking: Yahoo had too much to lose in case the escape clauses triggered and it structured all its paid-search licensing deals to ensure that the escape clauses did not trigger.

The actual terms of the Google Yahoo patent settlement are largely academic now. Yahoo understands that there is no simple way for it to enforce the original terms of the agreement. If Yahoo tries to publicize or enforce the original terms of the agreement in order to get a share price boost, Google will flatly dispute owing anything to Yahoo. Admitting to all the material terms of the patent settlement with Yahoo is not an option for Google as this is tantamount to admitting to fraud. Instead, Google will prefer to assert that Yahoo is misinterpreting the terms of the patent settlement because of greed and desperation. Consequently, a flood of negative PR will get unleashed at Yahoo and the media will be happy to denounce Yahoo as a patent troll (which happens to be true). Additionally, this may result in renewed legal challenges to the ‘361 patent or a review of the patent by the patent office. Under such a scenario Yahoo will be forced to go to court in order to resolve the dispute, but courts move slowly and are unpredictable. Yahoo may manage to destroy Google by going to court but it is uncertain if it will recover anything substantial anytime soon.

The other option for Yahoo, which it seems to be pursuing, is to ask Google to quietly compensate it. Google can structure the compensation as an investment similar to the $9 billion deal Microsoft offered for Yahoo’s paid search assets. Basically, Google can acquire 20-30 percent of Yahoo at an inflated price as a “strategic investment”, and decline all voting rights to the stock in order to avoid antitrust scrutiny. Of course, after getting a generous enough compensation Yahoo will forget all about the problem licensing terms.

The problem for both Yahoo and Google is that Microsoft wants to force itself into the deal. Microsoft knows that it can block any compensation deal between Yahoo and Google by beating up the antitrust drum. Microsoft is using this as leverage to goad Yahoo into selling its paid-search assets. Essentially, Microsoft has conveyed to Yahoo that there can be no payday for Yahoo if Microsoft does not get Yahoo’s paid-search assets, but if Yahoo acts sensibly Microsoft can conveniently look the other way when Google comes knocking with the ransom.

Not only that, but Microsoft is actively positioning itself to benefit from any cash infusion from Google in Yahoo. The $9 billion deal Microsoft offered to Yahoo asked for Microsoft buying $8 billion in Yahoo stock at $35 a share. This amounts to 228.5 million shares of Yahoo. The $35 a share may seem like a good premium for Yahoo shares but it really isn’t for three reasons. First, the premium should be calculated with reference to the average price of Yahoo shares in the months preceding the Microsoft bid, and not the $19.18 closing price on January 31st, and this would raise the reference price to around $25. Second, after a cash infusion from Microsoft at $35 a share, Yahoo shares will become more valuable. Third, Yahoo’s share price does not reflect the value of Yahoo’s Google deal, but once Yahoo accepts Microsoft’s terms, the Google deal will become a certainty.

Now, if Microsoft manages to get such a deal from Yahoo, Yahoo’s share price will immediately pop to around $30. If Microsoft were to sell its Yahoo stake at this point (which won’t be possible) Microsoft will have effectively paid less than $2.5 billion for Yahoo’s search assets. This is an awesomely sweet deal by itself, but this is not all Microsoft will be getting.

The Microsoft deal will be quickly followed by rumors of Google acquiring a stake in Yahoo, and this will likely result in further upwards momentum for Yahoo’s stock. Eventually, once Yahoo’s stock has hit a suitable high of around $36-40, Google will come through with its “strategic investment” to “counterbalance” Microsoft’s influence at Yahoo. Google will likely buy around 25 percent of Yahoo at more than $50 a share, and this will raise Yahoo’s share price above $40. If at that point Microsoft chooses to exit Yahoo, it will realize a gain in excess of $1.14 billion on its 228.5 million Yahoo shares. So even if Microsoft in addition to its $8 billion stock investment pays Yahoo $1 billion for Yahoo’s search assets, overall it will come out ahead with a gain in excess of $140 million.

Microsoft is unlikely to exit Yahoo in order to make its gains concrete, but the above sequence of events is central to Microsoft’s strategy. Microsoft is counting on the huge gap that exists between Yahoo’s current valuation and Yahoo’s potential valuation if it sells its paid-search assets to Microsoft. Microsoft is hoping that by quietly advertising the gap in Yahoo’s valuation and the associated loot to be had, it can get corporate raiders and short-term profit seekers to flock to Yahoo and force Yahoo management’s hand.

So far Microsoft has only had limited success getting corporate raiders do its bidding. The problem for Microsoft is that it has to be discreet; otherwise, some of its executives might end-up behind bars for conspiracy to manipulate Yahoo’s stock. Fortunately for Microsoft, Yahoo does not have many options and Microsoft has plenty of time to get its act right.

Yahoo has mostly itself to blame for the situation. The terms Microsoft is offering for Yahoo’s paid-search assets are incredibly harsh and humiliating, but Microsoft is unlikely to sweeten them. The original deal Microsoft proposed in 2006 involved Microsoft “co-owning” and not outright owning Yahoo’s paid-search assets but Terry Semel dismissed it. Since then Yahoo’s management has proven completely hostile to Microsoft overtures and has been unwilling to make concessions. Consequently, Microsoft does not owe Yahoo any favors and it has “earned” the right to own Yahoo’s paid-search assets. Besides, if Microsoft offers a decent deal it may lead to a rise in Yahoo’s share-price and release pressure on Yahoo’s management.

Some rumors suggest Yahoo maybe seeking a merger with a third-party but it is unclear how such a merger will help Yahoo collect the “dues” from Google. Such an attempt can only help Microsoft as it can join the deal by offering to unlock Yahoo’s hidden value in exchange for Yahoo’s paid-search assets. The only thing Yahoo can do is to get Google to bid for its non-search assets, and collect its “dues” that way. Effectively, Yahoo can try to sacrifice some of its non-core assets to save paid-search; however, Microsoft may get antitrust regulators to block that exit as well.

Currently, there seems to be stalemate. Yahoo is under siege but it is not yielding, and Microsoft can’t afford to back off. Time though is on Microsoft’s side. If Yahoo fails to extricate itself from the siege quickly, it may only be a question of how much Microsoft gets paid for taking over Yahoo’s paid-search assets.

LAST UPDATED by Usman Latif  [Jul 07, 2008]

Random Permutation Generation

Many problems require the use of randomly generated permutations, kpermutations, and ksubsets. Simple and efficient algorithms exist for producing these combinatorial objects; however, these algorithms are somewhat subtle and most people do not intuitively understand them. The algorithm for generating random permutations is the most significant of these algorithms, and the other algorithms are simple variants of this algorithm.

Permutations are rearrangements of items where the order the items are listed in is important. For example, the rearrangements {1,3,2} and {1,2,3} are two different permutations of the numbers [1,2,3]. A permutation has the property that it contains all the items in a given set without any repetitions. For instance, the lists {1,2}, and {1,2,2,3} are not permutations of [1,2,3].

It is helpful to visualize permutations as paths in a permutation tree. A permutation tree models the choices available when forming a permutation. The colored edges of the permutation tree denote the items that are being permuted. A particular item corresponds to edges of a specific color. Following an edge in the permutation tree is equivalent to selecting an item, and permutations are formed by following paths from the root to the leaves. Figure 1, shows a permutation tree for four items.

4 permtree

A permutation tree of n items is generated recursively; at the root all n items are available for selection, so the root has n edges of different colors leading to n subtrees. At the subtrees of the root only n-1 items are available (one item has been selected), so the subtrees of the root each have n-1 edges leading to n-1 subtrees. The color of the missing edge corresponds to the the item that has been selected, and each subtree itself is a permutation tree for n-1 items (see Figure 1). This process is repeated with the subtrees of the subtrees, and so on, until the leaves are reached. At that point all items have been selected; therefore, no edges are available to continue the process.

This construction of the permutation tree assures that all permutations of n items correspond to paths in the tree. Also, no two distinct paths correspond to the same permutation of items. This implies that there are as many permutations of n items as there are paths in a permutation tree for n items.

Counting the number of paths in a permutation tree is fairly straightforward; at the root n paths emerge, and each of these n paths splits into n-1 paths at the subtrees of the root. This gives n*(n-1) paths, and each one of these splits into a further n-2 paths at the next level in the permutation tree. The paths terminate at the leaves by which time the original n paths have split into n! (n factorial) paths, and that equals:

n! = n*(n-1)*(n-2)*..*1

An algorithm for selecting random permutations must assure that it has equal chance of picking any one of the n! possible permutations. Figure 2, suggests a simple algorithm for generating random permutations; to get a permutation of n items, simply pick a random path from the root to the leaves in a permutation tree for n items.

A random path can be picked by starting at the root, randomly picking one of the available edges to get to a subtree, and repeating that process to get to successive subtrees until a leaf is reached. The animation below illustrates this process.

permtree anim
Figure 2, Picking a random path in a permutation tree

Intuitively, this process works because the random path picking algorithm is not biased towards any particular path; therefore, all n! paths have equal chance of being picked. More formally, the probability of picking a path consisting of edges {E1,E2,..,En} is the probability of picking the path leading to edge En, and multiplying by the probability of picking edge En given that the path leading to En has been picked.

P({E1,E2,..,En}) = P({E1,E2,..,En-1}) * P(En|{E1,E2,..,En-1})

The above equation can be recursively expanded by substituting in the value for P({E1,E2,..,Ek}) in the right hand side of the equation.

P({E1,E2,..,En}) = P({E1,E2,..,En-1}) * P(En|{E1,E2,..,En-1}) 
                 = P({E1,E2,..,En-2}) * P(En-1|{E1,E2,..,En-2}) * P(En|{E1,E2,..,En-1}) 
                 ..
                 = P(E1|{}) * P(E2|{E1}) * .. * P(En|{E1,E2,..,En-1})
                 = P(E1)    * P(E2|{E1}) * .. * P(En|{E1,E2,..,En-1})

The probability P(Ek+1|{E1,E2,..,Ek}) can be computed readily. At the point where edge Ek+1 is in consideration k edges have been selected, and edges Ek+1 to En are available. Edge Ek+1 is randomly chosen from all the available choices, so there are n-k choices for it. Therefore, the probability of picking edge Ek+1 is 1 / (n-k). The following expression gives the probability of picking a particular path in a permutation tree for n items:

P({E1,E2..En}) = P(E1) * P(E2|{E1}) * .. * P(En|{E1,E2,..En-1})
               = 1/n   * 1/(n-1)    * .. * 1
               = 1/n!

The above expression implies that the path picking algorithm described above picks any path with probability 1/n!; therefore, the algorithm picks all permutations with equal probability.

The random path picking algorithm needs to be efficient; generating the whole permutation tree in advance is not practical. Fortunately, a complete permutation tree is not needed. Each iteration of the algorithm only needs to keep track of the path chosen so far, and the possible selection of choices for the next edge of the path; Figure 2, illustrates this idea.

There are a maximum of n outgoing edges at any node of the permutation tree, and these can be modeled as numbers 1 to n in an array. Selecting an item frees up space for one edge, and a clever algorithm can use that space to store the path. An algorithm that implements these ideas is given below:

for (i=1 to n) ar[i] = i;
for (i=1 to n) swap(ar[i], ar[Random(i,n)]);

The above algorithm partitions the elements of an array of n elements into two parts, positions 1 to i-1 and positions i to n. Positions 1 to i-1 contain the segment of the path chosen so far, and positions i to n contain the unselected edges. The first loop of the algorithm is just initialization of the array elements, and the second loop does all the work in this algorithm.

Each iteration of the second loop extends the path selected so far by one edge. This is done by picking a random edge from the unselected edges and moving it to position i. Of course, the edge at position i has to go somewhere; therefore, the edge at position i is moved to the former position of the selected edge. The table below illustrates this algorithm for picking a 5 item permutation.

IterationSelected EdgeSelected PathUnselected Edges
?1 2 3 4 5
1442 3 1 5
214 13 2 5
334 1 32 5
454 1 3 52
524 1 3 5 2

In the above table, array ar is the concatenation of the last two columns. At each iteration one edge is chosen and moved to position i. Unlike the permutation tree, unselected edges in array ar are in no specific order. This is all right as the algorithm chooses amongst the unselected edges randomly, and any specific ordering of the edges is irrelevant.

Another thing to notice is that after the second last iteration of the algorithm the contents of the array ar do not change. At the last iteration only one edge is left unselected; going through the iteration simply swaps it with itself and results in no change. This suggests that the last iteration of the algorithm is redundant and the algorithm can be changed to the following:

for (i=1 to n) ar[i] = i;
for (i=1 to (n-1)) swap(ar[i], ar[Random(i,n)]);

Multiple random permutations can be generated by repeating the second loop. As long as array ar contains a permutation of numbers 1 to n, it can be reused without reinitialization.

Choosing a random k-permutation turns out to be fairly simple as well. A kpermutation is a rearrangement of k items selected from a total of n items. Kpermutations are a generalization of permutations. A permutation is simply a rearrangement of all n items; a permutation is equivalent to a kpermutation when k equals n.

5 3 permtree
Figure 3, a kpermutation tree for n = 5 and k = 3

Kpermutations too can be visualized as paths in a permutation tree. Kpermutations correspond to paths of length k from the root of the tree. A kpermutation tree can be generated by pruning the permutation tree so that all possible paths from the root to the leaves are of length k. Figure 3, shows such a tree for n = 5 and k = 3. This correspondence with paths suggests the following algorithm for generating kpermutations:

for (i=1 to n) ar[i] = i;
for (i=1 to k) swap(ar[i], ar[Random(i,n)]);

The algorithm above is a modified version of the algorithm for generating permutations; that algorithm yields a path of length n while this one yields a path of length k. Also, it is not possible to optimize this algorithm to cut down one iteration as was the case with the previous algorithm. The optimization in the algorithm for random permutations was possible only because at the last iteration only one edge was left unselected. However, with n less than k more than 1 edges will be available for selection at the kth iteration, and randomly choosing one of the edges will make a difference.

The final algorithm is for choosing a random ksubset. A ksubset is simply a kpermutation where the order of items is unimportant. The lists {1,3}, {3,1} are different kpermutations of the items [1,2,3], but they are the same ksubset. While the lists {1,2} and {1,3} are different ksubsets as well as different kpermutations of [1,2,3].

Paths from the root to the leaves in the kpermutation tree enumerate all possible kpermutations; therefore, they also enumerate all possible ksubsets of n items. The only problem is that each ksubset is enumerated multiple times. This is not an issue as each ksubset appears exactly k! times; once for each permutation of the items in the ksubset. As each ksubset occurs as often as any other all ksubsets have the same probability of being picked at random.

Some problems require ksubsets that are arranged in a sorted order. For example, {1,2,3} and {1,3,2} are the same ksubset but {1,2,3} is in ascending order while {1,3,2} is unsorted. For small k, sorting is inexpensive; therefore the best approach to generating ordered ksubsets in such cases is to simply sort the elements of the ksubset after generating it.

The algorithms for random kpermutations and ksubsets use O(n) space and O(n) time to generate objects of size O(k). O(n) space is needed for the array to store the chosen path and the unselected edges, and O(n) time is needed for initializing the elements of this array. The time and space complexity is not a problem when n and k do not differ by too much, but if n is sufficiently large and k is small, the algorithms can be very inefficient. Part II of this article will discuss techniques to bring the space and time complexity of these algorithms to O(k).

LAST UPDATED by Usman Latif  [Feb 13, 2004]

Part II – Random KPermutations and KSubsets in O(k) space

The first part of this article described some algorithms for the generation of random permutations, kpermutations and ksubsets. The algorithm for generating permutations is very efficient; however, the algorithms for generating kpermutations and ksubsets can be improved significantly.

The following algorithm was given for the generation of random kpermutations, and ksubsets:

for (i=1 to n) ar[i] = i;
for (i=1 to k) swap(ar[i], ar[Random(i,n)]);

The big problem with this algorithm is that it uses space inefficiently. Selecting a Kpermutation of size k from n elements can require O(n) space. For instance, when selecting a KPermutation of 1000 items from a collection of 100,000 items, the algorithm requires an array of 100,000 elements. This is clearly suboptimal and undesirable. The algorithm also initializes the array of 100,000 elements, and this results in O(n) time as well.

Ideally the algorithm should use only O(k) space and O(k) time. This turns out to be possible but requires a few changes to the basic algorithm. The crucial insight is that while generating a Kpermutation, the algorithm disturbs at most O(k) elements in the array containing the item numbers. This allows using a sparse array of O(k) space to represent an array of n elements.

The sparse array contains the numbers 1 to n arranged in ascending order, and it is modeled by a hashtable. Elements that get disturbed by the kpermutation algorithm are placed in the hashtable, and all other elements are assumed to be in their correct places in the array. For example, an array with the following contents:

1 2 3 4  6 5  7 8 9

can be represented by a hashtable containing the following key-value pairs:

(5 6)
(6 5)

An array reference for element i is satisfied by first searching for the key i in the hashtable, and returning the associated value if it is in there; if the key is not in the hashtable the value i is returned. For example, an array reference for 3 in the above array returns 3, but an array reference for 6 returns 5 (the key 6 is in the hashtable).

The kpermutation algorithm only uses a swap operation, so by implementing a swap operation for the sparse array representation the original algorithm can be used without any significant modifications. The algorithm will change to the following pseudo code:

ar = init_htable();
for (i=1 to k) swap_keys(ar, i, Random(i,n));

The swap_keys operation is fairly straightforward to implement, but as the keys might or might not be present in the hashtable, there are four cases to be handled. The four cases and the actions required to swap the keys are summarized below:

Key i     Key j      Action

present   present    swap values, i.e., (i,n)(j,m) -> (i,m)(j,n) 
present   absent     add (j,j) to htable and swap values 
absent    present    add (i,i) to htable and swap values
absent    absent     add (i,i) (j,j) to htable and swap values 

The algorithm takes O(k) space and O(k) time as the swap_keys function executes k times, and on each invocation it uses O(1) time and can allocate at most O(1) additional space. After the algorithm has finished executing, the kpermutation can be retrieved from the hashtable by retrieving keys 1 to k in order. Actually, the algorithm can be easily optimized so that the kpermutation is directly stored in a separate array. Other optimizations are also possible but they don’t improve the O(k) time and space behavior of the algorithm beyond constant factors.

Unlike the original random kpermutation algorithm, this algorithm requires a reinitialization of the hashtable whenever a new kpermutation needs to be generated. Generating many kpermutations without reinitialization of the hashtable will lead the algorithm to use more than O(k) space; this behavior being the result of the swap_keys operation executing more than k times.

As discussed in part I of this article, the random ksubset generation algorithm is the same as the kpermutation algorithm, so the above algorithm can generate ksubsets using O(k) space and O(k) time. However, if the ksubset is required to be in sorted order then a bucket sort can be used to sort the output of this algorithm. A bucket sort will work very well in this scenario as the items of the random ksubset will be distributed randomly over the interval 1 to n. Combining bucket sort with this algorithm will allow sorted ksubsets to be generated in O(k) time.


LAST UPDATED by Usman Latif  [Mar 26, 2004]

Lego Mindstorms: What Went Wrong?

Lego launched the Lego Mindstorms line of programmable toy brick construction sets with a lot of fanfare back in the fall of 1998, but in recent years the company has lost all enthusiasm for the Mindstorms line. For several years now, Lego has not introduced any new Mindstorms sets, and the company has discontinued almost everything in the Mindstorms line apart from the core Robotics Invention System (RIS) set. Sadly, even the RIS is not faring lucky as it has not had an update since 2001. Lego seems to have relegated the Mindstorms line to niche status and frozen its development.

Strangely, Lego is doing all this even though consumer preferences clearly indicate healthy sales growth potential for toys based on the Mindstorms concept of programmable toy brick models. People love building programmable models and robots, and the Mindstorms concept has been a massive hit with everyone but Lego. A huge number of robot building competitions, countless fan websites, a never ending stream of glowing articles in the press, and more than twenty Mindstorms related books by authors unaffiliated with Lego are incontrovertible evidence of that. All these not only suggest massive consumer interest in programmable construction sets but also indicate blockbuster Robotic Invention System (RIS) sales in the past and a huge aftermarket.

Lego’s inattention to the Mindstorms line is all the more puzzling as it comes at a time when the company is desperately trying to recapture consumer interest. According to Lego’s 2004 annual report:

In 2004, the global market for traditional toys once again was under pressure, and in most countries the profile for total sales was either flat or in decline. In contrast, the market for electronic toys — video consoles and computer games — enjoyed a minor increase. The most serious threat, however, is that children are losing interest in traditional toys at a younger age, and that other products in the consumer-electronics sector — such as mobile phones and MP3 music players — are replacing toys to an increasing extent.

The Mindstorms line seems to be the perfect answer to this onslaught by video games and consumer electronics. Mindstorms sets have broad appeal to older age groups, sophisticated play value, and incredible educational potential. This is exactly what Lego needs to regain market share, but oddly, Lego is intent on passing the opportunity.

Maybe Lego’s profit margins on Mindstorms sets are very low, and this is forcing Lego to neglect the Mindstorms line. The strong consumer interest, however, suggests that Lego ought to be able to enhance margins simply by raising prices, but it is possible that demand for Mindstorms sets is elastic. When demand for a product is elastic, price increments cut demand for the product so drastically that total revenue from sales falls instead of rising. Elastic demand is not all bad though; on the plus side, decrements in the price of a product having elastic demand strongly spur demand and increase sales revenue despite lower per unit price. Unfortunately, businesses can only exercise this option of revenue growth if their profit margins allow them to cut prices.

If demand for Mindstorms sets is elastic and profit margins on the sets low then Lego can not do much of anything apart from looking elsewhere for profitability and growth. Essentially, this would mean that consumers love the Mindstorms sets but are unwilling to spend freely to acquire them. This scenario seems to be the only solid explanation for Lego’s disenchantment with the Mindstorms line and is worth exploring further.

The demand elasticity issue is something that can not be readily settled. Fortunately, this issue comes into play only if Lego’s profit margins on the Mindstorms line turn out to be low. If Lego’s profit margins are high then the only relevant issue would be a large potential market, but this is known to be so.

Lego does not disclose its profit margins on the Mindstorms line but they can be estimated indirectly. The key to getting an estimate for Lego’s Mindstorms profit margins is the RIS. The RIS is the most representative and comprehensive Mindstorms set, and an estimate for its production and development costs can serve as an upper bound cost estimate for other Mindstorms sets.

The Robotics Invention System (RIS) comes with 718 parts/pieces. Most of the parts included are not exclusive to the Mindstorms line and are found in other Lego sets as well. It is not at all unusual for Lego sets retailing at $60-$70 to come with an assortment of 600-700 pieces similar to the ones included with the RIS. The RIS retails at $200, so clearly, the non-exclusive pieces are not causing Lego’s margins on the RIS to be lower than its margins on the average Lego set. The discontinued sets in the Mindstorms line were also premiumly priced with respect to similar piece-count, traditional Lego sets; so non-exclusive pieces were not a problem there either.

The Robotics Invention System also includes some electronics not included in the average Lego set. These include an RCX brick, an IR tower, and some sensors. The RCX brick looks like the costliest component in the RIS set, but it does not include any expensive high-tech components that ought to cost a lot. It has an 8-bit microcontroller with 16 KB of ROM, 32 KB of RAM, a segmented LCD, a tiny speaker, IR communication circuitary, and motor/sensor control circuitary. These are commodity components and are often included in all sorts of inexpensive devices and toys. A good way of coming up with a cost estimate for these components and the RCX is to compare the RCX with a device of known price that incorporates similar components.

(UPDATE: The RCX comparison to the gaming device given below is unjustified. An 8-bit microcontroller with 16 KB of ROM can cost a dollar, so the RCX can not possibly cost 75 cents as asserted below. A realistic estimate of the cost of RCX is around $5, and a reasonable estimate of the total cost of Mindstorms specific components in the Robotics Invention System is $10 and not $3. However, these numbers still do not invalidate the conclusion that the cost of electronic components in the RCX is inconsequential. Lego priced the Mindstorms derivative Spybotics vehicles at $60 each, which affirms that assessment.)

The picture below shows an RCX brick along with a gaming device of Chinese make that incorporates components similar to the ones used in the RCX. The gaming device was purchased for approximately $1.83 from a mom-and-pop retail store, and it is missing only the IR communication and motor/sensor control circuitary.

Figure 1, RCX comparison
Figure 1, RCX comparison

As can be seen in the picture, the gaming device has a huge screen compared to the RCX brick. This partially compensates for the absence of some of the additional circuitary of the RCX. Now the gaming device made it to the store it was purchased from after going through two or more distributors, and each of the distributors and the retailer added significantly to the price; therefore, the original equipment manufacturer’s cost of making the gaming device must be less than fifty cents.

The RCX may cost a little more than fifty cents to manufacture but it certainly does not cost five times more; a fifty percent allowance to cover the additional circuitary in the RCX is more than generous. This means the RCX costs Lego less than 75 cents. The Robotics Invention System comes with motors/sensors and an IR tower as well, but similar reasoning suggests that $1.25 more than adequately covers the cost of these components. An additional $1 pays for some nicely printed documentation and a CD, and in total Lego is spending $3 on RIS specific components of the RIS set. This $3 increase in production costs is completely insignificant as the RIS retails at $200, substantially above comparable piece Lego sets.

The discontinued Mindstorms sets carry far fewer electronic components than are bundled with the RIS, so production costs for such sets are only a small fraction of $3 above those of traditional, similar piece-count Lego sets. Additionally, Lego has the option of reengineering/restructuring the sets to use fewer expensive components; therefore, the production costs of Mindstorms sets are not an issue. On the contrary, the premium pricing of the RIS and the discontinued Mindstorms sets suggests that gross margin (revenues minus production costs) on Mindstorms sales has always been higher as compared to Lego’s gross margin on its core product sales.

Lego also spent money on the design and development of the RIS. Putting together a user-friendly package that seamlessly blends together hardware, software, and documentation is always a challenge. Such a development effort requires significant resources and Lego did spend significant amounts on design and development of the RIS. However, whatever Lego has spent in the past on the RIS and Mindstorms development is irrelevant to Lego’s current/future Mindstorms margins. Lego’s past spending constitutes sunk costs: Lego has spent the money and can’t recover it by selling fewer Mindstorms sets.

Development costs of new Mindstorms sets are relevant though, but they can’t possibly be too burdensome. The software/hardware components Lego developed for the RIS are designed to serve as a common platform for all Mindstorms sets, and introduction of new sets in the Mindstorms line is only a matter of reuse; it does not entail costly development from scratch. Additionally, development costs of a Mindstorms set are fixed costs: they don’t change with the number of units shipped. This implies Lego can counter the impact of development costs by shipping large volumes. As Lego’s gross margin on Mindstorms revenues is very high, so higher volumes ought to be attainable via a combination of attractive pricing and strong marketing. (This assumes demand for Mindstorms is elastic, but if this is not so, Lego can recover its development costs simply by raising prices.)

Clearly, there is strong demand for Mindstorms sets, Lego needs Mindstorms sets to combat its diminishing market share, and Lego can produce Mindstorms sets cost-effectively as well. There does not seem to be any obvious rational reason for holding back support for the Mindstorms line but Lego is doing exactly that.

Such behavior is odd but sometimes businesses do treat successful products in this fashion. Often, the problem in such cases is cannibalization. Cannibalization is a marketing term, and it refers to a decrease in sales of older products of a business brought about by introduction of newer products by the same business. Cannibalization can hurt overall profitability of a business and can prompt a business to discontinue a product that is cannibalizing sales but is otherwise highly successful.

Cannibalization has been a problem for Lego as well; a disclosure in Lego’s 2003 annual statement positively affirms this. The disclosure states:

For several years, LEGO Company has invested substantial funds in expanding its product portfolio. This commitment and the consequent cost increases have not produced the desired results. In some cases, new products have even cannibalized on the sales of LEGO Company’s core products and thus eroded earnings.

The above disclosure does not name Mindstorms sets for cannibalizing sales, but there are no other candidates. Lego is persisting with the development and marketing of every other major product line it launched in recent years, and the timing of the disclosure coincides precisely with the phasing out of Mindstorms as a mainstream Lego product line.

Some level of cannibalization is inevitable whenever a business launches an improved product that competes with its existing products, but this is usually not a problem. Often higher margins on the newer product compensate for the loss of sales of older products. Clearly, Mindstorms sets cannibalized Lego’s traditional sales so drastically that the company was forced to move away from the Mindstorms line. Still, Lego’s current tactics remain puzzling: Lego is persisting with the Mindstorms Robotics Invention System (RIS) even though it can easily discontinue it.

Discontinuing a product that is cannibalizing sales is not always feasible for a business. Sometimes businesses are forced to persist with products that are money losers after figuring in cannibalization. Typically in such cases businesses are afraid that if they don’t introduce improved products, their competition will; and then they will end-up losing sales anyway.

Few people are aware but Lego actually happens to have some competition in the Mindstorms market. FischerTechnik a German company sells construction sets that compete with the Mindstorms line. FischerTechnik is not a cheap knockoff of Lego; the company makes very high quality construction sets, and its construction sets are not only comparable to those of Lego but are even considered superior by many. The company has an especially strong following amongst educators.

FischerTechnik isn’t much of a threat to Lego, but Lego’s several years of misguided marketing push of the Mindstorms line has created a big market for robotic construction sets. Lego knows if it discontinues the Mindstorms line completely, FischerTechnik can step in and fill the void. This realization is forcing Lego to make RIS supplies available so that people who just have to have a robotic construction set can get one from Lego instead of looking elsewhere. However, due to the cannibalization threat, Lego likes the Mindstorms line confined to a market niche.

All of this explains Lego’s current Mindstorms strategy, but the most interesting question remains unanswered: why do Mindstorms sales cannibalize sales of traditional Lego sets? This question is all the more interesting as Mindstorms sets and traditional Lego sets are complementary. Parts from traditional Lego sets can be used and are often used to build complex RCX based models. In fact, the Mindstorms line is based on Lego’s mechanically oriented Technic line, and Mindstorms sets are essentially bundles of Technic pieces complemented with a programming interface.

The cannibalizing effect of Mindstorms sales has to result from something peculiar about Mindstorms sets, but there is only the programming interface that stands out as a uniquely Mindstorms addition. Unfortunately, it is not obvious how the programming interface can impact sales of traditional Lego sets. The programming interface enhances the user experience, but it in no way obviates the need for complementing Mindstorms sets with pieces from Lego’s Technic and other core product lines. It is possible though that complementary sales are insignificant, and the enhanced user experience is leading Lego customers to lose interest in traditional Lego sets. This possibility is promising but evaluating it requires some knowledge of the play habits of Lego customers.

Actually, the programming interface is not all that is different about Mindstorms sets. Mindstorms sets although composed mainly of Technic pieces are structured very differently from Technic sets. Mindstorms sets are generic: the typical Technic set is designed to assemble into one specific model, but this is not so with the Mindstorms sets. The pieces in Mindstorms sets have been carefully selected to be useful for the construction of a very wide range of models. For instance, the Constructopedia (the RIS manual) provides assembly instructions for three very different robots using many of the same pieces. This generic structuring of Mindstorms sets is good for Lego customers, but it may be promoting ‘excessive’ reuse of Lego pieces and could be a factor in cannibalizing sales.

Both of these possibilities are plausible, but they are mutually contradictory. Extensive reuse of Lego pieces can only happen if Lego customers are Lego literate, i.e., Lego customers can design and build complex custom models on their own and are not dependent on Lego provided assembly instructions. However, a Lego literate customer base implies significant complementary sales and little potential for customers losing interest in traditional Lego sets. Consequently, deciding between these two possibilities is a matter of determining the level of Lego literacy of Lego customers.

Media stories about Lego tend to create the impression that most Lego customers are Lego literate and are building sophisticated models, but there is no evidence that such is the case. Lego literacy is a non-trivial qualification; it implies thorough knowledge of Lego pieces, familiarity with various model construction techniques, and reasonable understanding of mechanical concepts. For instance, the RIS comes with a torque limiting device in the form of a clutch gear; however, a person can not do much with the clutch gear without understanding torque, gears, and the utility of the clutch gear in various mechanical mechanisms. Moreover, the clutch gear is not the only piece included with the RIS that requires a hefty explanation; the RIS is loaded with all sorts of sophisticated parts: differentials, rack gears, pulleys, cams, connectors, and various types of bricks.

Developing widespread Lego literacy is a tough ask as is, but this task is made exponentially tougher by the documentation Lego bundles with its sets. Lego documentation primarily consists of model specific assembly instructions, and these instructions encourage play that involves searching for pieces and putting them together as depicted. Such play is completely scripted and devoid of all creativity and imagination, great training for developing assembly-work skills but completely useless for developing Lego literacy. Actually, Lego documentation contains little that is of value for developing Lego literacy. Lego documentation provides no explanation of mechanical concepts, it lacks functional description of Lego pieces, and it discourages people from looking up information on Lego pieces by omitting names. Additionally, by providing sophisticated reference models, it makes experimenting with custom (invariably unsophisticated) models unsatisfying and further impedes development of Lego literacy.

All of this misdirection implies that there is no possibility of more than an insignificant fraction of Lego customers being Lego literate. This rules out the possibility of the genericness of Mindstorms sets leading to cannibalization, and the cannibalizing effect of Mindstorms sales has to be a consequence of a vastly enhanced user experience offered by Mindstorms sets.

Actually, the Mindstorms user experience by itself has never been the problem. The Mindstorms user experience leads to a substitution effect: it reduces demand for traditional Lego product lines, but compensates for that by creating additional demand for the higher margin Mindstorms line. Lego would have won on the whole had it managed to convert the additional demand so created to sales, but Lego failed to do that and lost on account of that failure.

Lego’s Mindstorms product lineup was the reason behind Lego’s failure. The Mindstorms lineup consisted of the RIS, some stripped down versions of the RIS, and several accessory sets intended to complement the RIS. The RIS was the entry point to the Mindstorms line; it was a well-designed set with wide appeal. The stripped down versions of the RIS were also well-designed but the RIS obviated any need for them. The accessory sets were not so well-designed and were mostly bundles of Lego pieces intended for building complex robots; their use required Lego literacy and this requirement severely diminished their appeal. Overall, the Mindstorms lineup was uncompelling with only the RIS having good sales potential. Consequently, in the years after the launch of the Mindstorms line, Lego shipped huge volumes of RIS sets but not much else. Unfortunately, this was not good enough as Lego needed to sell additional Mindstorms sets to RIS owners in order to avoid getting hurt by the substitution effect created by the Mindstorms user experience.

Lego can sidestep the cannibalization by a simple restructuring of the Mindstorms line, but the company is unlikely to win anything big by doing that. The Mindstorms line was Lego’s attempt at achieving substantial revenue growth by broadening its customer base to include older children and adults; however, Lego ended up selling the Mindstorms sets primarily to its existing customers. Renewed focus on a restructured but not rethought Mindstorms line will mostly achieve more of the same. The result will be a reallocation of revenues from traditional Lego product lines to the Mindstorms line. Such a reallocation in the absence of cannibalization might turn out to be a net gain but this is not what Lego wants. Lego wants solid revenue and profit growth and this objective requires a fundamental rethinking of the Mindstorms line.

Lego was correct in attempting to broaden its customer base with the Mindstorms line as it seems to be selling all it can to the younger age groups. However, the manner in which Lego proceeded indicates complete cluelessness as to what is required in order to win over older individuals. To attract older age groups, Lego does not need to add bells and whistles to Lego bricks; instead, Lego just needs to address the lack of Lego literacy. Most people including long time Lego customers are totally unaware of the considerable play potential of Lego bricks and believe Lego play to be all about putting pieces together as depicted, and this perception of Lego play is turning away older age groups. The bells and whistles included in Mindstorms sets are helpful in garnering attention but by themselves they don’t lead to sophisticated play, and Lego needs to educate its older customers so that they can engage in play that is sophisticated, constructive, and fun.

Lego needs to introduce a new product line that can serve as a vehicle for developing Lego literacy. One idea for such a product line is to have sets based around important concepts and mechanisms. For instance, the product line can have one set for introducing people to torque and gears, another to demonstrate more sophisticated parts like the clutch gear, and yet another to cover pulleys and belts. The quality of the documentation bundled with the sets will make or break any such effort, so Lego will need to include documentation that stimulates thinking, emphasizes problem solving, and encourages experimentation and creative play. The documentation can achieve these goals by providing individuals with readily digestible information, as well as by leading them through exercises and experiments that build intuition. Lego should also add programmability to such sets but this should be done selectively, without creating dependencies amongst sets, and in a manner consistent with the overall goal of the product line.

Admittedly, it is inconceivable that the majority of Lego customers will ever become Lego literate enough to design complex models on their own; however, if Lego makes an honest attempt at addressing the problem, it will end up with a customer base that is at least capable of understanding the designs provided by Lego and tinkering with them in some small way. This will translate into an exponential increase in customer satisfaction and will immeasurably add to Lego’s ability to retain customers and attract a broader audience.

Lego’s prospects are good and the company is not about to become irrelevant. The appeal of Lego bricks is timeless and their potential unlimited. It is just that Lego is too obsessed with growth strategies that have worked in the past but are no longer relevant. Lego is unwilling to recognize that it is not selling a system of play but only a particular kind of play, and the market for that kind of play has become saturated. To grow Lego needs to promote new kinds of play and Lego possesses all the infrastructure necessary to accomplish that. For Lego, growth is only a matter of putting the pieces together creatively.


LAST UPDATED by Usman Latif  [Nov 27, 2005]

Minesweeper First Click Behavior

What does Windows Minesweeper do to make sure a mine is not uncovered on the first click? According to Ivars Peterson’s Minesweeper Logic page, if a mine is uncovered on the first click, it is moved to the upper-left corner of the board. If the upper-left corner is occupied the mine is moved to the right of it. This link on the other hand claims a bit more eccentric behavior for Minesweeper first click. I decided to investigate and settle the question for good.

The only way for any investigation of Minesweeper to make a definitive claim is to reverse engineer and examine the Minesweeper code. I did just that and it turns out that the first claim is true.

I used the WinDbg debugger to run Minesweeper and watch its behavior while it is executing. The crucial code is embedded in the StepSquare function. I disassembled and read the code to determine the actual algorithm. The disassembled code can be viewed by following this link.

The StepSquare function is invoked by Minesweeper every time an unmarked square is clicked. The function checks if it is the first click, and that the square being clicked is a mine. It then tries to move the mine to the upper-left corner. If unsuccessful it tries the square to the right of it. If all of the first row is occupied by mines, the function tries to put the mine in the leftmost square of the row below, and so on.

Using the debugger I generated identical boards to demonstrate this behavior. Figure 1 shows a board on which the first click was on a square not containing a mine. Figure 2 shows the same board but now the first click was on a square containing a mine. Notice that the mine in the upper-right corner in figure 1 has moved to the upper-left corner in figure 2.

Figure 1.Figure 2.

I generated two additional boards to demonstrate Minesweeper behavior when the upper-left corner is occupied. The board in figure 3 is one where a non-mine square was clicked. Figure 4. is the same board as in figure 3. but the first click in this case was on a mine. The rightmost mine was the one that was clicked and it has consequently moved to the right of the upper-left corner.

This image has an empty alt attribute; its file name is mine-corner4.gif
Figure 3.Figure 4.

This behavior has an interesting consequence, the upper-left corner is typically not a good place to look for a cascade during a Minesweeper game. On the first click, corners are the best place to look for cascades, but the upper-left corner is the worst choice of the four corners. A cascade can occur in the other three corners even if the corner itself is a mine: the first-click will simply move the mine elsewhere. But, in case of the upper-left corner the mine will move right adjacent, and will block the cascade.

After the first click, the upper-left corner has an above average probability of containing a mine: a mine could have moved there from the first-clicked square. Therefore, the player will be taking undue risk by clicking the upper-left corner.

If you open Minesweeper by clicking the upper-left corner it would be best to switch to another corner. The actual impact of clicking the upper-left corner depends on the total number of mines in the board. The impact can be very significant for boards with lots of mines and totally insignificant for boards with very few mines.

LAST UPDATED by Usman Latif  [Nov 30, 2003]
Thanks to Ruben V. for pointing out errors in this article.

The Probability of Unplayable Solitaire (Klondike) Games

The Solitaire game Klondike has a few idiosyncracies: not all Klondike games are solvable. Moreover, Klondike sometimes produces unplayable games. In such cases no moves are available to the player even at the beginning of the game. The probability of occurrence of unplayable games is an important number as it is a lower bound for the probability of occurrence of unsolvable games.

Klondike, the version bundled with Windows, consists of seven stacks of cards containing a total of 28 cards, a deck of 24 cards, and four initially empty suit stacks. The seven stacks are arranged in a single row with one card in the first stack, two cards in the second stack, three cards in the third stack, and so on. The objective of the game is to move all 52 cards to the four suit stacks (one for each suit) in order of rank.

Klondike has two variants; the player is either dealt three cards from the deck at a time, or is dealt one card at a time. In the three card at a time variant, only the topmost card is playable. The analysis described here is for the three card variant of the game.

At the start of a Klondike session, only fifteen cards are playable. Seven of the fifteen cards are the top-most cards of the row-stacks and the other eight cards are in the deck of 24 cards. Any aces present in these fifteen cards can be moved to the suit stacks. A pair of playable cards can be stacked, if the two cards are of different colors, differ by one rank, and the bottom car has higher rank. Cards from the deck can only be moved to either the row-stacks or the four suit stacks. The game has some additional rules as well but they are irrelevant to the discussion at hand, and are not described here.

An unplayable Klondike game satisfies the following three conditions simultaneously:

  1. No aces are in the fifteen playable cards
  2. None of the seven playable cards in the row-stacks can be moved to a different row-stack.
  3. None of the eight playable cards in the deck can be moved to any of the seven row-stacks.

The probability of satisfying only the first condition can be easily calculated. This probability is the number of all possible arrangements (combinations) of 15 cards taken from a deck with no aces, divided by the number of all possible arrangements of 15 cards taken from a deck that includes aces. The two numbers in question can be computed using Binomial coefficients, and the following expression gives the result of the calculation:

Binomial[48,15] / Binomial[52,15] = 0.2439

The number 0.2439 suggests that on average 24.39 percent of Klondike games start with no aces amongst the initially playable cards. Equivalently, 75.61 percent of Klondike games have at least one ace in the 15 initially playable cards.

Unfortunately, the number computed above is of no great help in computing the probability of occurrence of unplayable games. That calculation requires simultaneously satisfying all three conditions mentioned previously; there is no simple analytical approach to solving that problem.

A brute force approach to generate and test all possible Klondike games is not feasible either. Even considering only the games where no aces occur in the 15 playable cards, the number of all possible Klondike games is quite large. Under the previous scenario, the number of games to be examined totals:

Binomial[48,7] * Binomial[41,8]  = 7,035,128,610,578,640 

This number is more than a handful for current computing hardware; therefore, a less computing intensive approach is required for solving this problem. One idea is to use Monte Carlo simulation to estimate the probability of unplayable games.

A Monte Carlo simulation consists of repeating an experiment a large number of times. An experiment in the context of Monte Carlo simulation is occurrence of a random event that either generates a favorable or an unfavorable outcome, e.g., a coin toss. The simulation proceeds by repeating the experiment some specified number of times and recording the number of favorable outcomes. The number of favorable outcomes divided by the total number of trials gives an estimate for the probability of the favorable outcome.

Designing a Monte Carlo simulation for modeling Klondike games is straightforward. Cards can be modeled as a set of 52 numbers, and random Klondike games can be generated by permuting this set of numbers. The favorable event under this scenario is an unplayable game. Checking a randomly generated Klondike games for unplayablity can also be accomplished easily.

A scheme program for this simulation problem was coded, and was used to simulate 10 million Klondike games. A total of 24,893 unplayable games were reported by the simulation. This gives 0.0025 (rounded to two significant figures) as an estimate of the probability of occurrence of unplayable games. This estimate suggests that on average 0.25 percent (one out of 400) of all Klondike games are unplayable.

As mentioned earlier, the probability of unplayable games is a lower bound for the probability of unsolvable games. All unplayable games are unsolvable, but some initially playable games are unsolvable as well. Many Klondike games allow some initial moves but then run out of possible moves. It is hard to estimate the probability of unsolvable games but a reasonable estimate would be 10-40 times the probability of unplayable games. This suggests that anywhere from 2.5 to 10 percent of all Klondike games are unsolvable.

Some players might be surprised by the above numbers. These numbers imply that majority of Klondike games are winnable; however, experience playing the game indicates otherwise. The reason players do not win majority of Klondike games is mainly the tremendous amount of guesswork involved in playing Klondike. A few wrong moves can easily make a player lose and this is what happens most of the time.


LAST UPDATED by Usman Latif  [Feb 01, 2004]

Why Windows is a Security Nightmare

Security in all mainstream operating systems is non-existent; however, things are especially bad for Windows. Windows happens to be the favorite target of worm and virus writers. Conventional wisdom suggests that the huge installed base of Windows helps spread the worms and viruses, and also makes it a highly attractive target for worm/virus writers. The installed base of Windows certainly has an undeniable effect on the prevalence of malware on Windows, but this is not all there is to it.

Worms and viruses are so stunningly effective on Windows only because Windows provides some atrocious functionality which makes it easy for worms to strike. It might seem counterintuitive but Windows Registry, and a misdesigned Windows Update are the primary culprits that create a hospitable environment for worms and other malware.

A typical Windows system follows a simple lifecycle: it starts out with a clean Windows installation, which gradually deteriorates as programs are installed, and uninstalled. Eventually, the Windows registry accumulates so much crud that the user is forced to do a clean install. When a user does a clean install that user’s system loses all the previously applied security updates, and becomes a sitting duck for worms and other malware.

Things wouldn’t be so bad if the user was able to update the new system with security patches painlessly, but Windows Update makes it very hard to do so. My personal experience with the killer duo is an enlightening example of how all of this works.

I purchased a Thinkpad X21 with Windows 2000 Professional in January 2002, and since then have gone through three clean install cycles. After the second cycle I decided to stick with a deteriorating installation no matter what happened.

As expected, pretty quickly the registry started accumulating all sorts of rubbish, and the system started exhibiting strange bugs. First Mozilla stopped working; reinstallations, uninstallations, upgrades did not resolve the problem, so I switched to Opera.

A few months later Windows explorer started to hang on folder right click. I did my best to search for a solution to this problem on the internet, but never managed to find a solution. Resigned, I eventually learned to avoid right clicks on folders, and became adept at killing and reinvoking the explorer process after an inadvertent forbidden click.

Then I made the mistake of installing VMWare 30 day demo on my system. As soon as I booted Linux under it as a guest OS, the the sound card went bonkers, and started producing high pitched screeching sounds. I tried reboots which didn’t work; as a last resort I uninstalled VMWare but that didn’t work either. This forced me to lower the volume of the speakers to muffle the screeching, but I continued using the same setup.

Finally, I had the bright idea of downloading a registry cleaner to fix things. The product I downloaded turned out to be some pathetic crippleware, and I uninstalled it. Well, that was the fatal fatal mistake; the next time I rebooted, Windows refused to load. Safe mode, last known good configuration, etc., all failed, and so I was forced to do a clean install.

As expected the clean install took care of the bugs. However, it also got rid of all the security updates. I immediately connected to Windows update to download the service packs, and the critical updates. Rather quickly I was welcomed by Messenger Service spam. The Messenger Service spam was only a minor inconvenience as I knew how to turn it off; however, within a short while I got a message from Windows saying that svchost.exe had crashed: the Blaster worm had struck.

The Blaster worm attacks Windows XP, and Win2K systems. In order to infect a system the worm needs to send the correct payload for the respective OS. The worm is not able to differentiate between the XP and Win2K so it randomly guesses the OS type; however, if it guesses wrong the RPC service crashes, and Windows reports it as a crash of svchost. The Blaster attack was quite a surprise as the major outbreak of the worm occurred back in August 2003, and I was expecting all infections of the worm to be fixed by now.

I was in no position to do anything about the Blaster attack, so I continued downloading the 35 MB service pack 4 over my dialup connection. It took me a couple of hours to download it, but Windows Update refused to install it; Windows Update probably needed some functionality provided by the crashed svchost.exe.

I rebooted and connected to the internet, which was a mistake as I was giving the worm a second chance to infect my system. Anyway, I proceeded to Windows Update, and tried the same download again. Alas, Windows Update had forgotten all about the 35 MB it had downloaded previously, and started downloading the same stuff all over again. Worse, the Blaster worm crashed svchost again, and I had to discontinue the download.

I knew about the existence of a standalone security update to patch the vulnerability Blaster exploits, so I decided to bypass Windows Update and download it directly. The download was small less than 1MB, but as soon as I tried running it I learned that it requires at least service pack 2 to install, which I didn’t have.

Microsoft provides a separate download for service packs as well, and I decided to download the latest service pack, service pack 4. Well, the standalone service pack 4 distribution turned out to be a mammoth 129 MB download. This is about the maximum I have ever downloaded over a dialup connection; a download of this size can easily take 10 or more hours to complete.

Downloading a large file over dialup requires the ability to resume downloads which Internet Explorer does not provide, so I downloaded Wget to acquire that ability. Wget is a commandline tool and is invoked by calling it with the URL name. I tried pasting the URL on the command line, but it turns out that the cut and paste functionality disappears after a blaster attack, so I was forced to manually type the URL.

Normally, typing a URL is not a big deal. Everyone types URLs all the time, and I do too, but I do mind typing gibberish strings of 95 characters like the following:

http://download.microsoft.com/download/E/6/A/E6A04295-D2A8-40D0-A0C5-241BFECD095E/W2KSP4_EN.EXE

To cut a long story short I managed to download and install the service pack, and the Blaster security update. Finally, the Windows Update started working and after another 30-40 MB of downloads, and 3 or so reboots, I managed to installed the 18 security updates available there (another 5 have been added to that number as of now).

After this experience I cannot help but laugh at the ‘usability’ problems Windows users are reporting about GNOME and KDE. It has become pretty clear to me that Windows users are so accustomed to usability problems that they don’t even recognize them as usability problems. But, as soon as these people move to a different environment they start complaining simply because the new environment does not replicate the features and bugs of Windows exactly.

The other big lesson from all this is that most Windows users are incapable of ‘securing’ their systems. This is precisely why an unprotected system gets attacked in a matter of seconds, and spammers are still sending out Messenger service spam. Worse, Microsoft is directly responsible for this state of affairs. Windows encourage users to reinstall it every once in a while, and when they do, Windows Update actively prevents users from updating their systems.

The whole idea of Windows Update is a joke. Using an unreliable and insecure network as the primary means of distributing security updates is simply idiotic. This is like asking people to walk through a minefield to get to a shelter. I was able to download security updates off the internet only because the current generation of worms are not particularly malicious; they are just minor irritants.

If Microsoft is serious about Windows security it needs to fix Windows Update, and get rid of the damned Registry for good. Unfortunately, Microsoft’s approach is to layer half baked fixes over utterly broken things to keep them going for as long as possible. Microsoft knows that there is a problem with the Registry, but the way it is dealing with it is by offering Registry rollbacks, and similar worthless functionality.

I did a search on Google for “System Restore Does Not Work” and as anticipated there are plenty of complaints about XP’s System Restore functionality. Furthermore, such approaches even if they somehow became reliable would still not work. There is a very simple reason for that, users cannot reliably associate the problems they are experiencing with changes in the Registry. For instance, if svchost crashes how is a user to know whether changes in the Registry caused it or a worm caused it? The extra functionality will likely lead to futile rollbacks and additional frustration for the users.

The upcoming SP2 update for Windows XP is another good example of a clueless fix. According to the reports I have read SP2 will enable the XP firewall by default, and will also include many nifty features to protect the system. It is pretty obvious that such updates cannot work in the presence of the Windows Registry. Windows users who install any kind of software will sooner or later be forced to downgrade because of registry problems, and when they do they will get fried.

I am not saying Microsoft should not do what is doing, but it should focus on the more important things first. For the short term the correct approach is to fix Windows Update so that users aren’t forced to connect to a network to get security updates. Windows update should encourage users to create a Windows Update CD that contains all the security updates the user has downloaded so far. The CD should contain a setup routine that is capable of installing all the updates in an automated fashion without requiring user intervention. Inevitably, when the user downgrades he/she can use that CD to update the system, and then connect to a network to download any further updates. Such a CD should be shareable amongst users, so that if someone doesn’t have an update CD, he/she can simply get one from a friend or an acquaintance.Actually, Microsoft does offer a security update CD, and is willing to ship it to customers free of charge. But, as always Microsoft has made a mockery of a decent idea. First of all, 2-4 weeks are needed to deliver the CD. Then there is the problem of availability, the CD is not available everywhere (I live in Pakistan, and the CD is not available for Pakistan). Also, the CD Microsoft is offering is horribly out of date. There is no fix for this last problem, if Microsoft starts updating the CD every other week, then people will start asking for a new CD every other week. Obviously, shipping a CD to every customer every few weeks is quite an expense, and Microsoft doesn’t want that. So, the Microsoft Update CD is there just for moral support.

Overall, Microsoft is flat-out confused about how to deal with Windows security problems. The recent decision to disallow pirates access to Windows XP SP2 is another action reflective of that confusion. I can’t understand why Microsoft is so jittery about supporting pirates. Microsoft’s paying customers are suffering because of insecure Windows systems; therefore, Microsoft’s first priority should be to get the worm infected systems fixed. If this requires distributing security updates to pirates so be it.

Microsoft really needs to look beyond short term remedies to solve security problems. The company has to move away from its Windows roots in order to create a secure operating system environment. Microsoft has a huge research and development budget, and it just doesn’t make sense why it cannot develop a security centered OS.

LAST UPDATES: by Usman Latif [May 16, 2004]