Vi fortsätter studien av välfärdsmaximering på enhetsefterfrågans (matchning) marknader, i en distribuerad informationsmodell där agentens värderingar är okända för den centrala planeraren, och därför krävs kommunikation för att fastställa en effektiv fördelning. Dobzinski, Nisan och Oren (STOC'14) visade att om marknadsstorleken är n, då r omgångar av interaktion (med logaritmisk bandbredd) räcker för att erhålla en n 1/(r+1) - approximation till optimal social välfärd. I synnerhet innebär detta att sådana marknader konvergerar till ett stabilt tillstånd (konstant approximation) i tid logaritmisk i marknadens storlek. Vi får den första multi-round nedre gränsen för den här installationen. Vi visar att även om den tillåtna per-round bandbredden för varje agens är n ε(r), approximationsförhållandet för alla r-round (randomized) protokoll är inte bättre än  på 1/5 r+1 ), vilket innebär en  och (log log n) lägre gräns för konvergensen av marknaden till jämvikt. Vår konstruktion och teknik kan vara av intresse för avrundning i den mer allmänna inställningen av kombinatoriska auktioner, för vilka den enda kända nedre gränsen är för samtidiga (r = 1) protokoll [DNO14]. I detta dokument studeras avvägningen mellan mängden kommunikation och antalet interaktionsrundor som krävs för att hitta en (ungefär) optimal matchning i ett bipartitdiagram. I vår modell finns n "spelare" och m "poster". Varje spelare vet inledningsvis en delmängd av de objekt som det kan matchas (dvs.. m bitar av information). Spelarna kommunicerar i rundor: i varje omgång skriver varje spelare ett meddelande på en delad svart tavla. Meddelandet kan bara bero på vad spelaren vet i det skedet: hans initiala input och alla meddelanden från alla andra spelare som skrevs på svarta tavlan i tidigare rundor. Detta problem introducerades nyligen av [DNO14] som ett enkelt marknadsscenario: spelarna är unit-demand 1 budgivare och vårt mål är att hitta en (ungefär) välfärdsmaximering av objekten till spelarna. Den klassiska auktionen av [DGS86] -som kan ses som en enkel Walrasian-liknande marknadsprocess för denna inställning - kan genomföras för att hitta en ungefär optimal tilldelning där varje spelare behöver bara skicka O(log n) bitar av kommunikation (i genomsnitt). Den fråga som [DNO14] övervägde var om en så låg kommunikationsbörda räcker utan att använda flera interaktionsrundor. Som en lägre gräns bevisade de att ett icke-interaktivt protokoll, dvs. en som använder en enda omgång kommunikation, inte kan få en n 1/2-faktor approximation (för alla fasta > 0) med n o(1) bitar av kommunikation per spelare. Som övre gränser ställde de ut (I) ett O(log n)-runda protokoll, där varje spelare skickar O(log n) bitar per runda, som får en 1 1−ε -faktor approximation (för alla fasta δ > 0) och (II) för varje fast r ≥ 1, ett r-round protokoll, där varje spelare skickar O(log n) bitar per runda, som får en O(n 1/(r+1) )- tillnärmning. 2 Förutom det faktum att den nedre gränsen i [GO13] endast gäller för att testa exakta matchningar och inte ungefärliga matchningar, består deras modell av ett litet antal parter (konstant eller logaritmiskt i n) som kommunicerar i ett visst fast antal sekventiella rundor (inte samtidigt). Ingången själv av varje spelare är därför super-linjär i antalet noder av ingångsgrafen (n), och faktiskt de visar en super-linjär kommunikation lägre gräns, vilket är klart omöjligt i vår modell. [GO13] modellen motiverades av strömmande lägre gränser och verkar inte fånga det ekonomiska scenario som vi försöker modellera i detta dokument (dvs. privat-värderingar) och därför är detta resultat ojämförligt för vårt, vilket också framgår av de distinkta bevis-tekniker. 3 Där grafkanterna är fördelade bland endast två spelare. kan trivialt uppnås av en av de två spelarna). Visst, eftersom tvåpartimodellen är starkare, är inga bättre nedre gränser kända. Det finns många öppna problem relaterade till vårt arbete. Låt oss nämna några av de mest naturliga. Vårt första öppna problem är att stänga gapet mellan vår nedre gräns och den övre gränsen: Vi visar att r =  och (log log n) rundor av kommunikation krävs för att uppnå konstant approximation förhållande med hjälp av poly-logaritmiska bitar per spelare, medan den övre gränsen är r = O (log n). Vi anser att den övre gränsen faktiskt är snäv, och att förbättra den nedre gränsen lämnas som vårt första och direkta öppna problem. En annan intressant riktning är att försöka utöka vår lägre bundna teknik för att få liknande-in-and avkopplingar för den mer allmänna installationen av combinatorial auktioner, också studeras av [DNO14]. Från ett kommunikationskomplex perspektiv, lägre gränser i denna uppsättning är mer övertygande, eftersom spelarvärderingar kräver exponentiellt många bitar att koda, därför interaktion har potential att minska den övergripande kommunikationen (krävs för att få effektiva tilldelningar) från exponentiellt till polynom. Det visas faktiskt i [DNO14] att när det gäller sub-additiva budgivare finns det ett r-round randomiserade protokoll som får en Õ(r ·m 1/(r+1) )-uppskattning till optimal social välfärd, där i varje runda varje spelare skickar poly(m, n) bitar. Återigen gavs en (exponentiell i m) lägre gräns på kommunikationen endast för samtidiga protokoll (r = 1) och den naturliga frågan är att utvidga den till flera rundor också. Ett mer allmänt öppet problem som förespråkas av [DNO14] är att analysera kommunikations komplexiteten att hitta en exakt optimal matchning. Man kan naturligtvis anta att n  på(1) omgångar av interaktion krävs för detta om varje spelare bara skickar n o(1) bitar i varje omgång, men ingen super-logaritmisk gräns är känd. Problemets kommunikationskomplexitet utan någon begränsning av antalet rundor är också öppen: ingen signifikant superlinjär (n log n), nedre gräns är känd, medan den bästa övre gräns som är känd är Õ(n 3/2 ).
I ett uppföljningsarbete, Alon et al. REF erhöll den första icke-triviala nedre gränsen för antalet rundor för allmänna randomiserade protokoll.
Welfare Maximization with Limited Interaction
{'venue': '2015 IEEE 56th Annual Symposium on Foundations of Computer Science', 'journal': '2015 IEEE 56th Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}