Vi studerar konkurrens inom en allmän ram som infördes av Immorlica, Kalai, Lucier, Moitra, Postlewaite och Tennenholtz [17] och besvarar deras huvudsakliga öppna fråga. Immorlica m.fl. [17] anses klassiska optimeringsproblem i termer av konkurrens och infört en allmän klass av spel som kallas dueller spel. De modellerar denna tävling som ett nollsummespel, där två spelare tävlar om en användares tillfredsställelse. I deras huvudsakliga och mest naturliga spel, ranking duell, en användare begär en webbsida genom att skicka en fråga och spelare ut en beställning över alla möjliga webbsidor baserat på den inlämnade frågan. Användaren tenderar att välja den beställning som visar hennes begärda webbsida i en högre rang. Målet med båda spelarna är att maximera sannolikheten för att hennes beställning slår hennes motståndare och får användarens uppmärksamhet. Immorlica m.fl. [17] visa detta spel leder båda spelarna att ge suboptimala sökresultat. De lämnar dock följande som sin huvudsakliga öppna fråga: "Förbättrar eller försämrar konkurrensen mellan algoritmer förväntade prestanda?" (se inledningen för fler citat) I detta dokument löser vi denna fråga för rankningen duell och en mer allmän klass av dueller spel. Mer exakt studerar vi kvaliteten på beställningar i en tävling mellan två spelare. Detta spel är en nollsumma spel, och därmed alla Nash jämvikt i spelet kan beskrivas med minimax strategier. Låt värdet av användaren för en beställning vara en funktion av positionen för hennes begärda objekt i motsvarande beställning, och social välfärd för en beställning vara det förväntade värdet av motsvarande beställning för användaren. Vi föreslår det pris på konkurrens som är förhållandet mellan social välfärd och den sämsta minimax-strategin och den sociala välfärd som en social planerare får. Att hitta priset på konkurrensen är en annan metod för att få strukturella resultat av Nash equilibria. Vi använder detta kriterium för att analysera kvaliteten på beställningar i rankningen duell. Även om Immorlica et al. [17] visar att konkurrensen leder till suboptimala strategier, vi bevisar kvaliteten på minimax resultat är förvånansvärt nära den optimala lösningen. Framför allt, genom en ny faktoruppenbarande LP för beräkning av priset på anarki, vi bevisa om värdet av användaren för en beställning är en linjär funktion av sin position, då priset för konkurrens är minst 0,612 och begränsas till 0,833. Dessutom anser vi att kostnadsminimering version av problemet. Vi bevisar att den sociala kostnaden för den sämsta minimax-strategin är högst 3 gånger den optimala sociala kostnaden. Sist men inte minst går vi längre än linjära värderingsfunktioner och fångar den största utmaningen för att begränsa priset på konkurrens för eventuella godtyckliga värderingsfunktioner. Vi presenterar en princip som anger att den lägre gränsen för konkurrenspriset för alla 0-1 värderingsfunktioner är densamma som den lägre gränsen för konkurrenspriset för alla möjliga värderingsfunktioner. Det är värt att nämna att denna princip inte bara fungerar för rankningen duell men också för alla duell spel. Denna princip säger, i alla dueller spel, den mest utmanande delen av att begränsa priset på konkurrens är att hitta en lägre gräns för 0-1 värdering funktioner. Vi utnyttjar denna princip för att visa att priset för konkurrens är minst 0,25 för den generaliserade ranking duell, och för att hitta övre gränser på priset för konkurrens för binär sök duell och komprimering duell som införs av Immorlica et al. [17]..................................................................
var huruvida konkurrensen mellan algoritmer förbättrar eller försämrar förväntade prestanda inom detta ramverk, som besvarades av Dehghani, Hajiaghayi, Mahini, och Seddighin REF för ranking duell och en mer allmän klass av duell spel.
Price of Competition and Dueling Games
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}