{'fraction_non_alphanumeric': 0.03970932027700587, 'fraction_numerical': 0.007564730272153853, 'mean_word_length': 4.377750103777501, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 39, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Machine Learning for Strategic Inference

We study interactions between strategic players and markets whose behavior is guided by an algorithm. Algorithms use data from prior interactions and a limited set of decision rules to prescribe actions. While as-if rational play need not emerge if the algorithm is constrained, it is possible to guide behavior across a rich set of possible environments using limited details. Provided a condition known as weak learnability holds, Adaptive Boosting algorithms can be specified to induce behavior that is (approximately) as-if rational. Our analysis provides a statistical perspective on the study of endogenous model misspecification.


Introduction
The importance of algorithms in guiding economic behavior is already significant, and likely to only be more so in the years to come. But since a number of economic phenomena rely crucially on the presence of rational individuals on both sides of a particular interaction, an open question is whether traditional rational models apply to such situations. Of course, economists recognize that people often fail to act rationally, with certain consistent failures having empirical implications. But the extent to which algorithms are susceptible to errors is a separate issue, and one that should be addressed for economists to speak to the increasing number of applications where algorithm design plays a central role.
This paper introduces a framework to study the question of whether and when algorithms can approximate rational behavior. In our model, a rational, strategic player (who we refer to as a sender ) chooses a strategy when interacting with an algorithm that prescribes actions to a stream of short lived actors (who we refer to as receivers). 1 A distinguishing feature of our exercise is our focus on the problem of strategic inference: Specifically, we assume that the sender commits to a strategy which maps states into actions, and so a rational receiver would update beliefs about the best reply after observing the sender's action. A rational receiver would thus make an inference regarding a payoff relevant state using knowledge of the sender's strategy. On the other hand, the algorithm has access to observations on what transpired in previous interactions. We are interested in comparing the rational receiver's strategy with the strategy induced by the algorithm, with a focus on determining when rationality can be replicated. We are particularly interested in the case where the algorithm seeks to provide these recommendations without using details of the sender's objective or the particular setting at hand (for instance, as a sales platform might when designing an algorithm to be used for a variety of different products). In other words, we are interested in finding an algorithm capable of inducing rationality under as wide a set of environments as possible.
In our model, the algorithm produces recommendations using data from relevant interactions in the past (where data consists of sender actions and ex-post payoffs). These recommendations are determined by finding a best fitting decision rule. By best fitting, we mean that there is minimal error, with errors being weighted according to some specific objective. The main assumption here is that the algorithm can determine the best fitting rule from a particular set of decision rules, which we refer to as a hypothesis class (following the machine learning literature). A crucial limitation is that this hypothesis class is restricted and must be specified in advance, so that not every feasible mapping from messages into actions can be fit to the data. Thus, there is no a priori guarantee that finding the best fitting rule within the given set yields the rational reply; whether this property holds will depend upon the sender's strategy.
Our theoretical question can be phrased as follows: Do these limitations of algorithms inhibit the ability to prescribe actions which are (approximately) rational? We show that, while constraints may be exploited by strategic actors, an algorithm designer with particular capabilities can induce the as-if rational outcome in equilibrium. The answer to this question thus depends on what we assume the algorithm is capable of. Our contribution is to identify what some of these capabilities are.
Constraints on algorithms of the kind in our model are often studied in the machine learning literature, which typically treats the data generating process as exogenous. Our goal, however, is to perform a similar algorithm design exercise, but in a strategic setting. To make sense of the restrictions on classifiers that can be fit to data, it may be instructive to note that in typical machine learning problems, a simple prediction (for instance, a "yesno" recommendation) is sought for an observation among a very large set of possibilities. Seeking to find the correct recommendation for each one may be intractable or undesireable (given data limitations), and so a simpler set may be used as a baseline. On the other hand, it may still be possible to construct a new decision rule if the algorithm specifies how this should be done in advance. In our model, this takes the form of assuming the algorithm is limited in what can be fit to the data, but is otherwise flexible, in a way we will make precise below.
One interpretation of this limitation is that the algorithm suffers from a form of model misspecification: the true optimal decision rule for a receiver may fall outside of the class of decision rules that can be prescribed by the algorithm. There are two notable differences from a standard model misspecification exercise, however. The first difference is that the algorithm in our framework is concerned explicitly with prescribing behavior, and not with the problem of inference per se. In the (currently very active) literature on model misspecification (see, for instance, Esponda and Pouzo (2014)), a decisionmaker is assumed to be potentially incorrect regarding the set of possible parameters, but otherwise uses an optimally chosen decision rule. We, on the other hand, are not (directly) interested in learning the underlying parameters, but rather making an optimal prediction. The second difference is that the extent to which the optimal prediction falls outside of the realm of considered models is endogenous in our setting. Since we allow algorithms to specify decision rules arbitrarily-instead constraining how models can be fit to the data-they are, in principle, able to expand the potential decision rules the receiver could use if it is specified how this should be done. As a result, the extent to which the algorithm is misspecified is endogenous to the constraints of the algorithm design problem.
What should one expect to happen given these limitations of an algorithm? On the one hand, in order for the algorithm to be able to give non-degenerate predictions without using detailed knowledge of the particular parameters of the receiver's problem, a sufficiently rich set of classifiers should be used. We focus on cases where this criterion suggests using at least the set of single-threshold classifiers, which conditions a recommendation only on which side of a threshold the observable messages lie. However, since our setting requires strategic inference on the part of receivers, this class of hypotheses is susceptible to manipulation by a rational sender. For our purposes, Rubinstein (1993) identified the key economic force, studying a buyer-seller game where the buyer is restricted in the set of decision rules that can be utilized. Specifically, this paper showed that if a rational decisionmaker is restricted to use a single threshold classifier-i.e., one that makes the same decision on a given side of a fixed threshold-then the seller can price discriminate via a particular form of randomization which "fools" these buyers into making a decision which is suboptimal given the realized price. 2 Our framework nests Rubinstein (1993) as a special case, but considers more general environments as well.
Our analysis elucidates a tension between the ability to fit rich and coarse sets of models. As Rubinstein (1993) shows, if a decisionmaker is limited in the decision rules that can be utilized, then there is a potential for exploitation. In order to combat this temptation, one may seek to add more possible replies to be fit to the data; in other words, to make the hypothesis class richer. Indeed, a decisionmaker could prevent the particular instance of exploitation he highlights by doing so. However, fitting richer decision rules may have other undesirable consequences, and may still fail to prevent a slightly more elaborate strategy from succeeding at exploitation. Above, we mentioned that this view is common in the machine learning literature; finding the best fitting model within a set of models may be computationally demanding if this set is very large. A goal of our paper is to highlight this tradeoff between fitting coarse models-which have attractive statistical properties, but poor behavioral properties-and rich models, for which the sitution is reversed.
Our proposed solution is to use the Adaptive Boosting algorithm (Schapire and Freund (2012)), which specifies exactly how to construct a decision rule as a weighted combination of classifiers, with the weights specified by the algorithm. The algorithm requires 2 The reasoning behind this result is as follows. First, the optimally chosen classifier chosen can do strictly better than simply randomizing the guess, implying that the seller can exploit the incentives of the buyer in order to manipulate the decision rule. On the other hand, it is impossible for threshold rules to implement the optimal decision with probability 1 when this rational rule is non-monotone in the price. The first point implies the buyer trades off against errors, and the second point implies that the tradeoff falls short of the fully rational response. As a result, the seller can force a different decision than would be rationally optimal for these buyers (with arbitrarily high probability).
(repeatedly) fitting a classifier to some distribution over prices and outcomes, from some set of baseline classifiers.
Returning to the particular question at hand, the requirement on the set of classifiers able to be fit is called weak learnability, and it is significantly less demanding than requiring all possible rational replies to be specified. We seek to highlight that this requirement is necessary and sufficient to overcome the problem of model misspecification mentioned above, i.e., the gap between the set of decision rules that can be fit to the data and those that a rational receiver can utilize. We provide results which show how to check it in several straightforward applications, particularly when resorting to single-threshold classifiers (which typically have natural interpretations).
To summarize, the answer to our theoretical question is that rationality can be ensured with the ability to (a) find a best-fitting decision rule from a class which satisfies weak learnability, and (b) combine such classifiers in a particular way (specified in advance). It is worth emphasizing one technical difference-due to our focus on a strategic inference problem-between our exercise and similar ones considered in computer science or machine learning where these issues have received more attention. In principle, the rational decision in our model is not observed if the sender uses a strategy that does not reveal the state given an observation. In a lemons problem, for instance, it may be that "low quality" is observed at some price, but that "high quality" is in fact more likely and that correspondingly a rational buyer (receiver) would choose a "buying" action. Therefore, in our problem, the payoff-maximizing decision must be inferred and constructed by the algorithm. One of the main results of this paper is that this added difficulty does not change the qualitative desirable properties of the algorithm, which we show using results from large deviations theory-though this does induce some modifications on precisely how good of an approximation the algorithm is able to guarantee.
Returning to the discussion of Rubinstein (1993), we see that the issue with single threshold classifiers is that they are not strong learners (i.e., they cannot ensure the optimal decision is taken with probability 1 following any price), even though they are weak learners (i.e., they can outperform random guesses when chosen optimally). The remarkable property of the Adaptive Boosting algorithm is that weak learnability is sufficient to construct a classifier that yields a similar guarantee as under a model class satisfying strong learnability. It is interesting that part of the intuition for the main result in Rubinstein (1993)-which relies upon the buyer being able to strictly improve payoffs beyond a trivial default to induce a particular decision rule-exactly tells us how to overcome the main conclusion, once we have the algorithm in hand.
At first glance, it appears that there is a significant gap between decision rules satisfying weak learnability and those which induce rational replies. Rationality requires, in principle, very rich decision rules to be used, and for the performance of them to leave very little room for error. Weak learnability does not, and only requires a uniform improvement over a random guess. It is therefore perhaps surprising that in our exercise, the turns out to be no gap at all. Due to weak learnability, the apparent gap in rationality caused by the limitation in the decision rules that can be fit to data can be overcome by a clever choice of algorithm. The result is that the algorithm can induce rational behavior without knowing anything beyond the observed data from past interactions. In contrast, strong learnability (i.e., prescribing the optimal action with high probability) will usually require precise knowledge of the sender's strategy.
We briefly mention that the algorithm design problem we study accommodates a rich possible action space, even with the same restrictions in the decision rules that can be fit to data. In particular, a version of the weak learnability condition in settings with two possible receiver actions also applies to settings with an arbitrary finite number of actions. This is in sharp contrast to many other papers in the large literature on "decisionmakers as statisticians" (reviewed below), which use similar motivation to study departures from rationality. These papers have typically focused on the binary action case. This limitation is very natural-many of the key results from machine learning which arise when there are two possible predictions do not extend easily (or even at all) to the case of multiple actions. However, we can handle this in our problem, suggesting our algorithm is of broader interest. We believe that this extension is important, as it shows our conclusions do not hinge on other artificial limitations on the environment.
Our exercise provides formalism within which machine learning methods can be applied to answer new questions relevant to microeconomic theorists, and visa versa. Our model is deliberately abstract, in order to provide general principles guiding when the problem of model misspecification can be overcome. One key message is that while it is not possible to guarantee that rationality emerges for arbitrarily data generating process, it is possible if the data generating process is endogenous (due to the strategic player) to the statistical algorithm. This argument requires some additional steps using incentives of the actors to demonstrate that the resulting output does in fact correspond to what is traditionally thought of as subgame perfection. This endogeneity issue makes the problem no longer a pure statistical exercise. The modifications our analysis requires extend beyond the initial need to show that it is possible to do better than random guessing in this environment. As our analysis elucidates, AdaBoost is capable of handling a particular kind of unboundedness in the cardinality of the action space. It is thus necessary to discipline the environment further in order to achieve our results.

Literature
This paper takes the framework of PAC learnability, familiar from machine learning, and applies it to a strategic setting. Within economics, this agenda is most closely related to the literature on learning in games when behavior depends on a statistical method. The single-agent problem is a particular special case, and this case is the focus of Al-Najjar (2009) and Al-Najjar and Pai (2014). However, since we are focused on a strategic setting, the data the algorithm receives is endogenous in our setting. In contrast, their benchmarks correspond to the case of exogenous data. This problem is also studied in Spiegler (2016), who focuses on causality and defines a solution concept for behavior that arises from individuals fitting a directed acyclic graph to past observations. More recently, Zhao, Ke, Wang, and Hsieh (2020) take a decision-theoretic approach in a single-agent setting with lotteries, showing how a relaxation of the independence axiom leads to a neural-network representation of preferences.
Taking these approaches to games, the literature has still for the most part focused on settings where the interactions between players is static, ruling out the main environments we are interested in here. 3 In contrast, our setting is a simple, two-player (and two-move) sequential game. We also note that much (though not all) of this literature focuses on binary prediction problems, whereas we discuss how to specify algorithms in the general finite action cases as well. Cherry and Salant (2019) discuss a procedure whereby players' behavior arises from a statistical rule estimated by sampling past actions. This leads to an endogeneity issue similar to the one present in our environment, i.e., an interaction between the data generating process and the statistical method used to evaluate it. Eliaz and Spiegler (Forthcoming) study the problem of a statistician estimating a model in order to help an agent take an action, motivated as we are by issues involved with the interaction between rational plays and statistical algorithms. Liang (2018) also focuses on games of incomplete information, asking when a class of learning rules leads to rationalizable behavior. Studying model selection in econometrics, Olea, Ortoleva, Pai, and Prat (2019) consider an auction model and ask which statistical models achieve the highest confidence in results as a function of a particular dataset. 4 On the other hand, the literature on learning in extensive form games has typically assumed that agents experiment optimally, and hence embeds notion of rationality on the part of agents which we dispense with in this paper. Classic contributions include Fudenberg and Kreps (1995), Fudenberg and Levine (1993) and Fudenberg and Levine (2006). Most of this literature has focused on cases where there is no exogenous uncertainty regarding a player's type, and asking whether self-confirming behavior emerges as the outcome. An important exception is Fudenberg and He (2018), who study the steadystate outcomes from experimentation in a signalling game. While a rational agent in our game would need to form an expectation over an exogenous random variable, signalling issues do not arise because our sender has commitment.
Perhaps closest in motivation is the computer science literature studying how well algorithms perform in strategic situations, as well as how rational actors may respond when facing them. Braverman, Mao, Schneider, and Weinberg (2018) consider optimal pricing of a seller repeatedly selling to a single buyer who repeatedly uses a no-regret learning algorithm. They show that, on the one hand, while a particular class of learning algorithms (i.e., those that are mean-based) are susceptible to exploitation, others would lead to the seller's optimal strategy simply being to use the Myersonian optimum. Deng, Schneider, and Sivan (2019) also study strategies against no-regret learners in a broad class of games without uncertainty, and consider whether a strategic player can guarantee a higher payoff than what would be implied by first-mover advantage. Blum, Hajiaghayi, Ligett, and Roth (2008) consider the Price of Anarchy (i.e., the ratio between first-best welfare and worst-case equilibrium welfare), and show in a broad class of games that this quantity is the same whether players use Nash strategies or regret-minimizing ones. Nekipelov,3 By itself the distinction may not immediately seem significant-after all, a Nash equilibrium in an extensive form game involves choosing a strategy to best respond to the opponent, and is usually stated as a single (and thus static) choice. However, the additional restriction to binary action or 0-1 prediction problems makes nesting our problem less straightforward.

4
On the question of algorithms in particular, one concern is that the algorithm design problem may be susceptible to bias or induce unwanted discrimination when implemented, relative to rationality. See Rambachan, Kleinberg, Mullainathan, and Ludwig (2020) for an analysis of these issues and how they may be overcome.
Syrgkanis, and Tardos (2015) assume players in a repeated auction use a no-regret learning algorithm, making similar behavioral assumptions as we do here. Their interest is in inferring the set of rationalizable actions from data. While our motivation is very similar-and indeed, we seek to incorporate several aspects of this literature's conceptual framework-there are three notable differences. First, this literature typically assumes particular algorithms or principal objectives (such as no-regret learning) which differ from traditional Bayesian rationality. In contrast, we maintain a Bayesian rational objective for the seller, and also focus on an algorithm designer seeking to maximize the expected payoffs of agents. Second, we focus on relating the incentives of the rational player and the algorithm's capabilities, and study the extent to which different assumptions on the algorithm design problem influence the task of approximating rationality. Our main result articulates how different action spaces for the algorithm designer yield different results regarding whether and when the outcome will approximate the rational benchmark. Lastly, our general framework focuses on settings with strategic inferencethat is, where the payoffs following a given principal action are state-dependent-and thus covers a set of single-agent applications which extend beyond particular pricing settings, where most (though admittedly not all) of this literature has focused. In particular, the settings discussed in this literature do not cover Lemons markets settings (which Rubinstein (1993) falls under, for example) or Persuasion, which form our primary starting point. 5 As a result, new technical issues (e.g., dealing with residual uncertainty in the correct actions) is not addressed in these papers to our knowledge. Despite these differences, our hope is that this paper inspires further connection between the economics literature on decisionmakers as statisticians and the computer science literature on strategic choices against classes of algorithms. It appears to us that these results from computer science have not yet been fully appreciated in economics.

(Sender-Receiver) Stage Games
We first describe the stage game interaction in which the algorithm designer seeks to prescribe actions on behalf of myopic actors (who may be, for instance, receivers, buyers, or agents, depending on the particular setting of interest). The stage game features a strategic actor as well. That said, our exposition in this section addresses neither how the strategic actor chooses her strategy, nor how the algorithm is determined. This is done in Section 4, which describes the interaction which yields these objects and the relevant objective for each actor.

5
An important exception is Camara, Hartline, and Johnsen (2020), who study an environment covering many of our same applications such as Bayesian Persuasion. However, they still maintain the other two distinguishing features, focusing on a regret objective for the principal, as well as particular no-regret assumptions for the agent. Still, we emphasize that both our paper and theirs focuses on environments where the principal/sender chooses a state-dependent strategy. This leads to the aforementioned endogeneity between the data generating process (induced by the principal) and the choices of the algorithm/learner-this emerges due to the fact that the same sender action may induce two distinct replies from the algorithm following two distinct sender strategies. In their setting, this endogeneity motivates the use of "policyregret" as an objective for the principal (due to their reinforcement learning approach to the principal's problem). While we do not use a regret objective for the principal, see Arora, Dekel, and Tewari (2012) and Arora, Dinitz, Marinov, and Mohri (2018) for more on the differences between these notions.

Actions and Parameters.
The stage game is a sender-receiver game in which an informed sender makes the first move. We often call the sender the (informed) principal, and the receiver the agent, as our lead example is built on the informed principal problem of Maskin and Tirole (1992). However, our model also describes a sender-receiver game with sender commitment, as in Kamenica and Gentzkow (2011).
Let Θ be the set of types endowed with a prior distribution π which is common knowledge among players. This type is payoff relevant to both the sender and the receiver. Define π(θ) as the probability that type θ ∈ Θ is realized. Throughout the paper, we only consider π with finite support. Conditioned on the realized value of θ ∈ Θ, the sender takes an action p ∈ P ⊂ R n where P is a compact subset of R n . Our analysis in most of the paper will assume further that |P| < ∞, although we discuss how to modify this assumption in Section 5.3.3 (to allow for, for instance, continuous distributions). A strategy of the Sender is: σ : Θ → ∆(P), where ∆(X) denotes the set of probability distributions over a set X. We let Σ denote the set of feasible strategies for the sender, and importantly, assume that this strategy is determined (and committed to) in the Algorithm Game described in Section 4. Conditioned on p (but not θ), the agent chooses a ∈ A according to r : P → ∆(A).
We assume|A| < ∞, and in our analysis we treat the case of |A| = 2 and |A| > 2 separately. The payoffs of the sender and the receiver from (θ, p, a) are u(θ, p, a) and v(θ, p, a).
The timing of the moves in the stage game is as follows: S 1 . An exogenous state θ ∈ Θ is realized according to π, with only the sender observing the realized state θ. S 2 . The sender's action p ∈ P is realized according to σ(p : θ). S 3 . The receiver takes action a ∈ A conditioned on p. S 4 . Payoffs are realized according to u(θ, p, a) and v(θ, p, a). For instance, if we interpret p = (p 1 , . . . , p n ) as a contract, and a ∈ A = {−1, 1} as "reject" (a = −1) or "accept" (a = 1), the stage game is a model of the informed principal (Maskin and Tirole (1992)). If p is interpreted as a message sent by a worker, and a ∈ A as the wage paid by the firm, then the stage game becomes a signaling game (Spence (1973)). For now, we place no further restrictions on u(θ, p, a) and v(θ, p, a), though these are often implicit in the economic problem of interest.
3.2. Payoffs and the Rational Benchmark. Describing the outcomes of the above interactions when the receiver is rational is a familiar exercise. In this case, his optimization problem is max where π(θ : p) is the posterior probability assigned to θ conditioned on p. If p is used with a positive probability by σ, then π(θ : p) is computed by Bayes rule: .
We define the rational label to denote the receiver's strategy were they rational. More precisely, the optimal response is a function of the chosen σ ∈ Σ and the realized p ∈ P: is a solution to the following optimization problem: where π(θ : p) is computed via Bayes rule whenever θ σ(p : θ)π(θ) > 0. 6 Define σ R as a best response of the sender against a Bayesian rational receiver with perfect foresight: By the construction, (σ R , y R ) constitutes a perfect Bayesian equilibrium in the stage-game with a rational receiver.
3.3. Examples of Stage Games. Before proceeding to the description of the algorithm game, we describe a few of the stage game interactions that are of primary interest. We will return to these later in order to illustrate the incentives for each player.
3.3.1. Insurance. The following is borrowed from Maskin and Tirole (1992). Suppose that the principal (sender) is a shipping company seeking to purchase insurance from an insurance company, an agent (receiver) that is seeking to delegate the decision of whether to offer the terms put forth by the shipping company. The principal seeks insurance every period, but faces risk (e.g., due to the location of shipping demand) that is idiosyncratic every period.
In this case, we imagine the principal choose terms within some compact set P ⊂ R 2 , where p = (x, q) denotes a policy which provides a payment x in the event of a loss, and costs an amount q. If θ ∈ {L, H} (with L < H) denotes the probability of a loss, then the principal's utility is: for some concave f . The agent's utility is: It is natural to consider P whereby, against a rational buyer, the principal would seek a high level of insurance when risk is high (i.e., θ = H), and avoid insurance when risk is low (i.e., θ = L). In contrast, the agent's payoff may be decreasing in the quantity of insurance when θ = H, while increasing in the quantity of insurance when θ = L.

Labor Market Signaling.
Our framework is general and can be expanded to cover other settings as well. Let us consider a labor market signaling model. Here, the "receiver" takes the role of the firm and the "sender" takes the role of the worker from the Spence signalling model (as in, for instance, Maskin and Tirole (1992)). The true state is the productivity of the worker θ ∈ Θ = {H, L} where π(H) = π(L) = 1 2 : H > L. Conditioned on θ, a worker chooses p which we interpret as education level. Her strategy is The payoff function of the sender is u(θ, p, a) = a − p θ + 1 We abstract away the competition among multiple firms in the labor market. Conditioned on p, the labor market wage is determined according to the expected productivity E(θ : p) conditioned on p. The firm has to pay the worker the equal amount of the expected productivity because of (un-modeled) competition among firms. The receiver's goal is to make an accurate forecast about the expected productivity of the worker. The payoff of the receiver is If the support of σ(p : H) is disjoint from the support of σ(p : L), σ is a separating strategy. If a separating strategy is an equilibrium strategy, then the equilibrium is called a separating equilibrium. We often focus on the Riley outcome, which maximizes the ex ante expected payoff of the principal among all separating equilibria.

Monopoly Market.
In the first two examples, only the sender has private information. We can allow the stage game interaction to feature additional parameter observed only by the receiver, denoting this by i. We denote the sender's payoff by u(θ, p, a, i), and the receiver's payoff by v(θ, p, a, i). For example, the sender may interact with some receivers who are algorithmic, and others who are fully rational. The agent knows whether he is algorithmic or fully rational. The principal does not observe the type of an agent, but only knows the probability distribution. Indeed, the setting of Rubinstein (1993) features such a dichotomy, as we discuss. While Rubinstein (1993) differs expositionally, we review the key ideas and describe how it falls under our framework.
The action of a buyer is a ∈ A = {−1, 1}. A buyer responds to p ∈ P by purchasing (a = 1) or not purchasing (a = −1) the good at p.
The seller is facing a unit mass of infinitesimal buyers, who can be either type 1 or type 2. The proportion of type 1 buyer is r ∈ (0, 1). A buyer observes his type, but the seller does not observe the type of a buyer. The buyers differ in terms of the cost of sales. If θ = L, the product costs c L for the seller regardless of the types of the buyer. If θ = H, the product costs c i to serve type i buyer (i ∈ {1, 2}). We assume so that the agent is exposed to the lemon's problem. We focus on π supported on parameters which satisfy (3.1) and (3.2).
A buyer generates utility only if he purchases the good, whose payoff function is The unique equilibrium strategy of the seller is The buyer's equilibrium strategy is The trading occurs only if θ = L, and therefore, the equilibrium is inefficient. Note that the construction of y R requires a precise information about v L .
3.4. Introducing Time. Our question of interest is whether the receiver can learn the rational label y R , if the stage game is repeated over time. As an intermediate step toward defining algorithm games, we describe our approach and assumptions involved with this step. In the next section, we discuss the algorithm choice that occurs on top of this.
By expanded stage game, we refer to a repetition of the stage game interaction, played over discrete time t = 1, 2, . . ., where the stage game interactions described previously occur at every t ≥ 1. Let (σ t , r t ) be the pair of strategies by the sender and the receiver in period t. 7 The true state θ is drawn IID across periods according to π and the pair (p t , a t ) of the price and the action in period t is selected by (σ t , r t ). In this case, the expected payoff of the sender is 8 and the expected payoff of the receiver is For now, we are intentionally vague about the strategy space of each player in the expanded stage game, as this is described in the next section. 8 Our results are most elegantly stated in the undiscounted limit. Prior versions of this paper considered the case where future payoffs were discounted at rate δ < 1; the main lessons remain valid for δ sufficiently large, although there are some added technical difficulties in the analysis of Section 5.3.3 this introduces.

Algorithm game
Having outlined the basic timing of moves, we now describe the "super" game which determines the player's strategy in the expanded stage game. We refer to this as an algorithm game. Throughout this paper, we assume that the sender (principal) is fully rational, but the strategic choice of the receiver (agent) must be delegated to an algorithm. 4.1. Choices of Algorithms. We will refer to the strategy a receiver uses-which is output by the algorithm at every time-as a classifier, in line with the machine learning and computer science literature: This may additionally be referred to as either a strategy or a forecasting rule.
In order to construct the classifier, the algorithm faces some computational constraints. More precisely, we assume that there is a fixed set of classifiers H (referred to as the hypothesis class) for which the algorithm can solve the following problem: for an arbitrary function L and function y : P → A. We refer to this step as finding the best fitting hypothesis. We can think of L as being the cost of misclassifying a particular observation, which may vary. Note that, since we can add arbitrary constants to L and normalize so that it sums to 1 over all p, it is equivalent to assume the algorithm can solve for a probability distribution d over p. This provides an alternative interpretation, regarding the classifier seeking to make the correct guess with the highest possible probability. We treat the process of finding the best fitting hypothesis as a black box. The purpose of this paper, however, is to understand how the algorithm designer might utilize from additional capabilities, and across a variety of environments. One question is which kinds of additional capabilities are necessary. The main ones we will discuss are: • Constructing labels based on observations, • Creating classifiers derived from solutions to the above maximization, • Changing observations of p t top t , if the data is generated by a randomized rule.
One hypothesis class is of particular interest. Let H(λ, ω) be a hyperplane in R n : ∃λ ∈ R n and ω ∈ R such that Define H + (λ, ω) as the closed half space above H(λ, ω):

Definition 4.2. A single threshold (linear) classifier is a mapping
Definition 4.3. Let Γ be the set of all classifiers, andΓ ⊂ Γ denote a subset of classifiers. A statistical procedure or algorithm is an onto function where D is a set of histories, T is the set of feasible algorithms (i.e., a subset of the set of functions from D intoΓ).
What D consists of is very much problem specific. In a typical learning model, we assume that the receiver observes the realized outcome (p t , a t ) in period t but also can access some information about the performance of his choice a t to achieve his goal. For example, if the goal of the receiver is to learn the rational label y R , a natural candidate would be a sufficient statistics of the ex-post payoff v(θ t , p t , a t ).
One specification of T emerges from not having any restrictions onΓ at all. In general, the setΓ will be implicit in the description of the algorithm. Our main interest is in understanding which kinds of T enable the receiver to approximate the rational label y R .

Timing and
Objectives. An algorithm game takes the interaction in the stage game as a starting point, and considers the outcome when, instead of having the receiver's strategy emerging from Bayesian rationality, it instead emerges from fitting a model to past observations. An algorithm game is a simultaneous move game under asymmetric information between the (rational) sender and the boundedly rational ("algorithmic") receiver, built on the "expanded" stage game.
A −1 . According to some prior distribution, nature selects the distribution π of the underlying game from Π, where Π is a subset of probability distributions over Θ with finite support. A 0 . Conditioned on realized π, the sender commits to some strategy σ. The receiver (or alternatively, an entity acting on the receiver's behalf) commits an algorithm τ ∈ T without observing the realized π ∈ Π. A 1 . The expanded stage game is played, with the receiver's strategy in each period t being τ (D t )(p) (i.e., the action specified by the algorithm following sender's action p at time t), with the algorithm adding the observation (which includes p and ex-post utility following each receiver action) to the dataset at the end of each period.
These actions determine the realized payoffs by each player, as described in the previous section. Notice that we do not necessarily assume that any pair π 1 , π 2 ∈ Π have intersecting or even overlapping support (though this is also certainly allowed). Correspondingly, we emphasize we do not assume Θ is itself finite, even though all π ∈ Π have finite support.
Additionally, since we only assume the algorithm observes the receiver's ex-post utility, θ itself need not ever observed by the algorithm. For instance, θ may reflect a production cost which only influences the sender's payoff. In this case, while the algorithm would observe the receiver's payoff from each action, they would not observe the seller's cost. The sender chooses σ once and for all, with the action p t drawn i.i.d. over time. On the other hand, the receiver's strategy in period t is determined by the algorithm τ and history D t in period t. The expression for the payoffs of the sender and the receiver are (3.3) and (3.4), respectively, where r t (· : p) is given by τ (D t )(p).
We consider the objectives of the rational player and the algorithmic player separately. The former is straightforward; given a sequence (θ t , p t , a t ), the rational player's payoff (i.e., the sender's payoff) function is simply the long run average expected payoff: where (p t , a t ) is generated by (σ, τ ) in period t and the expectation is otherwise conditioned only on π ∈ Π (recalling that θ is taken to be drawn IID). The objective of the rational sender is to maximize U s by choosing σ, conditioned on π ∈ Π. The payoff function of the algorithm player is also the long-run average expected payoff: Note that implicitly we the players do not discount future payoffs, we call the algorithm game an algorithm We are interested in comparing the outcomes induced by the algorithm and the rational label y R (σ, p) introduced in the last section. We note that the comparison is potentially unfair because algorithms are more constrained in the decision rules that can be used. We therefore introduce a notion of rationality reflecting these limits: with the probability referring to uncertainty over D t . An algorithm τ is fully rational if Γ is replaced by the set of all h : P → A.
The "constrained" qualifier is due to the limits on the strategies that can be chosen by the receiver. A fully rational receiver would choose y R (σ, p) in the stage game; a constrained rational algorithm yields actions are as optimally as possible, given that its output must be within the expanded model classΓ. We often regard γ ∈Γ as a forecasting rule and τ as a formal procedure to construct a (strong) forecasting rule.
In later sections, we will also discuss an important performance criterion of an algorithm is PAC (Probably Approximately Correct) learnability (Shalev-Shwartz and Ben-David (2014)).
with the probability referring to uncertainty over D t and the realized p.
A key difference between Definitions 4.4 and 4.5 is that the latter is a condition on the actions themselves and the decision rule, yet the former is a condition on the utility. In order to learn the equililbrium outcome y R (σ R , ·), σ R must be a best response to the decision rule induced by the algorithm in the long run.
Definition 4.6. An outcome (σ, τ ) of the algorithm game emulates (σ R , y R ) of the underlying stage game, if σ = σ R and τ is fully rational.
The substance of the definition is that σ R is a best response to τ . Then, along the equilibrium path of the algorithm game, the receiver behaves as if he perfectly foresees σ R and responds optimally subject to the feasibility constraint imposed byΓ.
4.3. Specifying T . Our main interest will be in the case where T is restricted to emerge as the outcome of an ensemble algorithm. Without loss of generality, we can assume that K k=1 α k = 1, since if not we can simply divide by this sum and obtain the same classifier. We can interpret H as a weighted majority vote of h 1 , . . . , h K . An ensemble algorithm constructs a classifier through a linear combination classifiers from H. Since the final classifier is constructed through a basic arithmetic operation, one can easily construct an elaborate classifier from rudimentary classifiers. Ensemble algorithms have been remarkably successful in real world applications (Dietterich (2000)).
The algorithms produce an output ensemble classifier according to a recursive scheme: • First, the loss function in (4.5), say L 1 , or probability distribution in (4.6), say d 1 , is taken to treat all observed sender actions symmetrically-that is, L 1 (p) = d 1 (p) = 1/G where G is the number of elements in the support of mixed strategy σ. • At each stage k = 1, . . ., the best fitting hypothesis is found by solving either (4.5) or (4.6). The best fitting hypothesis is referred to as h k . • The term α k is then determined, possibly as a function of the objective of the best fitting hypothesis. • Depending on h k and α k , the loss function L k is updated to L k+1 (or, in the case of distributions, d k is updated to d k+1 ). • After repeating this iteration K times, a classifier of the form of Definition 4.7 is output, which is used to determine the final choice of the receiver.
The ability to use an ensemble algorithm allows additional richness in the set of classifiers that can be used. There remain, however, a number of challenges: • Clearly, repeatedly solving the same problem will not yield different outcomes, and so to meaningfully expand H one needs to determine how to change the objective to be fit as well, and • Weights must be specified in advance. Both of these are on top of the need to potentially alter the observed p t and determining the labels y t (σ, p t ) to use for the observations, since the observed utility-maximizing decision need not coincide with the rational one ex-post.
Remark 4.8. The reader may still wonder why algorithm design is necessary in the first place. For instance, if y R (σ, p) is a single threshold rule, it may be surprising that simply fitting the optimal single threshold rule to the data is insufficient to emulate rationality. While it may be sufficient in some cases, it is not in general, and in particular the ability to emulate rationality does not follow from the rational reply being in H; the reason is that it is necessary to be able to construct richer rules in order to deter the sender from deviating to exploit limitations in H, which would prevent the receiver from choosing the rational reply "off-path." This is articulated in Section 5.3.2, where we also clarify the role of taking a richer set of possible Π, to correspondingly justify choosing a sufficiently rich set of H to begin with.

Main Results
We now present our main results, showing the existence of an equilibrium of the algorithm game where the rational reply is emulated. We begin with a preliminary observation, useful for understanding our subsequent analysis: PAC learnability is a sufficient condition for the algorithm game to have a Nash equilibrium emulating (σ R , y R (σ R , p)).
This observation suggests it suffices to show the PAC-condition holds; in that case, the sender would find it optimal to choose σ R , and by definition it would not be possible for the receiver to outperform rationality. However, there are two main difficulties which we seek to emphasize: (1) First, it may be that y R ∈ H, and yet if H is limited then the rational outcome cannot be emulated without expanding the set of feasible decision rules, and (2) Second, one still needs to specify how the algorithm should use the historical data in inferring the correct decision. This section addresses each of these issues. We first consider the case where the receiver knows the values of y R (σ, p) ∀(σ, p). We then show, in Section 5.1, that the PAC-condition holds for an algorithm: Proposition 5.2. If the receiver knows the values of y R (σ, p) ∀(σ, p), there exists an algorithm τ A that is PAC learnable. Thus, (σ R , τ A ) is a Nash equilibrium of the algorithm game, which emulates (σ R , y R ).
We then turn to the case where the algorithm cannot observe y R (σ, p). This yields an algorithm τÂ, which coincides with τ A with the added step of inferring the labels. We show that we obtain an analogous result for this case in Section 5.2: Proposition 5.3. Suppose that y R (σ, p) is a strict best response ∀σ but the receiver does not observe the values of y R (σ, p). Then, there exists an algorithm τÂ that is PAC learnable. (σ R , τÂ) is a Nash equilibrium of the algorithm game that emulates (σ R , y R ).
In our analysis, the first step is to construct an algorithm that generates an accurate forecast in the long run. The remaining step is to show whether the sender has an incentive to choose σ R against τÂ in the algorithm game, in Section 6. 5.1. Specifying the Algorithm and Weak Learnability (Proposition 5.2). 5.1.1. Weak Learnability. The sufficient condition which ensures we can approximate an arbitrary decision rule combining single-thresholds is weak learnability. Roughly speaking, weak learnability says that the hypothesis class can outperform someone who had some very minimal knowledge of the truth of the hypothesis. That is, it must be that the hypothesis class can do better than a someone who made a random guess, which would be made correct with some arbitrarily small probability. While this may seem permissiveand indeed, it is certainly less stringent than requiring it can approximate the truth with high probability-the difficulty in achieving it is the fact that this guarantee must be uniform over all possible distributions.
We formally define this as follows: h is an optimal weak hypothesis.
Definition 5.5. If |A| = 2, a hypothesis class H is weakly learnable if, for every distribution d over observations p ∈ P (σ) and labels y(p), the optimal weak hypothesis satisfies: If |A| > 2, a hypothesis class H is weakly learnable if, for every distribution d over observations p ∈ P (σ) and labels y(p), the optimal weak hypothesis satisfies: for some ρ > 0 and some distribution B over A.
The second condition is a generalization of the first, though the first is perhaps more familiar from the machine learning literature (as most attention has focused on the twolabel case). This condition reflects the idea that the classifier randomly guesses the label according to some distribution B, but is "flipped to being correct" with probability ρ. For the |A| > 2 case, the right hand side describes the expected error in such a case, and the left hand side describes the error from the optimal weak classifier.
If weak learnability fails, then no recursive ensemble algorithm can be built to approximate y(p) based on H alone. 9 Perhaps more surprising is that it is tight, a fact which we discuss further in Section 5.3.1. For now, we simply mention that if we take H, the set of single threshold classifiers is weakly learnable.
Proposition 5.6. The set of single-threshold classifiers satisfies the weak learnability condition of Definition 5.5.

Proof. See Appendix A.
Our proof uses the important fact: Any hypothesis class that contains all label permutations can at least match the random guess guarantee. The proof of this intermediate lemma uses a duality argument in order to show that no distribution can lead to a lower payoff when this condition is satisfied. Importantly, however, this is true for any hypothesis class, including the trivial one. This observation allows us to show that the added richness of single-threshold classifiers is sufficient to provide the additional gain over random guessing.

From Weak Learnability to Decision Rules. For simplicity, we present the case where
leaving the general case to the appendix. The formal description of the algorithm takes two steps. First, we describe an algorithm under the assumption that the receiver knows the value of y R (σ, p) ∀p. If A contains two elements, the specification of the algorithm parameters coincides with the Adaptive Boosting algorithm τ A of Schapire and Freund (2012). We first outline the parameters and then review, for completeness.
The kth stage (initializing with the uniform distribution if k = 1) starts with probability distribution d k (p) over the support of σ. Define 9 For example, imagine H only consists of trivial classifiers. A corollary of a result in Appendix A.1 is that these classifiers can do equally well as a random guesser. However, it is clear that they cannot do strictly better, as they are restricted to giving the same guess to all possible p, unlike a random guesser who is correct with an added probability ρ.
as the probability that the optimal classifier h k at k misclassifies p under d k . If ǫ k = 0, then we stop the training and output h as the forecasting rule, which perfectly forecasts y R (σ, p). Suppose that ǫ k > 0. Define The weak learnability of the single threshold rule implies that ∃ρ > 0 such that Define for each p in the support of σ, and each pair (p, y R (σ, p)), Given d k+1 , we can recursively define h k+1 and ǫ k+1 , both of which are functions of d k+1 as per the above.
The decision of the receiver is based upon which is equivalent to is the sign of real number x. Following Schapire and Freund (2012), we can show that for any mixed strategy σ, where G is the number of elements in the support of σ. 10 5.2. Inferring the Rational Label (Proposition 5.3). Next, we drop the assumption that the receiver can observe σ so that he can calculate the expected utility conditioned on p in the support of σ: θ v(θ, p, a)µ(θ : p) (5.10) where µ is computed via Bayes rule, and therefore, knows the value of y R (σ, p). If the receiver does now know y R (σ, p), then he cannot calculate ǫ k in (5.7). We need to construct an estimatorŷ t (p) for y R (σ, p) from data D t available at the beginning of period t. How we construct estimatorŷ t (p) depends upon the specific details of the rule of the game such as the available data and the variable of interest. We require thatŷ t (p) satisfies a regularity property.
We require thatŷ t (p) satisfies the large deviation property (LDP), which is a stronger property than consistency.
Definition 5.8.ŷ t (p) satisfies large deviation properties (LDP) if ∃λ > 0 such that, ∀p in the support of σ, If an estimator satisfies LDP, the tail portion of the forecating error vanishes at the exponential rate, as the sample average of i.i.d. random variables converges to the population mean. If an estimator fails to satisfy LDP, the finite sample property of the estimator tends to be extremely erratic (Meyn (2007)). Most estimators in economics satisfy LDP.
In the three examples illustrated in Section 3.3, the variable of interest is the probability distribution of the underlying valuation conditioned on p ∈ P. Let π(v : p) be the posterior distribution of v conditioned on p. If v is drawn from a finite set, then π(v : p) is a multinomial distribution. Letπ t (v : p) be the sample average for π(v : p). We know that the rate function ofπ t (v : p) is the relative entropy ofπ t with respect to π (Dembo and Zeitouni (1998)) from which we derive λ in (5.11): ∀ǫ > 0, let N ǫ (π) be the ǫ neighborhood of π(v : p), and λ = inf πt ∈Nǫ(π) I π .
Note that y R (σ, p) =ŷ t (p) only if π andπ t prescribe differen actions. Sinceπ t is a consistent estimator of π, the probability of two probability distributions prescribing two different actions vanishes. The large deviation property ofπ t implies thatŷ t (p) satisfies (5.11), if y R (σ, p) is a strict best response. By the concavity of the logarithmic function, I π is minimized if π is a uniform distribution and inf π I π > 0.
If |P | < ∞ and |A| < ∞, we obtain the uniform version of (5.11) with respect to the true probability distribution. We state the result without proof for later reference.
Lemma 5.9. Suppose thatŷ t (p) is consistent and satisfies (5.11). Then, ∃λ > 0 such that lim sup t→∞ − 1 t log P y R (σ, p) =ŷ t (p) ∀p in the support of σ ≤ λ. (5.12) We construct algorithm τÂ by replacing y(σ, p) byŷ t (p) in τ A constructed in the previous section. More precisely, let f y t (p) be the empirical probability thatŷ t (p) = 1 at the beginning of period t. Thus,ŷ t (p) = −1 with probability 1 − f y t (p).
Using weak learnability, we can show that ∃ρ > 0 such that Sinceŷ t (p) has the full support over {−1, 1} ∀t ≥ 1, Given an algorithm τ A with observed labels, we can therefore replace it with τÂ which involves inferring the labels y R (σ, ·), setting them equal toŷ t (·), for all t ≥ 1.
With τÂ, we can construct labels from data, and that for the hypothesis class of interest the weak learnability condition is satisfied. The last step to show the algorithm works, in the case where the set of possible p has finite support, is that the output of the algorithm will indeed converge to the rational reply, as dictated by the labels, provided the weights are specified correctly.

Proof. See Appendix B.
The construction ofŷ t depends on the specifics of a problem, especially what data D t available in period t contains. In many interesting economic models, the algorithm forŷ t needs the knowledge of Θ rather than simply the support of π, and D t can contain at least the ordinal information about the performance of the decision recommended by τÂ.
Let us consider the insurance model illustrated in Section 3.3.1. The critical value is (5.10). Instead, suppose that the receiver can observe the average performance difference of two actions: in the past. 11 That is, Given a probability distribution over y R (σ, p),ŷ t (p) satisfies LDP: ∃λ > 0 such that We know that the large deviation rate function over a binominal distribution is uniformly bounded from below (Dembo and Zeitouni (1998)). Thus, we can choose λ > 0 uniformly over all probability distribution over y R (σ, p). The ordinal information (5.13) about the average quality is necessary. Without access to (5.13), the algorithm cannot estimate y(σ, p), which is critical for emulating the rational behavior. The information contained in (5.13) is coarse, because the algorithm does not take any cardinal information about the parameters of the underlying game. Without the cardinal information, the receiver cannot implement the equilibrium strategy of the baseline game, which is a single threshold rule. Because the algorithm does not rely on parameter values of the underlying game, the algorithm is robust against specific details of the game, if the algorithm can function as intended by the decision maker.

Discussion.
5.3.1. Accommodating Multiple Actions. We use the Adaptive Boosting algorithm, as introduced by Schapire and Freund (2012), to specify the α k weights and the updates if |A| = 2. The original Adaptive Boosting algorithm only applies to the case of |A| = 2. To handle the case of |A| > 2, we appeal to a generalization introduced by Mukherjee and Schapire (2013).
The |A| > 2 algorithm works for the |A| = 2 case, with one minor drawback, which is that the learnability constant must be computed in advance. While our work shows an algorithm exists, the computation of the learnability constant is more indirect and hence explicitly finding a parameter that works is more difficult. The arguments for these proofs follow from results in the machine learning literature (see Schapire and Freund (2012)), which we can apply to show that this algorithm can yield a response for which the misclassification probability vanishes.
The proof of Proposition 5.10 is stated for the general case. The proof reveals that the rate at which the probability of misclassfication vanishes is determined entirely by the number of sender actions in the support of σ. Thus, the algorithm is efficient in that it maintains an exponential rate of convergence (Shalev-Shwartz and Ben-David (2014)).

5.3.2.
On the Necessity of Expanding H. So far, our analysis has assumed that the set of initial classifiers H contains the set of single-threshold classifiers, we have shown that the rational reply can be guaranteed by an algorithm. We now show that this result requires the ability to construct algorithms to expand the set of possible decision rules, even if y R (σ, p) ∈ H, given sufficient richness in the set Π-recall that we do not necessarily assume |Θ| < ∞, so that different π with non-overlapping support may be possible; that is, if the designer seeks to provide rational replies in a variety of different environments, one cannot simply find the best fitting hypothesis within H to emulate rationality.
Indeed, it is straightforward to find conditions on Π, the set of possible distributions over Θ (all of which, we assume, have finite support), such that the optimal decision rule is of the threshold form. In fact, the algorithm designer may improve upon the rational reply given knowledge of π. To illustrate, suppose u(θ, p, a) is independent of θ, and weakly increasing (coordinatewise) in p, for each a (the latter of which would hold if, for instance, p were a menu of prices). The following simple result shows that in this case, at least (increasing) single threshold classifiers should be included: Proposition 5.11. Suppose u(θ, p, 1) − u(θ, p, 0) is constant in θ and weakly concave in p. Suppose further that u(θ, p * , 1) > u(θ, p * , 0). Then there exists a single threshold classifier which the algorithm could commit to using which ensures the strategic player chooses p * with probability 1.
The proof follows immediately from an observation that the set of p at which the consumer chooses a = 1 is convex under the conditions of the proposition. 12 In order for the algorithm designer to improve upon a degenerate prescription to always choose a = 0, Proposition 5.11 suggests including at least single threshold classifiers which are increasing. Against the highlighted π, such prescriptions would give the receiver even higher commitment power than the rational benchmark. In order to maximize payoff against richer and richer Π, more and more classifiers should therefore be included to H.
This raises the question of whether adding in these classifiers goes "too far." Namely, in seeking to maximize payoff against a rich set of possible π, does this risk doing worse against others? In fact, it may be that the receiver does worse than the rational benchmark.
Proposition 5.12. Suppose thatΓ is the set of all single threshold classifiers, and suppose all π ∈ Π has binary support. For any {θ L , θ H } supporting π, suppose the following is satisfied: • The sender's optimal p − a pair when θ = θ L is (p * L , 1) • The sender's optimal p − a pair when Then a policy arbitrarily close to the sender's optimal p − a pair is implementable, even if this differs from the rational outcome under σ R .
12 See also Gilboa and Samet (1989) for a similar observation on how the use of restricted decision rules can be advantageous.
A setting where this sender-optimal action strategy differs from the rational outcome was first studied, to the best of our knowledge, in Rubinstein (1993). His setting satisfies the conditions of the proposition. Our proof adapts his arguments to the current setting (i.e., incorporating the statistical aspect of our exercise and beyond the application he considered, described above), and highlights the importance of counterveiling incentivse in driving the result. The reason the sender can profitably deviate in the previous proof is because the new σ induces a non-monotone response from the receiver optimally, even though this is not prescribed by σ R . In contrast, decision rules with single-threshold classifiers must be monotone. 13 In other words, we show that the sender can construct a strategy which ensures that the receiver's utility as a function of p violates single-crossing. Now, if the sender were using the particular σ * from the previous proof, then the rational response can be achieved via a double-threshold classifier, since there are only three optimal sender choices. But on the other hand, if the receiver were restricted to using single-or double-threshold classifiers, then one could find another strategy whereby the optimal response would be to use a triple-threshold classifier, via a similar scheme. As long as the number of thresholds used is finite, a similar kind of exploitation would emerge.

Accommodating Richer Principal Action Spaces.
While τÂ is designed to be robust against parametric details of the underlying problems, the algorithm is still vulnerable to strategic manipulation by the rational sender. The proof of Proposition 5.10 reveals that the rate of convergence is decreasing as the number of sender actions in the support of σ increases. The sender can randomize over infinitely many messages to slow down the convergence rate arbitrarily. That said, such manipulation would be short lived, and therefore have limited gains. Nevertheless, in order to ensure that there are only a finite number of observations that the algorithm may observe, it is necessary to augment the observation space so that the distribution facing the receiver can be treated as discrete. This section discusses how this modification can be done.

Approach One: Discretization
We describe how to revise τÂ accordingly to discretize the observation space. Instead of processing individual actions, we let τÂ process a group of actions at a time, treating "close" actions as the same group. In principle, we want to partition P into a set of half-open rectangles intervals with size λ. More precisely, given some arbitrary λ, we can partition each dimension of a rectangle containing P into the collection of half open intervals of size λ > 0 with a possible exception of the last interval: where K λ j is the number of elements in the partition and j ∈ {1, . . . , n} is a partiular dimension.
For each element in the partition, the algorithm receives an ordinal information about the average outcome from the decision, if it contains a sender action in the support of σ: 13 Even though y R (σ R , p) is an element ofΓ, y R (σ * , p) is not an element ofΓ. Since σ * is the choice variable of the sender, the sender generates misspecification endogenously.
where p in the support of σ and P k is the product of partition elements. Let τ λ A be the algorithm obtained by replacingŷ t (p) in τÂ byŷ λ t (k). Note that as λ → 0, the size of the individual elements in the partition shrinks and τ λ A converges to τÂ for a fixed σ. Compared to τ A and τÂ, τ λ A takes only coarse information for two important reasons. First, the algorithm cannot differentiate two ps which are very close. This features makes the algorithm robust against strategic manipulation of the sender to slow down the speed of learning. Second, the algorithm cannot detect the precise consequence of its decision, but only the ordinal information of the past decision, aggregated over time. The second feature allows the algorithm to operate with very little information about the details of the parameters of the underlying game.

Approach Two: Smoothing
Discretizing the action space as above is one way of ensuring that there are only a finite number of sender actions to worry about in the long run, and given a sufficiently fine discretization, any distinct p is distinguished by the algorithm. However, in principle, close sender actions may still be quite far in terms of payoffs, and only be distinguished in the long run. That is, there is no guarnatee that for a fixed horizon, that the algorithm is not grouping too many p possibilities. The issue is that the discretization approach uses no information about the receiver's payoff function. Our other alternative describes more explicitly how close to rationality the receiver can achive, given some fixed discretization scheme.
The idea is the following: We add a small amount of noise to each observed p, with the amount of noise tending to 0 as the sample size grows large. Doing so allows us to show that the receiver perceives the sender's strategy to have the property that E θ [u(a, θ, p(a) : p] is uniformly equicontinuous (as functions of p). As a result, if the receiver only seeks to use a strategy that is ε−optimal against σ, uniform equicontinuity implies that their best reply can essentially be collapsed within intervals.
It will additionally be important that the algorithm does not seek to make predictions at p values where the corresponding density would be estimated to be small. Hence a second step will be to determine whether a p realization occur in a region with sufficiently large probability, where the "sufficient" amount will also tend to 0 as the amount of data grows large.
Formally, suppose the algorithm observes data ((p 1 , y), . . . , (p n , y)). Let z η,i be an independent random vector in the unit ball around 0 distributed according to the PDF: where K is a constant which ensures φ η integrates to 1. Our first augmentation is the following: • Replace the observed p 1 , . . . , p n withp 1 , . . . ,p n , wherep i = p i + z η,i , with z η,i distributed according to the above.
Second, it turns out that the above smoothing operation only works if the density is sufficiently large. Otherwise, the smoothing noise has too much power.
• For anyp = (p a ) a∈A\a 0 drawn, estimate the event thatσ η (p) < γ by fixing some δ small and determining whether menu(s) p with max a∈A\{a 0 }pa − p a < δ occurs with frequency at least (2δ) |A|−1 γ. Recommend action a 0 for any such p. As δ → 0, the condition holds if the density is at least γ. Together with the previous, we can show that if the receiver instead observes noisy sender actions, the perceived sender's strategy is sufficiently well-behaved to maintain the appropriate convergence for the algorithm.
Proposition 5.13. Suppose the sender is restricted to choosing distributions which are either discrete or continuous with bounded density. Consider an algorithm which can ensure that an ε-rational label is PAC-learnable, for any arbitrary ε > 0 given a finite number of possible sender actions. Then there exists a smoothing operation which maintains PAC-learnability of ε-rationality, for every ε > 0.
The idea of the proposition is to use the smoothing operation to show that the algorithm perceives that the sender uses a σ such that E[u(a, θ, p(a)) : p] is uniformly equicontinuous. Given that we seek ε-optimality, uniform equicontinuity allows us to essentially discretize the menu space, transforming the environment into a much simpler one.
There are two important properties of the transformation which allows us to ensure this works. The first is that, definingσ η (· : θ) to be the perceived p distribution of p i + z i , we have: D ασ η (p : θ) = P D α φ η (p −p)σ(p : θ)dp, so thatσ η inherits the smoothness properties of φ η . The second is that, on any compact subset of P , we have σ η (· : θ) → σ(· : θ) uniformly. Now, in order to obtain uniform continuity as η → 0, it will be important that we can simultaneously ensure that the sender's strategy does not involve dramatic movements in the conditional probability. For instance, suppose the sender were to use the following strategy: σ(p : G) = p(sin 1 p + 1), σ(p : B) = p(sin 1 p − π + 1), defined on an interval [0, p] such that both densities integrate to 1. Then P[θ = G : p] = 1 if p = 1 (2k+1/2)π for some k ∈ N, and 0 if p = 1 (2k+1/2)π , for some k ∈ N. As k → ∞ (so that p → 0), this oscillates infinitely often.
We handle the problem this example poses by only making non-degenerate predictions if the probability of using such sender actions is sufficiently high. That is, we "ignore" p realizations which only occur with low probability according to an estimated density. 14 Seeking to estimate the probability that all sender actions are within δ of p in order to estimate the density is just one way of doing this step; for instance, one could estimate the CDFσ η (p), and use the estimated density to determine whether the observations should be thrown away. Ultimately, however, given the compact P, we can minimize the 14 One may wonder why this trick works; for instance, we do not obtain the result when σ(p : G) = sin 1 p + 1, σ(p : B) = sin 1 p − π + 1. However, unlike the previous example, these will fail the continuity requirement on the sender's strategy space, which is needed in the proof.
probability that this is done by using sufficiently low thresholds. As a result, it has a vanishing impact on PAC-learnability, as well as the sender's expected profit.

Review of Examples
We now verify the implications of this observation on the sender behavior in our particular examples, showing that this results in the sender-preferred Stackleberg outcome is emerging. This requires us to verify the previously discussed conditions in the context of these applications.
6.1. Informed Principal. The decision problem of the agent is to identify each pair (x, q) of payment x and cost q as an acceptable constract (a = 1) or not (a = −1). Without loss of generality, we can assume that the agent uses the single threshold linear classifier induced by hyperplane We can construct τÂ by estimating Ev(θ, p, a) for each (p, a).
Lemma 6.1. Suppose that σ assigns a positive probability to (x, q) where E(q − θx : (q, x)) = 0 for x > 0. Then σ is not a best response to τÂ.
Proof. Let (x, q) be some offer such that the agent is indifferent between accepting and rejecting, so that: The principal's expected payoff is found by taking the expectation of u(θ, (x, q), a) over all realizations of x, q. By the law of iterated expectations, this occurs if and only if the principal's payoff is maximized following each realization of (x, q). We claim the principal is not indifferent between actions following any such (x, q). Indeed, letting E[θ : (x, q)] = r, indifference implies: Note that equality holds if f (y) = y. This implies that both lotteries, whether or not the principal accepts, have the same expected values. However, if f is concave, then since I > I − rx > I − L + (1 − r)x > I − L, it must be that the left hand side is strictly greater than the right hand side.
It follows that if indifference holds, the principal strictly prefers the agent accept the offer by slightly reducing x.
Following the same logic as in the previous example, we conclude that if σ is a best response to τÂ, then τÂ(D t )(q, x) = y R (σ, (x, q)) with probability 1. A best reply σ to τÂ emulates (σ R , y R (σ R , p)).
6.2. Labor Market Signaling. The firm's objective function is to forecast the productivity of the worker: v(θ, p, a) = −(θ − a) 2 If A is a real line, then where the posterior distribution over θ is calculated via Bayes rule from σ and the prior over θ. Strict concavity of v implies that y R (σ, p) is a strict best response ∀σ, p.
Without loss of generality, we consider a single threshold decision rule parameterized by (a + , a − , p 0 ): Let H be the set of all single threshold decision rules. In each round, h t solves max h∈H E θ v(θ, p, a) : p, σ if the data includes σ. We construct τ A accordingly. If σ is not observable by the algorithm, we estimate the posterior distribution of σ conditioned on each p to construct τÂ. If the agent learns y R (σ, p) eventually ∀σ, p, then the principal's choice σ R E[u(θ, p, y R (σ, p)) : σ, p] = θ p u(θ, p, y R (σ, p))σ(p : θ)π(θ).
If σ R entails separation by the high productivity worker, then the Riley outcome is the solution, that generates the largest ex ante expected surplus for the principal among all separating equilibria. In order to satisfy the incentive constraint among different types of the principal, the principal with θ = H incurs the signaling cost. If the signaling cost outweighs the benefit of separation, then σ R is the pooling equilibrium where both types of the workers takes the minimal signal. The analysis is based upon the assumption that y R (σ, p) is a strict best response ∀σ, p. As |A| = J < ∞, y R (σ, p) may not be a strict best response for some σ and p. Let us assume that A = {a 0 = 0, a 1 , . . . , a J } and a i − a i−1 = ∆ > 0 and a F = 1 + sup Θ > 0. Although y R (σ, p) may not be a strict best response for some σ and p, the set of best responses contains at most 2 elements, which differ by ∆ > 0. Abusing notation, let y R (σ, p) be the set of best responses, if the agent has multiple best responses at p. Applying the convergence result, we have ∃T such that, ∀t ≥ T , P ∃y ∈ y R (σ, p), y = τÂ(D t )(p) < e −ρt .
For a sufficiently small ∆ > 0, σ R is either a strategy close to the Riley outcome, or the pooling equilibrium where both types of the principals choose the smallest value of p.
6.2.1. Monopoly Market. In the model of Rubinstein (1993) illustrated in Section 3.3.3, suppose that type 1 buyer is an algorithmic player, while type 2 buyer is a rational player. To simplify the model, we assume that type 2 buyer's decision is y R (σ, p) ∀σ. Assume that type 1 buyer uses τÂ. y R (σ, p) is not a strict best response, if ∀i (6.14) so that the agent is indifferent between accepting and rejecting p. Thus, τÂ is not PAC learnable. Still, the best response of the monopolistic seller against τÂ is σ R . The critical step is to show that a rational seller would not use any σ which assigns positive probability p > v L satisfying (6.14).
Lemma 6.2. Fix σ which assigns p > v L with positive probability, satisfying Then, the ex ante expected profit of the principal against τÂ from σ is strictly smaller than from σ ′ : Proof. It suffices to show that if p > v L and E(v : p) − p ≥ 0, then the expected profit from p is strictly less than π L v L . We write the proof in Rubinstein (1993) for the later reference. For any price p satisfying P(H : p)v H + P(L : p)v L ≥ p, the revenue cannot exceed P(H : p)v H + P(L : p)v L but the cost is P(H : p)(1 − r)c 2 + P(H : p)rc 1 . Thus, the seller's expected profit is at most Because of the lemon's problem, Integrating over p, we conclude that the ex ante profit is strictly less than π L v L .
Lemma 6.2 implies that again τÂ, the principal will not use σ which assigns a positive probability to p so that both 1 and -1 are best responses. Thus, if σ is a best response to τÂ, then y R (σ, p) is a strict best response ∀p > v L . We can apply Proposition 5.3. Proposition 6.3. In the example of Rubinstein (1993), if σ is a best response to τÂ, then (σ, τÂ) is a Nash equilibrium of the algorithm game, which emulates (σ R , y R (σ R , p)).

Conclusion
This paper has applied the framework of PAC learnability to describe the performance of algorithms in a strategic setting. We show that as long as some initial set of classifiers satisfy weak learnability, an algorithm can be specified which ensures the receiver takes an optimal response to the sender's action. As noted by Rubinstein (1993), this need not be the case when the receiver's behavior follows from the optimally chosen single-threshold classifier given the sender's strategy. However, being able to combine classifiers is enough to overcome this limitation, even if it only remains possible to find the "best" classifier from within this limited class.
Our general analysis has focused on settings featuring strategic inference-based on the observed action of the strategic sender, a rational receiver would update beliefs about an underlying state (thus influencing the optimal response). This adds a complicating feature that the ex-post optimal action is only observed with noise. Yet because this noise diminishes with the size of the sample, we are still able to show this presents no added difficulty (thanks to results from large deviations theory). We briefly mention that if the amount of label noise were bounded away from zero, then our approach need not be successful (a well-known issue with Boosting algorithms). While a technical contribution, it is one that is necessary due to the uncertainty inherent in our applications of interest.
We have sought to articulate the following tradeoff in the design of statistical algorithms to mimic rationality: on the one hand, simply fitting a single-threshold classifier to data will fall short of rational play and be exploited. On the other hand, it may not be clear why this is the end of the story. By adding the ability to fit classifiers repeatedly and combining them in particular ways, we show how the rational benchmark can be restored. Here, we have taken as a black box the ability to fit these classifiers. But given this, our algorithm specifies exactly how to put these fitted classifiers together in order to construct one which can mimic rationality arbitrarily well.
We have focused on a simple yet general setting where the comparison to the rational benchmark is most transparent. Still, we believe that many concerns highlighted by the machine learning literature regarding the design of algorithms can speak to issues of interest to economic theorists. Given how productive the machine learning literature has been in terms of designing algorithms for the purposes of classification, we hope that our work will inspire further analysis of how these algorithms behave in strategic settings.

Appendix A. Weak Learnability Proofs
The proof of 5.6 uses the following Lemma: Lemma A.1. Let H be an arbitrary hypothesis class with the property that for every h ∈ H and every permutation π : A → A, the composition π • h is contained in H. Then this hypothesis class can do at least as well as a uniform random guesser.
Proof. Let Π be the set of all possible permutations on A, noting that |Π| = k!. Fix an arbitrary classifier h ∈ H, and define h π = π • h. Let cj,y be the cost of assigning label y to price pj. Define π∈Π c j,h π (p j ) = cj.
In particular, note that this is invariant to the true label of j. As a result, the random guesser's expected payoff on observation j is is cj/k!. To see this, note that h(pj) gives some fixed guess regarding the label of price pj. Then randomizing over permutations is equivalent to randomizing over labels, as there are an equal number of permutations which flip the label according to h(pj ) and every other label.
We therefore obtain the following matrix equation, for an arbitrary ρ ∈ (0, ∞), where the number of columns is k! and the number of rows is the number of possible prices.
Also note that: (1/ρ, · · · , 1/ρ) · So as long as ρ > 0, by the theorem of the alternative, we therefore cannot have that a vector x exists with: Let D(p) be an arbitrary distribution. Since p∈P D(p) = 1, this implies we can find some π such that: Taking ρ → ∞ and rearranging gives: Ep∼D[c j,h π (p j ) ] ≤ Ej∼D cj k! Recalling again that the right hand side of this inequality is the payoff of the random guesser, we have shown that for every possible distribution over prices, we can find some permutation which delivers a cost bounded above by the random guesser. This proves the Lemma.
Proof of Proposition 5.6. Let H be the set of hyperplane classifiers. We prove this by contradiction. If there were no universal lower bound on the error, then we would have, for all ρ, a distribution Dρ and cost c ρ j,y (without loss normalized to be on the unit sphere themselves) with the property that: where U ρ c is the payoff of the uniform random guesser who is correct with added probability ρ. Taking ρ → 0 and passing to a subsequence if necessary, compactness of the unit sphere implies that we can find a distribution D * and cost function c * such that: where we note by Lemma A.1 that at least this bound can be obtained by permutation the labels if necessary. We will arrive at a contradiction by exhibiting a single-hyerplane classifier that achieves a strictly better accuracy, given D * . Note that H contains the set of "trivial" classifiers, which give all menus the same label. Also note that the only non-trivial case to consider is when there are at least two prices in the support of D * ; if there were only one price, then simply choosing the prediction corresponding to the label on that price would yield a perfect fit. Since, by assumption, no classifier does better than random guessing, it must be the case in particular that each trivial classifier cannot exceed the randomguess bound. On the other hand, by our previous result, we know there does exist a trivial classifier which achieves at least this bound, for any D supported on P . Let P = {p1, . . . , p k } be the set of prices supporting D * , and letp ∈ P be a price in that is also an extreme point of the convex hull of P . Without loss of generality, assume thatp is nontrivial, in the sense that it does not give the same cost to all labels. Note that indeed, this is without loss, since for any such price, the choice of classification is irrelevant. 15 Note thatp is not in the convex hull of P \{p}. Therefore, by the separating hyperplane theorem, we can find an h ∈ H which (strictly) separatesp from P \{p}. Denote such a hyperplane by h * , and note that the set of hyperplane classifiers contains classifiers which assign any two labels (possibly the same label) to prices depending on which side of h * they lie on.
Also note that, again by our previous result, a trivial classifier supported on P \{p} can achieve the random guess guaranatee if p is distributed according to the conditional distribution on this set. In other words, our prior lemma implies that there exists y * ∈ A such that: On the other hand, a classifier which separates pj from the other prices can fit pj perfectly. Thus we must have So consider the hyperplane classifier which predictsỹ forp, and y * for p ∈ P \{p}, i.e., depending on which side of h * they are on (acknowledging that this may be a trivial classifier). Denote the resulting classifier by h. For this single-hyperplane classifier, we have B.1.1. The |A| = 2 case. We replicate the proof in Schapire and Freund (2012) for reference. Define Following the same recursive process described in Schapire and Freund (2012), we have Following Schapire and Freund (2012), we can show that P Ht(p) = y(σ, p) = E p d1(p)1(Ht(p) = y(σ, p)) ≤ E p d1(p) exp(−y(σ, p)Ft(p)), and P(Ht(p) = y(σ, p)) = E t k=1 Z k .
The rest of the proof follows from Schapire and Freund (2012), which we copy here for later reference.
Recall that the maximum number of the elements in the support of σ is N . Thus, where the right hand side converges to 0 at the exponential rate uniformly over p.
B.2. The |A| > 2 case. The specification of the algorithm can be found in Mukherjee and Schapire (2013). The proof provided below fills in some details to show that convergence holds in a self-contained way. First, initialize F 0 y (xi) = 0. • From previous stage, take F t y . • At stage t, find the h ∈ H solving: The final prediction is Ht(xi) = arg maxỹ T t=1 1[ht(xi) =ỹ]. The weak learnability condition says that the hypothesis class can outperform a random guesser that does better than some γ, where we allow for a potentially asymmetric cost of making different errors.
We now show convergence to the rational rule: Step 1: Bounding The Mistakes: This step is as previous. We have Indeed, the exponential is positive, so this inequality holds when yi is labelled correctly, and if the label is incorrect, then that means that someỹi satisfies F t y i (xi) > F t y i (xi). Since all exponential terms are positive, and furthermore the exponent is positive if xi is labelled incorrectly, meaning the right hand side is greater than 1 if mislabeled.
Step 2: Recursive Formulation of the Loss We now show that the right hand side goes to 0 at an exponential rate. We define the loss function to be: Lt(xi).
We first expressLt+1 as a function ofLt. Note that F t+1 y (xi) = F t y (xi) for allỹ = ht(xi), and F t+1 y (xi) = F t y (xi) + 1 forỹ = ht(xi). The loss from a given xi changes depending on whether or not it is correctly classified. For any observation that is classified correctly at the t + 1th stage, we multiply that observation's loss by a factor of e −η . On the other hand, for any observation that is classified incorrectly asỹ, we add the following: Note that if we subtractLt from both sides, and substitute in for Lt(xi) above, we obtain: Step 3: Weak Learnability By the above, ht+1 is chosen to solve: In fact, using the previous step, we see that this can equivalently be expressed asLt+1 −Lt. On the other hand, someone who is random guessing, but is correct with extra probability γ, will be correct with probability 1−γ k +γ, and guess an incorrect labelỹ with probability 1−γ k . Furthermore, the hypothesis class ensures a weakly lower error (as measured by this cost) than the random guessing. Hence this expression is bounded above by: 1 m ( 1 − γ k + γ)(e −η − 1) + 1 − γ k (e η − 1) L t.
Note that the right hand side is independent of σ, which is the rate function of the uniform distribution over Θ. Thus, we can choose ρ(ǫ) ≤ ρ(ǫ, σ) uniformly over σ, which is strictly increasing with respect to ǫ > 0. We choose T (ǫ) independently of σ as well.
Following the same logic as in the proof of Proposition 5.10, we can show that ∃γ(G) > 0 such that under τÂ. Similarly, we defineF a(p) = t s=1α s1(hs(p) = a).

Recall that
Following the same logic as in the proof of Proposition 5.10, we know that if τÂ(Dt)(p) = y R (p), Conditioned on event L,ŷ t(p) = y R (σ, p) ∀t ≥ T (ǫ).
Suppose the algorithm designer prescribes that the receiver choose a = 1 at any menu p such that λ · p ≤ ω and a = 0 otherwise. Note that having the receiver choose a = 1 therefore requires choosing p where the sender would rather the receiver choose action a = 0, by definition of K. Therefore, the strategic player cannot do any better than choosing σ(p | θ) which is a point mass at p * .
Consider the following randomized pricing rule σ * of the sender: in state H,pH(ǫH ) is chosen with probability 1. In state L, pL(ǫL) is chosen with probability 1 − ǫ andp with probability ǫ. Under this strategy, the optimal response followingp is 0, and this does not vanish as all other parameters tend to 0. However, the ex-post optimal decisions are 1 for bothpL(ǫL) andpH (ǫH). Nevertheless, (C.19) implies first, the decisionmaker prefers to choose a = 1 if and only ifpL(ǫL) than choose a = 1 if and only ifpH(ǫH ); and second, that the loss from choosing a = 1 followingp is larger than the loss from choosing a = 0 atpL(ǫL). Putting this together, and taking ǫ, ǫL, ǫH → 0 shows this policy approximates the sender's optimum, as desired.
The case of v(θL, p * L , a1) > v(θL, p * L , a0) is even more straightforward, since in this case the gain from choosing a1 is non-vanishing, meaning that we can set εL = 0.
The verification that the optimal rule converges to this threshold when emerging from data is straightforward; any recursive learning algorithm generates {φt} which converges to φ ∈ vL − ǫL, v H +v L 2 to emulate the best response of type 1 buyer against σ. Thus, the long run average payoff against such algorithm should be bounded from below by U * p − ǫ.
Appendix D. Proofs for Section 5.3.3 D.1. Proof of Proposition 5.13. The proof of the theorem proceeds in the following steps: • Step 1: Show that the expected value conditional on price, in the image of the sender's possible strategies after applying the augmentation, is uniformly equicontinuous. • Step 2: Show that the same label is applied to E[v θ | p + zi,η, σ, φη] as would be applied to E[v θ | p, σ], with high probability. • Step 3: Verify that the change in recommendation due to discarding "low density prices" occurs with vanishing probability.
Integrating over p, we conclude that the ex ante profit is strictly less than πLvL.