Vi studerar problemet med att sätta ett pris för en potentiell köpare med en värdering från en okänd distribution D. Säljaren har "data" om D i form av m ≥ 1 i.i.d. Prover, och den algoritmiska utmaningen är att använda dessa prover för att få förväntade intäkter så nära som möjligt till vad som kan uppnås med förhandskunskap om D. Vår första uppsättning av resultat kvantifierar antalet prover m som är nödvändiga och tillräckliga för att erhålla en (1 - )- approximation. Till exempel, för en okänd fördelning som uppfyller monoton riskfrekvens (MHR) villkorar, vi bevisar att ( −3/2 ) prover är nödvändiga och tillräckliga. Anmärkningsvärt nog är detta färre urval än vad som är nödvändigt för att korrekt uppskatta de förväntade intäkterna för en sådan fördelning genom till och med ett enda reservpris. Vi visar också i huvudsak snäva urval komplexitet gränser för regelbundna distributioner, begränsad-stöd distributioner, och en bred klass av oregelbundna distributioner. Vår lägre gräns, som gäller för alla randomiserade prissättningsstrategier, lånar verktyg från differential integritet och information teori, och vi tror att det kan hitta ytterligare tillämpningar i auktionsteori. Vår andra uppsättning resultat tar hänsyn till fallet med ett enda urval. Även om ingen deterministisk prissättningsstrategi är bättre än 12 - ungefärlig för regelbundna distributioner, visar vi för MHR-distributioner hur man kan göra bättre: det finns en enkel deterministisk prissättningsstrategi som garanterar förväntade intäkter minst 0,589 gånger så mycket som möjligt. Vi bevisar också att ingen deterministisk prissättningsstrategi uppnår en tillnärmningsgaranti som är bättre än e 4  på.68.
Jo, Huang och Al. REF studerar problemet med att fastställa ett pris för en potentiell köpare med en värdering som hämtats från en okänd distribution D och visar sig vara snäva urvalskomplexa gränser för regelbundna distributioner, begränsade distributioner och en bred klass av oregelbundna distributioner.
Making the Most of Your Samples
{'venue': "EC '15", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}