Tänk på en spelare och en profet som observerar en sekvens av oberoende, icke-negativa tal. Spelaren ser siffrorna en efter en medan profeten ser hela sekvensen på en gång. Målet med båda är att besluta om fraktioner av varje tal de vill behålla för att maximera den viktade delsumman av de valda talen. Det klassiska resultatet av Krengel och Sucheston (1977-78) hävdar att om både spelaren och profeten kan välja ett nummer, då kan spelaren göra minst hälften så bra som profeten. Nyligen har Kleinberg och Weinberg (2012) generaliserat detta resultat till inställningar där de nummer som kan väljas är föremål för en matrisrestriktion. I denna not går vi ett steg längre och visar att den bundna för över till inställningar där de bråk som kan väljas är föremål för en polymatroid restriktion. Detta band är tight eftersom det redan är tight för den enkla inställningen där spelaren och profeten kan välja bara ett nummer. En intressant tillämpning av vårt resultat är i mekanismdesign, där det leder till förbättrade resultat för olika problem.
Dütting och Kleinberg REF utökar detta resultat till polymatroider.
Polymatroid Prophet Inequalities
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}