Description
Combinatorics Seminar.
Speaker: Anuj Vora.
Affiliation: Systems and Control Dept., IIT Bombay.
Date and Time: Wednesday 12 February, 11:00 am - 12:30 pm.
Venue: Room 114, Department of Mathematics.
Title: Zero Error Strategic Communication.
Abstract: We consider a setting between a sender and a receiver, where the
receiver tries to exactly recover a source sequence privately known to the
sender. However, unlike the usual setting of communication, the sender
here aims to maximize its utility and may have an incentive to lie about
its true information. We show that the maximum number of sequences that
can be recovered by the receiver grows exponentially and is given by the
largest independent set of a graph defined on sequences. We then define a
notion of the strategic capacity of a graph and show that it is lower
bounded by the independence number of a suitably defined graph on the
alphabet. Moreover, the Shannon capacity of the graph is an upper bound on
the capacity. This talk will briefly discuss the Shannon's zero-error
capacity problem. We then proceed to derive bounds on the strategic
capacity and give exact values for perfect graphs. If time permits, we
will also discuss the case where the receiver aims for asymptotically
vanishing probability of error.