Abstract-I samband med multiplayer spel, kan parallellrepetition problem formuleras enligt följande: med ett spel G med optimal vinst sannolikhet 1 − α och dess upprepade version G n (där n spel spelas tillsammans, parallellt), kan spelarna använda strategier som är betydligt bättre än de där varje spel spelas självständigt? Denna fråga är relevant inom fysiken för studier av korrelationer och spelar en viktig roll inom datavetenskapen i samband med komplexitet och kryptografi. I detta dokument beaktas flerspelarspel utan teckenspel, dvs. den enda begränsningen för spelarna är att de inte får kommunicera under spelet. För kompletta supportspel (spel där alla möjliga kombinationer av frågor har icke-noll sannolikhet att ställas) med ett antal spelare, visar vi ett tröskelvärde teorem som anger att sannolikheten att icke-signalerande spelare vinner mer än ett bråk 1-α +β av n-spel är exponentiellt liten i nβ 2 för varje 0 ≤ β ≤ α. För spel med ofullständigt stöd, vi härleder ett liknande uttalande för en något modifierad form av upprepning. Resultatet är bevisat med hjälp av en ny teknik baserad på en nyligen de Finetti teorem, vilket gör att vi kan undvika centrala tekniska svårigheter som uppstår i standardbevis för parallella repetition teorem.
Arnon-Friedman, etc. bevisa liknande resultat för flera spelare icke-signaling spel, men de använder en ny teknik som kallas de Finetti minskningar REF.
Non-Signaling Parallel Repetition Using de Finetti Reductions
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Mathematics', 'Physics', 'Computer Science']}