Competitive optimality of source codes
H. Yamamoto, T. Itoh · IEEE Transactions on Information Theory · 1995
Competitively optimal coding is considered and the following is proved. (1) If the competitively optimal code exists for a given source probability p(x), then it also attains the minimum expected codeword length. (2) If the Huffman code tree for p(x) is unbalanced in probability weight, then the competitively optimal code does not exist. Furthermore, the relation between competitively optimal coding and game theory is considered.