Felix Breuer's Blog

Time Flies at RISC

It is amazing how quickly time can pass: I am already half a year at the Research Institute for Symbolic Computation in Linz, Austria. (Actually, RISC is in Hagenberg, but I am living in Linz.) I am working in Peter Paule’s Partition Analysis project, which is part of the SFB Algorithmic and Enumeratice Combinatorics, a joint special research program of Johannes Kepler University Linz, the University of Vienna and the Technical University of Vienna. The people at RISC are fantastic and I enjoy the lively - and very international - research environment.

I have been positively surprised by both the quality and the quantity of events that are taking place around here. In addition to the regular Algorithmic Combinatorics Seminar and Theorema Seminar, there are always interesting workshops and conferences to go to. Mentioning just those I attended, there were:

in addition to several internal meetings of our SFB, both at RISC and in Vienna. Unrelated to all these local events, I was also happy to travel to Geneva to participate in the Open Knowledge Conference, back in September, which was a great experience.

Between all these goings-on and the general excitement of a transatlantic move to a new country, I also got a lot of research done. Primarily, I have been working with my good friend Zafeirakis Zafeirakopoulos on the joint project we started back in San Francisco and I have been exploring new territory with Brandt Kronholm, my fellow postdoc in the partition analysis project, and Dennis Eichhorn. In addition, I managed to finally get a couple of papers out the door which have been in the pipeline for a long time, and I have enjoyed many stimulating conversations with the people at RISC and in the SFB, leading up to exciting future projects.

Last but not least, I met a couple of very nice coders in the coworking space Quasipartikel right around the corner from my apartment. Michael Aufreiter and Oliver Buchtala are working on the fantastic editing and publishing platform Substance and I have had many in-depth discussions about Fund I/O with Martin Gamsjäger and Milan Zoufal.

All of the items above, would deserve their own blog post, but that is (obviously) not going to happen. However, judging by the experience of the last few years, the spring is always a good time to start blogging again. So, look forward to further updates soon!

Pictures

I want to close this post by sharing a couple of pictures of the beautiful scenery that comes with doing research at RISC. The institute itself is housed in the venerable Castle of Hagenberg.

Castle of Hagenberg, home of RISC

The castle’s tower offers a nice view of Wartberg and the valley.

View from tower

My own office is in a very nice new extension building overlooking the pond.

RISC extension building

RISC extension building in the evening

I myself do not live in Hagenberg but the city of Linz. Here you see the view over Linz from the Pöstlingberg.

Linz skyline

As you can see from the list above, Strobl is a favorite location for status seminars of the different working groups here at JKU. Unfortunately, these usually go from early morning to late in the evening, so that there is usually no time to enjoy the scenery. But if you can manage to squeeze in a walk between sessions and the weather plays nice, the view on the Wolfgangsee can be truly breathtaking.

Wolfgangsee, seen from Strobl

From Open Science to Open Mathematics

“Science is based on building on, reusing and openly criticizing the published body of scientific knowledge. For science to effectively function, and for society to reap the full benefits from scientific endeavors, it is crucial that science data be made open.” Panton Principles

“A piece of data or content is open if anyone is free to use, reuse, and redistribute it — subject only, at most, to the requirement to attribute and/or share-alike.” Open Definition

I could not agree more. However, what do open science and open data mean for mathematics?

As exciting as the open science and open data movements are, they appear at first glance to be largely unrelated to the world of pure mathematics, which revolves around theorems and proofs instead of experimental data. And theorems and proofs are “open” the moment they are published, right? Does this mean that mathematics is already “open”?

Of course, the word “published” is loaded in this context: The debate around open access publishing in academia is ongoing and far from settled. My personal view is that the key challenge economic: We need new funding models for open access publishing - a subject I have written a lot about recently. However, in this blog post I want to talk about something else:

What does open mathematics mean beyond math papers being freely available to anyone, under an open license?

The goal is to make mathematics more useful to everyone. This includes:

  • Discovery. How can we make relevant mathematical research easier to find?
  • Understanding. How can we make math papers easier to comprehend for a wider range of people?
  • Exploration. How can we allow readers to interact with our work?
  • Application. How can we make mathematical knowledge easier to use in many different contexts?
  • Modification. How can we make it easier to build upon mathematical research?

We can open up new possibilities in each of these areas by reimagining what it means to publish mathematical research.

Mathematics as data

Examples, definitions, theorems, proofs, algorithms - these are the staples of mathematical research and constitute the main body of tangible mathematical knowledge. Traditionally we view these “items” of mathematical knowledge as prose. What if we start to view examples, definitions, theorems, proofs and algorithms as data?

Examples have always been the foundation of any mathematical theory and the discovery of new examples has been a key driver of research. As systematic search for examples (with computers and without) is becoming increasingly important in many fields, experimental mathematics have flourished in recent years. However, while many researchers publish the results of their experiments, and some great open databases exist, experimental results often remain stuck in a tarball on a personal website. Moreover, the highly structured nature of the mathematical objects encoded has led to a profusion of special purpose file formats, which makes data hard to reuse or even parse. Finally, there is a wealth of examples created with pen and paper that either are never published at all, or remain stuck in the prose of a math paper. To make example easier to discover, explore and reuse, we should:

  • Create decentralized databases of examples. Think both OEIS and “github for examples”.
  • Promote the use standard formats to represent structured data, such as YAML or JSON.
  • Acquire the parsing skills to deal with special-purpose file formats where necessary.
  • Complement LaTeX papers with data sets of examples in machine readable form.
  • Make uploading data sets on the arXiv common practice.
  • Publish examples even if they don’t make it in a paper.

The rise of experimental mathematics goes hand in hand with the rise of algorithms in pure mathematics. Even in areas that were solidly the domain of pen-and-paper mathematics, theoretical algorithms and their practical implementation play an increasingly important role. We are now in the great position where many papers could be accompanied by working code - where papers could be run instead of read. Unfortunately, few math papers actually come with working code; and even if they do the experiments presented therein are typically not reproducible (or modifiable) at the push of a button. Many important math software packages remain notoriously hard to compile and use. Moreover, a majority of mathematicians remains firmly attached to low-level languages, choosing small constant-factor improvements in speed over the usability, composability and readability afforded by higher-level languages. While Sage has done wonders to improve interoperability and usability of mathematical software, the mathematical community is still far away from having a vibrant and open ecosystem as available in statistics. (There is a reason why package managers or a corner stone of any programming language that successfully fosters a community.) In order to make papers about algorithms actually usable and to achieve the goal of reproducible research in experimental mathematics, we should:

  • Publish the software we write. This includes publishing the scripts we use to run our experiments in order to make the easily reproducible.
  • Write software to be used - even outside of our own office. Invest the time to polish and document code.
  • Use common package repositories to publish software, not just the personal home page.
  • Prefer high-level languages over low-level languages to make our libraries easier to reuse and our code easier to read and modify.
  • Make software easy to install.
  • Make coding part of the pure math curriculum, not just part of applied math.

Theorems and proofs are the main subject of the vast majority of pure math papers - and we do not consider them as data. However, opening up theorems and proofs to automatic processing by making their semantic content accessible to computers has vast potential. This is not just about using AI to discover new theorems a couple of decades in the future. More immediate applications (in teaching as well as research) include using computers to discover theorems in the existing literature that are relevant to the question at hand, to explore where a proof breaks when modifying assumptions, to get feedback while writing a proof about the soundness of our arguments or to verify correctness after a proof is done. The automatic and interactive theorem proving communities have made tremendous progress over the last decades, and their tools are commonly used in software verification. To be able to apply these methods in everyday mathematics, we should:

  • Develop formal tools suitable for everyday use by working mathematicians (as opposed to experts in software verification or formal methods).
  • Start formalizing parts of the mathematical articles we write.
  • Create the infrastructure to publish and integrate formal content with prose articles.
  • Explore the use of formal methods in teaching mathematics.

Mathematics for people

The points mentioned so far focus on making mathematical knowledge more accessible for computers. How can we make mathematical knowledge more usable for humans?

First of all, there is of course the issue of accessibility. From screen readers to Braille displays and beyond, there is a wealth of assistive technologies that can benefit from mathematics published in modern formats. For example, MathML provides richer information to assistive technologies than do PDF documents. Adopting modern formats and publishing technology can do a world of good here and have many positive side-effects, such as making math content more readable on mobile devices as well. But even assuming a readers are comfortably viewing math content on a desktop screen, there is a lot of room for improving the way mathematical articles are presented.

Communication depends on the audience. Math papers are generally written for other experts in the same field of mathematics, and as such, their style is usually terse and assumes familiarity with facts and conventions well-known to this core audience. However, a paper can also be useful to other readers who would prefer a different writing style: Researchers from other fields might prefer a summary that briefly lays out the main results and their context without assuming specific prior knowledge. Students would appreciate a wealth of detail in the proofs to learn the arguments a senior researcher takes for granted. Newcomers could benefit from links to relevant introductory material elsewhere. And everyone appreciates richly illustrated examples.

A single static PDF document is not the best tool for achieving all of the above objectives at the same time. By experimenting with dynamic, interactive documents, we can create articles that are more useful to a wider range of audiences. Documents could be “folded” by default, giving readers an overview first and allowing them to drill down for details where needed, possibly all the way to a formal proof. Examples could be presented side-by-side with the results they illustrate instead of the two being interleaved in a linear text. Software can enable readers to dynamically rearrange the text, for example by “pinning” definitions from the preliminaries to the screen while working through the proofs. Procedurally generated figures can be modified and explored interactively. Algorithms can be run and their execution observed - and articles could even be used as libraries from other software. Social annotation frameworks can allow readers everywhere to engage in a dialogue.

As soon as we leave the printed page behind us, the possibilities are endless. However, for these visions to fulfill their potential, openness is key. In particular:

  • File formats have to be open and not proprietary. Everyone has to be able to create their own software for reading and writing these files.
  • File formats have to be easily extensible, so that everyone can experiment with what a “document” can be.
  • It should be possible to inspect a document to learn how it was written. (Think “show source” on a web page.) This way, authors can learn from each other by default.
  • There is no reason why there should be separate software programs for “reading” and “writing” a document. The transition from “reading” to “working with” to “building on” can and should be seamless.
  • Finally, licenses have to allow all of the above.

Conclusion

Open data matters for pure mathematics. Taking open principles seriously can transform mathematical research and make it more useful and relevant both within academia and in the real world.

To conclude, I want to add three more thoughts:

  • Intuition is a form of mathematical knowledge that I have not mentioned so far. In my view, it is the most important one, but at the same time it is by far the most difficult one to convey in writing. The best way to communicate intuition is through dialogue. Intuitive explanations on a printed page can confuse more than they help, which is why they are often excluded from published papers. Dynamic documents can offer new room for experimenting with intuitive explanations - this cannot replace interaction in person, but which can be very valuable for anyone without access to an expert in the subject area.
  • Open science and open mathematics have to be at least as much about education as they are about research. Open data that requires a team of data scientists and a compute cluster to make use of may create huge value for industrial applications, but excludes a large part of society. One of the key tenets of open knowledge is that it should be open to everyone. Being open to everyone is not just about licenses and price, however. It also means giving everyone the means to benefit from these resources. Open mathematics should empower not just experts, but learners at all levels.
  • Making even a tiny fraction of these ideas happen will require a huge amount of work, and this work does not come for free. Making one math paper open means that a second paper is not going to get written. I think this is a worthy investment and creates far more value for society. However, as long as the academic job market values publication counts above everything else, this may not be a wise choice for many, career-wise. The transition to open mathematics will require both young researchers who are willing to take that risk and academic search committees who value innovation.

Here is how to fund Open Textbooks and MOOCs

Open textbooks and MOOCs are the way of the future. Yet, traditional business models, from donations to sales, do not suffice to make the full breadth of educational content open to everyone. Fund I/O is the business model to fill this gap.

It is simple, really: the more people have access to an educational resource, the more can benefit from it. In an age where copying has almost zero cost and education becomes increasingly important, open textbooks and open online courses seem like the obvious way to go. However, the question how open educational resources can be funded remains unanswered.

The classical approach is to sell educational resources for profit. However, the price of textbooks is skyrocketing, instead of going down. Reasons are publishers’ profit interests, market failure (professors choose textbooks, but students pay), high production costs (both for content and for printing hardcopies) and the increase in the number of students’ buying used textbooks, renting textbooks and downloading unlicensed digital copies (aka “piracy”) to avoid paying the full price. These trends lead to publishers pricing their textbook out of the market and are thus self-reinforcing. Clearly, the traditional business model is not sustainable.

The alternative way to fund educational resources is through donations. This can take many forms. Professors may choose to devote their time to write a book (or produce an online course) for free. Governmental agencies or private foundations may provide grant money. Companies may sponsor a course (in exchange for some form of advertising). Or a fundraising campaign could gather donations from the interested public. If donations suffice to fund an open textbook, that is great. However, except for a few high-profile examples, donations won’t suffice to support high-quality educational publishing in its full breadth. (In fact, there is a theorem which, roughly, says that, if people behave rationally, the amount of money that can be raised for open content through donations is just the square root of the amount that can be raised through sales, i.e., \$1.000 instead of \$1.000.000.)

Crowdfunding is a new funding model that is working spectacularly well in the entertainment industry. While crowdfunding has yet to be tried at scale for funding open textbooks, there are two reasons why current reward-based crowdfunding models will not be a viable option for educational publishing in general. First, most successful crowdfunding projects do not promise the creation of open content. Instead, their success is critically tied to the exclusivity of rewards. Second, crowdfunding projects are typically carried by high-tier backers who pay exorbitant amounts for token rewards. While it stands to reason that the hard-core fans of an artist will happily donate large amounts of money in exchange for a casual meet-and-greet, it is hard to imagine students paying huge sums to meet their textbook authors.

Enter Fund I/O. Fund I/O is a new kind of business model that can provide access to textbooks to as many people as possible while at the same time covering the cost of production. The model is independent of donations and maximizes access instead of publisher profits. Moreover, Fund I/O provides a smooth transition towards making the textbooks open to everyone, according to a transparent mechanism.

An illustrated introduction to the Fund I/O model is given here. In a nutshell, the idea is this:

  • The more students buy the textbook, the lower the price.
  • As the price drops, early buyers receive a full refund for the price difference. So nobody has an incentive to wait with their purchase.
  • When the price reaches a minimum value, the textbook is made free for everyone.

In particular, students (or universities, or libraries) can pledge how much they are able to pay for the content. If enough students pledge that amount, the price will drop automatically. In this way, students can determine the price of educational content.

From the publishers’ point of view, the deal looks like this: Publishers limit their profits to a fixed maximum amount, right from the outset. In return, they greatly reduce their financial risks and give their customers a rational incentive to reveal how much they are truly willing to pay for the content. By giving publishers and their readers a mechanism to communicate rationally about price, Fund I/O resolves the vicious cycle of publishers charging ever more and customers finding new ways to avoid paying.

In short, whenever donations or ads do not suffice to cover costs, Fund I/O is the business model to use for funding content that serves a common good.

A different way to fund websites, web services and software development

In the age of the Internet, it is difficult for websites, web services and software developers to monetize the value they create. Most customers are extremely price sensitive and try to pay as little as possible for software or web services provided through software.

The prevalent business model is to provide a basic, ad-supported service for free and to charge for the full-featured service. Rates of conversion from the free to the premium service are generally low, and ads do not pay much per impression. As a result, such services are only sustainable if they reach massive scale quickly.

These economic constraints shape the software services we use - often not in a good way: Software that could run perfectly well as a standalone application is turned into a web service to funnel traffic past advertisements. Services that would work perfectly well for a small group of users are turned into yet-another social network, in order to advance scale through network effects. Companies put the interests of advertisers before the interests of their users, because advertisers are where the money comes from. User data offers additional revenue streams at the expense of user privacy. And software that caters to niche markets cannot be financed, even if the value created for its users would cover the costs of development.

Many of these constraints are not facts of life, but simply a feature of current business models. In this post I describe a radically different business model, dubbed Fund I/O for web services, that provides incentives for users to finance the development of software products and web services directly. This model is based on the Fund I/O mechanism, and provides one key feature: it gives developers and users a rational mechanism to communicate about price.

Key Benefits

Fund I/O for web services offers a number of advantages for both users and developers.

Advantages for users

  • Users get access for the lowest possible price, that covers the cost of providing the service.
  • Users can pledge how much they are willing to pay. If enough users pledge, the price of the service will go down.
  • Early adopters receive a refund as the price goes down. Everybody pays the same price, nobody overpays.
  • Users pay only for what they use. If a user ends up not using the service after they sign up, they won’t pay anything.
  • Users have full cost control. They never pay more than their pledge for a subscription period, no matter how much they use the service.
  • By supporting developers directly, users know that the company has the economic incentives to serve their interests over the interests of advertisers or investors.

Advantages for developers

  • Costs are covered through revenues. No need to finance operations through equity or debt.
  • Fund I/O is optimized for growth. Prices are set automatically to maximize the number of active users, while costs are covered.
  • Customers reveal how much they are willing to pay for the service, providing invaluable market data.
  • Fund I/O provides incentives for price-sensitive customers to support the service financially and stop free-riding.
  • Developers can focus on creating value for their customers, instead of worrying about placing advertisements or maximizing profit.

Fund I/O for web services creates a playing field that is radically different from the current model centered around VC capital, ads, freemium services and massive scale. As such, it caters primarily to web services for which the current model is not a good fit. Fund I/O is a great choice for web services that:

  • do not have the scale neccessary to support itself through ads or sales of premium features,
  • cannot be supported through donations alone, or
  • do not have the venture capital to support years of operations at a deficit.

How it works

Fund I/O for web services is around the following three assumptions about the behavior of the majority of users with regard to web services and software:

Users want to pay as little as possible. Here, the Fund I/O model subscriptions can be of tremendous value, as it gives users rational incentives to reveal their true valuation for the product or service. This is in contrast to a classical sales context, where users would understate their true valuation and, e.g., opt for the free tier of a service, even if the value they obtain from the service exceeds the price of the premium tier.

Users do not want to buy something they do not know. Most software products and web services are not commodities. They cannot be perfectly substituted. Instead it depends on the particular characteristics of a given software product whether a user will want to work with that software at all. Thus, users avoid making a significant up-front investment without trying the product first. However, even after a trial is over, relatively few users make a purchase. In short, discontinuities in spending turn away users. A simple solution is to adopt a simple rule: Charge users in proportion to their actual usage.

Users do not want to constantly monitor their usage. Hence the popularity of flat rate offers for all kinds of services. Therefore, users should be charged in proportion to their actual usage, but only up to a fixed total amount. This way, users have peace of mind, even if they do not pay attention to how much they are using the product.

Here is an example how this could work in practice. Suppose a company wants to develop an HTML5 web app. It needs \$10,000 per month for developer salaries. To keep things simple, let us assume that on top of that, additional hosting costs are \$1 per user per month of non-stop usage. However, the average user would use the app for about 30 hours per month, which amounts to average hosting costs of about 5 cents per user per month.

The pricing now happens as follows:

  • Development cost are distributed equally among all users, according to the Fund I/O for subscriptions model.
  • A user counts only as a “full user” when they used the web app for 20 hours or more in the current month. A user who just tried the web app for 2 hours would just have to pay for “one tenth” of the average development costs.
  • Hosting costs are passed on to the user directly. This boils down to a rate of less than 0.2 cent an hour, with an absolute maximum of \$1 per month.

Suppose the web app has a small but consistent user base of 1,000 “full” users, 500 occasional users at 10 hours per month and another 1,000 users who just stop by and look at the app for 1 hour. Then the app would have a total of 1,000 + 500 * 0.5 + 1000 * 0.05 users, which amounts to a total of 1,300 “full” users. Distributed evenly among them, the development costs amount to \$7.70 per user. So, the 1,000 full users are charged \$7.75. The 500 “half” users are charged \$3.87. And the 1,000 “window shoppers” have to pay 77 cents each. Just opening the app and looking at it for a couple of minutes would cost less than 10 cents.

Now, suppose over time the service grows by a factor of ten, so that we have 10,000 full users, 5,000 half users and 10,000 window shoppers. Then the respective price would drop to \$0.77 + \$0.05 = \$0.82 for full users, \$0.385 + \$0.02 = \$0.41 for half users and 8 cents for window shoppers. Just looking at the app for a couple of minutes would cost just 1 cent. The tremendous economies of scale inherent in web apps are passed on entirely to users. Moreover, the Fund I/O concept of average cost pricing and refunds as prices drop mean two things:

  • Users can pledge how much they would be willing to pay for the service, even if their pledge is below the current price. When enough users pledge, the price will go down.
  • To compensate early adopters for their investment in the service, a part of the revenues can be passed on to them as a refund for the premium they paid early on. The golden rule is that within one subscription period, everyone pay the same price for the service, no matter when they join or how much they pledge. There can also be transfers across subscription periods, for example if version 1.1 of a web service builds on version 1.0, for which early adopters paid a premium.

Of course this is not the end of the story. There are many variations that can be used to tailor this protocol to particular use cases. (See this list of posts for more details on these variations.)

  • To price-discriminate low-valuation from high-valuation customers, web services can offer tiered subscriptions where the upper tiers are tied to a higher base cost. The higher tiers can include dontations made in exchange for special rewards. The lower tiers can include an ad-supported free tier; however, as a free tier decreases the incentive for users to participate in the pricing mechanism, this is not recommended.
  • Producers can choose the cost function such that they make a limited profit if the service becomes popular. * Stretch goals can be used to achieve specific growth targets and provide funding for additional features.
  • The fact that prices drop over time can be used to create a smooth transition to a release of the software developed under an open source license. (See here and here for more on Fund I/O for free software.)

Conclusion

Fund I/O for web services is a business model that breaks with many of the conventions we currently take for granted in the internet economy. At the heart of the model is a transparent mechanism for users and developers to communicate rationally about price. Users actively shape the pricing of the web service through the very payments they make. Developers cover their development costs while reducing their dependence on advertisers and venture capital. Fund I/O for web services makes web services for niche audiences sustainable and at the same time provides them with a smooth transition to serving mass audiences if they become popular. Finally, Fund I/O offers a flexible toolbox that can be adapted to many different use cases.

Fund I/O offers a felxible toolbox of concepts for designing innovative business model, and it is just the beginning: There is plenty of room for disrupting the internet economy.

A Business Model for Crowdfunding Subscription Services

Fund I/O is a model for funding the production of any type of good with massive economies of scale. In its basic version, Fund I/O is intended to finance fixed costs that only apply once, such as the one-off cost of writing a book. (See here for an introduction.) However, many important goods and services incur fixed costs on a recurring basis. Examples include ongoing software development, research or journalism. These services require financing a staff of people to produce new software releases, white papers or articles on a continuing basis. However, once a given release/paper/article is produced, it can be distributed to an arbitrary number of people at a vanishingly small marginal cost. Thus the basic Fund I/O concept still applies.

A variant of Fund I/O that finances ongoing fixed costs is the following subscription model. Of course, each particular use-case will require further tweaks, but the basic model is this.

  • Each period creates new fixed costs. A period can be a time interval or a new release. An example would be \$5,000 every month.
  • Each customer submits a pledge for how much they would be willing to pay each period for access to the subscription. Let’s assume that on June 1st there are 100 people who submitted a pledge of \$50 or more, and a few more who pledged less than \$20.
  • The price is chosen as low as possible such that the costs are covered. Costs are distributed evenly among all subscribers who get access. In the example, the price would be set \$50 and the 100 people who pledged at least as much receive access for the current month of June.
  • As more subscribers sign up the costs drop. Say, another 100 people pledge at least \$25 by June 5th, then the price drops to \$25 and these 100 people receive access to the subscription for the month of June.
  • Previous subscribers are refunded the price difference. Each of the original 100 subscribers receive \$25. This can either be a cash refund or a credit that can be applied to the next months’ subscription fees.
  • Pledges remain active across periods. So if nobody changes their pledge, the subscription will cost exactly the same amount every month.

Just as in the case of one-off payments, the Fund I/O model has a number of advantages over classic subscription models.

  • Customers have an incentive to reveal their true valuation for the product.
  • The subscription is provided at the lowest possible price to the largest possible audience, while costs are covered.
  • Customers determine the price of the subscription through a transparent mechanism.

The subscription model described above can serve as a foundation for many different variants.

  • Rolling subscriptions can be incorporated into the pricing scheme. One customer can subscribe for June 1st till July 1st while another subscribes from June 5th till July 5th.
  • “Stretch-goals” can allow customers to determine the scope of the subscription through their pledges. If pledges are high enough to provide \$10,000 per month, another staff member can be hired, for example.
  • Periods can build on each other. Subscribers to version 1.0 of a software package can get refunds from sales of version 1.1, as the development work put into 1.0 clearly benefits 1.1.
  • And, of course, a share of the revenues can go to the producers as profit beyond the fixed costs for each month. These profits can serve as capital to provide funding for months with insufficient subscriptions.

Bottom line: Fund I/O is well-suited to subscription services. In the next post, I will go into detail on how this can be used to fund web services.

Funding Vaccine Production

Fund I/O can be extremely useful in funding projects with a social or environmental impact: producing vaccines, for example. One challenge of vaccine production is getting the market for a new vaccine to scale to the point where the vaccine becomes affordable. Because prospective buyers expect prices to drop, many will wait with their purchase, which may even prevent the market from reaching the required size. Fund I/O offers an original solution to this problem, by giving buyers incentives to buy now. This can provide a viable alternative to difficult-to-negotiate advance market commitments.

Fund I/O can be used not only for digital goods, but for anything that has large fixed costs and low marginal costs. This includes physical goods that have a large social impact, such as vaccines. Here is how this might work.

Suppose a vaccine for a certain disease has already been developed. Now it needs to be produced at scale to reach millions of people world wide. The problem is vaccine production requires a substantial investment to get going. This means, if a supplier were to produce just 100,000 doses of the vaccine, each dose might be prohibitively expensive. But at a scale of 10 million doses, each dose could be very cheap. As long as the market is small, the price for the vaccine will be very high so that only few people will be able to afford it. But once the market grows, the price will drop, and many more people will be able to afford the vaccine.

This creates a chicken and egg problem: To get the price down, many people would need to buy the vaccine. But for many people to buy the vaccine, the price would need to drop. So how can we get the market started?

One approach to getting the market started are advance market commitments. A couple of large buyers of the vaccine, such as governments or charitable donors, make a joint commitment to buying a large number of doses at a specified price. The idea is that by guaranteeing a certain demand for the vaccine in advance, the market can be jump-started at a volume attractive to suppliers and at a price attractive to buyers.

There is a catch, however: Because, the price for the vaccine will drop over time, buyers have an incentive to wait. Those who start buying early will pay a premium. It you wait, you pay less, and the later you get in, the more you save. Even if everyone wants to buy the vaccine, those who manage to start buying last will pay the least. Early adopters effectively subsidize late entrants.

You can imagine that this leads to quite a lot of maneuvering over who gets to be the last. Especially because the market for governments buying vaccines has several features that exacerbate the problem: First, very large sums of money are at stake. Second, buyers (such a governments) are often frugal, by necessity. Third, implicitly subsidizing other parties may be unpopular, even if it is for a good cause such as getting more vaccines to more people. And finally, the only benefits of entering early are measured in terms of impact (saving lives) and not profit (return on investment), which often makes spending money harder instead of easier - unfortunately. Advance market commitments can help a lot in this setting: by forming a coalition of first movers, the financial disadvantage to buying early is reduced considerably. But the incentive to get in later remains, and this makes it often very hard to establish such a coalition.

Here Fund I/O can help. In fact, Fund I/O was designed to solve exactly this chicken-and-egg problem. Using Fund I/O, buyers do not have an incentive to wait. To achieve this, all you need to do is apply the refund mechanism used in the second phase of the Fund I/O model. Buyers can purchase immediately and still benefit from economies of scale as the market matures. Through the refund mechanism, they can rest assured they will benefit from decreasing prices in just the same way as a late entrant.

This solution makes jump-starting markets much easier, by offering a smooth transition from a low volume/high price market to a high volume/low price market. Moreover, it does not require complicated negotiations aimed at getting buyers to commit to making purchases now, even though it would be in their financial interest to wait. The Fund I/O mechanism guarantees the same financial benefits as an advance market commitment involving all potential buyers, present and future, but it can be set in motion by just a few interested parties right away. Agreements are not made at a negotiating table but on a platform of exchange that incentivises all participants to reveal their true valuation for the vaccine.

Of course there are many more details to be addressed here, both as far as the theoretical model and practical issues are concerned. But these general considerations already make clear the Fund I/O shines at resolving difficult negotiations of this type by intermediating price differences across time.

A Crowdfunding Model for Open Source Software?

I think we need more crowdfunding projects for open source software! And here is one, for example: Yorba, the guys behind Shotwell, are currently running an Indigogo campaign to fund the development of their open source email client Geary. As of this writing, they have raised about \$50,000 of their \$100,000 goal and the rush of the last 24 hours has just begun. So, please head over there now and consider making a dontation. You can always come back here to read on!

Why Funding Open Source Software is Difficult on Kickstarter

Crowdfunding has taken off, for physical goods as well as for software-related products like games. So why do we see so few open source project take advantage of crowdfunding? In fact, Kickstarter is based on the Street Performer Protocol (SPP), a method for raising funds that was originally intended as a model for financing open source software, and that had some early successes such as making Blender open source. Could it be that rewards-based crowdfunding as on Kickstarter simply does not work as well for open source software?

There is one subtle difference between open source and closed source projects on Kickstarter, and this difference may be crucial: The successful game projects on Kickstarter have no intention of giving away their core product for free. This makes pledges pre-sales instead of donations. Open source projects on the other hand announce right away that their product is going to be free. Does this influence backer behavior?

It is certainly true that many crowdfunding campaigns are successful because some altruistic backers pledge huge amounts of money to the project - much more than they would need to pledge to get a copy of the product for themselves. But projects rarely can be funded through such altruistic contributions alone. Take a look at Shrouds of the Avatar, for example: the large majority of backers pledged the minimum amount required to receive a copy of the game. These backers are obviously price conscious and don’t pledge more than they have to. I will call these backers rational, in the economic sense. This means that they are self-interested and act to maximize their own welfare.

This leads me to the following working hypothesis:

Crowdfunding projects need contributions from both rational and altruistic backers to raise large amounts of money.

This would explain why open source projects appear (so far) to be less successful than other creative projects at raising money via crowdfunding: Because open source software is (going to be) free, rational backers don’t pledge anything.

In fact, there is research in the economics literature on the optimal behavior of an entirely rational backer who is faced with the decision of backing an open source project. The amount he or she is willing to pledge is determined by the probability of their pledge being pivotal and getting the project funded. Backers correctly observe that this probability decreases with the total number of backers interested in a project. A consequence is that - if all backers were rational - the amount of money open source projects can expect to raise grows only proportional to the square root of the number of people interested in the project. In contrast, the amount a closed source project can raise grows linearly in the number of people interested in the project. This can quickly lead to a difference of several orders of magnitude!

(Now, before anyone gets a wrong impression: I do not think that people behave entirely rationally or that they should behave rationally. It is vital for our society that people act out of altruistic motives. And it is great that crowdfunding has found a way to get altruism to scale, so that we can make great things happen. I think we should look for more ways in which we can integrate altruism into our economic activities. All I am saying is that there is a reason that our entire economic system is built on the assumption that people tend to behave rationally. Our goal should be to find economic models that incorporate both altruistic and rational motives.)

Fund I/O as a Model for Funding Open Source Software

Fund I/O is a new crowdfunding model based on the Average Cost Threshold Protocol (ACTP). (If you are not yet familiar with Fund I/O, you may want to check out this example before continuing here.) When I developed the ACTP, one of my goals was to find a crowdfunding model that would work for open source software. And in many ways Fund I/O achieves precisely that:

  • Most importantly, Fund I/O gets rational backers to reveal how much they would truly be willing to pay for the software.
  • This allows open source project to raise as much money as closed source projects.
  • Moreover a project can raise more money on Fund I/O than using the Kickstarter model, because it lets the market determine the optimal price of the product.
  • At the same time, Fund I/O still allows altruistic backers to dontate as much as they want to the project. (This requires Fund I/O to be used with the option of allowing each backer to set their own minimum price level.)
  • Finally, Fund I/O provides a clear path towards the relase of the software product under an open source license.

Now, you may have noticed that I did not quite say Fund I/O “works” for open source software. In fact, I do not think the Fund I/O model gives me everything I would personally want from an open source funding model. However, I do think it works much better than anything that is currently out there. So let me first explain in what way it does work for open source software. In the next section I will then go on to explain the limitations I see.

Fund I/O works great for open source projects if your project meets the following assumptions:

  • Your goal is to finance the creation of version 1.0 - no more.
  • You are willing to release your software under a closed license at first.

Then you just run through the three phases of the Fund I/O mechanism (with individual minimal price levels) and at the end:

  • you have completed the software you wanted to write,
  • you have released the software and its source code under an open source license, free for everyone to use and modify,
  • your costs were covered right from the start and
  • you even made a certain profit that you can determine in advance.

The release under an open source license happens if and only if there is enough altruism among your customers to finance the costs of production through voluntary donations. However, this absolutely not the same as simply using the SPP. First of all, your project gets made if there is enough rational interest in your software. It just won’t be open sourced unless there is enough altruistic interest. Second, Fund I/O achieves a smooth transition from the state where there are few users who would need to donate very large amounts to the state where there are many users who need to donate just a couple of dollars. This lessens the burden on any individual donor considerably. Moreover, the donation is a sunk cost for the customer: donating means forgoing future refunds instead of paying money now. All of these factors make it much easier to gather the required donations, than using the SPP, even if Fund I/O is used with individual minimal price levels. If a fixed minimal price level is used for everyone, then gathering the required donations gets easier still.

Caveats

Now, I believe the above could work great for developing, say, an open source game. But for open source software I see a couple of caveats.

First of all, the user base of the software has to be willing to use closed source software during the second phase of the protocol. If a substantial number of users will never run anything but free software, then you are of course out of luck. I do not think this will be a problem; it was not a problem for Light Table during its crowdfunding campaign.

Second, it has to be reasonable to make the software non-free during the second phase. This means that the software is for sale and according to the license users are not allowed to pass copies of the software along to their friends. This is a stronger restriction than just not releasing the source code and may turn off more of the free software crowd. More importantly, this limits viral marketing effects during the crowdfunding and sales phases. People have to buy the product to try it out. (Even though a demo could certainly be offered.)

Of course the whole point of Fund I/O is that because of the refund mechanism, there is less of a disincentive to buying than in a classical sales context. In particular, if a customer sets their minimal price level to zero, then they get a full refund in case the software is released as open source. But in a world where many people expect application software (as opposed to games) to be free, this may be a hurdle. I’d be optimistic and say that the compromise of making software non-free for a limited amount of time, according to a transparent mechanism, in order to cover the costs of development is convincing enough to assuage these concerns.

Finally, and most importantly from my point of view, software requires maintenance. Application software needs to be developed continually. A game may be “done” after the 7th patch or so, but application software never is. If the only goal is to fund the creation of a version 1.0, then this is not a problem. But what if you are looking for a way to finance the development of open source software throughout its entire lifecycle?

An obvious modification to Fund I/O for financing several consecutive versions would be to run a new campaign for each major version. The mechanism could easily be adjusted to make a part of the revenues from the version 2.0 sales refunds for version 1.0. And once 1.0 is free, buyers/backers of subsequent versions could stop paying refunds to version 1.0 owners. The problems I see with this are therefore not theoretical, but practical in nature. The company developing the software would have to maintain several versions of the software side-by-side, they would have to backport security patches and provide support, and they would have to finance these activities from their version 2.0 revenues. While all of these concerns appear in commercial (and open source) software development anyway, they are exacerbated by keeping different versions under different licenses around - just because of the funding scheme.

Ultimately, it will depend on the particular project which of these considerations are relevant, and which variant of Fund I/O makes the best fit. Personally, I view Fund I/O as a toolbox that can be tailored to fit many different needs.

Conclusion

I hope to have convinced you that crowdfunding open source software is possible at much bigger scale than we have seen so far. What we have to do to make this happen is to find a crowdfunding model that takes the backers’ diverse patterns of economic behavior into account. I think Fund I/O is a step in the right direction, but can certainly be improved upon with regard to funding open source software.

What do you think would be the challenges when applying Fund I/O to open source software? How would you modify Fund I/O to make it more applicable to open source software? Comments and questions are welcome!

A different way to think about business

Throughout my conversations about Fund I/O over the past couple of weeks, one thing has become clear: Fund I/O implies a radically different way of thinking about business.

What is the Fund I/O business model? Fund I/O is a business model for the production of goods with substantial economies of scale. In a nutshell:

  • Financing is provided through presales made during a crowdfunding campaign.
  • The producer commits in advance to a pricing scheme that passes savings due to economies of scale on to customers directly, by lowering prices as fast as possible.
  • Early buyers are guaranteed to get a refund when the price drops, so that they have no incentive to wait with their purchase.

If you are looking for details, good places to start are fund-io.com and this example.

What makes Fund I/O different from the conventional way of doing business? Suppose you run a company and want to produce a product that benefits from economies of scale. Here is what Fund I/O means to you:

  • You finance your product entirely through presales. You do not have take on a loan, you do not have to pay interest, and you do not have to maximize profit for your investors. This drastically reduces your risk and your cost of capital. The presales appear as a non-interest bearing liability on your balance sheet, and the primary interest of your financiers is to receive a great product, not to get paid.
  • You place an absolute limit on the profit you can make off a product. This limit can be chosen arbitrarily, but by choosing a refund scheme you are committing to an absolute limit on your profits. Note that because you used presales from customers to finance production you are making a profit without having invested any capital yourself, so from that point of view your return on investment is infinite, even if your maximum profits are not!
  • You obtain a tremendous amount of market information: By committing to a refund scheme, you give your customers an incentive to reveal exactly how much they are willing to pay for your product. This translates into higher sales, more revenue and faster growth.

Through the combination of crowdfunding, a clear price reduction scheme with a limit on profits and a refund mechanism, Fund I/O manages to align the interests of key stakeholders and it provides them with a mechnism to communicate truthfully about value: It resolves the fundamental conflict of interest between investors who want to maximize their profits and customers who want to minimize what they have to pay.

What makes Fund I/O different from other crowdfunding schemes? There are basically two different crowdfunding models out there: reward-based crowdfunding and equity crowdfunding.

Equity crowdfunding is not that different from the conventional business model. Financiers are still interested in return on investment. The key difference is that investors often have another stake in the business in addition to their profit interests. For example, they may be not only investors but customers at the same time, or they may have an interest in the social impact of the business. But still the business is obliged to maximize profits on behalf of its investors, which gives customers incentives to understate their valuation of the products the business is offering.

Reward-based crowdfunding makes customers the financiers of a product, aligning the interests of two key stakeholders. But it still does not provide a mechanism to communicate about value. In reward-based crowdfunding, creators have to fix the price a priori and often a majority of backers pledge just this price and no more. The success of reward-based crowdfunding hinges on the generosity of backers who self-select for price targeting by willingly paying a large premium for the product. This type of altruism (whether motivated by appreciation of the project, the thrill of being part of something great or the enjoyment of receiving secondary merchandise) is great, if it suffices to finance the project. Fund I/O can be tweaked to captialize on this type of gift economy as well, but the main contribution of Fund I/O lies elsewhere: Fund I/O makes crowdfunding work in cases where the capital requirements of a project are large or where the potential customers are price sensitive. Fund I/O provides the mechanism that allows producers and customers to join forces in order to create great products, even if all parties involved need to avoid paying more than they have to.

What problem does Fund I/O solve? From the point of view of a business, Fund I/O reduces risk, aligns interests of stakeholders, provides a wealth of market information and generates more sales. Moreover Fund I/O provides financing alternatives to debt and equity and conventional crowdfunding. This is particularly useful in cases where debt and equity are too expensive, too risky or simply unavailable and when altruistic contributions made through a rewards-based crowdfunding campaign do not suffice.

However, this is just one angle on the question: “What problem does Fund I/O solve?” Over the next days, I will post other answers, taking the point of view of a customer, or examining the applicability of Fund I/O to non-profit projects aimed at social impact. One very technical answer is already written up: Fund I/O provides a practical implementation of an incentive compatible, individually rational mechanism for the private provision of excludable public goods that is asymptotically optimal.

Introducing Fund I/O

Fair crowdfunding has a new home: Fund I/O.

Fund I/O

As you may have seen, I have been blogging recently about a new crowdfunding mechanism for public goods, the Average Cost Threshold Protocol. Since the last post on the topic, I have spent quite some time discussing this idea with people, and have decided to give this idea into a project dubbed Fund I/O with an own website fund-io.com and an own Twitter account.

To get updates about his project and idea, you can subscribe to a (very-low volume) mailing list on the project website, or just follow this blog. I’ll keep posting whatever I have to say on the subject of fair crowdfunding on this blog. (If and when Fund I/O gets its own blog, I will make an announcement here.)

Finally, in case you are wondering, Fund I/O is not a startup. (Not yet, anyway.) The current goal of Fund I/O is to try some variant of the ACTP in practice. If you have got just the right project in need of a revolutionary funding mechansim, let me know!

Visualizing the GCD

There are many beautiful geometric interpretations of the GCD and visualizations of the Euclidean algorithm out there, see for example here, here and here. I have written about this myself some time ago. But I find that some of the pictures become much clearer when lifted into the third dimension.

[Note: I am using Sage Cells to produce the pictures in this post. This has the advantage that you, dear reader, can interact with the pictures by modifying the Sage code. However, this will probably not run everywhere. It certainly won’t work in most RSS readers…]

Here is the graph of the GCD! First a little static preview…

Graph of the GCD

… and now a proper interactive graph. Be sure to rotate the image to get a 3d impression. (Requires Java…)

def mygcd(a,b,depth=0): if a > b: return mygcd(a-b,b,depth+1) if a < b: return mygcd(a,b-a,depth+1) if a == b: return [a, depth] def drawgcd(boxsize=10): M = boxsize s = Set([QQ(p)/QQ(q) for p in xrange(1,M) for q in xrange(1,M)]) lines = [] for x in s: p = x.numerator() q = x.denominator() l = min(M/p,M/q) [gcd,depth] = mygcd(p,q) lines.append(line3d([(p,q,1),(l*p,l*q,l)], rgbcolor=Color(depth/M,1,0.8,space="hsv").rgb())) return reduce(lambda a,b: a+b, lines) drawgcd(10)

What precisely are we seeing here? The gcd is a function $\mathrm{gcd}:\mathbb{N}^2\rightarrow\mathbb{N}$. Its graph is a (countable) set of points in $\mathbb{N}^3$. This graph is precisely the set of integer points contained in one of the (countably many) lines indicated in the above picture. The value of the gcd is given by the vertical axis.

Now, what are those lines? Suppose $a$ and $b$ are two natural numbers that are relatively prime, i.e., $\gcd(a,b)=1$. Then we know that $\gcd(ka,kb)=k$ for any positive integer $k$. So all (positive) integer points on the line through the origin and $(a,b,1)$ are in the graph of the gcd. Conversely, for any numbers $x,y$ with $gcd(x,y)=z$, we know that $\gcd(\frac{x}{z},\frac{y}{z})=1$, that is, the point $(x,y,z)$ lies on the line through the origin and $(\frac{x}{z},\frac{y}{z},1)$. So by drawing all these lines, we can be sure we hit all the integer points in the graph of the gcd.

What I find very beautiful about this is that when looking at this picture from the right angle, you can see the binary tree structure of this set of lines. It is precisely this binary tree that we walk along when running the Euclidean algorithm. The lines in the above picture are color coded by their depth in this “Euclidean” binary tree.

The version of the Euclidean algorithm I like best this one. Suppose you want to find $\gcd(a,b)=1$. If $a>b$, compute $\gcd(a-b,b)$. If $a<b$, compute $\gcd(a,b-a)$. If $a=b$, we are done and the number $a=b$ is the gcd. At each point in the algorithm we make a choice, depending on whether $a>b$ or $a<b$. If we keep track of these choices by writing down a 1 in the former case and a 0 in the latter, then, for any pair (a,b), we get a word of 0s and 1s that describes a path through a binary tree. As we walk from one pair $(a,b)$ to the next in this fashion, we trace out a path in the plane: For each 1 we take a horizontal step and for each 0 we take a vertical step. This path can look as follows.

a = 31 b = 19 def gcd1(a,b): # returns the gcd, a list of choices and a drawing if a > b: [gcd, path, drawing] = gcd1(a-b,b) return [gcd, path+[1], drawing+point2d([a,b])+line2d([[a-b,b],[a,b]])] if a < b: [gcd, path, drawing] = gcd1(a,b-a) return [gcd, path+[0], drawing+point2d([a,b])+line2d([[a,b-a],[a,b]])] if a == b: return [a, [], point2d([a,b])] [gcd,path,drawing] = gcd1(a,b) print "The gcd of %d and %d is %d." % (a,b,gcd) print "During the computation the Euclidean algorithm, makes the following choices:" print path drawing

Now comes the twist. We can turn the Euclidean algorithm upside down. Instead of walking from the point $(a,b)$ to a point of the form $(g,g)$ and thus finding the gcd, we can also start from the point $(1,1)$ and walk to a point of the form $(\frac{a}{g},\frac{b}{g})$ to find the gcd $g$. (Why $(\frac{a}{g},\frac{b}{g})$? Well, $(\frac{a}{g},\frac{b}{g})$ is the primitive lattice vector in the direction of $(a,b)$. In terms of the graph at the top, $(\frac{a}{g},\frac{b}{g},1)$ is the starting point of the ray through $(a,b,\gcd(a,b))$.)

How do we get there? We start out by fixing the lattice basis with “left” basis vector $(0,1)$ and “right” basis vector $(1,0)$. Their sum $(1,1)$, which I call the “center”, is a primitive lattice vector. Now we ask ourselves: is the point $(a,b)$ to the left or to the right of the line through the center? If it is to the left of that line, we continue with the basis $(0,1)$ and $(1,1)$. If it is to the right of that line, we continue with the basis $(1,1)$ and $(1,0)$ and recurse: We take the sum of our two new basis vectors as the new center and ask if $(a,b)$ lies to the left or to the right of the line through the center, and continue accordingly. If $(a,b)$ lies on the line through the center, we are done: the gcd of $a$ and $b$ is the factor by which I have to multiply the center to get to $(a,b)$.

As we follow this algorithm, we draw the path from one center to the next, until we reach $(\frac{a}{g},\frac{b}{g})$. Then we get the following picture. It looks almost like a straight line from $(1,1)$ to our goal, but it is only straight whenever we take two consecutive left turns or two consecutive right turns. Whenever we alternate between right and left, we have a proper angle, it only gets difficult to see this angle the farther out we get. If we write down a sequence of 1s and 0s, corresponding to the left and right turns we take, we get the exact same sequence as with the standard Euclidean algorithm.

a = 31 b = 19 def gcd2(a,b,left=vector([0,1]),right=vector([1,0])): center = right + left if b/a < center[1]/center[0]: [gcd, path, drawing] = gcd2(a,b,center,right) return [gcd, path+[1], drawing+point2d(center)+line2d([center,right+center])] if b/a > center[1]/center[0]: [gcd, path, drawing] = gcd2(a,b,left,center) return [gcd, path+[0], drawing+point2d(center)+line2d([center,left+center])] if b/a == center[1]/center[0]: return [a/center[0], [], point2d(center)] [gcd,path,drawing] = gcd2(a,b) print "The gcd of %d and %d is %d." % (a,b,gcd) print "During the computation the reverse Euclidean algorithm, makes the following choices:" print path drawing

The obvious next step is to draw the complete binary trees given by the above two visualizations of the Euclidean algorithm (up to a certain maximum depth). Drawing the first tree gives a big mess, because many of the edges of the tree overlap. You can clean up the picture by removing the lines and drawing only the points: In the code below comment the first definition of thisdrawing and uncomment the second. This then gives you a picture of all primitive lattice points (pairs of relatively prime numbers) in the plane at depth at most maxdepth in the tree.

maxdepth = 7 def drawtreehelper(a,b,parenta,parentb,depth): thisdrawing = [point2d([a,b]),line2d([[parenta,parentb],[a,b]])] #thisdrawing = [point2d([a,b])] if depth == 0: return thisdrawing else: return thisdrawing + drawtreehelper(a+b,b,a,b,depth-1) + drawtreehelper(a,b+a,a,b,depth-1) def drawtree(depth): return [point2d([1,1])] + drawtreehelper(2,1,1,1,depth) + drawtreehelper(1,2,1,1,depth) reduce(lambda a,b:a+b,drawtree(maxdepth))

The second variant of the Euclidean algorithm gives a much nicer picture, revealing the fractal nature of the set of primitive lattice points. The nodes of the tree, i.e., the points drawn in the picture are the starting points of the rays plotted in the 3d graph of the gcd given at the beginning of this post. In this way, this drawing of the tree gives the precise structure of the binary tree intuitively visible in the three-dimensional graph. One thing you may want to try is to increase the maxdepth of the tree to 10. (Warning: this may take much longer to render!) Note how far out from the origin some of the points at depths 10 are.

maxdepth = 7 unitmatrix = matrix([[1,0],[0,1]]) lefttransform = matrix([[1,0],[1,1]]) righttransform = matrix([[1,1],[0,1]]) thevector = vector([1,1]) def drawtreehelper2(basis,parent,depth): #thisdrawing = [point2d([a,b]),line2d([[parenta,parentb],[a,b]])] thispoint = basis*thevector #print thispoint,parent thisdrawing = [point2d(thispoint),line2d([thispoint,parent])] if depth == 0: return thisdrawing else: left = matrix return thisdrawing + drawtreehelper2(basis*lefttransform,thispoint,depth-1) + drawtreehelper2(basis*righttransform,thispoint,depth-1) def drawtree2(depth): return [point2d(thevector)] + drawtreehelper2(lefttransform,thevector,depth) + drawtreehelper2(righttransform,thevector,depth) reduce(lambda a,b:a+b,drawtree2(maxdepth))

The reader may have observed that the binary tree described in this post gives us a very nice way of enumerating the rational numbers. Calkin and Wilf made this observation in the paper Recounting the Rationals, whence it is sometimes called the Calkin-Wilf tree, even though Euclid tree might be a better name as it is given by the Euclidean algorithm itself. As we have seen above, a look through the lens of lattice geometry tells us how to draw this tree in the plane and how to find it in the graph of the GCD.