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

Assume For Contradiction

Am I the only one who’s noticed an amusing (or perhaps alarming) tendency of proofs by contradiction to sneak in places they don’t really belong?

Let me illustrate with an absurd example.

Prop 0. It is cold outside.

Proof. Assume for contradiction that it is warm outside.
Then it must not be snowing right now.
But it is snowing right now.
This is a contradiction, so our assumption was false.
So it is cold outside.

Continue reading

Lua-Functional library updated for Lua 5.2.0

The lua-functional library has been updated to version 1.101 and is now compatible with Lua 5.2.

Two other small changes:

  • range() can now be called with one argument. range(x) is equivalent to range(1,x) = {1,2,…,x}.
  • increased functionality of casef().

I’d like to briefly explain the second one, partly because it’s slightly complicated and partly because I think casef() is cool.

The closely related `case` is basically a long if/elseif chain. It takes in pairs of (x,y) and is equivalent to `if x1 then y1 elseif x2 then y2 elseif …`. Casef packages this behavior into a function that can be called later, and also allows x1 and y1 to be functions.

casef(case1,case2,case3,…) takes one or more arguments. Each table argument such as case1 has the form case1 = {pred,cond}. Each pred and cond argument may be one of the following: true, false, nil, or a function.

casef returns a function f. When called as f(a,b,c,…), it will check each predicate in order. If the predicate is a function, it will call pred(a,b,c,…) and use that as the value to check; otherwise, it just uses the predicate’s value. For the first true predicate (or more exactly, the first non-nil, non-false predicate), it returns the corresponding result. If ‘result’ is not a function, it is returned; if it is, then we return result(a,b,c,…).

Here’s a quick example — a recursion/memoization solution for computing the Levenshtein (or edit) distance between two arrays.

dofile('lua-functional.lua'):loadglobally()

levenshtein_dist = function(arr1,arr2)
    -- d is a list of #arr1 empty lists
    local d = gen({}, function() return {} end,
                  function(a,ind) return ind>#arr1 end)
    
    -- f(i,j) = edit distance between arr1[1:i] and arr2[1:j]
    f = casef(
    {function(i,j) return i==0 end, function(i,j) return j end},
    {function(i,j) return j==0 end, function(i,j) return i end},
    {function(i,j) return d[i][j] end, function(i,j) return d[i][j] end},
    {true, function(i,j)
               d[i][j] = case({arr1[i]==arr2[j],f(i-1,j-1)}, -- match at current location
                              {true, min({f(i-1,j)+1,        -- deletion
                                          f(i,j-1)+1,         -- insertion
                                          f(i-1,j-1)+1})})   -- substitution
               
               return d[i][j]
           end})
    
    return f(#arr1,#arr2)
end

print(levenshtein_dist({1,3,2,3,4},{2,3,3,3,3,4}))

The heart of the method is the recursive function f.  f takes care of its base cases first: if i or j is zero. Then it checks if we have already computed and memoized this square; if so, return it. Finally, for all other cases (condition “true”), recursively compute and memoize the minimum edit distance based on recursive calls to f.

A final note: within this last function, we call case rather than casef. This is somewhat computationally expensive, because we have to call f four times to fill the arguments to the case statement — if we’d used casef and wrapped these calls inside functions, only the necessary one would’ve been called. However, it would have required more typing.

Anyway, as always, I appreciate any feedback, thoughts, or comments on lua-functional!

Installing and using MySQL (on Fedora 15)

I had some trouble getting basic installation of MySQL to work, so here’s a ground-up tutorial.

  1. Install mysql and mysql-server from the repositories. On Fedora, that’s ‘sudo yum install mysql’ and the same with ‘mysql-server’.
  2. To run the MySQL server, you have to run the command ‘/etc/rc.d/init.d/mysqld start’. (You may need to run this as root by prefacing with ‘sudo’.)
  3. The problem I ran into was, it was trying to use the innodb database, which is not installed by default. So you need to edit the file ‘/etc/my.cnf’. Under the section [mysqld], add the lines:
    skip-innodb
    default-storage-engine=myisam
  4. Now run  ‘/etc/rc.d/init.d/mysqld start’ and it should say things are going ok. If not, you’ll have to check the error log file ‘/var/log/mysqld.log’ to see what went wrong.
  5. Now, from a terminal, run ‘mysql’. It should connect to the database you have running.  This should open up in interactive MySQL interpreter where you can enter commands like “SHOW DATABASES;”.

A Functional Library For Lua

I’ve put up online a functional programming library for Lua that I wrote this summer. It’s located here:

https://bitbucket.org/luafunctional/lua-functional

 

The idea is to provide a bunch of functional programming constructs such as maps, filters, folds, list comprehensions, zips, some stuff like that. It includes a documentation file and a test suite that I’ve used to make sure the functions are correct and bug-free. (But you can never be sure!)

The bad news — I tested it with Lua 5.1.4, the current version, but Lua 5.2, in beta, introduces some changes that break lua-functional. I hope to have a fix for this up by the time Lua 5.2 is official!

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

Simple Memoization in Haskell

Being a beginner in Haskell, it took me quite a while to figure out a nice solution to this problem. (Of course, since I’m a beginner, I can’t guarantee that better solutions don’t exist!)

What’s the problem? Well, Haskell is, of course, a purely functional language, meaning that:

  • It has no real state to speak of,
  • Everything that’s calculated, is calculated by recursion.

See any contradictoins there? The classic solution to recursive problems is memoization. But memoization requires us to save state — something that’s unnatural and difficult in Haskell! So I’ll walk through a simple but general way to solve this problem.

Let’s use the classic example of the Fibonacci numbers, because I’m too lazy to come up with anything else and complexity would only get in the way. Note, however, that our solution works on recursive formulas of any number of variables.

fibs 0 = 1
fibs 1 = 1
fibs n = (fibs (n-1)) + (fibs (n-2))

Looks great, but if you try “fibs 40″ you’ll never get an answer. We’re going to fix this by making a Data.Array. This array will store our Fibonacci numbers. The only downside is that we have to know ahead of time how large we want our Array to be.

OK, first we need to know how to make an Array. For more info on Arrays, you should check out the relevant article on A Gentle Introduction to Haskell. But for now, we’re going to use the mkArray function presented in that article:

import Data.Array
mkArray :: (Ix a) => (a -> b) -> (a,a) -> Array a b
mkArray f bnds = array bnds [(i, f i) | i <- range bnds]

-- make a one-dimensional array indexed from one to ten,
-- element at i is equal to i
arr1 = mkArray (\x -> x) (1,10)

-- make a 2d array from (0,0) to (10,10),
-- entry (i,j) is equal to i+j
arr2 = mkArray (\e -> (fst e) + (snd e)) ((0,0),(10,10))

Good. Now, how do we apply this to fibs in a general way?  Well, first we’ll transform our function into a “let” construct:

fibs x =
       let f 0 = 1
           f 1 = 1
           f n = (fibs (n-1)) + (fibs (n-2))
        in f x

Now we’re going to take “fibs” out and make it its own function, using the “let” construct to build our array.

fibarr = mkArray func (0,10000)
        let ...

fibs x = fibarr!(x)

Here we see how to access our array. More generally, if we want to access an n-dimensional array at a1,…,an, we have to access it using a tuple:  myarray!(a1,a2,…,an).

Ok, the last step is to connect the “func” used in building the array to our let clause down below. We’ll do this simply by defining func:

fibarr = mkArray func (0,10000)
    where func elem =
            let f 0 = 1
                f 1 = 1
                f n = (fibs (n-1)) + (fibs (n-2))
             in f elem

fibs x = fibarr!(x)

Note here that elem is a tuple in the more general case. With more than three variables, you may need to write your own functions to access the elements of a tuple beyond the first and second, or download the appropriate library. But here’s how the construct looks in the 2-dimensional case:

-- li and ui are lower and upper bounds
myarr = mkArray func ((l1,l2),(u1,u2))
    where func elem =
             let f x1 x2 = ...
                 ...
                 ...
              in f (fst elem) (snd elem)

origfunc x1 x2 = myarr!(x1,x2)

And here’s our complete code for fibs:

import Data.Array
mkArray :: (Ix a) => (a -> b) -> (a,a) -> Array a b
mkArray f bnds = array bnds [(i, f i) | i <- range bnds]

fibarr :: Array (Int) Integer
fibarr = mkArray func (0,10000)
    where func elem =
            let f 0 = 1
                f 1 = 1
                f n = (fibs (n-1)) + (fibs (n-2))
             in f elem

fibs :: Int -> Integer
fibs x = fibarr!(x)

main = do print (fibs 10000)