Vi introducerar en ny hierarki över monotone set funktioner, som vi kallar MPH (Maximum over Positive Hypergraphs). Nivåerna i hierarkin motsvarar graden av komplementaritet i en viss funktion. Den högsta nivån i hierarkin, MPH-m (där m är det totala antalet objekt) fångar alla monotona funktioner. Den lägsta nivån, MPH-1, fångar alla monotona submodulära funktioner, och mer allmänt, den klass av funktioner som kallas X OS. Varje monoton funktion som har en positiv hypergraf representation av rank k (i betydelsen definieras av Abraham, Babaioff, Dughmi och Roughgarden [EC 2012]) är i MPH-k. Varje monoton funktion som har supermodulär grad k (i betydelsen definieras av Feige och Izsak [ITCS 2013]) är i MPH-(k + 1). I båda fallen håller inte den motsatta riktningen, inte ens i ungefärlig bemärkelse. Vi presenterar ytterligare resultat som visar uttryckskraften hos MPH-k. Man kan få bra approximationsförhållanden för vissa naturliga optimeringsproblem, förutsatt att funktioner krävs för att ligga i låga nivåer av MPH hierarki. Vi lägger fram två sådana ansökningar. En visar att det maximala välfärdsproblemet kan approximeras inom ett förhållande på k + 1 om alla spelare har värderingsfunktioner i MPH-k. Den andra är en övre gräns på 2k på priset på anarki av samtidiga första pris auktioner. Att vara i MPH-k kan visas att omfatta två krav -ett är monotonitet och det andra är ett visst krav som vi kallar P LE (Positive Lower Envelope). Genom att ta bort kravet på monotonitet får man PLE-hierarkin över alla icke-negativa uppsättningsfunktioner (oavsett om de är monotona eller inte), som kan vara bördig grund för ytterligare forskning.
REF introducerar en komplett hierarki av monotona funktioner, den maximala över positiva hypergrafer med rang som mest k, MPH-k.
A Unifying Hierarchy of Valuations with Complements and Substitutes
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}