
From:  Kiril Videlov 
Subject:  [Helpglpk] Calculating O'Neill prices in combinatorial auctions using the dual 
Date:  Wed, 3 Dec 2014 14:49:59 +0000 
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: ([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: 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 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) 
[Prev in Thread]  Current Thread  [Next in Thread] 