Att hitta optimala lösningar för kombinatoriska auktioner med flera enheter är ett svårt problem och att hitta approximationer till den optimala lösningen är också svårt. Vi undersöker användningen av Branch-and-Bound tekniker: de kräver både ett sätt att binda från över värdet av den bästa tilldelningen och ett bra kriterium för att avgöra vilka bud som ska prövas först. Olika metoder för effektiv begränsning från över värdet av den bästa fördelningen beaktas. Teoretiska originalresultat kännetecknar det bästa approximationsförhållande och det beställningskriterium som ger det. Vi föreslår att man använder detta kriterium. Kombinatoriska auktioner, Branch and Bound Auktioner har använts sedan urminnes tider, men det förnyade moderna intresset för auktioner härrör från: • deras ökade användning för att sälja av statlig egendom efter andra världskriget och senare i omfattande denationaliseringar, och • de teoretiska genombrotten startade med [14]. En mycket ny ökning av intresset för auktioner beror på deras överraskande framgång på internet. Många förutser internetauktioner där: • antalet köpare kommer att vara stort • antalet föremål för försäljning kommer att vara stort • den mekanism som används för att bestämma tilldelningen och betalningen kommer att vara komplex både ur spelteoretisk strategisk och ur beräkningssynpunkt.
Ett annat arbete som också använder en gren-och-bundet teknik för att lösa multi-enhet combinatorial auktion problem presenteras i REF.
Optimal Solutions for Multi-Unit Combinatorial Auctions: Branch and Bound Heuristics
{'venue': "Second ACM Conference on Electronic Commerce (EC'00) Minneapolis, Minnesota, October 2000, pp. 13-20", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}