A key problem in designing marketplaces is how to efficiently allocate a collection of goods among multiple people. Auctions have emerged as a powerful tool with the promise to increase market efficiency by allocating goods to those who value them the most. Nevertheless, traditional auctions are unable to handle real-world market complexities. Over the past decade, there has been a trend towards allowing for package bids and other types of multidimensional bidding techniques that enable suppliers to take advantage of their unique abilities and put forth their best offers. In particular the application of iterative combinatorial auctions in procurement saves negotiation costs and time. Conceptually these auctions show a potential for improving the overall market efficiency. However, in practice they host several new challenges and difficulties.
One challenge facing the auctioneer in an iterative combinatorial auction environment is to quickly find an acceptable solution for each round of the auction. Bidders require time to precisely evaluate, price, and communicate different possible combinations based on their current information of item prices. The auctioneer requires time to solve the underlying mathematical problem formulation based on the bids received, report back the feedback information and initiate a new round of the auction.
In Chapter 3, we propose a Lagrangian-based heuristic to solve the auctioneer's winner determination problem. After generating the Lagrange multipliers from the solution of a linear relaxation, the heuristic applies several procedures to fix any potentially infeasible optimal Lagrange solutions. In addition to providing an efficient way of solving the winner determination problem, as compared with the leading commercial solver CPLEX, our approach provides Lagrange multipliers. The latter are used as proxies for prices in the auction feedback mechanism.
In Chapter 4 we develop a model for the bidders pricing problem, an issue that has received much less attention in the literature. Using the auctioneer feedback, that includes the Lagrange multipliers, the pricing model maximizes the bidders' profit while at the same time keeping their bids competitive. We derive several optimality results for the underlying optimization problem. Interestingly, we analytically show that the auction converges to a point where no bidder is able to submit a bid that yields strictly better profit for him and is not less competitive than his previous bids submitted. We experimentally observe that this approach converges in an early stage. We also find that this iterative auction allows the bidders to improve their profit while providing lower and competitive prices to the auctioneer.
In Chapter 5, we introduce a flexible auction model that allows for partial bids. Rather than the regular all-or-nothing indivisible package bids, divisible bids provide flexibility for the auctioneer with the possibility to accept parts of the bids and yet allow the suppliers to capture synergies among the items and provide quantity discounts. We show numerically that this approach improves the overall efficiency of the auction by increasing the suppliers' profit while decreasing the auctioneer's total price of procurement. In addition, we find that computationally the flexible auction outperforms the regular auction. / Thesis / Doctor of Philosophy (PhD)
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/16396 |
| Date | 11 1900 |
| Creators | Mansouri, Bahareh |
| Contributors | Hassini, Elkafi, Computational Engineering and Science |
| Source Sets | McMaster University |
| Language | English |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0023 seconds