BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Ankur A. Kulkarni

Ankur A. Kulkarni appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.OCComputer Science and Game TheoryInformation Theorymath.ITSystems and Controleess.SYMachine Learningmath.CODiscrete Mathematicsmath.NT

Catalog footprint

What is connected

11works
10topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2022arXiv

Refinement of the Equilibrium of Public Goods Games over Networks: Efficiency and Effort of Specialized Equilibria

Recently Bramoulle and Kranton presented a model for the provision of public goods over a network and showed the existence of a class of Nash equilibria called specialized equilibria wherein some agents exert maximum effort while other agents free ride. We examine the efficiency, effort and cost of specialized equilibria in comparison to other equilibria. Our main results show that the welfare of a particular specialized equilibrium approaches the maximum welfare amongst all equilibria as the concavity of the benefit function tends to unity. For forest networks a similar result also holds as the concavity approaches zero. Moreover, without any such concavity conditions, there exists for any network a specialized equilibrium that requires the maximum weighted effort amongst all equilibria. When the network is a forest, a specialized equilibrium also incurs the minimum total cost amongst all equilibria. For well-covered forest networks we show that all welfare maximizing equilibria are specialized and all equilibria incur the same total cost. Thus we argue that specialized equilibria may be considered as a refinement of the equilibrium of the public goods game. We show several results on the structure and efficiency of equilibria that highlight the role of dependants in the network.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Shannon meets Myerson: Information Extraction from a Strategic Sender

We study a setting where a receiver must design a questionnaire to recover a sequence of symbols known to strategic sender, whose utility may not be incentive compatible. We allow the receiver the possibility of selecting the alternatives presented in the questionnaire, and thereby linking decisions across the components of the sequence. We show that, despite the strategic sender and the noise in the channel, the receiver can recover exponentially many sequences, but also that exponentially many sequences are unrecoverable even by the best strategy. We define the growth rate of the number of recovered sequences as the information extraction capacity. A generalization of the Shannon capacity, it characterizes the optimal amount of communication resources required. We derive bounds leading to an exact evaluation of the information extraction capacity in many cases. Our results form the building blocks of a novel, noncooperative regime of communication involving a strategic sender.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Duopolistic platform competition for revenue and throughput

We consider two competing platforms operating in a two-sided market and offering identical services to their customers at potentially different prices. The objective of each platform is to maximize its throughput or revenue by suitably pricing its services. We assume that customers have a preference or loyalty to the platforms while the workers freelance for the two platforms. Assuming that the resulting interaction between the users is such that their aggregate utility is maximized, we show that for each value of the loyalty, there exists a pure strategy Nash equilibrium for both the throughput and revenue competition game and characterize it.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Strategy-Proof Spectrum Allocation among Multiple Operators for Demand Varying Wireless Networks

To address the exponentially increasing data rate demands of end users, necessitates efficient spectrum allocation among co-existing operators in licensed and unlicensed spectrum bands to cater to the temporal and spatial variations of traffic in the wireless network. In this paper, we address the spectrum allocation problem among non-cooperative operators via auctions. The classical Vickrey-Clarke-Groves (VCG) approach provides the framework for a strategy-proof and social welfare maximizing auction at high computational complexity, which makes it infeasible for practical implementation. We propose sealed bid auction mechanisms for spectrum allocation which are computationally tractable and hence applicable for allocating spectrum by performing auctions in short durations as per the dynamic load variations of the network. We establish that the proposed algorithm is strategy-proof for uniform demand. Furthermore, for non-uniform demand we propose an algorithm that satisfies weak strategy-proofness. We also consider non-linear increase in the marginal valuations with demand. Simulation results are presented to exhibit the performance comparison of the proposed algorithms with VCG and other existing mechanisms.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

New Results on the Existence of Open Loop Nash Equilibria in Discrete Time Dynamic Games

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Dimensionality Reduction of Affine Variational Inequalities Using Random Projections

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

An Existence Result for Hierarchical Stackelberg v/s Stackelberg Games

In Stackelberg v/s Stackelberg games a collection of leaders compete in a Nash game constrained by the equilibrium conditions of another Nash game amongst the followers. The resulting equilibrium problems are plagued by the nonuniqueness of follower equilibria and nonconvexity of leader problems whereby the problem of providing sufficient conditions for existence of global or even local equilibria remains largely open. Indeed available existence statements are restrictive and model specific. In this paper, we present what is possibly the first general existence result for equilibria for this class of games. Importantly, we impose no single-valuedness assumption on the equilibrium of the follower-level game. Specifically, under the assumption that the objectives of the leaders admit a quasi-potential function, a concept we introduce in this paper, the global and local minimizers of a suitably defined optimization problem are shown to be the global and local equilibria of the game. In effect existence of equilibria can be guaranteed by the solvability of an optimization problem, which holds under mild and verifiable conditions. We motivate quasi- potential games through an application in communication networks.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

An Optimizer's Approach to Stochastic Control Problems with Nonclassical Information Structures

We present an optimization-based approach to stochastic control problems with nonclassical information structures. We cast these problems equivalently as optimization prob- lems on joint distributions. The resulting problems are necessarily nonconvex. Our approach to solving them is through convex relaxation. We solve the instance solved by Bansal and Basar with a particular application of this approach that uses the data processing inequality for constructing the convex relaxation. Using certain f-divergences, we obtain a new, larger set of inverse optimal cost functions for such problems. Insights are obtained on the relation between the structure of cost functions and of convex relaxations for inverse optimal control.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Approximate dynamic programming using fluid and diffusion approximations with applications to power management

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Non-asymptotic Upper Bounds for Deletion Correcting Codes

Explicit non-asymptotic upper bounds on the sizes of multiple-deletion correcting codes are presented. In particular, the largest single-deletion correcting code for $q$-ary alphabet and string length $n$ is shown to be of size at most $\frac{q^n-q}{(q-1)(n-1)}$. An improved bound on the asymptotic rate function is obtained as a corollary. Upper bounds are also derived on sizes of codes for a constrained source that does not necessarily comprise of all strings of a particular length, and this idea is demonstrated by application to sets of run-length limited strings. The problem of finding the largest deletion correcting code is modeled as a matching problem on a hypergraph. This problem is formulated as an integer linear program. The upper bound is obtained by the construction of a feasible point for the dual of the linear programming relaxation of this integer linear program. The non-asymptotic bounds derived imply the known asymptotic bounds of Levenshtein and Tenengolts and improve on known non-asymptotic bounds. Numerical results support the conjecture that in the binary case, the Varshamov-Tenengolts codes are the largest single-deletion correcting codes.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Two Approaches to the Construction of Deletion Correcting Codes: Weight Partitioning and Optimal Colorings

We consider the problem of constructing deletion correcting codes over a binary alphabet and take a graph theoretic view. An $n$-bit $s$-deletion correcting code is an independent set in a particular graph. We propose constructing such a code by taking the union of many constant Hamming weight codes. This results in codes that have additional structure. Searching for codes in constant Hamming weight induced subgraphs is computationally easier than searching the original graph. We prove a lower bound on size of a codebook constructed this way for any number of deletions and show that it is only a small factor below the corresponding lower bound on unrestricted codes. In the single deletion case, we find optimal colorings of the constant Hamming weight induced subgraphs. We show that the resulting code is asymptotically optimal. We discuss the relationship between codes and colorings and observe that the VT codes are optimal in a coloring sense. We prove a new lower bound on the chromatic number of the deletion channel graphs. Colorings of the deletion channel graphs that match this bound do not necessarily produce asymptotically optimal codes.

0 citations0 reviewsNo code linkedOpen access