BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Venkat Anantharam

Venkat Anantharam contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computer Science and Game TheoryInformation Theorymath.ITmath.PRmath.OCecon.THCryptography and Securityeess.SYSystems and Control

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
9works
0followers
9topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

9 published item(s)

preprint2023arXiv

A Universal Low Complexity Compression Algorithm for Sparse Marked Graphs

Many modern applications involve accessing and processing graphical data, i.e. data that is naturally indexed by graphs. Examples come from internet graphs, social networks, genomics and proteomics, and other sources. The typically large size of such data motivates seeking efficient ways for its compression and decompression. The current compression methods are usually tailored to specific models, or do not provide theoretical guarantees. In this paper, we introduce a low-complexity lossless compression algorithm for sparse marked graphs, i.e. graphical data indexed by sparse graphs, which is capable of universally achieving the optimal compression rate in a precisely defined sense. In order to define universality, we employ the framework of local weak convergence, which allows one to make sense of a notion of stochastic processes for sparse graphs. Moreover, we investigate the performance of our algorithm through some experimental results on both synthetic and real-world data.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Reversible Markov decision processes and the Gaussian free field

A Markov decision problem is called reversible if the stationary controlled Markov chain is reversible under every stationary Markovian strategy. A natural application in which such problems arise is in the control of Metropolis-Hastings type dynamics. We characterize all discrete time reversible Markov decision processes with finite state and actions spaces. We show that policy iteration algorithm for finding an optimal policy can be significantly simplified Markov decision problems of this type. We also highlight the relation between the finite time evolution of the accrual of reward and the Gaussian free field associated to the controlled Markov chain.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Sequential Channel Synthesis

The channel synthesis problem has been widely investigated over the last decade. In this paper, we consider the sequential version in which the encoder and the decoder work in a sequential way. Under a mild assumption on the target joint distribution we provide a complete (single-letter) characterization of the solution for the point-to-point case, which shows that the canonical symbol-by-symbol mapping is not optimal in general, but is indeed optimal if we make some additional assumptions on the encoder and decoder. We also extend this result to the broadcast scenario and the interactive communication scenario. We provide bounds in the broadcast setting and a complete characterization of the solution under a mild condition on the target joint distribution in the interactive communication case. Our proofs are based on a Rényi entropy method.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Mechanism Design for Cumulative Prospect Theoretic Agents: A General Framework and the Revelation Principle

This paper initiates a discussion of mechanism design when the participating agents exhibit preferences that deviate from expected utility theory (EUT). In particular, we consider mechanism design for systems where the agents are modeled as having cumulative prospect theory (CPT) preferences, which is a generalization of EUT preferences. We point out some of the key modifications needed in the theory of mechanism design that arise from agents having CPT preferences and some of the shortcomings of the classical mechanism design framework. In particular, we show that the revelation principle, which has traditionally played a fundamental role in mechanism design, does not continue to hold under CPT. We develop an appropriate framework that we call mediated mechanism design which allows us to recover the revelation principle for CPT agents. We conclude with some interesting directions for future work.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Deterministic Algorithm for the Capacity of Finite-State Channels

We propose two modified versions of the classical gradient ascent method to compute the capacity of finite-state channels with Markovian inputs. For the case that the channel mutual information is strongly concave in a parameter taking values in a compact convex subset of some Euclidean space, our first algorithm proves to achieve polynomial accuracy in polynomial time and, moreover, for some special families of finite-state channels our algorithm can achieve exponential accuracy in polynomial time under some technical conditions. For the case that the channel mutual information may not be strongly concave, our second algorithm proves to be at least locally convergent.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Black-Box Strategies and Equilibrium for Games with Cumulative Prospect Theoretic Players

The betweenness property of preference relations states that a probability mixture of two lotteries should lie between them in preference. It is a weakened form of the independence property and hence satisfied in expected utility theory (EUT). Experimental violations of betweenness are well-documented and several preference theories, notably cumulative prospect theory (CPT), do not satisfy betweenness. We prove that CPT preferences satisfy betweenness if and only if they conform with EUT preferences. In game theory, lack of betweenness in the players' preference relations makes it essential to distinguish between the two interpretations of a mixed action by a player - conscious randomizations by the player and the uncertainty in the beliefs of the opponents. We elaborate on this distinction and study its implication for the definition of Nash equilibrium. This results in four different notions of equilibrium, with pure and mixed action Nash equilibrium being two of them. We dub the other two pure and mixed black-box strategy Nash equilibrium respectively. We resolve the issue of existence of such equilibria and examine how these different notions of equilibrium compare with each other.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Learning in Games with Cumulative Prospect Theoretic Preferences

We consider repeated games where the players behave according to cumulative prospect theory (CPT). We show that, when the players have calibrated strategies and behave according to CPT, the natural analog of the notion of correlated equilibrium in the CPT case, as defined by Keskin, is not enough to capture all subsequential limits of the empirical distribution of action play. We define the notion of a mediated CPT correlated equilibrium via an extension of the stage game to a so-called mediated game. We then show, along the lines of the result of Foster and Vohra about convergence to the set of correlated equilibria when the players behave according to expected utility theory that, in the CPT case, under calibrated learning the empirical distribution of action play converges to the set of all mediated CPT correlated equilibria. We also show that, in general, the set of CPT correlated equilibria is not approachable in the Blackwell approachability sense. We observe that a mediated game is a specific type of a game with communication, as introduced by Myerson, and as a consequence we get that the revelation principle does not hold under CPT.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Nash equilibrium structure of Cox process Hotelling games

We study an N-player game where a pure action of each player is to select a non-negative function on a Polish space supporting a finite diffuse measure, subject to a finite constraint on the integral of the function. This function is used to define the intensity of a Poisson point process on the Polish space. The processes are independent over the players, and the value to a player is the measure of the union of its open Voronoi cells in the superposition point process. Under randomized strategies, the process of points of a player is thus a Cox process, and the nature of competition between the players is akin to that in Hotelling competition games. We characterize when such a game admits Nash equilibria and prove that when a Nash equilibrium exists, it is unique and comprised of pure strategies that are proportional in the same proportions as the total intensities. We give examples of such games where Nash equilibria do not exist. A better understanding of the criterion for the existence of Nash equilibria remains an intriguing open problem.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Load Balancing in Hypergraphs

Consider a simple locally finite hypergraph on a countable vertex set, where each edge represents one unit of load which should be distributed among the vertices defining the edge. An allocation of load is called balanced if load cannot be moved from a vertex to another that is carrying less load. We analyze the properties of balanced allocations of load. We extend the concept of balancedness from finite hypergraphs to their local weak limits in the sense of Benjamini and Schramm (2001) and Aldous and Steele (2004). To do this, we define a notion of unimodularity for hypergraphs which could be considered an extension of unimodularity in graphs. We give a variational formula for the balanced load distribution and, in particular, we characterize it in the special case of unimodular hypergraph Galton Watson processes. Moreover, we prove the convergence of the maximum load under some conditions. Our work is an extension to hypergraphs of Anantharam and Salez (2016), which considered load balancing in graphs, and is aimed at more comprehensively resolving conjectures of Hajek (1990).

0 citations0 reviewsNo code linkedOpen access