หลักสูตร/ปี พ.ศ. วิศวกรรมศาสตรบัณฑิต สาขาวิชาวิศวกรรมคอมพิวเตอร์ ปี พ.ศ. 2557
ภาคและปีการศึกษาที่สำเร็จการศึกษา ภาคปลาย ปีการศึกษา 2556
ประเภทโครงงาน
โครงงานวิศวกรรม
ชื่อโครงงานภาษาไทย
การแบงปนคาใชจายในการออกแบบเครือขายที่สอดคลองกับแรงจูงใจ
ชื่อโครงงานภาษาอังกฤษ
Incentive Compatible Cost Sharing in Network Design
ผู้พัฒนา
5310504028 นายอรรถกร พุธวัฒนะ
อาจารย์ที่ปรึกษาหลัก
จิตร์ทัศน์ ฝักเจริญผล
อาจารย์ที่ปรึกษาร่วม
จิตร์ทัศน์ ฝักเจริญผล
บทคัดย่อ
ราคาของความเสถียร (price of stability) ของเกมใด ๆ คืออัตราส่วนระหว่างค่าใช้จ่ายของคำตอบของเกมที่เป็นจุดสมดุลของแนชที่มีค่าใช้จ่ายต่ำที่สุดกับค่าใช้จ่ายของคำตอบที่ดีที่สุด ขีดจำกัดบนของอัตราส่วนดังกล่าวระบุว่ามีคำตอบของเกมที่ไม่มีผู้เล่นคนใดต้องการเปลี่ยนทางเลือกที่มีค่าใช้จ่ายแตกต่างจากคำตอบที่ดีที่สุดของปัญหานั้น ๆ
ในเกมการออกแบบเครือข่ายบนกราฟที่ไม่มีทิศทาง (network design game in undirected graphs) ผู้เล่นแต่ละคนเลือกเส้นทางที่เชื่อมจากจุดเริ่มต้นไปยังจุดปลายที่ค่าใช้จ่ายของเส้นเชื่อมแต่ละเส้นจะถูกแบ่งกับผู้เล่นทุกคนที่ใช้เส้นเชื่อมนั้นเท่า ๆ กัน โครงงานนี้สนใจกรณีที่ผู้เล่นแต่ละคนแทนจุดยอดต่าง ๆ ในกราฟ และต้องการหาเส้นทางจากจุดยอดของตนเองไปยังจุดปลายทางเป็นจุดยอดที่ระบุพิเศษจุดยอดหนึ่งในกราฟ เกมดังกล่าวจะถูกเรียกว่าเกมการกระจาย (broadcast game) ในกรณีทั่วไปของกราฟที่ไม่มีทิศทางใด ๆ Bilo, Flammini, และ Moscardelli ได้พิสูจน์ว่าขีดจำกัดบนของราคาของความเสถียรของเกมการกระจายนั้นมีค่าเป็นค่าคงที่ อย่างไรก็ตามขีดจำกัดบนดังกล่าวถึงแม้จะมีค่าคงที่แต่ก็ห่างจากค่าขีดจำกัดล่างที่มีค่าเท่ากับ 1.818 โครงงานนี้พิจารณากรณีพิเศษของกราฟที่เกิดจากการรวมเส้นทาง (path) หลาย ๆ เส้นเข้าด้วยกันโดยการรวมจุดยอดที่เป็นจุดยอดปลายของเส้นทางเหล่านั้น ภายใต้กรณีพิเศษนี้ โครงงานนี้ได้พิสูจน์ว่าราคาของความเสถียรนั้นจะมีค่าไม่เกิน 5
Abstract
"Price of stability" of a game is the ratio between the cost of the minimum-cost Nash equilibrium and the minimum cost solution. The upperbound of the price of stability implies that there exists a solution where no player wants to change whose cost does not diverge too much from the optimal cost.
In the ''network design game'' in undirected networks, each player choose a path connecting some source with some destination. The cost of each node is shared equality among all players using that edge. When each player corresponds to each node and wants to find a path from its designated node to a root the game is called ''broadcast game''. Recently, Bilo, Flammini, and Moscardelli show that for broadcast game the upperbound for the price of stability is a constant. However, the upperbound is very far from the known lowerbound for the problem which is only 1.818. This project considers a special case of the broadcast game where the graph is formed by a set of paths whose each end are combined. Under this special case the project proves that the upperbound for the price of stability is at most 5.
คำสำคัญ (Keywords)
ทฤษฎีเกม (Game theory), การออกแบบเครือข่าย (Network design), เกมการกระจาย (Broadcast games), ราคาของความเสถียร (Price of stability)
เว็บไซต์โครงงาน
-
วีดีโอคลิปของโครงงาน
-
ที่เก็บเวอร์ชันซอร์สโค้ด
-
ผู้นำเข้าข้อมูลครั้งแรก
นายอรรถกร
พุธวัฒนะ
(b5310504028)
แก้ไขครั้งสุดท้าย
เมื่อ Aug. 19, 2014, 3:57 a.m. โดย
นายอรรถกร
พุธวัฒนะ
(b5310504028)
สถานะการอนุมัติ
รออนุมัติ