A Market for Accuracy: Classification Under Competition
Authors: Ohad Einav
Nir Rosenfeld
Venue: ICML 2025 poster (2025)
Keywords: accuracy markets
best-response classifiers
game theory
competition
Primary area: theory->game_theory
TL;DR: We study learning in a setting where multiple classifiers compete over users in a `market for accuracy'; we propose an effective approach for learning under competition and analyze market outcomes

Abstract: Machine learning models play a key role for service providers looking to gain market share in consumer markets. However, traditional learning approaches do not take into account the existence of additional providers, who compete with each other for consumers. Our work aims to study learning in this market setting, as it affects providers, consumers, and the market itself. We begin by analyzing such markets through the lens of the learning objective, and show that accuracy cannot be the only consideration. We then propose a method for classification under competition, so that a learner can maximize market share in the presence of competitors. We show that our approach benefits the providers as well as the consumers, and find that the timing of market entry and model updates can be crucial. We display the effectiveness of our approach across a range of domains, from simple distributions to noisy datasets, and show that the market as a whole remains stable by converging quickly to  an equilibrium.

A Market for Accuracy: Classification under Competition
Ohad Einav!
Nir Rusenfeld
Abstract
In accuracy markets, firms seek to maximize their market share by competing with other firms over who provides more users with accurate predictions. This paper aims to study such markets from three perspectives, namely of: (i) the firms (or 'learners') that compete in the market, (ii) the population of potential users, and (iii) the market itself. We follow the market model proposed by Ben-Porat & Tennen- holtz (2017; 2019), but focus on classification (rather than regression), which we argue is more natural for this setting. The main idea is that users choose a firm if it provides them with accurate predictions; if multiple such firms exist, then ties are broken randomly. When there is only one firm in the market (a monopoly), then maximal market share can be attained by maximizing accuracy directly-which is also optimal for users. However, once there is competition, each firm must take into account the predictions all other firms, as it depends on their choice of classifiers. This dependence forms an oligopoly market in which the interests of the firms longer necessarily align with user welfare, defined the ratio of users for whom at least one firm is accurate.
Machine learning models play a key role for ser- vice providers looking to gain market share in consumer markets. However, traditional learn- ing approaches do take into account the exis- tence of additional providers, who compete with each other for consumers. Our work aims to study learning in this market setting, as it affects providers, consumers, and the market itself. We begin by analyzing such markets through the lens of the learning objective, and show that accuracy cannot be the only consideration. We then pro- pose method for classification under competi- tion, so that learner can maximize market share in the presence of competitors. We show that our approach benefits the providers as well as the con- sumers, and find that the timing of market entry and model updates can be crucial. We display the effectiveness of our approach across range of do- mains, from simple distributions to noisy datasets, and show that the market as whole remains sta- ble by converging quickly to an equilibrium.
The main result of Ben-Porat & Tennenholtz (2019) is that if firms in such markets can successfully compute best (or better) response (i.c., find a model that maximizes market share conditioned on all other models remaining fixed), then dynamics will converge is insightful, but leaves many questions unanswered: When can best-response classifiers be found efficiently, and how?" What kind of equilibria can be reached, and what will happen on the way there? How will the market be shared by the different firms? And will outcomes be beneficial for users? Our goal to shed light on these issues and others, using theoretical analysis and empirical evaluation, and as they relate the learning firms, the users, and the market.
1. Introduction
pure Nash equilibrium. This
Machine learning models play an essential role in consumer markets of today. Across many domains, firms that offer products and services can significantly gain by attaining better predictions about their users, or providing better pre- dictions for them. In a sense, this has made accuracy itself a commodity which consumers pursue; consider how user choices have come to depend on the quality of personalized predictions in recommendation systems, media platforms, online marketplaces, or health analytics services. The in- creasing demand for accurate predictions incentivizes firms to improve their predictions, which in turn creates 'supply" of accuracy-a process which results in the formation of what we refer to as accuracy markets.
From the perspective of the learner, our results show that finding the best-response classifier is as hard-but also not harder than than-solving a standard classification problem. In fact, given the predictions (or classifiers) of other players, maximizing market share corresponds to maximizing a particular weighted accuracy objective. This means that although solving this exactly is hard, standard learning tech- niques (e.g., using proxy losses) can be highly effective in
Faculty of Computer Science, Technion - Isracl Institute of Technol- ogy. Correspondence to: Nir Rosenfeld <nirr cear@css..echiio..c.. www.oooooo...........m.m........ ac.il>.
Proceedings of the 1nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Ben--Prat & Tennenholtz (2019) give algorithm that applies to linear regression and relies on integer linear programming.

---

A Market for Accuracy: Classification under Competition
practice. It also provides the learner flexibility in choosing the model class to work with, it sees fit under standard considerations (e.g,, data size, compute capacity). Interest- ingly. however, we see that the choice of when to respond bears significant implications on outcomes for the learner. This brings to focus questions regarding the pioneering of a new market, entering an existing one, and maintaining user loyalty (or its harmful counterpart of user lock-in practices).
of adapting competition.
2. Related work
Studying the dynamics of machine learning models com- peting for market share has been a budding line of research. Ben-Porat & Tennenholtz (2017; 2019) present a regression learning task where providers wish to maximize their market share of users by reducing prediction errors to below a given threshold. Their focus is the equilibrium dynamics in the induced game between the providers. Employing a simi- lar setting, Jagadeesan et al. (2024) focus on the effects of competition dynamics on social welfare, showing that better data representation does not necessarily translate to better welfare; some of our results echo theirs. Feng et al. (2022) study the bias-variance tradeoff in competitive settings. Yao et al. (2023; 2024a:b) introduce competition setting for content creation and study welfare, equilibrium behaviors, and best-response dynamics. Ginart et al. (2021), Dean et al. (2024), and Su & Dean (2024) study how competitors specialize when user choices influence the observable data of each competitor. Our work puts emphasis on the learning task itself, and studies its effects on market dynamics and outcomes.
From the perspective of the market, our analysis suggests that most markets will exhibit strong anti-coordination (the other alternative being the existence of a single dominant strategy, which is possible but rare). In particular, mar- ket forces push firms to secure exclusive access to certain user sectors, and firms compete over who secures the larger sectors. Notably, gaining access first does not guarantee ex- clusivity; in fact, for simple markets with two firms we show that firms engage in chicken-like game, where moving first is disadvantageous. Our analysis reveals that, despite com- petition, firms are in a sense cooperating: when one firms acts to increase its market share, this also serves to increase the market shares of the other. Empirically, we observe that for larger markets with more firms outcomes are more nu- anced, although the order of play remains highly significant.
From the perspective of users, direct result of the market is that competition improves welfare. What may be surprising is how efficient the market is: Empirically, we observe that welfare increases quickly and attains the maximum possible value with only a few firms, and after one round of updates. For the latter, we give theoretical grounding for why this can happen. One reason is that our model for the market enables efficient outcomes to materialize-as long as information flows freely. This has policy implications: social planner that seeks to maximize welfare should incentive firms (or introduce regulation) to make their models public. Thus, transparency becomes an operational consideration which, in utilitarian sense, works in favor of both firms and users.
More generally, our research relates to the growing literature on strategic learning. The majority of work in this field mod- els users as strategic agents that can manipulate their fea- tures (c.g., Hardt et al., 2016; Levanon & Rosenfeld, 2021). In contrast, we model users as choosing among alternatives, and put emphasis
the strategic role that learning must assume to contend with competition. The idea that users can choose provider has been considered in Koren (2023) and Horowitz et al. (2024), but only for binary choice (i.c., join or drop out) and under uncertainty. Our work differs in that it supports choices between multiple firms in a competitive market. In a recent paper, Chen et al. (2025) study strategic learning with externalities; interestingly, their construction also gives rise to a potential game (as ours does), but be- tween users (rather than providers). Our work also draws connections to the field of performative prediction (Per- domo et al., 2020), which studies how (re)training models can gradually change the underlying data distribution. As we show, this perspective applies to our approach when con- sidered from the viewpoint of single competing provider.
We end with series of experiments using synthetic and real data that demonstrate the underlying mechanics of accuracy markets and how they operate. Our results demonstrate that learning in such markets can be feasible, that competition converges quickly, and that the market is typically highly efficient and favorable to users. Results also highlight the importance of adjusting the objective account for competition, and show how lacking to do so (and optimizing accuracy naïvely) can be detrimental to both firms and users. For the market, we present analysis revealing how it decomposes across firms, and measure concentration and market power. We also show the importance of timing market entry and model updates, the relation between performance and model class capacity, and the constructive role of information sharing. These results underscore the dynamics of accuracy markets and showcase the importance
3. Setup
In our competitive learning setting, users are described by features x E X' and labels E y, over which there is an unknown joint distribution p(x, y). There are n service pro- viding firms, $1...., Sn, who provide prediction services to users, and together form a market. Given a training set S { v:) mm each service provider 8; learns classi-
2

---

A Market for Accuracy: Classification under Competition
fier hy from some model class H, Each user a then chooses provider among those offering an accurate prediction:
Dynamics. To understand how game states progress, we will explore dynamies in which providers can update their predictive models over time, and in response to others. As- sume w.l.o.g. that providers are ordered, $1 < X ..... X 8n. Then at round i, each provider in turn chooses their h by playing best response, defined as:
(() E {or : h1(x) -} y
(1)
If multiple providers are accurate, then s(x) is determined by a random rie-breaking rule. When no providers offer an accurate prediction, we denote the null choice by ((x) = Ø. Welfare is defined as the ratio of users that obtain service:
M = BR(L
argmax p(h h--)))
(5)
NEH,
W (h) = (s()) 2 1H
(2)
That is. providers respond by choosing the optimal classi- fier h, assuming all others classifiers remain fixed, namely h²=: = (hj.....e h M441, 12--)) and for some choice of initial classifiers {h.) }. We refer to h as the best- best-response classifier of s;, but note it need not be unique. Since solv- ing Eq. (5) can be computationally infeasible, we will also consider approximate best responses that replace juh hL:)) with a tractable surrogate objective (see Sec. 5).
where h- (hi..... hm) are all classifiers in the market.
The goal of service providers is to maximize their market share, defined as the expected ratio of users that choose them. For each provider 8t this depends on its choice of learned model hú, but also on the set of all other models, h-4, For- mally, the market share of service provider 8; is defined as:
N = (1hss h- = (s(()
s:]]
(3)
We will be interested in studying the game's 's equilibria, focusing mostly on pure Nash equilibrium (PNE). These are defined states h in which no provider has incentive to unilaterally deviate from its chosen strategy:
Equilibrium.
where probability is w.r.t how s(x) is chosen from the set of accurate providers in Eq. (1). For simplicity we assume ties are broken uniformly at random, namely P [[s(z)= = s;] =
1 1/((#) where x(x) = (s3 s(x) E 8.)l- This conforms to the setting of Ben-Porat& & Tennenholtz (2017; 2019).
Vie [m], h E Hy: p(h h_.)) 2 u(h h-:)) (6)
Ben-Porat & Tennenholtz (2017) prove that the game is type of potential game (Monderer & Shapley, 1996). 2
When the market includes only a single provider, maximiz- ing market share is equivalent to maximizing accuracy:
Since the game is played on the empirical distribution, which implies that the set of all possible predictions is finite (even if H is not), a direct result is that a PNE exists and is reachable via a finite sequence of best responses (Eq. (5)). Note that multiple equilibria may exist, and that these may differ significantly in market shares, market concentration, and induced welfare. Furthermore, not all equilibria can necessarily be reached via best-response dynamics, and the equilibrium that is reached can depend on the initial game state (i.e., choice of first classifiers) and the order of play.
argmax E (v = M(x)]]
(4)
which is the standard objective of supervised learning, and in this case also maximizes welfare by definition. However, once there is competition, this connection breaks since each provider's market share becomes dependent on all others. Thus, the naive approach of maximizing accuracy as proxy becomes suboptimal, and the question of how providers maximize their market share must be considered jointly.
4. Analysis
Competitive learning as a game. For given distribution p. if we think of each provider 8; as player and interpret Eq. (3) as their utility, then this defines a game, which we refer to as an accuracy game. The strategy space for each s; is the set of all models in its model class H,, and each tuple h = (h1,...,Ah .,,)) defines a game state. We will assume the game is played on the empirical distribution induced by S, but that final payoffs are given by expected market share w.r.t. P. Note the game remains well-defined when players have their own St pt, although current equilibrium results do not hold for this setting. In terms of information, we work in the full information setting where all players have complete access to the payoff matrix. However, as we will see, optimal strategies for providers require strictly less information.
In this section we set out to analyze basic properties of accu- racy markets. To permit tractable analysis, here we focus on simple two player markets. We start with restricted model class, and then proceed to consider more general classes. Proofs for all results are deferred to Appendix A.
We begin with some basic notation and properties that are useful for games with n 2. Fix p, and consider some H. For each provider s, denote the accuracy of its chosen h, as:
a: = (h, = y'l
Forr completeness, in Appendix B.1 we give the game's charac- terization congestion game by identifying the appropriate congestible resources and constructing an explicit cost function.
3

---

A Market for Accuracy: Classification under Competition
In the latter case, the game admits a chicken-like" structure: one provider obtains a larger market share by choosing the 'better' classifier, while the other must settle for the smaller share. Note that better here does not mean more accurate, as outcomes at equilibrium also depend on discrepancy. The proof of Thm. relies on the following result:
l12
h1
{a1 + 812), {a2 621)
2
hn
2 (02 + 821), {am + 812)
J02 f02
Table
I: Payoff matrix of the 2x2 game
Lemma 1. Providers will choose differing strategies at equilibrium if and only if (a a2 S 3 (012 + d21).
We define the partial discrepancy of by relative h2 as:
Thus, anti-coordination emerges when hy, hy are sufficiently similar in terms of accuracy, but note that the condition is fairly lenient. Empirically, we observe that chicken play is by far the more prevalent scenario, and that the order of play (which is only hinted to here) is highly significant. We next show that the above properties hold more broadly.
6Gj- = 6,(h)) (1)1((h(()) y (x)x) + v3l (8)
which sums points on which h; is correct on but b is wrong-
Proposition 1. Let his hg, then p(h;/ hyy) = 1 (a, + 5zy).
This implies that there are two ways to increase market share: by improving overall accuracy (a;), or by being exclusively correct on more points (6.z). Thus, the choice of h should consider how these two terms trade off. Note that points in ōij are counted twice, since they are also included in ag.
4.2. Accuracy markets with threshold classifiess
Keeping n 2, consider more general accuracy game in which E {0, 1}, inputs are scalar (r E R), and H comprises threshold classifiers h, (z) = 1 (x > r}. This also captures settings with general inputs x where there is pre- pre-trained score function (x) and each 8; can set its own thresholds as hx(2)) = I (f(x) > T:): i.e., competition revolves around different ways to 'set the bar' w.r.t. f(z).
Interestingly, as long as the classifiers are distinct, then who- ever has higher accuracy also secures a larger market share: Proposition 2. For any h4 + h2. it holds that:
Our next result shows that under certain conditions, even though H includes a continuum of models, the game simpli- fies significantly. Consider the following common property:
p(he (1y) pahy h2)
a2ag
(9)
This, however, should not be taken to imply that maximizing accuracy is a good strategy, since providers seek to maxi- mize their absolute market share-not their market share in relation to others. Regardless of the other's market share, a provider may switch to an equally accurate classifier or even sacrifice in accuracy to gain greater discrepancy- if this results in market share increasing. Empirically ob- serve that sacrificing accuracy is both common and effective.
Definition 1 (MLR). Let p(z., y) be continuous in x. and fy the PDF of each conditional p(æly) for y E {0, 1}. We say that exhibits a (strict) monotone likelihood ratio (MLR) if the density ratio p(xx) f((a) is (strictly) increasing.
[o
We show that MLR entails a simple closed-form solution to the best-response classifier against any other classifier:
Theorem 2. Fix n = 2, and let H = {h+} } be class of threshold classifiers over d = 1. Let p be such that it is strictly MLR in some interval [a, b). Then for any T E [a, b):
4.1. Warmup: 2 x 2 accuracy markets
Consider simple setting with 2 providers and shared model class of size two, H- = {A1: h2). For example, these could be two available pre-trained models, or an existing model that is already in deployment and new model that is a possible alternative. Such x 2 games are fully determined by the tuple (a1, 02 812, 821) see Table 1. This formula- tion enables characterization of all possible equilibria:
BR (7) E E p (1/2)), min (2)()
where (o (T) is the best-response T from the set (a, b).
Thm. 2 states that of all thresholds in the range where MLR holds, the set of candidates for a best-response classifier reduces to just two. For natural cases in which the extreme choices of 7 < a and T > b are not optimal, the structure of the game simplifies even further.
Theorem 1. Let H = (hi, h2). Then for any ps the gume admits one of two following types:
1. Dominant-strategy: either (h1, h1) or (h2, hz) is a PNE
'The standard Chicken game has payoff's of the form Coordinationn-Neuree TemptatonnCCorrddaatinnnn
2. Anti-coordination: both (h,, h2) and (h2, are PNEs
Punisshett our variant has T>>>>>>>> O, which preserves the same PNE. Forr example, mixture of two Gaussians is MLR everywhere except possibly in the tails, where thresholding is ineffective.
"This is likely scenario: works on the 'Rashomon' effect (Paes et al., 2023) and model multiplicity (Semenova et 2022).
4

---

A Market for Accuracy: Classification under Competition
Corollary 1.
For n 2 and H {he}, any accuracy
Corollary 2. Fix initial classifter h. Vi, and let h² be the
game played on MLR region of p reduces to 2 x game. Hence, all results from Sec. 4.1 hold.
set of classifiers equilibrium. Then W(h") 2 W(h").
In terms of the market, we can bound its concentration: Proposition 6. Let ht = (bi,h)) be any equilibrium. Then p(hishhy) S 2- p-(hh)hh))
Note the reduced model class is H (1=2 This is not by chance: under MLR, these ratios are precisely the points in which accuracy and discrepancy balance each other. Interestingly, this partitions the population into three segments: mostly negative points, mostly positive, and a mixed subpopulation. Providers then compete over who obtains exclusive access to the more rewarding segments.
Thus, despite the tendency for differentiation under compe- tition, no player can dominate more than 2/3 of the market.
General accuracy markets. Empirically, many of our above results hold also for any number of players and gen- eral model classes: quick convergence, implicit cooperation, incentive to differentiate, sacrificing accuracy for mar- ket share, bounded market concentration, and high welfare. Some results however do not carry over to n > 2; for ex- ample, the order of play becomes much more intricate, and whether moving first is good or bad can depend on context. Importantly, our results hold despite the intractability of computing best responses exactly, and by using our method for learning approximate best responses presented next.
Thm. 2 can be generalized to any ID distribution:
Theorem 3. Fix n 2, and let H {h-} be a class of threshold classifiers. Then for any interval [a, bj and any T:
of E (a, h, where (T) =
0}.
For reasonable distributions, it is likely that |PF (z)l < c for some small constant c. This then implies that H effec- tively reduces to include only (c)) candidate strategies.
5. Method
The above results also have implications on dynamics: Proposition 3. For n and H }, best-response dynamics converge after one round.
We now turn to the question of how to implement a best re- sponse, i.e., by solving Eq. (5) for any setting. Our main oh- servation is that a provider's market share objective (Eq. (3)) can be rewritten with a particular choice of per-example weights:
We therefore receive that for threshold classifiers, not only is calculating the hest-response a simple task, but the market also converges immediately. The difference from the MLR setting is that there can now be multiple equilibria, and convergence can depend on the initial choices of {Λ.}.
weighted expected accuracy objective
14 = FF, (x)) (h((z)) = -}]. wx(x)
+ k K-
(10)
Best-response dynamics imply that model updates can im- prove market share only for the provider that responds. In- terestingly, in the above setting, we can show that best- response by one player improves outcomes also for the other. Proposition 4. Let Nº = hopt,
where (=) = Hs, + s; h2(x) = .)|, i.e., the number of other providers that are correct on x. Thus, weights wx(x) determine the importance of input æ for provider i,
and inform the objective of which inputs to target, or avoid.
Vi. Then for each 8;, market share P4 increases even when the other 8j best-responds.
Hardness. In terms of tractability, our results are mixed:
Observation 1. For any choice of H, and given wi, com- puting the best-response classifier h4 = BR(h-:) is just as hard as maximizing expected accuracy over H.
Empirically, we observe that this form of implicit coopera- tion emerges also in broader settings. For n 2, outcomes improve once all other players have responded.
This holds since weights in Eq. (10) simply modify the data distribution, a change to which learning algorithms should be agnostic.? Unfortunately, because maximizing the ex- pected 0-1 accuracy is computationally intractable (and sta- tistically challenging) for the vast majority of classification problems, computing best-response classifier exactly will mostly be infeasible. The bright side is that this is precisely the problem that machine learning practice aims to solve.
4.3. Accuracy markets for general model classes
For general classes and n 2, several properties of the market can still be established. The first considers providers: Proposition 5. If h 0 Vi, for some ho, then μ3 2 n.
That is, if providers start at the same initial classifier, then all of them will provably gain from competition. This directly implies that competition also improves welfare for users:
'E.g. consider how the PAC framework defines class H as learnable if there exists (efficient) algorithm that maximizes accuracy well simultancously for all distributions (Valiant, 1984).
'If they exist; otherwise the optimal models are at a, by see Thm. 2.
5

---

A Market for Accuracy: Classification under Competition
Market shares
0.500
2)
Provider
N(a 1)
0.475
Provider
0.450
Thresholds
h1
0.425
1.0
0.000
0.375
6.5
Accuracy
0.350
0.50
0.325
0.300
0.25
Market Share
-2 Bell 1] Elelyy -1
to Ag
to f/
Figure 1: Two-player threshold market. (Left:) Data consists of two class-conditional Gaussians p(1 (y) N May, σy) Beginning at hops, providers compete over who gets the better classifier, f2g which secures exclusive access to the larger sector of positive users (blue). (Center:) The game as played over time. Each best response improves market share for both providers, but the second mover (82) prevails. (Right:) Outcomes for increasingly distanced p(a; [ y)) (here oy - o).
Equilibrium classifiers are pulled further away, and sacrifice accuracy for increased market share.
Hence, any solution that works well for general machine learning tasks should also work well learn best responses.
are only two providers, performativity is stateless, meaning that p + depends only on the current hद through how sy will best-respond; this relates the common (and simpler) setting often studied in performative prediction (Perdomo et al., 2020). When n > 2, dynamics become stateful, i.e., are path-dependent, and so choices accumulate over time- a generally much more challenging setting (Brown et al., 2022; Li & Wai, 2022). Luckily, our market construction adds structure that makes it tractable instance. An inter- esting point to make is that performativity in our setting has 'real' effect the distribution. Rather, it only changes how providers should perceive the distribution in order to effectively maximize their utility in the market.
Learning (approximate) best-response classifiers. Since the game is played the empirical distribution, can adapt any method of empirical risk minimization that sup- ports custom example weights, i.e., that aims to solve:
h, = arggmnn REH m.
1 - Σ we ((xx,))((,,,M)))) M2,))) + AB(h) (11)
where é is proxy loss (e.g., hinge loss or cross-entropy) and an (optional) regularization term. This approach applies any type of data and choice of model class H. We refer to hn the approximate best-response classifier of st- Note that optimizing hn depends on the other classifiers h- only through the example weights (xz)). This means that computing the empirical best-response classifier requires only access to the number of other providers that are correct on each data point-non to the actual classifiers in h-s, Also, we can observe that the average weight [ST Eies w; has an intuitive meaning: is the maximum possible market share that could be achieved by a perfect classifier, i.c., when all its predictions are correct. The actual μı is then this optimal market share minus the weighted loss incurred by the chosen classifier h,.
6. Experiments
We now present our empirical investigation of learning in accuracy markets. We begin by demonstrating the basic mechanics of competitive learning on simple synthetic data which allows us to compute best-response classifiers exactly, Then we switch to real data and apply our method from Sec. 5 to accuracy markets across multiple datasets and various learning algorithms. Code is publicly available at https: http://ggtttuuuteeegg thub com BML-Techhnio haop/mmrkee t4acc.
1
6.1. Synthetic data
Performativity. Eq. (4) casts maximizing market share as a problem of learning under distribution shift, where shift is due competition, as expressed by weights wx(x). From the perspective of a single provider s; at time weights (x) describe how the market has changed in response to its own actions, i.c., the choice of hg This reveals that learning in a market setting is of a performative nature: the choice of classifier at the current time step shapes the (effective) distribution the next, p ++1 (x. y). When there
To gain an understanding of how accuracy markets work, consider a simple setting with n providers, binary la- bels y [+1]. univariate features x R sampled from class-conditional Gaussians p(x y) M(ay, o,), and threshold classifiers H = (h~(x) = 11 (a: > 7} | I E RJ. Figure (left) illustrates this setup for = 1, = 2, and a+1 = 1, and shows the learned classifiers at equilib- rium, hi and ho; as Thm. 2 suggests, these are precisely p (1/2) and p ((2). Note how the region between hy and
6

---

A Market for Accuracy: Classification under Competition
Table 2: Learning in accuracy markets. Results show outcomes of best-response dynamics, implemented as training by Eq. (11). All runs were initialized to h = hopt, and converged after at most t = 2 rounds. Results include % increase at equilibrium of market share (min and max over providers), market concentration (HHT = -, and welfare. Standard errors of the experiments are insignificant and shown in Appx. D.I.
COMPAS-arrest
COMPAS-violent
Adult
min j
max μ
HHI
welfare
min 1
max
HHI
welfare
min 14
max μ
HHI
welfare
+25.4%
+31.0%
+64.5%
+28.2%
+41.8%
+61.2%
+130.6%
+51.5%
+4.0%
+30.5%
+39.8%
+17.3%
R providers
3
+38.7%
+48.5%
+106.2%
+43.5%
+46.8%
+82.5%
+163.7%
+61.6%
+2.9%
+41.7%
+51.8%
+22.1%
4
+38.0%
+66.9%
+121.9%
+48.4%
+48.5%
+94.6%
+172.0%
+63.9%
+6.1%
+39.4%
+51.2%
+22.0%
+36.8%
+83.2%
+128.7%
+50.1%
+48.7%
+94.6%
+172.3%
+64.0%
+11.7%
433.2%
+51.4%
+22.7%
+38.7%
+80.4%
+127.9%
+50.2%
+48.5%
+89.0%
+172.3%
+64.2%
+10.5%
+41.6%
+53.7%
+23.2%
h2 (hatches) is split between the providers: 81 is exclusively correct on positive examples, and 82 on negatives. The regions to the right of h and left of by are shared.
learning algorithms, including linear SVMs, boosted trees (using XGBoost), and random forests. These generally work well for standard accuracy tasks on the above datasets, Ap- pendix C includes full details datasets, methods, and our experimental setup. Appendix D includes additional exper- iments that extend and complement those presented here.
Fig. 1 (center) shows how market shares μ1, 122 evolve rounds of best-responses. Here we initialize hy = hg hopt where hops is the optimal classifier (i.e., which maxi- mizes accuracy on p). In line with our results from Sec. 4.2, dynamics converge after one round, i.e., each provider re- sponds once, and so in = ht and h2 = lty. Although 81 moves first and improves μl, this not only improves μ2 for $2, but also greater extent than that of $1. When 82 then moves, again both P1, M2 increase, but μ2 retains its advan- tage over jr1. Hence, 82 'wins" the chicken game by playing second and obtaining access to the larger exclusive subgroup of positives. Regardless of who wins, users gain from the competition since welfare (= 141 + (12) always increases.
Learning. Table 2 shows performance under several mea- sures of interest across multiple datasets and for varying number of providers. Here we show results for Linear SVMs, but note that other learning algorithms exhibit over- all similar trends (see Appendix D.1). All results are aver- aged over 10 random train-test splits. The table describes outcomes after f = 2 rounds, which we found sufficed to obtain coveernnee across all settings-regardless of training set size, model class complexity, and the use of proxy objective to implement (approximate) best responses.
Fig. (right) shows how outcomes change for matching gaussians 0- 1) when the class-condition tributions p(z y -1) and p(z y = 1) are pulled closer together, achieved by decreasing a. When the distributions are far away, hi and /22 are at hopt and so fully share the market. But as overlap increases, several effects take place. First, hy and he grow further apart and become more distinct in who they target, causing the exclusivity regions to grow in size. Second, since classification becomes harder, the maxi- mal attainable accuracy decreases. The accuracies of h1, h2 also decrease, but at faster rate result of specialization. Third, we see that welfare-aa as the sum of market shares- begins at its maximal value of (when the gaussians are perfectly separable), then decreases when the exclusivity doesn't 't extend to the tails, and finally returns to 1 when the providers play opposite thresholds. We explore additional aspects on non-matching gaussians in Appendix D.4.
In terms of market share improvement, we see that competi- tion is helpful for all providers; nonetheless, there can be a large gap between the minimal and maximal improvement. In the COMPAS datasets, this gap begins at smaller values, but grows as n increases. For Adult, whose baseline accu- racy is higher, the gap remains mostly stable, but is large to begin with. As competition progresses, the market becomes more concentrated, which also generally increases with n. Overall welfare gains are quite high, reaching up to +65%.
dis-
Market outcomes. Figure 2 shows how the market is partitioned across providers at equilibrium. Here we focus on COMPAS-Arres with XGBoost and n = 3 providers; providers are numbered by their order of play (i.e., 81 < 82 < 83), where this order is preserved across rounds. The plot shows for each provider s; its total market share (bottom left) and accuracy on the entire population (top left) due to its final learned h4. The plot also shows the decompasition of the market across all subsets of providers: what proportion is exclusive to $1, what is joint to $2 and $3, what is shared by all, etc. (right). Here we see that $j, who moved first, attained the largest market share (36%). However, its accuracy is significantly lower than others,
6.2. Real data
Our goal in this section is to explore accuracy markets der our three perspectives: (learning) providers, users, and the market. We experiment with three datasets: COMPAS- Arrest, COMPAS- COMPAS-Violence, Violence, and Adult, and consider several
7

---

A Market for Accuracy: Classification under Competition
50%
44.4%
Ay He M1
+10%
0.6
40%
222
H/ Ps
accuracy
0.4
30%
28.5%
Ay 0-
0.2
20%
19.2%
-10%-
0.0
10%
5.7%
51
92
53
0.3%6..5%
0.9%0.6%
2
5
6
market share (el
Number of providers
35.6%
51
!!!!
29.4%
$2
Figure 3: Influence of order of play on market share. The orange densities measure the difference in market share between the provider that moved 2nd and the provider that moved 1st, and the blue densities measure the difference in market share between the provider that moved 2nd and the provider that moved 3rd, for > 2. Dashed lines inside the densities represent the 25% 50%, and 75% quantiles of values, respectively, from bottom to top.
29.4%
$3
Figure 2: Market share. An example for = 3 where the first mover (s1) dominates the market, achieved by sacri- ficing overall accuracy for exclusive access to a large user sector. Other providers are left to share the remaining sector.
and below 50%. The subsets plot reveals the reason: 81 was able to gain exclusive access to 28.5% of the market; shares an additional 19% with all providers, but only 1% with each of them alone. In contrast, 82 and 83 share almost all of their users, either with $1. This shows how $1 has come to dominate the market by learning a classifier h1 that sacrifices accuracy in order to effectively target an exclusive user sector. The low overall accuracy of fu suggests that naively optimizing for accuracy without considering the effects of competition can be highly suboptimal in terms of market outcomes.
The vast majority of experiments showed a significant gain in market share, as seen by the fact that the 25% quantile of values already shows net-positive gain from moving last. We also note that the expected (mean) competitive advantage of moving last is 3.6% with median of 4.8%. Given that for 2 players with equal model classes, the mar- ket share of a single provider will never exceed 3 = 0.67 (see Proposition 6), then a 4.8% difference in market share is quite significant.
pair (44%) along
When the competition game is played with n 2 providers, however, we observe an entirely different dynamic. Figure 3 provides two densities: The orange density is in the 2- provider setting (#2 -11). The blue density is the difference in market share between the player who moved 2nd versus the player who moved 3rd (#22 (a).. We find here that the ratios have switched: it is in fact more advantageous to be the provider that moves 1st, as evidenced by the negative orientation of the orange density plot. The next interesting thing that note is the seeming insignificance of order- of-play beyond the first two positions, as we can observe that the blue density hovers around O with relatively low variance. This alludes to the premise put stated above that in competitive settings with 3 or more players, the person who moves 1st in essence "grabbing his territory", which then induces all of the other players play among themselves for the other resources, ie. consumers.
Order of play. Whereas our 2 2 analysis from Sec. 4.1 suggested that the game either has dominant strategy chicken-like structure (which implies that moving second is preferable), we see in Fig. 2 that for n > 2 providers reality is more complex, and in fact moving first allows to dominate the market. Interestingly, this first move induces a 2-player game on the other providers whose equilibrium ad- mits dominant strategy. To quantify this phenomenon, and assert its robustness across methods, we experiments for every combination of datasstts and model classes, listed in Appendix C. For each experiment, namely for each combi- nation of model class and dataset, the final market shares were calculated for each provider along with his/her rela- tive position of play, i.e., at what position did the provider perform a best-response. Additionally, each experiment was performed for competitions with 2,3.4,5, and 6 players, so that we can compare dynamics across different market saturations. Figure 3 shows the order of play comparisons, averaged out across all of the experiments that were de- scribed above. When the competition game is played with n = providers, we see a clear preference to be the provider that moves last, characterized by the market share term J12-
User welfare. Our result in Cor. 2 states that competition is conductive to welfare. It remains to consider how conduc- tive it is. as well as how quickly welfare improves. Fig. 4 left shows how welfare changes over time and for increasing number of providers n. Here we focus on COMPAS-arme and LVC, with other settings shown in Appendix D.3.
8

---

A Market for Accuracy: Classification under Competition
number of providers (n)
number of features (d)
7. Discussion
1.0
This work studies learning in a competitive setting where classifiers are trained to increase market share. From a learn- ing perspective, our main message is that while maximizing accuracy naively is likely not good strategy, optimizing weighted accuracy objective that correctly encodes com- petition can be very effective. Although technically similar, the transition to market-induced objectives has implications on the market and consequently on user welfare. In our market model competition promotes welfare, but this relies on model transparency, efficient information flow, and calculated user decisions. Realistic markets are likely to fall short of such ideals: firms may prefer to keep models private, informational advantages can be exploited, and user behavior can be far from rational. The fact that most service sectors currently include only a few competing platforms (consider media, social, e-commerce, finance, housing, etc.) should raise concerns of oligopolistic behavior, notably collusion and lock-in practices. This requires deliberation of appropriate regulation for these emerging accuracy markets.
wellare
0.8
d= 12
0.7
14
+ -6-16
-6-18
0.6
0 10
all
2
2
round (t)
round (c)
Figure 4: Welfare over rounds. Competition consistently increases welfare over time, until convergence. Welfare improves with the number of providers (left), but (perhaps counterintuitivelyy decreases with the quality of data (right).
The plot shows clear trend of welfare increasing through- out competition. It also makes apparent the effect of n: as the number of providers increases, welfare climbs higher and faster. For n = 2. welfare attains maximum of 0.85, reached only at the second round. For n = 3, welfare max- imizes at 0.95 by the end of the first round. Notice that welfare reaches the upper bound of already at n = and before the end of the first round (i.e., before all providers have moved). With n 6 providers, this occurs even earlier.
Impact Statement
Our work considers the role of machine learning in fostering markets in which utility to consumers derives from person- alized accuracy. The market model we study is inspired by real markets of this type, but as a model, makes sev- eral simplifying assumptions that merit consideration before drawing conclusions about actual markets. One assumption is that there is a single underlying distribution that is fixed and accessible to all providers. Although this is a common assumption in standard machine learning, under competi- tion it has further implications. When data distributions differ across providers, even when the distribution is the same but samples are different (which is plausible), it is no longer clear if pure equilibrium exists or is reachable through reasonable dynamics. Another assumption is that users choose a provider who is accurate on their own input. This applies in some cases, such as personalized recom- mendations: users likely know their preferences, but do not know if (and which) content items match them-but can make conclusions once recommended. More generally how- ever, we consider our model as simplification of outcomes that materialize and stabilize over time, such as provider reputation, social learning, or confirmation in hindsight. An- other alternative is that users interact with a platform not once but many times; if the platform has access to some personalized examples, then competition can revolve around future expected outcomes. A final assumption is that users are rational and choose by maximizing utility independently at each time step. This can be reasonable assumption in settings where users have both incentive and resources to invest effort in bettering their choices, and when sufficient
The above depicts accuracy markets as highly efficient. On the one hand, our market setting allows for the free flow of information, and models users as making informed (ra- tional) decisions- which are necessary to enable efficient outcomes. But on the other, providers are restricted in that they cannot compute best-responses exactly. We therefore take the results above to again suggest that maximizing mar- ket share using proxy objectives can work well in practice.
Since market share should generally align with accuracy, another interesting question is how does the capacity to max- imize accuracy affect the overall welfare. For a different setting of competing predictors, Jagadeesan et al. (2024) argue that increased capacity can result in lower welfare for users. We show that this occurs quite distinctly in our set- ting as well: When the complexity goes down, maximizing accuracy may be harder, but gaining discrepancy is easier, as there are more users to specialize on. Following the idea of controlling capacity by the quality of representation, we implement this by varying the number of features available for learning. Fig. 4 (right) shows welfare for increasing number of features and for n 2 (see Appendix D.3 for more settings). As expected, at time = 0, better represen- tations entail higher accuracy, and therefore higher welfare. But once providers respond, the trend inverts: restricting learning to use only two features attains the optimal welfare of 1, while using all features gives welfare of 0.84.

---

A Market for Accuracy: Classification under Competition
time passes between rounds enable switching providers. More generally, user behavior is likely to play a key role in market outcomes, and can benefit from more realistic mod- eling. is also likely that competition can drive providers to exploit users' hehavioral waa additional reason for establishing appropriate regulations and norms.
In International Conference on Artificial Intelligence and Statistics, pp. 1693-1701. PMLR, 2021.
Hardt, M., Megiddo, N., Papadimitriou, C., and Wootters, M. Strategic classification. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pp. 111-122, 2016.
Acknowledgments
Horowitz, G., Sommer, Y., Koren, M., and Rosenfeld, N. Classification under strategic self-selection. arXiv preprint arXiv: 15274, 2024.
The authors would like to thank Fan Yao, Moran Koren, Omer Ben-Porat, and Eden Saig for their insightful remarks and valuable suggestions. This work is supported by the Israel Science Foundation grant no. 278/22.
Jagadeesan, M., Jordan, M., Steinhardt, J., and Haghtalab, N. Improved bayes risk can yield reduced social wel- fare under competition. Advances in Neural Information Processing Systems, 36, 2024.
References
Koren, M. The gatekeeper effect: The implications of pre- screening, self-selection, and bias for hiring processes. arXiv preprint ar 167 2023.
Angwin, J., Larson, J., Mattu, S., and Kirchner, L. Machine bias. propublica, may 23, 2016, 2016.
Ben- Ben-Porat, O. and Tennenholtz, M. Best response regression. Advances in Neural Information Processing Systems, 30, 2017.
Levanon, S. and Rosenfeld, N. Strategic classification made practical. In International Conference on Machine Learn- ing. pp. 6243-6253. PMLR, 2021.
Ben-Porat, O. and Tennenholtz, M. Regression equilib- rium. In Proceedings of the 2019 ACM Conference Economics and Computation, pp. 173-191, 2019.
Li, Q. and Wai, H.-T. State dependent performative pre- diction with stochastic approximation. In International Conference on Artificial Intelligence and Statistics, pp. 3164-318 3186. PMLR, 2022.
Brown, G., Hod, S., and Kalemaj, I. Performative prediction in a stateful world. In International conference on arli- ficial intelligence and statistics, pp. 6045-6061, PMLR, 2022.
Marx, C., Calmon, F,, and Ustun, B. Predictive multiplicity in classification. In International Conference on Machine Learning, pp.
PMLR, 2020.
Chen, Y., Hossain, S., Micha, E.,, and Procaccia, A. Strate- gic classification with externalities. In The Thirteenth International Conference on Learning Representations, 2025. URL https:/ http///peeeeveeeeeeeeeeeeeeeeeee www.enewwwweeeeeeeeeeeeeeeeeeeee for 06CXkEEttn.
Monderer, D. and Shapley, L. S. Potential games. Games and economic behavior, 14(1):124-143, 1996.
Paes, L. M., Cruz, R., Calmon, F. P., and Diaz, M. On the inevitability of the rashomon effect. 2023 IEEE International Symposium on Information Theory (ISIT), pp. 559-554. IEEE, 2023.
Dean, S., Curmei, M., Ratliff, L.,, Morgenstern, J., and Fazel, M. Emergent specialization from participation dynamics and lulti-leamerr retraining. In Dasgupta, S., Mandt, S., and Li, Y. (eds.), Proceedings The 27th International Conference on Artificial Intelligence and Statistics, vol- ume 238 of Proceedings of Machine Learning Research, pp. 341-351. PMLR, 02-04 May 2024. URL https: //proceedings... mlr press/
Perdomo, J., Zrnic, T., Mendler-Dümme Dünner, C., and Hardt, M. Performative prediction. In International Conference on Machine Learning, pp. 7599-7609, PMLR, 2020.
Semenova, L., Rudin, C., and Parr, R. On the existence of simpler machine learning models. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, pp. 1827-1858. 2022.
html.
Feng. Y., Gradwohl, R., Hartline, J., Johnsen, A.. and Nekipelov, D. Bias-variance games. In Proceed- ings of the 23rd ACM Conference Economics and Computation, EC '22. ACM, July 2022. doi: 10. 115534990486.5338248, URL 1445/3490486.3532222
Su, J. and Dean, S. Learning from streaming data when users choose. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F. (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Ma- chine Learning Research, pp. 66772-46803 PMLR, 21- 27 Jul 2024. URL https: https:: h/tp:::///procedinggs mlr. press/ v235 v235/su24a 2tt.4....mm....
Ginart, T., Zhang, E., Kwon, Y., and Zou, J. Competing ai: How does competition feedback affect machine learning?
10

---

A Market for Accuracy: Classification under Competition
Valiant, L. G. A theory of the learnable. Communications
of the ACM, 27(11):1134-1144 1984.
Yao, F., Li. C., Nekipelov, D., Wang, H., and Xu, H. How bad top-k recommendation under competing content creators? In International Conference on Machine Learn- ing, pp. 39674-39701. PMLR, 2023.
Yao, F., Li, C., Sankararaman, K. A., Liao, Y., Zhu, Y., Wang, Q., Wang. H., and Xu, Rethinking incentives in recommender systems: are monotone rewards always beneficial? Advances in Nearal Information Processing Systems, 36, 2024a.
Yao, F., Liao, Y., Wu, Li, C., Zhu, Y., Yang, J., Liu, J., Wang, Q. Xu, H., and Wang, H. User welfare optimiza- tion in recommender systems with competing content creators. In Proceedings of the 30th ACM SIGKDD Con- ference on Knowledge Discovery and Data Mining, PP- 3874-3885, 2024b.

---

A Market for Accuracy: Classification under Competition
A. Proofs
Notations. In the proofs below, we may use the multiple notations for partial discrepancy interchangeably, namely di 5n, (hy). This for readability and ease of portrayal. Similarly, place of μ (market share), sometimes there can be written U, for utility. These terms are also interchangeable. Lastly, the terms "player" and "provider" are interchangeable as well, since both refer the learner.
Before delving in to the proof' of the individual statements from the main paper, we will start with showing helpful observation that sits at the crux of competitive dynamics, and will help with many of the proofs below.
Observation 2. For any 2 classifiers ba, by with accuracies di, Oj it stands: a₁ òig 0g Özé-
Proof. Visual proof by building a confusion matrix split up by accuracy on the label:
hg =
hg + y
hig y
a; dej
dij
ag
l1g #
6zf
1 - 04 8j{
= 1 a₁
= Uj
= 1 - -aj
Explanation of the table:
the cells are partitioned by buckets according to the correctness of the classsifiers. This helps understand the discrepancy and overlap of accurate predictions between the classifiers.
We can immmediately observe that the 1st to a, and the 1st column sums aj- Similarly, the 2nd row and 2nd column sum up to 1 0z, aj. repsectively. So too, dij and ōjs are in the top right and bottom left cell by definition.
From the sums of the rows and columns, we observe the following equality from the top-left cell:
6ig = aj - 553
(12)
Proposition 1 (Market Share).
Proof. from the definition of our problem setting, classifier hy gets:
Full market share on the points that only hy is correct on: 1 " Σ 1(h)(z) = y A (4(2)) # w}
Half market share on the points that they are both correct on: 1 Σ 1 (x) = y A ( - y
By the definition of partial discrepancy (Eq. 8), the first bullet is exactly on, (hi), and the second bullet is equal to (a, 5n, (h4)).
We then receive: (ha = on, (h+) + 1 (aa - 6n, (h+)) (a. + 5n, (h.))
12

---

A Market for Accuracy: Classification under Competition
Proposition 2 (Market share accuracy). We will first prove helpful claim:
Helpful claim 1. For any 2 classifiers /1, fg with accuracies 01 d2, respectively, it stands that 612 > 821 4 ai > 02.
Proof. From Observation 2, 01 d12 = 821, meaning: = 02 + 812 821. Therefore:
02 + 01 02 2 0
2 02 + 812
821
02 2 0
e 812 821 2 0
+ 812 2 821
Where the 2nd inequality comes from substituting d1 02 + 612 821
We will now prove Proposition 2:
Proof. From Proposition 1, We know: ((h1l/22 a1 + 812, and u(hg]h1) a2 821
1hh1 h2) (h2 h))
d1 + 012 a2 d21
(13)
> 42
Where the last inequality follows from Helpful claim
Lemma 1. We will start with a helpful claim: Helpful claim 2. Let hi, ha E H. Then:
(hh)lh2) (heelh2) + 8n. > 1
U(halbi) > Uhi < 6n² > 2 55,
Additionally, the above inequalities hold if and only if jōn, -oaal < [812 + 821).
Proof. From Proposition we know that U(h (h1) jar, Ui,,,((h2lll (22) a2, U Uhhilhg) {(; diz). Therefore,
1 + - (a1 + 812)) (a2)
(hil)h2) > (122)122
+ a1 6hg > a1 8Nz
Sb
+ 8n 6, 8mm
(14)
+ 20n, dn.
+ 8n, > 8/z
2
Where the substitution of the RHS in the 2nd line comes from Observation Similarly.
Uhel)hg) Uhilhhi + a2 6r. > a1
+ 02 0bg > + 8m. 8nz
+ 8ng > 6n, 8n
(15)
+ 26n, > Öm
1
+ 80z2 > 5hn
Now assume that the inequalities hold, meaning 8n, 56 and 8ng fm Then,
13

---

A Market for Accuracy: Classification under Competition
3
0h1 > = Öhz
+ ōn > 8/12
2
2
2
6nz2
<
3 (8,, + +haa)
(16)
Similarly, 8n, < (ôn, + Óng). This means that max max(on, [2g) < [6); - δhz), and therefore jôn, 18gl < $ { + )mz).
[Note that all derivations apply both ways, meaning if [ō), ōhz
< [dh, + 6n2)) then on > foh, and òn > (0m
Using Helpful claim 2, the proof of Lemma I is almost immediate: from Observation 2 we know that ai 02 - =012 821.
The players will choose differing strategies in the 2x2 game if and only if ( (22) > U(h2 and ((12211) > Uhh1 [h), which holds and only if 5n, > 2 h5 and ō/2 > 2 2 which holds if and only if 1ō%, - Qhal < ( + 621). Since we know d1 - d2 = 812 821, this proves Lemma 1.
Theorem 1 (2x2 PNEs.) From the inequalities Lemma 1, we receive the conditions for which the providers play anti-coordinated strategies.
If one of these inequalities doesn't 't hold, meaning either (hg (ha) U (h22 h2) or (h2)(ha) < (ha)))))) then the dominant strategy is h1, h2, respectively, depending which inequality does not hold.
Theorem 2 (Threshold best-responses under MLR))
Proof. Firstly,we note that since g is continuous* and increasing strongly in [a, 6]. g).g-* g- is well defined.
We will split [a, b] into sub-intervals [a, h1, [h. b] and calculate the best response in each interval:
Let be the strategy we are responding to.
is clear that for all strategies in [a, h). the utility on all points in [h, bj is constant, since the classification on those points the same. So within the interval [a. h). the player is looking to maximize UjaAj. Similarly, when considering the best response in interval [h. b). need only maximize Up.oj since for all points in the interval Uja.) is the same.
Let Ufa h) It stands that Ahy E [a, hl:
1'' h h/ f1(()) fo(x)dde
1
(hi,)( -c=
This is straightforward expression of the utility. Any points outside [h1, h]] have identical classification for both h and h1 and so the only difference in utility is found inside the interval [41, li]. which hı classifies positive and h classifies as negative. Therefore the gain in utility Jh, fi (1))), but the loss on the negative points Jh, fo(x))d,, since the utility on those points would be otherwise shared with h.
Similarly, Vh, E [h, b]:
hhs (1a - c= S/m fo(x) - - (z)do 2
1
Therefore, BRio, (h) argmax U/a.0/ (hilh) argmax
argmaxx M (1x))) =2o(x))dr. hre(a.h)
krE(a,k]
And BR (h) = argmax U (hi = argmax 1h fo(x) - /
E
We will divide into cases based on the value of g(h):
We note that the theorem holds for categorical distributions well, where the provider will simply go the nearest point x g(()) the left, or x g(x) S doing a best-response to the right.
14

---

A Market for Accuracy: Classification under Competition
Case 1: 1/2 g(h) 2:
We will calculate a. Since is strietly increasing in [a, b]. the value fo(œ) ff((z) is positive for all points where g(x) 2 2- Therefore, vh, < 22 [a, M1, g(hi) 2 &/ then (ia.))(hi [/) z U (a.m)(22lt In this case: B (h) max (a, g. g (1/2)), since in the case where Wh1 E (l))) 2. then the maximum utility found at a.
Similarly, the same argument holds to derive that: B (h) = max (b,g-1(2))
Case 2: g(h) 2:
In this case, 1h1 > h stands that (hal())))))) < Up. (hlh), since the value fo(x) - [1)()) is negative for all points in [h, b).
Therefore the best-response found in the interval (a, h). in which case the derivation from the previous case holds, and so (a, (h) max (a. g (1/2)).
Case 3: ghh) < 1/2:
In this case, vh, h stands that (h, < ([o.n (h(h), since the value fo(æ) 1 (2:) negative for all points in [a, hl.
Therefore the best-response is found in the interval [h. b), in which case the derivation from the previous case holds, and B (h) = max (b,g-1 (2)).
So across all cases, we find that in the interval [a, 6]. there are only 2 possible best responses:
max (b,g-1 and min (a,g (1/2)).
Corollary 1.
Proof. Immediate from the fact that the strategy space of both players can be reduced to the 2 candidate best-responses stipulated in Theorem
Theorem (General threshold best-responses).
Proof. As in the proof of Theorem 2, We will split (a, b] into sub-intervals [o,, h1, [h, 6] and calculate the set of possible best responses for each interval:
Let be the strategyythresshold we are responding to. We will rewrite the explicit forms for Uja.0j:
Wh1 [a, hl:
1/ f1(x) fo(z)dr
(hall)-cc hb
Vhy b]:
(ha.)(hilh)-e- - 1'¹ h fo(x) 2 (x))dr
Where (ha.)((hh).
As explained in the proof of Theorem 2. to calculate the best response in [a, hi is sufficient to maximize Uja,3]; and to calculate the best-response in [h, 6). it is sufficient to maximize U
We will calculate the best response in [a, A):
Helpful claim 3. Let (h2, 122) be any open interval in [a, h| such that Vx E (h1, h22) it holds that g(x) > 1 2. Then Vx (h,, ha] > Uj..N] (hz h)) U(a.n((x(1))
15

---

A Market for Accuracy: Classification under Competition
Proof. Let a E (11,
Using the derivations above of relative market shares between thresholds, we will compare the market shares of and h1: (i.. U (x)h) = Jr fi(u) (u)ddu.
Since we are given that in the segment [/1, .r), 9 3. then folows that Vu, [1(()= - //((u) 0, and therefore the integral must be positive and hence U|a, (hx (h) Uja.Nj (= 0.
Helpful claim 4. Let (/1, (22) be any interval in [a, h| such that Vo E (f1,, h2) it holds that g(z) < 2'
Then Vo [h1, h2) - U|o_i (by h) ((a,)(
Proof. We will show that (o.. - (xll)()))h))))) >> 0. in a similar manner to Helpful claim 3: Let x E (h1, h2]. We will compare the market shares of x and hy: U (z))) -,00 fo(u) 2/ (u)du.
Since we given that in the segment [sc, h22,, 9 < 1.2 then it folows that Vu, So(u) - ///(u) O, and therefore the integral must be positive and hence (la,:(h2lh)) - [a. hn) 0.
Using the helpful claims, we can see that (Ra E (F
Let h1 $ (a, 1) U (1/2).
Case 111g1ghhg g(h1) > }:
Let (1, S (a, h] be the largest consecutive interval that includes h1 such that vh' E (Ir,) g(k)) 3.2 Since fo, fn continuous, then know is continuous. Therefore, either g(x) and g (a) > 0, a. From Helpful claim 3, receive that (z/hh) > (hilk, and therefore hi cannot be best response.
Case 2- s(11) :
Let (I, 3) C [a, /i] be the largest consecutive interval that includes f, such that Vh E (I, - g(h') < } Since fo, fi are continuous, then we know is continuous. Therefore, either g(y) = and g (x) > 0, or h. From Helpful claim 4, we receive that (u/,))(u(h) Uja.Ay(ha [h), and therefore h1 cannot be best response.
We define similar claims calculate the set of possible best responses in [f, b]: Helpful claim 5. Let (h1, h2) be any open interval in [h, such that Vx E (h1, h2) it holds that g(x) >
Then Va (hi, h2) > Up, (ha Ula,n (x)()).
Proof. We will show that (/ (x)1)))0/1))> > 0:
Let x h2]. We will compare the market shares of x and hy:
Vin,,j(all Un Sh f1() fo(u)du.
Since we are given that in the segment (zr, h2], >> 2, then it follows that Vu, (1) -o(()) > 0. and therefore the integral must be positive and hence Up. (ha /h) - Un. (x( > O.
Helpful claim 6. Let (h1, h2) be any open interval in [h, such that Vx (h1, it holds that g(x) < 2. Then Va E [11, + Uja,Ni (hz h) > (x14h.
Proof. We will show that Un, ( Ummaa(Z(1)) > 0:
Let (hi, hz). We will compare the market shares of x and h
16

---

A Market for Accuracy: Classification under Competition
(12l)))) (= - _- fo(u) - (fi(u)du
Since we are given that segment [xr, h2), < 2, then it follows that Vu, fo(u) [u) 0, and therefore the integral must be positive and hence U|,,o| (hg])) (n. (z/h) >
Using the helpful claims, Let 11 $ [6] (2).
that [R E PT
Case 1- (h1)) 2:
Let (1) S (a, b] be the largest consecutive interval that includes hy such that Aı (2r,y) g(h)> 2. Since Jo, fi continuous, then know g is continuous. Therefore, either g(x) and g (xx > 0, From Helpful claim 5, we receive that (xal)) > (hi.n)(hllh) and therefore h cannot be best response.
Case 2 g(h)) < 2:
Let (x. v) S [h. b] be the largest consecutive interval that includes h, such that Ah' E (x. - g(h)) < 2. Since fu. fi are continuous, then we know y is continuous. Therefore, either g(v) = 2 and g((x) > 0, or = b. From Helpful claim 5, we receive that U (ul,h( Uia,n1(h11 [h), and therefore f cannot be best response.
Proposition 3 (Convergence after round).
Proof. Let h be any starting classifier.
At timestep 0, we asume both players are at h.
At timestep 1, player plays h! BR(h), and player j plays h! BR(h)).
Let limin min( h3 Ammax = max hg).
Firstly, we will argue that there exists an caciual- classifier hopt such that hopt E [/ymain hmaz]]
Assume for the sake of contradiction that this isn't the case. Then there must exist some hapt either the left of hmin or to the right of hmann Let's s assume w.l.o.g that there exists some hopt >> hmman- Then u(hopt (bmin) > julhmann Ihmin): aopt > amaz by definition, and Sopt, men mmaz,min min, since when fmmnn < -mmax < hopts then 8max, min C 8opt.minn.
Therefore, exists some hopt E [hmins [maz]-
We now argue that (k4, h2) a PNE.
Assume without loss of generality h! < hopt- This generalization is without loss since we are proving a best-response equilibrium symmetrically for both thresholds, so it does not matter which player is on which side of hopt-
From the proof of Theorem 3, we know that hi
argmax
(hihho)))
hE hE P. (1/21}
[if ! = Nopt we are done.]
know then that ht 2 hopt-
Assume for the sake of contradiction that hj < hopt
Then 8p (ht) 5n² (h+) and from the optimality of hope: Gopt 2 an3, and therefore (hopplhh)) > U(h)lh?).
contradiction to h3 being best-response.
Now, h hopt > ht
We will argue h is a best-response to ht:
containment here refers to points that contribute to the values
17

---

A Market for Accuracy: Classification under Competition
wh (hopt: 11g, the utility of hopt is greater, similarly to how was argued above.
wh hopt: h a best-response to hopt then it must also be a best-response to h/, since the accuracy stays the same and the discrepancy grows in an equal amount for all classifiers hopt-
Therefore, both classifiers h h are best responses to each other and therefore are PNE.
Proposition 4 ('I improve, you improve").
Proof. From the proof of convergence in Proposition 3, we receive that in all threshold games, the players go to either side of an optimal classifter hopt-
Assume that player moved as initial best-response lij some hort Then player j's best-response hi is such that hopt between hç and hj. Since it BR, we know the market share of player increases (weakly).
For player i, from Proposition 1, 14 = (a: + ō.z)-
a; remains the same, but ōig increase because h3 went further away to the other side of hopts and as explained the proof of Proposition 3, opt Ónq.n3.
Therefore μi increases as well.
Proposition 5 (Market share increases during competition).
Proof. Assume the players started from ,::
()) aa
Let (h1, h2) be anyt equilibrium.
1(2) (a1 + 812) We will prove + 012 a:: Assume 01 + 812 < a. Then a + 6 > a1 + 012, contradiction f4 being a best-response to h2.
Corollary (Welfare increases during competition).
This is immediate from Proposition since SW Σn Hi.
Proposition 6
Proof. Let h1, h2 be any PNE.
Assume for the sake of contradiction that ((hılh2) > 2 ((h2lh1).
From Proposition we receive that ((hz)/)) = (a2 + 621).
We will show that y(h,/h)) [h1) f/ai > { 521) = p(h2 h1):
W know that ((h //2) 2 plh22 (h1) ai + 812 2 (a2 d21).
We also know 812 by definition of partial discrepancy.
Therefore a1 + aı 2 + و12 > 2 (az + 621)
And So: 41 > 42 + 52z = phha (b2) > p(hzlh2) contradiction to (h1, h2) being a PNE.
18

---

A Market for Accuracy: Classification under Competition
B. Additional theoretical results
B.1. Characterization of our problem sefting as a congestion game.
In Section 3, we mentioned that our problem setting is proven to have a PNE, a result shown by (Ben-Porat & Tennenholtz, 2019) through the use of an exact potential function. Additionaly, (Monderer Shapley, 1996) show that every potential game isomorphic some congestion game; this connection however is not always readily evident. We show here the exact reduction of problem setting congestion game, and highlight that the cost function is negative, which may be counterintuitive to more classic settings of congestion games.
Observation 3. Our problem setting is reduced to the congestion game (N,M, (H,) (G))EMM Where:
N is the number of players
M is the samples in the training set upon which the players want to gain market share
Hj the hypothesis class available to player
(y(a) = - is the cost function assigned to each sample, where & is the number of companies accurate on consumer j
Proof. Firstly, we will show that the game that is defined above is indeed a congestion game. We can observe this almost immediately, as the cost function (while negative) is monotone increasing with n2, and the cost is per-sample (equal for each player).
Additionally, the hypothesis class H; has a one-to-one function a: H P(M) which is a(h) (1r,)) M h(x) v). Therefore, each strategy h is equivalent to the strategy a(h) and this is subset of the facilities M.
From the game that is defined, we receive potential function & such that Vi, AΦ AC,.
The potential function is: (hh)= = プラ= Eks Ci( (k)
(For each sample, we take the sum of c(()),..c((n)), and since e monotone increasing, minimizing the potential means minimizing both players being accurate for the same classifier)
Now, will show that problem setting reduces to this game by showing the equivalence between maximizing the player utility in the problem setting and minimizing the player cost in the above congestion game, meaning, Vi, AU; AAC
Let of be the number of samples that player is accurate on along with k 1 other players.
We observe that
--
12
C.(h) Σ ((n
Σ c(k)
Σ 8
-U,
(ka)(h))
(where the middle equality comes from rearranging the samples bins of how many other players were accurate, and and then the cost constant in that bin).
C. Experimental details
C.1. Data details
All of the experiments on real data were studied on datasets: compas-arrest, compas-violent, and adult. The compas datasets originated from studies recidivism in the United States (Angwin et al., 2016), and are used to predict a criminal will be rearrested for general crimes and violent crimes, respectively. The adult dataset is used to predict whether the an individual's income exceeds $50K.
Preprocessing Details:
Adult: The adult dataset was imported in python through the uciml library. All of the categorical features were one-hot encoded, and numerical features remain unprocesssed. To enable balanced learning task, SMOTE resampling was
19

---

A Market for Accuracy: Classification under Competition
applied from the imblearn package to attain 50% positive class ratio. After the above preprocessing. 10,000 samples were chosen randomly, resulting in dataset with 10, 000 samples and 100 features.
COMPAS-Arres/Violens The COMPAS-Arres dataset was preprocessed for analysis by Marx et al. (2020), and a copy of their esv files are included their code. The esv files can be found at
https: / g thub. com/ charl p Ls/ prree/masted /data.
Both datasets contain d 21 preprocessed binary (previously one-hot encoded) features. The COMPAS- dataset contains 6, 172 samples and has a positive class ratio of 45.5%. COMPAS-Violent
The COMPAS- Violent dataset also originally had 6, 172 samples, however the positive ratio was 88.8%. Therefore
SMOTE upsampling was applied to the negative class to bring the positive ratio to 50%. The total number of samples for which we use COMPAS-Violent is then n = 10, 960.
C.2. Model Class details
For empirical anlysis, analyzed results of the experiments with 3 model class variants that were used as the effective strategy space of the service providers. We note that since the objective of this work is to understand the ability of providers to learn based on the importance of the samples, we kept the hyperparameter tuning minimal, so as not to forcefully overfit the data.
1. Linear SVM:
Hyperparameters: The regularization parameter C' = 1.0. Other hyperparameters were left as default. Hyperparameter tuning was performed on the values of C, but we observed no significant difference in the ability of providers to best-respond.
The model was implemented using the LiC class from the sklearn package.
sample weights from our method were passed using the sample weight parameter of the fit method.
2. XGhoost:
Hyperparameters:
Learning rate: 0.3
Max tree depth:
all other hyperparameters remained the default, in particular performing row and column subsampling of 1.
the loss metric used for boosting is log-loss
the model was implemented using the XGBClassi fier class from the xgboost package
We note that some basic hyperparameter tuning was performed using grid search, but default values yielded satisfactory results.
3. Random Forest:
Hyperparameters:
Number of estimators: 10
Max tree depth: the default, meaning all nodes were expanded until all of the leaves are pure or contain a single sample.
all other hyperparameters remained the default.
the loss metric used for boosting is log-loss
the model was implemented using the SandomforestClasssee class from the sklearn package
Hyperparameters were minimally tuned, and the default values were primarily used.
C.3. General implementation details
Test and validation set. For all experiments, the dataset was split into training, validation, and test sets. The test set comprised 20% of the data and was held out for final performance evaluation. The validation set, also comprising 20% of the data, was used for hyperparameter tuning when applicable. In cases where no hyperparameter tuning was performed, the validation set was not utilized, and so only the training and test sets were used.
20

---

A Market for Accuracy: Classification under Competition
Experiment Splits. To ensure integrity and mitigate the effect of random variations in the data, each experiment was conducted over 10 random splits of the dataset. For each split, the data shuffled and divided into training, validation, and test sets according to the above proportions. The reported results in the following sections include standard errors calculated across these 10 splits, providing an estimate of variability in the model performance.
Code. All of our code is implemented in Python. All of our experiments are reproducible and attached supplementary material.
Hardware. All experiments were run in the PyCharm IDE on a single Macbook Pro laptop, with 16GB of RAM, and M2 processor, and with no GPU support. However, the experiments to create the table metries were cumbersome on the IDE, and so the PyCharm heap size was raised 8K MegaBytes in order enlarge the stack. The total runtime for all the results takes roughly 12 minutes.
D. Additional experimental results
D.1. Main results for additional settings
In this appendix we showcase additional insights from our main results when tested on additional model classes
Table 3: XGboost performance
Adult
COMPAS-arrest
COMPAS-violent
min ç
max /
HHI
welfare
min /1
max /
HHI
welfare
min /
max l
HHI
welfare
+1.1%
+2.1%
+3.2%
+1.6%
+20.5%
+39.0%
+69.3%
+29.7%
+26.7%
+54.6%
+100.0%
+40.7%
providers
+1.7%
+3.3%
+5.2%
+2.6%
+34.5%
+57.8%
+105.8%
+43.0%
+35.7%
+68.9%
+120.5%
+47.7%
4
+2.4%
+3.8%
+6.2%
+3.1%
+35.3%
+66.3%
+116.1%
+46.4%
+36.3%
+66.1%
+125.8%
+49.8%
+2.4%
+4.6%
+7.2%
+3.5%
+37.2%
+78.0%
+122.0%
+48.1%
+43.3%
+68.6%
+128.6%
+50.8%
+2.0%
+5.0%
+7.2%
+3.5%
+40.2%%
+73.1%
+124.0%
+49.1%
+43.4%
+69.3%
+130.8%
+51.6%
XGhoost Table 3 shows the learning performance of the service providers when using XGBoost as the model class for training and inference. The details of the Xgboost implementation and hyperparameters can be found in Appendix C.2. A comparison of interest is the general improvements of the players relative to the Linear model class. We can notice that the welfare improvement, which is equal to the total market share all players, is significantly lower for both the Adult and COMPAS-ARREST dataset. This does indicate that the total welfare is lower, but rather that due the increased expressiveness of the XGboost model, the starting welfare began higher value.
Another point of interest is how the HHT (the measure of imbalance in market share between the providers) persists across model classes, regardless of expressivity. This further highlights the importance of taking into account the market dynamics and the order of play when competing with other providers.
Table 4: Random forest performance
Adult
COMPAS-arrest
COMPAS-violent
min y
max
HHI
welfare
min
max
HHI
welfare
min
max μ
HHI
welfare
+2.9%
+3.9%
+6.9%
+3.4%
+20.6%
+36.1%
+65.3%
+28.3%
+25.7%
+53.0%
+96.1%
+39.3%
providers
+4.1% %
+5.8%
+10.1%
+4.9%
+30.9%
+58.7%
+98.9%
+40.3%
+34.3%
+71.8%
+118.9%
+46.9%
+4.5%
+6.5%
+11.3%
+5.5%
+33.0%
+70.5%
+111.8%
+44.7%
+33.5%
+70.6%
+124.5%
+49.2%
+4.5%
+7.5%
+12.5%
+6.1%
+34.2%
+81.0%
+117.0%
+46.0%
+41.7%
+75.1%
+128.3%
+50.5%
+5.2%
+8.0%
+13,5%
+6.5%
+37.4%
+78.2%
+119.5%
+47.3%
+38.6%
+75.7%
+130.3%
+51.2%
In a similar manner, Table 4 presents the results on competition where the providers are employing a Random Forest model, whose details can be found Appendix C.2. We can observe that the results resemble those of the XGboost model class, which can be expected due to the similarity in nature of all Decision Tree models.
Random Forest
21

---

A Market for Accuracy: Classification under Competition
Standard errors of experiments As mentioned in Appendix C, each experiment was run over 10 train-test splits and the metric values averaged over those splits. Table portrays, for each metrie, the maximum variation of the standard error among the three model classes analyzed. We note that all of the errors are below 5%, and most of the errors are well below 3%.
Table Max standard errors of experiments across all model classes
Adult
COMPAS-arres
COMPAS-violent
min μ
max 4
HHI
welfare
min μ
max 1
HHI
welfare
min μ
max
HHI
welfare
2
+1.9%
+4.4%
+2.1% 1%
+2.6%
+1.0%
+2.6%
+1.2%
+ 113%%
+1.0%
+2.9%
+1.4%
#1.1%
# providers
+0.8%
+1.9%
+1.0%
+2.0%
+1.2%
+3.5%
+0.8%
+2.7%
+0.8%
+2.5%
+0.8%
+2.3%
4
#0.7%
+2.0%
+2.1%
+4.2%
+0.9%
+2.9%
+0.7%
#3.2%
#0.7%
+2.2%
+1.2%
#3.2%
5
+0.9%
+2.2%
+1.1%
+3.2%
+1.0%
+3.5%
10.7%
44.4%
+0.7%
+2.2%
40.8%
+3.6%
40.8%
+1.9%
+2.4%
+3.4%
+1.0%
+3.2%
10.8%
14.4%
40.6%
#2.1%
+1.0%
+2.7%
D.2. Competition Dynamics
Market Share In order provide more comprehensive analysis of how the market shares of the providers move through the best responses in the competition, Figure 5 shows, for each number of players competing for market share, the shifts in market share of each provider based on their positions in the game (order of play).
We can observe a few key points:
1. Market Stability. Across all variations of the number of players, the market shares of the player converge almost immediately to their final respective values. This convergence occurs even before every player offered single best-response, i.e, by the end of Round 1.
2. Order of play. In line with what expressed in Section 6.2, The order of play when offering a best-repponse important, and varies function of the number of players. For providers, playing second can offer a significant competitive advantage. When shifting to markets with n 2 3 providers, however, observe significant advantage the 1st mover, as discussed in Section 6.2.
3. General market share trend. Regardless of the order of play, and as alluded to in Table 3, the market share rises for players, which supports the empirical claim that providers that are competing are way collaborating to figure out how optimally divide the market.
4. Generalization to an unseen test set. The performance on the unseen test set closely mirrors that observed during training, highlighting the robustness of the competition method. The similarity in performance demonstrates that the model can calculate a best-response without overfitting, and underscores the ability of the framework to maintain accuracy in line with that expected from traditional MI. methods.
D.3. Welfare
Welfare behaviors in additional settings. Figure 6 shows the social welfares across the model classes described in Appendix C.2, namely LinearsVC, XGBoost, and RandomForest. The test welfares are shown for the COMPAS-arres dataset, and are portrayed for each model class and each game varying the nubmer of players. We can see that, as in Section 6.2, the welfare gets mazimized very early for the Linear model class, but hits a non-maximal plateau for the Decision Trees. This is another example of the non-monotonic nature of social welfare: in many cases providers having less expressiveness in their models will in fact benefit the consumers.
Welfare across asymmetry in data. The social welfare trends across different levels of data representations can also behave in a surprising manner, as shown in Section 6.2 and explained in great detail by (Jagadeesan et al., 2024). As a portrayal of this phenomenon across different competition settings, Figure plots the social welfares across experiments of 2,3, and 4 players, respectively. We can observe, that while no as blatant as with n = providers, the general trend across all player formats is that the social welfare increases as an inverse proportion the richness of the data representations.
22

---

A Market for Accuracy: Classification under Competition
payers gans
Thae
Tuxl
Poar
6.45
6:11
033
033
6:325
leet
0.31-
0.34
0.27
0.2
1.30
0.8
Plyer
Roar
0.88
01690
4322
Teat
Rlye
0.35
Plyer
0.5
0.3
0.8
8:34
1.31
mm
0.8
0.35
0.5
625
Figure 5: Competition Dynamics with XGboost models on the COMPAS Arrest dataset. Utilities of individual players are shown for Train (Left) and Test (Right), in markets involving 2,3,4,5,and players (Top Bottom)
D.4. Synthetic Data
In Section 6.1, we showed an example of the chicken dynamic between asymmetrical conditiood gaussians. Ad- ditionally, we performed an overlap analysis between symmetric gaussians, where for each measure of distance between the means, or overlap, we calculated the best-response thresholds and performance metrics. Figure 8 (Left) shows the above analysis on asymmetric gaussians, namely a-1 = 2, a 1. As Section 6. at each overlap the thresholds of the players are initialized ho hg hope, where hopt is the naively optimal classifier that maximizes accuracy on the distributions. Here too, and guaranteed by Theorem the best-response dynamics converge after just one round. In this case of asymmetry between the conditoondd gaussians, in the same proximity to hopt in the symmetric case, threshold h2 has a "tipping point", where it suddenly jumps to the far end of both distributions. From the accuracy graph we can also see a sudden drop in accuracy coming fromm model hg- In regards to the market share, however, the provider that gets a spike in market share is in fact the one who played h, and remains close to the optimal, while the market share of fa simply shows a gradual increase, with no reference to a tipping point.
notice distinctly different behavior. while h remains
23

---

A Market for Accuracy: Classification under Competition
Social Welfrre COMPAS arrest dotaset
LinearSVC
XGBoost
HandomiForest
1.69
2:35
0.50
0.55
0.69
2 paaes
2 papes
2 plpes playes
apcss
playcs
playes
Figure 6: Social Welfares across model classes on the test set for the COMPAS arrest dataset. Each plot calculates the social welfare at each timestep and for each experiment that varies the number of players.
This phenomenon is understandable when we look Theorem 3, that states that the best-response may be the far end of
f1(z) is the MLR the distributions. This occurs when either the values g (1/2), g 1(2) stops existing, where g(z) = fo(z)
function. In these cases, the left right threshold (depending on which value of y- disappears) will continue to gain by moving to the far end of the interval. This is precisely what is shown in Figure 8 (Right); at certain overlap (~ -1), there is no threshold h for which ((h) 2, and so the gain in discrepancy for h2 will continue to outweigh the loss in accuracy, and h2 ends up at the far right end. The market share of hı is then suddenly increased, since while its accuracy remains the same, the discrepancy from hg is now significantly greater.
D.5. Asymmetrical power between players
Another interesting question we can ask from the perspective of the learners/providers is, if a provider were to invest cost and effort to gain better data, how would this help them in competition? In naïve settings, i.e. single-provider markets, the answer to this straightforward: more data better accuracy. In accuracy markets, however, the specialization needs to be considered as well, and as we have seen (Section 6.2), the behavior of the market when altering the data quality can be counter-intuitive. To measure the gain to be had when improving data, ran experiments where one of the providers has access to more features than its counterpart/s. For each of 2 possible move positions (Ist or 2nd), two metrics were considered:
1) The provider's gain in market share over himself if he weren't to improve his data (i.e. the data is identical for all parties), which measures the provider's 's marginal gain from improving data
2) The provider's gain in Ap from the next-best provider versus the setting where he didn't improve his data, which measures
Social welfare different number of features
COMPAS arrest dataset
2 players
players
4 players
1.0
Welaar
0.9
0.8
0.7
0.6
2
Round
Round
Round
Figure 7: Comparison of social welfares on the COMPAS arrest test set when varying the number of features available to use for model training (and inference).
24

---

A Market for Accuracy: Classification under Competition
Tapt
N1
Thresholds
Rupe
1.00
0.75
0.50
Accuracy
0.50
0.25
Market Share
Piys
Pnng
poaa
Figure 8: Dynamics of the best-response game on threshold classsifiers with asymmetric gaussians. The metrics at each level of proximity between the gaussians are shown (Left). The thresholds at the "tipping point" (Right) can be seen to be very far apart. The hatches represent the sectors of exclusivity.
the impact of the data investment on the concentration of the market as a whole.
Table 6 shows the above metrics for markets with 2,3, and 4 providers, and for various possibilities of data improvement.
We can observe a few interesting trends:
1. Ap from regular setting. One of our central insights from Section 6.2 that when providers, moving second beneficial, and when 2, the opposite is true, and moving first is better. In the case of investing in better data, and when comparing the provider's market gain himself in regular setting, see inverse effect.
For better data creates market gains only when you the first mover, in certain lopsided markets the gain is 12%. For example, in the case where the better-data provider has 15 features, and the other providers have features, we can observe a 12% gain, which measures the benefit of investing in the additional 12 features.
When the provider moves second, however, investing in more data does not translate to higher market share, in fact the provider loses significant market share, and would have been better off retaining the same primitive data as the other competitors. This phenomenom gets exacerbated further the more the provider invests in better data; For example, if one were to utilize all 21 features of the dataset when the competitors have access to only features, the advatnaged provider would see a -12.3% loss market share.
For markets where n > 2, is the other way around. When the advantaged provider moves first, he may see a decrease in market share from the regular setting where he didn't it gain extra data; When moving 2nd, the data gain proves helpful. This stands in polar contrast to the case where n = 2, and perhaps understandably so: seems that wherever the providers have initial advantage when the data is symmetrical, they would lose that advantage when investing in more data, perhaps hinting at the idea of decreasing marginal returns in investments.
2. Ap from the next-best provider. When comparing the difference across data- variation experiments in market shares between providers, we notice that the trend behaves similarly to how we have seen the order-of-ple of-play results of Section 6.2. We can observe that, interestingly, if provider improved his absolute market-share relative to himself, this doesn't translate to the provider improving his market share relative to others. Take for example the cases where >> 2 and the provider moves 2nd. As stated above and can be seen in Table 6, the added data advantage in this setting helps the provider gain in absolute market share. The market gain relative to the other providers, however, has an inverse result, and in many cases the competitors end up with a better overall utility. This tells us that in these settings, when advantaged provider goes second, the total welfare (as the sum of individual market shares) increases.
25

---

A Market for Accuracy: Classification under Competition
Table Asymmetrical power between players. Results are shown for markets with 2,3,and providers, respectively. Rows shown for each choice number of features for the provider with better data,and the columns for the number of features of the other providers. Table results are shown for using XGboost trees the compas dataset, that contains 21 features in total.
# features of the worse data
Au from regular setting
Ay from next best provider
providers
move position
first
6
3.20%
14.37%
5.34%
12.82%
9.41%
4.76%
14.04%
12.21%
1.01%
12.66%%
9.15%
4.99%
0.48%
14.48%
12.41%
2.17%
-10.96%
18
11.85%
8.76%
5,43%
0.605
-0.33%
13.46%
11.86%
3.69%
-9.43%
-10.63%
21
10,
7.01%
2,53%
-3.44%
-3.42% -3.11%
9.98%
8.02%
-1.16%
-14.89%
-14.12% -13.96%
secund
4.98%
20.32%
-8.8%%
-1.38%
17.55%
14.03%
11.336%
-5. 26.6
+8.40%
15.92%
17.19%
5.15%
-13.95%
-5 626%
.9.91%
-0.33%
15.91%
17.74%
3.98%
12.64%
.1..55%
.6.17%
-10 28%
-1.32%
-0.81% %
14,88%
17.09%
3.53%
11.06%
10.35%
21
16.46%
.8. 38%
-12.35%
-3.29%
-2.97%
-2.27%
9.92%
13.09%
-0,89%
5.76%
5.74%
7.20%
first
-0.48%
51.86%
9
0.25%
1,93%
57.14%
55.024
15
-4.65%
-3.75%
-1.33%
-0.41%
45.18%
44.24%
31.88%
18.26%
-0.65%
21
100.55%
-7.13%
33.11%
-2.65%
22.56%
-1.44%
30.02%
37.01%
30.149
16.38%
17.40%
17.42%
-27
9
9.68%
9.78%
-11.53%
-8.90%
15.
12.55%
5.81%
-7.08%
-6.05%
-7.29%
15. 10%
12.33%
5.51%
0.47%
-8.34%
-7.49%
-8. 85%
-15.49%
14.97%
12.24%
5.40%
0.84%
-0.25%
-8.39%
-7.48%
-9.09%
-14.97%
-16.66%
21
14.63%
11.25%
5.74%
-0.04%
-0.11%
-0.42%
-7.84%
-7.53%
-8.84%
-13.25%
-13.49%
-12.83%
first
6
1.09%
24.08%
9 -12.59%
5.66%
+8.55%
13.93%
88.1%%
3.04%
0.82%
.1.02%
.0.21%
16.53%
-7.90%
2.01%
-3.05%
-0.67%
-0.51%
-1.725
9.94%
16.75%
18
-8 18%
2.04%
-2. -2.88%
-0.00%
-0.60%
-1.00%
-1.90%
11. 10%0
16.96%
15.68%%
-7 7.666%
1.64%
-3.96%
22%
-2.36%
-1.32%
-0.35%
-2.985
8.00%
12.08%
10.025
12.10%
second
6.64%
-11.54%
14.80%
11.58%
-1.52%
+0.20%
12 21.42%
16.05%
9.82%
-1.49%
-3.83%
-9.99%
18
21.03%
15.72%
9.24%
0.10%
0.46%
.4.97%
-4.63%
.10.51%
-16.32%
-15. -15.31%
-0.73%
26


Reviews:
[{"review_id": "gJ74ImApLe", "reviewer": "Reviewer_37Jm", "summary": "The paper studies a market where multiple model providers compete to provide accurate predictions to as many users (points) as possible. The theoretical analysis reveals several interesting insights. The main insight is that naively maximizing for accuracy is not optimal for either player. For example, if there are two players and both use the optimal classifier that is accurate on say 80% of the points. Since they are accurate on the same points their payoffs are divided into half. They can increase their payoffs by deviating from the optimal classifier and being accurate on subsets of points (subpopulations) exclusively. This dynamics of the market improves the payoffs of the players and maximizes the welfare of users. Thus overall the market benefits all parties despite the competition. These insights are also illustrated through experiments on synthetic and real datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback! We are encouraged that you found the paper well-written and that you appreciate our analysis and experiments.\n\n**”The biggest weakness is the assumption that the players know the predictions of other players…”**  \nIndeed, 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.  \nTo 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: \n\n- **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.\n- **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).\n\nOur 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.\nWe will add these new results to the Appendix.  \n\n**”In practice … players may not share the same data points”**  \nThis 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.\n\n**”Grounding in a specific application could help here”**  \nThank 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. \n\n**”Analysis in multi-player settings would make the paper stronger”**     \nFurther 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.\n\n**”Can the empirical results be provided for realistic applications?”**  \nOur 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.\n\n**”Absence of error bars in the numerical results”**  \nPlease 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.\n\n\n\nOnce 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.\n\n\n[1] Milchtaich, I. (1996). Congestion games with player-specific payoff functions.", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The methods and evaluation criteria are reasonable.", "theoretical_claims": "I checked a few (Proposition 1 and Theorem 1). I do not see any major issues in other claims.", "experimental_designs_or_analyses": "Both synthetic and real data experiments are designed to evaluate the theoretical claims. Overall, there are no issues in the design of experiments, and they support the theory. One issue is the absence of error bars in the numerical results.", "relation_to_broader_scientific_literature": "The paper provides novel insights into the accuracy markets.", "essential_references_not_discussed": "This is fine.", "other_strengths_and_weaknesses": "S1. The paper provides an interesting analysis of accuracy market dynamics. Naive intuition suggests each player’s best interest is in deploying the model with the highest accuracy. The analysis shows it is not true and all parties can maximize their utility by deploying models that are accurate on exclusive sets of points. \n\nS2. The paper is well-written with a clear problem setup and analysis. I appreciate the analysis in a 2-player setting and with 1-d threshold-based classifiers. The synthetic experiment results in Figure 1 helps in getting to the core of the market dynamics and why the claims made in the paper make sense. \n\n\n------\n\n\nW1. The biggest weakness is the assumption that the players know the predictions of other players on all points and they are learning models on the same data points (eq. 11). In practice such information is private to the players and they may not share the same data points.\n \nW2. While the analysis in 2-player setting is good as a first step and easier to understand. Analysis in multi-player settings would make the paper stronger.\n\n\nW3. I like the paper for the insights but I am not sure about the practical relevance as the setting and assumptions seem too unrealistic. Grounding in a specific application could help here.", "other_comments_or_suggestions": "1. Introduction is easier to follow after reading the setup and some of the empirical results. Otherwise, the setting and the dynamics of the game are not clear which makes it difficult to follow the introduction. I’d suggest making the introduction crisper and also introducing the setting and some examples (e.g. Figure 1) earlier.  \n\n\n2. In section 4, it would help to list the main claims clearly. It is likely that readers can get lost in a series of propositions and theorems.", "questions_for_authors": "1. In practice precise information of other players may not be known. In such cases how will the analysis and implementation unfold? Are there applications where the assumptions made in the paper are realistic? \n\n2. Can the empirical results be provided for realistic applications?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CP1vWAGRy5", "reviewer": "Reviewer_n7A1", "summary": "This paper studies equilibria in marketplaces when multiple firms are competing with each other for consumers. As compared to the prior literature in this space, this paper focuses on the dynamics of learning an equilibrium between two firms, as well as the impact on consumers and markets. Interestingly, this paper shows that firms can converge to a stable equilibrium relatively quickly, shows that firms can implicitly coordinate which markets they enter, and that increased competition helps consumers. It concludes with experiments on synthetic and real data. The paper is pretty clearly written and addresses related literature well.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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:\n\n**”It would be helpful if authors address how their work connects with work on algorithmic collusion”**   \nThank 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.  \nWith that said, there are some fundamental differences between their work and ours which bear consideration: \n- 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. \n- 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.\n- 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.\n\n\n**“It would have been interesting to have deeper discussion of the effect of capacity on competition”**  \nWe 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).\n\n**“How [would] the main results of the paper change given a wider model of classifiers?”**  \nThank 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.", "claims_and_evidence": "Yes - this paper is clearly written and makes a compelling contribution to the study of how firms can converge to (anti)-competitive behavior.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "One high-level takeaway from the paper is that firms effectively coordinate by independently deciding to compete in different markets. This occurs even though firms move sequentially and don’t coordinate explicitly. Given this result, it would be helpful if authors address how their work connects with work on algorithmic collusion, e.g. https://arxiv.org/pdf/2409.03956.", "essential_references_not_discussed": "See above", "other_strengths_and_weaknesses": "It would have been interesting to have deeper discussion of the effect of capacity on competition (discussed at the end of section 6). \nSimilarly, it also could have been helpful to have deeper discussion of how the main results of the paper would change given a wider model of classifiers (e.g. where MLR isn't satisfied).", "other_comments_or_suggestions": "N/A", "questions_for_authors": "See above", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9fpwFuEDMT", "reviewer": "Reviewer_jrJ7", "summary": "This paper defines a simplified economic model to consider how the dynamics of an “accuracy market” between multiple firms would play out. In this model, each firm has a model that makes predictions about a user, and users are assumed to choose a provider with the highest accuracy. The paper lays out several theoretical and empirical results. First, it shows that firms must consider both their own accuracy and the accuracy of other players in the market, adopting a weighted objective approach. Second, it shows that adopting this strategy benefits both the model providers and the users, as defined through a welfare metric. It then considers several datasets and experiments, including both with synthetic data and simple real world datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**Relevance to ICML:**  \nICML 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.\n\n**”The setting seems quite idealized for how ML actually happens in practice.”**  \nStudying 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.\n\n**”Why assume that there is only one prediction per user..?”**  \nWhile 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.\nOther 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.  \nWe 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.\n\n**”The main way to get more accuracy is to have more users and thus get more data”**  \nThis 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.  \nA 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.\n\n**”Is it possible to summarize the results in table 2 in a more visual way?”**  \nTo 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.\n\n[1] Pustejovsky (2019). Effective sample size aggregation.  \n[2] Kaplan, Jared, et al.  (2020)  Scaling laws for neural language models.", "claims_and_evidence": "I believe the claims made in the paper regarding the behavior of these idealized markets are supported both by the proofs and empirical experiments. My primary reservations with the work are regarding the assumptions and relevance to ICML, as discussed in the “Other Strengths and Weaknesses” section below.", "methods_and_evaluation_criteria": "As far as I can tell, the experimental setups make sense for the idealized market setting proposed in the paper.", "theoretical_claims": "I did not check the details of the proofs as they are outside my area of expertise.", "experimental_designs_or_analyses": "My overall impression of the experimental designs is that they are sound, but I did not have the opportunity to dive deeply into any code or data to verify further.", "relation_to_broader_scientific_literature": "The work seems to be primarily related to other work on algorithmic markets. In particular, the work seems to build on the 2019 Ben-Porat and Tennenholtz paper on regression.", "essential_references_not_discussed": "I am not aware of any essential references that were not discussed.", "other_strengths_and_weaknesses": "The strengths of this paper are its clarity and novelty. The paper does a good job of showing why, in this idealized setup, firms need to consider their competitors. Based on my limited search, it also seems as though this is the first paper to consider a market-based approach in the classification regime (although they do cite work that does similar treatment for regression models). Several results are formally proven, and I do think it is likely to inspire discussion among the right set of readers.\n\nThe primary weaknesses of this work are its relevance to ICML and its practicality. First, the work seems like it would be more appropriate for an economics venue than a machine learning one. While it does introduce an economic formalism to a machine learning topic, it feels much heavier on the economics side. I acknowledge that this may be due to my own lack of knowledge regarding economic approaches to ML, but I had a hard time following several parts of the paper despite being an experienced ML practitioner. I also note that the primary work that the paper builds on, Ben-Porat and Tennenholtz, was published at the ACM Conference on Economics and Computation. \n\nSecond, the setting seems quite idealized for how ML actually happens in practice. For example, I noted right away in equation (1) that the choice to have a model making one prediction per user seems odd - if there are firms competing over users (for example, in social media), they would likely be making several predictions about a user’s preferences, and those predictions in aggregate would influence the user’s choice of firm. There also does not seem to be much consideration of the effect that number of users has on the accuracy itself. Accuracy is not a quantity that can be purchased as in a traditional market - instead, the main way to get more accuracy is to have more users and thus get more data. I may have missed it, but I do not think that the model accounts for this relationship. I suspect that if it were taken into account, the market timing results would be different - a first mover would be more likely to be able to improve their accuracy more quickly because they have more data than competitors. \n\nBecause of its simplifying assumptions and shaky relevance to ICML, I would recommend that this paper be submitted to a different venue.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. Why assume that there is only one prediction per user in equation 1 (and 7)? Are there any settings where this would be true? \n\n2. Is it possible to summarize the results in table 2 in a more visual way? At the moment it is very hard to understand what is going on or easily spot the trends that are described in section 6.2.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rr4ayvxVPu", "reviewer": "Reviewer_GVZQ", "summary": "This paper examines a machine learning (ML) model market for classification tasks. Specifically, the authors assume that multiple ML model providers compete for market share. Each user in the market randomly selects an ML provider that delivers an accurate prediction, and the market share of each provider is defined as the expected number of users choosing its model. The authors analyze the fundamental properties of best-response classification in simplified 2 × 2 accuracy markets and markets with threshold classifiers. They show that best-response classification can benefit both ML providers and consumers. Additionally, they propose an approach to effectively solve best-response classification using real finite samples and predictions from other ML providers. Synthetic and real-world experiments validate the theoretical findings.\n\n---\n\nI remain the score unchanged after rebuttal.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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:\n\n**”Best-response classification may be impractical in real-world settings since ML providers typically lack access to competitors’ predictions”**    \nIndeed, 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.  \nTo 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: \n- **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.\n- **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).  \nOur 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.   \nAdditionally, 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:    \n\n|   |  # research points| 100  (2.7%) | 200  (5.4%) | 400 (10.8%) | 800 (21%) | Full information |\n|:-----------:| --|:----------:|:----------:|:----------:|:----------:|:----------:|\n| **# providers**   |   |  |  |  |   |    |\n| $n=2$    |   | +17% | +21%   | +23%  | +26%   | +29%   |\n| $n=3$    |   | +25%   | +33%  | +35%  | +37%   | +42%  |\n|   $n=4$  |   | +34%  |+38%  | +42%  | +44%  | +46%  |\n| $n=5$    |   | +38%  | +42%  | +45% | +47% | +48%  |\n| $n=6$    |   | +41%  | +44%  | +46%  | +48%  | +48%  |\n\nThese 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.\nWe 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. \n\n**”Extending the theoretical analysis to a general N-provider setting would strengthen the paper”**     \nFurther 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).\n\nThanks 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.", "claims_and_evidence": "**(Pro)** The theoretical results are generally sound and are supported by both theoretical analysis and experiments.\n\n**(Con)** Best-response classification may be impractical in real-world settings since ML providers typically lack access to competitors’ predictions. While Equation (10) only requires information on the number of accurate predictions for each sample, obtaining this data in practice remains challenging. It would be helpful for the authors to discuss the implications of cases where this information is unavailable or biased.\n\n**(Con)** The theoretical results are primarily based on the $N=2$ setting. However, in real markets, the number of ML model providers is often much larger. Extending the theoretical analysis to a general $N$-provider setting would strengthen the paper.", "methods_and_evaluation_criteria": "**(Pro)** The proposed method is theoretically sound and validated through experiments.", "theoretical_claims": "I did not verify the details of the theoretical claims, but the results appear to be generally sound.", "experimental_designs_or_analyses": "**(Pro)** The experiments are well-designed to validate both the theoretical findings and the proposed method. They also explore more general settings beyond those covered in theory, which is valuable.", "relation_to_broader_scientific_literature": "Compared to Ben-Porat & Tennenholtz (2019), this work focuses specifically on classification problems and provides a more detailed analysis of best-response dynamics.", "essential_references_not_discussed": "No essential references appear to be missing.", "other_strengths_and_weaknesses": "No additional strengths or weaknesses were identified.", "other_comments_or_suggestions": "**(Pro)** The paper is generally well-written.", "questions_for_authors": "See the concerns listed above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewer consensus is that this paper makes an interesting contribution by studying the interplay of competition and model accuracy. They find the paper to be well written and supported.
Decision: Accept (poster)