[Help-glpk] Calculating O'Neill prices in combinatorial auctions using the dual

[Kiril Videlov]

Hello,

I am trying to calculate the O’Neill prices for the individual atoms in a combinatorial auction.

The method is:

1)      Solve the IP to find the optimal allocation.

2)      Remove the integer constraints and for each positively valued optimal integer variable from the IP solution construct an equality constraint

to the optimal value. The LP of the new problem has the same optimal solution as the initial IP.

3)      Solve the dual of the new IP.

4)      The dual variables corresponding to the integer variables are used in another optimization for the prices vector.

Due to my lack of experience in linear programming, I believe I am making a mistake in step 3. I have been using the example from chapter 3.2 of [1]Pricing combinatorial auctions.

In the example there are 4 bids:
([1,1,0], 30)

([0,1,1], 30)

([1,0,1], 30)

([1,1,1], 39)

where w is the participation quantity vector for the 3 assets (i.e in the first bid above the bid is for assets 1 and 2 and valuation 30).

The winner determination problem (WDP) is as follows:

Maximize: SUM(p_i*x_i) for all orders n

Subject to:

SUM(w1_i*x_i) <= 1 for all orders

SUM(w2_i*x_i) <= 1 for all orders

SUM(w3_i*x_i) <= 1 for all orders

x in {0,1}

i in {1…n}

(For each asset we have maximum supply of 1)

 

The IP solution of the above problem is  39 with x1=0, x2=0, x3=0, x4=1 (below is the AMPL model I used to test that) which is in line with what was presented in 

3.2 of [1]Pricing combinatorial auctions. However, when it comes to solving the dual I am probably making a mistake –

I remove the integer constraint and add the x[4]=1 solving the LP with GLPSOL:
glpsol -m wdpSingle.mod -d test.dat -o out.txt --ranges ranges.txt

My understanding was that the “Marginal” values for the x variables are the dual values I am interested in, however what I get is x[1]=-30 x[2]=. x[3]=. x[4]=.

This is different than what was presented in the example in 3.2 of Pricing combinatorial auctions where thy used values 12, 0, 0, 0 in the next optimization.

As a novice in linear programming I find the explanation and example in the above mentioned paper difficult to follow due to the ambiguity for how they obtained the “g” values in their example which were next used in calculating the prices for the atoms.

 

I would greatly appreciate any hints and advices on this matter. Perhaps I am misunderstanding the term “dual” in the context of that example.

Thanks for the help.

Kind regards

Kiril

 

Model:

param noOrds;

set assets;

param ords {1..noOrds, assets};

param prices {1..noOrds};

var x {1..noOrds} integer   >= 0;                                                                                                            

maximize T: sum{i in 1..noOrds} prices[i]*x[i];

subject to supply {a in assets}: sum{i in 1..noOrds} ords[i,a]*x[i] <= 1;           

 

Data:

param noOrds := 4;                                 

set assets := A, B, C;

param ords :

        A       B       C :=

1       1       1       0  

2       0       1       1  

3       1       0       1  

4       1       1       1; 

param prices :=

1       30 

2       30 

3       30 

4       39;

 

[1] Pricing combinatorial auctions
European Journal of Operational Research, Volume 154, Issue 1, Pages 251-270
Mu Xia, Gary J. Koehler, Andrew B. Whinston

http://www.sciencedirect.com/science/article/pii/S0377221702006781 (Unfortunately I can’t find a free link – it doesn’t have a paywall accessing form university networks)