VSVijay G. Subramanian

Vijay G. Subramanian

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Vijay G. Subramanian has a total of 87 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Sharing with Frictions: Limited Transfers and Costly Inspections

    by Federico Bobbio, Randall A. Berry, Michael L. Honig, Thanh Nguyen, Vijay G. Subramanian, Rakesh V. Vohra

    The radio spectrum suitable for commercial wireless services is limited. A portion of the radio spectrum has been reserved for institutions using it for non-commercial purposes such as federal agencies, defense, public safety bodies and scientific institutions. In order to operate efficiently, these incumbents need clean spectrum access. However, commercial users also want access, and granting them access may materially interfere with the existing activity of the incumbents. Conventional market based mechanisms for allocating scarce resources in this context are problematic. Allowing direct monetary transfers to and from public or scientific institutions risks distorting their non-commercial mission. Moreover, often only the incumbent knows the exact value of the interference it experiences, and, likewise, only commercial users can predict accurately the expected monetary outcome from sharing the resource. Thus, our problem is to determine the efficient allocation of resources in the presence of private information without the use of direct monetary transfers. The problem is not unique to spectrum. Other resources that governments hold in trust share the same feature. We propose a novel mechanism design formulation of the problem, characterize the optimal mechanism and describe some of its qualitative properties.

  • Open Access

    Information Compression in Dynamic Games

    by Dengwang Tang, Vijay Subramanian, Demosthenis Teneketzis

    One of the reasons why stochastic dynamic games with an underlying dynamic system are challenging is because strategic players have access to enormous amount of information which leads to the use of extremely complex strategies at equilibrium. One approach to resolve this challenge is to simplify players’ strategies by identifying appropriate compression of information maps so that the players can make decisions solely based on the compressed version of information, called the information state. Such maps allow players to implement their strategies efficiently. For finite dynamic games with asymmetric information, inspired by the notion of information state for single-agent control problems, we propose two notions of information state, namely mutually sufficient information (MSI) and unilaterally sufficient information (USI). Both these information states are obtained by applying information compression maps that are independent of the strategy profile. We show that Bayes-Nash Equilibria (BNE) and Sequential Equilibria (SE) exist when all players use MSI-based strategies. We prove that when all players employ USI-based strategies, the resulting sets of BNE and SE payoff profiles are the same as the sets of BNE and SE payoff profiles resulting when all players use full information-based strategies. We prove that when all players use USI-based strategies the resulting set of weak Perfect Bayesian Equilibrium (wPBE) payoff profiles can be a proper subset of all wPBE payoff profiles. We identify MSI and USI in specific models of dynamic games in the literature. We end by presenting an open problem: Do there exist strategy-dependent information compression maps that guarantee the existence of at least one equilibrium or maintain all equilibria that exist under perfect recall? We show, by a counterexample, that a well-known strategy-dependent information compression map used in the literature does not possess any of the properties of the strategy-independent compression maps that result in MSI or USI.

  • Open Access

    Restart Perturbations for Reversible Markov Chains: Trichotomy and Pre‐Cutoff Equivalence

    by Daniel Vial, Vijay Subramanian

    Given a reversible Markov chain on states, and another chain obtained by perturbing each row of by at most in total variation, we study the total variation distance between the two stationary distributions, . We show that for chains with cutoff, converges to 0, is asymptotically at most (with a sequence of perturbations for which convergence to this bound occurs), and converges to 1, respectively, if the product of and the mixing time of converges to 0, , and , respectively. This echoes recent results for specific random walks that exhibit cutoff, suggesting that cutoff is the key property underlying such results. Moreover, we show is maximized by restart perturbations, for which “restarts” at a random state with probability at each step. Finally, we show that pre‐cutoff is (almost) equivalent to a notion of “sensitivity to restart perturbations,” suggesting that chains with sharper convergence to stationarity are inherently less robust.


  • Open Access

    On Equivalence Between Decentralized Policy-Profile Mixtures and Behavioral Coordination Policies in Multi-Agent Systems

    by Nouman Khan, Vijay G. Subramanian

    Constrained decentralized team problem formulations are good models for many cooperative multi-agent systems. Constraints necessitate randomization when solving for optimal solutions -- our past results show that joint randomization amongst the team is necessary for (strong) Lagrangian duality to hold -- , but a better understanding of randomization still remains. For a partially observed multi-agent system with Borel hidden state and finite observations and actions, we prove the equivalence between joint mixtures of decentralized policy-profiles (both pure and behavioral) and common-information based behavioral coordination policies (also mixtures of them). This generalizes past work that shows equivalence between pure decentralized policy-profiles and pure coordination policies. The equivalence can be exploited to develop results on strong duality and number of randomizations.

  • Open Access

    Information Compression in Dynamic Games

    by Dengwang Tang, Vijay Subramanian, Demosthenis Teneketzis

    One of the reasons why stochastic dynamic games with an underlying dynamic system are challenging is since strategic players have access to enormous amount of information which leads to the use of extremely complex strategies at equilibrium. One approach to resolve this challenge is to simplify players' strategies by identifying appropriate compression of information maps so that the players can make decisions solely based on the compressed version of information, called the information state. For finite dynamic games with asymmetric information, inspired by the notion of information state for single-agent control problems, we propose two notions of information states, namely mutually sufficient information (MSI) and unilaterally sufficient information (USI). Both these information states are obtained with information compression maps independent of the strategy profile. We show that Bayes-Nash Equilibria (BNE) and Sequential Equilibria (SE) exist when all players use MSI-based strategies. We prove that when all players employ USI-based strategies the resulting sets of BNE and SE payoff profiles are the same as the sets of BNE and SE payoff profiles resulting when all players use full information-based strategies. We prove that when all players use USI-based strategies the resulting set of weak Perfect Bayesian Equilibrium (wPBE) payoff profiles can be a proper subset of all wPBE payoff profiles. We identify MSI and USI in specific models of dynamic games in the literature. We end by presenting an open problem: Do there exist strategy-dependent information compression maps that guarantee the existence of at least one equilibrium or maintain all equilibria that exist under perfect recall? We show, by a counterexample, that a well-known strategy-dependent information compression map used in the literature does not possess any of the properties of MSI or USI.

  • Open Access

    Information Compression in Dynamic Information Disclosure Games

    by Dengwang Tang, Vijay G. Subramanian

    We consider a two-player dynamic information design problem between a principal and a receiver -- a game is played between the two agents on top of a Markovian system controlled by the receiver's actions, where the principal obtains and strategically shares some information about the underlying system with the receiver in order to influence their actions. In our setting, both players have long-term objectives, and the principal sequentially commits to their strategies instead of committing at the beginning. Further, the principal cannot directly observe the system state, but at every turn they can choose randomized experiments to observe the system partially. The principal can share details about the experiments to the receiver. For our analysis we impose the truthful disclosure rule: the principal is required to truthfully announce the details and the result of each experiment to the receiver immediately after the experiment result is revealed. Based on the received information, the receiver takes an action when its their turn, with the action influencing the state of the underlying system. We show that there exist Perfect Bayesian equilibria in this game where both agents play Canonical Belief Based (CBB) strategies using a compressed version of their information, rather than full information, to choose experiments (for the principal) or actions (for the receiver). We also provide a backward inductive procedure to solve for an equilibrium in CBB strategies.

  • Rarest-First With Probabilistic-Mode-Suppression (RFwPMS)

    by Nouman Khan, Mehrdad Moharrami, Vijay G. Subramanian

    Recent studies suggested that the BitTorrent’s rarest-first (RF) protocol, owing to its work-conserving nature, can become unstable in the presence of non-persistent users. Consequently, for any provably stable protocol, many peers, at some point, have to be forced to hold off their file-download activity. In this work, we propose a tunable piece-selection policy that minimizes this (undesirable) requisite by combining the (work-conserving but not stabilizing) RF protocol with only an appropriate share of the (stabilizing but not work-conserving) mode-suppression (MS) protocol. We refer to this policy as “Rarest-First with Probabilistic Mode-Suppression” or simply RFwPMS. We study RFwPMS using a stochastic abstraction of the BitTorrent network that is general enough to capture a multi-swarm setting of non-persistent users—each swarm having its own altruistic preferences that may or may not overlap with those of other swarms. Using Lyapunov drift analysis, we show that for all kinds of inter-swarm behaviors and all arrival-rate configurations, RFwPMS is stable. Then, using the Kingman’s moment bound technique, we further show that the steady-state expected sojourn time of RFwPMS is independent of the arrival-rate in the single-swarm case (under a mild additional assumption). Finally, our simulation-based performance evaluation confirms our theoretical findings, and shows that the steady-state expected sojourn time is linear in the file-size (compared to our loose estimate of a polynomial with degree 6). Overall, an improved performance is observed in comparison to previously proposed stabilizing schemes like MS.

  • Open Access

    Learning-based Optimal Admission Control in a Single Server Queuing System

    by Asaf Cohen, Vijay G. Subramanian, Yili Zhang

    We consider a long-term average profit maximizing admission control problem in an M/M/1 queuing system with unknown service and arrival rates. With a fixed reward collected upon service completion and a cost per unit of time enforced on customers waiting in the queue, a dispatcher decides upon arrivals whether to admit the arriving customer or not based on the full history of observations of the queue-length of the system. (Naor 1969, Econometrica) showed that if all the parameters of the model are known, then it is optimal to use a static threshold policy -- admit if the queue-length is less than a predetermined threshold and otherwise not. We propose a learning-based dispatching algorithm and characterize its regret with respect to optimal dispatch policies for the full information model of Naor (1969). We show that the algorithm achieves an $O(1)$ regret when all optimal thresholds with full information are non-zero, and achieves an $O(\ln^{1+\epsilon}(N))$ regret for any specified $\epsilon>0$, in the case that an optimal threshold with full information is $0$ (i.e., an optimal policy is to reject all arrivals), where $N$ is the number of arrivals.