I den klassiska profeten ojämlikhet, en spelare observerar en sekvens av stokastiska belöningar V1,..., Vn och måste besluta, för varje belöning Vi, om att behålla det och stoppa spelet eller att förlora belöningen för evigt och avslöja nästa värde Vi. Spelarens mål är att få en konstant bråkdel av den förväntade belöningen som den optimala offline-algoritmen skulle få. Nyligen har profeten ojämlikhet generaliserats till inställningar där spelaren kan välja k objekt, och, mer allmänt, där han kan välja någon oberoende uppsättning i en matris. Alla befintliga algoritmer kräver dock att spelaren vet den distribution från vilken belöningarna V1,..., Vn dras. Antagandet att spelaren vet distributionen från vilken V1,..., Vn dras är mycket stark. Istället arbetar vi med det mycket enklare antagandet att spelaren bara känner till några få prover från denna distribution. Vi konstruerar den första enkelprov profeten ojämlikheter för många miljöer av intresse, vars garanterar alla matchar bästa möjliga asymptotiskt, även med full kunskap om distributionen. Specifikt ger vi en ny algoritm ett enda prov när spelaren kan välja alla k element vars analys är baserad på slumpmässiga promenader med begränsad korrelation. Dessutom tillhandahåller vi en svart-box metod för att omvandla specifika typer av lösningar till relaterade sekreterare problem till enstaka prov profet ojämlikheter, och tillämpa den på flera befintliga algoritmer. Slutligen ger vi en konstant-prov profet ojämlikhet för konstant-grad bipartit matchningar. Dessutom tillämpar vi dessa resultat för att utforma de första postade och flerdimensionella auktionsmekanismerna med begränsad information i miljöer med asymmetriska budgivare. Kopplingar mellan profetens ojämlikheter och postade prismekanismer är redan kända, men att tillämpa det befintliga ramverket kräver kunskap om de underliggande distributionerna, liksom de så kallade "virtuella värdena" även när de underliggande profetklyftorna inte gör det. Vi tillhandahåller därför en förlängning av denna ram som helt förbigår virtuella värden, vilket gör det möjligt för våra mekanismer att dra full nytta av den begränsade information som krävs av våra nya profeters ojämlikheter.
Ref studie profeten ojämlikhet under ett enda urval inställning.
Prophet Inequalities with Limited Information
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}