That's why you should include the size of the decompressor (AKA using a self-extracting archive). That's what the Hutter Prize does, for example http://prize.hutter1.net

The encodings in this article are self-extracting archives; although they don't use a bloated, arbitrary format like e.g. x86_64 Linux ELF executables. Instead they use Binary Lambda Calculus, which has a variety of interpreters (the smallest being 206 bits, written in BLC itself)