ปัญหาการเพิ่มสวัสดิภาพสูงสุดเป็นปัญหาการหาค่าเหมาะสมที่สุดที่ศึกษาในเศรษฐศาสตร์และวิทยาศาสตร์คอมพิวเตอร์เป้าหมายคือการแบ่งชุดของรายการต่างๆ ระหว่างตัวแทนที่มีฟังก์ชันอรรถประโยชน์ ที่แตกต่างกัน เพื่อให้สวัสดิภาพ – ซึ่งกำหนดเป็นผลรวมของอรรถประโยชน์ของตัวแทน – สูงที่สุดเท่า ที่จะเป็นไปได้ กล่าวอีกนัยหนึ่ง เป้าหมายคือการหาการจัดสรรรายการที่สอดคล้องกับกฎอรรถประโยชน์^{[ 1 ]}

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

มีเซตMที่ประกอบด้วย สิ่งของ mชิ้น และเซตNที่ประกอบด้วย ตัวแทน nตัว ตัวแทนแต่ละตัวiในNมีฟังก์ชันอรรถประโยชน์ ฟังก์ชันนี้กำหนดค่าจริงให้กับเซตย่อยที่เป็นไปได้ทั้งหมดของสิ่งของ โดยทั่วไปแล้วจะถือว่าฟังก์ชันอรรถประโยชน์เป็นฟังก์ชันเซตแบบโมโนโทนนั่นคือหมายความว่า นอกจากนี้ยังถือว่าเมื่อรวมกับความเป็นโมโนโทนแล้ว สิ่งนี้หมายความว่าอรรถประโยชน์ทั้งหมดมีค่าไม่เป็นลบ ${\displaystyle u_{i}:2^{M}\to \mathbb {R} }$${\displaystyle Z_{1}\supseteq Z_{2}}$${\displaystyle u_{i}(Z_{1})\geq u_{i}(Z_{2})}$${\displaystyle u_{i}(\emptyset )=0}$

การจัดสรรคือการแบ่งรายการออกเป็นnเซตย่อยที่ไม่ซ้ำกัน โดยแต่ละเซตย่อยแทนด้วยตัวแทนหนึ่งราย ซึ่งกำหนดให้เป็นโดยที่สวัสดิภาพของการจัดสรรคือผลรวมของอรรถประโยชน์ของตัวแทน: ${\displaystyle \mathbf {X} =(X_{1},\ldots ,X_{n})}$${\displaystyle M=X_{1}\sqcup \cdots \sqcup X_{n}}$${\displaystyle W(\mathbf {X} ):=\sum _{i\in N}u_{i}(X_{i})}$

ปัญหาการเพิ่มสวัสดิภาพสูงสุดคือ: หาการจัดสรรX ที่ทำให้ W ( X ) สูงสุด

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

ตัวแทนแบบเพิ่มค่าจะมีฟังก์ชันอรรถประโยชน์ที่เป็นฟังก์ชันเซตแบบเพิ่มค่า : สำหรับตัวแทนแบบเพิ่มค่าi ทุกตัว และสินค้าj ทุกรายการ จะมีค่าที่ทำให้สำหรับเซต สินค้า Z ทุกเซต เมื่อตัวแทนทั้งหมดเป็นแบบเพิ่มค่า การเพิ่มสวัสดิภาพสูงสุดสามารถทำได้ด้วยอัลกอริทึมแบบง่ายๆที่ใช้เวลาในการคำนวณแบบพหุนาม : มอบสินค้าj แต่ละรายการ ให้กับตัวแทนที่มีค่า สูงสุด (โดยการตัดสินใจในกรณีที่มีค่าเท่ากันโดยพลการ) ปัญหาจะมีความท้าทายมากขึ้นเมื่อมีข้อจำกัดเพิ่มเติมในการจัดสรร ${\displaystyle v_{i,j}}$${\displaystyle u_{i}(Z)=\sum _{j\in X_{i}}v_{i,j}}$${\displaystyle v_{i,j}}$

อาจต้องการเพิ่มสวัสดิภาพสูงสุดในบรรดาการจัดสรรทั้งหมดที่เป็นธรรมเช่นปราศจากความอิจฉาจนถึงรายการเดียว (EF1) เป็นสัดส่วนจนถึงรายการเดียว (PROP1) หรือเท่าเทียมกันจนถึงรายการเดียว (EQ1) ปัญหานี้เป็นปัญหา NP-hard อย่างมากเมื่อnเป็นตัวแปร สำหรับn ≥ 2 ที่กำหนดไว้ ปัญหานี้เป็น NP-hard อย่างอ่อน^{[ 2 ] [ 3 ]}และมี อัลกอริทึม เวลาพсевдоพหุนามที่ใช้ การ เขียนโปรแกรมแบบไดนามิก^{[ 2 ]}สำหรับn = 2ปัญหานี้มีแผนการประมาณค่าเวลาพหุนามอย่างสมบูรณ์^{[ 4 ]}

มีอัลกอริธึมสำหรับการแก้ปัญหานี้ในเวลาพหุนามเมื่อมีตัวแทนประเภทน้อย ประเภทของรายการน้อย หรือระดับค่าเล็ก^{[ 5 ]}ปัญหานี้ยังสามารถแก้ไขได้ในเวลาพหุนามเมื่อยูทิลิตี้แบบบวกของตัวแทนเป็นแบบไบนารี (ค่าของแต่ละรายการเป็น 0 หรือ 1) เช่นเดียวกับยูทิลิตี้ประเภททั่วไปที่เรียกว่าไบนารีแบบทั่วไป^{[ 6 ]}

ข้อจำกัดอีกประการหนึ่งในการจัดสรรคือ ชุดข้อมูลต้องเป็นเซตอิสระของเมทรอยด์ตัวอย่างเช่น แต่ละชุดข้อมูลต้องมีรายการไม่เกินkรายการ โดยที่kเป็นจำนวนเต็มคงที่ (ซึ่งสอดคล้องกับเมทรอยด์แบบเอกรูป ) หรือ รายการอาจถูกแบ่งออกเป็นหมวดหมู่ และแต่ละชุดข้อมูลต้องมีรายการไม่เกินk _{รายการ}จากแต่ละหมวดหมู่c (ซึ่งสอดคล้องกับเมทรอยด์แบบแบ่งส่วน ) โดยทั่วไป อาจมีเมทรอยด์ที่แตกต่างกันสำหรับแต่ละเอเจนต์ และการจัดสรรต้องให้แต่ละเอเจนต์i ได้ รับเซตย่อยX _iซึ่งเป็นเซตอิสระของเมทรอยด์ของตนเอง

การเพิ่มสวัสดิการสูงสุดด้วยยูทิลิตี้แบบบวกภายใต้ข้อจำกัดของเมทริกซ์ที่ไม่เหมือนกันสามารถทำได้ในเวลาพหุนาม โดยการลดให้เป็นปัญหาการตัดกันของเมทริกซ์แบบถ่วงน้ำหนัก^{[ 7 ]}

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

ตัวแทนแบบซับโมดูลาร์มีฟังก์ชันอรรถประโยชน์ที่เป็นฟังก์ชันเซตแบบซับโมดูลาร์ซึ่งหมายความว่าอรรถประโยชน์ของตัวแทนนั้นมีค่าส่วนเพิ่มที่ลดลงอรรถประโยชน์แบบซับโมดูลาร์มีความทั่วไปมากกว่าอรรถประโยชน์แบบทดแทนขั้นต้น

การเพิ่มสวัสดิการสูงสุดด้วยตัวแทนย่อยโมดูลาร์เป็นปัญหา NP-hard ^{[ 9 ]}ยิ่งไปกว่านั้น ไม่สามารถประมาณค่าได้ดีกว่าปัจจัย (1-1/e)≈0.632 เว้นแต่ว่า P=NP ^{[ 10 ]}ยิ่งไปกว่านั้น การประมาณค่าที่ดีกว่า (1-1/e) จะต้องใช้การสอบถามไปยังออราเคิล ค่าจำนวนมหาศาล ไม่ว่า P=NP จะเป็นอย่างไรก็ตาม^{[ 11 ]}

สามารถประมาณค่าสวัสดิภาพสูงสุดได้โดยใช้อัลกอริทึมแบบโลภ ( greedy algorithm) ที่ ใช้เวลาในการประมวลผลแบบพหุนามดังต่อไปนี้ :

• กำหนดค่าเริ่มต้นX ₁ = X ₂ = ... = X _n = ว่างเปล่า
• สำหรับแต่ละรายการg (โดยเรียงลำดับตามอำเภอใจ):
  • คำนวณอรรถประโยชน์ส่วนเพิ่มสำหรับตัวแทนแต่ละคนi สำหรับ gซึ่งกำหนดโดย: u _i ( X _i + g ) - u _i ( X _i )
  • มอบสินค้าgให้แก่ตัวแทนที่มีอรรถประโยชน์ส่วนเพิ่มสูงสุด

Lehman, Lehman และ Nisan ^{[ 9 ]}พิสูจน์ว่าอัลกอริทึมแบบโลภพบการประมาณค่า 1/2 ปัจจัย (พวกเขาตั้งข้อสังเกตว่าผลลัพธ์นี้เป็นผลมาจากผลลัพธ์ของ Fisher, Nemhauser และ Wolsey ^{[ 12 ]}เกี่ยวกับการเพิ่มค่าสูงสุดของการประเมินค่าย่อยโมดูลาร์เดียวเหนือเมทริกซ์) แนวคิดการพิสูจน์มีดังนี้ สมมติว่าอัลกอริทึมจัดสรรรายการgให้กับตัวแทนi บางราย สิ่งนี้มีส่วนช่วยต่อสวัสดิภาพในปริมาณvซึ่งเป็นอรรถประโยชน์ส่วนเพิ่มของgสำหรับiณ จุดนั้น สมมติว่าในวิธีแก้ปัญหาที่เหมาะสมที่สุดgควรถูกมอบให้กับตัวแทนอื่น เช่นkพิจารณาว่าสวัสดิภาพเปลี่ยนแปลงอย่างไรหากเราย้ายgจาก i ไปยังk :

• อรรถประโยชน์ของkเพิ่มขึ้นตามอรรถประโยชน์ส่วนเพิ่มของgซึ่งมีค่าสูงสุดเท่ากับvตามการเลือกแบบโลภ
• อรรถประโยชน์ส่วนเพิ่มของกลุ่มสินค้าi ที่เหลืออยู่จะเพิ่มขึ้นไม่เกินvซึ่งเป็นผลมาจากหลักการย่อยโมดูลาร์: อรรถประโยชน์ส่วนเพิ่มของgเมื่อนำไปรวมกับกลุ่มสินค้าที่เหลืออยู่ จะไม่สามารถสูงกว่าอรรถประโยชน์ส่วนเพิ่มของ g เมื่ออัลกอริทึมประมวลผลแล้ว

ดังนั้น สำหรับทุกๆ การมีส่วนร่วมของvต่อสวัสดิภาพของอัลกอริทึม การมีส่วนร่วมที่เป็นไปได้ต่อสวัสดิภาพที่เหมาะสมที่สุดจะมีค่าสูงสุดเพียง 2v เท่านั้นดังนั้นสวัสดิภาพที่เหมาะสมที่สุดจึงมีค่าสูงสุดเพียง 2 เท่าของสวัสดิภาพของอัลกอริทึม ปัจจัย 2 นี้ถือว่าค่อนข้างจำกัดสำหรับอัลกอริทึมแบบโลภ (greedy algorithm) ตัวอย่างเช่น สมมติว่ามีสินค้าสองรายการคือ x และ y และมีมูลค่าดังนี้:

การจัดสรรที่เหมาะสมที่สุดคือ อลิซ: {y}, จอร์จ: {x} โดยมีสวัสดิการเท่ากับ 2 แต่ถ้าอัลกอริทึมแบบโลภจัดสรร x ก่อน มันอาจจะจัดสรรให้กับอลิซ ในกรณีนั้น ไม่ว่า y จะถูกจัดสรรอย่างไร สวัสดิการก็จะมีเพียง 1 เท่านั้น

Value Oracleคือ Oracle ที่เมื่อได้รับชุดข้อมูลแล้ว จะส่งคืนค่าของ Agent ให้กับชุดข้อมูลนั้น ในแบบจำลองนี้:

• Dobzinski และ Schapira ^{[ 13 ]}นำเสนออัลกอริทึมการประมาณค่าแบบพหุนาม และอัลกอริทึมการประมาณค่า (1-1/e)≈0.632 สำหรับกรณีพิเศษที่ยูทิลิตี้ของตัวแทนเป็นฟังก์ชันการครอบคลุมเซต${\displaystyle n/(2n-1)}$
• Vondrak ^{[ 14 ] : Sec.5} และ Calinescu, Chekuri, Pal และ Vondrak ^{[ 15 ]}นำเสนออัลกอริทึมโพลีไทม์แบบสุ่มที่ค้นหาการประมาณค่า (1-1/e) ด้วยความน่าจะเป็นสูงอัลกอริทึมของพวกเขาใช้อัลกอริทึมแบบโลภต่อเนื่อง ซึ่งเป็นอัลกอริทึมที่ขยาย บันเดิ ลเศษส่วน (บันเดิลที่ประกอบด้วยเศษส่วนp _jของแต่ละรายการj ) ในทิศทางโลภ (คล้ายกับการไล่ระดับลง ) อัลกอริทึมของพวกเขาจำเป็นต้องคำนวณค่าของบันเดิลเศษส่วน ซึ่งกำหนดเป็นค่าที่คาดหวังของบันเดิลที่ได้รับเมื่อแต่ละรายการjถูกเลือกอย่างอิสระด้วยความน่าจะเป็นp _jโดยทั่วไป การคำนวณค่าของบันเดิลเศษส่วนอาจต้องใช้การเรียกไปยังออราเคิลค่า 2 ^{m ครั้ง} อย่างไรก็ตาม สามารถคำนวณโดยประมาณได้ ด้วยความน่าจะเป็นสูงโดยการสุ่มตัวอย่างแบบสุ่มซึ่งนำไปสู่อัลกอริทึมแบบสุ่มที่บรรลุการประมาณค่า (1-1/e) ด้วยความน่าจะเป็นสูง ในกรณีที่สามารถประเมินบันเดิลเศษส่วนได้อย่างมีประสิทธิภาพ (เช่น เมื่อฟังก์ชันยูทิลิตี้เป็นฟังก์ชันการครอบคลุมเซต) อัลกอริทึมสามารถทำให้เป็นแบบกำหนดได้^{[ 15 ] : ส่วนที่ 5} สำหรับฟังก์ชันซับโมดูลาร์โมโนโทนทั่วไป Buchbinder และ Feldman ^{[ 16 ]}ได้อธิบายอัลกอริทึมการค้นหาแบบโลคอลที่แตกต่างกันซึ่งเป็นแบบกำหนดได้และรับประกันการประมาณค่า - ในเวลาพหุนามสำหรับค่าคงที่ใดๆ${\displaystyle (1-1/e-\epsilon )}$${\displaystyle \epsilon >0}$

ปัญหาการเพิ่มสวัสดิการสูงสุด (ด้วย ฟังก์ชันย่อยโมดูลาร์ที่แตกต่างกัน nฟังก์ชัน) สามารถลดทอนลงเหลือปัญหาการเพิ่ม ฟังก์ชันเซตย่อยโมดูลาร์ เดียว ให้สูงสุด ภายใต้ ข้อจำกัดของ เมทริกซ์ : ^{[ 9 ] [ 14 ] [ 15 ]}เมื่อกำหนดอินสแตนซ์ที่มีรายการmรายการและ ตัวแทน nราย ให้สร้างอินสแตนซ์ที่มี คู่ (ตัวแทน, รายการ) m * nคู่ โดยแต่ละคู่แสดงถึงการจัดสรรรายการให้กับตัวแทน สร้างฟังก์ชันเดียวที่กำหนดสวัสดิการทั้งหมดของการจัดสรรที่สอดคล้องกันให้กับแต่ละเซตของคู่ สามารถแสดงได้ว่า หากยูทิลิตี้ทั้งหมดเป็นฟังก์ชันย่อยโมดูลาร์ ฟังก์ชันสวัสดิการนี้ก็เป็นฟังก์ชันย่อยโมดูลาร์เช่นกัน ฟังก์ชันนี้ควรได้รับการเพิ่มให้สูงสุดภายใต้ ข้อจำกัดของ เมทริกซ์การแบ่งส่วนเพื่อให้แน่ใจว่าแต่ละรายการจะถูกจัดสรรให้กับตัวแทนไม่เกินหนึ่งราย

อีกวิธีหนึ่งในการเข้าถึงอรรถประโยชน์ของตัวแทนคือการใช้ตัวพยากรณ์ความต้องการ (ตัวพยากรณ์ที่เมื่อได้รับเวกเตอร์ราคา จะส่งคืนชุดสินค้าที่ตัวแทนต้องการมากที่สุด) ในแบบจำลองนี้:

• Dobzinski และ Schapira ^{[ 13 ]}นำเสนออัลกอริทึมการประมาณค่าแบบ polytime (1-1/e)
• FeigeและVondrak ^{[ 17 ]}ปรับปรุงสิ่งนี้เป็น (1-1/e+ε) สำหรับ ε บวกขนาดเล็กบางค่า(สิ่งนี้ไม่ขัดแย้งกับผลลัพธ์ความยากข้างต้น เนื่องจากผลลัพธ์ความยากใช้เพียงออราเคิลค่า ในตัวอย่างความยาก ออราเคิลความต้องการเองจะต้องใช้การสอบถามจำนวนมากแบบเลขชี้กำลัง )

เมื่อยูทิลิตี้ของตัวแทนเป็นฟังก์ชันเซตย่อยบวก (ทั่วไปกว่าซับโมดูลาร์) การประมาณค่าจะต้องใช้การสอบถามค่าจำนวนเลขชี้กำลัง^{[ 11 ]}${\displaystyle {\frac {1}{m^{1/2-\epsilon }}}}$

Feige ^{[ 18 ]}นำเสนอวิธีการปัดเศษคำตอบเศษส่วนใดๆ ของการผ่อนคลาย LP ของปัญหานี้ให้เป็นคำตอบที่เป็นไปได้โดยมีสวัสดิการอย่างน้อย 1/2 ของค่าคำตอบเศษส่วน ซึ่งให้ค่าประมาณ 1/2 สำหรับตัวแทนย่อยแบบทั่วไป และค่าประมาณ (1-1/e) สำหรับกรณีพิเศษของการประเมินค่าย่อย แบบเศษส่วน

เมื่อยูทิลิตี้ของตัวแทนเป็นฟังก์ชันเซตแบบบวกยิ่งยวด (ทั่วไปกว่าแบบโมดูลาร์ยิ่งยวด) การประมาณค่าจะต้องใช้การสอบถามค่าจำนวนมหาศาลแบบพหุนามยิ่งยวด^{[ 11 ]}${\displaystyle {\frac {(\log m)^{1+\epsilon }}{m}}}$

ตัวแทนที่มีเป้าหมายเดียวต้องการเพียงชุดสินค้าที่เฉพาะเจาะจงเท่านั้น สำหรับตัวแทนที่มีเป้าหมายเดียวแต่ละคนiจะมีชุดสินค้าที่ต้องการD _iและค่าV _i > 0 ซึ่งทำให้นั่นคือ ตัวแทนจะได้รับอรรถประโยชน์บวกคงที่ก็ต่อเมื่อสินค้าที่ได้รับประกอบด้วยชุดสินค้าที่ต้องการ เท่านั้น${\displaystyle u_{i}(Z)={\begin{cases}V_{i}&Z\supseteq D_{i}\\0&{\text{otherwise}}\end{cases}}}$

การเพิ่มสวัสดิการสูงสุดด้วยตัวแทนที่มีใจเดียวเป็นปัญหาNP-hardแม้ว่าสำหรับทุกiก็ตาม ในกรณีนี้ ปัญหาจะเทียบเท่ากับการบรรจุเซตซึ่งเป็นที่ทราบกันดีว่าเป็นปัญหา NP-hard ยิ่งไปกว่านั้น ไม่สามารถประมาณค่าได้ภายในปัจจัยคงที่ใดๆ (ตรงกันข้ามกับกรณีของตัวแทนย่อยโมดูลาร์) ^{[ 19 ] อั}ลกอริทึมที่ดีที่สุดที่ทราบกันดีประมาณค่าได้ภายในปัจจัย^[ 20 ^]${\displaystyle V_{i}=1}$${\displaystyle O({\sqrt {m}})}$

เมื่อตัวแทนสามารถมีฟังก์ชันอรรถประโยชน์แบบโมโนโทนตามอำเภอใจได้ (รวมถึงรายการเสริม ) การประมาณค่าสูงสุดของสวัสดิการจะทำได้ยากภายในปัจจัยใดๆ[ ^{21 ] อย่างไรก็ตาม}มีอัลกอริธึมที่ใช้การค้นหาพื้นที่สถานะซึ่งทำงานได้ดีมากในทางปฏิบัติ^{[ 22 ]}${\displaystyle O(n^{1/2-\epsilon })}$${\displaystyle \epsilon >0}$

• ปัญหาการเพิ่มอรรถประโยชน์สูงสุด
• การเพิ่มผลกำไรสูงสุด