A 3-player protocol preventing persistence in strategic contention with limited feedback

Spirakis, PG ORCID: 0000-0001-5396-3749, Christodoulou, G, Gairing, M, Nikoletseas, S and Raptopoulos, C (2017) A 3-player protocol preventing persistence in strategic contention with limited feedback. In: 10th International Symposium on Algorithmic Game Theory (SAGT 2017), 2017-9-12 - 2017-9-14, L'Acquilla Iatly.

Text SAGTversion_20170505.pdf - Author Accepted Manuscript Download (354kB)

Abstract

In this paper, we study contention resolution protocols from a game-theoretic perspective. In a recent work, we considered acknowledgment-based protocols, where a user gets feedback from the channel only when she attempts transmission. In this case she will learn whether her transmission was successful or not. One of the main results of ESA2016 was that no acknowledgment-based protocol can be in equilibrium. In fact, it seems that many natural acknowledgment-based protocols fail to prevent users from unilaterally switching to persistent protocols that always transmit with probability 1. It is therefore natural to ask how powerful a protocol must be so that it can beat persistent deviators. In this paper we consider age-based protocols, which can be described by a sequence of probabilities of transmitting in each time step. Those probabilities are given beforehand and do not change based on the transmission history. We present a 3-player age-based protocol that can prevent users from unilaterally deviating to a persistent protocol in order to decrease their expected transmission time. It is worth noting that the answer to this question does not follow from the results and proof ideas of ESA2016. Our protocol is non-trivial, in the sense that, when all players use it, finite expected transmission time is guaranteed. In fact, we show that this protocol is preferable to any deadline protocol in which, after some fixed time, attempt transmission with probability 1 in every subsequent step. An advantage of our protocol is that it is very simple to describe, and users only need a counter to keep track of time. Whether there exist $n$-player age-based protocols that do not use counters and can prevent persistence is left as an open problem for future research.

Item Type:	Conference or Workshop Item (Unspecified)
Additional Information:	arXiv admin note: substantial text overlap with arXiv:1606.06580
Uncontrolled Keywords:	Contention resolution, Age-based protocol, Persistent deviator, Game theory
Depositing User:	Symplectic Admin
Date Deposited:	29 Jun 2017 08:35
Last Modified:	19 Jan 2023 07:02
DOI:	10.1007/978-3-319-66700-3_19
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3008128