Vi presenterar en allmän ram för att bevisa polynomiska urval komplexitet gränser för problemet med att lära sig från prover den bästa auktionen i en klass av "enkel" auktioner. Vårt ramverk fångar alla de mest framträdande exemplen på "enkla" auktioner, inklusive anonyma och icke-anonyma objekt och paketpriser, med antingen en enda eller flera köpare. Den teknik vi föreslår är att bryta analysen av auktioner i två naturliga bitar. För det första visar en uppsättning tilldelningsregler att de har stora mängder struktur; för det andra, fastställande av en tilldelning på ett urval, ett visar att uppsättningen auktioner som samtycker till denna tilldelning på detta urval har intäktsfunktioner med låg dimensionalitet. Våra resultat innebär effektivt att när det är möjligt att beräkna en nästan optimal enkel auktion med en känd tidigare, är det också möjligt att beräkna en sådan auktion med en okänd tidigare (med ett polynom antal prover).
Problemen med att lära sig enkla auktioner från prover har studerats i REF.
Learning Simple Auctions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}