Strategic Representation
Humans have come to rely on machines for reducing excessive information to
manageable representations. But this reliance can be abused -- strategic
machines might craft representations that manipulate their users. How can a
user make good choices based on strategic representations? We formalize this as
a learning problem, and pursue algorithms for decision-making that are robust
to manipulation. In our main setting of interest, the system represents
attributes of an item to the user, who then decides whether or not to consume.
We model this interaction through the lens of strategic classification (Hardt
et al. 2016), reversed: the user, who learns, plays first; and the system,
which responds, plays second. The system must respond with representations that
reveal `nothing but the truth' but need not reveal the entire truth. Thus, the
user faces the problem of learning set functions under strategic subset
selection, which presents distinct algorithmic and statistical challenges. Our
main result is a learning algorithm that minimizes error despite strategic
representations, and our theoretical analysis sheds light on the trade-off
between learning effort and susceptibility to manipulation.