En firad 1976 teorem av Aumann hävdar att Bayesian agenter med gemensamma tidigare kan aldrig "ense att vara oense": om deras åsikter om något ämne är allmänt känt, då dessa åsikter måste vara lika. Men två viktiga frågor gick obesvarade: för det första, kan agenterna nå en överenskommelse efter ett samtal av rimlig längd? För det andra: Kan de beräkningar som behövs för det samtalet utföras på ett effektivt sätt? Detta dokument besvarar båda frågorna jakande och stärker därmed Aumanns ursprungliga slutsats. Vi visar att för två agenter med en gemensam innan att komma överens inom ε om förväntningarna på en [0, 1] variabel med hög sannolikhet över sin tidigare, räcker det för dem att byta O 1/ε 2 ¡ bitar. Denna gräns är helt oberoende av antalet bitar n relevant kunskap som agenterna har. Vi utvidgar också de bundna till tre eller fler agenter; och vi ger ett exempel där "standardprotokollet" (som består av att upprepade gånger tillkännage ens nuvarande förväntningar) nästan mättar gränsen, medan ett nytt "uppmärksammat protokoll" gör bättre ifrån sig. Slutligen ger vi ett protokoll som skulle få två Bayesians att enas inom ε efter utbyte av O 1/ε 2 ¡ meddelanden, och som kan simuleras av agenter med begränsade beräkningsresurser. Med detta menar vi att, efter att ha undersökt agenternas kunskap och en utskrift av deras samtal, ingen skulle kunna skilja agenterna från perfekta Bayesians. Den tid som simuleringsförfarandet använder är exponentiell i 1/ε 6 men inte i n.
Beräkningsresultatet av REF avser ett protokoll där de två agenterna fortsätter att utbyta sina baksidor i Bayesien med en avsiktligt tillagd bullerterm.
The complexity of agreement
{'venue': "STOC '05", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}