Look-Ahead Reasoning on Learning Platforms

Thank you for your thorough review and the valuable feedback. Please see below for our point-by-point response to your questions.

Q1. Convexity assumption
It is inevitable to establish most theoretical results with the standard convexity and smoothness assumptions. However, we note that the simulation we conducted in Section 6.2 violated the strong convexity assumption of the collective’s utility. As indicated by the experimental results, there is no qualitative inconsistency with our theoretical results. The insights gained in convex settings are often indicative of the phenomena happening under a more complex landscape.

Q2. Linearity assumption
We note that only Theorems 4 and 6 require the linearity assumption in the last step of the proof to permit a cleaner and more interpretable expression. We will rewrite the proof to expose the expression before applying the linearity assumption. For Theorem 4, for example, $\Phi$ would need to be replaced by $\Vert\nabla\_h\nabla\_\theta\mathbb{E}\_{z\sim \mathcal{D}\_{h\^*}}$ u(z, \theta) $(\mathbf{H}\^\star)\^{-1}\mathbb{E}_{z \sim \mathcal{D}\_{h\^\ast}}$ \ell(z, \theta) $\Vert$. In this form the bound still holds without the assumption.

Q3. Practical challenges of coordinating populations
We agree that coordination is an important aspect to implement collective action strategies in practice. Reported cases have successfully used forums and social media groups to coordinate such efforts; see, for example, the #DeclineNow movement on Doordash. There is also ongoing research dedicated to developing digital tools for facilitating information exchange among platform participants. See, for example, [1, 2] who develop tools for gig workers on digital platforms. All of this is to say that empirically there is some evidence of large, decentralized populations unifying to execute collective strategies.

[1] Carlos Toxtli and Saiph Savage. Designing AI Tools to Address Power Imbalances in Digital Labor Platforms, 2023. [2] Kashif Imteyaz,Claudia Flores-Saviaga, Saiph Savage. GigSense: An LLM-Infused Tool for Workers' Collective Intelligence. 2024

Q4. Complexity of strategies $h$
In the context of collective reasoning, our goal is to understand the effectiveness of a given strategy $h$ that a collective might deploy, rather than model organic human behavior based on incentives and costs. As you pointed out in your previous question, implementing and coordinating large-scale efforts can be challenging in practice. This is why simple strategies, such as simple feature manipulations, play an important role (especially since they are often implemented by people who do not have algorithmic expertise). For example, in the #DeclineNow movement on Doordash drivers on a food delivery platform coordinate to decline orders above a threshold of $7 to raise the overall pay level. The numerical threshold they picked is not necessarily optimal but very easy to communicate and implement. It is an example of a simple strategy that was effective in practice.

Thank you for the positive assessment of our work. We elaborate on your questions and comments below:

Justifying unstrategic segments in the population
Throughout, our goal is to study heterogeneous populations of agents and to contrast different reasoning strategies, including the lack of strategic thought. In the context of collective action there is ample evidence that in practice typically not all agents in a population participate in collective strategies. For example, Burrell et al. report that a strategic control action was found in 17% of the tweets they coded for their study [1], still the strategy was effective. Our goal is to model this level of heterogeneity by incorporating non-strategic users.

[1] J. Burrell, Z. Kahn, A. Jonas, D. Griffin.”When Users Control the Algorithms: Values Expressed in Practices on the Twitter Platform” ACM CHI, 2019.

What would be the implications if we were to extend this to higher levels of k reasoning for the selfish participants?

In our results we characterize the stable point in scenarios where we have heterogeneous populations, meaning both agents who act selfishly (as studied in Section 3) and agents who reason collectively. In the following we explain why considering the mixture with only a single component at $k=1$ as a representative case for selfish agents is sufficient.

At the performatively stable point the behavior of agents at different levels $k \geq 1$ is the same as the behavior of a homogeneous population with only $k=1$ agents, since the second argument in the utility in Eq. (2) is fixed. Further, by Theorem 3 we know that the interplay between the population and the model converges to a unique stable point for any instantiation of the mixture weights in Eq. (3). As a result, the stable point across varying mixtures of selfish agents, no matter what their $k$ is. We will clarify this and explain that our results apply to selfish agents more broadly.

Thank you for your thorough review. We incorporated your feedback and we will use the additional page available for the revision to include a dedicated section on limitations, discussing the points that came up in the reviews. Below we discuss your comments in order.

Q1. Computation requirement The level-k thinkers assume all other agents are level-$(k-1)$ thinkers. Hence, they need to be able to compute the moves of level-$\{k-1,k-2, \ldots, 1\}$ thinkers (in order to compute $\mathcal{D}_{k-1}(\theta)$). Further, they need to be able to compute the output of the learning algorithm. The former assumption that agents at higher levels are able to emulate agents at lower levels is standard in economic models of cognitive hierarchies, see Nagel 1995. The latter is specific to our learning setting and requires that the agents know the specifics to the learner’s objective (which is common in strategic classification).

Additional experiment in response to the comment To investigate the sensitivity to violations of this assumption we have performed an additional empirical ablation where we allow agents to only approximately solve the learning problem. In particular, we assume all agents can only perform one stochastic gradient descent step on the deployed model to evaluate the model update with learning rate of 0.01. We set up the experiment with 2 levels of agents (same as the experiment in Section 6.1). The following table reports the convergence of the model parameters as the differences between iterations $\Vert \theta_{t+1} - \theta_t \Vert$ (same as Figure 1):

We observe that convergence is preserved, and a larger proportion of higher-level agents still accelerates convergence.

Q2. How does Proposition 8 relate to Hardt et al.? We assume you refer to Section 4.1 in Hardt et al. They analyze a fixed strategy whereas our bound holds for any possible strategy that could potentially shift the model to the target state. We demonstrated that the collective’s effort to implement such a strategy (modeled by the shift needed) is inversely proportional to the size of the collective. This is not a quantity studied in prior work. However, what is similar is that the norm of the gradient at the target solution naturally emerges as a notion of suboptimality (under the base distribution) for what the collective aims to achieve.

Q3. Connection to strategic classification utility model Thanks for pointing this out. For simplicity we removed the cost term from our problem statement to be more consistent with the performative prediction formalism. To fully recover the strategic classification’s utility model of Hardt et al., one would need to extend the notation as $U(h) = \mathbb{E}\_{z\sim \mathcal{D\_0}}[u(z, h(z), \mathcal A (D_h))]$. However, this does not change the results in our paper as it acts as a regularizer that equally applies to any level of reasoning for any fixed agent. For example, in Theorem 3, the convergence still holds as long as the sensitivity of the distribution map satisfies $\epsilon \leq \frac{\gamma}{\beta}$. And for later results still hold as the envelope theorem still applies. We will clarify this point in the revised version.

Q4. Clarification on Theorem 6
Yes, the model indeed converges immediately since $h^\sharp$ is not dependent on the current model parameter. Our goal is to characterize the suboptimality due to deviating from the case $\alpha=1$. We are not sure we understand what you are suggesting - could you please clarify what you mean by a best-of-both-worlds bound?

Code
The code requires additional modules that can be found in the github repo of the paper "Performative prediction." ICML 2020. The code is runnable if the dataset (Kaggle contest: Give Me Some Credit, cs-training.csv) and the modules (data_prep.py, optimization.py, strategic.py) are placed in the root folder of the notebook. We will work on the documentation and release our polished code publicly alongside the revised version.

Alignment condition
As long as the loss function and the agents’ utility functions are available, the gradient alignment expressions are in principle computable. The Hessian of utilities in differential games is indeed an important indicator of the “alignment” of the player’s objectives (see Section 2, Balduzzi et al., “The Mechanics of n-Player Differentiable Games”, ICML’18). It is inevitable to utilise the second-order information in characterising the exact alignment of the players’ objectives. In practice, it is possible for practitioners to infer the adversarialness of the learner and the collective through qualitative analysis without direct computations. For example, in the simulations, we measure the alignments using the importance of features, and the empirical results also align with our theoretical observations. However in general we see the main value of our analysis in highlighting the role of steering in collective reasoning (which is absent from strategic classification) and offering the first formal characterization of the tradeoff involved in strategizing collectively against a risk minimizing learner.

Thank you for the detailed response, and for the additional experiments! My concerns are addressed, and I'm adjusting my score accordingly. Regarding Q4, your clarification resolved my confusion - after going through the formal statements in Section 5.1 again, I think the question arose from a misunderstanding. Your explanation of the intent was very helpful, and may be worth emphasizing.

Thank you for your feedback. In the following we address your comments in sequence. Please let us know if anything requires further clarification.

Q1. Stackelberg structure
In the context of collective reasoning (Section 4), the actions of the learner and the population are defined as follows:

The learner is assumed to be risk minimizing (recall Assumption 1): observing $\mathcal D$, they choose $\mathcal{A}(\mathcal{D}) = \arg\min\_{\theta \in \Theta} \mathbb{E}\_{z \sim \mathcal{D}}[\ell(z; \theta)]$. In words, the learner best-responds to the population; their utility corresponds to the negative expected loss, and their action to a choice of parameters. The collective in turn finds a strategy that maximizes their collective utility $U$ by planning through the learner’s response. This optimal strategy is defined in L176 as $h^\sharp = \arg\max_h \mathbb{E}_{z \sim \mathcal{D}_h}[u(z, \mathcal{A}(\mathcal{D}_h) ]$.

Together, this structure corresponds to a two-player Stackelberg game where the collective acts as the leader and the learner as the follower. Note that the agents in the population are not necessarily optimizing their individual utilities. Like in traditional cases of collective action, participating in a collective is not always individually rational, but individuals may opt in for altruistic reasons.

In later sections we consider deviations from this model where the strategy space of the collective only permits the manipulation of a subset of the population ($\alpha<1$). This corresponds to some agents prioritizing their individual utilities, and others acting altruistically in the interest of the collective. We hope this clarifies your question about the game-theoretic formalization of collective reasoning.

Do individuals benefit from model updates? Agents’ utilities are not guaranteed to be monotone over time and even at stability a benefit is not guaranteed at the individual level. As explained above, our goal is to study agent behavior that is driven by collective goals rather than individual incentives. We demonstrate how a group of agents can improve their aggregate utility through coordination, more so than if all of them perform individually rational actions. The reason is that collectives can ‘steer’ the learner, rather than just their own data.

Q2. Participation dynamics
This question relates to an important conceptual departure between our work and strategic classification. We study agents that purposefully optimize the collective utility. This behavior does not arise from behavior that is rational according to an individual utility. Taking this collective perspective, our results show when the collective is better off coordinating, rather than acting myopically. In the present work, we do not study the dynamics by which collectives form, or mechanisms to incentivize participation. Understanding the role of heterogeneous incentives in the context of algorithmic collective action is an interesting and, to the best of our knowledge, an unexplored question.

Q3. Example
One concrete example of level-k strategies is demonstrated in the simulation of Section 6.1. It is an extension of the classical strategic classification setting with a quadratic cost and linear utility. Here, agents at level $k$ modify their strategic features $x_S$ assuming the other agents act according to level $(k-1)$. The actions of agents can be written in closed form as $x\_S^k = x_S - \epsilon \cdot \theta^{k-1}\_S$, where $\theta^k = \arg\min_\theta \sum_{i} \ell(x^k_i, y_i, \theta)$. In the following we use this example to numerically compare the utilities of level-1 and level-2 agents with the same initial features $x = (0, \ldots, 0)$. We report averages over 10 runs.

We observe that the utility gap decreases across time steps, as the procedure converges towards stability. However, there is no evidence on the monotonicity of utilities against their cognitive levels. We will include an extended version of this numerical analysis in the paper. Thank you for the suggestion!

Q4. Assumptions:

We discuss the three assumptions individually:

• Strong concavity. The simulation in Section 6.2 is an example when the utility is not strongly concave, but the results still qualitatively align with our theoretical findings.
• Linearity. The condition is only used in Theorem 4 and 6 in the last step of the proof to permit a cleaner and more interpretable bound. A “less clean version” of the result does not require this assumption and preserves the qualitative take-aways. For Theorem 4, for example, $\Phi$ would need to be replaced by $\Vert\nabla\_h\nabla\_\theta\mathbb{E}\_{z\sim \mathcal{D}\_{h\^*}}$ u(z, \theta) $(\mathbf{H}\^\star)\^{-1}\mathbb{E}_{z \sim \mathcal{D}\_{h\^\ast}}$ \ell(z, \theta) $\Vert$. In general, for simple densities the assumption can always be made possible by reparameterising the density functions which allows to differentiate through the individual terms.
• Agent behavior The analysis of the mixture distribution (Equation 3) is our attempt to understand heterogeneous populations and deviate from the typical model of a homogeneous population with a fixed level of reasoning. One insight we have is that convergence to stability is achieved for varying proportions of agents at different levels of cognitive hierarchy. We find that convergence is robust to these deviations.

Q5. Experiments
Thank you for the suggestions, we are happy to extend our experimental section along the dimensions you mentioned. We added error bars (as one standard deviation) for all plots in the paper. See below for the numbers.

Figure 1:

Figure 2:

In terms of convergence: note that Figure 1 (in the paper) illustrates convergence for the experiment of Section 6.1. For the experiment conducted in Section 6.2, for the inference of the collective strategy, convergence is achieved after 200 steps for all cases. We will give a more comprehensive report on these quantitative metrics in the revised version.

Regarding real-world datasets, we would like to emphasize that the credit scoring simulator is based on real data (data collected from 250,000 borrowers including historical information about the individual and information on whether they defaulted on a loan). More generally, in related literature, there are few experiments on real-world data since that would require obtaining samples under different model deployments. If the reviewer has a suggested dataset we could look at, we would be happy to incorporate it.

In the response of Q4: .... For theorem 4, for example, $\Phi$ would need to be replaced by $\Vert\nabla\_h\nabla\_\theta\mathbb{E}\_{z\sim \mathcal{D}\_{h^\ast}}$ u(z, \theta) $(\mathbf{H}^\star)\^{-1}\nabla\_\theta\mathbb{E}\_{z \sim \mathcal{D}_{h^\ast}}$ \ell(z, \theta) $\Vert$.... where the last term was missing a "$\nabla\_\theta$". Apologies for the typo, the openreview platform does not render LaTeX equations very well.