A study in combinatorial auctions

Abstract

oz TÜMLEŞİK AÇIK ARTIRMALAR ÜZERİNE BİR ÇALIŞMA Bilge, Betül Master, Bilişim Sistemleri Bölümü Tez yöneticisi: Doç. Dr. Ferda Nur Alpaslan Temmuz 2004,101 sayfa Elektronik işin ilerlemesi ve işlem ücretlerinin İnternette düşük olması sebebiyle yeni açık artırma mekanizmaları tasarlamak için ilgi artmıştır. Yakın zamanda bilgisayar bilimleri, ekonomi, iş, ve oyun teorisi üzeride çalışan pek çok bilim adamı açık artırma teorileri üzerinde çok değerli çalışmalar yapmışlardır. İşlemsel açıdan bakıldığında, tümleşik açık artırmalar en göze çarpan açık artırma türü olarak karşımıza çıkmaktadır. Tümleşik açık artırmalarda, teklif verenler satılan parçaların bileşimine bir teklif verebilir. Bu tür açık artırmalar, teklif verenlerin satılan parçalara biçtikleri değerin toplamsal olmadığı, çok-parça çok-birim olan açık artırma modellerinde geleneksel açık artırmalara gore çok daha verimli paylaştırma sağlar. Ama tümleşik açık artırmalarda kazancı azami hadde çıkaracak, kazanalan belirlemenin NP-Complete olduğu görülmüştür. vıBu çalışmada, önce tümleşik açık artırma problemi için yapılmış olan yaklaşımlar incelenmiştir. Bu inceleme sonunda üç farklı yaklaşım seçilmiş ve bu yaklaşımlar modellenmiştir. Bu yaklaşımlar : arama yolu, eşzamanlı azalan acık artırma yolu, ve sayısal programlama yoludur. Bu modellerin performansı yapılan simulasyonla karşılaştırılmıştır. Bu simulasyonda bant genişliği paylaştırımı modellenmiştir. Son olarak bir tümleşik açık artırma aracı yapılmıştır. Anahtar Kelimeler : Açık Artırma, Tümleşik açık artırma, Cok-parça çok-birim açık artırmaları, Eşzamanlı açık artırmalar, Sayısal programlama, lineer programlama, e-iş, e-tedarik, Kazanan belirleme, Simulasyon, Bant genişliği paylaştırımı vıı

ABSTRACT A STUDY IN COMBINATORIAL AUCTIONS Bilge, Betiil M.S., Department of Information Systems Supervisor: Assoc. Prof. Dr. Ferda Nur Alpaslan July 2004, 101 pages By the emergence of electronic commerce and low transaction costs on the Internet, an interest in the design of new auction mechanisms has been arisen. Recently many researchers in computer science, economics, business, and game theory have presented many valuable studies on the subject of online auctions, and auctions theory. When faced from a computational perspective, combinatorial auctions are perhaps the most challenging ones. Combinatorial auctions, that is, auctions where bidders can bid on combinations of items, tend to lead to more efficient allocations than traditional auction mechanisms in multi-item multi-unit situations where the agents' valuations of the items are not additive. However, determining the winners to maximize the revenue is NP-complete. IVIn this study, we first analyze the existing approaches for combinatorial auction problem. Based on this analysis, we then choose three different approaches, which are search approach, descending simultaneous auctions approach, and IP (Integer Programming) formulation approach to build our models. The performances of the models are compared using computer simulations, where we model bandwidth allocation system. Finally a combinatorial auction tool is built which can be used for online auctions and e-procurement systems. Keywords: Auctions, Combinatorial Auctions, Multi-item multi-unit auctions, Simultaneous auctions, Integer Programming, Linear Programming, e-commerce, e- procurement, Winner determination, Simulation, Bandwidth allocation