Chulalongkorn University Theses and Dissertations (Chula ETD)
An incentive compatible mechanism for booth auction / Puchit Sariddichainunta
Other Title (Parallel Title in Other Language of ETD)
กลไกสร้างแรงจูงใจที่เข้ากันได้สำหรับการประมูลพื้นที่จัดบูธ
Year (A.D.)
2010
Document Type
Thesis
First Advisor
Krung Sinapiromsaran
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Degree Name
Master of Science
Degree Level
Master's Degree
Degree Discipline
Applied Mathematics and Computational Science
DOI
10.58837/CHULA.THE.2010.1160
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 (Other language abstract of ETD)
ตัวแบบปัญหาการตัดสินผู้ชนะประมูลสำหรับสิ่งของหนึ่งชิ้น สามารถหาคำตอบโดยง่ายด้วยขั้นตอนวิธีละโมบ (Greedy algorithm) นอกจากนี้ปัญหาดังกล่าวสามารถแปลงเป็นปัญหากำหนดการเชิงเส้นจำนวนเต็มผสม และหาผลเฉลยโดยใช้โปรแกรมแก้ปัญหากำหนดการเชิงเส้นจำนวนเต็มผสมได้ แต่พบว่าปัญหาการตัดสินผู้ชนะประมูลสำหรับสิ่งของหลายชิ้นพร้อมกันซึ่งเป็นปัญหา NP-hard งานวิจัยนี้ปรับปรุงขั้นตอนวิธีการแก้ปัญหาของ Rothkopf et al (1998) และวิเคราะห์ตัวแบบกำหนดการเชิงเส้นจำนวนเต็มสำหรับการประมูลสิ่งของหลายสิ่งที่มีการวางตัวในเชิงเส้น นอกจากนั้นผู้วิจัยได้สร้างขั้นตอนวิธีโพลิโนเมียลในการแก้ปัญหาการประมูลดังกล่าว สุดท้ายได้วิเคราะห์ผลการเปรียบเทียบเวลาทำงาน และอภิปรายการแก้ปัญหาด้วยตัวแบบกำหนดการจำนวนเต็มและระเบียบวิธีของผู้วิจัย
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Sariddichainunta, Puchit, "An incentive compatible mechanism for booth auction / Puchit Sariddichainunta" (2010). Chulalongkorn University Theses and Dissertations (Chula ETD). 60130.
https://digital.car.chula.ac.th/chulaetd/60130