4 accepted papers
Suppose we are given an integer k and n boxes, labeled 1,2,…,n by an adversary, each containing a single number chosen from an unknown distribution; the n distributions not necessarily identical. We have to choose an order to sequentially open the boxes, and each time we open the next box in this or…
We study contention resolution (CR) on a shared channel modelled as a game with selfish players. There are n agents and the adversary chooses some k smaller than n of them as players. Each participating player in a CR game has a packet to transmit. A transmission is successful if it is performed as…
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…
We study the power and limitations of the Vickrey-Clarke-Groves mechanism with monitoring (VCGmon) for cost minimization problems with objective functions that are more general than the social cost. We identify a simple and natural sufficient condition for VCGmon to be truthful for general objective…