Boğaziçi University, Istanbul, Turkey
Ph.D., Computer Engineering, June 2011
Dissertation Title: Auction and Barter Models for Electronic Markets
Supervisor: Prof. Can Özturan
We propose three auction and barter based electronic market models. Our first model is a direct barter model for the course add/drop process in the universities. We model the course add/drop process as a direct barter problem in which add/drop requests can be placed as barter bids. We also introduce a two-level weighting system that enables students to express priorities among their requests while providing fairness among the students. Our second model is the multi-unit differential auction-barter model which augments the double auction model with barter bids so that besides the usual purchase and sale activities, bidders can also carry out direct bartering of items. Our model also provides a mechanism for making or receiving a differential money payment as part of the direct bartering of items, hence, allowing bartering of different valued items. Furthermore, a powerful and flexible bidding language is designed which allows bidders to express their complex preferences of purchase, sell and exchange requests. Our third model is the double auction with limited cover money model. In this model, we propose the use of discrete time double auction institution for the trading of used goods as well as new ones. Our model allows declaration of an amount of cover money so that what is spent on purchased items minus the proceeds of sold items does not exceed this cover money amount. We also introduce a mechanism so that bidders may place multiple item requests in a single bid and limit the maximum number of items to be purchased. We formally define these three models and formulate the corresponding optimization problems. We propose fast polynomial-time network flow based algorithms for optimizing the first and the second models and show that the decision version of the optimization problem for the third model is NP-complete. The performances of our algorithms are also demonstrated on various test cases.
M.Sc., Computer Engineering, July 2004
Supervisor: Prof. Can Özturan
Resource co-allocation problem is one of the challenging problems in grids. In order to model this problem, a new combinatorial auction based resource co-allocation (CABRC) approach is proposed. This economy based model provides efficient allocation of resources in a grid environment by allowing bidders to submit bids on the combinations of different resource types. In order to solve the model, CABRC problem is defined and formulated using integer programming. It is proved that CABRC problem is NP-hard and since optimum solutions may take tremendous amount of time to be found, two new greedy heuristics based on price per unit criteria are proposed. A software package that consists of an artificial test case generator, an optimum solver, an upper bound estimator and three greedy heuristic solvers for CABRC problem is coded. Since there is no real world data for testing the solvers, performance of algorithms are compared using a comprehensive test suite which is produced by the test case generator. Proposed two polynomial time heuristic solvers produce promising results of 97.3 per cent and 99.2 per cent average performance relative to the optimum solution respectively.
B.S., Computer Engineering, July 2002
Undergraduate Thesis Title: A Branch and Bound Based Algorithm for Multi-Unit Combinatorial Auction