the donkey bit

Over the weekend, I told a Stnaford ugrad friend about some of my recent work.

Sounds like economics, she said.

I told her I thought so too, but that I didn't quite want it that way. I guess it just seems like a thing Computer Scientists Rarely Want To Talk About, something dirty that must be flushed.

On the other hand, I suppose that an agent for social justice must be able to talk dirty, econometrically, in order to defend herself properly...

Oh well, time to flip the donkey bit.

...

I developed distributional ranking in response to a Y! talk on keyword auctions, which G and Y seemed to run in a way that didn't make sense to me.

After all, why use an auction model anyway? Besides the obvious, that somebody in the past posed it that way.

I suppose I'm questioning the assumption of a static hierarchy induced by a single auction. In a traditional auction, you may be bidding for a "unique" item, where the item can only go to the single highest bidder. But in a digital world, where most items can be copied at almost no cost, why should the laws of classical auctioning still apply?

Instead of posing the problem as an "auction" we can just focus on the set of "bids" and allot favorable (fluid) rankings to each bidder. (This assumes that the bidders and surfers don't mind fluid rankings in their ads, which seems reasonable to me but perhaps not to the rest of you.)

Here's some code.

#!/usr/bin/env ruby
#

def donkey!(arr)
  return [] if arr.empty?
  
  x, y = rand(arr.size), rand * arr.max
  x = (arr.length + 42) if (y > arr[x]) # Rejected... And How!

  [arr.delete_at(x)] + donkey!(arr)
end

This is a simple, unoptimized, donkey sort.

As described previously, this function implements a game called "immunize the donkey", and returns a sample from a distribution of rankings.

To get an idea of what this algorithm does, consider the following grid G, rendered in state-of-the-art ASCII graphics.

+-------+
|8 . . .|
|8 7 . .|
|8 7 . .|
|8 7 . .|
|8 7 . .|
|8 7 . .|
|8 7 2 .|
|8 7 2 1|
+-------+

donkey! picks a random(-ish) coordinate x, y so that it falls somewhere within the grid G.

If the coordinate (x, y) does not land on a number, we reject the coordinate and try again.

Otherwise, let's say the immunizing dart falls on the number seven. This is our first chosen element. We delete it from the array, and recurse on the rest of the array. Make sense? Good.

Example use:

require 'pp'
m = []

20.times { m << donkey!([8,7,2,1]).compact }
pp m.sort.reverse

Sample run on my non-lap-top computer:

>>> donkey.rb

[[8, 7, 2, 1],
 [8, 7, 2, 1],
 [8, 7, 2, 1],
 [8, 7, 1, 2],
 [8, 7, 1, 2],
 [8, 2, 7, 1],
 [8, 1, 7, 2],
 [8, 1, 7, 2],
 [7, 8, 2, 1],
 [7, 8, 2, 1],
 [7, 8, 2, 1],
 [7, 8, 2, 1],
 [7, 8, 2, 1],
 [7, 2, 8, 1],
 [7, 1, 8, 2],
 [2, 8, 7, 1],
 [2, 8, 7, 1],
 [2, 8, 7, 1],
 [2, 1, 8, 7],
 [1, 7, 8, 2]]

Note that "7" shows up about as much as "8" does in alpha (first) rank. Unlike a GSP auction, which is notably subceptible to gaming, "winning" a distributional (donkey sort) (non-)auction by a small amount doesn't change the outcome significantly.

To me, this seems like a good thing. G and Y reportedly make billions from keyword auctions, which suggests that there are a small number of keyword auctions that are worth quite a bit by themselves. Since winning the alpha click can mean a lot, you have to spend time gaming the deterministic system in what might come to be known as the penny wars of the early Interweb.

"7" and "8", notably, show up much more often than "2" and "1" one do in alpha rank, but they at least show up once in a long while, which to me is a good thing too. A small slice of a big big pie, after all, can be quite fattening in the end.

I was going to bake a few more graphs, but AntiRSI is telling me to take a break, and so I will.

(My shoulder is going to need (more) physical therapy when I get back to campus...)