Ankur A. Kulkarni

Sharu Theresa Jose, Ankur A. Kulkarni

We study the setting of channel coding over a family of channels whose state is controlled by an adversarial jammer by viewing it as a zero-sum game between a finite blocklength encoder-decoder team, and the jammer. The encoder-decoder team choose stochastic encoding and decoding strategies to minimize the average probability of error in transmission, while the jammer chooses a distribution on the state-space to maximize this probability. The min-max value of this game is equivalent to channel coding for a compound channel -- we call this the Shannon solution of the problem. The max-min value corresponds to finding a mixed channel with the largest value of the minimum achievable probability of error. When the min-max and max-min values are equal, the problem is said to admit a saddle-point or von Neumann solution. While a Shannon solution always exists, a von Neumann solution need not, owing to inherent nonconvexity in the communicating team's problem. Despite this, we show that the min-max and max-min values become equal asymptotically in the large blocklength limit, for all but finitely many rates. We explicitly characterize this limiting value as a function of the rate and obtain tight finite blocklength bounds on the min-max and max-min value. As a corollary we get an explicit expression for the $ε$-capacity of a compound channel under stochastic codes -- the first such result, to the best of our knowledge. Our results demonstrate a deeper relation between the compound channel and mixed channel than was previously known. They also show that the conventional information-theoretic viewpoint, articulated via the Shannon solution, coincides asymptotically with the game-theoretic one articulated via the von Neumann solution.

Anuj S. Vora, Ankur A. Kulkarni

During the COVID-$19$ pandemic the health authorities at airports and train stations try to screen and identify the travellers possibly exposed to the virus. However, many individuals avoid getting tested and hence may misreport their travel history. This is a challenge for the health authorities who wish to ascertain the truly susceptible cases in spite of this strategic misreporting. We investigate the problem of questioning travellers to classify them for further testing when the travellers are strategic or are unwilling to reveal their travel histories. We show there are fundamental limits to how many travel histories the health authorities can recover.% can be correctly classified by any probing mechanism.

Vivek Deulkar, Jayakrishnan Nair, Ankur A. Kulkarni

The inherent intermittency of wind and solar generation presents a significant challenge as we seek to increase the penetration of renewable generation in the power grid. Increasingly, energy storage is being deployed alongside renewable generation to counter this intermittency. However, a formal characterization of the reliability of renewable generators bundled with storage is lacking in the literature. The present paper seeks to fill this gap. We use a Markov modulated fluid queue to model the loss of load probability (LOLP) associated with a renewable generator bundled with a battery, serving an uncertain demand process. Further, we characterize the asymptotic behavior of the LOLP as the battery size scales to infinity. Our results shed light on the fundamental limits of reliability achievable, and also guide the sizing of the storage required in order to meet a given reliability target. Finally, we present a case study using real-world wind power data to demonstrate the applicability of our results in practice.

Mathew P. Abraham, Ankur A. Kulkarni

We address the problem of finding conditions which guarantee the existence of open-loop Nash equilibria in discrete time dynamic games (DTDGs). The classical approach to DTDGs involves analyzing the problem using optimal control theory which yields results mainly limited to linear-quadratic games. We show the existence of equilibria for a class of DTDGs where the cost function of players admits a quasi-potential function which leads to new results and, in some cases, a generalization of similar results from linear-quadratic games. Our results are obtained by introducing a new formulation for analysing DTDGs using the concept of a conjectured state by the players. In this formulation, the state of the game is modelled as dependent on players. Using this formulation we show that there is an optimisation problem such that the solution of this problem gives an equilibrium of the DTDG. To extend the result for more general games, we modify the DTDG with an additional constraint of consistency of the conjectured state. Any equilibrium of the original game is also an equilibrium of this modified game with consistent conjectures. In the modified game, we show the existence of equilibria for DTDGs where the cost function of players admits a potential function. We end with conditions under which an equilibrium of the game with consistent conjectures is an $ε$-Nash equilibria of the original game.

Bharat Prabhakar, Ankur A. Kulkarni

We present a method for dimensionality reduction of an affine variational inequality (AVI) defined over a compact feasible region. Centered around the Johnson Lindenstrauss lemma, our method is a randomized algorithm that produces with high probability an approximate solution for the given AVI by solving a lower-dimensional AVI. The algorithm allows the lower dimension to be chosen based on the quality of approximation desired. The algorithm can also be used as a subroutine in an exact algorithm for generating an initial point close to the solution. The lower-dimensional AVI is obtained by appropriately projecting the original AVI on a randomly chosen subspace. The lower-dimensional AVI is solved using standard solvers and from this solution an approximate solution to the original AVI is recovered through an inexpensive process. Our numerical experiments corroborate the theoretical results and validate that the algorithm provides a good approximation at low dimensions and substantial savings in time for an exact solution.

Wei Chen, Dayu Huang, Ankur A. Kulkarni et al.

Neuro-dynamic programming is a class of powerful techniques for approximating the solution to dynamic programming equations. In their most computationally attractive formulations, these techniques provide the approximate solution only within a prescribed finite-dimensional function class. Thus, the question that always arises is how should the function class be chosen? The goal of this paper is to propose an approach using the solutions to associated fluid and diffusion approximations. In order to illustrate this approach, the paper focuses on an application to dynamic speed scaling for power management in computer processors.