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.
A key aspect of many resource allocation problems is the need for the resource controller to compute a function, such as the max or arg max, of the competing users metrics. Information must be exchanged between the competing users and the resource controller in order for this function to be computed. In many practical resource controllers the competing users' metrics are communicated to the resource controller, which then computes the desired extremization function. However, in this paper it is shown that information rate savings can be obtained by recognizing that controller only needs to determine the result of this extremization function. If the extremization function is to be computed losslessly, the rate savings are shown in most cases to be at most 2 bits independent of the number of competing users. Motivated by the small savings in the lossless case, simple achievable schemes for both the lossy and interactive variants of this problem are considered. It is shown that both of these approaches have the potential to realize large rate savings, especially in the case where the number of competing users is large. For the lossy variant, it is shown that the proposed simple achievable schemes are in fact close to the fundamental limit given by the rate distortion function. Efficient downlink resource allocation (e.g., subbands in OFDMA LTE) requires channel state information (e.g., subband gains) local to each user be transmitted to the base station (BS). Lossy encoding of the relevant state may result in suboptimal resource allocations by the BS, the performance cost of which may be captured by a suitable distortion measure. This problem is an indirect distributed lossy source coding problem with the function to be computed representing the optimal resource allocation, and the distortion measuring the cost of suboptimal allocations. In this paper we investigate the use of distributed scalar quantizers for lossy encoding of state, where the BS wishes to compute the index of the user with the largest gain on each subband. We prove the superiority of a heterogeneous (across users) quantizer design over the optimal homogeneous quantizer design, even though the source variables are i.i.d. For the resource allocation problem in a multiuser OFDMA system, we propose an interactive communication scheme between the base station and the users with the assumption that this system utilizes a rateless code for data transmission. We describe the problem of minimizing the overhead measured in the number of bits that must be exchanged required by the interactive scheme, and solve it with dynamic programming. We present simulation results showing the reduction of overhead information enabled by the interactive scheme relative to a straightforward one-way scheme in which each user reports its own channel quality.