A Market for Accuracy: Classification Under Competition

Thank you for the insightful feedback! We are pleased that you appreciated the soundness of our results and found the empirical results to complement them nicely. We would like to address the questions laid forth in your review, and hopefully alleviate some concerns:

”Best-response classification may be impractical in real-world settings since ML providers typically lack access to competitors’ predictions”
Indeed, our analysis relies on the simplifying assumption that players have complete knowledge of $\\kappa_{-i}$, the number of other correct firms per $x$. This, however, need not be taken to imply that players share such information. Instead, we view this as simplifying a process in which each player has access to (some) information regarding competition. For example, there are markets where firms are likely to have a good sense of which user groups the other firms excel on or target. Another example are cases where a firm performs market research and obtains exact information on a subset of users. A third example is firms having coarse information, such as knowing whether users subscribed to a different provider.
To investigate this idea, we have added an additional experiment on partial and coarse information, in which firms have inexact estimates $\hat{\kappa}_{-i}$, and therefore learn with inexact weights. We consider two settings:

• Coarse: For each user, a player has knowledge only of whether there is at least one other accurate player, i.e., $\\hat{\\kappa}_{-i}$ is either 0 or rounded down to 1.
• Partial: Players know the true $\kappa_i$ for a random subset of users, and use this to make inference about the remaining $\\hat{\\kappa}_j$ (we use kNN).
  Our results suggest that despite partial or coarse information, overall trends are preserved. However, the cost of misinformation is that social welfare is lower (and hence also total market share). For coarse, this reduction is 37% for $n=3$, and up to 45% for higher $n$. For partial, we see for $n>3$ that market research on just 100 users results in a welfare gain that is >70% of that under full information, suggesting that extrapolation can work well in our setting.
  Additionally, this gain increases with the size of user information. We found that providers are able to learn near-optimal best responses even when only having done market research on 20% of the population. The gain in welfare is summarized in the following table for the COMPAS-arrest dataset:

These findings show promise to the approach of extrapolating to the uninformative user sectors, and suggest that even in real-world settings our approach can be worthwhile. We will be sure to present these new results using the extra page of the final version, and provide full details of the experimental setup and complete results in the Appendix.

”Extending the theoretical analysis to a general N-provider setting would strengthen the paper”
Further analysis for multiple players is certainly interesting, and it is indeed our hope that this work inspires future work in multi-player settings. We will note though that this is not without challenges. Take, for example, our notion of partial discrepancy ($\\delta$), which offers a simple expression for utility in 2-player settings. As $n$ grows, the number of partial discrepancies between any 2 sets of players grows exponentially, and so extending our results to general $n$ becomes complex. We would also like to point out that the works of Ben-Porat & Tennenholz (upon which we base our setting) began with a work on 2 players (2017), and later released an entirely separate work to discuss the $n>2$ player setting (2019).

Thanks again for the helpful feedback. We are happy to discuss further any follow-ups regarding the new experiments and topics discussed above. If you found these to your satisfaction, we would greatly appreciate it if you would consider raising your score.

Thank you for your review and efforts. We have addressed your concerns in our response below. As for the issue of whether our paper is a good fit for ICML – which seems to be a main concern – we hope that our response, combined with the other reviews for our paper, help in establishing its relevance and appropriateness. Given this, we are hopeful that you will be willing to reconsider your position regarding acceptance, and will gladly answer any further questions you may have.

Relevance to ICML:
ICML includes a large sub-community of researchers that study questions at the interface of learning and economics, with game theory being one of the conference’s stated topics of interest (see this ICML’s call for papers). Many of the papers we cite and share connections with have been published in leading machine learning venues (see references). In fact, we view our work as lying more on the machine learning side than typical works in this space. As for Ben-Porat & Tennenholtz (2019), please note that it is in fact a follow-up to Ben-Porat & Tennenholtz (2017) – which was published in NeuIPS.

”The setting seems quite idealized for how ML actually happens in practice.”
Studying learning in economic settings requires making simplifying assumptions. This is especially true when aiming to establish a theoretical understanding – which is one of our goals. This also allows us to build on earlier results (e.g., that best-response dynamics reach equilibrium) that rely on similar assumptions. Despite these limitations, one of our key points is that naively optimizing accuracy can be a bad strategy. If anything, this portrays conventional learning frameworks as “idealized” when confronted with an economic reality. Our hope is that our work serves as a step towards further exploration of learning in practical market settings.

”Why assume that there is only one prediction per user..?”
While not applicable to all scenarios, this modeling choice is appropriate for many real-world settings where each user makes only one decision and hence is in search of a single prediction. For instance, in housing or car sales, a user typically sells a single house or car, and therefore looks for a single accurate prediction about the worth of the entity (for example from Zillow as a real estate valuation predictor). This leads to a well-defined $(x, y)$ pair per user. Other examples are cases where users interact with multiple items (e.g., recommending multiple products in social media sites), but the outcome of interest often remains singular at the user level. For example, a user may receive multiple predictions $(x, z)$, but only one true outcome $y$ (e.g. user satisfaction). This aligns with our setting where the goal is to model a single, well-defined outcome per user.
We agree that there are also settings in which users are associated with multiple labels. One idea is to model user decisions based on the probability of correct prediction $P(\\hat{y} = y)$ (e.g., quantal response). However, equilibrium results for such a model remains an open question and is beyond our current scope. We believe our framework provides a solid starting point and can be extended to incorporate such user dynamics in future research.

”The main way to get more accuracy is to have more users and thus get more data”
This is a good point. In our work sample size comes in indirectly through competition: for player $i$, if other players are correct on many points, then these will get small weights in $i$’s objective, and therefore its effective data size (see [1]) will be small. Our setup abstracts away the direct effect of competition on data size – this is an intentional design choice, intended to enable tractable analysis of our main phenomena. One justification is that accuracy gains from increased sample size typically exhibit diminishing returns; i.e., once a reasonable number of samples are obtained, adding more samples has only a mild effect on accuracy (see e.g. [2]). In other words, sample size effects are important mostly in the small-data regime, which is not our focus.
A final note is that in our setup, the goal of learning is not maximizing accuracy, but rather, market share. Our results show that aiming for maximal accuracy can be a poor strategy, and that it is often better to focus efforts on a small subset of the population than to seek better accuracy on as many users as possible.

”Is it possible to summarize the results in table 2 in a more visual way?”
To complement Table 2, we have already illustrated the full best-response dynamics in Figure 5 and provided a detailed discussion of such in Appendix D.2. If you have specific suggestions for further improving clarity, we are happy to consider them and will gladly add them to the final version if applicable.

[1] Pustejovsky (2019). Effective sample size aggregation.
[2] Kaplan, Jared, et al. (2020) Scaling laws for neural language models.

Many thanks for your positive review! We are pleased that you found that the paper was clearly written and that you enjoyed our result showing how competition can induce anti-competitive behavior. In line with this, we would like to address some of your feedback below:

”It would be helpful if authors address how their work connects with work on algorithmic collusion”
Thank you for raising our attention to this work! It is interesting to see another example of cooperative behavior arising implicitly in a setting of competition. It seems that they show that under certain families of stateful online algorithms, multiple competitors can actually retain monopolistic prices, which would benefit all of the providers. While our focus here is how machine learning prediction can be optimized under competition, their positive result in the area of pricing optimization is certainly interesting to see, and gives thought to how we can incorporate pricing into future work. More specifically, it would be a neat extension to define a price parameter for each provider, and as such the user choice can be according to which provider gives the best price-to-accuracy tradeoff.
With that said, there are some fundamental differences between their work and ours which bear consideration:

• As mentioned above, our focus is entirely on how machine learning predictors can implicitly coordinate under competition (through the weighted-accuracy objective laid out in Section 5). The work on Algorithmic Collusion does not consider the effect that product relevance has on the user choices, and therefore there is no consideration for how predictors play a role in the strategies of the players.
• In our setting we assume best-response dynamics, where the players respond optimally to the current strategies of the competitors. Indeed in the pricing model of their work, if players best-responded locally at each timestep, then the dynamics would converge to expected competitive behavior.
• As stipulated in the performativity paragraph at the end of Section 5, our setting is stateless (at least for $n=2$), whereas the Algorithmic Collusion work is stateful in that it takes into consideration the pricing in previous timesteps. This may also explain the positive result under the family of no-regret algorithms, which are different from best-response dynamics.

“It would have been interesting to have deeper discussion of the effect of capacity on competition”
We appreciate your interest in how the capacity of data representation affects the overall welfare. It is indeed a counter-intuitive result, and one reasoned about at length in the work of Jagadeesan et al. (mentioned in the paper), albeit in a different (though related) setting. Our intention here was to show how the result of “lower data representation resulting in higher welfare” shows itself in our setting as well, as it seems to be a central characteristic of competition in machine learning. We would also like to note that the main paper shows this result for $n=2$ players, and results for $n=2,3,4$ players are shown in Appendix D.3 (Figure 7).

“How [would] the main results of the paper change given a wider model of classifiers?”
Thank you for this feedback. To make sure we fully understand your concern, is your intention regarding the theoretical results for $n=2$ players? Regarding our results on equilibrium, market share dynamics, and welfare, indeed when extending to general model classes and for multi-dimensional data (Section 4.3 in the paper), the convergence results may not hold. Our empirical results, however, show that in general model settings, convergence still occurs almost immediately, within two rounds. The market share and welfare results hold strongly as well, suggesting, as you may have alluded to here, that there is opportunity for future work to extend our results to more general settings, as we did in the 1-dimensional case.

Thank you for your feedback! We are encouraged that you found the paper well-written and that you appreciate our analysis and experiments.

”The biggest weakness is the assumption that the players know the predictions of other players…”
Indeed, our analysis relies on the simplifying assumption that players know the number of other correct classifiers. This, however, need not be taken to imply that players share such information. Instead, we view this as simplifying a process in which each player has access to (some) information regarding competition. For example, there are markets where firms are likely to have a good sense of which user groups the other firms excel on or target. Another example are cases where a firm performs market research and obtains exact information on a subset of users. A third example is firms having coarse information, such as knowing whether users subscribed to a different provider.
To investigate this idea, we have added an additional experiment on partial and coarse information, in which firms have inexact estimates $\\hat{\\kappa}_{-i}$, and therefore learn with inexact weights. We consider two settings:

• Coarse: For each user, a player has knowledge only of whether there is at least one other accurate player, i.e., $\\hat{\\kappa}_{-i}$ is either 0 or rounded down to 1.
• Partial: Players know the true $\kappa_i$ for a random subset of users, and use this to make inference about the remaining $\\hat{\\kappa}_j$ (we use kNN).

Our results suggest that despite partial or coarse information, overall trends are preserved. However, the cost of misinformation is that social welfare is lower (and hence also total market share). For coarse, this reduction is 37% for $n=3$, and up to 45% for higher $n$. For partial, we see for $n>3$ that market research on just 100 users results in a welfare gain that is >70% of that under full information, suggesting that extrapolation can work well in our setting. Please see the table attached in our response to reviewer GVZQ for a more detailed comparison. We will add these new results to the Appendix.

”In practice … players may not share the same data points”
This is a fair point (and one we mentioned in our broader impact section). From a learning perspective, it is certainly possible to define a market where different firms have differing datasets, and in this setting our method would be valid and well-defined. However, from a game theoretic perspective, once exact datasets differ, then the market is no longer a congestion game, and its analysis becomes much more involved. We are familiar with only one work that aims to extend congestion games to settings where resources are not shared [1], but this requires making strong structural assumptions and the results are limited. Nonetheless, we agree that exploring a setting with differing datasets is of practical value and can be interesting as future work.

”Grounding in a specific application could help here”
Thank you for this recommendation. Consider a media platform, such as Netflix, whose value lies (in large part) in their ability to recommend relevant content to their users. Given their knowledge of the potential user base, they would like to create a recommendation system that maximizes subscriptions. Using their knowledge of the performance of the competitors (Disney Plus, etc.), whether through general, coarse, or partial information, they can use our method to give larger weight to the less-targeted users and in doing so optimize for market share.

”Analysis in multi-player settings would make the paper stronger”
Further analysis for multiple players is certainly interesting, and it is indeed our hope that this work inspires future work in multi-player settings. We will note though that this is not without challenges. Please see our response to reviewer GVZQ on this matter for more detailed reasoning regarding the challenges involved in extending our results to $n>2$ players.

”Can the empirical results be provided for realistic applications?”
Our empirical results focused primarily on the effectiveness of our method, establishing its robustness and efficiency. That said, we believe our framework lays a strong foundation for future empirical studies, and if applicable, we can address more potential directions for empirical validation in the final version.

”Absence of error bars in the numerical results”
Please note that we report standard errors in the Appendix (Table 5). These were omitted from the main paper for clarity, but if you feel these would be helpful there, we can certainly incorporate them back in.

Once again, thank you for the detailed feedback. If you found the above clarifications and improvements to your satisfaction, we would greatly appreciate it if you would consider raising your score.

[1] Milchtaich, I. (1996). Congestion games with player-specific payoff functions.