Learning Classifiers That Induce Markets
Authors: Yonatan Sommer
Ivri Hikri
Lotan Amit
Nir Rosenfeld
Venue: ICML 2025 poster (2025)
Keywords: strategic classification
learning-induced markets
Primary area: social_aspects->robustness
TL;DR: strategic classification assumes costs are fixed and predetermined; instead, we model costs as arising from a `market for features' induced by the learned classifier

Abstract: When learning is used to inform decisions about humans, such as for loans, hiring, or admissions, this can incentivize users to strategically modify their features, at a cost, to obtain positive predictions. The common assumption is that the function governing costs is exogenous, fixed, and predetermined. We challenge this assumption, and assert that costs emerge as a *result* of deploying a classifier. Our idea is simple: when users seek positive predictions, this creates demand for important features; and if features are available for purchase, then a market will form, and competition will give rise to prices. We extend the strategic classification framework to support this notion, and study learning in a setting where a classifier can induce a market for features. We present an analysis of the learning task, devise an algorithm for computing market prices, propose a differentiable learning framework, and conduct experiments to explore our novel setting and approach.

Learning Classifiers That Induce Markets
Yonatan Sommer' Ivri Hikri
Lotan Amit Nir Rosenfeld
Abstract
o' incurs a cost to the user. These costs are typically mod- eled via a cost function c(æ, x²) that underlies user decisions, and hence governs strategic behavior. The vast majority of the literature considers costs as predetermined and fixed; even if unknown to the learner, costs are still assumed to simply 'exist'. But where do costs come from, what form do they take, and how do they come to be? Challenging the conventional assumption of exogenous costs, our works sets out to propose and study alternative cost mechanisms.
When learning is used to inform decisions about humans, such as for loans, hiring, or admissions, this can incentivize users to strategically modify their features, at a cost, to obtain positive pre- dictions. The common assumption is that the function governing costs is exogenous, fixed, and predetermined. We challenge this assumption, and assert that costs emerge ing a classifier. Our idea is simple: when users seek positive predictions, this creates demand for important features; and if features are available for purchase, then a market will form, and compe- tition will give rise prices. We extend the strate- gic classification framework to support this notion, and study learning in a setting where classifier can induce market for features. We present an analysis of the learning task, devise an algorithm for computing market prices, propose a differen- tiable learning framework, and conduct experi- ments explore our novel setting and approach.
result of deploy-
One such alternative, and the focus of our paper, is the idea that costs materialize through market forces: the clas- sifier creates demand, suppliers set prices, and users pay for items or services that aid them in securing positive pre- dictions. As an example, consider university admissions, which often rely on standardized test scores (c.g.. SAT), Since these affect acceptance decisions, students are incen- tivized to improve their scores; this, in turn, has created a (billion-dollar) market for preparation courses. We posit that the price of such courses is determined by the importance of standardized tests as a feature in the decision rule for admission: if a policy update changes the relative weight of test scores, then prices should adjust accordingly.' ! Note that such changes also affect who will-and even who can- such costly courses. This, in turn, can affect the eventual composition of admitted students. If a learned classifier is to be used to inform such decisions, then learning must be aware of, and accountable for, the market it fosters.
1. Introduction
Strategic classification (Hardt et al., 2016; Brückner al., 2012) considers learning in a setting where users can strate- gically manipulate their features to obtain positive predic- tions. This applies to tasks such as loan approval, job hiring, school admissions, insurance claims, and welfare benefits, in which the interests of users (e.g.. getting the loan or being hired) may not be aligned with the system's learning objec- tive of maximizing accuracy. The primary goal of strategic learning is to train classifiers that are robust to such respon- sive user behavior, an idea that has gained much recent traction (see Sec. 1.1 for partial list of related work).
Our paper formalizes this idea and applies it to the frame- work of strategic classification. When users seek positive predictions, this creates demand for features that are im- portant for classification; and if features are available for 'purchase' from sellers, then a competitive market is formed. The cost of obtaining features is then determined by their market price, which is reflective of their market value, and users can purchase any bundle of features whose price is within their budget. Crucially, prices are not given nor pre- determined; rather, they depend on the learned classifier through how shapes demand, as it relates to the entire data distribution. This means that obtain a strategically robust classifier, learning must be able to anticipate the market it induces. We refer to this as market-aware classification. To
A core assumption of strategic classification that feature manipulation is costly, i.c., that modifying x to some other
Equaa contribution Faculty of Computer Science, Technion - Is- rael Institute of Technology, Haifa, Isracl. Correspondence to: Nir Rosenfeld <nirr@es.ce es. all.......c....
Proceedings of the 12nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
'Frr broader discussion on changes in SAT policy they relate strategic behavior see Liu & Garg (2021).

---

Learning Classifiers That Induce Markets
facilitate learning in this setting, we (i) define 'a market for features', as it relates to the learning task; (ii) characterize an appropriate notion of price equilibrium; and (iii) study the task of learning strategic classifiers that induce markets.
hold most of the aggregate budget, then prices will be low, negative points will cross the decision boundary-and accuracy will be reduced. Thus, since classifiers gain power over the induced market, maximizing accuracy will often be achieved by learning classifiers under which positive predictions are indirectly associated with high budgets. This raises natural questions regarding socioeconomic equity an important yet underexplored notion of fairness.
Learning in our market setting admits two key challenges. First, since market prices rely on the aggregate demand of all users, the behavior of users becomes dependent through the market mechanism. This is in sharp contrast to the stan- dard setting in which users respond independently and the objective decomposes over training examples. As we show, this can have a stark effect on learning, since even points that lie far from the decision boundary can still have a significant impact on market prices, and hence on the behavior, of oth- ers. Fortunately, a useful property of equilibrium prices is that if the market is efficient, then prices reflect all relevant information. In our setting, this implies that conditioned on prices, the objective does decompose over users. This allows us to adapt standard techniques for strategic learning with (independent) user responses to handle (dependent) market-inducee cost functions. Our second challenge is therefore to compute market prices effectively and as part of the training pipeline. For this, we first give an algorithm for computing prices exactly, and show that it is efficient. We then propose differentiable variant of the algorithm that computes 'smooth' prices, which enables end-to-end optimization of the entire objective using gradient methods.
1.1. Related work
Strategic classification. The field of strategic classifica- tion (Brückner et al., 2012; Hardt et al., 2016) has gained much recent interest. This has led many advances both in theory (Sundaram et al., 2021; Zhang & Conitzer, 2021) and in practice (Levanon & Rosenfeld, 2021). The original for- mulation includes several strong assumptions, in particular regarding costs, which subsequent works have challenged or relaxed. One line of research considers learning under unknown (but nonetheless fixed) costs, including in the on- line (Dong et al., 2018; Ahmadi et al., 2021), multi-round batch (Lechner et al., 2023), and one-shot (Rosenfeld & Rosenfeld, 2024) settings; under personalized costs (Lech- ner et al., 2023; Shao et al., 2024) and for general manipu- lation graphs (Ahmadi et al., 2023; Cohen et al., 2024). A related thread relaxes assumptions on user-side information, but focuses on uncertainty regarding the classifier rather than costs (Ghalme al., 2021; Bechavod et al., 2022; Bar- sotti et al., 2022). Another assumption is that users respond independently; this has been relaxed by injecting depen- dencies through the utility function in a ranking task (Liu et al., 2022), or through the model class by making use of a network structure over users (Eilat et al., 2023). In a recent work, Hossain et al. (2025) augment the cost function to include externalities, which entail dependencies. Our work proposes that user behavior becomes dependent through a market mechanism in which demand, and therefore prices, derive from the classifier.
Using our approach, and via both synthetic and semi- synthetic experiments, we proceed to explore the effects of induced markets on learning and its outcomes, Our main re- sults here twofold. First, we show that markets can give rise to complex behavioral patterns that differ significantly from the conventional strategic setting. Under a fixed cost function (e.g., some norm), whether a point will move or not depends only on its distance from the decision boundary. Conversely, since market prices are adaptive, the cost- effectiveness of moving for any given point depends on the aggregate demand induced by the particular classifier. This means that which points move and which don't 't can follow highly irregular patterns, and in some cases counterintuitive. One example is that 'raising the bar' on acceptance by increasing the threshold- a common approach to combat strategic behavior-can cause more points to cross. Another surprising outcome is that unseparable data can become separable. This can occur when (i) budgets correlate with labels, and (ii) prices discriminate against low- wow-budget users.
Learning and markets. A large literature considers mar- kets for data (e.g.. Agarwal et al., 2019; Ghorbani & Zou, 2019; Chen al., 2022) or trained models (e.g.. Chen et al., 2019; Huang al., 2023). A recent line of work studies competition between platforms or service providers (Ben- Porat & Tennenholtz, 2017: 2019; Guo et al., 2022; Ja- gadeesan et al., 2023; 2024; Shekhtman & Dean, 2024; Einay & Rosenfeld, 2025). Here learning is used to elicit user preferences, e.g. towards making useful recommen- dations (Hron et al., 2023; Eilat & Rosenfeld, 2023). In contrast, our setting considers how learning creates mar- ket, where the commodity is features. The idea that features affect demand has been considered in Nahum et al. (2024), but for market decongestion via feature selection and in a different setting. Closer to ours in spirit, Hardt et al. (2022) measure the power of learning to shape outcomes through
This drives our second result, which is that budgets play a distinctive role in shaping learning outcomes. Our frame- work makes a distinction between what users have (i.c., their features) and their economic stature (via their budget). Here we show that learning tends to favor users with larger budgets. The mechanism for this is indirect: if the classifier separates the data well but in way that negative points
2

---

Learning Classifiers That Induce Markets
predictions that cause a distribution shift. However, they target a general performative setting in which neither mar- ket nor user incentives are explicitly modeled. Epasto et al. (2018) study data-driven algorithms for mechanism design (e.g., auctions) in which rational agents can misreport infor- mation (e.g., bid untruthfully). Interestingly, they conclude that learning a mechanism is possible if misreporting bears a cost to users as in strategic classification.
can buy features (but cannot sell), so that 6 2 0: together with p 2 O, this ensures Cp cp(5) 2 0 always. 2 Rather than assuming prices are fixed and given, our main innovation is to let p be determined by forces of supply and demand.
Sellers and market prices. Our setting assumes there are d distinct sellers, ; 8d, where each seller s, sells fea- ture i exclusively and can determine its price pt. The goal of each seller is maximize her expected revenue, defined as:
2. Setup
r; (p) = Pt (x:
(4)
Strategic classification. In standard strategic classification, users are described by features x E Rd, and have binary labels y E {0, 13. Given a sample set of pairs (x, y) drawn iid from some unknown joint distribution D, the goal in learning is find a classifier h from some model class H whose predictions i h(x) obtain high expected accuracy on future samples. Our focus will be on linear classifiers, (z) = sign(w' (w + T). The challenge in strategic learn- ing is that users can 'game" the system by manipulating their features to obtain positive predictions. In particular, given the classifier h, users are assumed to be rational and there- fore modify their features via the best-responss mapping:
where 6; is the amount of feature purchased by user at prices p. We consider a setting of unlimited supply (e.g.. as in digital goods) and in which users can purchase any real quantity of any feature, 6, E R. Vi e [d].
Note revenue to seller s; depends not only on its p.. which it controls, but also on all other prices, p-i. which are set by other sellers. As such, we will assume that prices reach equilibrium, denoted p* = (Pi,...., maximii-a in the sense that no seller s; can improve her own revenue by changing Pt. given that all other prices remain fixed. We refer to pd as 'market prices', and will define them precisely in Sec. 3. A erucial point is that market prices depend on the joint demand for all features, aggregated over all users. This, in turn, is shaped by the choice of classifier, as we describe next.
which is
An(x) argmax h(2²) - c(xxx²)
(1)
where h(x²) E [=1} is their utility gained from prediction outcomes on the modified input, and c(xx, x²) is a cost function that governs the costs of changing x to any other x'. The goal is then to learn a classifier h that is robust to such strategic responses, and the strategic learning objective is:
Classifiers that induce markets. Since by Eq. (1) utility
to users derives from their prediction ÿ = h(x)). any user x who is classified as negative (i.e., has l(xx) = 0) will be interested in purchasing additional features
(81,... ... 88)
argmin ED (v # M[ x²= ===And An(z)) (2) bеR
if this results in flipping her prediction to h(:: + 6) = 1. The
demand set of user therefore includes all 8 for which:
Market setting. Our setting builds on the above to allow for the formation of market for features. To generally enable transactions, we require two additional structural assumptions. First, we assume features describe tangibles; this means that each Ø[}] 2 O, and that a larger value means having 'more' of feature i. Second, we assume each user has an (individualized) monetary budget 2 which limits the amount they are willing spend (or, equivlently, the value they attribute to obtaining positive prediction). This extends the joint distribution to be over tuples (I. b, v) ~ D.
w (ar + +++)++ + 0 and 5 spsb b
(5)
Overall demand is then given by aggregating all such over the collection of all users, and market prices p* are set by sellers to maximize revenue under this global demand set.
Notice how demand, and therefore prices, depend on the in- teraction between the data distribution (i.e., all pairs (I, b)) and the classifier h (via w and r). In this sense, we get that each choice of classifier induces a market. We will hence- forth use pd == p" (h: D) to denote the classifier-dependent cquilibrium prices that govern user responses in the market.
Apart from these, the only distinction of our setup is that we use a particular cost function to express market costs. We will make use of linear costs (Hardt et al., 2016); given a vector p= (pi.....PP) .P)) 2 and for 5 x' xr define:
Strategic learning objective. Given a sample set ((x;, bi, }: drawn iid from D, we will be interested in learning a classifier that maximizes expected accuracy under the market it induces. This requires us to anticipate how users will respond: for a given h. plugging Eq. (3) into
cp(z,x') x') (0) = 8 STD p
If we consider 5 as a bundle of features, then we can in- terpret p as a vector of prices, where each p3 is the price of purchasing one unit of feature i. We assume that users
Note this circumvents an artifact of linear costs, made apparent in Hardt al. (2016), which is that points can move 'for free' in any direction (and hence to any distance) that is orthogonal to er
3

---

Learning Classifiers That Induce Markets
standard setting
market setting
price computation
market costs
different classifier
h
(A)
h
B
(C)
h
(D)
(E)
Ax(
4
4markes (x)
8
Bi 5,000
Amarket (x)
st G,(0)
Figure 1: Strategic classification under market costs. (A) In the standard setting with predetermined norm costs, each classifier h induces fixed region of points that will cross (light grey). (B) In our market setting, points have budgets b (circles), and their distance to h determines their demand 8 (dashed lines). (C) Demand for all users is projected onto single demand space (top) and then normalized by budgets (bottom), over which exvenue-maximizing prices p" are computed. (D) Under market costs, points move if their budget permits buying sufficient features, and do not move otherwise. (E) A different classifier ''' creates different demand, and therefore induces different prices p" This can result in different points moving.
Eq. (1) gives the market best-response mapping:
down into three steps: First, compute ý = h((r), and pro- ceed only if g 11. If so, then second, find the least-costly 8 that gives a positive prediction, this by solving the LP.
A h
Market
(x, b) + dg:
6² = argmax M6 + 6)
500 (0)
820
8, = argmin ōT p s.t. w (x) -T=
(8)
which satisfies budget constraints implicitly. Given Eq. (6) can be interpreted as each user having individualized costs Ca (0) & Cp (6). Nonetheless, crucial point is that when h is learned, individual best-responses Amarket (ar b) be- come dependent on all other users, since p" depends on the distribution D through the learned h. Thus, users respond as a collective-not independently. Fig. illustrates the
820
Third, apply x² = x + 6, iff budget permits, i.e., 6_ p S b.
To understand 8_, consider a change of variables in Eq. (8)
using 2, 6,w; The LP can now be rewritten as:
d
process in comparison to standard strategic classification.
argmin =20
Pi 24 Wi
s.t.
Σ
24 Riz
Given Eq. (6), our strategic learning objective is:
argmin ED [y + H[ xh = Ap (I, (7)
where the constant Ka = -ww TT x is non-negative for relevant points (i.e., having á = 11). This provides an alternative interpretation: the user must allocate K2 mass across features, using z, to minimize total cost-per-value, where 'values' correspond to entries of w. This has a simple solution. which to set 2 = Kg if attains the minimal ratio pi/u;, and 0 otherwise. If multiple features attain the minimum, then these features are substitutable, and so any allocation of z among them is equivalently optimal. In other words, users will purchase only the most cost-effective features, but are indifferent within this set of features.
hell
which in practice we will replace with an appropriate empir- ical proxy (Sec. 4). Note h is a function of features alone and not of budgets; thus, we assume budgets are observed at train time, but at test time are private to users, and affect their computation of zh, This makes Aparket a special case of the generalized response model proposed in Levanon & Rosenfeld (2022) which supports private information, albeit with cross-user dependencies (which are unsupported).
3. Market Prices: Analysis and Algorithm
How prices adjust to demand. Given the above, we next consider how sellers should set prices. Notice how by Eq. (9). all user decisions depend on the ratios pi/w;; and differ only in the constant K.. Since all users buy only the most cost-effective features, any s, whose ratio is not min- imal will receive zero market share. Sellers therefore com- pete over who attains the minimal p./ p//w, Since sellers in our setting have no capacity constraints or production costs, we assume sellers have foresight and so coordinate to prevent
Optimizing Eq. (7) requires the ability to anticipate how users respond to the market. By Eq. (6), this can be achieved by computing induced prices p² Our first task is therefore to compute market prices for given h. We begin with ana- lyzing the market, and then give an exact pricing algorithm.
How users respond to prices. Given a classifier h and a general price vector p. how will users behave? To gain in- sight, we will first consider the case of w > 0, and later gen- eralize. Notice that computing ztt in Eq. (6) can be broken
Since users minimize costs, we can use an equality constraint.
4

---

Learning Classifiers That Induce Markets
Algorithm 1 Exact empirical market prices
Observation 1. Let is and S, then for a given user x, and for any p RR her demand under prices p pro is:
1: input: classifier hw sample set S = {(1, bt, 31 )/ (revenue), U- (total units sold)
2: initialize:
3: for = I,..., do
= dist' (a;; h)) .mxx { 0,
w x +
(12)
4: u; 1 dist (I:;; h)
|w|
5: ū; 1 u//b;
6: (#(1),..., [((m) t sort (w1,t.. )m))
Here the max over ensures that demand is considered only for relevant users, i.e., for which f(x)) -1. This transition to units of demand lays the ground for our algorithm.
7: for i = -I,..,, m do
8: P: +- (
9:
U + U + ((()
Exact aglorithm. Algorithm 1 provides pseudocode for an algorithm that efficiently computes the optimal (scalar) prices ý for given h and S. Our key observation is that it suffices to work with units-per per-budger, defined as ū, = uz/b; for each user I;. The first steps are therefore to project demand onto w. obtain all us and normalize by b; to get ū, Correctness of the algorithm follows from the next result:
10:
if p;U > then
11:
r r+ T+P;UU
12:
P Ps
13:
return: P - D. w/ |wll|
price collapse.* 4 This gives the equilibrium condition:
Theorem 1. Given (uni-dimensn dimensiensionll demand {(us, be) } the revenue- maximiina price is أ = u,, for some i* E [m].
ViE [d],
Pi W/
= > 0
(10)
for p" that admits maximal total revenue, r r= E: r.. This implies a tight connection between the classifier and prices: Proposition 1.
Proof. It suffices to show that the set of all local maxima of revenue (as a function of p = ") correspond exactly to the set of points (ū.1) ====- Assume w.l.o.g. that u,² are ordered. Then for any interval (0, ..,71)). revenue is linear in pt this is since for all p in this interval, the set of users that purchase are precisely j = 1,...,2, ja units at price p. Next, notice that at any p u increasing p infinitesimally causes i to not purchase, since she can no longer afford her required units at budget b;. and revenue exhibits a sharp drop. Thus, revenue is discontinuous peice- wise linear with increasing segments between the u,
Let h(x)= sign(wTx++ +T), then there exist equilibrium market prices p" that are proportional to w:
p" D); = p²
(11)
each purchasing J
for some p" E IR., which also depends on h and D.
The particular equilibrium in Eq. (11) will become highly useful for our method in Sec, 4. Interestingly, for the purpose of learning, prices can be computed as in Eq. (11) even if some entries in w are negative. This is because for every there exists a price vector p' 2 0 such that (i) p' an equilibrium price, and (ii) outcomes under p" and p' the same, i.e., the same set of points cross. Intuitively, this is due to items being exchangeable; see Appendix A.1.
Fig. 2 illustrates the structure of revenue as a function of price. Thm. implies that it suffices to compute r at prices P: = 1/û; for all E [m]] choose the maximizing i", and set I = P We will henceforth refer to the user i" as the price setter. Sorting by ū, makes this process efficient: at price pt. the set of point who purchase are precisely for which ūj S up-
Computing empirical market prices. Given a classifier h and sample set S = {(2,, 6,, m we will be interested in computing evenue-maximizae
ū₁ Since revenue i is p.U = ps Σū su, üjj date U on the fly as cumulative count of total units bought, and multiply by price, giving runtime of Om log m))
market prices. Because we only have a sample at hand, our goal will be to compute optimal empirical market prices p. Applying Eq. (11) to the empirical distribution over S, we get that p fo for the scalar و which maximizes total empirical revenue, denoted A. This is highly useful, since the problem of computing cquilibrium for the empirical market under a given h reduces to optimizing over scalars E R.
One interesting observation is that prices are agnostic to scale: we multiply demand (or budgets) for all users by a constant, then prices will scale inversely (proportionally). Such "change of curreney" has no effect on user responses.
4. Learning Approach
By Eq. (11) we can find market prices in the direction of w. The demand of a user is the (directional) distance from x
We now turn to the question of how to learn an accurate classifier on the market distribution it induces. Our general approach will be to follow the empirical risk minimization framework and replace the expected risk in Eq. (7) with an
to the decision boundary of h. measured in 'units" E R...
"This essentially Bertrand's paradox, for which invoke the folk theorem to enable the formation of cooperative equilibrium.
5

---

Learning Classifiers That Induce Markets
given p. this is the amount of units that each user i can buy, namely bs/ p. This gives our proposed market hinge loss:
empirical revenue data points ú;
0.4
revenue
hm-inng (2, y h p) - mnxx(0, 1 y(w T x + x
| I))
0.2
(15)
A primary benefit of lm hinge is that does not include A ex- plicitly. Furthermore, it requires only the scalar market price p (which depends on h). Our final step is to replace P with differentiable market price as smooth approximation. This is achieved by making Algo. 1 itself differentiable full details see Appendix. C. The relation between the market hinge and the 0-1 loss is explored in Appendix B.
0.0
0.0
0.2
0.4
0.6
0.8
1.0
price (p)
Figure 2: Empirical revenue as a function of price. Rev- enue increases before each ū,- and drops immediately after, implying the argmax is attained at some i" E [mn] (Thm. 1).
5. Learning in Markets: Exploratory Insights
empirical proxy objective over the sample set S, namely:
In this section we use synthetic experiments to demonstrate the basic mechanics underlying how learning creates mar- kets, and how induced markets affect learning outcomes. As we show, such effects can be quite stark. We begin with ques- tions regarding fixed h, and then consider / that are learned.
argmin hEHl
(e xi = = (Iz
by)
(13)
Here l is a surrogate loss (c.g., hinge), Ri is an (optional) reg- ularization term with coefficient A, and responses A Aaareet defined w.r.t. empirical market prices, P = p" S):
5.1. Typical market behavior
Challenges. There are several challenges to optimizing Eq. (13). First, as in standard strategic classification, A is an argmax operator, which is non-differentiable and even dis- continuous. Second, in our market setting, the objective no longer decomposes over examples, since how each 2; moves now depends on all points in S through p. Third, prices p de- pend not only on the data, but are also a function of h, which is the target of optimization. Finally, it is unclear what are appropriate choices for E and R since strategic learning often requires using specialized proxy losses and regularizers.
Given a classifier h, how will the market respond? Let g be the distribution over demand-budget pairs (u, 6) induced by h. By Sec. 3, q fully determines prices. For our following analysis we will focus on g that are simple, parametric, and well-behaved. We first consider uniform budgets, and then move to heterogeneous budgets that vary across users.
Uniform budgets. When b 1 for all users, and so ū u, users are naturally 'ordered' by their demand. From Sec. 3, this means that if u is the revenue-maximizing point (i.e.. the price setter), then all users with u S u² move, and all others do not. This is similar to the standard setting (with fixed costs and uniform budget), only that the threshold on who will move is now adaptive (u") rather than fixed (7).
Approach. Our solution will be to replace A with differentiable proxy that permits to take gradients 'through the market'. First, notice that conditioned on prices, user updates x become independent; this is precisely role prices play in any efficient market. Next, we define e. While there are no known strategic losses for linear costs-even with fixed parameters--uuppiinnggll we show it is possible to adapt the strategic hinge (Levanon & Rosenfeld, 2022):
Since only the closest users the negative side of h move, the main question here is how many of them will be deemed as sufficiently close by the market. Fig. 3 shows revenue curves for several demand distributions, depicting the subset of srggatieel-classifeee points, p( 9 1). Here we use various parameterizations of the expressive Beta family, scaled to [1, 10). The figure also shows for each distribution the price setter u² and the percentage of points that cross (i.c., all u < u²). Although the distributions are quite diverse in shape, market prices are typically low, and price- setters lie mostly in extreme upper quantiles. As a result, almost all points cross, with over 95% in most cases. This effecc is robust across many distributions-sse Appx. A.2.
Estingg (I, y; h) = max(0, 1 y(w x x+ 2([ww])) (14)
which applies to fixed 2-norm costs. Although our costs are linear, since we work with market prices of the form p= p-p users are modelled as moving towards the decision boundary. Thus, because prices adapt to the classifier h, users respond to (directional) market prices p "as if' projected onto h, in the same manner as under (symmetric) 2-norm costs. Note fa-hinge penalizes all points according to the maximal moving distance of (for y E (=1}), which is the same for all users. The key difference in our setting that users have individualized maximal distances: for a
To gain some intuition to the underlying reason, the following result provides simple sufficient condition:
Theorem Let gf (u) be a demand distribution with pdf
6

---

Learning Classifiers That Induce Markets
Beta(0.5,2)
B
Beta(2.8)
Beta(2,4)
Beta(2.2)
Beta(4,2)
revenue
argmax
pdf
% crossers 83%
96%
95%
96%
98%
Figure 3: Demand and price setters. Demand distributions ((u) for various Bela distributions and = 1. Shown are pdfs and revenue curves. Note how revenue- maximizing points ('price setters") are extreme, suggesting that almost all points cross.
1
b=u-l
b
b
revenue
argmax
% cross Gini
% cross price
0
1.25 1.75 29 2 2 202022222222 202 units (ú = inequity (b (bmax/Dmin)
1 1.251.1.77 2 1 1.25 1.57 1 1.25
1.25 1.5..5 units (Ú =)
units (ū -0=))
units (ā )
units (ú =
Figure 4: Demand under varying budgets. When budgets b decrease as demand for units u grows, price setting points become less extreme. However, this effect mild, and only very high inequity (Giniæ 1) helps to suppress mass crossing.
fu) Then the function (u)y is either strictly increasing, decreasing, unimodal, it holds that:
Implications. If h is such that most points are able to move, then this can have dire implications on predictive performance. Because learning generally aims to separate points by their class for any moderately accurate classifier the majority of points that will participate in the market (i.e., have ! = 0, and therefore u > 0) will be negative (y = 0). This means that for classifiers with high pre-market accu- racy, can expect performance drop to low ~50 after the market forms. This ill effect can be somewhat mit- igated if budgets correlate with distance to h, but only if in- equity is extremely high within negative points. Fig. 4 (right) shows the relation between the ratio of crossers and inequity in budgets, measured in Gini units, as function ar in our example, high accuracy is possible only when the gap be- tween the lowest and highest budgets is extreme 2o2-f
1. There is unique revenue-maximizer u².
Let Umax = argmax,, f()),, then u² 2 Umax-
Since fu)J is unimodal under any log-concave Thm. 2 applies many known distribution classes.5 Appendix A.3 includes proof and an in depth analysis of some examples.
Correlated budgets. When users vary budgets (and so u # ū) this can be thought of as 'distorting' demand by scaling units as u + u. Note this means that far-away points can now be closer, and close points can move far b. Potentially, this can lead to less extreme price setters if the distribution becomes concen- trated around smaller values; this effect occurs mildly for (0.5 2) in Fig. 3, which is left-skewed. Because demand is now over = u/b, then if we think of as a function of u, demand will be skewed if is sub-linear in u, since this will "push" larger ū increasingly further. If this negative correlation is sufficiently strong, then market prices should be higher, and we expect fewer points to cross. Fig. 4 shows revenue, prices. prices-setters, and the per- centage of crossers for = u with E (0, 1, 2,.,..., 32). Here we use Gaussian u scaled to [1, 2]. so that dani the smallest u, and bmax 2- for the largest. Results show that increasing a does shift the price setter, and reduces the number of crossers. However, this requires to be large, and even for 16, 30% of points still move.
away, depending
5.2. Market-aware thresholds
Strategic movement by negative points harmful to accu- racy; but positive points that move are actually helpfid since they correct the classifier's mistakes. In standard strategic classification, useful strategy that exploits this idea is to 'raise the bar' by increasing for a given h = hw.r. Un- fortunately, this idea does not easily transfer to a market setting, because prices adapt to changes in T. Nonetheless, varying for given can still have positive effect.
Our construction allows accommodate for changes in Let h. and w.l.o.g. assume h hw.0- Define p(z) as the induced distribution of distances from points x to the decision boundary of h. For any т, we can express the marginal over units as dr (w) = p(= S 7). We can now ask how r shapes demand. Our next example sets p(z) 2)) to be
"This includes: Normal, uniform, exponential, logistic, Laplace, Gamma, Beta, Weibull, Gumbel, Rayleigh, and Chi distributions.

---

Learning Classifiers That Induce Markets
1.0
+1
Amarka: acc 0.96
accuracy
% pos cross
Ap classifier
1
0.5
% cross
price (scaled)
0
Boas
Busa 5 Bya
0.0
-1
Pratie
1.0
inequity (Dmas//bmin)
rev. pdf
-2
4 5
0
1
0.5
X2
X2
Deec 3
Figure 6: Market classifiers. Consider a distribution where 21 enables class separation, and 22 uninformative of y. A naive classifier that uses only xj is unable to prevent neg- ative points from crossing, and attains low accuracy (left). In contrast, a market-aware classifier that uses 22 is able to capitalize on the variation in budgets to classify well (right).
0.0
-1
0
1
2
4
5
threshold (T)
demand (0)
Figure 5: Varying threshold. For mixture distribution of two class-conditions Gaussians, p(z| N (wp, o), varying the threshold results in surprising outcomes under induced market responses. For uniform budgets (top left), there is no good solution. When inequity in budgets b is mod- erate (top right), accuracy jumps to once a critical point is reached. When it is low (bottom left), this occurs only at a small interval. Increased inequity distorts the demand distri- bution, at some point enabling accuracy xs 1 (bottom right).
clustering behavior applies widely- see Appendix B.3.
5.3. Market-aware classifiers
In terms of the market, control over h allows the learner to 'choose' which demand distribution to work with: the choice of determines p(=), and r induces q(u). This gives learning much power over which users will be in the market, as well as which of them will cross. Interestingly, an hwsr that is effective on the induced market need not be accurate on raw data (z,, y) ~ D. For example, w can focus weight on features that are entirely uninformative of y. Our next construction demonstrates an extreme version of this idea.
a mixture of two conditinndiional Gaussians p(2 y), where p(= y = 0) is scaled to [-1,0) and p(z y = 1) is scaled to (0, 1]. In terms of accuracy, we would like T to cause points from p(2 y 1) move, and from p(2 y = 0) to stay unchanged. Fig. 5 shows prices, accuracy, and the ratio of crossers per class for the range [-1,5]. When budgets are uniform (b = 1), no threshold obtains accuracy above 55% despite the data being separable. This is be- cause increasing r causes prices to decrease and remain low enough so that almost all points cross; essentially the same effect of Sec. 1. However, when b negatively correlates with even mildly then it becomes possible to achieve high accuracy: for b that increases linearly with from bmin 1 bmax = 5, we see that once 2 0.75, accuracy abruptly jumps from ~0.5 to ~0.95. This is because at this threshold, the price setter shifts from being an extreme point of p(2 y = 1) to an extreme point of p(2 yy = 1) (see ridgeline plot). Note that this holds for any 0.75; here the adaptivity of prices plays in favor of learning and provides robustness to the choice of 7.6 Interestingly, for a smaller buax = 3. we get that accuracy is high only for r E [1, 2]: once r becomes too large, the price returns to be set by an extreme negative point.
Let d 2, and consider (#1, feature class-conditional Gaussians D(2; Iv). The first feature is Tn N(uy,, which allows to separate the classes (we use μ = 1 and ture is 22 ~ NN00 or, i.e., has the same distribution under both classes, as so is by definition inseparable. We set D(y = 0) = 0.75 and D(y = 1) = 0.25. Here we let b depend on labels as 4y Fig. 6 shows the behavior of two classifiers on this data: huaive which uses only Tı (left), and markee which uses only 222 (right). The idea of Anaive follows that of Sec. 5.2: separate the raw data well, and then tune T on the market. Here we see that this approach breaks down completely: the best it can achieve is 0.29 accuracy, since it cannot prevent the bulk of negatives from crossing. In contrast, Amarket exploits the market to create separability over the otherwise ineffecttve Z2. This is the optimal market- aware classifier. The correlation between and y results in demand distribution q which clusters the positive ă close to h, and pushes negative ù sufficiently far. This results in almost only positive points crossing, and accuracy reaches 0.96. In Appendix B.4 we show this effect can be even more extreme. Note learning will not always tend to favor h in which labels and budgets correlate- see Appendix B.2.
composed of per-
0.15). The second fea-
Fig. (bottom right) reveals an interesting phenomenon: as inequality varies, the price setter jumps from extreme point of one cluster to that of another. We hypothesize this
TThis is in contrast to standard strategic classification which re- quires a particular 7 and can he highly sensitive to its choice.
8

---

Learning Classifiers That Induce Markets
6. Experiments
0.95
MASC
naive:
% crosa
stret (short)
We now turn to demonstrate how our market-aware strategic leamning framework performs empirically on real data with simulated market behavior. We use two datasets common and publicly available datasets and adapt them our strate- gic market setting: (i) the adult dataset, showed here, and using cap tal__aiin feature as a proxy for budgets b; and (ii) the folktables dataset, deferred to Appendix B.5. For further details see Appendix. D.I. Code is publicly available at https:/ / / gith........ com/ BML- TeML-Technion /nn on/MMSC. MASC.
stret (long)
0.85
benchmark
Accuracy
y
-y-1
0.80
1.0
0.75
welfare
burden
0.70
0.5
0.65
2b
23
2
2
2
2
2
2
2a
2
z
2
2
2
2
2
2
0.0
budget inequality (Biad
budget inequality
Figure 7: Results on adult. (Left:) Accuracy across re- duced budget inequity scales, relative to the data's original highly skewed scale of busx xe 2 (star). (Right:) For MASC, per-class ratio of crossers (top; high good for y = 1, low is good for y 0), welfare, and social burden (bottom).
Setup. Our method of market-aware strategic classification (MASC) optimizes the proxy objective proposed in Eq. (13) see Appendix D.3 for details. We compare to two baselines: (i) naïve, a conventional non-strategic classifier; and (ii) strat, a strategic classifier that anticipates user responses (to fixed prices) but does not account for how the market adapts. ? The latter is done by training naive, computing optimal prices p. setting w = p. and then optimizing r to maximize accuracy a held-out set. We measure short- term performance on current prices p (short) and long- term performance after prices re-equilibrate at p" (long). We also show the accuracy of naïve on non-strategic data (for which it is consistent) as a benchmark.
Paii
which matches the sharp performance increase for MASC. This shows that larger scales make it possible to find clas- sifier for which negative points are mostly unable to cross. A possible explanation is our clustering hypothesis: once accuracy is sufficiently high, the price setter jumps from an extreme negative point (under which almost all points move) to an extreme positive point (under which mostly positives move). In terms of social outcomes, welfare (normalized) begins reasonably high, but reduces to 0.5, and does not fully recover. Burden remains flat until scale 24, and then gradually rises, but remains relatively low throughout.
Our main question regards the effect of budget distribution on learning and its outcomes. The distribution of budgets b as found in the data is highly skewed, with a ratio of bmin to bmax of approximately 1:1000, which depicts a state of high inequality. To balance this, we consider the ef- fects of redistributing budgets to attain lower inequality, achieved by rescaling budgets to reduced ranges [1, 2 for
7. Discussion
a = 2,..., 10, where the largest value of Oirue = 20 P 1000 matches the original data (star marker). For each such k, we measure test accuracy, welfare (normalized by total budget), and social burden (Milli et al., 2019) (normalized by total budget of positives). We also measure the ratio of positive points that move (high is good) and of negative points that don't 't (low is good). All results are averaged over 10 random splits, and we report mean and standard errors.
The use of learned models to inform decisions about hu- mans has become common practice. But when those very humans also take interest in prediction outcomes, conven- tional learning tools no longer necessarily apply. This paper advances the idea that when users seek to obtain certain predictions, learning inevitably becomes a driver of demand. When this creates an opportunity for profit, it is only natural to expect that a market will form. Learning classifiers that induce markets poses unique challenges as a learning task. Our paper takes first step address these, and so targets particular market setting and pursues basic understanding of it. But there is of course a plethora of other market set- tings to explore at this new intersection of machine learning and markets. Nonetheless, the idea that learning can drive economic outcomes has broader implications to consider. One example is the question of how learning influences social welfare, as it relates e.g. to market efficiency. An- other example is the question of information asymmetry and the capacity of learning to exploit its informational advan- tage. Given the growing influence of learning on our lives, such questions merit careful thinking and much deliberation. Our hope is therefore not only to spark interest, but to also motivate discussion on these important and timely topies.
Results. Fig. 7 shows results across budget redistributions at different inequity scales busa
22, ..... 200 In terms of accuracy (left), all methods improve as budget gaps increase, but at different rates. MASC clearly outperforms naïve by large margin. It also outperforms strat in the long term for almost all scales a > 2 (which includes (true) and shows similar performance for the lowest scales. Interestingly, this is where strat reveals a large gap between short-term performance (for which it is optimized) and long-term out- comes (as result of prices adapting to updated demand).
Banin
Fig. 7 (top right) depicts the percentage of users that cross per class. Note the abrupt drop in negative crosses at a x 24,
"This draws on the idca of the main algorithm in Hardt al. (2016).

---

Learning Classifiers That Induce Markets
Acknowledgements
References
The authors would like to thank Inbal Talgam-Cohe and Moran Koren for their dilligent advice and insightful feed- back. This work is supported by the Israel Science Founda- tion grant no. 278/22.
Agarwal, A., Dahleh, M., and Sarkar, T. A marketplace for data: An algorithmic solution. In Proceedings of the 2019 ACM Conference on Economics and Computation, pp. 701-726, 2019.
Ahmadi, S., Beyhaghi, H., Blum, A., and Naggita, K. The strategic perceptron. In Proceedings of the 22nd ACM Conference on Economics and Computation, Pp. 6-25, 2021.
Impact Statement
Our paper sets out to study the interplay between learning classifiers and the markets this process can facilitate. We believe that the impact of prediction on economic outcomes can be significant and widespread when machine learning tools are used in social contexts. In the market model we propose, the choice of classifier is modeled as affecting both users and sellers: it inadvertently determines who must in- vest to be classified as positive (i.e., receive the loan or get the job), what this will cost, and which sellers will profit. These forces arise naturally through how the market coor- dinates supply and demand. But whereas the mechanies of conventional markets are well understood both in theory and practice, we believe that the role of learning in mar- kets, and the impact that learning can have, has so far been insufficiently explored.
Ahmadi, S., Blum, A., and Yang. K. Fundamental bounds online strategic classification. In Proceedings of the 24th ACM Conference on Economics and Computation, pp. 22-58, 2023.
Akerlof, G. A. The market for "lemons": Quality uncer- tainty and the market mechanism. In Uncertainty in economics, pp. 235-251. Elsevier, 1978.
Barsotti, F., Kocer, R. G., and Santos, F. P. Transparency, detection and imitation in strategic classification. In 31st International Joint Conference on Artificial Intelligence, IJCAI 2022, pp. 67-73. International Joint Conferences on Artificial Intelligence (UCAA), 2022.
An understanding of how learning creates and affects mar- kets can be used to advance efficient and fair trade, foster equal opportunity, and promote social welfare. It can also be used to gain insight to how dearning-driven markets should be regulated and by what means. But such knowl- edge and tools should be used with care, as they can poten- tially serve to drive markets to undesired outcomes. One example is economic inequity, which can be exacerbated by learning, as our results suggest can happen. Another exam- ple is information asymmetry: Our stylized market model assumes perfect information and efficient prices. But in reality where learned models have access to an unparalleled amount of data-certainly more than is accessible to users or sellers-the learning system gains distinct informational advantage. It is widely recognized that such settings can lead to the exploitation of consumers and even to market collapse (e.g., Akerlof, 1978). We hope that our work serves to encourage fruitful discussion these important topics.
Bechavod, Y., Podimata, C., Wu, S., and Ziani, J. In- formation discrepancy in strategic learning. In Interna- tional Conference on Machine Learning, pp. 1691-1715. PMLR, 2022.
Men-Porat, O. and Tennenholtz, M. Best response regression. Advances in Neural Information Processing Systems, 30, 2017.
Ben-Poras O. and Tennenholtz, M. Regression equilib- rium. In Proceedings of the 2019 ACM Conference on Economics and Computation, pp. 173-191,200
Brückner, M., Kanzow, C., and Scheffer, T. Static prediction games for adversarial learning problems. The Journal of Machine Learning Research, 13(1):2617-2654, 2012.
Chen, J., Li, M., and Xu, H. Selling data to a machine learner: Pricing via costly signaling. International Con- ference on Machine Learning. pp. 3336-3359. PMLR, 2022.
It is also important to note that the market model we study is simple and draws on many assumptions, such as unlimited supply, a fixed number of exclusive sellers, and no external- ities. Results regarding market outcomes, both theoretical and empirical, should therefore be taken under this light. the same time, hope this motivates researchers in both machine learning and economies deepen understand- ing of learning and markets in broader and more realistic economic settings.
Chen, L., Koutris, P., and Kumar, A. Towards model-based pricing for machine learning in a data marketplace. In Proceedings of the 2019 international conference on man- agement of data, pp.
2019.
Cohen, L., Mansour, Y., Moran, S., and Shao, H. Learn- ability gaps of strategic classification. arXiv preprint arXiv:2402. 193003 2024.
10

---

Learning Classifiers That Induce Markets
Ding, F., Hardt, M., Miller, J., and Schmidt, L. Retiring adult: New datasets for fair machine learning. Advances in neural information processing systems, 34:6478-6490, 2021.
Hron, J., Krauth, K., Jordan, M., Kilbertus, N., and Dean, S. Modeling content creator incentives algorithm-curated platforms. In The Eleventh International Conference on Learning Representations, 2023.
Dong, J., Roth, A., Schutzman, Z., Waggoner, B., and Wu, Z.S. S. Strategic classification from revealed preferences. In Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 55-70, 2018.
Huang, T.-H., Vishwakarma, H., and Sala, F. Train' n trade:
foundations of parameter markets. Advances in Neural Information Processing Systems, 36:28478-28490, 2023,
Jagadeesan, M., Jordan, M. I., and Haghtalab, N. Competi- tion, alignment, and equilibria in digital marketplaces. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 37, pp. 5689-5696 2023.
Eilat, I. and Rosenfeld, N. Performative recommendation: diversifying content via strategic incentives. In Interna- tional Conference on Machine Learning, pp. 9082-9103. PMLR, 2023.
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.
Eilat, I. Finkelshtein, B., Baskin, C., and Rosenfeld, N. Strategic classification with graph neural networks. In The Eleventh International Conference on Learning Rep- resentations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
Lechner, T., Umnrr, R., and Ben-David, S. Strategic classifi- cation with unknown user manipulations. In International Conference on Machine Learning. PMLR, 2023.
Einav, O. and Rosenfeld, N. A market for accuracy: Classi- fication under competition. In Forty-second International Conference on Machine Learning (ICML), 2025.
Levanon, S. and Rosenfeld, N. Strategic classification made practical. In International Conference on Machine Learn- ing, pp. 2243-6253. PMLR, 2021.
Epasto, A., Mahdian, M., Mirrokni, V., and Zuo, S. Incentive-aware learning for large markets. In Proceed- ings of the 2018 World Wide Web Conference, 2018
Levanon, S. and Rosenfeld, N. Generalized strategic classifi- cation and the case of aligned incentives. Proceedings of the 39th International Conference on Machine Learn- ing (ICML), 2022.
Ghalme, G., Nair, V., Eilat, I., Talgam-Cohenn I,, and Rosen- feld, N. Strategic classification in the dark. In Interna- tional Conference on Machine Learning, pp. 3672-3681. PMLR, 2021.
Liu, L. T., Garg, N., and Borgs, C. Strategic ranking. In International Conference on Artificial Intelligence and Statistics, pp. 2489-2511 2518. PMLR, 2022.
Ghorbani, A. and Zou, J. Data shapley: Equitable valuation of data for machine learning. In International conference on machine learning, pp. 1242-2251. PMLR, 2019.
Liu, and Garg, N. Test-optional policies: Overcoming strategic behavior and informational gaps. In Proceed- ings of the 1st ACM Conference Equity and Access in Algorithms, Mechanisms, and Optimization, pp. 1-13, 2021.
Guo, W., Kandasamy, K., Gonzalez, J., Jordan, M., and Stoica, I. Learning competitive equilibria in exchange economies with bandit feedback. In International Con- ference Artificial Intelligence and Statistics, 2022.
Milli, S., Miller, J., Dragan, A. D., and Hardt, M. The social cost of strategic classification. In Proceedings of the Con- ference on Fairness, Accountability, and Transparency, pp. 239.239, 2019.
Hardt, M., Megiddo, N., Papadimitriou, C., and Wootters, M. Strategic classification. In Proceedings of the 2016 ACM conference innovations in theoretical computer science, pp. 111-122 2016.
Nahum, O., Noti, G., Parkes, D. C., and Rosenfeld, N. Decongestion by representation: Learning to improve economic welfare in marketplaces. In The Twelfth Inter- national Conference on Learning Representations, 2024.
Hardt, M., Jagadeesan, M., and Mendler-Dlineet C. Perfor- mative power. Advances in Neural Information Process- ing Systems, 01-22999-22981 2022.
Prillo, S. and Eisenschlos, J. Softsort: A continuous relax- ation for the argsort operator. In International Conference on Machine Learning, pp. 7793-7802. PMLR, 2020.
Hossain, S., Micha, E., Chen, Y., and Procaccia, A. D. Strategic classification with extermalities. In The Thir- teenth International Conference on Learning Representa- tions, 2025.
Rosenfeld, E. and Rosenfeld, N. One-shot strategic classifi- cation under unknown costs. In Forty-first International Conference on Machine Learning, 2024.

---

Learning Classifiers That Induce Markets
Shao, H., Blum, A., and Montasser, O. Strategic classifi- cation under unknown personalized manipulation. Ad- vances in Neural Information Processing Systems, 36, 2024.
Shekhtman, E. and Dean, S. Strategic usage in multi- learner setting. In International Conference on Artificial Intelligence and Statistics, pp. 2665-2673, PMLR, 2024.
Sundaram, R., Vullikanti, A., Xu, H., and Yao, F. PAC- learning for strategic classification. International Con- ference Machine Learning, 2021.
Zhang, H. and Conitzer, V. Incentive-awarc PAC learn- ing. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 5797-5804, 2021.
12

---

Learning Classifiers That Induce Markets
A. Market prices additional theoretical and empirical results
A.1. Equilibrium prices
Consider some classifier h = Aw,r, and assume there cxists some E [d] for which w, > O. W.L.og. let i The following result states that computing market outcomes under h can be done by projecting demand onto the direction of (i.e., by computing distances from negatively classified points the decision boundary of h), (ii) computing (scalar) revenue-maximizing price p², and (iii) moving points iff b > p²_ This suggests that even for with some negative entries, market outcomes can be computed "as if" users move directly towards h, i.e., as determined by "prices" p p
The idea is to show that outcomes are mostly invariant to the actual direction in which points move. Because features are substitutable, we can artificially constrain purchases to single feature (here, x1) and maintain the same outcomes. This results from the same user taking on the role of prices setter irrespective of the chosen direction movement.
Proposition 2. Given h, let p² by the revenue-maximin revenne-maximizing price assuming there demand only for feature x1, i.e. points can only buy 21 and therefore only move along this dimension. Define p' (p) ........), 0). Then:
1. Total revenue will be the same under p- and p².
2. The same set of users will cross h under p and p'.
Proof. The lg distance of a point æ to the hyperplane defiend by / is given by:
w + T
2
Contrarily, the distance of point to hyperplane in the direction of xi alone is:
x + T w
which we think of u as units of demand in the direction of 01. Together, we get the relation:
w
u
|
Plugging the above into the definition of maximal revenue gives:
by
Σ
r = argmax
Uj
U1
Bi
3:
b
Σ
W1
argmax
||/||
j
2
[w]
1
b argmax
Σ
where r is the total revenue when only purchases of 2ı are permitted. The equality holds since scaling does not change the argmax, and by multiplying both sides of the inequalities in the summation by ||ll Thus, total revenue remains the same.
weil
Note also that by switching from u to u², albeit scaling, the summation is taken over the same set of points. In other words, a different direction might entail a different currency, but the market will maintain its operation. Thus, the set of points that move also remains the same.
13

---

Learning Classifiers That Induce Markets
For given w, one implication is that for any direction i in which w; O, the corresponding p' is an equilibrium price. When multiple such exist, any p; is equilibrium price. When result above states that market outcomes are equivalent under any of these prices, and so in principle we are free to work with any of them. The second convenient implication is that even for w having negative entries, and for which p' is not well-defined, we can nonetheless work with p-
in all entries, p" is also equilibrium price. Our
minor comment is that although we assume only that items and prices are positive (and not w), is possible to constrain > 0 as part of the learning algorithm. Another possibility is to permit negative prices: these can be interpreted as paying reduce æ (e.g., pay the gym to lose weight), but requires constraining x² (or permitting negative æ).. For w, can interpret this seller not permitted (or able) to sell at all.
A.2. Expected prices
In Sec. 5.1 have empirically shown that for many 'natural' distributions over demand, there is: (i) unique revenue- maximizing point u", and (ii) this point tends to materialize extreme quantiles of the distribution. Here show that this phenomenon holds more broadly. Fig. 8 shows pdf-s, revenue curves, and price setters for a wide range of parameterizations of the Beta distribution. These include symmetric, left-skewed, right-skewed, concave, bell-shaped, and uniform distributions. For all distributions considered, the price setter at least in the 80-th percentile, and typically much more extreme.
(et.(0.5,0.5)
Betal0.5,1)
Beta(0.5,2)
Beta(0.5,4)
Beta(0.5,8)
revenue
argmax
crossers
99%
87%
82%
83%
Beta(1,0.5)
Beta(11
Beta(1.2 (1,2)
Beta(1.4)
Beta(1,8)
99%
91%
6%
92%
Betal2.D.5)
Beta(2.1)
Beta(2.2)
Beta/2.4)
Beta(2.8)
97%
97%
Beta(4.0.5)
Beta(1,1)
Beta(1.2)
Beta(1.4)
Beta(1.8)
99%
Beta(8.0.5)
Beta(8,11)
Beta(8,22
Beta(8.4)
Beta(8,8)
98%
Figure 8: Price setters are extreme across a wide range of Beta distributions.
A.3. Theoretical insight
To complement the observations above, this section aims to provide theoretical underpinning for the questions of (i) when do unique revenue-min awvenue-maximzzing prices exists, (ii) why is this prevalent across many natural distributions, and (iii) how extreme are price setters (c.g., in terms of quantiles). We begin with some general claims and sufficient conditions, and then present some examples of particular distribution classes which we analyze in depth.
14

---

Learning Classifiers That Induce Markets
1. ANALYZING REVENUE
Consider continuous distribution over (univariate) revenue defined by pdf f(u). We assume that f has support on [0, t] fort E R,, U {oo), and consider uniform budgets b for all users. This is made w.l.ogg- below. Recall that expected revenue r(u; f) is defined as the sum of demands of all users u' u, divided by This can be rewritten as:
1 Fr [n' s u] = J f(u') 1 S u} u d'dd' - r(u; f) = 1
a 1o s(ul) v'
To determine whether the expected revenue has a maximum, we compute the derivative of r(u; f) with respect to u:
f(: du r(u; f) = - f(u)
1 u
/ f(w) u' du' f(u)
1 2 f(u') rl dul
u²
Denote by u" the revenue maximizer w.r.t. f (if such exists). That is, u² argmaz.rru; f). The following observations will be useful:
Observation 2. rfr'(u; (u; f) > 0 through S u S t, then u' is unique and is attained at t.
Observation r (u; f) < 0 through < u S t, then u² is unique and is attained at 0.
Setting (u; f) 0, we find:
f(u) = w² (-" f(u'). dd
f(u)²² 1// f(u')-''du
A.3.2. PROOF OF THEOREM
Theorem states that sufficient conditions for the existent of unique argmax for expected revenue are that f'u)u is either strictly increasing, strictly decreasing, strictly unimodal. We now turn to its proof.
Proof. Denote by D(u) the function D(u) fu]). We split the proof to two distinct cases:
Case I: D(u) contains one maxima point. Let denote the maxima point of Duu), meaning that û = argmax, D(u).
For u E [0, ú). D(u) is increasing, and for u [ū, t]. Duu) is decreasing. Therefore, for < d1 < U2 < û, it holds that D(w1) = f(u1)us f(u2)u2 = D(u2). Thus, for all u < â:
Duu)== = I()) > S. s(ul''',
This implies:
(': f(u) u2 I f(ud)u', du'
If fu) is continuous on [0, t), then (w; f) is also continuous on [0, t). Therefore, no u satisfies f(u)u² S f(u)) du', then r' (1: f) > 0 throughout [o, t). By observation 2, n* maximizes the revenue of the distribution.
Suppose there exists point u" such that:
f(u') S-' f(wd) ul du'.
First, it follows directly that n* 2 û. since for u â, it holds that r'(u; f) 0. Second, referring Figure for each 0, moving to u² increases area and decreases area 3. Area 2 changes as well but is mutual to both terms. Therefore, in the range (u", t), the following inequality holds:
f(u)u² S f(u') n' du'
15

---

Learning Classifiers That Induce Markets
Figure Areas 1 and contribute to So f(u")u' du', while areas 2 and 3 yield f(u")u", At u u², we have So f(u')u' du' = f(u")u²² which implies that area 1 equals area 3. Furthermore, for each O, shifting to + increases area and decreases area 3. Area also changes but remains common to both terms. Thus, for each > 0, at u² + it follows that So f(u')u' du' > (u.)u?
1
Rul-a"
3
2
This implies that within the range (u", t]. the derivative ('; f) < O. Consequently, u" is the unique revenue maximizer by definition.
Case II: (uu) contains no maximum point. ((u) strietly increasing over [0. 4J. follows that f(u)u² > Jo" f(u')u' du' for all E [0, f). Consequently, r' (u: f) for all u, which, by Observation 2, indicates that the unique revenue maximizer u" t. Moreover, in this argmax, D(u) t, meaning that u" argmax, D(u)
Conversely, if (u) is strictly decreasing over [0, (], it follows that s(u)u²² < So" s(u))u du' for all u E [0, Consequently, (u; < O for all which, by Observation 3, indicates that the unique revenue maximizer is u² = 0. Moreover, in this case argmax, (u)) = O, meaning that u² = argmax,, D(u).
We note that the proof can be easily extended distribution in the range [a, f). for 0. The changes to the original proof minor, and include modifying the lower limit of the integration. For distributions in range [a, oo]. the proof is valid too, as long (uu) is strictly increasing, decreasing, or unimodal.
The proof also give a lower bound on u' in terms of Corollary 1. Under all conditions Thm. 2, it holds that u² û.
The following examples show this relation explicitly for two classes of distributions: Beta, and uniform.
A.3.3. EXAMPLE: BETA DISTRIBUTION
Based on Theorem 2, we establish the following result about Beta distributions:
Theorem 3. For every a, let fu) denote the probability density function (PDF) of the Beta distribution Beta(a, b). defined on the interval [0, 1]. Then, the function D(u) f() is either strictly increasing or strictly unimodal.
The following theorem implies that every Beta distribution has unique revenue maximizer, which is confirmed empirically over different Beta distributions in Figure 8.
Proof. The PDF of Beta(a, b) is given by:
f(u) = (1-
where Kab 0 is normalization constant that depends only and b. Thus, D(u) f(u) u== Ka,u 2)a-1 We will show that (u) is either strictly increasing, strictly unimodal. First, compute the derivative of D(u) w.r.t
D(u)= = Kas [an ujb-1 - "a - 1)(1 -2) -
du
Simplifying the expression gives:
d
D(u) = Kasuu-1(1 2 [a(1 - u) - u(b 1)]
du
16

---

Learning Classifiers That Induce Markets
and setting da D(w) solve:
K Ka,s" (1 3))03((00 - u) - u(b 1)]
The solutions are:
U1 = 0,
U2 = 1, U3 =
a + b
Here, ii exists if a > 1, and U2 exists if b (otherwise, they are undefined due to the powers of u²=1 and (1 3))--3). Since the Beta distribution defined on [0, 1] and D(u1) (u2) 0, we focus on ug. For ug [0, 1]. must hold that b>1 1.
Next, observe that for all u < ug, the term a(1 - u) u(b 1) > 0. Therefore, D'(u) > 0 and Duu) increases in this range. The proof now splits into two cases:
Case 1: uy & [0, 1]. In this case, D(u) is strietly increasing over the interval [0, 1], because D'(u) > 0 throughout [0, 1] and the proof complete.
Case 2: ug [0, 1J. For us <u< 1, the term a(I u) u(b - 1) < Therefore, D'(u) < 0 and (u) decreases in this range. Thus, Uy is the sole maximum point of D(u), which implies that D(u) is strictly unimodal, as required.
As shown in the proof of Theorem 2, if Duu) is strictly increasing, the revenue maximizer occurs at the right edge of the distribution, which in this case is at u = 1. If D(u) is strictly unimodal, we know that the revenue maximizer is greater than the maximum point of (u)) In this case, the maximum point is a+b-I (noting that b > in this scenario).
Moreover, the maximum point of a Beta distribution with parameters a, b is given by argmax, f(u) we obtain:
e-1 For b 1, a+d-2'
+ b a + --
which implies that the percentile of arg max,, Duu) is greater than the percentile of arg max, f(u), and both are smaller than the percentile of u².
This analysis provides an intuition for the unequivocal empirical results shown in Figure 8, which demonstrate that the revenue maximizer is at least in the 80th percentile (and typically even higher). To conclude, under this family of distributions, when they induce individual demands for a feature under a uniform budget, large percentage of users will be able to afford purchasing the amount of the feature they need.
A.3.4. EXAMPLE: UNIFORM DISTRIBUTION
We now perform a similar analysis for the uniform distribution over the range [0, 4). where / >>> 0. The PDF of this distribution is constant for all u: fu) = Consequently, D(u) f())u u fu is strictly increasing function of u. By Theorem 2, the revenue maximizer for this distribution is the right edge of the range, which t.
We can extend this result to the uniform distribution over the range (a, b).
Theorem 4. For any a, b > O, let (u) denote the probability density function (PDF) of the uniform distribution over (a, b). Then, the revenue maximizer is unique and occurs at b.
Proof. The PDF of the uniform distribution is constant for all u: [()) 1. b-o-
The function r(u; J') is therefore given by:
r(u; f) 1i S f(u') al dul
1 -
1
f"
1
ul du' u(b - a) [ du'
u
b-
Evaluating the integral:
2 a2
a²
r(u: f) u(b a)
2
2
2(b
2(b a)
Next, compute the derivative of r(u;f) f) with respect to u:
a²
1
a 1
(u; f) 2(b a)
2(b 0)
u2
=
2(b
a)
+
2(b
a)
2
17

---

Learning Classifiers That Induce Markets
0.8
0.5
revenue / ppice
market price (p)
0.4
0.6
0.3
0..
0.2
0.2
0.1
-
F(Sb)
((S))
-O-
F(Ss)
0.0
CO
0
1
2
3
4
5
0
1
3
4
7
10
units (u)
value of additional point
Figure 11: The effect on price of adding single point to fixed sample. Original sample points shown x-axis.
Figure 10: Empirical revenue curves f for different sam- ples S; featuring different revenue-max maximizing points u².
Since both terms are positive for all u E (a, b]. it follows that ("; f) > for all u E [a, 6]
By Observation 2, the revenue maximizer is unique and occurs the right edge of the range, which b.
A.4. Empirical prices
Our analysis above considers expected prices defined over a demand distribution. But in practice, learning must work with finite samples, and therefore with empirical markets. We begin by investigation some features of empirical markets, revenue, and prices, and then make the connection population markets with expected revenue and prices.
A.4.1. THE PRICE-RE REVENNREVENUE LANDSCAPE
Thm. states that the revenue-maxinizin price is always some u, hence, we can instead think of revenue function of inverse prices = u, measured in demand units. This is useful since we can now consider directly how changes in the demand set affect revenue, and through it, the optimal price.
Fig. 10 plots empirical revenue F(5) for three different samples S₃ of size m 10 with units u, scaled to span [1, 10]:
Note that revenue always begins m however, outcomes differ considerably across samples, in terms of the shape of the revenue curve, the location and index of the price setter i", and the optimal price p.
1 for the smallest u, since only one unit sold (to one user) price p 1. From here,
This raises the question: how sensitive are market prices to variation in demand? For this, we take sample "I.... Um and measure how prices change due to adding a single new point ug- Fig. 11 shows the outcome of this process for a fixed select demand set of size m 5 and for an increasing value of an additional point ug E [1, 10] (x-axis):
The in are shown in color and positioned the x-axis. The revenue curve includes segments colored according the matching price setter, with turquioise (and yellow highlight) indicating that the price setter is tgg As can be seen, the value of uo has stark effect on market prices: even though it is increased gradually, prices jump at discrete points whenever the price-setter i" changes. Generally, prices are down-trending, and i' appear in increasing order of u;-but this is not necessary, as prices can also jump up, and some s; can be price-setters more than once.
A.4.2. WHY PRICES JUMP
One reason for this behavior that optimal prices may not be unique. The following an extreme construction which all points are revenue-maxinn maximizin...... Proposition 3. Let 2 3, and w.l.o.g. assume uniform budgets. Define wi...., Um recursively as:
u: =12 Σ
jzt Uj:
U2 = 2, un =1
Then for all i >> 1, prices P; u, attain the same revenue.
Together with Thm. 1, this implies that f is also maximized under all p;- To see how this lends to price jumps, consider the minimal case of m = 3. we slightly decrease u2 then it becomes the unique price-setter; in contrast, if we slightly increase U2, then Ug becomes the price setter. Thus, small perturbations U2 can cause prices to jump between P2 and Ps-
18

---

Learning Classifiers That Induce Markets
A.4.3. REVENUE FOR LARGE SAMPLES
Our examples above considered mostly very small market sizes. Fortunately, prices tend to be more well-behaved when the number of samples grows as long the underlying demand distribution is well-behaved. For example, for Beta(0.5, 4), (and scaled to [1, 10), Fig. 12 presents revenue curves (left) well maximal revenue (top right).and empirical market prices (bottom right) for samples of increasing size m.
Empirical revenue curves
Limiting behavior
0.5
price (0) max revenue
sample limit
0.6
0.4
0.5
0.3
revenue
2
0.4
0.75
0.2
2
2
0.1
0.50
2
0.0
0.25
2
3
5
24
26
2
2
2
units (u)
sample size
Figure 12: Revenue and prices for increasing sample size.
As can be seen, despite significant variation under small m, results stabilize as m grows in terms of the revenue curve (left), its maximum value (top right), and optimal prices (bottom right).
B. Experiments additional results
B.1. Market hinge loss vs. 0-1 loss
Our proposed m-hinge in Sec. 4 permits both tractable optimization via gradient methods and without the need for explicitly computing best-responses Ap Aparkat(z2 (z). Due to Levanon & Rosenfeld (2022), it also intends to maximize generalized notion of "strategic' margin (although their generalization bounds do not immediately carry to our setting due to dependence across users in the sample). Here we examine the loss landscape for the m-hinge under simple ID example and compare it to the 0-1 loss, which it intends to approximate.
Data as generated as follows. Setting d we sample each x from a condiiooniiional distribution x ~ ((y: 1). Classes balanced with ply = 0) = ply = 1) 0.5. Budgets b are sample uniformly from [1, 8.5) for negative points and from (8.5, 16] for positive points. This means that b are generally in [1, 16) and correlate with y. and generally with x, but do with given y for either class. We sample 1000 points in each setting.
Po E (1,, 0, 1, 3). For a range of thresholds E [-3, 10). each plot shows values of: (i) the 0-1 loss, (ii) the m-hinge with exact empirical prices á. (iii) the m-hinge with smoothed empirical prices p (using a mild Tsoftsont = 0.1 and large Teottmax = 10), (iv) prices, and (v) the price setter (in percentage from all points, sorted by their x value). Note prices and m-hinge values are scaled to fit the plot.
Fig. 13 illustrates the loss landscape for increasing class mean gaps
Po
1.0
0.8
0.6
mittinge (wooet
misiinge (smouth BI (reersled)
0.4
price setter (7)
0.2
0.0
-2
threshold (r)
threshold (T)
threshold (r)
threshold (T)
threshold (7)
Figure 13: Market hinge loss landscape, compared the 0-1 loss.
19

---

Learning Classifiers That Induce Markets
Overall the m-hinge appears be adequate proxy for the 0-1 loss. When classes are reasonably distances at μ1 Mo 1 (center), the 0-1 loss decreases gracefully large price variation. Once 7 reaches R 1, the price setter begins to stabilize at around 60%; from this point on the m-hinge is well-behaved. For larger gaps (right), there is an abrupt jump in the 0-1 loss once certain 7 is reached. This can be seen both in prices peaking, and the price setter settling on 50%. The 0-1 becomes very close to 0, and the m-hinge is faithful in this regard. Again we see that smaller T are more challenging for the m-hinge, but note how soft prices help smooth the (non-linear) loss curve and reducing the number sharp local minima.
increases. The m-hinge follows closely, but struggles for negative due
Interestingly, even when the class gap zero or negative (left)iie., the positive class lies mostly to the left of the negative class the market mechanism enables obtain low loss values." Here overall behavior smoother for both the 0-1 loss and the m-hinge, due to smooth behavior of prices and price setters.
B.2. Budgets and labels
Our empirical analysis in Sec. 3 focused cases where budgets correlate with labels for given h. While our goal there was to reveal how the strength and types of correlation can affect market outcomes, it does not imply that learning will always tend towards classifiers h in which budgets and labels correlate along the direction that h induces (or more precisely, on distances of negatively-classfier points to the decision boundary). Importantly, we note that what matter is not the correlation between labels and budgets per se, but rather, the relation between labels and the normalized demand-which results from how budgets 'morph' distances to the decision boundary of given h.
Here demonstrate market outcomes what drives the classifier is user features in way that circumvents dependence budgets-which which in this case, enables higher accuracy.
example in which there is no correlation between b and y. As we will see,
Our construction is as follows. Consider features in IR? and denote x = (I1, T2). Points are generated such that each coordinate is sampled independently. For all points (regardless of class) 21 is drawn from the distribution (0, 0.4). For positive points 22 is drawn from (1, 0.3), and for negative points æ2 was drawn from 1,-1, Note the means of these distributions match labels, μ 2y 1. The base rate set to ply 1) = 0.25. Budgets were determined as:
b(x) = max(0.1, 2.5 + e),
<~ N (0, 0.2).
i.e, budgets generally increase with v₁ but are noisy, and from above at capped at 0.1. Note that by construction:
is correlated with xi, but independent of 2/2
y correlated with æ2, but independent of æ1.
We compare two threshold classifiers: hy which makes use only of æi, and ha which makes only of 222 Each was trained on its respective feature to attain the maximal strategic accuracy its induced market. Results shown in Fig. 14:
y == +1
acc=0.63
y=-1
1
(xarket(x) classifier
h2
g 0 acc=0
83
-1
-2
X1
X1
Figure 14: Revenue and prices for increasing sample size.
"This surprising because our model class here includes only one-sided thresholds, h-(x) = (xx 2 r).
20

---

Learning Classifiers That Induce Markets
As can be seen, the classifier by (which uses æ2i left), yields better accuracy than bı (which uses 4ii right). Crucially, hg uses only 22, which is independent of b, and so the classifier does not rely any correlations between labels and budgets (via distances). Accuracy here is high since positive points on the positive side of l22 and the market enables only subset of negative points to cross. Note that eπтотs are precisely due to those negative points which do move: these are points with high 21 values, and therefore those with higher budgets that permit cost-effective strategic movement. Conversely, accuracy for h is low because it cannot limit only negative points from crossing. This is because the distribution budgets (and distances)
same for both classes for any choice of threshold.
B.3. The cluster hypothesis
Our results in Sec. demonstrated how for well-behaved demand distributions the price setter tends to an extreme point. This was complemented by our theoretical characterization in Appendix A.3. Our conjecture is that the phenomena broader, in that when the demand distribution comprises several "clusters", then the price setter will tend be an extreme point of one of those clusters. Fig. 15 shows this holds for various mixtures of two Gaussians. We vary the relations between the Gaussians along several dimensions, such as distance from the decision boundary, gap between means, and variance. For all considered settings, results show that (i) the price setter is indeed an (almost) extreme point of one of the clusters, and (ii) the price setter "jumps" between clusters at particular points as we vary the parameters of the setup.
1.0
0.8
price setter (%)
0.1
revenue price setter pdf
0.6
0.2
0.1
0.2
0.0
0.0
Pa
1.0
0.8
0.4
0.6
price setter
0.4
0.2
0.0
5
10
5
10
5
10 0
10
2
1.0
0.8
price settrr (%)
0.6
1.0
0.4
0.5
0.2
0.0
0.0
0.0
1.0
Figure 15: The cluster hypothesis. We conjecture that when the demand distribution is mixture of well-behaved "clustered" distribution, the price setter will be an extreme point of one of the clusters. Varying the relations between clusters causes the price setter to "jump" from one cluster to the other. Here we vary: the gap between means of the two components (top), the distance of the entire distribution from the decision boundary (middle), and variance of each component (bottom). In each row, the four left plots show example distributions, while the rightmost plot shows the price setter (in percentage from the sample) for the entire parameter range. Note how each variation shows distinct jumps across clusters.
21

---

Learning Classifiers That Induce Markets
1.5
-,-2
non-stral
1.00
0,50.5
0.3.3
0.75
CTORS
accuracy
0.75
0.70
y=
y
0.50
0.85
1.0
0.25
0.60
MASC ralve
-2
0
4
-4
-2
2
4
0.55
21rt [long]
manchmart
gap (p-
-M-)
gap Iu+ - -4-)
0.50
0.0
21
2
2
Figure 16: Accuracy of threshold classifiers on 'inverted' data.
budget inequality (Dyrad
budget inequality
Figure 17: Results for the folktables dataset.
B.4. Markets induce separability (further exploration)
Our results in Sec. 5.3 revealed a surprising result: that induced markets make unseparable data become perfectly separable. Here we show that this effect can be even more extreme and unintuitive. Consider a univariate mixture distribution with class-conditional distributions p(z y) = (P o). We set a = 0.15 and will be interested in the effects of varying μ.. We will examine both balanced data (p) = ply = 1)) and class-imbalanced data with pl = p(y = 1) = 0.3. For budgets, we set = b and show results for b1 E {1, 1.5, 2, 2.5}. Our model class will consist of threshold functions (x()) 1 {a > 7. Note that we intentionally consider only thresholds that are oriented to classify larger as positive (i.e., the class does not include 'reverse" thresholds 1l [(x < <)))
Fig. 16 shows accuracies for the optimal threshold classifier across increasing gaps between class-conditions means μ11 Po- Note that negative gap means that the positive distribution generates values that are mostly smaller than the negative distribution. The plot shows results for the range of budget scales bj. and plot the performance of a non-strategic benchmark (dashed grey). As expected, the benchmark attains reasonable accuracy when the gap is large, provides accuracy when the gap is zero (and the two distributions are superimposed), and deteriorates quickly as the gap becomes more negative. But for market-ane wware classifiers, this is not the case. For p1 0.5 (left), we see that for the larger budgets, accuracy can be I even when the gap is negative. For smaller budgets, outcomes under negative gap be better than under positive! This latter behavior is much more distinct for P1 = 0.3 (right), where for all budget considered, positive gap enables significantly lower accuracy than moderate negative gaps allow.
B.5. Main experiment: results on folktables dataset
Here reproduce main experiment from Sec. 6 additional dataset, building the folktables data due to Ding et al. (2021). For the target variable y use a binarized version of the 'employment status' feature (code ESR), budgets we use the 'total income' feature (code PINCP). Appendix 1.1.2 includes further details on the data and preprocessing.
Fig. 17 shows the results. Overall trends are similar to those of adult in Fig. from Sec. 6, though there are several notable distinctions. As in adult, here as well all methods improve with scale, and our MASC approach outperforms others- here from scale a 2 and higher. Note that improvement for naive more pronounced. One key different is that the benchmark not only much higher, but also hard to improve upon even for MASC. This can be explained by the lower ratio of positive crossers, i.c., even at large scales it is hard to allow positives to cross while preventing negatives (top right). Another difference is that strat underperforms by a larger margin and across all scales. Note that there is also larger and consistent gap between short and long performance, suggesting stronger market adaptation.
C. Differentiable market prices
Our market-aware learning approach replaces exact market prices p² with smooth surrogate X to enable differentiation. This is achieved by modifying the exact pricing scheme in Algorithm to be differentiable.
One useful property of Algorithm is that each of its steps can be easily vectorized, and each atomic operation is either already differeeniablee, or can be made differentiable using existing smoothing methods. In particular, note that: (i) dist a differentiable operator, (ii) sort can be implemented as a linear operator II with II, = if item is in position j and 0 otherwise; and (iii) can be computed using a cumulative sum, implemented as linear operator with entries G2 = lii < j.. The remaining non-differentiable operations are IT and the argmax for choosing the revenue-mane maximiin
22

---

Learning Classifiers That Induce Markets
point i". Thus, if we replace IT with a differentiable softsort operator IT (e.g., using Prillo & Eisenschlos (2020)) and the argmax with a softmax, then the entire algorithm becomes differentiable. These steps comprise Algorithm 2, which returns smoothed market prices an approximation to P. The final differentiable market price vector can be obtained as ý pw, but is unnecessary to compute when using our market hinge loss, which requires only P. Note both softsort and softmax operators require setting appropriate temperature parameters.
Algorithm 2 Smoothed empirical market prices
I: input: unit-budeget pairs {u,, bi) with u, 0'i
2: u (u/bb....... ......,,,/buu (b,)
3: IT < softsort(M. (7)
> apprex. sorting matrix
Ilu 4: un f Iu, Un <
5: 7 & min
6: 0 < u/7
b normalize demand
7: 2 - 1/ūn
8: - cumsum(un)
9: < c
10: p = z softmax(r) -7
> de-normalize prices
11: return: p
Normalization.
practice, we found it useful to normalize ū so that its smallest entry is 1. This is possible since market prices are insensitive scale: if f optimal for u. then for scaled au, the solution is p. Normalizing ensures that all temperature parameters (e.g., in softsort and softmax) operate at the same scale across all batches, which is important since the relation p b/u suggests that even mild perturbations to small u-s can cause large variation in computed prices.
Truncated demand. Recall that demand is determined by the distances of all points the lic on the negative side of h. In principle, since points on the positive side are assigned u = 0, their presence does not affect prices. However, when using soft prices, this does have a mild effect. To see this, consider that softsort employs row-wise softmax operations that replace the argmax used to indicate the sorting position. Since scores for all entries are exponentiated, points with u = now contribute e"
the denominator. This biases outcomes, and becomes significant when there are many positively classified points. We circumvent this problem by simply truncating all points with 0 completely from the calculation.
The smoothness of prices can be adjusting via two temperature hyper-paramette Troftsort for the soft sort operator, and Toottmax for the final softmax. In the limit, these recover the exact argsort and argmax operators, respectively. Varying these temperatures therefore trades off approximation and smoothness (for optimization purposes).
Hypper-parameters
D. Experimental details
D.1. Data and preprocessing
D.1.1. ADULT
Data description. Our main experiment makes use of the adult dataset. This dataset contains features based on census data from the 1994 census database that describe demographic and financial data. There are 14 features, 8 of which are categorical and the others numerical. The binary label is whether a person's 's income exceeds $50k. The dataset includes a total of 48,842 entries, 76% of which are labeled as negative. The data is publicly available at https: / //archive.ics... eewuuiiiduuddatsseeeeeeeeee teaittaasse///duuuli //uult.
Preprocessing. make the data appropriate to our strategic market setting, we took the following steps. First, all rows with missing values were removed (7.4%). Two features were excluded: couttre and education, which had perfect correlation with the numerical feature education_ne _um. The feature capital_gari classifier, but rather as the basis of determining budgets. Second, to maintain class balance, 25% of negative examples were randomly removed. Finally, because behavior in strategic classification applies to continuous features, for our main experiment we dropped all categorical features. These however were still used for constructing budgets (see below). The remaining numerical features were normalized.
not used as input to the
Budgets. For budgets b, we chose to use the papitall_aiin feature; of all features, this most closely related to an indication
23

---

Learning Classifiers That Induce Markets
of wealth. Unfortunately, only 8.5% (3,561) of the entries in the data contained values that were not O, 99999, or NaN. As such, we decided replace such missing extreme entries with imputed values, for which trained two random forest models (one per class) on the valid subset of the data. Hyper-parameters for this process were chosen using grid search with the following parameters: n_ n_estimators E (50, 100, 200), max_depth E [None, 10, 20, 30),
samples__st jes_spltt E (2. 5, 10), min__amm samples_less & (1, 2, 4), 5 folds, and Rº scoring. All features were used during imputation. The normalized RMSE was 0.366 for positives and 0.679 for negatives.
Data splits.
We used cain-validation-tes split of 70:10:20 and averaged the results over 10 random data splits.
D.1.2. FOLKTABLES
Data description. We reproduce the main experiment of Sec. 6 using folktables an additional dataset (Ding et al., 2021) see Appendix. B.5. The data is publicly available at https:
http:///aaalloofnaaaooossss woloons/lllokkk folktables.
Features, budgets, and labels. We made use of the following features: "AGEP" - age (int), 'SCHL' educational Attainment (ordinal 0-24), 'MAR' - marital statue (categorical encoded to 1-5), 'RELP' - religious Affiliation (categorical 1-7), 'ESP' employment status of parents (categorical 0-7), 'CIT" citizenship status (categorical 1-5). For the target variable y we used 'ESR' employment status, converted into binary "employed" and "not employed". For budgets b, we used 'PINCP" total person's 's income (float).
Preprocessing. All features where scaled to [0, I]. Features that were negatively correlated with y were flipped as H3 + (1 - Iz). Examples with extreme or outlier budget values (below 50 and above 50,000) where removed.
Data splits. Same as adult.
D.2. Evaluation
Metrics. In addition to accuracy, we measure the following metrics:
Welfare: Measures the profit (utility minus cost) for all users of the system as:
1 welfare(h) BBA
E b.11h(())) 1} c((),x²))
(16)
Social burden: Measures the overall cost required to ensure that all deserving users (i.e., with y = 1) rightfully obtain positive predictions (Ú = 1):
burden(h) =
Σ oa==1
min c(x;,2²) 2'sh=="=11
(17)
B+
Here B = E, by is the total budgets, and B+ Eig:=1 experimental settings vary considerably in the distribution of budgets well its total, normalizing by B and B₁ permits meaningful comparisons across conditions.
=1 b, is the total budget of the positive examples. Since the different
D.3. Training, tuning, and optimization
Implementation. All code was implemented in python, and the learning framework was implemented using Pytorch.
Optimization. Our overall approach is to optimize the objective in Eq. (13) using gradient methods. In particular, we use ADAM with mini-batch updates- see details below. Additional decisions and considerations:
The softsort and softmax hyper- hyper-paramett parameters are intended to facilitate differentiable prices. In general, tuning their parameters should seek to optimally trade off between how well they approximate 'hard' sort and argmax, and the effectiveness of gradients. However, particular to our market settings, we observed that they also contribute to smoothing out discontinuities that result from sharp transitions between market states, i.e., cases where a mild change in prices causes large change the number of points that move and mooss-which can significantly affect the loss.
Similarly, we observed that mini- mini-batches also have a smoothing effect on the market. This however related to a different aspect: Since market prices correspond to the normalized demand of one of the data points ū; prices in general
24

---

Learning Classifiers That Induce Markets
be sensitive the particular sample which they are computed. Another concern if a small change in learned parameters move points from being slightly above the decision boundary to slightly below it. If this occurs, then this new point has u that is positive but very small, which can affect soft prices (despite normalization step in bini-batches help in this regard because they average out the
Algorithm 2) through the choice of hyperparameters. effect that any single data point may have. They are also helpful in cases when several points 'compete" over setting the price (i.e., entail similarly large revenue) by permitting p to express their (weighted) averaged.
Initialization.
The model was initialized with the weights and bias term of the naive model. Notably, initializing it with randomly generated weights from normal distribution had minimal impact on the results.
Hyperparameters. We used the following hyperparameters:
Temperature Tooftoort for the softsort operator: 0.001
Temperature Tofumax for the softmax operator: 0.01
Batch size: 500
Learning rate:
adult: 0.001 for budget_scale [1, 32], 0.01 for budget_scale E [64, 1024]
folktables: 0.001 for all budget scales
Regularization and coefficient: 0.1
Epochs: 100 for adult, 1000 for folktables
Hypeepaarmeteess were chosen by standard hyperparameter search over grid of possible combinations and chosen based on performance validation set along with considerations for reasonable convergance times.
25


Reviews:
[{"review_id": "ix8uE0IdQK", "reviewer": "Reviewer_XboL", "summary": "The authors propose a market-based perspective in strategic classification and challenge the key assumption that cost functions do not depend on the classifier and are fixed. The paper builds on the premise that classifiers, when used in the real world, incur demand for their features, especially when they lead to a desired prediction. To this end, the authors present a proof of concept using linear classifiers and conduct an empirical study on the `adult` dataset to demonstrate how classifiers impact markets and vice versa.", "questions": "", "limitations": "", "rating": 2, "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 careful reading and important comments. Overall, it seems that your concerns are: (i) clarity of exposition and captions, (ii) discussion of the empirical findings in Sec. 6, (iii) the use of a single dataset, and (iv) contribution.  \nFor (i) and (ii), **we believe these are easily fixable**, especially given the extra page for the final version. For (iii), **we have added another dataset**, please see our response to Rev. 8pCZ. For (iv), **we believe our response below will help establish the contrary** by clarifying the role of budgets. In this case, we kindly hope you would be willing to reconsider your evaluation.\n\n> Empirical results analysis is insufficient\n\nThank you for pointing this out. In hindsight we agree that a more thorough discussion of the results in Sec. 6 would be beneficial – we will gladly expand the discussion here. As you note, there are many potential insights to discuss within the existing results.  \nPlease note however that our empirical analysis spans both Sec. 5 (synthetic data) *and* Sec. 6 (real data). We hope you agree that our discussion in Sec. 5 is adequately comprehensive (as other reviewers note), and that together they provide a useful picture. \n\n> Exposition\n\nAs per your suggestion, **we will add to the introduction a succinct summary of the paper’s contributions as bullet points**. We will also make the distinction from standard strategic classification clear and explicit.   \nOn a more general note: Our paper lies at the intersection of two disciplines. Presenting our setup and motivation in a way that is equally readable to both audiences is not an easy task. We have given this much thought, but it is possible that the current version leans more towards one than the other (given that other reviewers were happy with clarity). If there are any particular clarity issues you feel are present, please let us know and we will improve them.\n\n> Figures/plots\n\nThank you for this input. We will gladly make use of the extra page to clarify and further elaborate.\n\n> If the performance is dependent on budgets, isn't the classifier really classifying based on the budget?\n\n**Generally, no.** Budgets are certainly important, and can play a significant role in determining learning outcomes, but are not the only component that matters. If this were the case, then learning itself would become degenerate. Our results indicate that this is not what happens. The relation between budgets and labels affects accuracy through the market mechanism – **but the market itself depends on the classifier**. Since the classifier h(x) does not take budgets as input, the relations between features x and labels y is what determines the space of *possible* markets. Learning *can* come to rely on features for which budget disparities are dominant (if exist), but it is equally plausible that learning will come to *avoid* such markets. We have included in the appendix a simple 2D example which illustrates this behavior. In the construction, b correlates with y in the direction of x1, but the optimal classifier uses only x2, under which the market is stagnant.\n\n> Last sentences in intro:\n  \nPlease note that these should be read in the context of the preceding sentence – not as a general independent claim.\n\n> How does this algorithm perform when budgets are not correlated with the outcome?\n\nThis is a good question. In general, standard (linear) classifiers work well when the labels correlate with distances from the decision boundary. In strategic market settings, budgets can improve (or degrade) this correlation–which is why they can be helpful. Thus, what matters is the relation between budgets and labels **along the direction of the classifier** (or more precisely, the distances on its negative side). This depends on the classifier and is not an a-priori property of the data. This is also why learning should make use of features (see our point above).  \nIf budgets and labels are completely independent, then the choice of classifier should have little effect on the market. But the more likely scenario is that in some directions features will be more informative, and in others, budgets. An optimal solution is likely one that exploits the combination of these two different sources of information through how they form a market.  \n\n> Do we want to build such classifiers? Or [is this] an accurate description of reality?\n\nThe question of what we should “want” is of course multifaceted and depends on context. What we believe our results convey is that: (a) if we learn naively (in a way that does not account for the market), then market forces will obscure our performance, whereas (b) if we learn in a way that accounts for the market, then this can improve performance, but possibly by exploiting financial inequalities.\n\n> Minors:\n\nline 363: See Hardt et al. (2016).  \nline 296: Yes, we will correct this.  \nline 303: bmin and bmax have been swapped.\nFig 5: We will add arrows for a subset of points.", "claims_and_evidence": "> In standard strategic classification, a useful strategy that exploits this idea is to 'raise the bar'... (line 363)\n\nIs there citation for this?", "methods_and_evaluation_criteria": "No issues here.", "theoretical_claims": "I didn't find major issues with the correctness of the paper's theoretical results. However, there were some incorrect claims that might have been a result of typos. See Questions.", "experimental_designs_or_analyses": "The experimental design itself doesn't have major flaws. Perhaps one could complain about the lack of other datasets, but as long as there are meaningful results and analysis, the number of datasets is not a big issue.\n\nHowever, this paper's empirical results analysis is woefully insufficient. The results section merely describes what we see in Figure 6 and does not derive any meaning from it. I think there is a missed opportunity with the *burden* metric; when I read section 5.3 and Figure 3, I immediately thought of the cost of such classifiers for those with $y = 1$ -- there is quite a bit to discuss here.", "relation_to_broader_scientific_literature": "See other strengths and weaknesses.", "essential_references_not_discussed": "I couldn't think of essential references that the authors did not mention.", "other_strengths_and_weaknesses": "Three major weaknesses:  \n1. **Exposition**  \nAlthough the technical details are not widely complex (which is fine), the paper is hard to follow. For example, in the introduction, there is an attempt to summarize the contributions of the work towards the end, but the takeaways are not clear. \n> we show that markets can give rise to complex behavioral patterns that differ significantly from the conventional model of strategic classification (lines 85-88).  \n\nWhat are the behavioral patterns in conventional strategic classification? I think this is implied in the sentences that follow, but stating it explicitly and contrasting the findings would serve the paper better.  \n\n2. **Figures/Plots**  \nAnother major issue (related to 1.) is how the plots are explained (or not). It takes a very long time to parse the figures (especially figures 2, 3, and 4). The captions are not descriptive. For example, I believe the revenue curves are drawn from a large sample size (since they are smooth), but I can't find any mention of that in the caption or the text. This was especially confusing since figure 1 shows how revenue curves are piecewise linear functions. Considering how figures are supposed to aid understanding, this is a major concern.  \n\n3. **Contribution**  \nLastly, I am not convinced that this is a valuable contribution to strategic classification. This is perhaps an artifact of the lack of analysis in the results section, but I am unsure of the value of considering a classifier-dependent cost function through the paper's mechanism. If the performance is dependent on budgets, isn't the classifier really classifying based on the budget? \n\nFurthermore, consider the last couple of sentences in the introduction:  \n> classifiers will be accurate under the markets if they induce only if they associate positive predictions with high budgets. This raises natural questions regarding fairness and socioeconomic equity.  \n\nThis yields two questions:  \n-  How does this algorithm perform when budgets are not correlated with the outcome?\n-  Do we want to build such classifiers? Or are the authors suggesting that this is an accurate description of reality?", "other_comments_or_suggestions": "- line 296: should be right-skew?\n- line 303: $b_\\textrm{max} = 2^{-\\alpha}$: isn't this smaller than $b_\\textrm{min} = 1$ for $\\alpha > 0$ ?\n- Figure 5: would appreciate if there could be a better way to indicate $\\Delta_{h}(x)$? Its very hard to differentiate the points.\n- If the authors want to use the term \"negative\" outcome, they may want to switch to $y\\in \\\\{-1,1\\\\}$. There are some typos regarding classes (e.g., eq (8), line 193)", "questions_for_authors": "- Why the term \"inequity\" (vs. let's say inequality) in figure 3?\n\n> setting $w=\\boldsymbol{p}$  (line 411)\n- Can the authors reason in detail how this draws on the idea of the main algorithm in [1]?\n\n[1] Hardt, Moritz, et al. \"Strategic classification.\" 2016.", "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": "xRbIi62VYq", "reviewer": "Reviewer_8pCZ", "summary": "The paper studies strategic classification in settings where the cost function for modifying inputs depends on the chosen classifier, via the market this classifier induces. In particular, the chosen classifier determines which features are more \"important\" for positive decisions and therefore affects the demands for each feature, thus also impacting the market equilibrium. The authors propose a natural mathematical framework for this problem, extending the classic strategic classification model. Then, they derive the equilibrium prices for the case of linear classification and propose an algorithm for computing the empirical equilibrium prices. They propose a learning algorithm for their problem and evaluate it on the adult dataset, comparing it to existing methods. The also market adaptation to classifiers in several simple settings, providing further insights into their model.", "questions": "", "limitations": "", "rating": 2, "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 comments. We were glad to hear you see our paper as making a clear conceptual contribution – this was indeed our primary aim and focus.\n\nYour review mentions that you believe our results can be strengthened, in particular by considering (i) alternative proxy losses and (ii) more datasets. In regards to (ii), and as per your suggestion, **we have extended our empirical results to include an additional dataset based on Folkstable**. Results here confirm most of our previous findings and provide additional insights. Regarding (i), we address this and all other points below.\n\n> The proposed method underperforms compared to a standard strategic method\n\nThis is true, but only for small budget scales ($\\le 8$). Note the original data has scale $2^{10}$ (star marker), for which our approach clearly outperforms the baselines and by a large margin. Note also that the x-axis is in logarithmic scale: our method is better in the range $[16,1024]$.  \nIn terms of results, we consider this phenomena an interesting finding. In contrast to our approach (MASC) which anticipates prices that *adapt* to the learned classifier (at equilibrium), the standard approach (strat) assumes fixed prices. Our interpretation of the results is that when the distribution of budgets approaches uniform, price adaptation becomes either mild or inconsequential. In this regime, the “price” we pay to enable differentiability turns out to be larger than the benefits of accounting for price equilibration.\n\n> Perhaps another loss surrogate can perform better?\n\nThis is certainly possible, and we would love for future work to develop better solutions. Note however that designing proxy losses for strategic learning tasks can be quite challenging. Even for standard strategic classification, fundamental concepts such as margins can break completely (see Levanon & Rosenfeld (2022)). The only existing approaches that we are aware of and that apply to our setting are the s-hinge (which we build on) and Hardt et al. (2016), which underlies our baseline. For our market setting, even the connection to the s-hinge is not straightforward, as it is intended for the 2-norm cost – not linear, and the generic extension of the s-hinge to other costs is generally intractable.\n\n> Experiments on other datasets\n\nWe are happy to report that our experimental section has been extended to include another dataset based on Folktables (thanks for this suggestion!). The target variable is employment status, and budgets derive from income. Results show overall similar trends to Adult, but with some distinctions. All methods improve as inequality increases. Our method outperforms all others – here at all scales $\\ge 4$. The % of crosses, welfare, and social burden behave similarly to Adult. Interestingly, and in contrast to Adult, here strat *underperforms* across all scales, even when compared to naive. We will add these results to the final version.\n\n> Can the weights, in general, be both positive and/or negative? \n\nAlthough possible, our approach does not explicitly constrain weights to be positive. This is in line with the results of Hardt et al. (2016) for non-adaptive linear costs. We do however expect them to be such for the learned classifier (otherwise, users would be paying to decrease feature values). \n\n> Vs. Chen et al. (2024):\n\nThis recent paper is similar to ours in that it generalizes strategic classification to support dependencies across user response through the cost function. The main difference is that in their setup, dependencies are encoded explicitly as externalities in the cost function, which is fixed and predetermined. This means that, as in standard strategic classification setup, learning requires knowledge of the particular cost function. In contrast, our work models dependencies as forming indirectly through the market mechanism; the cost function itself is adaptive, and learning only requires knowledge of how the market operates. Another distinction is that externalities depend on the classifier only indirectly: explicitly, they depend on how other points move. Market costs depend on demand rather than on actions; given prices, actions become independent. These distinctions make it hard to draw direct connections between the results and methods of our work and theirs.\n\n> Minors\n\n- Eq. (4): $\\delta$ is defined as the amount purchased. This implicitly depends on b, which constrains how much *can* be purchased.\n- Demand set: Eq. (5) is the definition. Demand set in general is a common construct.\n- a vs. $\\tau$: Thanks – we will correct this.\n- $\\Delta$ in Eq. (6): This is true! Thank you for noticing. The fix is to add $x+$ before the argmax.\n- Sellers have foresight: See e.g. “Noncooperative Collusion under Imperfect Price Information” (Green & Porter, 1984).\n\n----\n\n**Thank you again for your feedback. We hope our response and improvements meet your expectations, and kindly ask you to consider increasing your score.**\n\n----", "claims_and_evidence": "The paper proposes a new framework for strategic classification, motivated by the observation that prices for features may depend on the classifier itself. I find the problem interesting and the proposed model natural and relevant.\n\nOverall, I think that the authors derive an algorithm and conduct an evaluation which are reasonable. That said, several aspects of the work can be strengthened, to make the contribution more convincing. \n\nIn particular, the authors propose a surrogate hinge-like loss for their problem. However, in Figure 6 the proposed method underperforms compared to a standard strategic method. This brings the question of whether another loss surrogate can perform better - perhaps an ablation study for the role of the hinge loss can be helpful here?\n\nSimilarly, experiments on other datasets, e.g. Folktables or some synthetic example like in Section 5 can help to bring further evidence for the empirical effectiveness of the proposed algorithm.", "methods_and_evaluation_criteria": "See above.\n\nAt a few places, the notation and assumptions remain a bit unclear to me - please see below at \"Other Comments Or Suggestions\" for a few specific suggestions and requests for clarifications.", "theoretical_claims": "The derived theoretical results are interesting and interpretable. \n\nIn Section 2, the authors claim that the prices are positive. However, in Section 3 we see that the equilibrium prices are proportional to the linear weights. Am I missing something, or can the weights, in general, be both positive and/or negative? How is that compatible with the prices being constrained to be non-negative?", "experimental_designs_or_analyses": "See above.", "relation_to_broader_scientific_literature": "The conceptual contribution of the paper is clear and extends the framework of strategic classification in a meaningful way. \n\nThe paper of Chen et al. (2024) is mentioned in the related work, however it's unclear to what extend their model and/or techniques are relevant here. Perhaps the authors can elaborate?", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "- In equation 4, I guess delta also depends on b?\n- The authors refer to the \"demand set\" before equation (5). It will be good to give a formal definition of this concept, or at least refer to some relevant source.\n- At a few places, the authors refer to the linear models parameters as w and a, rather that w and tau - it will be nice to sync that throughout the text.\n- In equation 6, Delta is defined as the amount of feature change, rather than the new resulting data point. However, in equation 7, it seems to be used as the resulting data point?\n- Before equation 10, the authors state that they assume that \"sellers have foresight\". Could you please provide a technical statement for this assumption?", "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": "2eZIiaPfQX", "reviewer": "Reviewer_QMW2", "summary": "This paper extends strategic classification to a setting where users seeking positive predictions can purchase features from sellers, leading to the formation of a competitive market. The authors analyze how users respond to prices, how market prices adjust based on demand, and how classifiers influence these dynamics. The authors propose an efficient algorithm for computing prices and introduce a learning framework that takes into account the market effects of a classifier. The authors also demonstrate how the market-aware strategic\nlearning framework performs empirically on real data with simulated market behavior.", "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": "Response:\n\nThank you for your positive review! We were happy to hear that you found our paper exciting and novel. If you have any further questions we would be glad to discuss.\n\n> Would've preferred to validate on multiple datasets\n\nWe are happy to report that **we have extended our experimental section to include an additional dataset**. For details please see our response to Rev. 8pCZ.\n\n> Simplifying assumptions such as linearity in cost modeling etc.\n\nWe agree that supporting more complex costs and models would have been a nice addition. However, as a first step, we think that it is reasonable to focus on a linear construction – especially given that most works on strategic classification consider also linear classifiers and simple cost functions (e.g., linear, 2-norm, or squared).", "claims_and_evidence": "Yes. The claims are well motivated, theoretically sound and supported with experiments.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense", "theoretical_claims": "Yes (Generally went through the statements but didn't check too much in detail)", "experimental_designs_or_analyses": "Yes. They seem fine but would've preferred to validate on multiple datasets instead of just adult income.", "relation_to_broader_scientific_literature": "This paper extends strategic classification and combines it with topics from the markets and learning literature. I found the direction exciting and quite novel. Further empirical validation on real-world economic datasets would strengthen the claim and relevance.", "essential_references_not_discussed": "References are adequate.", "other_strengths_and_weaknesses": "The paper is generally well-written with novel ideas that are theoretically sound, supported by a algorithms for computing prices and learning market-aware classifiers and decent validation through empirical experiments.\n\nA potential weakness is in the simplifying assumptions (such as linearity in cost modeling etc). Another weakness is that the evaluation is quite limited to a single real-world dataset (Adult Income).", "other_comments_or_suggestions": "Minor typos here and there.\nEqn 8, typo in constraint\nLn 213: Aglorithm", "questions_for_authors": "Refer above to comment on datasets/ experiments.", "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": {"ethical_review_concerns": "N/A"}}, {"review_id": "oUkEEarimR", "reviewer": "Reviewer_Y1a5", "summary": "This paper considers a standard binary strategic classification problem with a twist: the costs of manipulating features are endogenized, i.e., determined by a market. For example, college applicants could improve their SAT scores by paying for an SAT prep course, but the cost of the course is determined by market prices. The theoretical and empirical results focus on linear classifiers, linear costs for improving features and the utility of the decision-makers is their classification accuracy. They provide an algorithm for computing market prices for feature improvements given demand for features, and formulate a differentiable proxy objective for learning a classifier. Then they explore the range of outcomes that can occur using simulations, including a simulation calibrated to the Adult dataset.\n\n## Update after rebuttal: I still view the setting and results as interesting. The clarity and questions of the other reviewers does not make me doubt this. I will keep my scores.", "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": "Thank you for your encouraging review and insightful questions.\n\n> Simplifying assumptions such as linear classifiers and linear costs\n\nOur choice to focus on a simple setup stems from several considerations. Indeed, one consideration is tractability (of both pricing and learning problems). Another consideration is simplicity as a guiding principle: as a first step to exploring market-inducing classification, we believe our choices are reasonable. Note also that almost all works on strategic classification focus on linear models and simple costs (e.g., linear, 2-norm). Since our formalism layers on an additional market mechanism, preserving this structure seemed useful. Finally, we hope you agree that despite our simplifying assumptions – the phenomena that arise from the market mechanism are sufficiently interesting, and even surprising, to merit simplifying assumptions. That said – we certainly agree that more elaborate settings are worth pursuing in future work.\n\n> No analysis or comparison of the surrogate loss function or why it is worth including\n\nThis is a great suggestion! **We will gladly add a comparison of the 0-1 loss vs. our m-hinge loss** for settings where computing the 0-1 loss is tractable. In fact, we already have such results for some settings; for example, in Fig. 4 (which shows 0-1 accuracy), the hinge loss can be shown to replace “flat” regions with linear slopes – as can be expected. This suggests that the hinge serves as a useful proxy when slopes push the model towards “lower” flat regions. We can add this to the figure (it was actually removed due to clutter), and include further analysis on other examples in the Appendix.\n\n> In the market setting, most individuals are able to attain the positive classification\n\nWe think we understand your concern, but this claim is not entirely precise. Looking at the results in Fig. 2, it is true that most points end up being able to cross. Fig. 3 suggests that this effect reduces when budgets are more diverse. But both examples consider a single “cluster” of points; once there are more clusters, then it is no longer the case that all or most points will move. The more general phenomena we believe is at play is that *clusters move together*, i.e., the price setter will tend to be an extreme point of *some* cluster. This can be seen for example in Fig. 4 (bottom right): note how changing the budget ratio (y-axis) causes the price setter to jump from being the extreme point of one cluster to that of another.  \nGiven your input, we think it will be valuable to add further empirical investigation of this phenomena. We already have some initial results on this and will gladly add them, either in the Appendix or using the extra page of the final version.\n\n> How well [does] the model describe real-world strategic classification contexts?\n\nThis is a good question which we feel summarizes well many of the previous comments. Real world market dynamics are very likely more complex than our model posits, especially if the market forms in response to a classifier. We believe our model, albeit its simplicity, is still able to capture (at least coarsely) certain effects of transitioning from fixed costs to those of an induced market. But of course this is speculation, and a definitive answer requires much further investigation and research efforts.  \nIn regards to production capacity and costs, these are certainly a natural next step to consider. One reason we focused on no constraints or costs is that this significantly reduced the number of free parameters required to specify the setup. Another subtler point is that it isn’t immediate how constraints and costs operate when transitioning from a finite sample (as in training) to expected outcomes (on which we aspire to evaluate). Having no constraints and costs makes it possible to have a single well-defined market mechanism that captures both and supports the notion of generalization.\n\n> I didn’t understand the connection between Theorem 2 and the fact that almost all points cross\n\nThm. 2 states that, for the considered distributions, (i) there is a unique price setter, and (ii) it lies beyond the peak of uf(u). Intuitively, since this point is typically more extreme than the peak of f(u) itself, the price setter will be positioned at an extreme quantile. We will make this clearer in the next revision.", "claims_and_evidence": "Overall, the idea of endogenizing manipulation costs is an interesting one, and I found the questions answered in the paper to be interesting.\n\nSeveral aspects of the model formulation (mostly simplifying assumptions) should have been more clearly justified. For example, the use of linear classifiers: Either (1) Linear classifiers are commonly deployed in the motivating examples the authors consider. (2) Linear classifiers make the problem tractable and the insights generated are interesting. In either case, beyond explaining why the authors made this assumption, I would have liked to see the analysis extended to other settings (even if just via simulations) to see how the insights change under different analysis choices. I have similar questions about the cost for manipulating features.\n\nSimilarly, there was no analysis or comparison of the surrogate loss function or why it is worth including, beyond the property that it is differentiable and so amenable to gradient-based methods. There was no comparison between solutions obtained by optimizing for the surrogate loss and the global minimum, either theoretically or empirically.\n\nOne of the main qualitative claims in the paper is that in the market setting, most individuals are able to attain the positive classification. This is surprising, and makes me doubt how well the model is describing real-world strategic classification contexts. In applications of interest, do we see this behavior? If not, my guess is that this result comes from the zero capacity constraints and zero production costs, and don’t fit well with real-world contexts of interest. It would be interesting to consider relaxations of these assumptions, and the authors should further justify why they decided to build in these assumptions and why they are illuminating.", "methods_and_evaluation_criteria": "The theoretical results were limited (see the lack of evaluation of the surrogate loss above), and the empirical examples mostly relied on toy examples. I found the simulations to be fairly comprehensive and illuminating about the different possible outcomes. I really appreciated the construction of a classifier that is completely orthogonal to the feature that would be relevant in a non-strategic setting. Generally, the takeaway that strategic classification may lead to classifiers that behave totally differently than naive ones is interesting and worth further exploration. I also found the observations that if budgets correlate with distance to the decision boundary, it is possible to set classification thresholds so as to get high accuracy to be interesting in the simulations. In future work, I would like to see this proved formally, rather than in simulations.\n\nI didn’t understand the connection between Theorem 2 and the fact that almost all points cross, and there wasn't enough discussion for me to follow it.", "theoretical_claims": "Proof of theorem 1 looks good to me. I didn't check the ones in the appendix.\n\nThe techniques used mainly involve solving linear programs and analyzing the simple game induced between the decision-maker and decision subjects. I didn't find the theoretical results very compelling, especially since they strongly depend on the linearity assumptions and structure of price setting on the part of sellers.", "experimental_designs_or_analyses": "The simulations were very interesting, well-motivated and yielded interesting conclusions!", "relation_to_broader_scientific_literature": "This paper contributes a novel model of strategic classification (where costs to change features are endogenous). To my knowledge, this is novel.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The writing was clear and the problem is well-motivated. I wish the authors had spent more time on the observations in section 5 since these were more counterintuitive and interesting than sections 3 and 4.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Why is the surrogate loss good? Does it have good properties? Did you check performance of optimizing against the surrogate loss against brute force solutions.", "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 paper studies strategic classification where the cost of manipulation depends on the classifier.  On the positive side, the reviewers find the paper technically sound, the model natural, and the findings overall interesting.  On the negative side, there were questions about the significance of the contributions, as well as certain aspects of the experimental evaluation.  Overall the reviews collectively suggest this is a valuable contribution that could still be improved, which makes it a borderline case.  We encourage the authors to take the chance and further strengthen their paper regardless of the outcome.
Decision: Accept (poster)