An incentive compatible mechanism for booth auction / Puchit Sariddichainunta

Thesis (M.Sc.)--Chulalongkorn University, 2010

Saved in:

Bibliographic Details
Main Author:	Puchit Sariddichainunta
Other Authors:	Krung Sinapiromsaran
Format:	Theses and Dissertations
Language:	English
Published:	Chulalongkorn University 2013
Subjects:	Auctions > Mathematics Exhibit booths Integer programming การประมูล > คณิตศาสตร์ การโปรแกรมเชิงจำนวนเต็ม
Online Access:	http://cuir.car.chula.ac.th/handle/123456789/36366
Tags:	Add Tag No Tags, Be the first to tag this record!
Institution:	Chulalongkorn University
Language:	English

id	th-cuir.36366
record_format	dspace
spelling	th-cuir.363662013-10-25T11:05:40Z An incentive compatible mechanism for booth auction / Puchit Sariddichainunta กลไกสร้างแรงจูงใจที่เข้ากันได้สำหรับการประมูลพื้นที่จัดบูธ Puchit Sariddichainunta Krung Sinapiromsaran Chulalongkorn University. Faculty of Science Auctions -- Mathematics Exhibit booths Integer programming การประมูล -- คณิตศาสตร์ การโปรแกรมเชิงจำนวนเต็ม Thesis (M.Sc.)--Chulalongkorn University, 2010 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. ตัวแบบปัญหาการตัดสินผู้ชนะประมูลสำหรับสิ่งของหนึ่งชิ้น สามารถหาคำตอบโดยง่ายด้วยขั้นตอนวิธีละโมบ (Greedy algorithm) นอกจากนี้ปัญหาดังกล่าวสามารถแปลงเป็นปัญหากำหนดการเชิงเส้นจำนวนเต็มผสม และหาผลเฉลยโดยใช้โปรแกรมแก้ปัญหากำหนดการเชิงเส้นจำนวนเต็มผสมได้ แต่พบว่าปัญหาการตัดสินผู้ชนะประมูลสำหรับสิ่งของหลายชิ้นพร้อมกันซึ่งเป็นปัญหา NP-hard งานวิจัยนี้ปรับปรุงขั้นตอนวิธีการแก้ปัญหาของ Rothkopf et al (1998) และวิเคราะห์ตัวแบบกำหนดการเชิงเส้นจำนวนเต็มสำหรับการประมูลสิ่งของหลายสิ่งที่มีการวางตัวในเชิงเส้น นอกจากนั้นผู้วิจัยได้สร้างขั้นตอนวิธีโพลิโนเมียลในการแก้ปัญหาการประมูลดังกล่าว สุดท้ายได้วิเคราะห์ผลการเปรียบเทียบเวลาทำงาน และอภิปรายการแก้ปัญหาด้วยตัวแบบกำหนดการจำนวนเต็มและระเบียบวิธีของผู้วิจัย 2013-10-25T11:04:11Z 2013-10-25T11:04:11Z 2010 Thesis http://cuir.car.chula.ac.th/handle/123456789/36366 en Chulalongkorn University application/pdf Chulalongkorn University
institution	Chulalongkorn University
building	Chulalongkorn University Library
country	Thailand
collection	Chulalongkorn University Intellectual Repository
language	English
topic	Auctions -- Mathematics Exhibit booths Integer programming การประมูล -- คณิตศาสตร์ การโปรแกรมเชิงจำนวนเต็ม
spellingShingle	Auctions -- Mathematics Exhibit booths Integer programming การประมูล -- คณิตศาสตร์ การโปรแกรมเชิงจำนวนเต็ม Puchit Sariddichainunta An incentive compatible mechanism for booth auction / Puchit Sariddichainunta
description	Thesis (M.Sc.)--Chulalongkorn University, 2010
author2	Krung Sinapiromsaran
author_facet	Krung Sinapiromsaran Puchit Sariddichainunta
format	Theses and Dissertations
author	Puchit Sariddichainunta
author_sort	Puchit Sariddichainunta
title	An incentive compatible mechanism for booth auction / Puchit Sariddichainunta
title_short	An incentive compatible mechanism for booth auction / Puchit Sariddichainunta
title_full	An incentive compatible mechanism for booth auction / Puchit Sariddichainunta
title_fullStr	An incentive compatible mechanism for booth auction / Puchit Sariddichainunta
title_full_unstemmed	An incentive compatible mechanism for booth auction / Puchit Sariddichainunta
title_sort	incentive compatible mechanism for booth auction / puchit sariddichainunta
publisher	Chulalongkorn University
publishDate	2013
url	http://cuir.car.chula.ac.th/handle/123456789/36366
_version_	1681413030574817280

An incentive compatible mechanism for booth auction / Puchit Sariddichainunta

Similar Items