Motiverade av problemet med att fråga och kommunicera budgivares värderingar i kombinatoriska auktioner, studerar vi hur väl olika klasser av set-funktioner kan skissas. Mer formellt, låt f vara en funktion kartläggning undergrupper av vissa markuppsättning [n] till icke-negativa reella tal. Vi säger att f är en α-sketch av f om för varje uppsättning S, värdet f (S) ligger mellan f (S)/α och f (S), och f kan anges med poly(n) bitar. Vi visar att för varje subadditiv funktion f finns det en α-sketch där α = n 1/2 · O(polylog(n)). Dessutom tillhandahåller vi en algoritm som finner dessa skisser med ett polynomtal kravfrågor. Detta är i grund och botten det bästa vi kan hoppas på sedan: 1. Vi visar att det finns subadditiva funktioner (i själva verket XOS funktioner) som inte medger en o(n 1/2 ) skiss. (Balcan och Harvey [3] har tidigare visat att det finns funktioner som tillhör kategorin ersättningsvärderingar som inte medger en O(n 1/3 ) skiss.) 2. Utgångspunkten är följande: Vi bevisar att varje deterministisk algoritm som kommer åt funktionen via värdefrågor bara inte kan garantera ett skissförhållande bättre än n 1—. Vi visar också att täckningsfunktioner, en intressant underklass av submodulära funktioner, medger godtyckligt bra skisser. Slutligen visar vi ett intressant samband mellan skissning och lärande. Vi visar att för varje klass av värderingar, om klassen medger en α-sketch, kan det α-ungefär läras i PMAC-modellen av Balcan och Harvey. Gränserna vi bevisar är endast informationsteoretiska och antyder inte förekomsten av beräkningseffektiva inlärningsalgoritmer i allmänhet.
Därefter, Balcan et al. gav en distributionsoberoende PMAC inlärningsalgoritm för XOS-funktioner som uppnår en Õ ( ε n)-uppskattning och visade att detta i huvudsak är optimal REF.
Sketching Valuation Functions
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}