Combinatorial Group Testing with Selfish Agents
Authors: Giorgos Chionas
Dariusz Rafal Kowalski
Piotr Krysta
Venue: NeurIPS 2023 poster (2023)
Keywords: Combinatorial Group Testing
Adversarial Equilibrium
Contention Resolution
selfish agents
learning time
adaptive learning algorithms

Abstract: We study the Combinatorial Group Testing (CGT) problem in a novel game-theoretic framework, with a solution concept of Adversarial Equilibrium (AE). In this new framework, we have $n$ selfish agents corresponding to the elements of the universe $[n] =\{0,1,\ldots,n-1\}$ and a hidden set $K \subseteq [n]$ of active agents of size $|K| = k \ll n$. In each round of the game, each active agent decides if it is present in a query $Q \subseteq [n]$, and all agents receive feedback on $Q \cap K$. The goal of each active agent is to assure that its id could be learned from the feedback as early as possible. 

We present a comprehensive set of results in this new game, where we design and analyze adaptive algorithmic strategies of agents which are AE's. In particular, if $k$ is known to the agents, then we design adaptive AE strategies with provably near optimal learning time of $O(k \log(n/k))$. In the case of unknown $k$, we design an adaptive AE strategies with learning time of order $n^k$, and we prove a lower bound of $\Omega(n)$ on the learning time of any such algorithmic strategies. This shows a strong separations between the two models of known and unknown $k$, as well as between the classic CGT, i.e., without selfish agents, and our game theoretic CGT model.

Combinatorial Group Testing with Selfish Agents
Georgios Chionas
Dariusz R. Kowalski
Piotr Krysta'
Department of Computer Science University of Liverpool Liverpool, United Kingdom g chionas@liverpool.
School of Computer and Cyber Sciences
Augusta University Augusta, Georgia, USA
{dkowalski pirooallskkk.yyyyaaa//aggstttt.. edu
Abstract
We study the Combinatorial Group Testing (CGT) problem in a novel game- theoretic framework, with a solution concept of Adversarial Equilibrium (AE). In this new framework, we have n selfish autonomous agents, corresponding to the elements of the universe [n] {O,1.....
1}, and a hidden set K S [n] of active agents of size |K] = k << n. In each round of the game, each active agent decides if it is present
query Q S [n]. and all agents receive some limited feedback on Q n K. The goal of each active agent is to ensure that its id could be revealed from the feedback as early as possible.
We present comprehensive set results for this new game, where we design and analyze adaptive algorithmic strategies of agents which AE's. In particular, if k is known to the agents, then we show adaptive AE strategies with provably near-optimal maximum revealing time of O(k (og(n)))). In the case of unknown k, we design adaptive AE strategies with maximum revealing time of order ==11, and we prove a lower bound (2n)) on the maximum revealing time any such algorithmic strategies. This shows strong separations between the two models of known and unknown k. as well as between the classic CGT, i.e., without selfish agents, and game theoretic CGT model.
Introduction
Combinatorial Group Testing (CGT) is a classic area of learning theory, see the book Du et al. [2000]. It is about revealing elements from hidden set of size k. typically much smaller than the size the universe of all elements, by asking queries and receiving answers (feedback). Queries subsets of universe, while feedback is fixed function that provides some limited information about the intersection of the query with the hidden set, e.g., how big is the size of the intersection. CGT was introduced by Dorfman [1943] in the context of revealing infected individuals in large populations using pooled tests, and has been intensively explored recently during the COVID-19 19 pandemic, c.f., Augenblick et al. [2020], Mallapaty et al. [2020]. Linnott-Amsstree et al. [2020]. CGT has growing applications to Machine Learning, c.f.: simplifying multi-label classifiers Ubaru et al. [2020], approximating the nearest neighbor Engels et al. [2021], and accelerating forward pass of deep neural network Liang and Zou [2021]. CGT also used in data mining and stream processing, c.f.: extracting the most frequent elements Cormode et al. [2003], Cormode and Muthukrishnan [2005], Cormode and Hadjieleftheriou [2008], Yu et al. [2004], Kowalski and Pajak [2022b), quantile tracking Cormode et al. [2005], Gilbert et al. [2002b]. Greenwald and Khanna [2001]. or approximate histogram maintenance and reconstruction Gibbons al. [2002], Gilbert et al. [2002a]. Other areas include coding and network communication, c.f.: Kautz and Singleton [1964]. Clementi et al. [2001]. Porat and Rothschild [2011], 1]. The adversarial aspects of CGT were also considered, c.f., Klonowski et al. [2022], Kowalski and Pajak [2022a].
typically
Piotr Krysta also affiliated with Computer Science Department, University Liverpool, U.K.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

We study the Combinatorial Group Testing (CGT) problems in a novel game theoretic framework with solution concept which an Adversarial Equilibrium (AE). In this enhanced model, elements are autonomous selfish players, also called agents, while those with id in the hidden set are active. Ideally, the active agents should follow a CGT algorithm to have them revealed after some number of queries have been answered. 2 We study efficient deterministic CGT algorithms which are also AE that is, which additionally incentivise the active agents to follow the CGT algorithm without any deviations. In particular, they are designed in such a way that an agent could worsen its revealing time it decides to include/exclude itself from the query created by the CGT algorithm (see Section 2.1 for detailed definition of AE). We also show substantial limitations on scalability of the maximum revealing time when the number & of active agents is unknown.
Closest related work and their relevance. The concept of deterministic Adversarial Equilibrium (AE), used in our work, was introduced in the context of non-adaptive contention resolution (CR) games by Chionas et al. [2023]. CR is a communication problem in which each player has a packet to transmit successfully (i.e., alone) in a given time unit on the multiple-access channel to which it is connected, together with other agents. It was introduced in the context of resolving conflicts in Local Area Networks (LANN), co-funded by the recent Turing Award winner Robert Metcalfe, c.f., Metcalfe and Boggs [1976]. Initially it was assumed that agents would respect the
given algorithm. Greenberg and Winograd [1985] proved a lower bound S
(logg(n)
[Tg(k)) on the running
time of any adaptive deterministic CR algorithm with restricted feedback with collision detection. Capetanakis [1979a.b] and Hayes [1978] independently found an adaptive, deterministic binary tree algorithm to solve the CR problem, which runs in O(k A log(n/k)) time.
CR could be interpreted as a CGT-type problem with some subtle differences. The main conceptual similarity between CR and CGT is the environment agents decide to transmit in CR (equivalently, be included in the query in the CGT) or not and they receive feedback from the channel (equivalently, broker of the CGT process the feedback function). The main, though subtle, difference is that in CR is required that every active agent needs to eventually be a singleton intersection with some query (i.e., to transmit successfully on the channel, without interference from other active agent), while this is not required in the CGT - the CGT, the set of active agents could be revealed based on analyzing the feedback, even if some agents are not in singleton intersections with any queries.
Fiat et al. [2007] initiated the work on CR algorithms in which agents seek to minimize their individual latency costs. They designed randomized algorithms that are Nash equilibria with bounded latency. Later, Christodoulou et al. [2014] studied CR games where the cost of each agent depends on the number of attempted transmissions before success. As mentioned earlier, Chionas et al. [2023] were the first who introduced deterministic game theoretic framework to CR. In particular, they showed non-adaptive adversarial equilibria of well-scalable Ollog n.) latency (i.e., revealing time), but only for k = 2, 3 active agents. In contrast, we study more general adaptive algorithms (which correspond to much richer space of strategies), provide wider framework for the analysis of adversarial equilibrium for general field of CGT with any feedback function, and design well-scalable equilibria for any size le of the hidden set.
Bolouki et al. [2017] studied a Bayesian game where the population is partitioned in two sets, i.c.. healthy and infected individuals. The goal of the former set is to have the infected individuals revealed as soon as possible, while the goal of the latter set not to get revealed for as long as possible. The only strategy of individuals is to comply or not when they are called for test. Our setting is quite different in the following aspect. We consider a richer space of strategies, since the agents may choose to comply with the query or to deviate by either including themselves in query without being called for, or not including themselves in a query while being called for.
Technical contributions. Apart from our conceptual contribution of designing an adversarial equilibrium model for general (i.e., adaptive) CGT (see Section 2.1), we demonstrate its difference compared to the classical CGT (and related settings, such as CR) by providing several new techniques and performance bounds, c.f., Table 1. The main conceptual difference between the classical and our CGT setting is that while we preserve all features of the classical model, in addition we augment it
Depending on the feedback function, revealing of a hidden agent/element could be direct, when the id of this element is returned in the feedback. or indirect, when the analysis of the feedback for the previous queries ensures that the agent must be in the hidden set.
2

---

(n, ..G
(n, CG- and (n, K)EA
Class
Lower Bound
Upper Bound
Lower Bound
Upper Bound
known l
(lg((z) 52
log(k)
Okklog(n/H))) i
Ω
klog(n) log(k)
*
Okklog(n/k) Thm. 3.1
unknown
.2
(o)(
log(R)
*
O ((klo((n/))) f
(n)) Thm. 4.1
O( Thm. 4.2
Table 1: Summary of our main results. Asymptotic notations O, Q denote an upper/lower estimate wrt constant factor. All logarithms are to base 2, unless stated otherwise. Results marked * and t were published Greenberg and Winograd [1985] and in Capetanakis [1979a.b], Hayes [1978], resp.
with the game theoretic aspect. This adds new technical challenges in designing efficient algorithms in this new setting. In the main part, we focus on popular feedback function with collisions, and design two algorithms with two very different revealing mechanisms that are also adversarial equilibria. The first algorithm (see Section 3) assumes knowledge of the number of active agents & and reveals agents' ids one by one, using appropriate shortcuts in the binary search process. The second algorithm (see Section 4.2), designed for unknown k. reveals all the active players during the first successful query, by gradually decreasing the size of subsequent queries.
The maximum revealing time of the first algorithm is Ol ([klog(2n/k)) for any 2 < k < n. This
is very close to the best possible maximum revealing time, due to the lower bound S2
[ [ogg(()
log
by Greenberg and Winograd [1985] for any adaptive deterministic solution in the considered CGT setting. In contrast, Chionas et al. [2023] designed scalable non-adaptive algorithms only for l: = 2, 3. Moreover, proving AE for general adaptive CGT algorithms, done in this work, is more challenging than proving it for non-adaptive solutions, as the space of all adaptive algorithms is much bigger and complex than the space of pre-defined sequences of queries, i.e., non-adaptive algorithms.
The existence of such algorithms allows to consider the price of stability, c.f., Nisan et al. [2007], Maschler et al. [2020], in CGT games with respect to adversarial equilibria in adaptive strategies. Our equilibria with deterministic adaptive strategies imply an upper bound of Olog k) on the price of stability (PoS).² This upper bound on PoS follows by dividing our bound O
on
the maximum revealing time by the lower bound ? llg(n) of Greenberg and Winograd [1985].
To compare, Chionas et al. [2023] designed adversarial equilibria in less complex deterministic non-adaptive strategies in the CR game (related to our setting), achieving constant PoS only for = 3 and the PoS of only θik Iog(nK]] for any k >
All the abovementioned results and comparisons assume known In case of unknown k; we formally show that this setting is more difficult than the one with known & by proving lower bound ((n) on the maximum revealing time even if an upper bound k' 2 3 on is known (see Section 4.1). We also designed universal AE algorithm for any unknown k mentioned earlier, which has polynomial revealing time if the actual number of active agents is constant in n (see Section 4.2).
Extensions and applications. We analyzed several extensions and applications of the new framework, showing its generality. We applied it to other feedback functions: ones that instead returning an id of singleton intersection return "beep" (i.e., a single bit indicating that the intersection is singleton), and others which return "null" in case of non-singleton intersection of the query with the hidden set. Direct applications include adaptive equilibria contention resolution algorithms and new mechanisms for blockchain. Due to the page limit, all details, proofs and extensions and applications deferred to the Supplementary Materials, in the form of the full version of our paper.
2 The Model, the Problem and the Preliminaries
In Combinatorial Group Testing (CGT) types of problems, we are given a universe [n]] {0, 1. In 1} of clements and a hidden subset K [n]] of size |K] = k. where 2 < k S n.*
'PoS is ratio between the cost of the best-case equilibrium and the cost of socially optimal outcome. our case, the cost is the maximum revealing time. "Typically CGT assumes that & & that is, the hidden set is much smaller than the size of the universe, n.
3

---

Later, when introducing game theoretic framework for CGT, we will also be referring to the hidden subset K as configuration of the game. Let F be the set of all k-element subsets of [n], i... the family of all possible hidden sets. The goal of an algorithm is to learn the set K using the smallest number of queries. query Q S [n] returns a value of some function, called Feedback( n K). We consider a classical feedback defined in the following way:
if K| = 0, then Feedback (Q = 0 ("empty");
if K| 1, then Feedback K) = i, where {i} - Qn) K (element "selected");
+f 2 2, then Feedback( n K) =T ("clash" or "collision" or "2+").
This feedback function one of the simplest considered in CGT, known in the literature as a ternary feedback or (2, log n) f1)-edbbbckk in the generalized CGT terminology, cf. Klonowski et al. [2022]. If the query has a singleton intersection with the hidden set, then naturally the feedback reveals the respective agent's ss ID. If the intersection is empty has size at least 2 (clash), then the feedback is empty or clash, respectively. We also study different feedback functions in extensions, included in the Supplementary Materials due to the page limit.
(deterministic) algorithm for the CGT problem is an adaptive algorithm which, based on the history of the computation, generates subsequent queries Qt. which are asked by the algorithm in the order specified by index L, for 1 = 1.2,3.... Each query Q, may depend on the feedback Feedback (Q (().......... ...... Fredback(Q:-.. n from the previous queries Q1, Q2...., ...,.111 generated by the algorithm, where K the hidden set on which the algorithm is executed. We will refer the index t as time, step or round of the algorithm. Note that the first query Q1 is hardwired since the feedback history before round 1 is fixed (empty).
Feedback histories. Suppose that a given algorithm for a given hidden set K, generates a sequence of queries Q1, Q2,Q2.-a Qs when the algorithm executed on K by a round The corresponding unique sequence of feedbacks received in such execution, ø o[1.t] = Feedback((u n K), Feedback Q2 N K)..... Feedback Q2 n K). called a feedback history (of the algorithm on set K, we know the algorithm and K) by round 1.5 Note that for a given feedback history there is a unique sequence of queries that resulted in such feedback history - -his is because we consider deterministic algorithms. We have {14 E {0. 3 U [m]. for round L. E {1, 3, ..... and @|1.. E ((0, 1) U (ni))* ( (when i is irrelevant, we simply write o, where o E (10. 13 U [nl))) ) Although the algorithm is not given set K as an input, for each round it knows the feedback history. We call a given sequence of queries, or feedbacks, a valid query sequencelfeeddack history iff they are query scquence/feedback history obtained in an execution of the algorithm on some hidden set K E FA
Compatibility. For a given algorithm, we say that a set K E F& is compatible with a given feedback history, if the execution of the algorithm on the hidden set K generates that feedback history. For a given feedback history Φ, let K.g. C F be the family of all sets K compatible with é, and let Koh = (K K. E K).
Definition 1 (Revealing time). Suppose we are given an algorithm, a hidden set K E n and an element i E K. Let de be the feedback history of the algorithum run on the hidden set K for t rounds. The smallest such that all sets K' E Fhi compatible with oe contain element is called the revealing time of element on the hidden set K.
Note that, in our feedback model above, the revealing time / of agent could sometimes result from explicit feedback in round t, i.c., Feedback Q2 n K) = i, but in other cases could be deducted implicitly by ruling out non-compatible configurations that do not contain i (c.f., Definition 1).
We say that an algorithm solves the CGT problem, or is an (n, k)T if for any hidden set K E FA the revealing time of any element i E K is finite. The maximum of the revealing time, over all hidden sets K E F% and E K, is called the maximum revealing time of the (n, -GGT algorithm. A performance measure of secondary interest is the maximum completion time, which is the maximum, over all hidden sets K E Fk, of the minimum round when empty queries follow. 6
$ "plt....., t. denotes sub- sequence of o consisting of values of sequence in positions tt.... 'Clearly, an (n, k)-CGT algorithm has to reveal all elements in the hidden set before stopping to generate non-empty queries (feedback to which does not bring any information): therefore, the maximum completion time is not earlier than the maximum revealing time.

---

2.1 Game-theoretic framework for CGT
We now define the game theoretic setting of the CGT problem. The set of available selfish players, also called agents, coincides with the elements of the universe [n]. The hidden set K C [nx] is the set of active agents chosen among available agents, who participate in the given instance of the game. As mentioned earlier, also refer to the hidden set K configuration of the game. Initially an adversary chooses a configuration K E Fi and informs every agent of their status with respect to the configuration, i.e., each active agent knows about the fact that it is in set K, but does not know ids of the other active agents in K.
Each agent then executes the same deterministic algorithm, called strategy, determined by the parameter n (and k, if given) and the feedback history. Actions of an agent will also be determined by its unique id. We will usually denote the algorithm as collection of deterministic algorithms (strategies) (s0, 81, 8n-1), one for each of the n agents. In each round, the strategy determines
the agent, say i, is in the current query in a round & or not, i.e., s;[t] = 1 or [4] = O, respectively. After each agent decides whether it is present in the query or not, the outcome of the feedback function is computed centrally, based on the combined agents' decisions and communicated all the agents.? ?
Given an algorithm, the goal of each active agent E K' is to minimize the revealing time of i. Therefore, the payoff or utility of agent E is strictly decreasing function of i's revealing time. In order to improve its payoff, an agent i E K may want to deviate from the algorithm at some rounds t, in which the corresponding query Q: generated by the algorithm could be modified by i by either:
including itself in the query Q:i the original query, where i & Qs. is modified to Q2 Qt U {i}: or
excluding itself from the query Qi: the original query, where E Qt. is modified to Q = Qi {i}.
The agents following the algorithm are not informed about the deviation of the other agent, although could deduct some information later on, based on the received feedback the feedback is given for the modified query, i.e., ø1{] = Feedback(Q) O K) for the game configuration K.
Adversarial equilibria. The following notion of an adversarial equilibrium has been introduced by Chionas et al. [2023] in the context of related but more restricted non adaptive contention resolution games. We extend this definition to the CGT game. A collection of deterministic algorithms (strategy profile) $1......... 8n-1), one for each of the n agent, solving the CGT problem, is called an (n. -adavvrrraai equilibrium,
(n, k)-AE, iff for any agent E [ri] and any change of its strategy (a.k.a. a deviation) from 8; to some other strategy 8 * 8, (while all other agents j * i follow their strategies 8,), if there is configuration K of h agents for which the change strictly decreases the revealing time of agent i, then there is a configuration K" of k agent for which this change strictly increases the revealing time of agent K (K', resp.) is called an improving (worsening, resp.) configuration for agent i under deviation s/. We also call strategies (sn, , k)AA) for any k 2,3....,
87-1) n n-AE if it is
Essentially, the notion of adversarial equilibrium is similar to the notion of individual Pareto optimality. This means that, for strategy profile that is adversarial equilibrium, for each agent there does not exist an action (deviation) that improves its payoff in one configuration (compared to its respective payoff before deviation) without worsening in another configuration (again compared to its respective payoff before the deviation). We refer the reader for a further discussion about this definition to Chionas et al. [2023] and to the Supplementary Materials.
Universal A Adversarial Equilibria (with unknown k). An algorithm is universal (n, )')-AE if the algorithm is (n, k)-AE for every l S k.. An algorithm which is universal (n, ni)AEE, is also called universal n-AF.
"Note that, since the algorithm is deterministic, all agents could compute the strategies of other agents- however, due to initially unknown configuration (and, thus, ambiguity) and potential deviations (see the next paragraph), such strategies" computation may not often help the agent to predict the actual feedback (which could help improve the revealing time by deviation, see again the next paragraph for details).
5

---

2.2 Preliminaries
Grim-trigger strategies. Similarly to the other related models and papers Fiat et al. [2007], Chionas et al. [2023], we will also use the following Grim-Trie Trigger (GT) mechanisms in agents' strategies. When the algorithm, run by an agent (who not deviating), discovers certain state that may suggest deviation of other agents, it (repeatedly) includes itself in subsequent queries for long period. This is done to discourage agents from creating deviations to the CGT algorithm. We will call such behavior persistent inclusions (of the agent). Strategies with the GT mechanism are called Grin-Trigger strategies. The notion of Grim-trigger strategies were also used in similar context repeated games, see [Axelrod and Hamilton, 1981, Nisan et al., 2007, Sec. 27.2]. It plays the role of punishment mechanism, which is necessary for the existence of equilibria.
Search trees and (ambiguous) queries. For the purpose of designing algorithms which are AE's, we will study binary trees whose leaves are uniquely labeled with elements of the universe [n] and the internal nodes correspond to queries that could be generated by a search algorithm. More specifically, for such given binary tree and its vertex v; a query Q. contains all leaves in the subtree rooted at v. Let e be given feedback history. We say that a query Qu is ø-ambiguous iff there are at least two different configurations K1, K₂ E FK compatible with e such that Feedback Q,,nK * Feedback (redback(Q..nh (gg We could omit parameter & whenever it is clear from the context. If the query Qu associated with vertex e is ambiguous, we also call vertex e ambiguous - all this with respect to some family of configurations A.
Eulerian tour. For a given binary tree, we will be often referring to a left-to-right Eulerian tour along the tree (or an Eulerian tour, for short). This is a standard procedure that lists vertices of the tree in the left-to-right recursive order, that is. lists the root, then recursively vertices in the left sub-tree, followed by recursive enlisting of vertices in the right sub-tree.
2.3 Binary tree search algorithms
Tree algorithms have been extensively studied to solve the combinatorial group testing and contention resolution problems. These algorithms can be thought of as a short version of an Eulerian tour on the (complete) binary tree in which the leaves correspond 1-1 to the elements and stations in the literature of CGT and contention resolution, respectively, or agents in our game theoretic framework. As warm-up, we study the algorithm proposed by Capetanakis [1979a] and we shall call it Binary Search, or BS for short. This algorithm is based on a simple divide and conquer techmique. Firstly, as said, consider that the total number of agents correspond 1-1 n leaves of (complete) binary tree. Let Qu denote the agents that correspond to the leaves of the subtree with root v. We shall call e verter with token, or a token for short (we will formalize the appropriate notation in Section where we analyze our more sophisticated algorithm). At each time f, agents Qu form the query, and afterwards changes its location depending on the feedback Φ. Initially. v the root of the tree and changes its position as follows. At each round t if Qu results in no collision, i.c., ølt] E {0) U (i}. where i E K, then token moves to the next-right subtree where collisions are not yet resolved. If Q results in a collision, then token e moves to the left subtree in order to resolve the collision. Essentially, the algorithm BS traverses the lefi-to-right Eulerian tour of the binary tree by doing some shortcuts. In order to understand the shortcuts of the token in the algorithm BS compared to the Eulerian tour see Figure I(a). Note that if k = n, the tour of the token is exactly the Eulerian tour of the binary tree.
BS runs in O(k log(n/k)) time. This algorithm was proposed in the classical setting of contention resolution without deviations. It is easy to see that BS is (n, k)T but it is not a (n, AAE-EE We modify BS by adding the grim trigger strategies as follows. If agent is not revealed as long as token is the root of a subtree that it belongs to, it will start including itself in the queries persistently in every following round (we may also set up a cap, say, to these persistent inclusions in the next 4n rounds, just to make sure that it is longer than the search algorithm's 's maximum revealing time without deviation). Let us call this algorithm Grim Trigger Binary Search or GT_BS for short. Even with this modification BS is not an (n, AE-
Lemma 1. _T_BSI
BS is not an (n, A)-
In the example in Figure ((a), in the given configuration, agent 7 could deviate by including itself in the query after the second active agent is selected (i.e., the feedback is equal to the id of this agent). It improves its revealing time compared to the one by following BS. By following this simple strategy,

---

W1
W1
W/2
103
102
WU3
W4
W6
WG
W4
W6
WG
2
5
2
5
(a) BS tour the token is (wh, Wa, Wa, W6; W7, 6, 7)
(b) BS_ Jumps tour of token, with the appropriate shortcuts, is (w2, ws, 6, 7)
Figure 1: Here, π 8, are present in the queries with the following sequence according to the token and feedback: 0, (4, 6, 6, +1, (4.5)
3, and active agents are K 60,6,7 7}. (a): In BS agents
{0. 1, 5, 6, 7} --1, 1, 1, 2.3)
0. (6,7) -Te (6}
6, (7) + 7. Note that the tour of the token was ((w1), W2. W3, W6, W7, 6, 7), whereas the Eule- rian tour is (w1, W2 W/, 0, 1, Ws, W3, W6, 4, 5, W7, 6, 7). (b): Illustration of Bumps.
the agent will either be better off or will have the same revealing time compared to BS. This leads us to the following important observation that will help us construct our next algorithm (in Section 3): In order for an algorithm to be an (n, A--AE, active agent who has not been selected should be included the query immediately after the revealing of the (k - 1)'st active agent.
Efficient equilibrium with known size k
The algorithm, called Binary Search with Jumps (or BS_ Jumps, for short), is based on binary tree, in which leaves correspond 1-1 to agents (this correspondence is part of the input to every agent, thus it is common). More specifically, we cnumerate leaves from left to right, using consecutive numbers agent The tree is complete, if is a power
in [n] {0, 1,..., 1}. and i-th leaf corresponds of 2, or almost complete otherwise, the sense that all leaves are at the same distance from the root, if possible, their distances may differ only by 1, respectively.
Vertex with token and definition of queries. In each round, an agent maintains a distinguished vertex of the tree, called verier with token, or token for short. The query consists of ids of all leaves that are descendants
the vertex with token. Here descendant means that the token vertex located on the path from the leaf to the root, including both ends. From the perspective of an agent, it finds itself included in the query if its corresponding leaf is a descendant of the current vertex with token call it an (algorithmic) query inclusion rule.
The initial position of the token, in round 1, in the leftmost child of the root of the tree. The current (round) position of the vertex with token is computed based only on feedback history and the agent id The token update rule, described later, is based on the concept of feedback-come compatible configurations and ambiguous queries, defined in Section 2 and 2.2, respectively.
Updating token location. The location of the token is calculated the beginning of each round | as follows. Consider an execution of the algorithm by an agent i. Let (t((') be the location (vertex of the binary tree) of the token at the beginning of step t' of the considered execution, for S stored by agent i. We define [t | to be the carliest of the following two vertices on the left-to-right Eulerian tour on the binary tree starting at at 1]:
the first internal (i.e., non-leaf) vertex of the tree in that tour such that query Qo is ambiguous with respect to the set of configurations Kgl:
the first leaf that tour that is in every configuration in K.gle
Note that if the vertex defined the first bullet does not exist, it means that configurations in Kgs have the same feedback at each subsequent internal vertex of the Eulerian tour. Then, ag(t] is
7

---

Algorithm 1: BS_ (1s__uspsnnn k), pseudo-code for active agent j
e + root // Initialization of the token
K - 0 // Initialization of the revealed active agents for : = ..2....klogg. do
j E Right(v) then
| 1 Qu
else j Child(t) then
L Qu
else
if K then
L j E Qu.// Persistent inclusions if j has not yet revealed
if < = [i} then K // Agent revealed from feedback Φlt] in current
round t
0 f to,en(o,
Output K
defined in the second bullet as the first leaf j in the tour such that the corresponding agent j is in every K K-
Grin-trigger sequence. the computed token location a [t] after the leaf corresponding to agent according the Eulerian tour, and agent has not been revealed, it starts including itself persistently in the following queries.
Termination rule. The algorithm for agent finishes its algorithm execution immediately after it is revealed, if occurs before starting the grim-trigger sequence by this agent. If such revealing does not occur and the agent (eventually) starts its grim-trigger sequence, it continues transmitting until the end of the sequence and then it switches off.
The Algorithm shows how BS_ jumpa works. We use three functions:
Right(-) which takes argument the current token location and returns the set of leaves of a right subtree;
Child(-)) which takes as an argument the token location and returns the set of leaves that are descendants of the token;
which takes as arguments the current token location and the feedback history and returns the next token location according the token update rule (see the two bullets the "Updating token location" paragraph).
Efficient implementation of [BB___umm _u__usps. In this work. the main metric of consideration is the reveal- ing time (or query complexity), in which the last agent was revealed. In this paragraph, we briefly discuss other metrics of efficiency of our protocol, such the computational and communication complexity. The most cime-ccnsuming part of algorithm BS _umps the token update. Because of the structure of binary tree, identifying ambiguous internal vertices leaves that are in every ø- compatible configuration could be done fast by each agent, in each step. In short, the agent simulates locally the Hinary-Searchh
process and evaluates whether the number of "remaining" leaves is large enough compared to the number of remaining active agents (the latter could be computed from the feedback Φ). If it is. it yields ambiguity, as the number of active leaves/agents the currently considered vertex could be 0 or larger. As this local procedure is built on the top of Binary Search (simulated locally), it is efficient, in the sense that the number of local computational time in any agent is O + & log(n/k) which is O(1) amortized per round. More details of efficient implementation and analysis of correctness and efficiency are given in the Supplementary Material. Regarding the communication complexity of the protocol, it can be derived as a function of the revealing time of the protocol. each round, each active agent communicates a single bit. The output of the ternary feedback can be encoded by log n bits. Let reutime be the revealing time of the protocol. Thus, total communication complexity of protocol is (I- + log reulime bits. The total number of local steps during the protocol could be upper bounded by log revtime, because each
the subtree of

---

step/round of algorithm BS Bu_Jumps requires updating of the token, which is a logarithmic operation (see the Supplementary Materials, Section 3). Lastly, the memory needed each agent logarithmic. mainly due to the simple recursion in the main algorithm and the token update, and constant number of variables. This is under assumption that any basic arithmetic operation on variables/values, represented by logarithmic numbers of bits, could be done in a single local step, while these numbers could be stored in a unit of memory.
Theorem 3.1. Algorithm BS_ Jumps((, k) is ()-EE,,E, for any 2 S k S n, and has revealing time Ok log(2n/k))
Equilibria for unknown size k:
We first show in Section 4.1 that the restricted feedback with collision detection only universal n-AE come at high cost in performance measures. Intuitively, the high cost in that setting occurs because the adversary has even more power, since it does not only select the configuration but also the size of it and the agents are agnostic to it. We then give a universal (n,, K)-AE which is an (n, k)-CGT with maximum revealing time O(n^11), for any < k S W < n. Here, k is the actual number of active agents, unknown the agents, while K' is the known upper bound. In particular, the maximum revealing time is polynomial for constant-size configurations.
4.1 Equilibria characteristics and lower bounds
We start from proving that universal adversarial equilibria require (at least some) dense queries. Lemma 2. For any 3 S k' S n, no algoritium with first query of size different from 1 is universal (n, k') Y-A.
Intuitively. by applying Lemma 2 to the first n/2 queries (assuming that the feedback is collision), we either get impossibility some point or all these queries have be of size 1. This intuition cannot be extended much beyond the first n2/2 queries produced by an algorithm, because each query of size n somehow restricts the family of configurations of size that we could use the proof of Lemma 2.
Theorem 4.1. Any algorithm that is an (n, CCGT and universal (n, K' )-E has the maximum revealing time ((n)), any ke 2 3. Moreover, the total number of elements in the queries in some executions is Q(
4.2 Equilibrium algorithm for unknown k
We now present the algorithm called Block Builder with Grim Trigger (or BB_ 2B_GR. for short), see Algorithm 2 for a pseudo-code, The structure of algorithm BB_ (B_GR(n,,') where k' S n is the known upper bound k. consists of some x' < k'' subsequent blocks of queries. In each block of queries By, for an integer x such that S x < x', there are y/+ = (
(*) queries, while the last block, a', contains only one query. To simplify the notation for the sake of this algorithm, but with some abuse of the notation used in previous sections, here we denote the rth query of block BR as Q-. Until the first selection of an element, we define a query QF as the r-th set from the family F (where the order of these sets could be fixed arbitrarily by the algorithm). When the first successful selection happens, say for some query QF in block xx such that x² = x' 2 (or x: k' 1 in some cases when x' = kk, see the second part of the pseudo-code when the value of x has been set to k' 1), the hidden set K is revealed as
K = (eed n nk) u (In) o:²)
After the first selection, the selected agent with id Feedback(( n K") includes itself persistently in the following queries up to query Q which is the first query of the last block B executed by the algorithm in the current game. Then, the algorithm stops following the block structure and terminates.
In the analysis of BB_GR(n k') below, we show that the block number of the revealing time, x", satisfies =² k- - 1, where k is the actual size of configuration. Consequently, the number of blocks in the game execution is x' = k or x' k, where the latter occurs when k = k'' (see the second part of the algorithm's 's pseudo-code, with these two cases).

---

Algorithm 2: BB_ CR(n, K), pseudo-code for active agent j
for x ,,...,k' do
// We execute blocks Br, until first selection for r 1,2, (n-m) do
Q - r-th query F Ful (arbitrarily ordered) if Feedback((F n K) for some i E K then
K K u Q*) // Hidden set revealed break
Feedback(Q", n K) = then
for r t" + 1,,,... (===) do
// We continue in block B₂ but with grim trigger Q < [i} // Persistent inclusions
x < then
for r 1, .... (n+(++)) do
// We run one more block B with grim trigger when x
O < {i} Persistent inclusions
Q + [5} // Last persistent inclusion when x < V'
else
Qp+1 {i} // Last persistent inclusion when k
Output K
Lemma 3. BB_GR is an kGT for any < S W, with maximum revealing time O(n &
Lemma 4. BB_ is a universal (n, y'A-AE
Theorem 4.2. BB_GR is universal (n, A'E with maximum revealing time O(n for any number k of active agents, such that is < k <
Discussion and further directions
We initiated a study of combinatorial group testing algorithms that are also adversarial equilibria no agent/element has an incentive to deviate under the presence of an adversary. Our solution in case of known size & of the hidden set is almost optimal, in the sense that the price of stability is Ollog k), i.e., the ratio between our result and the absolute lower bound revealing time Ω(k log by Greenberg and Winograd [1985]. Closing this gap, and more importantly, devising efficient equilibrium for less complex feedback function is an interesting direction. negative results could be proved for deterministic solutions, then the question about efficient mixed equilibria (i.e., using randomized algorithms as strategies) would be interesting.
Another interesting question would be to try to close the gap between the bounds maximum revealing time where the number l active agents known, that O(k log n), and the bounds where & unknown, which is (=n)=1).
Other potential areas of application include: considering different feedbacks (e.g.. full quantitative) and other related problems, e.g., discovering hidden multi-sets transmissions of packets multiple-access channel without collisions. One may also consider weaker "risk averseness" in the definition of AE, and how it influences efficiency of CGT.
Finally, would be interesting to study connections of our games to repeated games, see, e.g., Osboree and Rubinstein [1994], where each agent has to transmit more than packet.
10

---

Acknowledgments and Disclosure of Funding
The work of Dariusz Kowalski was partially supported by the NSF grant 2131538. The work of Piotr Krysta has been partially supported by the Network Sciences and Technologies (NeST) initiative of the University of Liverpool.
References
Ned Augenblick, Jonathan Kolstad, Ziad Obermeyer, and Ao Wang. Group testing in a pandemic: The role of frequent testing, correlated risk, and machine learning. Technical report, National Bureau of Economic Research, 2020.
Robert Axelrod and William D. Hamilton. The evolution of cooperation. Science, 241(4489): 1390-1396, 1981.
Sadegh Bolouki, Mohammad Hossein Manshaei, Vida Ravanmehr, Angelia Nedić, and Tamer Başar, Group testing game. IFAC-PapersOnLine, 50(1):9688-9673, 2017, ISSN 2405-8963, 20th IFAC World Congress.
John I. Capetanakis. Tree algorithms for packet broadcast channels. IEEE Transactions on Information Theory, 2555):505-515, 1979a. doi: 10. 109/TTT.1999.11566999
John I. Capetanakis. Generalized tdma: The multi-accessing tree protocol. IEEE Transactions on Communications, 27(10):1476-4488 1979b.
Giorgos Chionas, Bogdan S. Chlcbus, Dariusz R. Kowalski, and Piotr Krysta. Adversarial con- tention resolution games. Proceedings of the 32nd International Joint Conference Artificial Intelligence (IJCAT), 2023.
George Christodoulou, Katrina Ligett, and Evangelia Pyrga. Contention resolution under selfishness. Algorithmica, 70(4))675-693, 2014.
Andrea E. F. Clementi, Angelo Monti, and Riccardo Silvestri. Selective families, superimposed codes, and broadcasting on unknown radio networks. In Proceedings of the Twelfth Annual Symposium Discrete Algorithms, January 7-9, 2001, Washington, DC, USA, pages 709-718. ACM/SIAM, 2001.
Graham Cormode and Marios Hadjieleftheriou. Finding frequent items in data streams. Proceedings of the VLDB Endowment, 1(2):1530-1541 2008.
Graham Cormode and Shan Muthukrishnan. What's hot and what's not: tracking most frequent items dynamically. ACM Transactions Database Systems (TODS), 30(1):249-21) 278, 2005.
Graham Cormode, Flip Korn, Shanmugavelayutham Muthukrishnan, and Divesh Srivastava. Finding hierarchical heavy hitters in data streams. In Proceedings 2003 VLDB Conference, pages 474. Elsevier, 2003.
Graham Cormode. Minos Garofalakis, Shanmugavelayutham Muthukrishnan, and Rajeev Rastogi. Holistic aggregates networked world: Distributed tracking of approximate quantiles. In Proceedings of the 2005 ACM SIGMOD international conference on Management of data, pages 25-36, 2005.
Robert Dorfman. The detection of defective members of large populations. The Annals of Mathemat- ical Statistics, 14(4):436-440, 1943.
Dingzhu Du, Frank K Hwang, and Frank Hwang. Combinatorial group testing and its applications, volume 12. World Scientific, 2000.
Joshua Engels, Benjamin Coleman, and Anshumali Shrivastava. Practical near neighbor search via group testing. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 9950-9962. Curran Associates, Inc., 2021.

---

Amos Fiat, Yishay Mansour, and Uri Nadav. Efficient contention resolution protocols for selfish agents. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA); pages 179-188. SIAM, 2007.
Phillip B Gibbons, Yossi Matias, and Viswanath Poosala. Fast incremental maintenance of approxi- mate histograms. ACM Transactions on Database Systems (TODS), 27(3):261-299 2002.
Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, Sivaramakrishnan Muthukrishnan, and Martin Strauss. Fast, small-space algorithms for approximate histogram maintenance. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 389-398, 2002a.
Anna C. Gilbert, Yannis Kotidis, S Muthukrishhan, and Martin J Strauss. How to summarize the universe: Dynamic maintenance of quantiles. In VLDB 02: Proceedings of the 28th International Conference Very Large Datahases, pages 454-465. Elsevier, 2002b.
Albert G. Greenberg and Shmuel Winograd. lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels. Journal of the ACM, 32(3):89--596 1985.
Michael Greenwald and Sanjeev Khanna. Space-efficient online computation of quantile summaries. ACM SIGMOD Record, 30(2):58- 66, 2001.
Jeremiah F. Hayes. An adaptive technique for local distribution. IEEE Transactions on Communica- tions, 26(8):1 117111181111 1111-188761111111111111111111111 1186, 1978.
William Kautz and Roy Singleton. Nonrandom binary superimposed codes. IEEE Transactions on Information Theory, 10(4):363-377, 1964.
Marek Klonowski, Dariusz R. Kowalski, and Dominik Pajak. Generalized framework for group testing: Queries, feedbacks and adversaries. Theor. Comput. Sci., 919:18-35, 2022.
Dariusz Kowalski and Dominik Pajak. Scalable and efficient non-adaptive deterministic group testing. In S. Koyejo. S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Prucessing Systems, volume 35, pages 15132-1511 1514.. Curran Associates, Inc., 2022a.
Dariusz R. Kowalski and Dominik Pajak. Light agents searching for hot information. In Luc De Raedt, editor, Proceedings of the Thirty-Fite Firs- International Joinl Conference Arlificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pages 363-369. ijeai.org, 2022b.
Weixin Liang and James Zou. Neural group testing to accelerate deep learning. In 2021 IEEE International Symposium on Information Theory (ISIT), pages 958-963. IEEE, 2021.
Smriti Mallapaty et al. The mathematical strategy that could transform coronavirus testing. Nature, 583078177:504-555, 2020.
Michael Maschler, Eilon Solan, and Shmuel Zamir. Game Theory. Cambridge University Press, second edition, 2020.
Robert M. Metcalfe and David R. Boggs. Ethernet: Distributed packet switching for local computer networks. Communications of the ACM, 19(7):395-404, 1976.
Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007.
Martin Osborne and Ariel Rubinstein. Course in Game Theory. MIT Press, 1994.
Ely Porat and Amir Rothschild. Explicit nonadaptive combinatorial group testing schemes. IEEE Transactions Information Theory, 57(12):7982-7988 2011.
Nasa Simnstt-Armstrong, Daniel Klein, and Brendan Hickey. Evaluation of group testing for sars-cov-2 ma. MedRxiv, 2020.
12

---

Shashanka Ubaru, Sanjeeb Dash, Arya Mazumdar, and Oktay Gunluk. Multilabel classification by hierarchical partitioning and data-dependent grouping. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 22542-22555
Curran Associates, Inc., 2020.
Jeffrey Xu Yu, Zhihong Chong, Hongjun Lu, and Aoying Zhou. False positive or false negative: Mining frequent itemsets from high speed transactional data streams. In VLDB, volume 4, pages 204-215, 2004.
13


Reviews:
[{"review_id": "9YM3X4zJ3Q", "reviewer": "Reviewer_YF8o", "summary": "In this paper, the authors study the problem of combinatorial group testing in a new framework, when the elements to be found are selfish players. The authors propose an algorithm such that no agent is willing to deviate from the algorithm strategy (being in this way in an adversarial equilibrium). ", "questions": "See weaknesses.", "limitations": "No potential negative societal limitations.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-written and very clear. The graphical example the authors provide helps in understanding the mechanism beyond the algorithm.\n\n- The authors provide lower bounds on the novel problem setting and an algorithm to solve the problem.\n\n- I checked the proofs and the results seem sound and well-explained.", "weaknesses": "- It is not very clear to me which is the application of this approach. What kind of application cannot be modeled with classical CGT and they can be modeled with this multi-agent setting? In which cases do these selfish agents appear? I saw that there are some examples in the appendix, but it would be helpful to spend more time describing them.\n\n- I suggest moving to the main paper an intuition for the presented lower bounds. It is always helpful to understand the hardness of the problem.\n\n- What are the main technical challenges with respect to Chionas et al.?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for valuable feedback. Below we give our answers. If the reviewer believes that we have addressed adequately all of her/his concerns, we would very much appreciate if she/he reconsiders upgrading the score for our paper.\n\n**Question 1:**\n*It is not very clear to me which is the application of this approach. What kind of application cannot be modeled with classical CGT and they can be modeled with this multi-agent setting? In which cases do these selfish agents appear? I saw that there are some examples in the appendix, but it would be helpful to spend more time describing them.*\n\nResponse: \n\nOur CGT+AE framework is not actually competing, in terms of applications, with the classical CGT, but it is rather an add on. It could be applied to **assure fairness** in any application of the CGT which assumes some autonomy of the elements. For instance, one could consider new blockchain mechanisms in which miners compete to add their blocks to the blockchain in a fair way. To do it, they could pick or be assigned with a random ID, and our new framework assures that all blocks will be efficiently added, in a random order (as no miner has any incentive to deviate the search going through random IDs).\n\nAnother application that uses the full CGT setting is where we are given a distributed database with $n$ selfish servers, where some $k$ of those servers hold $k$ pieces of information that a user is looking for in the database. In the beginning, the IDs of these servers are not known to the user (in this sense, we could model it as adversarial choice). Each of the $k$ servers wants to have its information to be found (\"released\") as early as possible (because it can use its resources to serve the next query when it is free and does not need to wait to \"release\" its information, or could be even awarded for promoting the information stored on it). A possible approach could give random ids to the servers before running a CGT+AE search, thus also ensuring fairness in the treatment of the servers, unless they would deviate (but that is prevented, or at least discouraged, by the solution being an AE).\n​\nSimilar technique could be applied to the master-workers systems, including Distributed/Decentralized/Federated ML and AI. In order to **avoid biases** when processing the results of the jobs in some order, the master could require the workers who are ready (in our model -- active) to submit their results in random order. To do it, the master attaches random IDs to the jobs sent to workers, and asks those of them who are ready to execute the CGT protocol which is AE. The CGT part assures that all work is collected. Random IDs of jobs assure random order, provided no worker deviates. AE part assures that no matter which set of workers is ready, none of them is incentivized to deviate.\n​\nThere are also several other applications of CGT considered in recent ML/AI publications, to different types of searches, string mining, etc. cf., \n​\n- J. Engels, B. Coleman, and A. Shrivastava. Practical near neighbor search via group testing. NeurIPS 2021\n​\n- D.R. Kowalski and D. Pajak. Light agents searching for hot information. IJCAI 2022\n​\n\nWe will include these applications in the proceedings version of our paper (as typically 1 extra page is available in the proceedings) if the paper is accepted.\n\n\n**Question 2:**\n*I suggest moving to the main paper an intuition for the presented lower bounds. It is always helpful to understand the hardness of the problem.*\n\nResponse: \n\nIf our paper gets accepted, we will add these aspects to the main body of the paper, as well as the details of the above application to blockchain. (NeurIPS  typically allows one more page in the proceedings.)\n\n**Question 3:**\n*What are the main technical challenges with respect to Chionas et al.?*\n\nResponse: \n\nThe main challenge arises from the fact that our work considers adaptive strategies while the one by Chionas et al. considers only non-adaptive strategies. "}, {"review_id": "rp7obY5veS", "reviewer": "Reviewer_X2Ux", "summary": "This paper introduces a game theoretic framework in the context of combinatorial group testing. In detail, in a population of $n$  elements, there are $k<n$ agents that are considered active (e.g. they are positive to some disease) and the goal is to use queries on subsets of the $n$ elements to reveal who those $k$ agents are. These active agents can strategize, i.e., choose whether they are included in the queries used to reveal the subset of active elements. \n\nThe authors introduce a modified notion of adversarial equilibrium that allows adaptive queries (i.e. queries that can depend on previous queries).", "questions": "* What would be the main challenge in getting similar results for an unknown number $k$?\n* Why do you not consider non-active elements as non-strategizing?\n* Could you clarify the connection between CR and CGT?", "limitations": "The limitations are, to the best of my understanding, adequately discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* Clear and interesting outline of previous work.\n* Accessible language, self-contained definitions, and overall clear presentation of background and novel ideas.\n* The game theoretic setting seems interesting, natural, and well-motivated.", "weaknesses": "The main weakness is the fact that the main results have to do with an a priori known number of active elements $k$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for valuable feedback. Below we give our answers. If the reviewer believes that we have addressed adequately all of her/his concerns, we would very much appreciate if she/he reconsiders upgrading the score for our paper.\n\n**Weakness:**\n*The main weakness is the fact that the main results have to do with an a priori known number of active elements.*\n\nResponse: \n\nWe prove that, it is the nature of the problem that the lack of any knowledge of $k$ yields high complexity. \nMore precisely, we prove that if $k$ is unknown, no algorithm can guarantee a revealing time smaller than $\\Theta(n)$ -- please see our lower bound; in this case we show an algorithm with the revealing time of $O(n^k)$. Hence, for unknown $k$ the problem is provably hard. On the other hand, this question of the reviewer opens an interesting avenue for further work. That is, we can ask what happens if we have some partial knowledge about $k$, for instance, a rough upper bound on $k$, e.g., $k \\leq k^*$ for some $k^*$ known to the algorithm? In this case, could one prove an upper bound on the revealing time that is, for instance, polynomial in $k^*$ and $\\log(n)$ ?\n\nAnother opportunity for efficient algorithms would be a model with extended feedback function, e.g., returning some approximate or even exact size of the intersection of the query and the hidden set (so called Quantitative Group Testing). However, one would need to study if there are any beneficial deviations due to such extended feedback received in each round of the game.\n\n\n**Question 1:**\n*What would be the main challenge in getting similar results for an unknown number $k$?*\n    \n\nResponse: \n\nIf $k$ is unknown, the adversary has even more power, since it not only selects the configuration but also the size, and the agents are agnostic to it. \nOur current approach is, roughly speaking, to query complements of all possible configurations for increasing values of $k-1$ (starting from $k-1=1$), so that when the considered size of a configuration is correct, any deviation leads to discoverable effect and a \"punishment strategy\" could be applied by non-deviating agents. Finding a way to avoid addressing all configurations of a given size in separate queries, and thus (substantially) reducing the number of queries, seems to be the main challenge in the setting with unknown $k$. We formally show that this setting is more difficult than the one with known $k$\nby proving a lower bound of $\\Omega(n)$ on the revealing time.  We remind that in BS_Jumps$(n,k)$ we achieve equilibrium with low latency because of the knowledge of the $(k-1)$'st revelation -- this is not possible in the case of unknown $k$.\n\n**Question 2:** \n*Why do you not consider non-active elements as non-strategizing?*\n\nResponse: \n\nThe nature of CGT splits agents into $k$ active agents and the remaining $n-k$ non-active agents. However, at the beginning of the game no agent knows which other agents are active and therefore could strategize. The set of active agents is being revealed as the game proceeds. But we cannot assume that from the perspective of any (active) agent, some other agent, say $i$, is non-strategizing, because that agent may not know whether $i$ is active until the whole set of active agents is revealed. \nThat is, the non-active agents cannot be assumed to be non-strategizing, because the protocol (AE) must be prepared for ANY of the $n$ agents to be chosen (by the adversary) as active, and therefore -- prevent its potential deviations.\n\n**Question 3:**\n*Could you clarify the connection between CR and CGT?*\n\nResponse:\n\nFormally speaking, CR is a communication problem in which each player has a packet to send successfully (i.e., alone) on the multiple-access channel to which it is connected (together with other agents). CGT is a learning problem in which a hidden set must be discovered by asking queries and receiving feedback.\nThe main conceptual similarity between CR and CGT is the environment -- agents decide to transmit (equiv., be included in the query) or not and they receive feedback from the channel (equiv., broker of the CGT process -- the feedback function). Differences are in details, as CR problem -- as a communication problem -- may adopt communication features, such as acknowledgments (i.e., feedback received only by a single transmitter), possibility of sending actual information to be received by others in case of successful/alone transmission (apart of the feedback), possibility of performing fake/jamming transmissions (even if it is an alone transmission, it does not fulfill the goal of CR because the actual packet has not been transmitted), etc. \nAnother subtle difference is that in CR each player has to transmit alone at least once in order to fulfill its goal, which in CGT we may sometimes reveal the hidden set based on feedback analysis, even if not every active element occurred in a singleton intersection with a query.\nWe also provide some intuitions about transformation from CGT to CR in the Supplementary Materials Section 5; we could copy it to the main part, space permitting.\n"}, {"review_id": "4bUtjRVfxm", "reviewer": "Reviewer_LHGX", "summary": "This submission applies and extends a very recent game theoretic perspective, introducing in particular a notion of strategy equilibrium called adversarial equilibrium, on contention resolution games to the more general setting of combinatorial group testing. In combinatorial group testing, a (typically small) group must be revealed among a large set of candidates by feedback to certain queries. In this game theoretic setting the small group is considered as the set of players who execute strategies to include or remove themselves from the queries prescribed by an algorithm given on input. Adversarial equilibrium captures the notion that, no deviation from a strategy allows a to not increase and to strictly decrease their revealing time for all adversarial and one adversarial choice of the small set. It also provides strategies for agents which satisfy an adversarial equilibrium and achieve almost the best possible bound (the lower bound is known and independent from the considered game theoretic model) on the latest revealing time of a player in the small group when the size of the small group is known, and less tight upper and lower bounds for the latest revealing time of a player achievable by adversarial equilibrium strategies.", "questions": "Can you clarify the above points relating to the motivation behind taking a game theoretic perspective and requiring adversarial equilibrium for CGT?", "limitations": "No concerns.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The combinatorial group testing problem is highly relevant, also in the context of machine learning and hence fits the scope of NeurIPS well.\nThe contribution claims to generalise some recent results accepted for publication at a strong venue (unfortunately the proceedings seem not to be available yet and hence I was not able to have a closer look at it).\nThe quality of the technical writeup is good and I did not spot any flaws.", "weaknesses": "To me the motivation of requiring adversarial equilibria or even considering CGT as games played by the small set that should be revealed is not sufficiently supported in my opinion. In particular I would appreciate a discussion of settings of CGT in which this is natural to consider (the applications provided in the supplementary material are a step in this direction but I would ask even more explicitly why one would be interested in designing AE strategies for blockchain mechanisms; for CR this seems a bit more clear to me but this is also somewhat unsurprising as this is the context in which AE was introduced) as well as a more explicit comparison of how `adversarial aspects' have been addressed in CGT previously.\n\n-L76: it is not completely clear to me, what `usefulness' is demonstrated here. By this I do not mean to say that the presented results are uninteresting but rather that I do not understand how they make a point of any benefit behind requiring AE as it is even presented for unknown k that this comes at the necessary cost of worse latest revealing times.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for valuable feedback. Below we give our answers. If the reviewer believes that we have addressed adequately all of her/his concerns, we would very much appreciate if she/he reconsiders upgrading the score for our paper.\n\n**Question 1:**\n*To me the motivation of requiring adversarial equilibria or even considering CGT as games played by the small set that should be revealed is not sufficiently supported in my opinion. In particular I would appreciate a discussion of settings of CGT in which this is natural to consider (the applications provided in the supplementary material are a step in this direction but I would ask even more explicitly why one would be interested in designing AE strategies for blockchain mechanisms; for CR this seems a bit more clear to me but this is also somewhat unsurprising as this is the context in which AE was introduced) as well as a more explicit comparison of how \"adversarial aspects\" have been addressed in CGT previously.*\n\nResponse:\n\nOur CGT+AE framework could be applied to **assure fairness** in any application of the CGT which assumes some autonomy of the elements. For instance, one could consider new blockchain mechanisms in which miners compete to add their blocks to the blockchain in a fair way. To do it, they could pick or be assigned with a random ID, and our new framework assures that all blocks will be efficiently added, in a random order (as no miner has any incentive to deviate the search going through random IDs).\n\nAnother application that uses the full CGT setting is where we are given a distributed database with $n$ selfish servers, where some $k$ of those servers hold $k$ pieces of information that a user is looking for in the database. In the beginning, the IDs of these servers are not known to the user (in this sense, we could model it as adversarial choice). Each of the $k$ servers wants to have its information to be found (\"released\") as early as possible (because it can use its resources to serve the next query when it is free and does not need to wait to \"release\" its information, or could be even awarded for promoting the information stored on it). A possible approach could give random ids to the servers before running a CGT+AE search, thus also ensuring fairness in the treatment of the servers, unless they would deviate (but that is prevented, or at least discouraged, by the solution being an AE).\n​\nSimilar technique could be applied to the master-workers systems, including Distributed/Decentralized/Federated ML and AI. In order to **avoid biases** when processing the results of the jobs in some order, the master could require the workers who are ready (in our model -- active) to submit their results in random order. To do it, the master attaches random IDs to the jobs sent to workers, and asks those of them who are ready to execute the CGT protocol which is AE. The CGT part assures that all work is collected. Random IDs of jobs assure random order, provided no worker deviates. AE part assures that no matter which set of workers is ready, none of them is incentivized to deviate.\n​\nThere are also several other applications of CGT considered in recent ML/AI publications, to different types of searches, string mining, etc. cf., \n​\n- J. Engels, B. Coleman, and A. Shrivastava. Practical near neighbor search via group testing. NeurIPS 2021\n​\n- D.R. Kowalski and D. Pajak. Light agents searching for hot information. IJCAI 2022\n​\n\nWe will include these applications in the proceedings version of our paper (as typically 1 extra page is available in the proceedings) if the paper is accepted.\n\n\n**Question 2:**\n*-L76: it is not completely clear to me, what \"usefulness\" is demonstrated here. By this I do not mean to say that the presented results are uninteresting but rather that I do not understand how they make a point of any benefit behind requiring AE as it is even presented for unknown k that this comes at the necessary cost of worse latest revealing times.*\n\nResponse:\n\nApologies for a confusion. We used the word \"usefullness\" in the wrong context. What we meant here is that our added notion of AE does make a difference comparing to the classical CGT (and related settings, such as CR) because it leads to different algorithms, techniques and performance bounds."}, {"review_id": "DU9m7BckmY", "reviewer": "Reviewer_53TB", "summary": "The paper studies Combinatorial Group Testing (CGT) problem in a game-theoretic setting. The setup consists of a set $[n]$ of $n$ agents, of which a set of $k$ agents, denoted by $K$ are `active'. The goal is to reveal their identities in the minimum time possible via set of queries. Each query $Q$ is a subset of $[n]$ and the feedback available to agents is information about $Q\\cup K$. Authors present results using the notion of adversarial equilibrium (AE). Two scenarios are explored: one where the number of active agents (k) is known, and one where it is not. In the known scenario, they demonstrate AE strategies that achieve near-optimal revealing times $O(k \\log(\\frac{n}{k}))$. However, in the unknown scenario, the revealing time increases to the order of $n^{k-1}$ with a lower bound of $\\Omega(n)$.\n\n=====================================================================\n\nEDIT:\nI have improved the score from 6 to 7 after authors' response.", "questions": "(*) I do not understand the idea of `` selfishness'' of an agent. What constitutes the selfish behavior and what are the implications of that? Please clearly define and introduce it?\n\n(*) In Section 2.1, is it true that none of the agents have information about the query generated at time $t$ (as one agent can deviate from the prescribed strategy). so, is it fair to say that ``algorithm'' is a central entity collecting the output of each agent's decision to be included in the query or not along with agents decision to deviate from the standard strategy or not. This central algorithm entity then creates a query.\n \n(*) The authors present two new algorithms but don't provide enough information about their efficiency, besides mentioning the revealing time. For instance, are there any concerns about computational complexity, memory use, or scalability to larger problems?", "limitations": "(*) As I mentioned before, please discuss the motivation/limitations/implications of the specific feedback function (lines 117 -- 119). \n\n(*) The authors mention various applications of CGT in the introduction, but it's unclear how well their AE model or algorithms would perform in these situations based on the information provided.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "(+) The problem is very nicely and clearly introduced in Section 2. Also, the problem is quite interesting. The paper is well written, especially the technical aspects are well articulated and discussed. \n\n(+) The algorithm for the case where $k$ is known (BS\\_Jumps) and the analysis showing that the performance is ``close'' to the optimal is a sound contribution.\n    \n(+) CGT has been studied for decades. This new outlook leveraging game-theoretic ideas is indeed interesting (though this paper is not the first one to use it). \n\n(+) Several interesting applications are identified and discussed.", "weaknesses": "(-) The paper essentially builds up on the ideas of Chionas et al. [2023]. It also seems like extension of their setups, which is not entirely a bad thing; however, it limits the extent of contributions. The main algorithmic contribution of the paper is basically the \\emph{BS\\_Jumps} algorithm. The other algorithms are either from the literature or are straight-forward.\n\n(-) The feedback function used is not well motivated (at least this reviewer can not make a practical sense out of it). Please discuss  the implications of it.\n\n(-) This paper offers theoretical results, which is good. However, there is no numerical evaluation/experiments section. I think a section dedicated to the empirical testing or validation of the proposed algorithms will surely enrich the paper. I think this is an important weakness of the paper.\n\n(-) The case where $k$ is unknown is not thoroughly (at least not as thoroughly as the case with known $k$) discussed. \n\\end{itemize}", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weakness 1**: *The paper … builds up on ideas of Chionas et al. [2023]. It also seems like extension of their setups, which is not entirely bad thing; however, it limits the extent of contributions. The main algorithmic contribution of the paper is basically the BS_Jumps algorithm.* \n\n Reply: \n\nWe adapt their definition of Adversarial Equilibrium (AE) in our new setting with any algorithms  (strategies), including non-adaptive and adaptive ones, but Chionas et al. consider only non-adaptive strategies. This adaptation of AE requires new formalization of deviation -- deviation was fixed in advance (non-adaptive) in Chionas et al. while in our case, it could be decided by the deviating agent online. There are also minor differences in the problem setting, as they consider CR problem but we focus on general CGT. Adaptive strategies pose new significant challenges, discussed in the general rebuttal file, and as a result -- our algorithms, formulas and analysis are **entirely different**. \n\n**Weakness 2, Limitation 1**: *Feedback function used is not well motivated (at least this reviewer can not make a practical sense out of it). Please discuss the implications of it.* \n\nReply: \n\nOur feedback function, defined in lines 117-119, is one of the simplest considered in  CGT, known in literature as ternary feedback or $(2, \\log n)$-feedback in the generalized CGT nomenclature, cf. Klonowski et al. Generalized framework for group testing:... TCS 2022. \n\nIf the query has a singleton intersection with the hidden set, then naturally feedback reveals the respective agent's ID. If the intersection is empty or has size at least $2$, then the feedback is empty or clash, respectively. We chose this feedback for presentation of our ideas because of its simple nature (eg, no need to \"decode'' the ID of singletons). \n\nProbably even more popular feedback is when instead of ID of the singleton, a value $1$ or range $\\ge 1$ (so called \"beeping\") is revealed. \n\nWe show (Suppl. Materials Sec. 5) how to extend our results to such weaker CGT feedbacks and to the setting used in the CR problem. \n\nThus, our results cover a wider range of natural, well motivated CGT and CR settings. \n\n**Weakness 3**: *The case where $k$ is unknown is not thoroughly (at least not as thoroughly as the case with known) discussed.* \n\nReply: \n\nThe case of unknown $k$ is less discussed, as we prove a strong lower bound in this case - we prove that any CGT+AE algorithm in this case has revealing time at least $\\Omega(n)$. \n\nWe also design and analyze an algorithm which is polynomial in $n$ for any constant $k$; see also our response to Q1 of Reviewer X2Ux regarding technical challenges. \n\nIt is interesting, though, to explore cases between knowing and not knowing at all the number of active agents, eg, having partial knowledge about $k$, an upper bound on $k$, or even consider the number of active agents as a random variable and devise bounds for the distribution of this number.   \n\n**Q1:** *I do not understand the idea of \"selfishness\" of an agent. What constitutes the selfish behavior and what are the implications of that? Please clearly define and introduce it?* \n\nReply: \n\nIn our setting, each agent's goal is to minimize its revealing time. Selfish behavior means that an agent could deviate from what a query says, see lines 169-176, in order to reduce its revealing time. As we prove that our algorithms are AE, no agent will deviate unilaterally without a threat of worsening their revealing time. An implication of selfish behavior in equilibrium is that the respective metric of global efficiency is compromised compared to the cooperative setting. This is quantified by Price of Anarchy, and the loss in efficiency is depicted in Table 1. \n\n**Q2:** *In Sec. 2.1, is it true that no agent has information about query generated at time $t$ (as one agent can deviate from the prescribed strategy). so, is it fair to say that \"algorithm\" is a central entity collecting output of each agent's decision to be included in the query or not along with agents decision to deviate from standard strategy or not. This central algorithm entity then creates a query.* \n\nReply: \n\nReviewer’s intuition is correct, our only comment is that we use word \"algorithm\" in association with strategies (or computing them) at each agent, while the \"centralized entity\" mentioned by Reviewer is actually the **feedback function**. It was defined within CGT setting (from line 115), but we will add a reminder after line 168 that: after each agent decides if it is present in the query or not, the feedback function’s outcome is computed based on the agents' decisions and communicated to all agents. \n\n**Q3:** *The authors present two new algorithms but don't provide enough information about their efficiency, besides mentioning the revealing time. For instance, are there any concerns about computational complexity, memory use, or scalability to larger problems?* \n\nReply: \n\nThe main efficiency metric is the revealing time (query complexity), i.e., number of game’s rounds. Total communication complexity can be derived as a function of protocol’s revealing time. In each round, each active agent communicates a single bit. The ternary feedback can be encoded by $\\log n$ bits. Let $T$ be the protocol’s revealing time. Thus, total communication complexity of a protocol is $(k+\\log n) \\cdot T$ bits. The total number of local steps during the game can be upper bounded by $\\log n \\cdot T$, as each round of algorithm BS_Jumps requires updating token, which is a logarithmic operation (see Suppl. Materials, Sec. 3). The memory needed in each agent is logarithmic, due to simple recursion in main algorithm and token update and a constant number of variables. This is assuming that basic arithmetic operation on values, with logarithmic bit representation, is done in single local step, and these numbers are stored in a memory unit.\n\n**Limitation 2** applications addressed in the general rebuttal file."}]

Author rebuttal:
We would like to thank the reviewers for their effort and valuable feedback. Below we address the main two requests for providing more applications and describing technical challenges comparing to Chionas et al. IJCAI 2023. Other questions we address as individual rebuttals to the reviewers.

**More details on applications of the CGT+AE framework.**


Response:
Our CGT+AE framework is not actually competing, in terms of applications, with the classical CGT, but it is rather an add on. It could be applied to **assure fairness** in any application of the CGT which assumes some autonomy of the elements. For instance, one could consider new blockchain mechanisms in which miners compete to add their blocks to the blockchain in a fair way. To do it, they could pick or be assigned with a random ID, and our new framework assures that all blocks will be efficiently added, in a random order (as no miner has any incentive to deviate the search going through random IDs).

Another application that uses the full CGT setting is where we are given a distributed database with $n$ selfish servers, where some $k$ of those servers hold $k$ pieces of information that a user is looking for in the database. In the beginning, the IDs of these servers are not known to the user (in this sense, we could model it as adversarial choice). Each of the $k$ servers wants to have its information to be found ("released") as early as possible (because it can use its resources to serve the next query when it is free and does not need to wait to "release" its information, or could be even awarded for promoting the information stored on it). A possible approach could give random ids to the servers before running a CGT+AE search, thus also ensuring fairness in the treatment of the servers, unless they would deviate (but that is prevented, or at least discouraged, by the solution being an AE).

Similar technique could be applied to the master-workers systems, including Distributed/Decentralized/Federated ML and AI. In order to **avoid biases** when processing the results of the jobs in some order, the master could require the workers who are ready (in our model -- active) to submit their results in random order. To do it, the master attaches random IDs to the jobs sent to workers, and asks those of them who are ready to execute the CGT protocol which is AE. The CGT part assures that all work is collected. Random IDs of jobs assure random order, provided no worker deviates. AE part assures that no matter which set of workers is ready, none of them is incentivized to deviate.

There are also several other applications of CGT considered in recent ML/AI publications, to different types of searches, string mining, etc. cf., 

- J. Engels, B. Coleman, and A. Shrivastava. Practical near neighbor search via group testing. NeurIPS 2021

- D.R. Kowalski and D. Pajak. Light agents searching for hot information. IJCAI 2022

We will include these applications in the proceedings version of our paper (as typically 1 extra page is available in the proceedings) if the paper is accepted. 


**Main (technical) challenges with respect to the paper by Chionas et al.**

Response: 
The main challenge arises from the fact that our work considers all possible strategies (adaptive and non-adaptive) while the one by Chionas et al. considers only non-adaptive strategies: 
- Thus, on one hand, adaptiveness  considered in our work allows building a wider class of strategies that adapt to the feedback history of the game, possibly being much better and faster revealing the hidden set. This opens additional opportunities of designing more efficient algorithms, but makes the proofs of lower bounds more difficult (as they need to hold for any feasible algorithm).

- However, on the other hand -- it is more difficult to assure that such adaptive strategies form an equilibrium, comparing to the analysis of non-adaptive strategies in Chionas et al. This is because there are much more deviating adaptive strategies than non-adaptive ones -- i.e., the deviating agent can decide about deviation online, even after revealing part of the hidden set, while non-adaptive deviating strategy must fix the changes in its strategy in advance (and they stay the same during the whole game, regardless of what are the other elements in the actual hidden set). In particular, in our analysis, we could not just fix a deviating strategy and consider any hidden set (as in Chionas et al.), but we also need to take into account deviations occurring after revealing some elements from the hidden set during the game.

Other challenges, though not as critical as above, arise from subtle differences between the Contention Resolution problem (focused on in the other work) and CGT (focused on in our work), for instance, we do not assume the feature analogous to "jamming transmissions" which was helpful in case of non-adaptive CR to enforce "punishment mechanism".
See also our response to Reviewer X2Ux for more details on differences between CGT (considered in this work) and CR problem (studied by Chionas et al.). 

As a result of the abovementioned new challenges, our algorithms and lower bounds are **entirely different** (in terms of design, formulas and analysis) from the ones in Chionas et al.

Meta-review: In this paper the author introduce a novel problem of combinatorial group testing as follows: There are n agents out of which k (k < n) are belong to the group of target (e.g. they all have a target featuer), and the goal is to use efficient number of queries on subsets of the n agents to correctly identify the k target agents. The novel setting is that the k target agents can strategize, i.e., choose whether they are included in the queries.

The main contribution of this paper is a modified notion of adversarial equilibrium that allows adaptive queries (i.e. queries that can depend on previous queries) and the analysis of this new equilibrium.

After a productive rebuttal phase, the only remaining concern from the reviewers is the lack of experiments. However, I don't this this is a major issue as the paper is theoretical. Hence I recommend accepting this paper.
Decision: Accept (poster)