I det här dokumentet studerar vi protokoll om lösning av tvister ur ett spelteoretiskt perspektiv. Vi fokuserar på erkännande-baserade protokoll, där en användare får feedback från kanalen endast när hon försöker överföra. I detta fall kommer hon att få reda på om hennes sändning var framgångsrik eller inte. Användare som inte skickar kommer inte att få någon feedback. Vi är intresserade av balansprotokoll, där ingen spelare har ett incitament att avvika. Den begränsade återkopplingen gör utformningen av jämviktsprotokollen till en svår uppgift eftersom bästa responspolicy vanligtvis måste modelleras som delvis observerbara Markovbeslutsprocesser, som är svåra att analysera. Vi visar dock hur vi kan kringgå detta för två aktörer och lägga fram ett jämviktsprotokoll. För många spelare ger vi omöjliga resultat för en stor klass av erkännande-baserade protokoll, nämligen åldersbaserade och backoff protokoll med ändlig förväntad avslutningstid. Slutligen ger vi en åldersbaserad jämvikt protokoll, som har oändlig förväntad sluttid, men varje spelare slutar i linjär tid med hög sannolikhet. Nyckelord och fraser innehållsupplösning, erkännande-baserade protokoll, spelteori Contention upplösning i flera åtkomstkanaler är ett av de mest grundläggande problemen i nätverk. I en flergångskanal (eller sändningskanal) vill flera användare kommunicera med varandra genom att skicka meddelanden till kanalen. Kanalen styrs inte centralt, så att två eller flera användare kan överföra sina meddelanden samtidigt. Om detta händer så kolliderar meddelandena och sändningen misslyckas. Protokoll för innehållsupplösning anger hur sådana konflikter ska lösas, samtidigt som vissa prestandamått optimeras, som kanalanvändning eller genomsnittligt dataflöde. I detta dokument följer vi standard antagandet att tiden är uppdelad i diskreta tider, meddelanden delas upp i fasta storlek paket, och ett paket passar exakt in i en tid slits. Dessutom anser vi att ett av de enklaste möjliga scenarierna där det finns n användare, var och en av dem har ett enda paket som måste överföras via kanalen. När exakt en användare försöker överföra i en given slot, är överföringen framgångsrik. Men om fler än en användare försöker överföra i samma spår, en kollision inträffar, deras överföring misslyckas och de behöver för att åter överföra sina paket i senare tider slots. Under centraliserad kontroll av användarna, undvika kollisioner skulle vara enkel: exakt en användare skulle överföra vid varje tidpunkt steg, växlande på ett round-robin-sätt. Problemets komplexitet beror på att det inte finns någon centraliserad kontroll och därför måste kanalåtkomst hanteras genom ett distribuerat protokoll. Det finns en stor samling av litteratur som
Bland andra resultat tillhandahåller REF det unika FIN-EQ-protokollet för två spelare och en deadline IN-EQ-protokollet för minst tre spelare.
Strategic Contention Resolution with Limited Feedback
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}