Please use this identifier to cite or link to this item: http://cuir.car.chula.ac.th/handle/123456789/36366
Title: An incentive compatible mechanism for booth auction / Puchit Sariddichainunta
Other Titles: กลไกสร้างแรงจูงใจที่เข้ากันได้สำหรับการประมูลพื้นที่จัดบูธ
Authors: Puchit Sariddichainunta
Advisors: Krung Sinapiromsaran
Other author: Chulalongkorn University. Faculty of Science
Advisor's Email: Krung.S@Chula.ac.th
Subjects: Auctions -- Mathematics
Exhibit booths
Integer programming
การประมูล -- คณิตศาสตร์
การโปรแกรมเชิงจำนวนเต็ม
Issue Date: 2010
Publisher: Chulalongkorn University
Abstract: The winner determination problem (WDP) for a single object auction is a relatively easy problem to solve using the greedy algorithm. It can be formulated and solved using the MIP optimization solver. In this thesis, we applied WDP to solve a booth auction which is one of the nonidentical multiple-object auctions known to be NP-hard. Formulation of the winner determination model for a linear arrangement of a multiple-object auction is explained in this study. Moreover, this research improves the algorithm from the study of Rothkopf et al (1998) having polynomial time complexity. Finally, the comparison of a running time exhibits the advantage of our proposed algorithm. The simulation results are discussed.
Other Abstract: ตัวแบบปัญหาการตัดสินผู้ชนะประมูลสำหรับสิ่งของหนึ่งชิ้น สามารถหาคำตอบโดยง่ายด้วยขั้นตอนวิธีละโมบ (Greedy algorithm) นอกจากนี้ปัญหาดังกล่าวสามารถแปลงเป็นปัญหากำหนดการเชิงเส้นจำนวนเต็มผสม และหาผลเฉลยโดยใช้โปรแกรมแก้ปัญหากำหนดการเชิงเส้นจำนวนเต็มผสมได้ แต่พบว่าปัญหาการตัดสินผู้ชนะประมูลสำหรับสิ่งของหลายชิ้นพร้อมกันซึ่งเป็นปัญหา NP-hard งานวิจัยนี้ปรับปรุงขั้นตอนวิธีการแก้ปัญหาของ Rothkopf et al (1998) และวิเคราะห์ตัวแบบกำหนดการเชิงเส้นจำนวนเต็มสำหรับการประมูลสิ่งของหลายสิ่งที่มีการวางตัวในเชิงเส้น นอกจากนั้นผู้วิจัยได้สร้างขั้นตอนวิธีโพลิโนเมียลในการแก้ปัญหาการประมูลดังกล่าว สุดท้ายได้วิเคราะห์ผลการเปรียบเทียบเวลาทำงาน และอภิปรายการแก้ปัญหาด้วยตัวแบบกำหนดการจำนวนเต็มและระเบียบวิธีของผู้วิจัย
Description: Thesis (M.Sc.)--Chulalongkorn University, 2010
Degree Name: Master of Science
Degree Level: Master's Degree
Degree Discipline: Applied Mathematics and Computational Science
URI: http://cuir.car.chula.ac.th/handle/123456789/36366
URI: http://doi.org/10.14457/CU.the.2010.883
metadata.dc.identifier.DOI: 10.14457/CU.the.2010.883
Type: Thesis
Appears in Collections:Sci - Theses

Files in This Item:
File Description SizeFormat 
puchit_sa.pdf1.34 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.