Combinatorial Group Testing with Selfish Agents
Authors: Georgios Chionas, Dariusz Kowalski, Piotr Krysta
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the Combinatorial Group Testing (CGT) problem in a novel gametheoretic 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] = {0, 1, . . . , n 1}, and a hidden set K [n] of active agents of size |K| = k n. In each round of the game, each active agent decides if it is present in a query Q [n], and all agents receive some limited feedback on Q 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 a comprehensive set of results for 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 show adaptive AE strategies with provably near-optimal maximum revealing time of O(k log(n/k)). In the case of unknown k, we design adaptive AE strategies with maximum revealing time of order nk 1, and we prove a lower bound of Ω(n) on the maximum revealing time of any such algorithmic strategies. |
| Researcher Affiliation | Academia | Georgios Chionas Department of Computer Science University of Liverpool Liverpool, United Kingdom g.chionas@liverpool.ac.uk Dariusz R. Kowalski Piotr Krysta School of Computer and Cyber Sciences Augusta University Augusta, Georgia, USA {dkowalski,pkrysta}@augusta.edu |
| Pseudocode | Yes | Algorithm 1: BS_Jumps(n, k), pseudo-code for active agent j; Algorithm 2: BB_GR(n, k ), pseudo-code for active agent j |
| Open Source Code | No | The paper does not provide any statement or link regarding the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and analysis for Combinatorial Group Testing within a game-theoretic framework. It does not involve empirical evaluation on datasets, and therefore no dataset access information is provided. |
| Dataset Splits | No | The paper presents theoretical research, focusing on algorithm design and analysis, and therefore does not involve empirical validation on datasets with train/validation/test splits. |
| Hardware Specification | No | The paper is theoretical, designing and analyzing algorithms for combinatorial group testing. It does not report on empirical experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical, presenting algorithm design and analysis, and does not mention any specific software dependencies or their version numbers required for implementation or experimentation. |
| Experiment Setup | No | The paper focuses on theoretical algorithm design and analysis and does not describe an experimental setup with hyperparameters or system-level training settings. |