I samband med auktioner för digitala varor har en intressant auktion för slumpmässigt urval föreslagits av. Auktionen har analyserats av Feige et al. [2005], som har visat att det får i förväntan minst 1/15 bråkdel av de optimala intäkterna, vilket är betydligt bättre än de tidigare bevisade konstanta gränser men fortfarande långt från den förmodade lägre gränsen av 1/4. I denna artikel bevisar vi att ovannämnda slumpmässiga urval auktion får minst 1/4 bråkdel av de optimala intäkterna för en stor klass av fall där antalet bud över (eller lika med) det optimala försäljningspriset är minst 6. Vi visar också att denna auktion får minst 1/4,68 procent av de optimala intäkterna för den lilla klassen av återstående fall, vilket lämnar ett försumbart gap mellan den nedre och övre gränsen. Vi använder en blandning av probabilistiska tekniker och dynamisk programmering för att beräkna dessa gränser.
Alaei m.fl. REF ger en nästan snäv analys av RSOP som visar att det är 4 konkurrenskraftiga för en stor grupp fall och 4.68 konkurrenskraftiga för en mycket mindre klass av återstående fall.
On Random Sampling Auctions for Digital Goods
{'venue': 'TEAC', 'journal': None, 'mag_field_of_study': ['Computer Science']}