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;

Fair Division

"The only way to rectify our reasonings is to make them as tangible as those of the Mathematicians, so that we can find our error at a glance, and when there are disputes among persons, we can simply say: Let us calculate [calculemus], without further ado, to see who is right" Leibniz

If you want to divide items between two people you want to make sure that the person who gets least gets as much as possible.

This Maximin algorithm where you maximise what the person who gets least gets. To do this each person should put a valuation on each item. You can then use linear programming to divide items fairly between people. This program is written for the GLPK(there is a tutorial on it here)

This program is a modified version of this one

param m, integer,:= 2;
/* number of people dividing stuff */

param n, integer, > 0;
/* number of items to be divided */

set I := 1..m;
/* set of people */

set J := 1..n;
/* set of items */

param b{i in I},:= 100; 
/* resource capacity of person i. 
How much each person can want */

param c{i in I, j in J}, >= 0;
/* amount received if item j 
is given to agent i */

var worst;
/*how is the worst person doing?*/

var x{i in I, j in J},>=0;
/*
here ,>=0; 
   means that the items can be subdivided.
here , binary;
  means that items cannot be subdivided 
x[i,j] = 1 means job j is assigned to agent i */

s.t. one{j in J}: sum{i in I} x[i,j] = 1;
/* item j must be assigned. 
An item can be split due to >=0
 being used instead of binary;*/

s.t. lim{i in I}: sum{j in J} c[i,j] * x[i,j] <= b[i];
/* total amount received by all items
 to person i must not exceed the person's capacity */

s.t. wor{i in I}: sum{j in J} c[1,j] * x[1,j] >= worst;
s.t. wor2{i in I}: sum{j in J} c[2,j] * x[2,j] >= worst;
/*constraint on who gets worst deal*/
maximize obj: worst;

data;

param n := 4;
      
/*Divorce between Donald and Ivana Trump 
described in Win-Win solution.
Items to be divided are Conneticut estate, Palm beach mansion,
 Trump plaza apartment, Trump Tower Triplex
param n := 4;
*/
param c :  1  2  3  4 :=
      1   10 40 10 40
      2   40 20 30 10 ;
end;

This last data part param c is important. The first line the columns are the items to be divided. The rows are the valuations placed on them. So c[i,j] is the value person i places on item j.
With splitting items allowed this results in

        No. Column name  St   Activity     
------ ------------ -- ------------- 
     1 worst        B        73.3333                             
     2 x[1,1]       NL             0            
     3 x[2,1]       B              1                          
     4 x[1,2]       B       0.833333                            
     5 x[2,2]       B       0.166667                            
     6 x[1,3]       NL             0            
     7 x[2,3]       B              1                            
     8 x[1,4]       B              1               
     9 x[2,4]       NL             0 

With splitting items not allowed the answer comes out as

  No. Column name       Activity    
------ ------------    ------------- 
     1 worst                      70
     2 x[1,1]       *              0 
     3 x[2,1]       *              1            
     4 x[1,2]       *              1
     5 x[2,2]       *              0
     6 x[1,3]       *              0
     7 x[2,3]       *              1
     8 x[1,4]       *              1 

This algorithm can be used to divide up items in a divorce, resources between countries and loads of other areas.
I will try make this easier for people to use. Any suggestions/comments are welcome.