Fair Division of Advertising

Wired today had a really interesting article on how Google uses auctions to sell advertisements here.

it has spawned—dozens of millionaire geeks, billions of auctions, and new ground rules for businesses in a data-driven society.

There is a great paper here(pdf) on the game theory of these online auctions.

But what other mechanisms are there to distribute out advertisements? One way is to use voting which I will describe again. Another method is the algorithmic fair division explained in my last post.

The glpk program given can be used to divide desired ad words between two bidders. You can add more bidders by adding constraints and people. There is an advantage to using this linear programming system of adword selling. It is not designed to maximise earnings but fairness. The procedure guarantees certain criteria described here. One advantage of these criteria is that the least unhappy buyer will be as happy as possible. As Amarillo Slim said "You can shear a sheep many times, but you can skin him only once." If you can keep each party as happy as possible you might maximise revenue over time rather then just for each particular auction. In the given program each party is assumed to have the same resources, 100, a fair division linear program for most applications would give each party a different level of resources.

Dinosaurs are interested in fair division


The book on fair division is this one

So using the previous code but with different data.

/*
Coke and Pepsi want to buy advertisements. They each have 100 dollars to spend.
The adwords they desire are 
1. Refreshing drink 2. Black Fizzy water 
3. cola 4. pop
param c gives how much each company desires an ad on 
each  of these words. Minimax guarantees that
 the company that does worst gets 
the most ads on the topics they want possible.
*/
param c :  1  2  3  4 :=
      1   10 40 10 40
      2   40 20 30 10 ;
end;