In many resource allocation problems, a centralized controller needs to award some resource to a user selected from a collection of distributed users with the goal of maximizing the utility the user would receive from the resource. This can be modeled as the controller computing an extremum of the distributed users’ utilities. The overhead rate necessary to enable the controller to reproduce the users’ local state can be prohibitively high. An approach to reduce this overhead is interactive communication wherein rate savings are achieved by tolerating an increase in delay. In this paper, we consider the design of a simple achievable scheme based on successive refinements of scalar quantization at each user. The optimal quantization policy is computed via a dynamic program and we demonstrate that tolerating a small increase in delay can yield significant rate savings. We then consider two simpler quantization policies to investigate the scaling properties of the rate-delay tradeoffs. Using a combination of these simpler policies, the performance of the optimal policy can be closely approximated with lower computational costs.
is a scheme that allows message passing over multiple rounds. At each round, the communicating parties are allowed to send messages based on what they have received in previous rounds as well as their local source observation @cite_30 . The interactive communication literature is roughly divided into two categories: communication complexity and interactive information theory.
@cite_30
2074493852
Let (X_ i , Y_ i ), i= 1,2 , be a sequence of independent, identically distributed bivariate random variables and consider the following communication situation. The X component of the process is observed at some location, say A , while the Y component is observed at a different location, say B . The X(Y) component of the process has to be reproduced at location B(A) . It is desired to find the amount of information that should be exchanged between the two locations, so that the distortions incurred will not exceed some predetermined tolerance. A "single-letter characterization" of a certain region **** ^ K R ^ 4 of rates and distortions is given. This region contains (all, and only) the achievable rates and distortions for the special case where block coding is used and the information is conveyed through a one-way link that can switch direction only K times per block.