I utformningen och analysen av intäktsmaximering auktioner, är auktionen prestanda normalt mäts med avseende på en tidigare distribution över indata. Den mest uppenbara källan till en sådan distribution är tidigare data. Syftet med detta dokument är att förstå hur mycket uppgifter som är nödvändiga och tillräckliga för att garantera nästan optimala förväntade intäkter. Vår grundmodell är en enda auktion där budgivarnas värderingar är oberoende av okända och icke-identiska distributioner. Säljaren får m prover från var och en av dessa distributioner "gratis" och väljer en auktion för att köra på ett nytt prov. Hur stor måste m vara, som en funktion av antalet k budgivare och > 0, så att en (1 − )-uppskattning av de optimala intäkterna är möjlig? Vi bevisar att under normala svansförhållanden på de underliggande distributionerna är m = poly(k, 1 ) prover nödvändiga och tillräckliga. Vår lägre gräns står i kontrast till många färska resultat på enkla och tidigare oberoende auktioner och innebär i grunden samspelet mellan anbudsgivarnas konkurrens, icke-identiska distributioner, och en mycket nära (men fortfarande konstant) approximation av de optimala intäkterna. Det visar i praktiken att det enda sättet att uppnå en tillräckligt god konstant approximering av de optimala intäkterna är genom en detaljerad förståelse av anbudsgivarnas värderingsutdelningar. Vår övre gräns är konstruktiv och gäller särskilt för en variant av den empiriska Myersonauktionen, den naturliga auktionen som driver den intäktsmaximerande auktionen med avseende på den empiriska fördelningen av proverna. En uppsättning tillåtna fördelningar, vi introducerar α-starkt regelbundna fördelningar, som interpolerar mellan välstuderade klasser av regelbundna (α = 0) och MHR (α = 1) fördelningar. Vi ger bevis för att denna definition är av oberoende intresse.
Cole och Roughgarden REF-studie single-item auktioner med n budgivare med värderingar hämtade från oberoende (inte nödvändigtvis identiska) "regelbundna" distributioner (se avsnitt 2), och bevisa övre och nedre gränser (polynom i n och  på -1 ) om urvalet komplexiteten i att lära a (1 -  på)-ungefärlig auktion.
The sample complexity of revenue maximization
{'venue': "STOC '14", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}