Traditionellt har problemet med Bayesian optimal auktionsdesign beaktats antingen när budgivarens värden är i.i.d, eller när varje budgivare är individuellt identifierbar via sin värdefördelning. Det senare är ett rimligt tillvägagångssätt när anbudsgivarna kan klassificeras i ett fåtal kategorier, men det finns många fall där klassificeringen av budgivare är en kontinuum. Till exempel, klassificeringen av budgivarna kan baseras på deras årsinkomst, deras benägenhet att köpa en post baserat på tidigare beteende, eller i fallet med annonsauktioner, klicka genom takten på deras annonser. Vi introducerar en alternativ modell som fångar denna aspekt, där budgivarna är en i förväg identisk, men kan särskiljas baserat (endast) på någon sida information auktionsförrättaren får vid tidpunkten för auktionen. Vi utökar urvalet komplexitet strategi Dhangwatnotai et al. Cole och Roughgarden till denna modell och få nästan matchande övre och nedre gränser. Som en åt sidan får vi en inkomst monotonitet lemma som kan vara av oberoende intresse. Vi visar också hur man använder empiriska riskminimering tekniker för att förbättra provet komplexitet bunden av Cole och Roughgarden för icke-identiska men oberoende värdefördelning fall.
REF ger urvalskomplexa gränser för utformningen av optimala auktioner med sidoinformation.
The sample complexity of auctions with side information
{'venue': 'STOC 2016', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}