Minimum-weight perfect matching in Android system code

Heh.. I've just bounced into this article:
http://www.troodon-software.com/Algorithms/Android/2010/06/20/euclidean-bipartite-matching-multi-touch-and-android/

Check this, it's funny :) Briefly, Android's multitouch dragging uses a function that tries to solve a bipartitate matching problem (aim: track fingers). The function is a greedy algorithm being awkward sometimes. Also, a comment refers to an article in which a near-linear approximation algorithm is developed.

It's maybe just me, but..

• the greedy algorithm seems to be a quick hack and
• the complicated near-linear approximation is an overkill?

I mean.. come on, how large can n, the number of points be in this task? Most people have ten fingers only :-P at this scale, it's not the asymptotic that matters, the constants also play a significant role. So - I would go with the Hungarian method, it's easy to implement and worst-case n^3 is not a big deal at this scale.. I guess.

Bottom line: take care with the hidden constants that hide in the big O. Especially when they are comparable with the input size.

Vickrey is the new Max

Probably most of you already have encountered some kind of an auction system (e.g. buying something on Amazon, eBay etc). There is an item to be sold, a number n of agents, agent i thinks the item worth v_i for him. Of course if this data was available for everyone, then there would be no need for an auction: the agent i who maximizes v_i gets the stuff and pays v_i.
However, such information is sensitive. Thus, during the auction the agents offer bets (either all at once, or sequentially, in one turn or in more turns) and the winner is deduced from the amount he bet.

A possibility for a one-turn sealed-bid auction (sealed-bid means that the agents do not know each other's bets, only the auctioner does) is that the auctioner collects the bids b_i from each agent i, e.g. in sealed envelopes, and agent i who maximizes b_i gets the stuff in exchange for his bid. This is the simplest model and the easiest one to understand.

However, it suffers from the so-called winner's curse: informally, the winner will be almost always unhappy with the outcome. Say there are three agents bidding 1, 2 and 10 respectively. Then Agent 3 will get the stuff for the price of 10. He could have also get the stuff for the price of 3 -- or, if not only integers are in play, for any real number being strictly greater than 2. Thus he can view the situation as "alas, I just lost 8 dollars, I should have bet only 2$ and one cent" which probably makes him unhappy.

There is a simple way for avoiding the winner's curse by employing the Vickrey mechanism: agent i maximizing gets the stuff but he has to pay only the second-highest price. In the previous example, Agent 3 gets the stuff but it costs him only two dollars.
The Vickrey mechanism has numerous other advantages, including:

• it gives an incentive for truthful bidding: each (selfish!) agent now plays his best strategy by bidding exactly b_i := v_i. 
• thus, it's also decision efficient: Agent i maximizing v_i gets the stuff.

(The system is vulnerable to shill bids, though.)

Things get much more complicated when there are more items to sell (either identical or not; an agent can either bet item-wise or for a set of items etc). In that case, complexity and economical problems arise.

Anyone wants to check the literature and write an essay on that? ;-)