Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
Rendered from LaTeX for readability, not typeset faithfully. Citation keys are highlighted; maths is left as source; figures, tables and equation environments are summarised rather than reproduced; unrecognised commands are greyed out so nothing is silently dropped. Email addresses are removed.
center[center omitted — 127 chars of source]
center[center omitted — 158 chars of source]
abstract{
We propose a new method for studying environments with unobserved individual heterogeneity.
Based on model-implied pairwise inequalities, the method classifies individuals in the sample into groups defined by discrete unobserved heterogeneity with unknown support. We establish conditions under which the groups are identified and consistently estimated through our method. We show that the method performs well in finite samples through Monte Carlo simulation.
We then apply the method to estimate a model of lowest-price procurement auctions with unobserved bidder heterogeneity, using data from the California highway procurement market.}
{ \ }
{ Key words: Unobserved Individual Heterogeneity, Discrete Unobserved Heterogeneity, Pairwise Comparisons, Nonparametric Classification, Consistency}
{ JEL Classification: C12, C21, C31}
bibunit[econometrica]
\@startsection{section}{1}
\z@{0.7\linespacing}{.7\linespacing}{Introduction}
The empirical analysis of many economic settings requires accounting for unobserved individual heterogeneity (UIH) which reflects agent-specific factors that influence agents' decisions but are not recorded in the data. Failing to account for UIH generally leads to biased estimates and affects the validity of counterfactual prediction.
In this paper, we consider a generic economic model where UIH induces a group structure among agents according to their types. We provide conditions for identification of the group structure, and propose a method to recover the group structure from data.
Our main idea is based on the insight that UIH often implies pairwise inequality restrictions on endogenous observable quantities. For instance, in multi-attribute auctions, bidders with higher (unobserved) quality levels have a greater chance of winning the auction, controlling for the bid and the set of competitors. In a labor market setting, agents with higher (unobserved) productivity receive higher wages than less productive ones. In Section 2.2 we provide further examples of economic applications in which pairwise inequality restrictions arise naturally from the behavior of agents in equilibrium.
We develop a statistical method to recover the group structure (that is, to classify individuals into groups defined by UIH) using a pairwise comparison approach. Our method treats UIH as individual-specific discrete parameters which may affect the distribution of other observed or unobserved variables. We assume that the support of UIH is a finite, ordered set that is not known to the econometrician. Such flexibility is important in structural models where individuals interact strategically and the UIH of all agents jointly affects the equilibrium outcome.
One may attempt to order individuals on a pair-by-pair basis using pairwise inequality tests. However, it may not produce an ordering that is transitive in finite samples. Our method recovers the whole group structure by sequentially sub-dividing the set of agents on the basis of the $p$-values of tests of pairwise inequality restrictions. The method recovers the group structure for each assumed number of groups, and then selects the number of groups (and the associated group structure) using a penalization scheme. We show that our estimator of the group structure is consistent under mild regularity conditions and performs well in small samples.
In many settings, classifying individuals into groups defined by UIH offers key economic insights. For example, our method can be used to identify colluding bidders in auctions, and firms' cost asymmetries or product quality differences. In addition, recovering the group structure also often serves as the first step for estimating structural models with strategic interactions, such as dynamic industry models or auctions with asymmetric bidders.\footnote{Estimation of discrete unobserved individual heterogeneity does not affect subsequent estimation of other structural parameters in terms of pointwise asymptotics. However, establishing uniform asymptotics remains an open question. This problem is analogous to that of post-model-selection inference. For discussion on the issues, see Potcher1991, LeebPotcher2005, and AndrewsGuggenberger2009 and the references therein. Uniform asymptotics in our setup is complex because of the need to consider every possible direction of local perturbation from the actual group structure in data-generating process. A full theoretical investigation of the issue in our context merits a separate paper.}
This approach offers a feasible way to identify and estimate games with UIH. Specifically, a traditional approach in a setting with UIH would be to treat UIH as “fixed effects" and estimate them jointly with other structural parameters. This approach poses practical challenges in a setting with strategic interdependence among agents, especially when equilibrium outcomes admit no closed-form expressions. First, it is generally not obvious what variation in the data may identify model components including the fixed effects in such settings. One of the contributions of our paper is to point out the variation which identifies the group structure associated with “fixed effects.”
Further, we propose to separate the recovery of the group structure from the estimation of other structural parameters. Recovering the group membership of every agent facilitates, and is often needed for, identifying the remaining structural elements in models with strategic interactions. A classical example is English auctions among bidders with unobserved types (in the sense that bidders' private values are drawn independently from the distributions “labeled” by bidder types) and where the data only report the transaction price and the identity of the winner. AtheyHaile2007 show that the distributions of private values cannot be identified in this model if the type of the auction winner is unknown. We provide details and additional examples in the supplemental note to this paper.
Finally, our approach offers a way to estimate games with UIH with low computational cost, compared with the alternative approach of estimating the fixed effects jointly with other structural parameters. For example, consider an environment with a large number of players where many independent games (each containing only a small subset of players) are observed in the data. The numerical optimization (such as simulated GMM or MLE) requires evaluating the objective function which involves computing equilibrium for each value of the fixed effects and other structural parameters. This can be computationally prohibitive in practice. In contrast, our method requires the game to be solved only for the estimated configuration of the agents’ group memberships rather than for every possible configuration as is required under the joint estimation.\footnote{KrasnokutskayaSongTang2020JPE used this classification method as a first step in the structural analysis of an online service market for computer coding.}
Our method is advantageous especially in settings where the number of agents is moderately large but each market (observation) in the data involves only a small subset of participants. For example, the total number of participants may be several hundreds but each market may contain only several participants. In this case, despite the large number of markets observed, the researcher may have only a small number of markets which contain the same set of participants. We call this issue the problem of the sparsely common set of agents. In such settings, the researcher cannot build inference on the conditional moments given the full set of participating agents in a market, as typically done in the structural empirical literature, because we do not have many such observations. Hence the researcher needs to “aggregate” the markets or the agents in order to conduct reliable inference with sufficiently many observations. Pairwise restrictions are often testable with accuracy since the number of markets where a given pair of agents is present tends to be large even if the number of markets with the same set of participants is small. Thus, pairwise restrictions and the classification procedure offer a natural way to aggregate agents into groups which permits estimation of other primitives.
We investigate the finite-sample performance of our classification method in Monte Carlo simulation. The data-generating process (DGP) is a lowest-price procurement auction among asymmetric bidders whose independent private values are drawn from distributions with different means.
We report the outcome of classification for DGPs with various numbers of bidders and group structures. Our classification method works well. Its performance is better when the number of bidders and groups are smaller relative to the number of observed markets/games, and when the differences between groups are larger. We also find that the impact of classification errors on subsequent estimation of other structural parameters in the game is non-substantial.
We analyze the California highway procurement market by applying our classification method to a model of asymmetric lowest-price procurement auction.
Existing empirical studies of auction markets typically emphasized asymmetry in bidders' private values associated with their observable characteristics.\footnote{For example, AtheyLevinSeira2011, RobertsSweeting2013 and AradillasGandhiQuindt2013 accounted for the bidder heterogeneity associated with size in the timber market (`mills' vs `loggers'); KrasnokutskayaSeim2011, Jofre-BonetPesendorfer2003 and GentryKomarovaShiraldi2016 incorporated bidder participation differences in highway procurement market (`regular' vs `fringe' bidders); ConleyDecarolis2016, Asker2010 and Pesendorfer2000 allowed for bidder heterogeneity in collusive behaviors.}
In comparison, we allow the bidders' private values to be drawn from heterogeneous distributions with different means. To account for other sources of cost heterogeneity, we control for bidders' distance to the project site. We also accommodate possible endogeneity in the competitive structure. We use the classification method to recover the unknown group structure (i.e., partition bidders into groups with different mean costs). Then, using this estimated group structure, we estimate group-specific cost distributions using GMM.
Our estimates indicate that the bidders in the data come from several unobserved groups with substantial differences in mean costs. We also find that ignoring such unobserved bidder heterogeneity would lead to biased estimates of how bidders' costs depend on various factors.
Related Literature. One of the popular methods of accounting for UIH in structural modeling is to adopt finite mixtures. (See Hu2008, HuSchennach2008, KasaharaShimotsu2009, HuShum2012, HuShiu2013, HuMcAdamsShum2013, and HenryKitamuraSalanie2014. See also See KasaharaShimotsu2014 and KasaharaShimotsu2015 for estimating and testing for the number of mixture components in finite mixture models.) The finite mixture modeling assumes that the UIH is a random variable drawn from some unknown distribution. The goal is to identify this distribution and estimate it from data. It does not require each individual to appear in many independent games. In contrast, our approach aims to \textit{classify individual agents in the sample into disjoint groups defined by their realized unobserved types}, using their participation outcomes in many games. Thus the two approaches are fundamentally different both in their aims and their data requirements. While general identification results have been developed in this literature of finite mixture models (see, e.g., HuSchennach2008, BonhommeJochmansRobin2016), implementation of the finite-mixture method is impractical in our set-up due to the issue of sparse commonality, and technical issues associated with high dimensionality.\footnote{When each market is drawn from a finite mixture distribution, and there are $n$ agents with each having a type from $S$ values, the number of the mixture components becomes $S^n$ which can be very large in pratice, even when $n$ is a moderate number such as five or ten. In addition, to construct a likelihood or moment condition, one would need to solve for a different market equilibrium for each component.}
The classification algorithm we propose is related to the clustering method in statistics. (See, e.g., Chapter 14 of HastieTibshiraniFriedman2009.) The main difference is that the clustering methods aim to group individuals based on the similarity of their observed attributes, whereas in our setting, a researcher's objective is to group individuals according to testable implications of their \textit{unobserved attributes}. To accomplish this, we exploit the relationship between endogenous outcomes and the unobserved types of individuals implied by an economic model. Our method also requires a data structure different from clustering methods. The literature of clustering methods mostly considers a set-up in which each cross-sectional unit is observed once, whereas our method uses many observations per individual in the sample.
Also related to our approach is the literature of panel models with group-level heterogeneity. For example, Sun2005 introduced a linear panel model where parameters take values in a finite set according to a logistic probability, and offered methods of estimating the group structure. Song2005 considered a panel model with finite-valued nonstochastic parameters and produced an algorithm to recover the unobserved group structure in large panel models. LinNg2012 provided a method of estimating a panel model using threshold variables when the group membership is unknown. SuShiPhillips2016 developed a new Lasso method to recover the unknown group-specific parameters. BonhommeManresa2014 proposed a k-means clustering algorithm to recover the group structure in a linear panel model. These papers often focus on models which admit a reduced form for the dependent variable in which its functional relation to UIH is made explicit. In contrast, our method targets a set-up where the dependence of the outcome variables on the UIH arises only implicitly through equilibrium contraints in games, and the group structure of UIH is identified only through pairwise inequality restrictions. Thus, the approaches developed in the panel literature are not applicable in settings our proposal focuses on.
\textbf{Roadmap.} This paper is organized as follows. Section 2 introduces the basic environment and defines pairwise inequality restrictions. This section also provides several examples from various contexts to motivate our classification method.
Section 3 establishes identification of the unobserved group structure using pairwise inequality restrictions. Section 4 proposes a consistent estimator of the group structure. Section 5 provides results from Monte Carlo simulation. Section 6 presents the empirical application. Section 7 concludes. Section 8 contains the proof of some results in the paper. Further examples and mathematical proofs are provided in the supplemental note of this paper. The note also contains further simulation results and details in our empirical application.
\@startsection{section}{1}
\z@{0.7\linespacing}{.7\linespacing}{The Model and Examples}
\@startsection{subsection}{2}
\z@{.4\linespacing}{.6\linespacing}{\normalfont}{Pairwise Inequalities in Game Models}
We consider a setting where the econometrician observes $L$ games, and in each game, a set of agents interact with each other. Each agent $i$ is associated with a non-stochastic type, $q_i$, which is not observed by the researcher. We assume that the type is finite-valued so that $q_i \in Q_0 = \{\bar{q}_{1},...,\bar{q}_{K_{0}}\}$, with $\bar{q}_{1}<\cdots <\bar{q}_{K_{0}}$. This induces an \textit{(ordered) partition} $(N_{1},N_{2},...,N_{K_{0}})$ of the set $N$ of agents such that for each $k=1,2,...,K_0$, $N_k$ consists of agents with higher type than those in $N_{k-1}$. The group structure is characterized by a function $\tau: N \rightarrow \{1,...,K_{0}\}$ that links the identity of a player to his unobserved type so that $q_{i}=\bar{q}_{\tau(i)}$ and for each $ k=1,...,K_{0}$, \[N_{k}=\left\{ i\in N :\tau(i)=k\right\}.\] The group structure defined by $\tau$ is represented as an ordered collection of sets $N_k$:
\begin{eqnarray}
T = (N_1,N_2,...,N_{K_0}).
\end{eqnarray}
The data available to the researcher contain for every observation $\ell = 1,...,L$: a vector of observable characteristics for all the agents involved, $\{X_{j,\ell}\}_{j\in S_\ell}$, as well as at least one but possibly multiple vectors of outcome variables, $Y_\ell=\{Y_{j,\ell}\}_{j \in S_\ell}$, where $S_\ell$ is the set of players involved in the $\ell$-th observation (e.g., a game or a market). Our main focus is on recovering the ordered partition $(N_{1},N_{2},...,N_{K_{0}})$ of the agents from data.
The main insight of our paper begins with the observation that in many structural models, the ordering among $q_i$'s (or equivalently $\tau(i)$'s) coincides with the ordering between indexes that can be estimated consistently even in the presence of sparse commonality of agents. Specifically, we use pairwise indexes $\delta_{ij}$ and $\delta_{ij}^0$ that satisfy the following relations:\footnote{For the sake of concreteness, our exposition in the paper focuses on this form of indexes. Our procedures rely on the indexes only through the availability of consistent tests of pairwise inequality restrictions: $\delta_{ij} >0$ and $\delta_{ij}^0 = 0$. As long as such consistent tests are available, one can use our method for other forms of pairwise indexes.}
\begin{eqnarray}
\delta_{ij} &>& 0 \textnormal{ if and only if } \tau (i)>\tau (j)
; \\
\delta_{ij}^{0} &=& 0 \textnormal{ if and only if } \tau (i)=\tau (j),
\nonumber
\end{eqnarray}
where the indexes $\delta_{ij}$ and $\delta_{ij}^0$ can be consistently estimated using the sample. In many applications, we can take the indexes as (a variant of) the following form:
\begin{eqnarray}
\delta_{ij} &=& \int \max\{\mathbf{E}[Y_{i,\ell}|X_{i,\ell} = x] - \mathbf{E}[Y_{j,\ell}|X_{j,\ell} = x],0\}dF(x), \text{ and }\\ \notag
\delta_{ij}^0 &=& \int \left|\mathbf{E}[Y_{i,\ell}|X_{i,\ell} = x] - \mathbf{E}[Y_{j,\ell}|X_{j,\ell} = x]\right|dF(x),
\end{eqnarray}
where $F$ is a known distribution or the distribution of an observable random vector.
For example, suppose that the outcome $Y_{i,\ell}$ admits the following reduced form:
\begin{eqnarray*}
Y_{i,\ell} = g(\tau(i),X_{i,\ell},\eta_{i,\ell}),
\end{eqnarray*}
where $g$ is a function that is strictly increasing in $\tau(i)$ and $\eta_{i,\ell}$ is an unobserved component that is independent of $X_{i,\ell}$ and does not depend on $\tau(i)$. Then under regularity conditions that ensure that $\delta_{ij}$ and $\delta_{ij}^0$ are well defined, we obtain the pairwise relations ((ref)) with ((ref)). The main advantage of our approach is that we do not require an explicit characterization of the reduced form $g$. Due to this flexibility, our approach is most useful for analyzing UIH in structural models where the reduced form for outcomes arises only implicitly through equilibrium constraints. In such a setting, the sign of the indexes $\delta_{ij}$ represents the pairwise relation which says that between any two agents, one agent's type is higher than the other if and only if his outcome tends to be higher than that of the other. As we demonstrate through examples below, many structural models imply such pairwise relations through indexes $\delta_{ij}$ and $\delta_{ij}^0$.
The main goal of this paper is to develop a statistical procedure to recover the group structure $\tau$ from data. Our method relies only on the pairwise inequality restrictions in ((ref)). Thus so far as the group structure is concerned, the pairwise comparison indexes $\delta_{ij}$ and $\delta_{ij}^0$ play the role of a sufficient statistic; the recovery of the group structure does not rely on other details of the structural model.
\@startsection{subsection}{2}
\z@{.4\linespacing}{.6\linespacing}{\normalfont}{Examples }
We now provide examples of pairwise inequality restrictions which arise as equilibrium implications in a variety of commonly studied empirical contexts.
\@startsection{subsubsection}{3}
\z@{.4\linespacing}{.6\linespacing}{\normalfont}{Unobserved Quality in Multi-attribute Auctions}
Consider a simplified version of multi-attribute auctions in KrasnokutskayaSongTang2020JPE that abstracts away from observed auction and seller heterogeneity. Let $N$ denote the total set of sellers and $S_\ell$ the set of sellers who submitted bids for a project $\ell$. Each seller has a discrete unobservable quality: $q_i \in \{\bar{q}_{1},..., \bar{q}_{K_{0}}\}$, with $\bar{q}_k < \bar{q}_{k'}$ whenever $ k < k'$. Such a quality is known to buyers but not reported in data.
The buyer for project $\ell$ selects a seller among those who submitted bids or chooses an outside option to maximize his payoff. The payoff to the buyer from engaging services of seller $i\in S_\ell$ is given by
$ U_{i,\ell}=\alpha _{\ell}q_{i}+\epsilon _{i,\ell}-B_{i,\ell}$ whereas the payoff from an outside option is $U_{0,\ell}$. Here $ \alpha_\ell $ is a non-negative weight the buyer gives to the seller's quality relative to the seller's bid, whereas $ \epsilon_{i,\ell} $ reflects a buyer-seller match-specific stochastic component.
Let us suppress the auction subscript $\ell$ and define for any two sellers $i,j$,
\[
\rho_{ij}(b)=P\left\{\,i\,\mbox{wins}\,|\,B_{i,\ell}=b,\,i\in S_\ell,\,j\not\in S_\ell\right\},
\]
for all $b$ on the intersection of the supports of $B_{i}$ and $B_{j}$.
Suppose that $\alpha, S_\ell,\{B_{i,\ell}, \epsilon_{i,\ell}\}_{i\in S_{\ell}}$ are mutually independent.\footnote{This is plausible, for example, if sellers are not informed of the weights or outside option of the buyer, or the identities of other sellers in $S_\ell$.} Proposition 1 of KrasnokutskayaSongTang2020JPE showed that
\begin{equation}
\text{sign}(\rho_{ij}(b)-\rho_{ji}(b))= \text{sign}(q_{i}-q_{j}),
\end{equation}
for any $b$ in the intersection of bid supports.
On the basis of this property the comparison indexes can be constructed as follows:
$\delta_{ij} \equiv \int \max \{\rho_{ij}(b)-\rho_{ji}(b),0\}db$ and $\delta _{ij}^{0} \equiv \int \left\vert \rho_{ij}(b)-\rho_{ji}(b)\right\vert db$. Note that the comparison indexes do not depend on other details of the structural model such as specific parametric assumptions for the distribution of buyers' tastes.
\@startsection{subsubsection}{3}
\z@{.4\linespacing}{.6\linespacing}{\normalfont}{Firms' Cost Efficiency and Pricing Decisions}
Consider a population of $n$ firms or brands, each of which produces a single brand of product. The data consists of independent markets indexed by $\ell = 1,...,L$. The marginal cost for firm $ i $ on market $\ell$ is $c_{i,\ell}=\varphi(w_{i,\ell},q_{i},\eta_{i,\ell})$, where $w_{i,\ell}$ are observable cost shifters, $q_i$ a brand-specific unobserved heterogeneity that is fixed across markets, and $\eta_{i,\ell}$'s are i.i.d. idiosyncratic noises independent of $ w_{i,\ell}$ and $q_i $.
We may interpret $q_i$ as a measure of firm $ i $'s cost efficiency. Firms have complete information about each others' cost efficiencies.\footnote{This assumption is plausible in certain industries where production efficiency is mostly determined by firms' technology or equipment that is publicly observable.} Firms in the population are partitioned into groups with different levels of $q_i$: $N=\cup_k N_k$ where $i \in N_k$ if $\tau(i)=k$.
Let $\sigma_{i,\ell}(\mathbf{x}_{\ell},\,\mathbf{p}_{\ell},\Omega_\ell)$ denote firm $i$'s market shares, which is a function of product attributes ($\mathbf{x}_{\ell}=\{x_{i,\ell}\}_{i\in S_\ell}$, where $S_\ell$ denotes the set of brands in market $\ell$) and prices ($\mathbf{p}_{\ell}=\{p_{i,\ell}\}_{i\in S_\ell})$ conditional on the set of products available in market $\ell$ and other market factors denoted by $\Omega_\ell$.
The profit for firm $ i $ in market $\ell$ is: $\pi_{i,\ell}=(p_{i,\ell}-c_{i,\ell})\sigma_{i,\ell}(\mathbf{x}_{\ell},\mathbf{p}_{\ell},\Omega_\ell)M_\ell$, where $M_\ell$ is a measure of potential consumers in market $\ell$.
In any pricing equilibrium with an interior solution, the first-order condition implies
\begin{equation}
c_{i,\ell}=p_{i,\ell}+\frac{\sigma_{i,\ell}}{\partial \sigma_{i,\ell}/\partial p_{i,\ell}}.
\end{equation}
Notice that if $ \eta_{i,\ell} $ is independent of $q_i$ and $w_{i,\ell}$, and $\varphi(w_{i,\ell},q_{i},\eta_{i,\ell})$ is strictly monotone in $q_i$ then so is the right-hand side of ((ref)), which can be constructed from estimates of the demand system.
Hence, for any pair $i,j\in N$, $q_{i}\geq q_{j}$ if and only if $\mathbf{E}[z _{i,\ell}|w_{i,\ell}=w_0] \geq \mathbf{E}[z _{j,\ell}|w_{j,\ell}=w_0]$, for all $w_0$, where $z_{i,\ell}$ is defined as the quantity on the right-hand side of ((ref)). The statement is also true when both inequalities are strict.
Thus we can define a pairwise comparison index
\begin{equation}
\delta_{ij}\equiv \int \max\{\mathbf{E}[z_{i,\ell}|w_{i,\ell}=w_0] - \mathbf{E}[z _{j,\ell}|w_{j,\ell}=w_0],0\}dF(w_0),
\end{equation}
where $F$ is the distribution of $w_{i,\ell}$. In equilibrium $ \delta_{ij} > 0 $ if and only if $q _i > q_j $.
Likewise, define $\delta_{ij}^0 $ by replacing $\max\{\cdot,0\}$ in the integral in $ \delta_{ij}$ with the absolute value. These pairwise comparison indexes do not condition on specific identities of firms in a market.
\@startsection{subsubsection}{3}
\z@{.4\linespacing}{.6\linespacing}{\normalfont}{Assortative Matching in Labor Market}
Sorting of heterogeneous employees across heterogeneous firms has been studied in LentzMortensen2010, AbowdKramarzMargolis1999, and LiseMeghirRobin2011.
In a typical setting, firms are heterogeneous in the productivity from a given worker \textit{ceteris paribus}.
Workers differ in their unobservable ability $q_i$.
Under further restrictions (see EeckhoutKircher2011 and HagedornLawManovski2016), workers with higher ability would in equilibrium earn higher wages than co-workers at the same firm, holding other things equal.
This forms a basis for pairwise comparisons. Specifically, let $w_{i,f,t}=W(q_i,X_{i,t},\Omega_{f,t})$ denote the wage worker $i$ earns at time $t $ while employed by firm $f$, where $W$ is a non-stochastic function. Here $\Omega_{f,t}$ captures all the relevant firm-specific unobservable factors while $X_{i,t}$ reflects worker $i$'s observable characteristics other than $q_i$. Here we assume that $(X_{i,t},\Omega_{f,t})$ is identically distributed across $f$'s and $t$'s. Using $N_{f,t}$ to denote the set of workers employed by firm $f$ at time $t$, we define the comparison index as
\begin{eqnarray*}
\delta_{ij}=\int \max\{\mathbf{E}[w_{i,f,t}|X_{i,t} = x] - \mathbf{E}[w_{j,f,t}|X_{j,t} = x] ,0\}dF(x), \text i,j\in N_{f,t},
\end{eqnarray*}
where $F$ is the distribution of $X_{i,t}$. Then $ \delta_{ij} > 0 $ if and only if $ q_i > q_j $, under regularity conditions such as strict mononicity of $W$ in $q_i$. Similar to before, define $\delta^0_{ij}$ by replacing the max operator in $ \delta_{ij} $ with its absolute value. In this setting comparison of workers is complicated by the (unobserved) firm heterogeneity and sorting of workers across firms. Pairwise comparisons allow researchers to circumvent these issues by focusing on workers' wages earned while they are employed by the same firm.
\@startsection{subsection}{2}
\z@{.4\linespacing}{.6\linespacing}{\normalfont}{Sparsely Common Set of Agents and Pairwise Inequalities}
Our pairwise comparison method is most useful in settings where players appear in markets only sparsely. When most distinct sets of players appear only once or twice in the data, it is challenging to study the competition pattern in the market, because we cannot recover from data the conditional probability of their choices conditional on the set of competitors.
\begin{figure}[t]
\begin{center}
\caption{ The panels show sparse commonality of bidder sets in the auction data we use for the empirical application later. In both panels, the $x$-axis denotes the number of the times that a particular bidder set appears in the data and the $y$-axis represents the number of distinct bidder sets in the data. For example, $(x,y) = (2,250)$ represents that there are 250 distinct bidder sets that appear twice in the data. The upper panel shows the number of distinct bidder subsets consisting of regular bidders submitting bids in an auction. (We define a regular bidder to be one who submits at least 5 bids per year in this market.) The lower panel shows all data. As the figure shows, most bidder sets appear only once or twice. Notice that in the upper panel, there is a single bidder set that appears in the data 56 times and this is the largest occurences that we observe in the data.}
\end{center}
\end{figure}
Such a data feature is not uncommon in practice. In Figure (ref), we show the structure of the auction data used for our empirical application. The $x$-axis in each panel denotes the number of the times that a generic bidder set appears in the data, and the $y$-axis represents the number of distinct bidder sets in the data. For example, $(x,y) = (2,250)$ represents that there are 250 distinct bidder sets that appear twice in the data. The upper panel shows the number of distinct bidder subsets consisting of regular bidders submitting bids in an auction.\footnote{We define a regular bidder to be one who submits at least 5 bids per year in this market.} The lower panel shows all data. As the figure shows, most bidder sets appear only once or twice. Notice that in the upper panel, there is a single bidder set that appears in the data 56 times and this is the largest occurences that we observe in the data. Furthermore, this set consists only of two bidders, making it hard to take this set as representing the whole auction market.
To express this data feature, define for any $S \subset N$,
\begin{eqnarray*}
\mathcal{L}(S) =\{1 \le \ell \le L: S_{\ell} = S \}.
\end{eqnarray*}
Thus $\mathcal{L}(S)$ represents the set of markets where the set of participants in a market $S_\ell$ is precisely $S$.
In this paper, we refer to the setting as that of a
\textbfit{sparsely common set of agents}, if the proportion $\max_{S \subset N} |\mathcal{L}(S)| / L$ is negligible in finite samples. In other words, only a small fraction of the markets in the sample share exactly the same set of participants.
\begin{figure}[t]
\begin{center}
\caption{ The first panel shows an example of a data set where the set of participants is the same across all markets. The second and third panels show another example of data where only a small fraction of markets share the same set of participants. As illustrated here, there are only three markets where the set of participants is precisely $\{1,3,4\}$. The third panel shows that in the same data represented in the second panel, there are many more markets where both agents $1$ and $3$ (represented by white ellipses) participate. Thus a researcher can estimate population quantities that condition on the joint participation of the two agents, $1,3$, with better accuracy than quantities that condition on the whole set of participants or the triple $\{1,3,4\}$.
}
\end{center}
\end{figure}
We illustrate the advantage of using pairwise comparisons in Figure (ref). Each column in the figure symbolizes a “market" and each row an individual agent. The ellipses in each column represent agents participating in a market. The first panel shows a standard set-up where all the agents appear in all the markets. The second panel shows an example of a data set where only very few markets share exactly the same set of participants $\{1,3,4\}$. As illustrated previously using real data, this feature of data is more realistic than the first panel. In this case, the conditional choice probability given the same set of agents simultaneously participating in the market cannot be accurately estimated. However, if we focus on only subsets with two agents $\{1,3\}$, there are many more markets in which the two agents participate. If each pair of agents appear in many markets simultaneously, we may aggregate over these markets, and infer accurately the ordering between the two agents using an inequality test. Given the p-values from inequality tests across pairs of agents, it remains to recover the whole group structure of the agents from these pairwise $p$-values. We develop an algorithm that recovers the group structure from the pairwise $p$-values consistently.
\@startsection{section}{1}
\z@{0.7\linespacing}{.7\linespacing}{Identification of the Ordered Group Structure}
Let us discuss conditions for the identification of the group structure. First, let $P$ be the distribution of observed random variables that belong to a market. (We assume that $P$ is the same across the markets.) We say that agents $(i,j)$ are \textbfit{comparable} if there exist pairwise indexes $\delta_{ij}$ and $\delta_{ij}^0$ such that the indexes are identified by $P$ and ((ref)) holds. In this identification analysis, we assume that a researcher knows whether each pair of agents is comparable through some pairwise comparison index or not. The determination of such comparability can be done in practice by checking whether the data contains sufficiently many markets in which both $i$ and $j$ participate so that the pairwise indexes may be accurately estimated.
Let $\mathcal{E}$ be the collection of pairs $(i,j)$ that are comparable. We refer to comparable agents as \textbfit{adjacent}, so that the set $\mathcal{E}$ forms the set of edges in a graph on the set of agents $ N $. We call this graph (denoted by $G = (N,\mathcal{E})$) the \textbfit{comparability graph}.\footnote{In a graph (or network) $G=(N,\mathcal{E})$ the set $N$ represents the set of vertices (or nodes) and $\mathcal{E}$ consists of some pairs $ij$, with $i,j \in N$, where each pair $ij$ is called an edge (or link).
Thus, if $(i,j) \in \mathcal{E}$, $i$ and $j$ are adjacent. A \textbfit{path} is a set of vertices $\{i_1,i_2,...,i_M\}$ such that $i_1i_2,i_2i_3,...i_{M-1}i_{M} \in \mathcal{E}$.
Two vertices are called \textbfit{connected} if there is a path having $i$ and $j$ as end vertices. A graph is called \textbfit{connected} if all pairs of vertices are connected in the graph.}
We say a group structure $\tau$ is \textbfit{identified} if it is uniquely determined once the comparability graph $G$ and the vectors of pairwise indexes $ (\delta_{ij},\delta_{ij}^0)_{ij \in \mathcal{E}}$ are known. Thus when $\tau$ is identified, it is only through the identification of the comparability graph $G$ and the pairwise indexes $ (\delta_{ij},\delta_{ij}^0)_{ij \in \mathcal{E}}$, not through other specification details of the structural model.
\begin{figure}[t]
\begin{center}
\caption{ This figure illustrates an example where the group structure is not identified even when all nodes are connected. The comparability graph is $G=(N,\mathcal{E})$, where $N=\{1,2,...,5\}$ and $\mathcal{E}
=\{12,23,34,45\}$.
Pairwise comparison is feasible only between nodes linked by solid black lines (a.k.a. links).
The two different group structures in this figure are compatible with the same pairwise ordering.
Therefore we cannot identify the group structure from pairwise orderings in this case.
}
\end{center}
\end{figure}
Let us explore the identification of $\tau$ given the comparability graph $G$ and the vector of pairwise indexes.
It is easy to see that if $\mathcal{E}$ contains only a small subset of possible pairs, we may not be able to identify the group structure. The identification of the ordered group structure $\tau$ is not guaranteed even when many pairs of agents are comparable. For example, even if $G$ is a connected graph (where any two agents are connected at least indirectly), the ordered group structure $\tau$ may not be identified. This is illustrated in a counter-example in Figure (ref). Certainly, when $G$ is a complete graph, i.e., every pair of agents are adjacent in the graph $G$, the ordered group structure $\tau$ is identified.\footnote{
If all pairs of agents are comparable, we can split the set of agents into one group with the lowest type and the other group with the remaining agents. Then we split these remaining agents into one group with the lowest type within these agents and the remaining agents. By continuing this process, we can identify the whole group structure.}
Below we establish a necessary and sufficient condition for the group structure to be identified from a potentially incomplete graph $G$ and the pairwise comparison indexes. Let us introduce some definitions.
\begin{figure}[t]
\begin{center}
\caption{ This figure shows an example where the condition $N = N^*$ in Theorem 3.1 is violated. The first panel depicts the comparability graph as one connecting 6 vertices (or nodes). The second panel shows the $\tau$-collapsed graph where the two comparable nodes 2 and 3 that have the same type are collapsed into one node named 23. The last panel shows that Nodes 23, 4, and 5 (expressed as solid black nodes) are identified, because they are on a monotone path of length $K_0 - 1 = 2$. In this example, the group membership of Nodes 1 and 6 are not identified and thus the comparable graph does not lead to the identification of the group structure.}
\end{center}
\end{figure}
\begin{definition}
(i) A graph $G_{\tau}$ is the \textbfit{$\tau$-collapsed graph} of $G$ if (a) any two adjacent vertices $i$ and $j$ in $G$ with $\tau(i)=\tau(j)$ collapse to a single vertex (denoted by $(ij)$) in $G_{\tau}$, (b) any edge in $G$ joining a vertex $k$ to either $i$ or $j$ joins vertex $k$ to $(ij)$ in $G_{\tau}$ when $\tau(i) = \tau(j)$ and (c) all the remaining vertices and edges in $G_{\tau}$ consist of the remaining vertices and edges in $G$.\\
(ii) A path in $G_{\tau}$ is \textbfit{monotone} if $\tau(i)$ is monotone as $i$ runs along the path.\\
(iii) A vertex $i$ is said to be \textbfit{identified} if its type $\tau(i)$ is identified.
\end{definition}
The $\tau$-collapsed graph of $ G $ is constructed by reducing any comparable pair of agents in $ G $ who have the same type to a single “agent", and retaining edges as in the original graph of $ G $.
Certainly, a $\tau$-collapsed graph $G_{\tau}$ is uniquely determined by $\delta_{ij}^0$'s and $G$. Any pair of adjacent agents in the $\tau$-collapsed graph must have different types, and hence the types of agents on a monotone path are strictly monotone. This means that every vertex on a monotone path in $G_{\tau}$ of length $K_0-1$ is identified.\footnote{The length of a path is defined as the number of the edges in the path.} Also by similar logic, every vertex on a monotone path with end vertices $i_H$ and $i_L$ is identified if the path has length $\tau(i_H) - \tau(i_L)$ and the end vertices $i_H$ and $i_L$ are identified. Using these two facts, we can recover the set of vertices that are identified as follows.
First, let $N_{[1]} \subset N$ denote the set of vertices such that each vertex in the $\tau$-collapsed graph $G_\tau$ is on a monotone path in $G_{\tau}$ of length $K_0-1$. For $j \ge 1$ generally, let $N_{[j+1]}$ be the set of vertices each of which belongs to a monotone path, say, $P$, such that its end vertices $i_H$ and $i_L$ are from $N_{[j]}$ and $\tau(i_H) - \tau(i_L)$ is equal to the length of the monotone path $P$. Then define
\begin{eqnarray*}
N^* \equiv \bigcup_{j \ge 1} N_{[j]}.
\end{eqnarray*}
Given $G_\tau$, $N^*$ is uniquely determined as a subset of $N$. It is not hard to see that if $N = N^*$ and $K_0$ is identified, the type structure $\tau$ is identified. The following theorem shows that this condition is in fact necessary for the identification of $\tau$ as well. The proof of the theorem is given in the appendix.
\begin{theorem}
Let $G$ be a given comparability graph and $G_{\tau}$ be its $\tau$-collapsed graph. The group structure $\tau$ is identified if and only if there exists a monotone path in $G_{\tau}$ whose length is equal to $K_0 - 1$ and $N = N^*$.
\end{theorem}
No monotone path in $G_{\tau}$ can have length greater than $K_0-1$. Note that there exists a monotone path in $G_{\tau}$ whose length is equal to $K_0 - 1$ if and only if $K_0$ is identified.\footnote{If there exists a monotone path in $G_\tau$ whose length is equal to $K_0 - 1$, then $K_0$ is identified, because through the comparability indexes, $\delta_{ij}$ and $\delta_{ij}^0$, we can identfy a longest monotone path and the length of this path should be $K_0 - 1$.} The conditions in the theorem are obviously satisfied if $G$ contains a monotone path that is monotone and covers all the vertices. The latter condition is trivially satisfied when $G$ is a complete graph. Figure (ref) gives a counterexample where the condition that there exists a monotone path in $G_{\tau}$ whose length is equal to $K_0 - 1$ is satisfied, but $N \ne N^*$ so that the comparability graph does not lead to the identification of the group structure.
\@startsection{section}{1}
\z@{0.7\linespacing}{.7\linespacing}{Consistent Estimation of the Ordered Group Structure}
\@startsection{subsection}{2}
\z@{.4\linespacing}{.6\linespacing}{\normalfont}{Pairwise Hypothesis Testing Problems}
In this section, we develop a method to estimate the group structure consistently for the case where the comparability graph is complete, so that we take $\mathcal{E}$ to be all $ij$ with $i,j \in N, i \ne j$. We first formulate three pairwise hypothesis testing problems for each comparable pair $ij \in \mathcal{E}$:
\begin{align}
H_{0,ij}^{+} &:\delta_{ij}\leq 0\text{ against }H_{1,ij}^{+}:\delta_{ij}>0\text{,} \\
H_{0,ij}^{0} &:\delta _{ij}^{0}=0\text{ against }H_{1,ij}^{0}:\delta_{ij}^{0}\neq 0\text{ and} \notag \\
H_{0,ij}^{-} &:\delta_{ji}\leq 0\text{ against }H_{1,ij}^{-}:\delta_{ji}>0\text{.} \notag
\end{align}
In most examples, we have various tests available. Instead of committing
ourselves to a particular method of hypothesis testing, let us assume
generally that we are given $p$-values $\hat{p}_{ij}^{+}$, $\hat{p}_{ij}^{0}$
and $\hat{p}_{ij}^{-}$ from the testing of $H_{0,ij}^{+}$, $H_{0,ij}^{0}$
and $H_{0,ij}^{-}$, against $H_{1,ij}^{+}$, $H_{1,ij}^{0}$ and $H_{1,ij}^{-}$
respectively. Let $L$ be the size of the sample (i.e., the number of the markets or games) that is used to construct these $p$-values. We will present conditions for the p-values later and explain how we construct $p$-values using bootstrap in Section 4.3.
\@startsection{subsection}{2}
\z@{.4\linespacing}{.6\linespacing}{\normalfont}{The Classification Method}
\@startsection{subsubsection}{3}
\z@{.4\linespacing}{.6\linespacing}{\normalfont}{The Selection-Split Algorithm}
Let us introduce a method of obtaining an ordered partition $(\hat N_1',\hat N_2')$ of a given subset $N' \subset N$ using $p$-values $\hat p_{ij}^s$, $s \in \{+,0,-\}$.
\begin{definition} For a subset $N' \subset N$, we say that the ordered partition of $N'$ into $(\hat N_1',\hat N_2')$ is obtained by \textbfit{the Split Algorithm} if it is obtained as follows. For each $i\in N'$, we let
\begin{align*}
\hat N_{1}'(i) &= \{j\in N'\backslash \{i\}: \log \hat{p}
_{ij}^{+}\le \log \hat{p}_{ij}^{-} - r_L \}\text{ and } \\
\hat N_{2}'(i) &= \{j\in N'\backslash \{i\}: \log \hat{p}
_{ij}^{-}\le \log \hat{p}_{ij}^{+} - r_L \},
\end{align*}
where $r_L \rightarrow \infty$ satisfies Assumption (ref) below.\footnote{In many cases, it suffices to consider a sequence such that $r_L/\log L \rightarrow 0$. In practice, we propose $r_L = (\log L)^{1/3}$ which satisfies Assumption (ref) below under lower level regularity conditions. See Section C.3 in the supplemental note for details.} Set
$i^*= \text{argmin}_{i\in N'}\min\{s_1(i),s_2(i)\}$, where
\begin{eqnarray*}
s_1(i) =\frac{1}{|\hat N_1'(i)|}\sum_{j\in \hat N_1'(i)}\log \hat{p}_{ij}^{+}, \text{ and } s_2(i) =\frac{1}{|\hat N_2'(i)|}\sum_{j\in \hat N_2'(i)}\log \hat{p}_{ij}^{-}.
\end{eqnarray*}
(We set $s_1(i) = 0$ if $\hat N_1'(i)$ is empty, and similarly with $s_2(i)$.) Then we take
\begin{eqnarray*}
(\hat N_1',\hat N_2') &=& (\hat N_1'(i^*), N' \setminus \hat N_1'(i^*)), \text{ if } s_1(i^*) \le s_2(i^*);\\
(\hat N_1',\hat N_2') &=& (N' \setminus \hat N_2'(i^*),\hat N_2'(i^*)), \text{ if } s_1(i^*) > s_2(i^*).
\end{eqnarray*}
\end{definition}
The set $\hat N_{1}'(i)$ estimates the set of agents of lower type than $i$, and the set $\hat N_{2}'(i)$ estimates the set of agents of higher type than $i$. Let
\begin{eqnarray*}
N_1'(i) = \{j \in N'\setminus\{i\}: \tau(i) > \tau(j) \}, \text{ and } N_2'(i) = \{j \in N'\setminus\{i\}: \tau(i) < \tau(j) \}.
\end{eqnarray*}
A necessary condition for $\hat N_1'(i)$ to coincide with $N_1'(i)$ is that $i$ has higher type than those in $\hat N_1'(i)$. The more negative the quantity $s_1(i)$ is, the more likely that this necessary condition is met. A similar observation applies to $s_2(i)$ as well. Thus we choose a partition based on $i^*$ that minimizes $\min\{s_1(i),s_2(i)\}$ over $i$.
Suppose that we are given an ordered partition $(\hat N_1',...,\hat N_s')$ of $N$. The Selection-Split Algorithm that we propose produces an ordered partition $(\hat N_1'',...,\hat N_{s+1}'')$ of $N$ from $(\hat N_1',...,\hat N_s')$ using two steps, the Selection Step and the Split Step, as follows.
\textbfit{1. The Selection Step}: Let $\hat p_k = \min_{i,j \in \hat N_k': i \ne j}\hat p_{ij}^0$, $k=1,...,s$, and select $\hat N_{k^*}'$ with $k^*$ such that
\begin{align*}
\hat p_{k^*} = \min_{1 \le k \le s} \hat p_k.
\end{align*}
\textbfit{2. The Split Step}: We split $\hat N_{k^*}'$ into $(\hat N_{k^*,1}',\hat N_{k^*,2}')$ using the Split Algorithm, and relabel the partition: $(\hat N_1',...,\hat N_{k^*-1}',\hat N_{k^*,1}',\hat N_{k^*,2}',\hat N_{k^*+1}',...,\hat N_s') = (\hat N_1'',...,\hat N_{s+1}'')$.
The Selection Step chooses a group $\hat N_{k^*}'$ that is most likely to contain agents with heterogeneous types and the Split Step splits this group into two sets using the Split Algorithm. The Selection-Split algorithm depends on the data only through the p-values $\hat p_{ij}^s$, $s \in \{+,0,-\}$.
\@startsection{subsubsection}{3}
\z@{.4\linespacing}{.6\linespacing}{\normalfont}{The Classification Method}
For a given positive integer $ K $, partition $ N $ into $ K $ groups as follows.
First, split $N$ into $(\hat N_1^{[2]},\hat N_2^{[2]})$ using the Split Algorithm to $N$, and apply the Selection-Split Algorithm sequentially to obtain $(\hat N_1^{[3]},\hat N_2^{[3]},\hat N_3^{[3]})$, $(\hat N_1^{[4]},...,\hat N_4^{[4]})$, and so on, until we have $(\hat N_1^{[K]},...,\hat N_K^{[K]})$ for a given number $K$. For each $ K $, we define
\begin{equation*}
\hat V(K)=\frac{1}{K}\sum_{k=1}^{K}\left\vert \min_{i,j\in \hat N_{k}^{[K]}} \log \hat{p}_{ij}^{0}\right\vert,
\end{equation*}
and then select
\begin{equation*}
\hat{K}=\text{argmin}_{1 \le K \le n} \hat V(K)+Kg(L),
\end{equation*}
where $g(L)$ is positive and slowly increasing in $L$.\footnote{The choice of $g(L)=\log \log L$ appears to work very well from our numerous Monte Carlo simulation experiments.} We take
\begin{align}
\hat T_{\hat K} = (\hat N_1^{[\hat K]},...,\hat N_{\hat K}^{[\hat K]})
\end{align}
to be our estimated group structure. The component $\hat V(K)$ measures the goodness-of-fit of the classification, and the second component $Kg(L)$ represents a penalty term that prevents overfitting.
We show that $\hat T_{\hat K}$ is consistent for the underlying group structure $T$ defined in ((ref)) under regularity conditions.
\@startsection{subsection}{2}
\z@{.4\linespacing}{.6\linespacing}{\normalfont}{Constructing $p$-Values Using Bootstrap}
In most applications, we can use bootstrap to construct $p$-values for
testing the inequality restrictions of ((ref)).\footnote{
See Bugni2010,
AndrewsShi2013, ChernozhukovLeeRosen2013,
LeeSongWhang2013, and LeeSongWhang2018, among many others,
and references therein.} For the sake of concreteness, we explain the bootstrap procedure along the proposal made by LeeSongWhang2018. Suppose that we are given observations $\{Z_{\ell}\}_{\ell = 1}^{L}$,
where $Z_{\ell}=(Z_{i,\ell})_{i=1}^{n}$ denotes the observations pertaining to
market $\ell$ and $Z_{i,\ell}$ denotes the vector of observations specific to agent $i$.
Suppose that for each pair of agents $i$ and $j$, there exists a nonparametric
function, say, $r_{ij}(x)$ such that $\tau(i) \ge \tau(j)$ if and only if $r_{ij}(x) \ge 0$ for all $x \in \mathcal{X}$, where $\mathcal{X}$ is the common domain of the function $r_{ij}(\cdot)$, $i,j \in N$.
To construct a test statistic, we first estimate $r_{ij}(x)$ using the
sample $\{Z_{\ell}\}_{\ell = 1}^{L}$ to obtain $\hat{r}_{ij}(x)$ (e.g., using a kernel regression estimator). Then we construct
the following indexes:
\begin{eqnarray}
\hat \delta_{ij} =\int \max \left\{\hat{r}_{ij}(x),0\right\} dx \text{ and } \hat \delta_{ij}^{0} = \int \left\vert \hat{r}_{ij}(x)\right\vert dx.
\end{eqnarray}
For $p$-values, we re-sample $\{Z_{\ell}^*\}_{\ell = 1}^{L}$ (with replacement)
from the empirical distribution of $\{Z_{\ell}\}_{\ell = 1}^{L}$ and construct a
nonparametric estimator $\hat{r}_{ij}^*(x)$ for each pair $(i,j)$ in
the same way as we did using the original sample. Using these bootstrap
estimators, we construct the following bootstrap test statistics:
\begin{eqnarray}
\hat \delta_{ij}^{\ast } =\int \max \left\{ \hat{r}_{ij}^*(x)-\hat{r}
_{ij}(x),0\right\} dx \text{ and } \hat \delta_{ij}^{0\ast } &=&\int \left\vert \hat{r}_{ij}^*(x)-\hat{r}
_{ij}(x)\right\vert dx. \notag
\end{eqnarray}
Note that the bootstrap test statistic involves recentering to impose the
null hypothesis. Now, the $p$-values, $\hat{p}_{ij}^{+}$, $\hat{p}_{ij}^{-},$
and $\hat{p}_{ij}^{0}$ can be constructed from the bootstrap distributions
of $\hat \delta_{ij}^{\ast }$, $\hat \delta_{ji}^{\ast }$, and $\hat \delta_{ij}^{0\ast }$ respectively, using $\hat \delta_{ij}, \hat \delta_{ji}$ and $\hat \delta_{ij}^{0}$ as test statistics.
\@startsection{subsection}{2}
\z@{.4\linespacing}{.6\linespacing}{\normalfont}{Consistency of Classification}
We prove consistency of the estimated classification $\hat T_{\hat K}$ as $L\rightarrow \infty$ while $n$ fixed. (Consistency results and the proof for the case of both $n$ and $L$ increasing to infinity are found in the supplemental note.) Let $\mathcal{P}$ be the collection of the distributions $P$ of the whole vector of the observations in each market $\ell$. For each $\varepsilon>0$, $ij \in \mathcal{E}$ and $s \in \{+,0,-\}$, we define
\begin{eqnarray*}
\mathcal{P}_{0,ij}^s = \{P \in \mathcal{P}: \delta_{ij}^s(P) \le 0 \}, \text{ and }
\mathcal{P}_{\varepsilon,ij}^s = \{P \in \mathcal{P}: \delta_{ij}^s(P) \ge \varepsilon \},
\end{eqnarray*}
where we write the pairwise indexes $\delta_{ij}^s$ as $\delta_{ij}^s(P)$ to reflect that the pairwise indexes depend on $P$. Thus $\mathcal{P}_{0,ij}^s$ is the collection of probabilities under the pairwise null hypothesis $H_{0,ij}^s$, and $\mathcal{P}_{\varepsilon,ij}^s$ is the collection of probabilities under the pairwise alternative hypotheses $H_{1,ij}^s$ such that $\delta_{ij}^s(P)$ is away from zero at least by $\varepsilon$. Then we define
\begin{eqnarray*}
\mathcal{P}_{0,\varepsilon} = \bigcup_{s \in \{+,0,-\}} \bigcup_{ij \in \mathcal{E}} (\mathcal{P}_{0,ij}^s \cup \mathcal{P}_{\varepsilon,ij}^s).
\end{eqnarray*}
We assume that the $p$-value takes the following form:
\begin{eqnarray*}
\hat p_{ij}^s = 1 - \tilde F_{ij}^s(\tilde T_{ij}^s), s \in \{+,0,-\},
\end{eqnarray*}
where $\tilde F_{ij}^s$ is a CDF and $\tilde T_{ij}^s$ is a random variable both of which depend on the data. Typically, $\tilde T_{ij}^s$ represents an appropriately normalized test statistic and $\tilde F_{ij}^s$ represents the CDF of the bootstrap distribution of the test statistic after recentering. We make the following assumption.
\begin{assumption}
There exist sequences $\lambda_L \rightarrow \infty$ and $\rho_L \rightarrow 0$ and constants $c_{ij}^s$, $s \in \{+,0,-\}$ such that along each sequence of probabilities $P_L \in \mathcal{P}_{0,\varepsilon}$ and for each pair $i,j \in N$, the following holds for all $s \in \{+,0,-\}$, as $L \rightarrow \infty$.
(i) If $\tau(i) = \tau(j)$, $\tilde T_{ij}^s \rightarrow_d W_{ij}^s,$ for some random variable $W_{ij}^s$.
(ii) If $\tau(i) > \tau(j)$, $\tilde T_{ij}^+/\lambda_L \rightarrow_P c_{ij}^+$ and $\tilde T_{ij}^- = O_P(1)$.
(iii) If $\tau(i) < \tau(j)$, $\tilde T_{ij}^-/\lambda_L \rightarrow_P c_{ij}^-$ and $\tilde T_{ij}^+ = O_P(1)$.
(iv) If $\tau(i) \ne \tau(j)$, $\tilde T_{ij}^0/\lambda_L \rightarrow_P c_{ij}^0$.
(v) $\sup_{t \in \mathbf{R}} |\tilde F_{ij}^s(t) - F_{ij,\infty}^s(t) | = O_P(\rho_L)$, where $F_{ij,\infty}^s$ is the CDF of $W_{ij}^s$.
(vi) $r_L^{-1} \log(1 - F_{ij,\infty}^s(c_1 \lambda_L) + c_2 \rho_L) \rightarrow - \infty$, for all constants $c_1,c_2>0$.
\end{assumption}
Here we are assuming that for each pair of agents we have enough observations on markets in which the pair of agents participate so that we can perform consistent tests based on pairwise comparison. Assumption (ref) is a high level assumption and is typically satisfied for various choices of test statistics that arise in the literature of moment inequality testing. We provide lower level conditions in the case of nonparametric tests based on LeeSongWhang2018 in the next subsection.
\begin{theorem}
Suppose that Assumption (ref) holds, and that $g(L) \rightarrow \infty$ and $g(L)/r_L \rightarrow 0$ as $L\rightarrow \infty$. Then, for any $\varepsilon>0$, along a sequence of probabilities $P_L$ from $\mathcal{P}_{0,\varepsilon}$,
\begin{equation*}
P_L\{\hat{K}=K_{0}\}\rightarrow 1, \text{ as } L \rightarrow \infty,
\end{equation*}
and the estimated group structure $\hat{T}_{\hat{K}}$ in ((ref)) satisfies that as $L\rightarrow \infty,$
\begin{equation*}
P_L \{ \hat{T}_{\hat{K}} = T \} \rightarrow 1.
\end{equation*}
\end{theorem}
The proof of Theorem (ref) is in the supplemental note. It proceeds in two steps. First, we show that $\hat T_{K_0}$ is consistent for $T$. Second, we show that $\hat{K}$ is consistent for $K_{0} $. To see the intuition for this second step, note that when $K\ge K_{0}$, the component $\hat V(K)$ is $O_P(1)$, and when $K < K_{0}$, the component $\hat V(K)$ diverges at a rate faster than $g(L)$. From this, we obtain that $\hat{K}$ is consistent for $K_{0}$.
\@startsection{subsection}{2}
\z@{.4\linespacing}{.6\linespacing}{\normalfont}{Lower Level Conditions for Assumption (ref)}
Lower level conditions for Assumption (ref) can be found from the literature of testing for moment inequality restrictions. For the sake of concreteness, we focus on the situation where nonparametric function $r_{ij}(x)$ introduced in Section (ref) arises from difference between two nonparametric regression functions and the testing procedure is done by the method proposed in LeeSongWhang2018. Suppose that we have
\begin{align}
m_i(x) > m_j(x), \forall x \in \mathcal{X} & \textnormal{ if and only if } \tau (i)>\tau (j); \\ \notag
m_i(x) = m_j(x), \forall x \in \mathcal{X} & \textnormal{ if and only if } \tau (i)=\tau (j); \\\notag
m_i(x) < m_j(x), \forall x \in \mathcal{X} & \textnormal{ if and only if }\tau (i)<\tau (j),
\end{align}
where $m_i(x) = \mathbf{E}[Y_{i,\ell}|X_{i,\ell} = x], i \in N$, and $\ell = 1,...,L$, is the sample unit index. We take $r_{ij}(x) = m_i(x) - m_j(x)$. Let us define a kernel estimator of $m_i(x)$ as follows:
\begin{eqnarray*}
\hat m_i(x) = \frac{ \sum_{\ell = 1}^L Y_{i,\ell} K_h(X_{i,\ell} - x)}{ \sum_{\ell = 1}^L K_h(X_{i,\ell} - x)},
\end{eqnarray*}
where $K_h(x) = K(x/h)/h$, and $K(\cdot)$ is a multivariate kernel and $h$ is a bandwidth. We let
\begin{eqnarray*}
\hat r_{ij}(x) = \hat m_i(x) - \hat m_j(x).
\end{eqnarray*}
Then the test statistics we use are defined as
\begin{align}
\hat \delta_{ij}^+ &= \int_\mathcal{X} \max\{\hat r_{ij}(x),0\} dx, \quad \hat \delta_{ij}^- = \int_\mathcal{X} \max\{\hat r_{ji}(x),0\} dx, \text{ and }\\ \notag
\hat \delta_{ij}^0 &= \int_\mathcal{X} |\hat r_{ij}(x)| dx.
\end{align}
As for the bootstrap test statistics, we first obtain bootstrap samples $\{(Y_{i,\ell}^*,X_{i,\ell}^*)_{i \in N}\}_{\ell = 1}^L$ by resampling the vector $(Y_{i,\ell}^*,X_{i,\ell}^*)_{i \in N}$ from the empirical distribution of $\{(Y_{i,\ell},X_{i,\ell})_{i \in N}\}_{\ell = 1}^L$ with replacement. Using the bootstrap sample, we construct
\begin{eqnarray*}
\hat r_{ij}^*(x) = \hat m_i^*(x) - \hat m_j^*(x),
\end{eqnarray*}
where
\begin{eqnarray*}
\hat m_i^*(x) = \frac{ \sum_{\ell = 1}^L Y_{i,\ell}^* K_h(X_{i,\ell}^* - x)}{ \sum_{\ell = 1}^L K_h(X_{i,\ell}^* - x)}.
\end{eqnarray*}
Then the bootstrap test statistics we use are defined as\footnote{One could also use alternative bootstrap statistics using estimated contact sets as in LeeSongWhang2018 to enhance the power. For simplicity of exposition, here we present the case where we use the least favorable configurations.}
\begin{align}
\hat \delta_{ij}^{+*} &= \int_\mathcal{X} \max\{\hat r_{ij}^*(x) - \hat r_{ij}(x),0\} dx, \quad \hat \delta_{ij}^{-*} = \int_\mathcal{X} \max\{\hat r_{ji}^*(x) - \hat r_{ji}(x),0\} dx, \text{ and }\\ \notag
\hat \delta_{ij}^{0*} &= \int_\mathcal{X} |\hat r_{ij}^*(x) - \hat r_{ij}(x)| dx.
\end{align}
Let the CDF of the bootstrap distribution of $\hat \delta_{ij}^{s*}$ be denoted by $F_{ij}^s$. Then we set the pairwise $p$-value to be $\hat p_{ij}^s = 1 - F_{ij}^s(\hat \delta_{ij}^s)$. In this situation, we provide a low level condition for Assumption (ref).
Let $a_{ij,L}^s$ and $\sigma_{ij,L}^s$ be sequences of constants such that
\begin{eqnarray}
a_{ij,L}^s = O(1), \text{ and } \sigma_{ij,L}^s \rightarrow \sigma_{ij}^s >0,
\end{eqnarray}
as $n,L\rightarrow \infty$. We take
\begin{align}
\tilde T_{ij}^s &= (\sqrt{L}\hat \delta_{ij}^s - h^{-d/2} a_{ij,L}^s)/\sigma_{ij,L}^s, \text{ and }\\ \notag
\tilde T_{ij}^{s*} &= (\sqrt{L}\hat \delta_{ij}^{s*} - h^{-d/2} a_{ij,L}^s)/\sigma_{ij,L}^s.
\end{align}
(The researcher does not need to know, estimate, or use the constants $a_{ij,L}^s$ and $\sigma_{ij,L}^s$ for the construction of the pairwise $p$-values and for the implementation of the classification algorithm of this paper.) Then we can rewrite
\begin{eqnarray*}
\hat p_{ij}^s = 1 - \tilde F_{ij}^s(\tilde T_{ij}^s),
\end{eqnarray*}
where $\tilde F_{ij}^s$ is the CDF of the bootstrap distribution of $\tilde T_{ij}^{s*}$. Let $\|\cdot\|_\infty$ denote the sup norm, i.e., $\|f\|_\infty = \sup_x |f(x)|$ for any real function $f$. Let us consider the following set of assumptions.
\begin{assumption}
(i) For each $s \in \{+,0,-\}$ and each $i,j
\in N$, there exist sequences of constants $a_{ij,L}^s$ and $\sigma_{ij,L}^s$ such that the conditions in ((ref)) hold, and under $H_{0,ij}^0$ in ((ref)),
\begin{eqnarray*}
\tilde T_{ij}^s \rightarrow_d N(0,1),
\end{eqnarray*}
and $\|\tilde F_{ij}^s - \Phi\|_\infty = O_P(L^{-\alpha})$ for some $\alpha>0$, and $\Phi$ is the CDF of $N(0,1)$.
(ii) $\sup_{x \in \mathcal{X}}|\hat r_{ij}(x) - r_{ij}(x)| = o_P(1)$, as $L\rightarrow \infty$.
(iii) Suppose that $L h^d \rightarrow \infty$ while $h \rightarrow 0$ as $L\rightarrow \infty$.
\end{assumption}
The lower level conditions for Condition (i) can be found in LeeSongWhang2018. Condition (ii) follows if the kernel regression estimators $\hat g_i(x)$ are uniformly consistent. (See, e.g., Hansen2008.) Condition (iii) is a standard bandwidth condition in the literature of kernel estimators. Then, we obtain the following lemma.
\begin{lemma}
Suppose that Assumption (ref) holds, and that the sequence $r_L \rightarrow \infty$ is such that $r_L/\log L \rightarrow 0$ as $L\rightarrow \infty$. Then Assumption (ref) holds.
\end{lemma}
The proof of this lemma is given in the appendix.
\@startsection{subsection}{2}
\z@{.4\linespacing}{.6\linespacing}{\normalfont}{Two-Step Estimation Using the Estimated Group Structure}
The estimated group structure can be used as a first-step estimator in a two-step procedure for estimating a structural parameter. Recall that $\tau:N \rightarrow \{1,...,K_0\}$ defines the group structure. Let us denote $\tau(\cdot;P)$ to indicate that the group structure is identified. Suppose that $\theta_0$ is a structural parameter that is identified as follows: $Q(\overline \theta, \tau(\cdot;P);P)$ as a function of $\overline \theta$ has a unique minimizer in a parameter space $\Theta$ and
\begin{eqnarray*}
\theta_0 = \arg \min_{\overline \theta \in \Theta} Q(\overline \theta, \tau(\cdot;P);P).
\end{eqnarray*}
In many applications $Q(\overline \theta, \tau(\cdot;P);P)$ is a population objective function that arises from Generalized Method of Moment (GMM) estimation or Maximum Likelihood Estimation (MLE). The two step estimator $\hat \theta$ of $\theta_0$ is defined as
\begin{eqnarray*}
\hat \theta = \arg \min_{\overline \theta \in \Theta} \hat Q(\overline \theta, \hat \tau(\cdot)),
\end{eqnarray*}
where $\hat \tau(\cdot)$ is the first-step estimator of the group structure that is consistent, i.e., for all $\varepsilon>0$,
\begin{eqnarray}
P\left\{\max_{1 \le i \le n}|\hat \tau(i) - \tau(i;P)|> \varepsilon\right\} \rightarrow 0,
\end{eqnarray}
as $L \rightarrow \infty$. As we saw before, one can obtain such estimator $\hat \tau$ using our Select-Split algorithm. Let $\tilde \theta$ be such that
\begin{eqnarray*}
\tilde \theta = \arg \min_{\overline \theta \in \Theta} \hat Q(\overline \theta, \tau(\cdot;P)),
\end{eqnarray*}
so that $\tilde \theta$ is an infeasible estimator when one uses the true group structure $\tau(\cdot;P)$ rather than the estimated version $\hat \tau(\cdot)$. The asymptotic normality of $\sqrt{L}(\tilde \theta - \theta_0)$ can be derived using the standard arguments, for example, using the general results in NeweyMcFadden1994. Then it is not hard to see that $\sqrt{L}(\tilde \theta - \theta_0)$ has the same limit distribution. To see this, by taking $\varepsilon<1$, we find from ((ref)) that
\begin{eqnarray*}
P\left\{\max_{1 \le i \le n}|\hat \tau(i) - \tau(i;P)| > 0 \right\} \rightarrow 0.
\end{eqnarray*}
Therefore,
\begin{eqnarray*}
P\{\hat \theta \ne \tilde \theta \} &=& P\left\{\arg\min_{\overline \theta \in \Theta}\hat Q(\overline \theta, \hat \tau(\cdot)) \ne \arg\min_{\overline \theta \in \Theta} \hat Q(\overline \theta, \tau(\cdot;P))\right\}\\
&\le& P\left\{\max_{1 \le i \le n}|\hat \tau(i) - \tau(i;P)| > 0 \right\} \rightarrow 0,
\end{eqnarray*}
as $L \rightarrow \infty$. Hence $\hat \theta = \tilde \theta$ with probability approaching one, as $L \rightarrow \infty$. This means that if the inference based on $\tilde \theta$ is asymptotically valid, so is that based on $\hat \theta$.
Note that this asymptotic validity holds pointwise in $P$. Given the known failure of uniform validity (uniform in $P$) for post-model selection inference (LeebPotcher2005), it is likely that the inference based on this two-step estimator $\hat \theta$ fails to satisfy asymptotic validity uniformly in $P$, unless one modifies the procedure appropriately. In this general set-up, it is far from trivial to find such a modification. We leave it to future research.
\@startsection{section}{1}
\z@{0.7\linespacing}{.7\linespacing}{Monte Carlo Simulations}
\@startsection{subsection}{2}
\z@{.4\linespacing}{.6\linespacing}{\normalfont}{Finite Sample Performance of the Classification}
We use a model of a first-price procurement auction with asymmetric independent private costs to study performance of our classification procedure. (See Appendix B.1 of the supplemental note.)
Bidders are classified into $K_{0}\ $groups. We abstract away from the formation of equilibrium strategies, and draw bids from a normal distribution $N(\mu _{k},\sigma ^{2})$ for each group $k=1,...,K_0$.
Let $L$ denote the number of auctions in which any given pair of bidders participate.
We consider two specifications of $\mu_k$'s. In one specification, $\mu_1=2.0,\mu_2=2.6,\mu_3=3.2,$ and $\mu_4=3.8$ with increment $D_\mu=0.6$, and in the other specification, $\mu_1=2.0,\mu_2=2.2,\mu_3=2.4,$ and $\mu_4=2.6$ with increment $D_\mu=0.2$. The variance $\sigma^2$ is taken to be $0.25$.
Table 1 summarizes the designs of group structures in our simulation.
The first two structures involve a total of 12 bidders and the last two 40 bidders.
The first and third are designed to be coarser group structures than the second and fourth respectively.
We construct $p$-values using the procedure in Section (ref) and obtain group classification from 500 simulated samples.
For each estimate, we used 200 bootstrap iterations to calculate $p$-values.
\begin{table}[t]
\begin{center}
Table 1: Group Structure in Experiments
\begin{tabular}{cccc}
\hline\hline
{ Structure} & ${\small \ \ \ \ }n{\small \ \ \ \ }$ & ${\small \ \ \
\ K}_{0}{\small \ \ \ \ }$ & ${\small \ \ \ \ n}_{k}{\small \ \ \ \ }$ \\
\hline
{ S1} & { 12} & { 2} & { 6} \\
{ S2} & { 12} & { 4} & { 3} \\
{ S3} & { 40} & { 2} & { 20} \\
{ S4} & { 40} & { 4} & { 10} \\ \hline\hline
\end{tabular}
\end{center}
\begin{flushleft}
{ Note:} $n$ { \ denotes the total number of
the bidders; }$K_{0}${ \ denotes the number of the groups; }$n_{k}$
{ \ denotes the number of actual bidders from group }${\small k}$
{ . For each structure in the simulation design, groups all have the
same number of bidders.}
\end{flushleft}
\end{table}
To evaluate the performance of our classification method, we define a measure of discrepancy between two ordered partitions $T_1$ and $T_2$:
\begin{eqnarray}
\delta \left( T_{1},T_{2}\right) &=& \frac{1}{K_1}\sum_{k=1}^{K_1} \min_{1 \le j \le K_2 } |N_k^1 \triangle N_j^2|,
\end{eqnarray}
where $T_{1}=(N_{1}^{1},...,N_{K_1}^{1})$ and $T_{2}=(N_{1}^{2},...,N_{K_2}^{2})$ are ordered partitions of $N$ and $\triangle$ denotes set-difference: $A \triangle B = (A\setminus B) \cup (B \setminus A)$.
We evaluate our classification method using two criterion: (1) Expected Average Discrepancy (EAD) defined as $ \mathbf{E} (\delta (T,\hat{T}_{\hat{K}}) ) $ and (2) HAD$(\lambda) \equiv P\{\delta (T,\hat{T}_{\hat{K}})>\lambda n\} $ for $0 < \lambda < 1$.
Table 2 reports estimates when there is no unobserved heterogeneity among bidders ($ K_0 = 1 $). In this case, our procedure detects the absence of unobserved heterogeneity effectively.
For a given $n$, there is a moderate increase in the accuracy of classification as $L$ increases, both in terms of EAD and HAD($\lambda$).
\fontsize{11}{13}\selectfont
\begin{table}[t]
\begin{center}
Table 2: Performance of the Classification with One Group ($K_{0} = 1$ and unknown)
\begin{tabular}{ccc|cccccc}
\hline\hline
& $n$ & $L$ & $\hat K_0$ & EAD & HAD(.10) & HAD(.25) & HAD(.50) & \\
\cline{2-8}
& 12 & 400 & 1.002 & 0.012 & 0.001 & 0.000 &0.000 &\\
& 12 & 200 & 1.003 & 0.014 & 0.002 & 0.000 &0.000 &\\
& 12 & 100 & 1.003 & 0.018 & 0.002 & 0.001 &0.000 &\\
\cline{2-8}
& 40 & 400 & 1.003 & 0.082 & 0.005 & 0.003 & 0 &\\
& 40 & 200 & 1.006 & 0.084 & 0.008 & 0.002 & 0 &\\
& 40 & 100 & 1.008 & 0.096 & 0.010 & 0.004 & 0 &\\
\hline\hline
\end{tabular}
\end{center}
\begin{flushleft}
{ Note: $n$ is the number of bidders in data; and $L$ the number of markets. $\hat K_0$ is the average number of estimated groups in 500 simulation samples. EAD is the average number of mismatched bidders across true groups and simulated samples. HAD($\lambda$) is the hazard rate of average discrepancy. For example, HAD(.10) = 0.002 means that in 499 simulated samples (out of a total of 500) the average number of mismatched bidders is less than 10 percent of the total number of bidders.}
\end{flushleft}
\end{table}
\fontsize{11}{13}\selectfont
\begin{table}[t]
\begin{center}
Table 3: Performance of the Classification with Multiple Groups ($K_{0} \ge 2$ and unknown)
\begin{tabular}{ccc|cccc|ccccc}
\hline\hline
& & & \multicolumn{4}{|c|}{$K_{0}=2$} & \multicolumn{4}{|c}{$K_{0}=4$} \\
$n$ & $L$ & $D_{\mu }$ & $\hat{K}_{0}$ & EAD & HAD(.25) & HAD(.75) & $\hat{
K}_{0}$ & EAD & HAD(.25) & HAD(.75) \\ \hline
12 & 400 & 0.6 & 2.00 & 0.00 & 0.00 & 0.000 & 3.96 & 0.03 & 0.01 & 0.00\\
12 & 400 & 0.2 & 2.00 & 0.01 & 0.00 & 0.000 & 3.94 & 0.04 & 0.03 & 0.00 \\
12 & 100 & 0.6 & 2.00 & 0.00 & 0.00 & 0.000 & 3.98 & 0.01 & 0.01 & 0.00 \\
12 & 100 & 0.2 & 2.03 & 0.52 & 0.07 & 0.004 & 3.24 & 1.53 & 0.24 & 0.00 \\ \hline
40 & 400 & 0.6 & 2.00 & 0.01 & 0.00 & 0.000 & 3.97 & 0.08 & 0.02 & 0.00 \\
40 & 400 & 0.2 & 2.01 & 0.01 & 0.00 & 0.000 & 3.83 & 0.43 & 0.09 & 0.00 \\
40 & 100 & 0.6 & 2.01 & 0.01 & 0.00 & 0.000 & 3.95 & 0.13 & 0.03 & 0.00 \\
40 & 100 & 0.2 & 2.18 & 1.91 & 0.02 & 0.000 & 3.06 & 1.93 & 0.49 & 0.11 \\ \hline\hline
\end{tabular}
\end{center}
\begin{flushleft}
{ Note: $\hat K_0$, EAD and HAD($\lambda$) are defined as in Table 2. $D_\mu$ is the difference between group means $\mu_1$ and $\mu_2$. Conditional on the number of markets ($L$) and the number of bidders in population ($n$), the classification task is harder when the difference between group means $D_\mu$ is smaller.}
\end{flushleft}
\end{table}
Table 3 reports results for $ K_0 = 2 $ and $ K_0 = 4 $. In both cases, the estimates for $K_0$ are mostly correct. Estimation accuracy increases with the difference between group means. For a given number of groups, the performance in terms of EAD and HAD are both better with greater group differences and larger sample sizes.
Misclassification errors tend to arise less often when the number of true groups is smaller, with the exception of $D_{\mu} = 0.2 $ and $ L = 100$. Intuitively, this is because when the same number of bidders is partitioned into fewer groups, we can use more pairwise inequalities for classification.
\@startsection{subsection}{2}
\z@{.4\linespacing}{.6\linespacing}{\normalfont}{Two-Step Estimation in a Structural Model}
In this section we use a simple structural model of procurement auctions to investigate the impact of classification errors on subsequent estimation of structural parameters.
A set of $N$ providers (bidders) is partitioned into $K_0$ groups, each with a distinct distribution of private costs. Let $N_{k} $ denote the set of providers in $N$ with type $k \in \{1,2,...,K_0\}$, and let $|N_{k}|$ denote its cardinality. The cost for a provider $i$ with type $\tau(i)\in \{1,2,...,K_0\}$ is given by $ c_{i,\ell}=\mu_{\tau(i)}+\epsilon_{i,\ell}$,
where $\epsilon_{i,\ell}$ follows $N(0,\sigma)$ with the support $[\underline{c},\,\bar{c}]$.\footnote{We set the upper and lower bounds of costs to $ \underline{c}=\frac{1}{K_0}\sum_k (\mu_{k}-1.96\times \sigma) $ and $\bar{c}=\frac{1}{K_0}\sum_k (\mu_{k}+1.96\times \sigma) $.
True parameters are chosen so that $\underline{c}$ is strictly positive.}
Auction participants are determined in two steps. First, two out of $K_0$ groups, $\tau_{l,1}$ and $\tau_{l,2}$, are chosen at random.
Next, $n_{1}$ and $n_{2}$ providers are randomly drawn from the corresponding groups $N_{\tau_{l,1}}$ and $N_{\tau_{l,2}}$ and their costs were constructed as above. Here $n_{1}$ and $n_{2}$ denote the numbers of actual participants (those who submitted bids in the auction). Then participants bid based on their realized costs.
The participant with the lowest bid wins. The identity of each participant and its bid are both reported in data.
We consider two specifications: ($S_1$) with $K_0=4$, $|N_k|=4$ for all $k$, and ($S_2$) with $K_0=4$, $|N_k|=10$ for all $k$.
For both specifications, we set $\mu=(2,\,2.4,\,2.8,\,3.2)$ and $\sigma=0.5$.
We run the following four experiments with different specification and sample sizes: (A) $S_1$, $L=200$; (B) $S_2$, $L=200$; (C) $S_1$, $L=400$; and (D) $S_2$, $L=400$. We set $n_{1} = 1$ and $n_{2}=1$ so that each auction has $2$ actual participants chosen from $K_0$ different types.
Structural parameters $K_0,\,\tau(\cdot),\, \theta=\{(\mu_{k})_{k=1}^{K_0}, \sigma\}$ are estimated via two steps.
First, the group structure ($\hat{\tau}(\cdot)$ and $\hat{K}$) are estimated using our classification algorithm.
Next, we apply GMM to estimate the remaining structural parameters using the following moments for $k = 1,...,K_0$: (1) within-group means of bids:
$\sum_{i=1}^n \mathbf{E}[B_{i,\ell}-\mu_{B,k}(\theta;\,I)]1\{\hat \tau(i) = k\} = 0$; and (2) within-group second moment of bids: $\sum_{i=1}^n \mathbf{E}[B_{i,\ell}^2-(\mu_{B,k}(\theta;\,I)^2+\sigma_{B,k}(\theta;\,I)^2)]1\{\hat \tau(i) = k\} = 0$, where $\mu_{B,k}(\theta;\,I)$ and $\sigma_{B,k}(\theta;\,I)$ denote the mean and standard deviation of equilibrium bid distribution for bidders from group $k$, $\theta$ the vector of parameters and $I$ the profile of participant types.
Standard errors are computed from the analytic expression for the covariance matrix in asymptotic distribution.
To compute $\mu_{B,k}(\theta_0;\,I)$ and $\sigma_{B,k}(\theta_0;\,I)$ for a given $\theta_0$ and profile of participant types $I=(\tau_{l,1}$, $\tau_{l,2}$, $n_1$, $n_2$) we simulate the equilibrium bidding functions.\footnote{
Specifically, we start from the analytical bidding function when all participants belong to the same group, and use a modified version of the numerical method in MarshallMeurerRichardStromquist1994 to solve for bidding strategies in the presence of multiple groups.
We impose a sample version of $\underline{c}$ and $\bar{c}$ by replacing $\sigma$ with its sample analog.}
The bidding functions are then combined with the cost distributions implied by a vector of trial parameters, $\theta_0$, to obtain the distribution of bids: $F_{B,k}(b|\,\theta_0,\,I)=F_{C,k}(\beta_k^{-1}(b)|\,\theta_0)$. Here $F_{C,k}(.|\,\theta_0)$ denotes the distribution of project's cost for a bidder belonging to group $k$ which is corresponds to a parameter vector $\theta_0$ and $\beta_k(c)$, $\beta_k^{-1}(b)$ are the bid and the inverse bid functions used by such bidder. We then compute the mean and the standard deviation of this bid distribution.
\fontsize{11}{13}\selectfont
\begin{table}[t]
\begin{center}
Table 4: Simulation Results from Specifications A and B
\begin{tabular}{rrrr|ccccc}
\hline\hline
& & & & $\mu_1$ & $\mu_2$ & $\mu_3$ & $\mu_4$ & $\sigma$ \\
\hline\hline
Spec A & \multicolumn{2}{r}{ Using True Groups} & & & & & & \\
& & & Rej. Prob. & 0.0150 & 0.0515 & 0.0523 & 0.0546 & 0.0149 \\
& & & Bias & -0.0189 & -0.0252 & -0.0610 & -0.0511 & 0.0242 \\
& & & MSE & 0.0005 & 0.0008 & 0.0035 & 0.0039 & 0.0039 \\
\cline{2-9}
& \multicolumn{2}{r}{Using Est'd Groups} & & & & & \\
& & & Rej. Prob. & 0.0148 & 0.0542 & 0.0510 & 0.0485 & 0.0151 \\
& & & Bias & 0.0059 & 0.0329 & -0.0241 & -0.0225 & -0.0549 \\
& & & MSE & 0.0041 & 0.0083 & 0.0035 & 0.0027 & 0.0383 \\
\hline
\hline
Spec B & \multicolumn{2}{r}{Using True Groups} & & & & & \\
& & & Rej. Prob. & 0.0120 & 0.0515 & 0.0512 & 0.0514 & 0.0111 \\
& & & Bias & -0.0211 & -0.0233 & -0.0621 & -0.0622 & 0.0236 \\
& & & MSE & 0.0005 & 0.0007 & 0.0039 & 0.0039 & 0.0034 \\
\cline{2-9}
& \multicolumn{2}{r}{Using Est'd Groups} & & & & & \\
& & & Rej. Prob. & 0.0131 & 0.0550 & 0.0540 & 0.0530 & 0.0160 \\
& & & Bias & -0.0213 & -0.0218 & -0.0763 & -0.0765 & 0.0211 \\
& & & MSE & 0.0004 & 0.0015 & 0.0411 & 0.0441 & 0.0023 \\
\hline\hline
\end{tabular}
\end{center}
\begin{flushleft}
{ Note: Specification A uses $K_{0} = 4$, $n_k=4$, and $L=200$ and Specification B uses $K_{0} = 4$, $n_k=10$, and $L=200$. Here $n_k$ is the number of bidders in group $k$, and $L$ the number of markets. The rejection probabilities are from $t$-tests for the individual parameters. The nominal rejection probability is set to 0.05. }
\end{flushleft}
\end{table}
\fontsize{11}{13}\selectfont
\begin{table}[t]
\begin{center}
Table 5: Simulation Results from Specifications C and D
\begin{tabular}{rrrr|ccccc}
\hline\hline
& & & & $\mu_1$ & $\mu_2$ & $\mu_3$ & $\mu_4$ & $\sigma$ \\
\hline\hline
Spec C & \multicolumn{2}{r}{Using True Groups} & & & & & \\
& & & Rej. Prob. & 0.0149 & 0.0500 & 0.0513 & 0.0520 & 0.0149 \\
& & & Bias & -0.0214 & -0.0222 & -0.0615 & -0.0713 & 0.0237 \\
& & & MSE & 0.0005 & 0.0007 & 0.0039 & 0.0039 & 0.0006 \\
\cline{2-9}
& \multicolumn{2}{r}{Using Est'd Groups} & & & & & \\
& & & Rej. Prob. & 0.0151 & 0.0485 & 0.0526 & 0.0545 & 0.0151 \\
& & & Bias & 0.0131 & 0.0412 & -0.0625 & -0.0656 & -0.0241 \\
& & & MSE & 0.0060 & 0.0008 & 0.0053 & 0.0031 & 0.0054 \\
\hline
\hline
Spec D & \multicolumn{2}{r}{Using True Groups} & & & & & \\
& & & Rej. Prob. & 0.0133 & 0.0480 & 0.0510 & 0.0520 & 0.0108 \\
& & & Bias & -0.0227 & -0.0219 & -0.0611 & -0.0231 & 0.0236 \\
& & & MSE & 0.0005 & 0.0007 & 0.0039 & 0.0039 & 0.0006 \\
\cline{2-9}
& \multicolumn{2}{r}{Using Est'd Groups} & & & & & \\
& & & Rej. Prob. & 0.0126 & 0.0498 & 0.0520 & 0.0520 & 0.0128 \\
& & & Bias & -0.0229 & -0.0123 & -0.0761 & -0.0361 & 0.0098 \\
& & & MSE & 0.0093 & 0.0056 & 0.0068 & 0.0061 & 0.0007 \\
\hline\hline
\end{tabular}
\end{center}
\begin{flushleft}
{ Note: Specification C uses $K_{0} = 4$, $n_k=4$, and $L=400$, and Specification D, $K_{0} = 4$, $n_k=10$, and $L=400$. Here $n_k$ is the number of bidders in group $k$ and $L$ the number of markets. The nominal rejection probability is set to 0.05.}
\end{flushleft}
\end{table}
Tables 4 and 5 report the bias and mean squared errors (MSEs) of two estimators for $(\mu_{k})_{k=1}^{K_0}$ and $\sigma$. The first is an “infeasible" estimator that uses the knowledge of the true group structure. The second is the two-step estimator we propose, which requires bidder classification in the first step.
These two tables also report the rejection probabilities from t-tests of individual parameters.
Table 4 reports results for a smaller sample with $L=200$.
The rejection probabilities are close to the nominal rejection rate 0.05, except for parameters $\mu_1$ and $\sigma$. The MSE and bias for all parameters are reasonably small. Table 4 also shows that the rejection probabilities for the infeasible estimator using the true groups and those for the actual estimator using the estimated groups are very similar. There is some minor difference between these two estimators in the MSE of some group means. The discrepancy seems more pronounced when the size of each group is increased from $|N_k|=4$ to $|N_k|=10$.
Table 5 reports the same results for larger samples with $ L=400 $. The performance of the estimators improves slightly relative to Table 4. Again, the rejection probabilities for the two estimators are similar.
There is also evidence that with a larger number of the markets, our classification method performs better given the same number of within-group bidders.
Overall, Table 4 and 5 provide simulation evidence that the classification errors in the first-step do not have any major impact on the finite sample performance of the two-step estimators for structural parameters.
\@startsection{section}{1}
\z@{0.7\linespacing}{.7\linespacing}{Empirical Application: California Market for Highway Procurement}
We apply our methodology to analyze procurement auctions conducted by the California Department of Transportation (CalTrans) to allocate projects for highway repair work. Our goal is to demonstrate the performance of our method in the empirical setting, and to highlight the consequences of ignoring agent unobserved heterogeneity in estimation.\footnote{Please note that under traditional approach the most straightforward way to account for possible cost asymmetries would be to
estimate firm-specific cost distributions. This approach, however, is not
feasible in most auction studies. This is because the primitives of an
auction game (cost distributions) are linked to the observed auction
outcomes (bid distributions) through a set of non-linear bidding strategies
which have to be obtained by solving a system of differential equations that
has a degeneracy on the boundary. Such system needs to be solved for every possible configuration of the set of participating bidders.
If we define such sets taking into account bidders' identities, the number of such sets will be very large, i.e. $2^N$ (N is the number of bidders).
Such concerns do not arise in non-parametric studies since the bidding
strategy and the underlying cost distribution could be recovered from the
first-order conditions by applying them to appropriate bid distributions
(see GuerrePerrigneVuong2000). However, as before, the estimation
has to be implemented conditional on the composition of the set of
participants which summarizes the competitive structure of an auction known
to all market participants and is reflected in bidding strategies. Thus, the
afore-mentioned procedure is likely to be infeasible due to data limitations
which are demonstrated in Figure 1.}
\paragraph{\textbf{Model.}}
We follow the literature in modeling the auction market so that each project attracts a set of potential bidders who decide whether to participate in the auction and, if deciding to participate, choose a bid to submit. Our main innovation is to allow for contractors participating in this market to differ in a way that is not observed by the researcher. Specifically, each contractor is characterized by a
contractor-specific cost factor (invariant across projects) $q_{i}$ which takes discrete values in $\{\bar{q}_{0},\,\bar{q}_{1},\,...,\,\bar{q}_{K_0}\}$.
This unobserved cost factor captures the difference in cost efficiencies
across firms generated perhaps by the differences in managerial ability or
other factors associated with the firm organization.
As in our basic set up this cost factor induces partitioning of the population of firms participating in this market into the groups:
$N=\cup_{k=1}^{K_0} N_{k}$ with $N_{k}=\{i:\,q_i=\bar{q}_k\}$ and so that $\tau(i)=k$ if and only if $i\in N_{k}$.
Following the convention in the empirical auction literature, we assume that each project $\ell$ auctioned in this market is summarized by a set of observable characteristics $X_{\ell}$ and an unobservable factor $U_{\ell}$. The latter is distributed according to normal distribution with mean zero and standard deviation $\sigma _{U}$. The set of firms which are potentially interested in project $\ell$ (potential bidders), denoted here by $S_\ell$, is exogenously drawn from $N$. A contractor $i$ that is a potential bidder for project $\ell$ is characterized by private entry costs, $E_{i,\ell}$, and the private cost of completing the
project, $C_{i,\ell}$. We assume that private costs vary independently across
bidders and auctions. The entry costs additionally are independent of $U_\ell$, and are distributed according to the exponential
distribution with a rate parameter $\lambda_{i,\ell}$. The costs of
completing the work are drawn from a log normal distribution with mean $\mu_{i,\ell}$ and standard deviation $\sigma _{C}$. The mean of the cost distribution depends on project characteristics including the distance between the project and the bidder's locations, $D_{i,\ell}$, as well as an unobserved cost factor $q_{i}$.\footnote{The groups reflect differences in the contractors' cost efficiencies related to the project work. While entry costs may also vary across groups, there is no reason for the group differences in project costs to coincide with the group differences in entry costs. For this reason, we explicitly distinguish between the parameters capturing the former ($\bar{q}_k$) and the latter ($\tilde{q}_k$) effects.}$^{,}$\footnote{
Following the literature, we distinguish between the bidders who regularly participate in the procurement market (regular bidders) and those who only appear in a very
small number of auctions (fringe bidders). We assume that all fringe bidders
are associated with the same fixed level of the unobserved cost factor $\bar{q}_{0}$.} Reflecting these features, we set
\begin{eqnarray*}
\mu_{i,\ell}=X_{\ell}\alpha_1 +D_{i,\ell}\alpha_2 +\sum_{k=1}^{K_0}\bar{q}_{k}1\{\tau(i)=k\}+U_{\ell}, \text{ and }
\lambda_{i,\ell} = X_{\ell}\gamma_1+\sum_{k=1}^{K}\tilde{q}_{k}1\{\tau(i)=k\}.
\end{eqnarray*}
A potential bidder decides to participate in the auction for project $\ell$ if his ex-ante expected profit conditional on participation exceeds entry costs.\footnote{The expected profit reflects his expectation over the participation decisions of other potential bidders, the expectation over his costs of completing the project, and reflects expected probability of winning the project which depends on the costs draws of his competitors.} The set of such bidders is denoted by $A_\ell$. A bidder who decides to participate observes realization of his costs and the identities of other contractors who decided to participate. He chooses a bid to maximize his interium profit which reflects the probability of winning the project conditional on his costs and the set of competitors.
We assume that the observed outcomes reflect a type-symmetric pure-strategy Bayesian Nash
equilibrium (psBNE).\footnote{In such an equilibrium, participants who are \textit{ex ante} identical in an auction $\ell$ (i.e. $i,j\in S_{\ell}$ such that $q_{i}=q_{j},$ and $D_{i,\ell}=D_{j,\ell}$) adopt the same strategies.}
\paragraph{\textbf{Estimation Details.}}
The estimation methodology consists of two steps. In the first step we use the pairwise comparison indexes to recover the unobserved group structure. In the second step the parameters of the model are estimated through a GMM procedure while imposing the group structure recovered in the first step. We assume bids are rationalized by a single equilibrium.
In the first step we use the pairwise comparison indexes derived in Appendix B.1 in the supplemental note to recover the unobserved group structure.\footnote{The pairwise comparison indexes are derived using Corollary 3 of Lebrun1999 which for $G_{ij}(b)$ defined as $P\{B_{i,\ell}\geq b|\,i,j\in S_\ell\}$ establishes that $G_{ij}(b)\leq G_{ji}(b)$ for all $b$ in the common support of $B_{i,\ell}$ and $B_{j,\ell}$ whenever $ \tau(i)\leq \tau(j)$. The inequality holds strictly at least over some interval with positive Lebesgue measure and holds unconditionally when aggregated over bidder identities and auction characteristics.} Specifically, in accordance with the notation used in the paper, we define $\delta_{ij}\equiv \int \max \left\{r_{ij}(b),0\right\}db$ and $\delta _{ij}^{0}\equiv \int |r_{ij}(b)|db$ with
$r_{ij}(b)=G_{ji}(b|\,d)-G_{ij}(b|d)$ and $G_{ij}(b|d)=P\{B_{i,\ell}\geq b|\,D_{i,\ell}=d,\,D_{j,\ell}=d,\,i\in A_\ell,\,j\in A_\ell\}$.\footnote{We recover group structure on the basis of the indexes which aggregate over the values of the distance $d$. As a robustness check we also compute groupings on the basis of subsets of distances. We find that the results of classification are very similar across these approaches.}
We obtain empirical counterparts of these indexes by replacing $G_{ij}(b|d)$ with its sample analog $\hat{G}_{ij}(b|d)$.
We implement classification using the bootstrap testing procedure described previously.
In the second stage, we consider the following moments: (a) the first and the second moment of bid distribution for a given level of $d$ and for a given group of bidders; (b) the
covariance between bids and the observable project characteristics; (c) the
covariance between any two bids submitted in the same auction; (d) the
expected number of participants in any given auction for every $(d,\,q)$-group; (e) the covariance between the number of participants and the observable project characteristics. We search for the set of parameters which minimizes the distance between the empirical and theoretical counterparts of these moments subject to participation constraints.\footnote{We do not explicitly solve for participation strategies. Instead, we discretize the support of auction characteristics $(X_\ell,U_\ell)$ and treat the probabilities of participation for bidders of various $(q,d)-$types corresponding to these grid values as auxiliary parameters. We follow the spirit of DubeFoxSu2012 by maximizing a moment-based objective function subject to the constraints that the optimality of the participation strategies is satisfied on the grid of the project characteristics' values.}
\paragraph{\textbf{Estimation Results.}}
We implement the analysis using the data for California Highway Procurement
projects auctioned between 2002 and 2012. The projects in our sample are worth
\$523,000 and last for around three months on average; 38% of these projects are partially supported through federal funds. There are 25 firms that participate regularly in this market. The other firms are referred to as “fringes". An average auction attracts six regular potential
bidders and eight fringe bidders. Since only a fraction of potential bidders
submits bids, an entry decision plays an important role in this market.
Finally, the distance to the company location varies quite a bit and is
around 28 miles on average for regular potential bidders.
In the first step, we obtain through our classification method the grouping of the bidders into eight groups that consist of 2, 3, 8, 3, 2, 3, 2 and 2 bidders respectively.
The parameter estimates obtained in the second stage of our estimation procedure and their standard errors are summarized in Table 6. We normalize bids by the engineer's estimate in the estimation. Therefore all the parameters measure
the effects relative to the project size.
\begin{table}[!t]
\begin{center}
Table 6. Parameter Estimates
\begin{tabular}{cc|cc|cc|cc}
\hline\hline
& & Estimate & Std. Error & Estimate & Std. Error & P-value&\\ \hline
\multicolumn{7}{l}{The Distribution of Project Costs} \\
& Constant ($\bar{q}_0$) & 0.127$^{\ast \ast \ast }$ & (0.0129) & 0.113$^{\ast \ast \ast }$ & (0.0119) & 0.216 & \\
& Eng. Estimate & -0.0004$^{\ast \ast \ast }$ & (0.0002) & -0.0005$^{\ast \ast \ast }$ & (0.0002) & 0.392&\\
& Duration & 0.00026$^*$ & (0.00036) & 0.00022$^{\ast }$ & (0.00027) & 0.212&\\
& Distance & 0.0012$^{\ast \ast \ast }$ & (0.00022) & 0.00086$^{\ast \ast \ast }$ & (0.00019) & 0.041&\\
& Bridge & -0.0092$^{\ast \ast \ast }$ & (0.0018) & -0.012$^{\ast \ast \ast }$ & (0.0011) & 0.074&\\
& Federal Aid & -0.043$^{\ast \ast \ast }$ & (0.0103) & -0.078$^{\ast \ast \ast }$ & (0.009) & 0.012 &\\
& Regular Bidder& & & -0.035$^{\ast \ast \ast }$ & (0.003) & &\\
& $\sigma _{C}$ & 0.087$^{\ast \ast \ast }$ & (0.032) & 0.112$^{\ast \ast \ast }$ & (0.022) & 0.087&\\
& $\sigma _{U}$ & 0.021$^{\ast \ast \ast }$ & (0.009) & 0.0207$^{\ast \ast \ast }$ & (0.008) & 0.452&\\\hline
\multicolumn{7}{l}{The Distribution of Entry Costs} \\
& Constant ($\tilde{q}_0$) & -0.0114$^{\ast }$ & (0.0078) & -0.0161$^{\ast }$ & (0.0091) & 0.212 & \\
& Eng. Estimate & 0.0055$^{\ast \ast \ast }$& (0.0016) & 0.0051$^{\ast \ast \ast }$ & (0.0012) & 0.333 & \\
& Number of Items & 0.0018$^{\ast }$ & (0.0011) & 0.0011$^{\ast \ast \ast }$ & (0.0005) & 0.082 & \\
& Regular Bidder & & & -0.022 $^{\ast \ast \ast }$ & (0.004) & \\
\hline\hline
\end{tabular}
\end{center}
\begin{flushleft}
{ Note: In the results above the distance is measured in miles. The fringe bidders are the reference group. The results are based on the data for 1,054 medium-sized projects that involve paving and bridge work. Standard errors are computed using bootstrap. The first two columns correspond to the specification which allows for the unobserved bidder heterogeneity; the next two columns correspond to the specification without unobserved bidder heterogeneity. The last column reports the p-value of the bootstrap-based test of the equality of coefficients estimated under the specifications with and without unobserved bidder heterogeneity. Details of the test can be found in the Supplemental Note to the paper. }
\end{flushleft}
\end{table}
The first two columns present the estimates which are obtained when the unobserved group structure is taken into account in the estimation. The results indicate significant differences in bidders' costs across the
groups. Specifically, fringe bidders (the reference group) tend to have the highest
costs whereas the difference in costs between the group of fringe bidders and the groups of regular bidders is comparable in impact to the shortening of the distance to the project site by 42.5 (i.e., by 0.051/0.0012), 10.1, 26.67, 48.33, 11.67, 6.67, 7.5, and 41.67 miles respectively.\footnote{The estimates of the group-specific fixed effects are omitted for brevity. The full table that contains these estimates is found in the supplemental note to the paper.}
The distance increases project costs (additional 8.33 miles result in costs which are 1% higher on average).\footnote{Recall that the coefficients reflect the impact on costs in terms of the fraction of the engineer's estimate. The distance resulting in 0.01 increase of average costs can thus be computed as 0.01/0.012. } The entry costs of regular bidders are significantly lower than entry costs of fringe bidders. However, they appear to be quite similar across the groups of regular bidders.
The next two columns of Table 6 show the parameter estimates under the specification when the unobserved group structure of the regular bidders is ignored in the estimation. The parameter estimates are obtained by the GMM estimation procedure using the same set of moments by imposing that only two groups of sellers are present in the data: fringe and regular bidders. Under this specification, the cost reduction due to the federal aid is estimated to be much higher (7.8% rather than 4.3%), the impact of the distance is estimated to be lower (the distance to the project has to be 11.67 miles higher in order to increase the average cost by 1%). Additionally, the entry costs are estimated to be lower relative to the baseline specification.
The last column reports the results of the bootstrap-based test of the equality of coefficients estimated under the specifications with and without unobserved bidder heterogeneity. The results indicate that the difference is significant for the mean parameters in front of the distance, the indicator for the federal aid, the indicator that a project entails bridge-related work, and the standard deviation for the distribution of project costs. The effect of the number of items on the distribution of entry costs is also significant. Our results thus confirm that regular participants in the highway procurement market are characterized by important unobserved cost differences that persist in the data.
\@startsection{section}{1}
\z@{0.7\linespacing}{.7\linespacing}{Conclusion}
This paper makes a number of contributions to the literature. First, for models with strategic interdependence between multiple agents, we develop a method to classify these agents based on their discrete unobserved individual heterogeneity, using pairwise inequalities implied by an economic model. Second, we show such pairwise inequalities arise in a number of game-theoretical settings where identification of model primitives is challenging. Third, we propose a computationally feasible method which consistently estimates the group structure defined by unobserved heterogeneity.
We apply this method to California highway procurement data to show that unobserved bidder heterogeneity plays an important role in this procurement market.
The classification method proposed in this paper is especially useful in settings where the analysis of unobserved individual heterogeneity is complicated by the presence of strategic interdependence in the model. We offer new insights into the identification and estimation of such models.
Specifically, classification could be used as a first step in the structural studies of many environments where analyses would otherwise be infeasible due to the identification or computational challenges.
\@startsection{section}{1}
\z@{0.7\linespacing}{.7\linespacing}{Appendix: Mathematical Proofs}
\textbf{Proof of Theorem (ref)}: Sufficiency is obvious. We focus on necessity. Let us assume that $\tau$ is identified. First consider the two facts:
Fact 1: If $G_{\tau}$ does not contain a monotone path of length $K_0-1$, $\tau$ is not identified.
Fact 2: A vertex $i$ is identified if and only if there is a monotone path $P$ containing $i$ such that its end vertices $i_H$ and $i_L$ are identified and
\begin{eqnarray*}
\tau(i_H) - \tau(i_L) = \ell(P),
\end{eqnarray*}
where $\ell(P)$ denotes the length of $P$.
By Fact 1, the necessity of $G_{\tau}$ containing a monotone path of length $K_0-1$ follows, and Fact 2 completes the proof of the necessity part of the theorem.
Now let us prove Fact 1. Suppose that $G_{\tau}$ does not contain a monotone path of length $K_0-1$. Let $N_{max}$ be the set of vertices such that for each vertex $i$ in $N_{max}$, all his $G_{\tau}$-neighbors have lower type than the vertex $i$. Then there is no edge in $G_{\tau}$ which joins any two vertices from the set $N_{max}$. Choose a vertex $i^*$ from $N_{max}$ which is an end vertex of a longest monotone path, say, with length $K-1 < K_0-1$. This identifies a lower bound for $K_0$ but there is no upper bound for $K_0$ that we can obtain from $G_{\tau}$. Take any $\tau'$ such that $\tau'(i^*) > \tau(i^*)$ and $\tau'(i) = \tau(i)$ for all $i \in N\setminus\{i^*\}$. Then $\tau'$ is compatible with $G_{\tau}$ and the given comparison indexes, proving that $\tau$ is not identified from $G$ and the comparison indexes.
Let us prove Fact 2. Sufficiency is trivial. Let us focus on necessity.
First, suppose to the contrary that there is no monotone path with identified end vertices which contains $ i $. Then obviously $ i $ is not identified. Therefore, if $i$ is identified, there exists a monotone path with identified end vertices which contains $i$. So it suffices to show that if $i$ is identified, it is necessary that such a monotone path has to have length equal to $ \tau(i_H) - \tau(i_L)$.
Suppose to the contrary that the following condition holds.
Condition A: Every monotone path $P$ that contains $i$ and has identified end vertices $i_H$ and $i_L$ also satisfies $\tau(i_H) - \tau(i_L) > \ell(P)$. Then we will show that $i$ is not identified.
First, assume that there exists a monotone path which contains $i$ but not as one of its end vertices. Let $i_H^*$ be a lowest type vertex among all the identified vertices each of which is on a monotone path that contains $i$ and is of higher type than $i$. Also, let $i_L^*$ be a highest type vertex among all the identified vertices each of which is on a monotone path that contains $i$ and is of lower type than $i$. Let $P$ be a monotone path between $i_H^*$ and $i_L^*$ that passes through $i$. Then by construction, the type difference $\tau(i_H^*) - \tau(i_L^*)$ between the two end vertices is smallest among all the monotone paths that go through $i$. Furthermore, $i_H^*$ and $i_L^*$ are adjacent to $i$ in $G_\tau$. By Condition A, we have $\tau(i_H^*) - \tau(i_L^*) > 2$.
Therefore, we have multiple different ways to assign $\tau(i_H^*)-1,\tau(i_H^*)-2,...,\tau(i_L^*)+1$ to the vertex $ i $ on the path $P$.
Hence $i$ is not identified.
Second, assume that all the monotone paths that contain $i$ have $i$ as one of their end vertices. Then either all neighbors of $i$ are of higher type than $i$ or all neighbors of $i$ are of lower type than $i$. Suppose that we are in the former case. (The latter case can be dealt with similarly.) Let $i_H^*$ be a lowest type vertex among all the vertices each of which is on a monotone path that contains $i$ and is of higher type than $i$. Then $i_H^*$ is adjacent to $i$ in $G_\tau$, and by Condition A, $\tau(i_H^*) - \tau(i) > 1$.
Thus we have multiple different ways to assign $\tau(i_H^*)-1,\tau(i_H^*)-2,...,\tau(i)+1,\tau(i)$ to the vertex $i$. Hence $ i $ is not identified. $\blacksquare$
\textbf{Proof of Lemma (ref)} Conditions (i) and (v) of Assumption (ref) follow from Condition (i) of Assumption (ref) with $W_{ij}^s$ being a standard normal random variable, and $\rho_L = L^{-\alpha}$. As for Conditions (ii)-(iv) of Assumption (ref), we focus on only (ii), because the proof for the other two statements is similar. Observe that when $\tau(i) > \tau(j)$, so that
\begin{align}
\tilde T_{ij}^+/\sqrt{L} &= (\sigma_{ij,L}^+)^{-1}\left( \int \max\{\hat r_{ij}(x) - r_{ij}(x) + r_{ij}(x),0\}dx - L^{-1/2} h^{-d/2} a_{ij,L}^+\right)\\ \notag
&= (\sigma_{ij}^+)^{-1} \int \max\{r_{ij}(x),0\}dx + o_P(1),
\end{align}
by Assumption (ref) (ii)(iii) and Condition ((ref)). Hence Assumption (ref)(ii) follows with
\begin{eqnarray*}
c_{ij}^+ = (\sigma_{ij}^+)^{-1} \int \max\{r_{ij}(x),0\}dx,
\end{eqnarray*}
and $\lambda_L = \sqrt{L}$.
As for Condition (vi) of Assumption (ref), note that $F_{ij,\infty}^s = \Phi$, the standard normal CDF. Hence there exists $C>0$ such that for all $t > C$,
\begin{eqnarray*}
1 - \Phi(t) \le C \exp\left( -\frac{C t^2}{2}\right).
\end{eqnarray*}
Therefore, for any constants $c_1,c_2>0$, taking $\lambda_L = \sqrt{L}$ and $\rho_L = L^{-\alpha}$, (from some large $L$ on)
\begin{eqnarray*}
r_L^{-1}\log \left(1 - \Phi(c_1\sqrt{L}) + c_2 L^{-\alpha} \right) \le r_L^{-1} \log\left(C \exp(-C c_1^2L/2) + c_2 L^{-\alpha}\right) \rightarrow - \infty,
\end{eqnarray*}
as $L\rightarrow \infty$, by the condition that $r_L /\log L \rightarrow 0$. $\blacksquare$
\putbib[refs_comp]