Optimal Allocation in Multi-Unit Combinatorial Auctions: A Linear Programming Approach

Title: Optimal Allocation in Multi-Unit Combinatorial Auctions: A Linear Programming Approach

Research Question: Can linear programming be used effectively to find the optimal allocation in multi-unit combinatorial auctions, despite being considered time-consuming by previous researchers?

Methodology: The researchers implemented a Branch-and-Bound search program along the lines of previous work. They used a linear programming routine to bound from above the value of extensions of partial allocations. They also presented an important way of saving on those expensive calls to the LP routine.

Results: The experimental results showed that linear programming is worth using. Investing almost all of one's computing time in using LP to bound from above the value of the optimal solution allowed for aggressive pruning. The researchers found that choosing to deal with the bid with the largest coefficient (typically 1) in the optimal solution of the relaxed LP problem also performed surprisingly well. The gap between the lower bound provided by greedy heuristics and the upper bound provided by LP was typically small, indicating that extensive pruning was possible.

Implications: These findings suggest that linear programming can be used effectively in multi-unit combinatorial auctions, contrary to previous assumptions. This approach can lead to more accurate results and save computing time by allowing for aggressive pruning. The method of saving on LP routine calls presented by the researchers can further increase the efficiency of this approach.

Link to Article: https://arxiv.org/abs/0202016v1 Authors: arXiv ID: 0202016v1