2012 Nobel Memorial Prize in Economics – Lloyd Shapley, Al Roth

For a popular article, see http://www.nature.com/news/a-nobel-for-the-art-of-matchmaking-1.11607#/ .

The goal of this post is to overview the basic problem of matching and give some examples of current/popular applications.

See also: Al Roth’s blog at http://marketdesigner.blogspot.com/ .

For some cool and more technical slides on market design, see Itai Ashlagi’s slides from the CMU Summer School on Algorithmic Economics, linked here: http://www.cs.cmu.edu/~arielpro/summer/schedule.html#itai .

Continue reading


Stealing, Copying, and the 4,000,000-Document Non-Theft

Recently, a young man named Aaron Swartz was arrested after an incident at MIT. Apparently, he had been using MIT’s network to download millions of documents from JSTOR, an online archive of scientific journal articles and the like. (Access to JSTOR is purchased by universities like MIT, and like Harvard, where Swartz is an employee).

What can this incident — and reaction to it — tell us about copyright in the U.S.? In this article, I’ll paint this incident as a symptom of larger copyright issues in our society. I’m not going to necessarily argue whether copyright is good or bad, but I will argue that public perception of copyright has been twisted away from all common-sense definitions — twisted by design. By the end, I hope to change the way you think about “intellectual property”, or at least cause you to consider how your views are shaped by the terms used in the debate.

Let’s start with Swartz.

Continue reading

Seven Reasons I Prefer Linux

We all like rants, right? Especially rants directed mainly against Microsoft (public enemy #1) and/or Apple (public enemy #2)? Of course we do. This is not a list of technical features. It has nothing to do with security or the free software movement. This is just a list of cosmetic, user-friendly features that Linux systems (or at least Ubuntu) get right — and certain big-name OSes get wrong.

1. In-Place Software Updates

With Ubuntu, updating is a piece of cake. There’s a single app, the Update Manager, that pops up with a list of all updates for my system and programs. When I click install, it doesn’t force me to quit any of my applications or (shudder) restart my system. It installs easily and quickly. This is directed at you too, Apple. I have a laptop so I can use it on the go. You think I want to restart my Macbook while I’m trying to take notes or look up directions? There never seems to be a good time to stop everything, quit everything, install, and wait to restart.

And there’s nothing worse than stopping what you’re doing, installing updates, restarting your machine, and immediately seeing this little guy pop up again:

2. Not Having To Babysit: Boot, Shutdowns, Installations

It’s bad enough when you set something to install, click through all the menus, and go take a break, only to come back and find out it’s still waiting for you to confirm that the program can make changes to your computer. What’s worse is when you have to remember to sit and watch your computer screen while it’s booting, in case it decides to try to “recover a drive – press a button to cancel”. (And what does that even mean?) Equally annoying is when you think you’ve shut your computer down, only to find out that it’s “Installing Important Updates (2 of 23)”. On Linux, when you start up the computer, it starts up. When you shut it down, it shuts down. When you hit install, the program is installed.

Also in this category: interruptions. Having some window pop up while you’re trying to watch a movie or edit a file can be anything from annoying (watching a movie, browsing reddit) to disastrous (giving a presentation, accidentally hitting the wrong button as it appears). It’s just a dumb idea, and Linux doesn’t do it.

3. Software is Free and Easy to Install

Ubuntu really shines here. If I need an application, it’s one click to the Ubuntu Software Center, a quick search, and then one more click to download and install. If the program I need is slightly more obscure, I can go to the command line and type “sudo apt-get install software“. Installed and done. Doesn’t ask me “Where do you want to save this file?” Doesn’t make me unzip, run the installer, select a directory, and configure options. Doesn’t make me restart my computer. One step.

4. Doesn’t Ask Me Dumb Questions

This goes along with the “allow this program to make changes to your computer” thing. For example, when I connect to my school’s wireless network, I don’t want to bother classifying it as Home, Public, or Work. In fact, I consider myself a moderately advanced user and I don’t even know the difference, much less care. This passes the level of minor annoyance when Windows recognizes the same network four times in a row as “Wifi 2”, “Wifi 3”, etc and presents me with a popup for each one repeatedly.

Similarly, I already know that my application is a “program you downloaded from the Internet” and yes, I’m “sure that you want to run it”. There’s probably a way to turn off all these idiotic questions and notifications, except…

5. Rational, Consistent Organization

If I want to change a system setting on Linux, I don’t need to have ever done it before. The menus and applications are organized logically (and everything is an application, so system settings are organized cleanly next to everything else).

On Windows, things aren’t so clear. I know I probably have to go into the Control Panel, but beyond that…. For instance, did you know that display settings are under “Hardware and Sound”, but disk partitioning is under “System and Security”? Who’d have guessed?

Meanwhile, folder setup and navigation are obfuscated in Windows, but consistent and logical in Linux. On Windows 7, if I download a pdf from my browser and just hit “save” without looking, it’ll take me 5 minutes of shuffling through folders and hierarchies to have a clue where it was saved. (C:\Windows\Downloaded Program Files? C:\ProgramData? C:\Users\myname\Downloads?) Plus, there are places (like the Control Panel) that can’t even be accessed from Windows Explorer. On Linux, it’s pretty clear where things belong, or at least it’s possible to narrow it down.

And the little things. I’m navigating through Windows Explorer, and I want to get the properties of the current folder. Turns out, that’s in the “Organize” menu. What? And here’s the one that made me decide to write this post: When I found myself googling the phrase “how to eject an external hard drive in windows 7.” No, I could not figure out how to do it on my own. This may be because I’m stupid, but stupid people use computers too; interfaces should be designed to be intuitive. It’s not hard to figure out how to hit the eject button in Ubuntu.

6. Sometimes, Windows is Just … Aaaargh

I don’t even know how to classify some of these. But let’s say I want to create my own wireless network. Here’s what happens to me in Windows 7. Hit the Network icon at the bottom right. Click on “Open Network and Sharing Center.” Click “Set up a new connection or network.” I’m faced with several odd options, but I’m pretty sure I want “Set up a new network (configure a new router or access point)”. Click it, hit next. It tells me to wait up to 90 seconds while it searches for unconfigured devices. Hmmm. Nothing appears. Nevermind, go back. Scroll down. Oh, ok: Click “Set up a wireless ad-hoc (computer-to-computer) network”. Hit next. Type a name, select “No authentication”, and hit next. Done! That’s 6 clicks (not counting where I messed up).

Ubuntu: Click on the little wireless icon. In the dropdown, select Create New Wireless Network. Type a name and hit Create. 2 clicks.

What about setting up sharing of files between computers? In Ubuntu, I right click on a folder and select “Sharing Options”. (It’s also not hard to figure out on a Mac.) On Windows, I try the same thing, but am stopped short — they want me to join a “Homegroup”? What is this, a network system designed by George Bush? “To create or join a homegroup, your computer’s network connection must be set to Home.” Thanks for the information, but I have no idea what you’re talking about. The options it gives me to click on are “What is a network location?”, “Tell me more about homegroups”, “Change advanced sharing settings…”, or “Start the HomeGroup troubleshooter”. None of these things is what I want to do (I want to share my files and folders). Sigh and give up.

7. Hack and Customize … At Your Own Pace

Linux is known, perhaps, for users coding their own scripts — the implication being that you need to be fluent in bash to install a Linux distro. In fact, especially with user-friendly distributions, you don’t need to know a thing about the command line. And anything you do end up needing to learn, you can pick up along the way, one step at a time. “Type ‘make install’ … hmm, I guess I can do that.” “Use ‘ls’ to find out the contents of a directory. Ok, let me try it.”

But once you start learning, you can find more and more useful things to do on the command line. If you want, you can learn to write scripts and so on. (If you don’t care to, you don’t have to.) The more you use it, the more you learn about your computer and how to get more out of it. You feel like you’re in charge of the computer, because you know your way around. In Windows, I always felt like I was poking around a few well-lit paths, while most of the system was dark “computer space” that belonged to the operating system and I had no place being there.


Question: How did Windows get the reputation of being for non-computer-savvy novices while Linux is supposedly for advanced users only? Holy Crap! No wonder people think computers are so complicated — they’ve been using Windows this whole time!

If you’re on Windows, and think that computers are complicated, tedious, and annoying, do yourself a favor and try out Ubuntu. (It’s easy — download Ubuntu to a CD or USB stick, then boot from it. You’ll be able to try out the OS without having to install it.)

Really, Macs score highly in these categories as well. Young, trendy Apple fans might hate me for saying this, but if you know someone older who has trouble with computers, do both of you a favor and get them a Mac. It’s so much simpler, won’t ask them confusing questions, and has great support.

But for general uses (except for specific programs and games that work only on Windows), I’m sticking to Linux from here on out. And I really think the average Windows user would be amazed at how much simpler it is.


After originally publishing this article, I’m just going to keep adding brief bullet points as they occur.

  • Memory footprint on the hard drive. As a general rule, my Ubuntu install takes around 1/10th the hard drive space of Windows to do the same task (better).

Large Primes, The Beatles, and $100,000

Prime numbers have fascinated mankind for thousands of years.

Or, rather, they’ve fascinated about 1/11th of mankind, and bored the rest.

But big primes are incredibly important in cryptography.  Every day, we rely on 512-bit primes — numbers about 150 decimal digits long. Our Internet data is secure, relatively, because it’s so hard to factor numbers this size.

But for the adventurous, 150 digits is nothing. What if you want to be cutting-edge? I’m talking the Lady Gaga of primes. If so, then you probably want to be the largest known prime: currently, 243,112,609 − 1.

How big is this number? It’s about 13 million digits long. (Think small bookshelf, full.) If you like, you can see part of the number here or even view the whole number here (the page could take a while to load!).

And like pop music, finding large primes can be lucrative (not as lucrative as being a record label, but still). The Electronic Frontier Foundation gave away a $100,000 prize to the first folks to find a 10-million-digit prime, and $150,000 is on the line for the first 100-million-digit prime.

Where do The Beatles come in?

They’re no longer as hip as Gaga, sure, but they still have plenty of devoted fans.

Now, you could argue that they were more into perfect squares than primes, with songs like “Revolution 9” and “WhenI’m 64”. But nevertheless, there’s a statistical chance that the Beatles created a “prime song” without even knowing it.

Here’s what I mean. If you take the largest known prime, 243,112,609 − 1, and store it on your hard drive, it’ll take up about 5.4 MB.

Now consider the Beatle’s song A Day in the Life, encoded as an MP3 at a nice average 128 kbps (kilobits per second).  That takes up somewhere in the neighborhood of five megabytes as well.

But here’s where the beauty of computers come in. A 5 MB file is just a whole lot of zeros and ones. If you give them to iTunes with the extension ‘.mp3’, then those zeros and ones will be interpreted as a music file and they’ll be played. On the other hand, you can choose to interpret them as a number. Looking at it this way, there’s a chance that A Day in the Life could be the largest prime ever discovered!  (If the Beatles aren’t really your thing, you could try the songs Wake Up, Where It’s At, or Californication.)

Sign me Up. I want to find a prime in a song.

Not so fast. You’ll need an incredibly well-trained ear and years of experience. OK, no you won’t. But it’s probably not too likely that many primes will sound aesthetically pleasing, or that many pop songs are represented as primes.

Let’s say you acquire the necessary skills and sit down with your music library to find a prime song. What are your odds? Luckily, there’s a theorem that tells us: The Prime Number Theorem. It tells us how often primes tend to occur: specifically, if we’re close to the number N, then we should find a prime number about once every log(N) numbers. (log(N), as you may or may not recall, is roughly a measure of the number of digits it takes to write down N.)

Applying the Theorem, we see that, on average, one in 30 million 5-minute songs, in a normal MP3 format, should be prime numbers. (Perhaps I’ll write a program to check all the songs in someone’s music library … then again, maybe not.)

Best of all, Gracenote’s media database contains 100 million songs, which means there’s a pretty decent chance that one or more of those is a prime — possibly a bigger prime than any yet discovered! Get listening! And if you win a cash prize, be sure to send me some.

Will Computers Beat Us at Our Own Game?

This article from Time raises some interesting questions: How long until computers are “smarter” than humans? (Especially considering Watson’s recent performance on Jeopardy!) What about machines with creativity, intuition, and generalized intelligence — the historical province of humans alone? And if that’s not scary enough, how long until we can achieve immortality by downloading our brains into computers and preserving ourselves as thinking machines indefinitely?

Their article on the subject from a social point of view is quite interesting. However, it seems that the issue could benefit from a computer science perspective as well. What kind of technology would be required to achieve these things, and how tough will it be to get there? Let’s find out, or at least make some guesses.

Continue reading