คำตอบโดยตรง
FACT: Auction Algorithm ของ Dimitri Bertsekas แก้ปัญหาจับคู่แบบหนึ่งต่อหนึ่ง โดยให้ผู้เสนอราคาที่ไม่มีงานเลือกงานซึ่งให้ผลประโยชน์สุทธิสูงสุด แล้วเพิ่มราคางานนั้นมากกว่าความได้เปรียบเหนืออันดับสองด้วยค่า ε เจ้าของเดิมที่ถูกแย่งงานจะกลับมาเป็นผู้เสนอราคาอีกครั้ง จนทุก Agent ได้งานครบ วิธีนี้จัดการการแย่งงานด้วยการปรับราคาและสลับเจ้าของ แทนการให้ทุกตัวเลือกงานพร้อมกันแล้วค่อยแก้ความซ้ำซ้อน
บทความนี้ใช้คำว่า Agent หมายถึงผู้ทำงานในแบบจำลอง เช่น หุ่นยนต์ คน หรือ process ที่ต้องเลือกหนึ่งงานจากรายการ ไม่ได้หมายถึง LLM หลายตัวสนทนากัน ตัวอย่างเป็น SIMULATION ของ Agent 3 ตัวกับงาน 3 งาน ใช้ต้นทุนจำนวนเต็มและ ε=0.25 ภายใต้เงื่อนไขที่ระบุ วิธี auction นี้รับประกันคำตอบต้นทุนต่ำสุดสำหรับตัวอย่างดังกล่าว ราคาในสมการเป็นตัวแปรของอัลกอริทึม ไม่ใช่เงินที่ Agent จ่ายจริง
ทำไมการจับคู่งานจึงสำคัญ
เมื่อมี Agent และงานหลายรายการ ระบบต้องตัดสินใจว่าใครรับงานใด หากให้แต่ละตัวเลือกงานที่ตัวเองชอบที่สุดโดยไม่ประสานกัน งานเดียวกันอาจถูกเลือกหลายครั้ง ขณะที่งานอื่นไม่มีคนทำ การมอบหมายแบบหนึ่งต่อหนึ่งต้องรักษาสองเงื่อนไขพร้อมกัน: Agent ทุกตัวได้งานหนึ่งชิ้น และงานแต่ละชิ้นมีเจ้าของได้ไม่เกินหนึ่งตัว
การแบ่งงานตอบว่าใครรับงานใด ส่วน Conflict-Based Search ตอบว่าเส้นทางที่หลายตัวใช้พร้อมกันชนกันหรือไม่ หากงานมีลำดับก่อนหลังหรือความจุทรัพยากร ให้ดู Constraint-Aware Planning เพิ่ม เพราะ assignment ในบทความนี้ยังไม่ได้เข้ารหัสเวลาเหล่านั้น
รากฐาน: จากต้นทุนเป็นผลประโยชน์
ให้มี Agent i=1,…,n และงาน j=1,…,n กำหนดต้นทุน cᵢⱼ ว่า Agent i ใช้ต้นทุนเท่าไรเมื่อรับงาน j เป้าหมายคือหาการจับคู่หนึ่งต่อหนึ่งที่ทำให้ผลรวมต้นทุนต่ำสุด
รูปดั้งเดิมของ Auction Algorithm ใช้ผลประโยชน์ที่ต้องการทำให้สูงสุด แปลงต้นทุนเป็นผลประโยชน์ได้ด้วย aᵢⱼ = −cᵢⱼ ดังนั้นผลประโยชน์สุทธิของ Agent i จากงาน j ที่มีราคาปัจจุบัน pⱼ คือ aᵢⱼ − pⱼ หรือเท่ากับ −cᵢⱼ − pⱼ ในตัวอย่างทุก Agent จึงชอบต้นทุนต่ำ แต่ราคาของงานที่ถูกแย่งจะสูงขึ้นและทำให้ตัวเลือกนั้นน่าสนใจน้อยลง
FACT: Bertsekas อธิบายราคาเป็นตัวแปรคู่ (dual variables) ในปัญหาการหาค่าเหมาะที่สุด ราคาในบทความนี้จึงเป็นกลไกภายในที่ช่วยจัดการการแข่งขัน ไม่ใช่ค่าจ้าง ค่าใช้จ่าย หรือราคาตลาดจริง (Bertsekas, 1990).
เมื่อ Agent ที่ยังไม่มีงานถึงตาของตน ให้คำนวณค่าสุทธิ aᵢⱼ − pⱼ สำหรับทุกงานที่เลือกได้ เรียกค่าสูงสุดว่า v และค่าสูงสุดอันดับสองว่า w จากนั้นเสนอราคาเพิ่ม v − w + ε ให้กับงานอันดับหนึ่ง หากมีเจ้าของเดิม เจ้าของเดิมจะถูกปลดและกลับเข้าคิวผู้ไม่มีงาน ค่า ε เป็นการเพิ่มขั้นต่ำเชิงบวกที่หลีกเลี่ยงการวนประมูลเมื่อมีหลายงานที่คุ้มเท่ากัน
สำหรับบทความนี้กำหนดกติกาจำลองให้ประมวลผลผู้ไม่มีงานตามลำดับดัชนี Agent ที่ดัชนีต่ำกว่าก่อน และจัดลำดับงานที่ค่าสุทธิเท่ากันด้วยดัชนีงานต่ำกว่า นี่คือกติกาเพื่อให้การสาธิตทำซ้ำได้ ไม่ใช่เงื่อนไขว่าทุก implementation ต้องประมวลผลตามลำดับนี้
สถาปัตยกรรมและข้อมูลที่ไหลผ่าน
อินพุต: เมทริกซ์ต้นทุนจำนวนเต็มขนาด n×n รายการงานที่แต่ละ Agent เลือกได้ ค่า ε ที่มากกว่าศูนย์ และกติกาการจัดการ tie ระบบต้องมีการจับคู่ที่เป็นไปได้ครบทุก Agent จึงจะรับประกันการจบด้วยงานครบได้ในกรณีคลาสสิกที่ทุกคู่เลือกได้
สถานะระหว่างคำนวณ: ระบบเก็บราคาของแต่ละงาน เจ้าของปัจจุบันของแต่ละงาน งานที่ Agent แต่ละตัวถืออยู่ และคิวผู้ไม่มีงาน ในการประมูลหนึ่งครั้ง Agent อ่านผลประโยชน์สุทธิจากต้นทุนและราคาปัจจุบัน แล้วเปลี่ยนราคาและเจ้าของของงานที่เลือก
ตรวจผล: เมื่อ Agent ทุกตัวมีงาน อัลกอริทึมคืนการจับคู่ครบหนึ่งต่อหนึ่ง ค่า ε-complementary slackness (ε-CS) หมายถึง Agent แต่ละตัวถือครองงานที่มีผลประโยชน์สุทธิห่างจากค่าสูงสุดที่หาได้ไม่เกิน ε เงื่อนไขนี้นำไปสู่ขอบเขตว่าผลประโยชน์รวมอยู่ห่างจากค่าสูงสุดไม่เกิน nε (Bertsekas, 1990, pp. 137–138).
สถานะผิดพลาด: ถ้าเมทริกซ์ห้ามบางคู่จนไม่มีการจับคู่ครบ หรือมี Agent มากกว่างานและไม่มีรูปแบบเพิ่มงานจำลอง ระบบต้องรายงานว่าไม่ feasible ตามแบบจำลอง ไม่ควรอ้างว่าอัลกอริทึมจบพร้อมการจัดสรรครบ หากหยุดเพราะเพดานจำนวนรอบที่ implementation ตั้งเอง ผลควรเป็นหยุดเพราะงบ ไม่ใช่สรุปว่าไม่มีคำตอบทางคณิตศาสตร์
C เป็นอาร์เรย์ต้นทุน 3×3 ส่วน prices, owners และ assignment เป็นอาร์เรย์ยาวสาม; trace บันทึก bidder, งานที่เลือก, ค่าสุทธิอันดับหนึ่ง/สอง, ราคาเดิม/ใหม่ และเจ้าของที่ถูกปลด ตัวตรวจต้องเช็กว่าแต่ละ Agent และแต่ละงานปรากฏครั้งเดียวก่อนรายงาน complete และตรวจ ε-CS จากราคาชุดสุดท้าย การถือครองระหว่างรันยังเป็นสถานะชั่วคราว
หากเชื่อมเข้าระบบ LLM ต้องแยก Context Window ซึ่งเป็นข้อมูลในคำขอปัจจุบัน, Retrieved Context ซึ่งเป็นส่วนที่ค้นมาใส่ในคำขอนั้น, External Memory ซึ่งเก็บข้ามคำขอ และ Weight Updates ซึ่งเปลี่ยนพารามิเตอร์โมเดล อาร์เรย์ของ solver เป็นสถานะภายนอกที่อาจบันทึกหรือส่งเป็น context ได้ การบันทึกราคาหรือส่ง trace ให้ LLM อ่านไม่ได้ฝึกน้ำหนักใหม่ และ bid trace แสดงขั้นตอนของโปรแกรม ไม่ใช่ร่องรอย reasoning ภายในโมเดล
ขั้นตอนประมูล
- เริ่มด้วยราคางานเป็นศูนย์และไม่มีเจ้าของ
- เลือก Agent ที่ยังไม่มีงานตามคิวที่กำหนด
- คำนวณผลประโยชน์สุทธิของงานทุกชิ้น แล้วหาอันดับหนึ่ง v และอันดับสอง w
- เพิ่มราคางานอันดับหนึ่ง v−w+ε และมอบงานให้ Agent นี้
- หากงานมีเจ้าของเดิม ให้คืน Agent เดิมเข้าสู่คิวผู้ไม่มีงาน
- ทำซ้ำจนไม่มี Agent ที่ยังไม่มีงาน แล้วตรวจว่าการจับคู่ครบและไม่มีงานซ้ำ
Conceptual pseudocode — กติกา sequential สำหรับกรณี n≥2 งานจำนวนเท่ากับ Agent และทุกคู่เลือกได้:
price[j] = 0; owner[j] = NONE; assigned[i] = NONE
queue = agents in deterministic order
while queue is not empty:
i = pop_next(queue)
net[j] = benefit[i,j] - price[j] for every feasible task
best = argmax(net[j], tie_break_by_task_id)
second = second_highest(net[j])
price[best] += net[best] - second + epsilon
old_owner = owner[best]
if old_owner exists:
assigned[old_owner] = NONE
queue = sort_by_agent_id(queue plus old_owner)
owner[best] = i
assigned[i] = best
return assigned if every agent has one unique taskSIMULATION: สาม Agent กับสามงาน
ทดลองจัดสรรงานด้วย Auction Algorithm
ตัวแทน 3 คนแข่งขันกันเพื่องาน 3 งาน กรอกต้นทุนของแต่ละงาน โดยค่าประโยชน์ของงานเท่ากับลบต้นทุน ทุกครั้งที่เสนอราคา ราคาของงานที่เลือกจะเพิ่มขึ้น และอาจทำให้เจ้าของเดิมต้องกลับมาประมูลอีกครั้ง
SIMULATION: ตัวอย่างนี้สาธิตอัลกอริทึมแบบกำหนดผลลัพธ์แน่นอน ราคาเป็นค่าภายในอัลกอริทึม ไม่ใช่เงินที่ต้องจ่าย ไม่มีโมเดล การเรียนรู้ หรือบริการภายนอก
| ตัวแทน | ต้นทุนงาน X | ต้นทุนงาน Y | ต้นทุนงาน Z |
|---|
สถานะการประมูล
พร้อมแล้ว เลือกต้นทุนแล้วเริ่มได้เลย
| ตัวแทน | งานที่ได้รับ | ต้นทุนของตัวแทน | ราคางาน |
|---|---|---|---|
| ราคางาน (X, Y, Z) | 0, 0, 0 | ||
ลำดับการเสนอราคา
ลองแก้ต้นทุนจำนวนเต็ม 0–20 ทั้งเก้าช่อง เลือก ε=0.25, 1 หรือ 5 แล้วเริ่มสถานะใหม่ กดทีละ bid เพื่ออ่านการย้ายเจ้าของ หรือรันจนจบ ปุ่ม Reset คืนโจทย์เริ่มต้นและล้าง trace เมื่อเปลี่ยนอินพุตต้องเริ่มรอบใหม่เพื่อไม่ให้ราคาจากคนละโจทย์ปะปนกัน Lab กำหนดเพดาน 200 bids; หากถึงเพดานก่อนครบ รายงาน UNKNOWN_LIMIT ซึ่งไม่ได้พิสูจน์ว่าไม่มีคำตอบ ตัวอย่างทุกคู่เลือกได้และมี complete assignment อยู่แล้ว
กำหนดต้นทุนเป็น
งาน 1 งาน 2 งาน 3
Agent A 1 2 7
Agent B 2 9 9
Agent C 9 1 2ผลประโยชน์คือค่าติดลบของต้นทุน เริ่มด้วยราคางาน [0,0,0] และให้ A ประมูลก่อน จากนั้นเลือก Agent ที่ไม่มีงานดัชนีต่ำสุดเสมอ ค่า ε เท่ากับ 0.25 และ tie เลือกงานหมายเลขน้อยกว่า
A เลือกงาน 1 เพราะต้นทุน 1 ต่ำที่สุด เมื่อหักราคาจะได้ค่าสุทธิ −1 เทียบกับ −2 ของงาน 2 และ −7 ของงาน 3 อันดับสองคือ −2 จึงเพิ่มราคางาน 1 อีก 1.25 และได้ครอบครองงานนี้
B เห็นว่างาน 1 ยังเป็นตัวเลือกสุทธิสูงสุด แม้ราคาจะเพิ่มแล้ว งาน 2 และ 3 มีต้นทุน 9 เท่ากัน การเพิ่มราคาเหนืออันดับสองทำให้งาน 1 มีราคา 7.25 และ B เข้ามาแทนที่ A ซึ่งกลับเข้าคิว
A กลับมาเสนอราคาและเลือกงาน 2 ซึ่งมีต้นทุน 2 ต่ำกว่างาน 3 เมื่อคิดราคาปัจจุบัน ราคางาน 2 เพิ่มเป็น 5.25 ส่วน C เลือกงาน 3 และเพิ่มราคางาน 3 เป็น 4.50 หลังจากนั้นทั้งสาม Agent ถือคนละงาน: B ได้งาน 1, A ได้งาน 2 และ C ได้งาน 3 ผลรวมต้นทุนเท่ากับ 2+2+2=6
SIMULATION: ผลนี้ตรงกับ optimum ของเมทริกซ์ เมื่อไล่การจับคู่ทั้งหมด 3! = 6 แบบ ค่าต่ำสุดเท่ากับ 6 ตัวตรวจใช้การไล่ permutation หกแบบเป็น oracle สำหรับตัวอย่างขนาดเล็ก ไม่ได้ใช้ SciPy หรือกล่าวอ้างว่าเป็น implementation สำหรับแก้ปัญหาขนาดใหญ่
เปรียบเทียบ greedy, exact solver และ auction
SIMULATION: Greedy แบบลำดับคงที่ให้ A เลือกงานที่ต้นทุนต่ำสุดก่อน แล้วให้ B เลือกจากงานที่เหลือ และสุดท้าย C เลือกงานที่เหลือ A ได้งาน 1 ด้วยต้นทุน 1, B เลือกระหว่างงาน 2 และ 3 ซึ่งต้นทุนเท่ากันที่ 9, C ได้งาน 3 ด้วยต้นทุน 2 รวมเป็น 12 ผลขึ้นกับกติกา tie และลำดับ Agent ด้วย
Exact central assignment solver ตรวจหาคำตอบต่ำสุดภายใต้เมทริกซ์และข้อจำกัดที่ให้มา SciPy linear_sum_assignment รุ่นปัจจุบันระบุว่า implementation ใช้ modified Jonker–Volgenant algorithm จึงไม่ควรเรียก implementation นั้นว่า Hungarian โดยไม่มีหลักฐานเพิ่ม (เอกสาร SciPy). ในการสาธิตนี้ permutation oracle พบผล 6 เพื่อใช้ตรวจผล auction บนสามงานเท่านั้น
Auction ใช้ลำดับประมูลและราคาเพื่อค่อย ๆ จัดการการแย่งงาน สำหรับตัวอย่างนี้กลับได้ผล 6 ตาม exact oracle ภายใต้เงื่อนไขจำนวนเต็มและ nε=3×0.25=0.75<1 จุดเด่นเชิงแนวคิดคือการอธิบายได้ว่าใครแย่งงานใดและราคาปรับอย่างไร ส่วนการเลือกวิธีใช้งานจริงควรพิจารณาขนาดปัญหา ความหนาแน่นของคู่ที่เป็นไปได้ ความต้องการแก้โจทย์ซ้ำ และคุณสมบัติของ solver ที่นำมาใช้
REPORTED CLAIM: Bertsekas รายงานว่า Auction Algorithm เหมาะกับการคำนวณแบบขนานตามโครงสร้างของวิธี และอธิบายประสิทธิภาพเชิงทฤษฎีและการทดลองในงานปี 1990 ข้อความดังกล่าวไม่ใช่ผล benchmark ของตัวอย่างนี้ และไม่รับประกันว่าวิธี auction จะเร็วกว่า exact solver สมัยใหม่ในทุกขนาดหรือทุกเครื่อง (บทความ Interfaces).
เงื่อนไขของคำรับประกัน
FACT: เมื่อการจับคู่ครบและสถานะตรงตาม ε-CS ผลรวมประโยชน์ของคำตอบอยู่ห่างจากค่าสูงสุดไม่เกิน nε สำหรับเมทริกซ์ประโยชน์จำนวนเต็ม หาก nε<1 ความต่างระหว่างผลรวมประโยชน์จำนวนเต็มสองคำตอบที่ไม่เท่ากันอย่างน้อยหนึ่งหน่วย จึงบังคับให้คำตอบที่อยู่ห่างน้อยกว่าหนึ่งต้องเป็น optimum ด้วย
ในตัวอย่างมี Agent สามตัวและ ε=0.25 ดังนั้นขอบเขตคือ 3×0.25=0.75 ซึ่งน้อยกว่า 1 และได้ exact optimum เมื่อเงื่อนไขอื่นครบ: เมทริกซ์ประโยชน์เป็นจำนวนเต็ม ปัญหามี complete assignment อัลกอริทึมทำตาม auction update ที่รักษา ε-CS และดำเนินจนได้ complete assignment
ถ้าค่าต้นทุนเป็นทศนิยมหรือข้อมูลจริง ต้องพิจารณาการสเกลข้อมูลหรือวิเคราะห์ขอบเขตที่เหมาะสมแยกต่างหาก ไม่ควรยกข้อสรุป integer optimality ไปใช้โดยตรง การมีราคาเพิ่ม ε เพียงอย่างเดียวไม่ได้พิสูจน์ว่าคำตอบแม่นที่สุด หากหยุดก่อนครบหรือใช้การอัปเดตคนละแบบ
โค้ดที่ตรวจดูได้ และขอบเขตการทดลอง
FACT: หน้ารวมซอฟต์แวร์ของผู้เขียน เชื่อมไปยัง auction.txt ซึ่งหัวไฟล์ลงวันที่ 7 พฤษภาคม 1992 และรวม AUCTION, AUCTION_FLP, AUCTION_AS และ forward/reverse variants ส่วน AUCTION ระบุ FORTRAN version 1.1 กันยายน 1990 พร้อม ε-scaling; มี driver สุ่มปัญหาและคำเตือนเรื่อง integer overflow กับการไม่ตรวจ infeasibility จึงไม่ใช่ไฟล์เดียวกับ Lab sequential ε คงที่ที่เขียนขึ้นสำหรับบทความนี้
อ่านส่วนหัวและเส้นทางอัปเดต bid ใน source แล้ว แต่ไม่ได้ compile/run FORTRAN หรือทำซ้ำ benchmark ต้นฉบับ ข้อความสิทธิ์ใช้งานที่พบมีคำแนะนำจำกัดการแก้ไขและให้ระบุการเปลี่ยนแปลง ยังไม่ได้ยืนยันสัญญาอนุญาตมาตรฐาน จึงบันทึก license เป็น UNKNOWN แทนการอ้างว่าใช้เชิงพาณิชย์หรือแก้ไขได้เสรี ไม่มีตัวเลขเวลาเร็วขึ้นหรือการทดสอบหุ่นยนต์จริงจากบทความนี้
งานหลาย Agent ในโลกจริง
ANALYSIS: การจับคู่แบบนี้ใช้เป็นชั้นย่อยในการมอบหมายงานที่แยกจากกันได้ เช่น เลือกหุ่นยนต์หนึ่งตัวต่อจุดเก็บของหนึ่งจุด หรือจับคู่ผู้ปฏิบัติงานกับคำขอหนึ่งรายการ เมทริกซ์ต้นทุนอาจรวมระยะทาง เวลา พลังงาน หรือความเหมาะสมที่ออกแบบเป็นคะแนน แต่การออกแบบตัวเลขต้นทุนเป็นความรับผิดชอบของระบบ ไม่ได้เกิดจาก Auction Algorithm เอง
Gerkey และ Matarić จัดประเภทปัญหา multi-robot task allocation ตามจำนวนงานที่หุ่นยนต์ทำได้และจำนวนหุ่นยนต์ที่ทำงานหนึ่งได้ และแยกกรณีงานครั้งเดียวออกจากกรณีที่มีเวลาและการทำงานต่อเนื่อง (Gerkey & Matarić, 2004). แบบจำลองหนึ่ง Agent ต่อหนึ่งงานในบทความนี้จึงเป็นเพียงกรณีแคบของการจัดสรรงาน ไม่ครอบคลุมภารกิจที่ต้องใช้หุ่นยนต์หลายตัวทำร่วมกัน งานที่มีลำดับก่อนหลัง งานที่ทำซ้ำได้ หรือการวางแผนเส้นทางและเวลา
ชื่อ Auction Algorithm อาจทำให้เข้าใจว่าเป็นระบบประมูลที่ Agent คุยกันโดยตรง แต่ตัวอย่างนี้ประมวลผลผู้เสนอราคาทีละตัวและเก็บสถานะรวมในตัวแก้ปัญหา ผู้ใช้จึงไม่ควรอ่านตัวอย่างนี้เป็นหลักฐานของการทำงานแบบ decentralized, asynchronous, ทนการขาดการเชื่อมต่อ หรือปลอดภัยต่อข้อมูลส่วนบุคคล
ข้อจำกัดและสิ่งที่ควรต่อยอด
LIMIT: ต้นทุนเป็นข้อมูลที่ระบบรับเข้ามา ตัวอย่างไม่ได้เรียนรู้ต้นทุนจากประสบการณ์และไม่ได้ยืนยันว่าคะแนนแทนคุณภาพจริง หากคำนวณต้นทุนผิดหรือเป้าหมายไม่สอดคล้องกับผู้ใช้ คำตอบที่เหมาะที่สุดเชิงคณิตศาสตร์ก็อาจเป็นการจัดสรรที่ไม่เหมาะในโลกจริง
LIMIT: แบบหนึ่งต่อหนึ่งบังคับให้ทุก Agent รับงานหนึ่งงานและทุกงานมีเจ้าของหนึ่งตัว หากจำนวน Agent กับงานไม่เท่ากัน หรืออนุญาตให้ Agent ถือหลายงาน ต้องเติม dummy tasks, capacity constraints หรือใช้โมเดลการจัดสรรที่รองรับโครงสร้างนั้นโดยชัดเจน
HYPOTHESIS: หากระบบต้องมอบหมายงานใหม่บ่อยและต้นทุนเปลี่ยนเพียงเล็กน้อย อาจทดสอบการเริ่มประมูลรอบใหม่ด้วยราคาจากคำตอบก่อนหน้า เพื่อดูว่าลดงานคำนวณได้หรือไม่ นี่เป็นแนวทางทดลองที่ต้องวัดกับชุดข้อมูลและเงื่อนไขจริง ไม่ใช่ข้อสรุปจาก Lab นี้
หากงานมีการเปลี่ยนแปลงระหว่างที่ Agent เดินทาง ต้องตัดสินใจว่าจะตรึงคำตอบจนจบรอบหรือคำนวณใหม่ และอาจต้องคิดต้นทุนการย้ายงานหรือความเป็นธรรมเพิ่ม แบบจำลอง assignment เปล่า ๆ ไม่ตอบคำถามเหล่านี้
สิ่งที่ควรจำ
- Auction Algorithm จัดการการแข่งขันโดยให้ผู้ไม่มีงานเสนอราคาเพิ่มแก่ตัวเลือกที่ดีที่สุด และคืนเจ้าของเดิมเข้าสู่คิวเมื่อถูกแย่ง
- คำนวณจากผลประโยชน์สุทธิ benefit − price; เมื่อโจทย์เริ่มจากต้นทุนให้ใช้ benefit = −cost
- ราคาเป็นตัวแปรในอัลกอริทึม ไม่ใช่การจ่ายเงินจริง
- ภายใต้ ε-CS ขอบเขตความคลาดเคลื่อนของผลประโยชน์รวมคือ nε; สำหรับข้อมูลจำนวนเต็มและ nε<1 ได้ optimum
- การสาธิต 3×3 ใช้ permutation oracle เพื่อตรวจคำตอบหกแบบ ไม่ได้อ้างว่าเป็น solver สำหรับงานจริง
- ระบุข้อจำกัดให้ตรง: แบบจำลองหนึ่งต่อหนึ่งไม่ได้ครอบคลุมงานหลายคนต่อชิ้น ลำดับเวลา การเดินทาง การสื่อสารขัดข้อง หรือการเรียนรู้คะแนน
เกมด้านล่างให้ควบคุมการเสนอราคาจริงหกครั้งบนโจทย์อีกเมทริกซ์หนึ่ง เป้าหมายคือเลือกงานจากค่าสุทธิของผู้เสนอราคาแต่ละตาให้ถูกจนการจัดสรรครบ อ่านราคาปัจจุบันและเจ้าของก่อนเลือก คำตอบผิดให้ feedback โดยไม่เปลี่ยนสถานะหรือคะแนน; คำตอบถูกจึงอัปเดตราคาและการถือครอง Reset เริ่มเกมใหม่ เป็น SIMULATION ของกติกา ไม่ใช่การวัดความสามารถ AI
ภารกิจประมูล 6 ครั้ง
ช่วยประมูลให้ครบ 6 ครั้ง ในแต่ละรอบ เลือกงานที่มีค่าประโยชน์สุทธิสูงที่สุดสำหรับตัวแทนที่ยังไม่ได้งาน: ลบต้นทุนด้วยราคาปัจจุบัน เมื่อตอบถูก ระบบจะเสนอราคาจริง เพิ่มราคา และส่งตัวแทนที่ถูกแย่งงานกลับเข้าคิว ทุกการเสนอราคาที่ถูกต้องได้ 1 คะแนน
SIMULATION: ใช้ชุดต้นทุนจำนวนเต็มและกติกาตัดสินกรณีคะแนนเสมอที่กำหนดไว้ สถานะอัลกอริทึมทำงานในหน้านี้เท่านั้น ราคาเสนอเป็นค่าภายใน ไม่ใช่เงินที่ต้องจ่าย และระบบไม่ใช้หรือฝึกโมเดลภาษา
| งาน | ตัวแทน A ต้นทุน / สุทธิ | ตัวแทน B ต้นทุน / สุทธิ | ตัวแทน C ต้นทุน / สุทธิ | ราคา |
|---|
บันทึกภารกิจ
คำถามที่พบบ่อย
Auction Algorithm รับประกันว่าได้คำตอบดีที่สุดหรือไม่
สำหรับกรณีคลาสสิกที่มีการจับคู่ครบและรักษา ε-CS ได้ คำตอบอยู่ห่าง optimum ไม่เกิน nε หากผลประโยชน์เป็นจำนวนเต็มและ nε<1 ผลลัพธ์ที่ครบจะเป็น optimum แบบ exact เงื่อนไขเหล่านี้เป็นส่วนหนึ่งของคำรับประกัน
ทำไม Agent ที่ถูกแย่งงานจึงต้องประมูลใหม่
หลังงานถูกมอบให้ Agent ใหม่ เจ้าของเดิมไม่มีงานแล้ว การนำกลับเข้าคิวเปิดโอกาสให้เลือกจากงานทั้งหมดอีกครั้งตามราคาปัจจุบัน การสลับนี้ช่วยแก้การเลือกเฉพาะหน้าโดยให้ตัวเลือกของ Agent อื่นมีผลต่อการจัดสรร
ราคาเป็นเงินที่ต้องจ่ายหรือไม่
ไม่ใช่ ในแบบจำลองนี้ราคาเป็นตัวแปรช่วยในการคำนวณและอธิบายความขาดแคลนหรือการแข่งขันของงาน ไม่ได้สร้างธุรกรรมทางการเงิน
วิธีนี้คือการทำงานแบบกระจายศูนย์หรือไม่
ไม่ใช่ตามการสาธิตนี้ ตัวอย่างใช้คิวกลางและประมวลผล Agent ทีละตัว งานของ Bertsekas กล่าวถึงความเหมาะกับ parallel computation แต่ข้อสรุปนั้นไม่เท่ากับการพิสูจน์ว่า implementation ใดทำงานแบบ asynchronous หรือทนเครือข่ายขัดข้อง
ต่างจาก CBBA อย่างไร
CBBA เป็นอัลกอริทึมประมูลแบบกระจายสำหรับการมอบหมายงานหลายภารกิจให้หลาย Agent และมีกลไก consensus ที่ออกแบบไว้โดยเฉพาะ ส่วนบทความนี้อธิบาย linear assignment แบบหนึ่งต่อหนึ่งด้วยราคาและการคืนผู้ถูกแย่งเข้าคิว จึงไม่ควรเรียกตัวอย่างนี้ว่า CBBA (Choi, Brunet & How, 2009).
แหล่งอ้างอิง
- FACT — แหล่งหลักของวิธีและทฤษฎี: Dimitri P. Bertsekas, “The Auction Algorithm for Assignment and Other Network Flow Problems: A Tutorial,” Interfaces 20(4), 133–149, เผยแพร่ออนไลน์ 1 สิงหาคม 1990. หน้าวารสารและ DOI · PDF ผู้เขียน.
- FACT — การจำแนกปัญหาจัดสรรงานหลายหุ่นยนต์: Brian P. Gerkey & Maja J. Matarić, “A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems,” The International Journal of Robotics Research 23(9), 939–954, กันยายน 2004. PDF ผู้เขียน.
- FACT — ข้อมูล implementation ของ solver เปรียบเทียบ: SciPy, scipy.optimize.linear_sum_assignment; เอกสารระบุว่าใช้อัลกอริทึม modified Jonker–Volgenant. เอกสาร API.
- ขอบเขตการเปรียบเทียบ: Han-Lim Choi, Luc Brunet & Jonathan P. How, “Consensus-Based Decentralized Auctions for Robust Task Allocation,” IEEE Transactions on Robotics 25(4), 912–926, 2009. DOI. ใช้อ้างเพื่อแยก CBBA ออกจาก simulator นี้ ไม่ได้นำมาอธิบาย auction update หลัก.
- FACT — โค้ดต้นทางที่อ่านแต่ไม่ได้รัน: Network optimization codes · auction.txt. หัวไฟล์อัปเดต 7 พฤษภาคม 1992; AUCTION version 1.1 กันยายน 1990 มี ε-scaling ต่างจาก Lab นี้ และ license ยัง UNKNOWN.
ใส่ความเห็น