Strategic Representation

Our formalization of strategic representation shares a deep connection to strategic classification (Hardt et al., 2016). Strategic representation and strategic classification share an underlying structure (a leading learning player who must take into account a strategic responder), but there are important differences. The first is conceptual: in our setting, roles are reversed—it is users who learn (and not the system), and the system strategically responds (and not users). This allows us to pursue questions regarding the susceptibility of users to manipulation, with different emphases and goals, while maintaining the ‘language’ of strategic classification.

The second difference is substantive: we consider inputs that are sets (rather than continuous vectors), and manipulations that hide information (rather than alter it). Technically, switching to discrete inputs can be done by utilizing the cost function to enforce truthfulness constraints as a ‘hard’ penalty on modifications. But this change is not cosmetic: since the system behaves strategically by optimizing over subsets, learning must account for set-relations between different objects in input space; this transforms the problem to one of learning set functions.²²2This is a subtle point: Since sets can be expressed as binary membership vectors, it is technically possible to use conventional vector-based approaches to learn $h$. Nonetheless, these approaches cannot account for strategic behavior; this is since $\phi$ implements a set operation, which is ill-defined for continuous vector inputs. From a modeling perspective, subsets make our work compatible with classic attribute-based consumer decision theory (Lancaster, 1966).

Overall, we view the close connection to strategic classification as a strength of our formalization, showing that the framework of strategic classification is useful far beyond what was previously considered; and also that a fairly mild variation can lead to a completely different learning problem, with distinct algorithmic and statistical challenges.

In our setup, a user is faced with a stream of items, and must choose which of these to consume. Items are discrete, with each item $x\in{}\mathcal{X}\subseteq 2^{E}$ described by a subset of ground attributes, $E$, where $|E|=q$. We assume all feasible items have at most $n$ attributes, $|x|\leq n$. The value of items for the user are encoded by a value function, $v:{}\mathcal{X}\rightarrow\mathbb{R}$. We say an item $x$ is worthwhile to the user if it has positive value, $v(x)>0$, and use $y=Y(x)=\operatorname{sign}(v(x))$ to denote worthwhileness, i.e., $y=1$ if $x$ is worthwhile, and $y=-1$ if it is not. Items are presented to the user as samples drawn i.i.d. from some unknown distribution $D$ over ${}\mathcal{X}$, and for each item, the user must choose whether to consume it (e.g., click, buy, watch) or not.

We assume that the user makes choices regarding items by committing at the onset to a choice function $h$ that governs her choice behavior. In principle, the user is free to chose $h$ from some predefined function class $H$; learning will consider finding a good $h\in H$, but the implications of the choice of $H$ itself will play a central role in our analysis. Ideally, the user would like to choose items if and only if they are worthwhile to her; practically, her goal is to find an $h$ for which this holds with large probability over $D$. For this, the user can make use of her knowledge regarding items she has already consumed, and therefore also knows their value; we model this as providing the user access to a labeled sample set $S=\{(x_{i},y_{i})\}_{i=1}^{m}$ where $x_{i}\sim D$ and $y_{i}=\operatorname{sign}(v(x_{i}))$, which she can use for learning $h$.

Strategic representations. The difficulty in learning $h$ is that user choices at test time must rely only on item representations, denoted $z\in\mathcal{Z}$, rather than on full item descriptions. Thus, learning considers choice functions that operate on representations, $h:\mathcal{Z}\rightarrow\{\pm 1\}$; the challenge lies in that while choices must be made on the basis of representations $z$, item values are derived from their full descriptions $x$—which representations describe only partially.

The crucial aspect of our setup is that representations are not arbitrary; rather, representations are controlled by the system, which can choose them strategically to promote its own goals. We model the system as acting through a representation mapping, ${\phi}:{}\mathcal{X}\rightarrow\mathcal{Z}$, which operates independently on any $x$, and can be determined in response to the user’s choice of $h$. This mimics a setting in which a fast-acting system can infer and quickly respond to a user’s (relatively fixed) choice patterns.

We assume the system’s goal is to choose a ${\phi}_{h}$ that maximizes expected user engagement:

Nonetheless, representations cannot be arbitrary, and we require ${\phi}_{h}$ to satisfy two properties. First, chosen representations must be truthful, meaning that $z\subseteq x$ for all $x$. Second, representations are subject to cardinality constraints, $k_{1}\leq|z|\leq k_{2}$ for some predetermined $k_{1},k_{2}\in\mathbb{N}$. We will henceforth use $\mathcal{Z}$ to mean representations of feasible cardinality. Both requirements stem from realistic considerations: A nontruthful system which intentionally distorts item information is unlikely to be commercially successful in the long run; intuitively, truthfulness gives users some hope of resilience to manipulation. For $k_{1},k_{2}$, we think of these as exogenous parameters of the environment, arising naturally due to physical restrictions (e.g., screen size) or cognitive considerations (e.g., information processing capacity); if $k_{2}<n$, we say representations are lossy.

Under these constraints, the system can optimize Eq. (1) by choosing representations via the best-response mapping:

Eq. (2) is a best-response since it maximizes Eq. (1) for any given $h$: for every $x$, ${\phi}_{h}$ chooses a feasible $z\subseteq x$ that triggers a positive choice event, $h(z)=1$—if such a $z$ exists. In this way, $k_{1},k_{2}$ control how much leeway the system has in revealing only partial truths; as we will show, both parameters play a key role in determining outcomes for both system and user. From now on we overload notation and by ${\phi}_{h}(x)$ refer to this best-response mapping.

Learning objective. Given function class $H$ and a labeled sample set $S$, the user aims to find a choice function $h\in H$ that correctly identifies worthwhile items given their representation, and in a way that is robust to strategic system manipulation. The user’s objective is therefore to maximize:

where ${\phi}_{h}$ is the best-response mapping in Eq. (2).

Our main focus throughout the paper will be on users that learn $h$ by optimizing Eq. (3). But to understand the potential benefit of learning, we also analyze ‘simpler’ types of user behavior. Overall, we study three user types, varying in their sophistication and the amount of effort they invest in choosing $h$. These include:

• •

  The naïve user: Acts under the (false) belief that representations are chosen in her own best interest. This user type truthfully reports her preferences to the system by setting $h=v$ as her choice function.³³3Note that while $h$ takes values in ${}\mathcal{X}$, $v$ takes values in ${}\mathcal{X}$. Nonetheless, truthfulness implies that $\mathcal{Z}\subseteq{}\mathcal{X}$, and so $v$ is well-defined as a choice function over $\mathcal{Z}$.

• •

  The agnostic user: Makes no assumptions about the system. This user employs a simple strategy that relies on basic data statistics which provides minimal but robust guarantees regarding her payoff.

• •

  The strategic user: Knows that the system is strategic, and anticipates it to best-respond. This user is willing to invest effort (in terms of data and compute) in learning a choice function $h$ that maximizes her payoff by accounting for the system’s strategic behavior.

Our primary goal is to study the balance of power between users (that choose) and the system (which represents). In particular, we will be interested in exploring the tradeoff between a user’s effort and her susceptibility to manipulation.

Before proceeding, we give an equivalent characterization of strategic representation as a game. Our setting can be compactly described as a single-step Stackelberg game: the first player is User, which observes samples $S=\{(x_{i},y_{i})\}_{i=1}^{m}$, and commits to a choice function $h:\mathcal{Z}\rightarrow\{\pm 1\}$; the second player is System, which given $h$, chooses a truthful $\phi_{h}:{}\mathcal{X}\rightarrow\mathcal{Z}$ (note how $\phi_{h}$ depends on $h$). The payoffs are:

Note that payoffs differ only in that User seeks correct choices, whereas System benefits from positive choices. This reveals a clear connection to strategic classification, in which System, who plays first, is interested in accurate predictions, and for this it can learn a classifier; and User, who plays second, can manipulate individual inputs (at some cost) to obtain positive predictions. Thus, strategic representation can be viewed as a variation on strategic classification, but with roles ‘reversed’. Nonetheless, and despite these structural similarities, strategic representation bears key differences: items are discrete (rather than continuous), manipulations are subject to ‘hard’ set constraints (rather than ‘soft’, continuous costs), and learning regards set functions (rather than vector functions). These differences lead to distinct questions and unique challenges in learning.

Ideally, a learning algorithm should permit flexibility in choosing the complexity of the class of functions it learns (e.g., the degree of a polynomial kernel, the number of layers in a neural network), as this provides means to trade-off running time with performance and to reduce overfitting. In this section we propose a hierarchy of set-function complexity classes that is appropriate for our problem.

Denote by $\Gamma_{k}(z)$ all subsets of $z$ having size at most $k$:

We start by defining $k$-order functions over the representation space. These functions are completely determined by weights placed on subsets of size at most $k$.

Not all functions $h(z)$ can necessarily be expressed as a $k$-order function (for some $k$); nonetheless, in the context of optimizing Eq. (7), we show that working with $k$-order functions is sufficiently general, since any set function $h$ can be linked to a matching $k$-order function $h^{\prime}$ (for some $k\leq k_{2}$) through how it operates on strategic inputs.

A binary weighted $k$-order $h$ determines a family of $k$-size subsets, described by having weights as $a_{+}$, such that for any $z\in\mathcal{Z}$ with $|z|\geq k$, $h(z)=1$ if and only if $z$ contains a subset from the family (for $z$ with $|z|<k$, $h(z)=-1$ always). This is made precise using the notion of lifted functions in Lem. A.4 in Appx. A.2. Next, denote:

The classes $\{H_{k}\}_{k}$ will serve as complexity classes for our learning algorithm; the user provides $k$ as input, and Alg outputs an ${\hat{h}}\in H_{k}$ that minimizes the empirical loss⁴⁴4Assuming the empirical error is zero.. As we will show, using $k$ as a complexity measure provides the user direct control over the tradeoff between estimation and approximation error, as well as over the running time.

Note that $H_{n}$ includes all binary-weighted set functions, but since representations are of size at most $k_{2}$, it suffices to consider only $k\leq k_{2}$. Importantly, $k$ can be set lower than $k_{1}$; for example, $H_{1}$ is the class of threshold modular functions, and $H_{2}$ is the class of threshold pairwise functions. The functions we consider are parameterized by their weights, $\bm{w}$, and so any $k$-order function has at most $|\bm{w}|=\sum_{i=0}^{k}{q\choose i}$ weights. In this sense, the choice of $k$ is highly meaningful. Now that we have defined our complexity classes, we turn to discussing how they can be optimized over.

The simple structure of functions in $H_{k}$ makes them good candidates for optimization. But the main difficulty in optimizing the empirical error in Eq. (7) is that the choice of $h$ does not only determine the error, but also determines the inputs on which errors are measured (indirectly through the dependence of ${\phi}_{h}$ on $h$). To cope with this challenge, our approach is to work with induced functions that already have the system’s strategic response encoded within, which will prove useful for learning. Additionally, as they operate directly on $x$ (and not $z$), they can easily be compared with $v$, which will become important in Sec. 5.

The induced class $F_{H}$ includes for every $h\in H$ a corresponding function that already has ${\phi}_{h}$ integrated in it. We use $F_{k}=F_{H_{k}}$ to denote the induced class of $H_{k}$. For every $h$, we denote its induced function by $f_{h}$. Whereas $h$ functions operate on $z$, induced functions operate directly on $x$, with each $f_{h}$ accounting internally for how the system strategic responds to $h$ on each $x$.

Our next theorem provides a key structural result: induced functions inherit the weights of their $k$-order counterparts.

Thm. 4.6 is the main pillar on which our algorithm stands: it allows us to construct $h$ by querying the loss directly—i.e., without explicitly computing ${\phi}_{h}$—by working with the induced $f_{h}$; this is since:

Thus, through their shared weights, induced functions serve as a bridge between what we optimize, and how.

We now present our learning algorithm, Alg. The algorithm is exact: it takes as input a training set $S$ and a parameter $k$, and returns an $h\in H_{k}$ that minimizes the empirical loss (Eq. (7)). Correctness holds under the realizabilility condition $Y\in F_{k}$, i.e., $Y$ is the induced function of some $h\in H_{k}$.⁵⁵5Note that even for standard linear binary classification, finding an empirical minimizer of the $0/1$ in the agnostic (i.e., non-realizable) case is NP-hard (Shalev-Shwartz and Ben-David, 2014).

The algorithm constructs $h$ by sequentially computing its weights, $\bm{w}=\{w(z)\}_{|z|\leq k}$. As per Def. 4.3, only $w(z)$ for $z$ with $|z|=k$ must be learned; hence, weights are sparse, in the sense that only a small subset of them are assigned $a_{+}$, while the rest are $a_{-}$. Weights can be implemented as a hash table, where $w(z)=a_{+}$ if $z$ is in the table, and $w(z)=a_{-}$ if it is not. Our next result establishes the correctness of Alg. The proof leverages a property that characterizes the existence of an $h\in H_{k}$ having zero empirical error (see Lem. E.1). The proof of Lem. E.1 uses Thm. 4.6, which enables the loss to be directly computed for the induced functions using the shared weight structure.

This runtime is made possible due to several key factors: (i) only $k$-sized weights need to be learned, (ii) all weights are binary-valued, and (iii) loss queries are efficient in induced space. Nonetheless, when $n$ and $k$ are large, runtime may be significant, and so $k$ must be chosen with care. Fortunately, our results in Sec. 5.1.1 give encouraging evidence that learning with small $k$—even $k=1$, for which runtime is $O((mn)^{2})$—is quite powerful (assuming $Y$ is realizable).

In the analysis, the $m{n\choose k}$ is made possible only since weights are sparse, and since Alg operates on a finite sample set of size $m$. Alternatively, if $m$ is large, then this can be replaced with ${q\choose k}$. This turns out to be necessary; in Appx. A.3 we show that, in the limit, ${q\choose k}$ is a lower bound.

We begin by studying the effects of $k$ on user payoff. Recall that users aim to minimize the expected error (Eq. (6)):

but instead minimize the empirical error (Eq. (7)). For reasoning about the expected error of the learned choice function ${\hat{h}}\in H_{k}$, a common approach is to decompose it into two error types—approximation and estimation:

Approximation error describes the lowest error obtainable by functions in $H_{k}$; this measures the ‘expressivity’ of $H_{k}$, and is independent of ${\hat{h}}$. For approximation error, we define a matching complexity structure for value functions $v$, and give several results relating the choice of $k$ and the complexity of $v$. Estimation error describes how far the learned ${\hat{h}}$ is from the optimal $h^{*}\in H_{k}$, and depends on the data size, $m$. Here we give a generalization bound based on VC analysis.

The system’s expressive power derives from its flexibility in choosing representations $z$ for items $x$. Since $k_{1},k_{2}$ determine which representations are feasible, they directly control the system’s power to manipulate; and while the system itself may not have direct control over $k_{1},k_{2}$ (i.e., if they are set by exogenous factors like screen size), their values certainly affect the system’s ability to optimize engagement. Our next result is therefore unintuitive: for system, a smaller $k_{2}$ is better (in the worst case), even though it reduces the set of feasible representations. This result is obtained indirectly, by considering the effect of $k_{2}$ on the user’s choice of $k$.

Proof in Appx. F. For $k_{1}$, it turns out that against strategic users—it is inconsequential. This is since payoff to the strategic user is derived entirely from $k$, which is upper-bounded by $k_{2}$, but can be set lower than $k_{1}$. This invariance is derived immediately from how functions in $H_{k}$ are defined, namely that $w(z)=a_{-}$ for all $z$ with $|z|<k$ (Def. 4.3). This, however, holds when the strategic user chooses to learn over $H_{k}$ for some $k$. Consider, alternatively, a strategic user that decides to learn subadditive functions instead. In this case, Thm. 5.8 shows that $k_{1}$ determines the users ‘effective’ $k$; the smaller $k_{1}$, the smaller the subset of subadditive functions that can be learned. Hence, for user, smaller $k_{1}$ means worse approximation error. This becomes even more pronounced when facing a naïve user; for her, a lower $k_{1}$ means that system now has a large set of representations to choose from; if even one of them has $v(z)=1$, the system can exploit this to increase its gains. In this sense, as $k_{1}$ decreases, payoff to the system (weakly) improves.