สมดุลการแข่งขันโดยประมาณจากรายได้ที่เท่ากัน ( A-CEEI ) เป็นกระบวนการสำหรับการจัดสรรสินค้าอย่างเป็นธรรมพัฒนาโดย Eric Budish ^{[ 1 ]}

CEEI (Competitive Equilibrium from Equal Incomes) คือกฎพื้นฐานสำหรับการแบ่งทรัพยากรที่สามารถแบ่งได้อย่างเป็นธรรม โดยจะแบ่งทรัพยากรตามผลลัพธ์ของกระบวนการสมมติดังต่อไปนี้:

• ตัวแทนแต่ละคนจะได้รับ เงินตราที่ไม่มีมูลค่าในตัวเองหนึ่งหน่วยนี่คือส่วนของหลักการกระจายรายได้อย่างเท่าเทียมกัน (Equal Incomes) ในโครงการ CEEI
• ตัวแทนจะทำการซื้อขายอย่างเสรีจนกว่าตลาดจะเข้าสู่ภาวะสมดุลการแข่งขันซึ่งเป็นเวกเตอร์ราคาและการจัดสรร โดยที่ (ก) ชุดสินค้าที่จัดสรรแต่ละชุดนั้นเหมาะสมที่สุดสำหรับตัวแทนแต่ละรายเมื่อพิจารณาจากรายได้ของเขา/เธอ กล่าวคือ ตัวแทนไม่สามารถซื้อสินค้าชุดที่ดีกว่าได้ด้วยรายได้เท่าเดิม และ (ข) ตลาดจะเข้าสู่ภาวะสมดุล กล่าวคือ ผลรวมของการจัดสรรทั้งหมดเท่ากับเงินทุนเริ่มต้นพอดี

การจัดสรรที่สมดุลนั้นพิสูจน์ได้ว่าปราศจากความอิจฉาและมีประสิทธิภาพแบบพาเรโตยิ่งไปกว่านั้น เมื่อตัวแทนมี ฟังก์ชัน อรรถประโยชน์เชิงเส้นการจัดสรร CEEI สามารถคำนวณได้อย่างมีประสิทธิภาพ

น่าเสียดายที่ในกรณีที่มีความไม่สามารถแบ่งแยกได้ ค่า CEEI อาจไม่มีอยู่เสมอไป ดังนั้นจึงไม่สามารถนำมาใช้โดยตรงในการจัดสรรรายการที่เป็นธรรมได้อย่างไรก็ตาม สามารถประมาณค่าได้ และการประมาณค่านั้นมีคุณสมบัติที่ดีในด้านความเป็นธรรม ประสิทธิภาพ และกลยุทธ์

A-CEEI เพียงแค่ตั้งสมมติฐานว่าตัวแทนรู้วิธีจัดลำดับกลุ่มของรายการต่างๆ การจัดลำดับนั้นไม่จำเป็นต้องเป็นแบบบวกอย่างอ่อนหรือแม้แต่แบบโมโนโทน

A-CEEI ที่มีพารามิเตอร์จะแบ่งทรัพยากรตามผลลัพธ์ของกระบวนการสมมติต่อไปนี้: ${\displaystyle \อัลฟา ,\เบต้า }$

• รายได้โดยประมาณ (Approximate-EI): ตัวแทนแต่ละคนจะได้รับรายได้ระหว่าง 1 ถึง... รายได้ที่แน่นอนของตัวแทนแต่ละคนสามารถกำหนดได้แบบสุ่ม หรือตามลำดับอาวุโส (ตัวแทนอาวุโสจะได้รับรายได้สูงกว่าเล็กน้อย)${\displaystyle 1+\beta }$
• Approximate-CE: เวกเตอร์ราคาและการจัดสรรจะถูกคำนวณ โดยที่ (ก) ชุดที่จัดสรรแต่ละชุดจะเหมาะสมที่สุดสำหรับตัวแทนแต่ละรายเมื่อพิจารณาจากงบประมาณ และ (ข) ตลาดจะ "เกือบ" สมดุล: ระยะทางแบบยุคลิดระหว่างผลรวมของการจัดสรรทั้งหมดกับเงินทุนเริ่มต้นมีค่าไม่เกิน${\displaystyle \alpha }$

Budish พิสูจน์ว่า สำหรับค่าใดๆ จะมี ค่า -CEEI อยู่ โดยที่ ขึ้นอยู่กับค่าต่ำสุดระหว่างจำนวนประเภทสินค้าที่แตกต่างกันและจำนวนสินค้าที่แตกต่างกันที่ตัวแทนอาจได้รับ ${\displaystyle \beta >0}$${\displaystyle \อัลฟา ,\เบต้า }$${\displaystyle \alpha }$

การจัดสรรนี้มีคุณสมบัติดังต่อไปนี้:

• ปราศจากความอิจฉายกเว้น 1 รายการ (ดูการกำหนดรายการที่ปราศจากความอิจฉา )
• ${\displaystyle (n+1)}$-การรับประกันส่วนแบ่งสูงสุด
• ประสิทธิภาพแบบพาเรโตเมื่อพิจารณาจากสินค้าที่จัดสรร กล่าวคือ ไม่มีธุรกรรมใดที่ช่วยปรับปรุงประสิทธิภาพแบบพาเรโตได้ระหว่างตัวแทน แต่Hอาจมีผู้ค้าที่ช่วยปรับปรุงประสิทธิภาพแบบพาเรโตได้ระหว่างตัวแทนกับผู้สร้างตลาด

ยิ่งไปกว่านั้น กลไก A-CEEI ยังป้องกันกลยุทธ์ที่ไม่ เหมาะสมได้ "ในภาพรวม" กล่าวคือ เมื่อมีตัวแทนจำนวนมาก ตัวแทนแต่ละรายจะมีอิทธิพลต่อราคาเพียงเล็กน้อย ดังนั้นตัวแทนจึงทำหน้าที่เป็นผู้รับราคาในกรณีเช่นนั้น การที่ตัวแทนแต่ละรายรายงานการประเมินมูลค่าที่แท้จริงของตนจึงเป็นสิ่งที่ดีที่สุด เนื่องจากจะช่วยให้กลไกสามารถมอบชุดสินค้าที่เหมาะสมที่สุดให้แก่ตัวแทนแต่ละรายโดยพิจารณาจากราคาได้

การจัดสรร A-CEEI นั้นยากต่อการคำนวณ: มันคือPPAD ที่สมบูรณ์^{[ 2 ]}

อย่างไรก็ตาม ในปัญหาที่มีขนาดสมจริง สามารถคำนวณ A-CEEI ได้โดยใช้กระบวนการค้นหาแบบสองระดับ:

1. ระดับขั้นสูง: ศูนย์นี้ใช้การค้นหาแบบ Tabuเพื่อแนะนำราคา;
2. ระดับตัวแทน: โปรแกรมเชิงจำนวนเต็มแบบผสมจะถูกแก้เพื่อหาความต้องการของตัวแทน ณ ราคาปัจจุบัน

โปรแกรมระดับเอเจนต์สามารถดำเนินการแบบขนานสำหรับเอเจนต์ทั้งหมดได้ ดังนั้นวิธีนี้จึงปรับขนาดได้ใกล้เคียงกับค่าที่เหมาะสมที่สุดในจำนวนโปรเซสเซอร์^{[ 3 ]}

กลไกนี้ได้รับการพิจารณาสำหรับงานการจัดสรรนักเรียนเข้าเรียนในหลักสูตรที่Wharton School ของมหาวิทยาลัยเพนซิลเวเนีย ^{[ 4 ​​]}

อัลกอริทึม Maximum -Nash-Welfare (MNW) จะค้นหาการจัดสรรที่เพิ่มผลคูณของอรรถประโยชน์ของตัวแทนให้สูงสุด อัลกอริทึมนี้คล้ายกับ A-CEEI ในหลายแง่มุม: ^{[ 5 ]}

• ทั้งสองอัลกอริทึมพบการจัดสรร EF-except-1
• ทั้งสองอัลกอริธึมเป็นการประมาณค่าการรับประกันส่วนแบ่งสูงสุด (maximin-share-guarantee)

อย่างไรก็ตาม A-CEEI มีข้อดีหลายประการ:

• มันใช้งานได้กับฟังก์ชันอรรถประโยชน์ใดๆ ก็ได้ ไม่ใช่แค่ ฟังก์ชัน ย่อย เท่านั้น และไม่จำเป็นต้องมีความเป็นเอกรูปของค่าความชอบด้วยซ้ำ
• ระบบนี้ทำงานกับข้อมูลเชิงลำดับ – ตัวแทนจะต้องรายงานเฉพาะการจัดอันดับของกลุ่มสินค้าเท่านั้น ไม่ใช่การประเมินมูลค่าเชิงตัวเลขของสินค้าแต่ละชิ้น
• นี่คือกลยุทธ์ที่พิสูจน์ได้ "ในวงกว้าง"

ในทางกลับกัน A-CEEI ก็มีข้อเสียหลายประการ:

• มีข้อผิดพลาดโดยประมาณในรายการที่จัดสรร - บางรายการอาจมีความต้องการเกินหรือมีอุปทานเกิน^{[ 6 ]}
• โดยเฉพาะอย่างยิ่ง การจัดสรรที่ส่งคืนมานั้นไม่มีประสิทธิภาพแบบพาเรโต กล่าวคือ ยังมีบางรายการที่ยังไม่ได้จัดสรร (จะมีประสิทธิภาพแบบพาเรโตเฉพาะในส่วนของรายการที่ได้รับการจัดสรรแล้วเท่านั้น)

ข้อผิดพลาดในการประมาณค่าของ A-CEEI จะเพิ่มขึ้นตามจำนวนรายการที่แตกต่างกัน แต่ไม่เพิ่มขึ้นตามจำนวนผู้เล่นหรือจำนวนสำเนาของแต่ละรายการ ดังนั้น A-CEEI จึงดีกว่าเมื่อมีตัวแทนจำนวนมากและมีสำเนาของแต่ละรายการจำนวนมาก แอปพลิเคชันทั่วไปคือเมื่อตัวแทนเป็นนักเรียนและรายการเป็นตำแหน่งในหลักสูตร^{[ 6 ]}

ในทางตรงกันข้าม MNW จะเหมาะสมกว่าเมื่อมีตัวแทนน้อยรายและมีรายการที่แตกต่างกันจำนวนมาก เช่น ในการแบ่งมรดก

A-CEEI (และ CEEI โดยทั่วไป) มีความเกี่ยวข้อง แต่ไม่เหมือนกับแนวคิดของสมดุลการแข่งขัน

• ภาวะสมดุลการแข่งขัน (Competitive equilibrium: CE) เป็นแนวคิดเชิงพรรณนา: มันอธิบายสถานการณ์ในตลาดเสรีเมื่อราคามีเสถียรภาพและอุปสงค์เท่ากับอุปทาน
• CEEI เป็นแนวคิดเชิงบรรทัดฐาน: มันอธิบายถึงกฎสำหรับการแบ่งสินค้าโภคภัณฑ์ระหว่างผู้คน

• การประมูลแบบผสมผสาน