The Index Coding problem: A game-theoretical perspective

The Index Coding problem has recently attracted a significant interest from the research community. In this problem, a server needs to deliver a set of packets to a group of wireless clients over a noiseless broadcast channel. Each client requests a subset of packets and has another subset given to it as side information. The objective is to satisfy the demands of all clients with the minimum number of transmissions. In this paper, we study the Index Coding problem from the game-theoretic perspective. We assume that each client is selfish and has a hidden private value for each packet it requests. The objective of the server is to maximize the value of social welfare that captures the trade-off between values of the transmitted packets and the transmission cost incurred by the server. The transmission process is decided through an auction in which the clients are required to submit bids to the server. Our goal is to design a truthful auction scheme that provides an incentive for each client to bid the true value of the packets and maximizes the value of the social welfare. The key challenge in this context is to determine the encoding functions of the transmitted packets. Since finding an optimal encoding function is an NP-hard problem, we propose efficient algorithms that identify the encoding functions as well as a payment scheme that provide an approximate solution and guarantee truthfulness.