Överväga en spelare som observerar en sekvens av oberoende, icke-negativa slumptal och tillåts att stoppa sekvensen när som helst, hävdar en belöning som motsvarar den senaste observationen. Den berömda profeten ojämlikhet av Krengel, Sucheston, och Garling hävdar att en spelare som vet fördelningen av varje slumpmässig variabel kan uppnå minst hälften så mycket belöning, i förväntan, som en "profet" som känner de provade värdena för varje slumpmässig variabel och kan välja den största. Vi generaliserar detta resultat till den miljö där spelaren och profeten tillåts göra mer än ett urval, under förutsättning att en matris begränsning. Vi visar att spelaren fortfarande kan uppnå minst hälften så mycket belöning som profeten; detta resultat är det bästa möjliga, eftersom det är känt att förhållandet inte kan förbättras även i den ursprungliga profeten ojämlikhet, vilket motsvarar det speciella fallet av rank-one matriser. Generalisera resultatet ytterligare, visar vi att under en korsning av p matris begränsningar, profetens belöning överstiger spelarens med en faktor på högst O(p), och denna faktor är också tight. Utöver deras intresse som teorem om rena online algoritmer eller optimala stopp regler, dessa resultat har också tillämpningar för mekanism design. Våra resultat innebär förbättrade gränser för förmågan hos sekventiella postade prismekanismer att approximera optimala mekanismer i en-parameter och multi-parameter Bayesian inställningar. I synnerhet innebär våra resultat de första effektiva beräkningsbara konstantfaktor approximationer till Bayesian optimala intäkter i vissa multi-parameter inställningar.
REF generalisera profeten ojämlikhet resulterar i matroidal miljö, och använda detta för att ge förbättrade approximationer för multi-parameter enhet-demand mekanism design problem.
Matroid prophet inequalities
{'venue': "STOC '12", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}