Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Combinatorial Group Testing with Selfish Agents
Authors: Georgios Chionas, Dariusz Kowalski, Piotr Krysta
NeurIPS 2023 | Venue PDF | 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 EMAIL Dariusz R. Kowalski Piotr Krysta School of Computer and Cyber Sciences Augusta University Augusta, Georgia, USA EMAIL |
| 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. |