From this, we can compute the likelihood of the full observed network, represented by the adjacency matrix $\mathbf{A}$. However, it is inmportant to note that the product below is only over pairs of nodes that belong to opposite categories. That is, if $i$ indexes workers and $j$ indexes jobs, we are only taking the product over $i,j$ pairs, not $i,i'$ or $j,j'$ pairs. Again, this is because in a bipartite network, edges can only connect nodes that belong to different categories.

\begin{align}
P(\mathbf{A}|\vec{d}, \mathbf{\Omega}, \vec{g}) = \prod_{i < j} \frac{(d_id_j\omega_{g_ig_j})^{A_{ij}}}{A_{ij}!} \exp \left( -d_id_j\omega_{g_ig_j}\right).
\end{align}

Notice that this expression lacks the second term found in equation (<ref>), which captures self-edges in which an edge runs connects a node to itself. This is because self-edges are impossible in a bipartite network, since self-edges would connect nodes belonging to the same category (e.g. workers to workers).

§.§ Visual representation of linked employer-employee data as a network

Our raw data looks like what is presented in Table <ref>, with the exception that we generate the “JobID” column ourselves by concatenating the establishment code (`Estab Code') and occupation code (`Occ Code'). However, we only use the two variables `WorkerID' and `JobID' in estimation. Therefore, in Figure <ref>, we show the worker and job IDs from the data alongside a network representation of the same data. In the network representation, workers are blue dots on the right, jobs are yellow dots on the left, and black lines represent edges connecting workers to jobs at which they were employed. Finally, in Table <ref>, we present an adjacency matrix representation of the same network.

Sample linked-employer-employee data

WorkerID	    Establishment	    Occupation	    Estab Code	    Occ Code	    JobID

1	    Walmart	    Cashier	    1	    1	    1_1

2	    Walmart	    Cashier	    1	    1	    1_1

2	    Kroger	    Cashier	    2	    1	    2_1

3	    Walmart	    Cashier	    1	    1	    1_1

3	    Walmart	    Greeter	    1	    2	    1_2

4	    Walmart	    Greeter	    1	    2	    1_2

5	    Walmart	    Cashier	    1	    1	    1_1

5	    Kroger	    Cashier	    2	    1	    2_1

6	    Walmart	    Greeter	    1	    2	    1_2

6	    CVS		    Manager	    3	    3	    3_3

6	    Chipotle	    Manager	    4	    3	    4_3

7	    Chipotle	    Manager	    4	    3	    4_3

8	    CVS		    Manager	    3	    3	    3_3

8	    Chipotle	    Manager	    4	    3	    4_3

9	    Chipotle	    Manager	    4	    3	    4_3

9	    Kroger	    Asst. Mgr	    2	    5	    2_5

10	    CVS		    Manager	    3	    3	    3_3

10	    Chipotle	    Manager	    4	    3	    4_3

10	    Chili's	    Waiter	    5	    4	    5_4

10	    Kroger	    Asst. Mgr	    2	    5	    2_5

Representing the data as a network

WorkerID	    JobID

1	    1_1

2	    1_1

2	    2_1

3	    1_1

3	    1_2

4	    1_2

5	    1_1

5	    2_1

6	    1_2

6	    3_3

6	    4_3

7	    4_3

8	    3_3

8	    4_3

9	    4_3

9	    2_5

10	    3_3

10	    4_3

10	    5_4

10	    2_5

Adjacency matrix: $\mathbf{A}$

Worker \Job     1_1     1_2     2_1     2_5     3_3     4_3     5_4

1                             1                 0                 0                 0                 0                 0                 0

2                             1                 0                 1                 0                 0                 0                 0

3                             1                 1                 0                 0                 0                 0                 0

4                             0                 1                 0                 0                 0                 0                 0

5                             1                 0                 1                 0                 0                 0                 0

6                             0                 1                 0                 0                 1                 1                 0

7                             0                 0                 0                 0                 0                 1                 0

8                             0                 0                 0                 0                 1                 1                 0

9                             0                 0                 0                 1                 0                 1                 0

10                            0                 0                 0                 1                 1                 1                 1

§ ESTIMATING LABOR SUPPLY PARAMETERS

This section describes the procedure we use to estimate the labor supply parameters of the model, conditional on the assignments of workers to worker types, $\i(i)$, and jobs to markets, $\g(j)$, described in Section <ref>.

§.§ Estimating $\Psi$ from observed matches

Identification and estimation of the labor supply parameters builds upon  <cit.> and <cit.>, with the key difference being that we assign both workers to worker types and jobs to markets prior to estimating labor supply parameters and do so in a way that more fully exploits the information revealed by worker–job matches, allowing us to identify a significantly greater degree of worker and job heterogeneity.[More precisely, <cit.> model workers matching with firms and therefore use k-means clustering to cluster firms on the basis of the firms' earnings distributions, while <cit.> models workers matching with clusters of occupations identified by combining occupational education requirements with k-means clustering on the basis of occupations' O*NET skills scores. Additionally, neither <cit.> nor <cit.> actually assign workers to types. Instead,  they employ random effects estimators, in which they identify the distribution of types, rather than assigning any individual worker to a type. As a result, both papers require that flows of worker types between firm/occupation groups form a strongly connected graph (they use the term “connecting cycle”). This is a strong data requirement and requires them to define worker and firm/occupation groups at a relatively aggregated level, ignoring considerable heterogeneity. By using the network structure of the data to assign workers and jobs to types in a previous step before estimating labor supply parameters, we are able to identify an order of magnitude more worker types and markets, and therefore to allow for much greater heterogeneity.]

We estimate parameters using a maximum likelihood approach. We assume that individual workers' earnings in period $t$ are observed with multiplicative measurement error $e_{it}$, which has a worker type–market-specific parametric distribution $f_e(e_{it} | \i(i), \g_{it}, \theta_e)$ with unit mean, summarized by parameter vector $\theta_e$. Observed earnings $\omega_{it}$ are therefore

\begin{align}
\omega_{it} = \psi_{\i(i)\g_{it}} w_{\g_{it}} e_{it}. \label{eq:observed_wages}
\end{align}

Finally, we assume that the earnings measurement errors are serially independent:
[Serial independence of earnings measurement error]

The realization of period $t$'s measurement error for worker $i$, $e_{it}$ is independent of the history of errors $\{e_{it'}\}_{t'=1}^{t-1}$, market choices $\{\g_{it'}\}_{t'=1}^{t-1}$, and separations $\{c_{it'}\}_{t'=1}^{t-1}$, conditional on the worker's type, $\i_i$, and current market choice $\g_{it}$.

Our model is identified by combining assumption <ref> with assumptions <ref> and <ref>, which stated that the market preference parameters $\ve_{i\g t}$ and exogenous separation shocks $c_{it}$ are each serially uncorrelated and independent of all other variables in the model.

Conditional on clustering workers and jobs into types, our data consist of three elements per worker per period: the worker's market choice, $\gamma_{it}$, the worker's earnings, $\omega_{it}$, and the indicator for whether or not the worker changed jobs, $c_{it}$. Observed data are denoted by $\mathbb{X} := \left\{ \gamma_{it},\omega_{it},c_{i t} | t = 1, \ldots, T; i = 1, \ldots, N \right\}$. The parameters are denoted by $\Theta := \left\{ \psi_{\ig}w_\g, \xi_{\g}, \nu, \theta_e | \i = 1,\ldots, I; \g = 1, \ldots, \Gamma  \right\}$. Recall that $\P[\g_{it}|\Theta]$ is the probability of worker $i$ choosing a job in market $\g$ and comes from the Roy model (equation <ref>). Meanwhile, let $f_{\omega}(\omega| \i(i), \g_{it}, \Theta)$ denote the density of observed earnings in period $t$. We construct our likelihood as follows.

In periods in which workers experience a separation, three pieces of data are generated: a separation indicator $c_{it}$, the worker's new market choice $\g_{it}$, and the worker's earnings $\omega_{it}$. We assume that all workers separate and rematch in the first period for which we have data: $c_{i1}=1$ for all $i$. In periods in which the worker does not separate from their job, we observe only $c_{it}$ and  $\omega_{it}$.[By only including the worker's market choice in the likelihood in periods in which a separation has occurred, but assuming that all workers separated in period $t=1$, we are ensuring that each match enters the likelihood exactly once. This gives all matches equal weight in the likelihood, regardless of match duration. Alternatively, we could have omitted exogenous separations from the model and assumed that workers make a new choice every period. Under this assumption, persistent matches would indicate that the worker has made the same choice repeatedly and we would put greater weight on persistent matches in estimation.]  Assumptions <ref> and <ref> tell us that realizations of $\omega_{it}$ and $c_{it}$ are independent, and $\g_{it}$ is independent of $\omega_{it}$ conditional on $c_{it}$. Therefore, we write the likelihood of observing $\{\g_{it},\omega_{it}, c_{it}\}$ for an individual worker in period $t$ as

\begin{align*}
l(\g_{it},\omega_{it}, c_{it}|\mathbb{X}) &= \underset{\text{Separation}}{\underbrace{\left[ f_{\omega}(\omega_{it}|\Theta) \P(\g_{it}|\Theta) \right] }}^{c_{it}}\underset{\text{No separation}}{\underbrace{\left[ f_{\omega}(\omega_{it}|\i(i), \g_{it},\Theta)\right]}}^{1-c_{it}}
\end{align*}

Our assumptions that $\{\g_{it},\omega_{it}, c_{it}\}$ are serially uncorrelated and independent across workers, conditional on the parameters of the data, allow us to write the full likelihood of the data as the product of the individual worker-time likelihoods:

\begin{align}
\mathcal{L}(\Theta | \mathbb{X}) 	&=  \prod_{i = 1}^N  \prod_{t=1}^{T} l(\g_{it},\omega_{it}, c_{it}|\mathbb{X}) \nonumber \\
&= \prod_{i = 1}^N  \prod_{t=1}^{T} \underset{\text{Separation}}{\underbrace{\left[ \P(\g_{it}|\Theta)f_{\omega}(\omega_{it}|\i(i), \g_{it},\Theta) \right] }}^{c_{it}}\underset{\text{No separation}}{\underbrace{\left[ f_{\omega}(\omega_{it}|\i(i), \g_{it},\Theta)\right]}}^{1-c_{it}}
\end{align}

Finally, the log-likelihood is

\begin{align}
\ell(\Theta | \mathbb{X}) 	&=  \sum_{i=1}^{N}\sum_{t = 1}^T c_{it} \log \P(\g_{it}|\Theta) + \sum_{i=1}^{N}\sum_{t = 1}^T \log f_{\omega}(\omega_{it}|\i(i), \g_{it}, \Theta) \label{eq:log_likelihood}
\end{align}

In order to maximize this likelihood function, we impose a distributional assumption and a normalization:

[Distribution of measurement error in wages]

$e_{it}$ has a log-normal distribution: $\ln e_{it} \sim \N(0,\sigma_{\ig})$.

[$\Psi$ normalization]

The mean productivity level in each market $\g$ is normalized to a constant, $k$:

\[\sum_{\i} m_{\i} \psi_{\ig} = k \quad \forall \g\]

where $m_{\i}$ is the mass of type $\i$ workers.

Assumption <ref> assumes that wages follow a log-normal distribution which is worker type-market specific, following <cit.> and <cit.>. Assumption <ref> normalizes the $\psi_{\ig}$ to have a mean equal to some constant $k$ within market.

Identification of $\Psi$ comes from two sources: earnings for all employed workers, and market choices for all workers in period $t=1$ and workers who receive exogenous separation shocks in periods $t>1$. Intuitively, ($\i,\g$) matches that pay more and occur more frequently are revealed to be more productive. The relative weight of earnings and market choices is determined by the inverse of the variances of measurement error in wages and idiosyncratic shocks — if the earnings measurement error $\sigma_{\ig}$ for a worker type–market pair has a relatively high variance, then estimation puts more weight on choices; if the idiosyncratic preference shocks have a relatively high variance (large $\nu$), estimation puts more weight on earnings. The normalization that the mean skill level in each market equals $k$ (Assumption <ref>) converts the distribution of relative skills into a distribution of skill levels. We choose $k$ to maximize the model's ability to match the observed employment rate.[This normalization is mostly without loss of generality. If one were to double the number of efficiency units of labor each worker supplied to a market, the equilibrium price of labor would halve. However, increasing the number of efficiency units of labor in the economy will impact the fraction of the labor force in employment versus non-employment. This is why we choose $k$ to maximize the model's ability to match the observed employment rate.]

The parameter governing the variance of non-pecuniary benefits, $\nu$, is identified by workers' choices of markets, $\g$. Workers will choose a market that offers their worker type low expected utility (low $\psi_{\ig} w_{\g} + \xi_{\g}$) when they receive a large preference shock draw for that market. Therefore, if workers frequently choose low expected utility markets, it must be because they frequently draw large preference shocks, indicating that the preference shock distribution has a large dispersion parameter, $\nu$. The market amenities parameter $\xi_{\g}$ is a market fixed effect and is identified by the component of the frequency with which workers choose market $\g$ that is common across all worker types $\i$. The relative value of $\xi_{\g}$ to $\xi_{\g'}$ allows the model to match the fact that some high-earning markets, such as doctors, account for a small share of total employment. This is because  $\xi_{\g}$ reflects not just the immediate utility benefits of working in a job in market $\g$, but also reflects broader compensating differentials. In this way, $\xi_{doctor}$ may be low, not because doctor jobs are unpleasant, but because the annualized cost of becoming a doctor — including medical school — and maintaining the requisite skills is high. We provide greater detail on identification in appendix <ref>.

§.§ Additional parameters to be estimated or calibrated

We also have the following parameters to estimate or calibrate:

* $\beta_{\g s}$ (output elasticity of labor in market $\g$) —  We calibrate these parameters as the share of the sector $S$ wage bill paid to workers employed in market $\g$ jobs.

* $\eta$ (CES consumption substitution elasticity)— We calibrate this parameter to 2.[<cit.> estimate this parameter to be 4, however their estimate comes from significantly more disaggregated product categories, so we choose a smaller value. This parameter affects our structural results in Section <ref>, but does not affect the reduced form estimates in Section <ref>.]

* $a_s$ (demand shifters) — We calibrate demand shifters to match actual sector output shares, given sector-level prices, for the state of Rio de Janeiro as measured by the Brazilian Institute of Geography and Statistics (IBGE).

§ MODEL SOLUTION APPENDIX

Firm's problem

This section describes a slightly different version of the firm's problem than we presented in the body of the paper. In the body of the paper we had a set of competitive firms in each sector, whereas in what follows here we have a single representative firm in each sector.

\begin{align}
\max_{\ell_{\g s}} \quad p_s \prod_{\g} \ell_{\g s}^{\beta_{\g s}} - \sum_{\g} w_{\g} \ell_{\g s}
\end{align}

There are $S$ optimizations with $\Gamma$ choice variables each, giving us $S \times \Gamma$ FOCs.

\begin{align}
\ell_{\g s}^D = \frac{p_s \beta_{\g s}\left( \prod_{\g'} {\ell_{\g' s}^D}^{\beta_{\g' s}}\right)}{w_{\g}} \label{eq:firm_FOC}
\end{align}

Combining the $\Gamma$ FOCs for a given sector $S$:

\begin{align}
\ell_{\g s}^D = \frac{\beta_{\g s}}{\beta_{\g' s}}\frac{w_{\g'}}{w_{\g}} \ell_{\g's}^D \label{eq:firm_FOC_ratio}
\end{align}

Plugging in <ref> for $\ell_{\g s}^D$ in equation <ref>, we have

\begin{align}
\ell_{\g s}^D = \left[ p_s \left( \frac{\beta_{\g s}}{w_{\g }} \right)^{1-\sum_{\g'} \beta_{\g' s}} \prod_{\g'} \left(\frac{\beta_{\g' s}}{w_{\g'}} \right)^{\beta_{\g' s}} \right]^{\frac{1}{1-\sum_{\g'} \beta_{\g' s}}} = \ell_{\g s}^D \left(\vec{p}, \vec{w} \right) \label{eq:labor_demand}
\end{align}

which represents labor demand for firm $s$, using only FOCs for firm $s$.[We could alternatively write this expression as

\begin{align*}
\ell_{\g s}^D =   \left( \frac{\beta_{\g s}}{w_{\g }} \right) \left[ p_s \prod_{\g'}  \left(\frac{\beta_{\g' s}}{w_{\g'}} \right)^{\beta_{\g' s}} \right]^{\frac{1}{1-\sum_{\g'} \beta_{\g' s}}}
\end{align*}

Since labor is the only factor of production, we can write firm $s$'s product market supply as

\begin{align}
y_s^S = y_s^S\left( \{\ell_{\g s}^D (\vec{p}, \vec{w}) \}_{\g=1}^{\Gamma} \right) = \prod_{\g} {\ell_{\g s}^D}^{\beta_{\g s}} \label{eq:product_supply}
\end{align}

Household's problem

\begin{align*}
\max_{\{y_s^D\}_{s=1}^S} \quad \underset{U(\{y_s^D\}_{s=1}^S)}{\underbrace{ \left(\sum_s a_s^{\frac{1}{\eta}} {y_s^D}^{\frac{\eta-1}{\eta}}\right)^{\frac{\eta}{\eta-1}} }} \quad \text{s.t.} \quad \sum_s p_s y_s \leq Y
\end{align*}

\begin{align*}
\underset{U(\vec{y}^D)}{\underbrace{ \left(\sum_s a_s^{\frac{1}{\eta}} {y_s^D}^{\frac{\eta-1}{\eta}}\right)^{\frac{\eta}{\eta-1}} }} - \lambda \left(  \sum_s p_s y_s - Y \right)
\end{align*}

\begin{align*}
\frac{\eta}{\eta-1} U^{\frac{1}{\eta}} \frac{\eta-1}{\eta} a_s^{\frac{1}{\eta}} {y_s^D}^{-\frac{1}{\eta}} - \lambda p_s = 0
\end{align*}

\begin{align*}
U^{\frac{1}{\eta}} a_s^{\frac{1}{\eta}}  {y_s^D}^{-\frac{1}{\eta}} - \lambda p_s = 0
\end{align*}

\begin{align}
y_s^D = \frac{U}{\lambda^{\eta}} \frac{a_s}{p_s^{\eta}} \label{eq:hh_FOC}
\end{align}

Next, we plug this into the constraint satisfied with equality ($\sum_s p_s y_s^D = Y $):

\begin{align*}
&\frac{U}{\lambda^{\eta}} \sum_s \left( a_s p_s^{1-\eta} \right) = Y \\
\Rightarrow & \lambda^{\eta} = \frac{U}{Y} \sum_{s'} \left( a_s' p_s'^{1-\eta} \right)
\end{align*}

Plugging this into <ref>, we have our expression for product demand:

\begin{align}
y_s^D = \frac{ a_s Y}{p_s^{\eta} \sum_{s'} \left(a_{s'} p_{s'}^{1-\eta}\right)} = y_s^D(\vec{p},Y) \label{eq:product_demand}
\end{align}

Worker's problem

\begin{align*}
\max_{\g} \quad w_{\g} \psi_{\ig} + \xi_{\g} + \ve_{i\g}, \quad \ve_{i\g} \sim T1EV(\theta)
\end{align*}

Solving the worker's problem gives labor supply:

\begin{align}
\ell_{\g}^S(\vec{w})  = \sum_{\i} m_{\i} \left( \frac{\exp \left( \frac{\psi_{\ig} w_{\g} + \xi_{\g}}{\nu} \right) }{ \sum\limits_{\g'=0}^{\Gamma} \exp \left( \frac{\psi_{\ig'} w_{\g'} + \xi_{\g'}}{\nu} \right) } \right) \psi_{\ig} \label{eq:labor_supply}
\end{align}

Equilibrium wages $\vec{w}_{\Gamma \times 1}$ and prices $\vec{p}_{S \times 1}$ must satisfy three market clearing conditions:

* Labor market:

\begin{align*}
\sum_s \ell_{\g s}^D = \ell_{g}^S \quad \forall \g\in\{1,\dots,\Gamma\}
\end{align*}

* Product market:

\begin{align*}
y_s^D = y_s^S  \quad \forall s \in \{1,\dots,S \}
\end{align*}

* Spending = Income = Wages + Profits

\begin{align*}
Y \equiv  \sum_s p_s y_s^D = W + \Pi \equiv \sum_s p_s y_s^S
\end{align*}

* Product demand:

\[ y_s^D = \frac{ a_s Y}{p_s^{\eta} \sum_{s'} \left(a_{s'} p_{s'}^{1-\eta}\right)} \]

* Product supply:

\[ y_s^S = \prod_{\g} {\ell_{\g s}^D}^{\beta_{\g s}} \]

* Labor supply:

\[ \ell_{\g}^S(\vec{w})  = \sum_{\i} m_{\i} \left( \frac{\exp \left( \frac{\psi_{\ig} w_{\g} + \xi_{\g}}{\nu} \right) }{ \sum\limits_{\g'=0}^{\Gamma} \exp \left( \frac{\psi_{\ig'} w_{\g'} + \xi_{\g'}}{\nu} \right) } \right) \psi_{\ig}  \]

* Labor demand:

\[ \ell_{\g s}^D = \left[ p_s \left( \frac{\beta_{\g s}}{w_{\g}} \right)^{1-\sum_{\g'} \beta_{\g' s}} \prod_{\g'} \left(\frac{\beta_{\g' s}}{w_{\g'}} \right)^{\beta_{\g' s}} \right]^{\frac{1}{1-\sum_{\g'} \beta_{\g' s}}} \]

* Budget (which can be plugged in for $Y$ in the product demand equation)

\[ Y = \sum_s p_s y_{\g s}^S \]

This is enough for equilibrium, which we find numerically using fixed point iteration. The algorithm proceeds as follows:

* Choose vectors of start values for wages $\vec{w}$ and prices $\vec{p}$

* Compute labor supply $\ell_{\g}^S(\vec{w})$ given wages $\vec{w}$ following equation <ref>

* Compute labor demand $\ell_{\g s}^D \left(\vec{p}, \vec{w} \right)$ given these start values following equation <ref>

* Compute the product supply $y_s^S\left( \{\ell_{\g s}^D (\vec{p}, \vec{w}) \}_{\g=1}^{\Gamma} \right)$ implied by the labor demand choice in the previous step following equation <ref>

* Compute household income $Y = \sum_s p_s y_{\g s}^S$ implied by product supply in the previous step

* Compute product demand $y_s^D(\vec{p},Y)$ following equation <ref>

* Update prices using the update rule $p_s^{t+1} = p_s^{t} \left(\frac{y_s^D}{y_s^S}\right)^{\rho}$, where $\rho$ is a dampening factor that controls the size of the update and $t$ indexes iterations. Intuitively, we increase prices if demand exceeds supply, and decrease them if supply exceeds demand. The size of the update depends on the size of the mismatch between supply and demand.

* Update wages using the update rule $w_{\g}^{t+1} = w_{\g}^{t} \left(\frac{\ell_{\g}^D}{\ell_{\g}^S}\right)^{\rho}$

* Repeat steps 2-8 until convergence

§ CHOOSING NUMBER OF WORKER TYPES AND MARKETS

Equation <ref> defined the probability of observing our network of worker–job matches, denoted by the adjacency matrix $\mathbf{A}$:

\begin{align}
P \bigg(\mathbf{A} \bigg|\vec{\i}, \vec{\g}, \vec{d_i}, \vec{d_j} , \mathbf{\mathcal{P}} \bigg)
&= \prod_{ i,j } \frac{\left(d_i d_j \mathcal{P}_{\i(i)\g(j)}\right)^{A_{ij}}}{A_{ij}!} \exp \left(d_i d_i^J \mathcal{P}_{\i(i)\g(j)} \right) .
\end{align}

As <cit.> shows, we can think of this in Bayesian terms and write the full joint distribution of the data, $\mathbf{A}$, and the parameters,  $\vec{\i}$, $\vec{\g}$, $\vec{d_i}$, and $\vec{d_j}$ as

\begin{align}
P \bigg(\mathbf{A}, \vec{\i}, \vec{\g}, \vec{d_i}, \vec{d_j} , \mathbf{\mathcal{P}} \bigg) =
P \bigg(\mathbf{A} \bigg|\vec{\i}, \vec{\g}, \vec{d_i}, \vec{d_j} , \mathbf{\mathcal{P}} \bigg)
P \bigg(\vec{d_i}, \vec{d_j}  \bigg|\vec{\i}, \vec{\g}, \mathbf{\mathcal{P}} \bigg)
P \bigg(\mathbf{\mathcal{P}} \bigg|\vec{\i}, \vec{\g} \bigg)
P \bigg(\vec{\i}, \vec{\g} \bigg)    \label{eq:bisbm_bayesian}
\end{align}

where $P \bigg(\vec{d_i}, \vec{d_j}  \bigg|\vec{\i}, \vec{\g}, \mathbf{\mathcal{P}} \bigg) $, $P \bigg(\mathbf{\mathcal{P}} \bigg|\vec{\i}, \vec{\g} \bigg)$, and $P \bigg(\vec{\i}, \vec{\g} \bigg) $ are prior probabilities.

It turns out that this Bayesian formulation has an equivalent information-theoretic interpretation. We can rewrite the joint probability defined in equation (<ref>) as

\begin{align*}
P \bigg(\mathbf{A}, \vec{\i}, \vec{\g}, \vec{d_i}, \vec{d_j} , \mathbf{\mathcal{P}} \bigg) = 2^{-\Sigma}
\end{align*}

\begin{align*}
\Sigma =-\log_2 P \bigg(\mathbf{A}, \vec{\i}, \vec{\g}, \vec{d_i}, \vec{d_j} , \mathbf{\mathcal{P}} \bigg) = \mathcal{S} + \mathcal{L}
\end{align*}

is called the description length of the data and represents the number of bits necessary to encode the data.

\begin{align*}
\mathcal{S} = - \log_2 P \bigg(\mathbf{A} \bigg|\vec{\i}, \vec{\g}, \vec{d_i}, \vec{d_j} , \mathbf{\mathcal{P}} \bigg)
\end{align*}

represents the number of bits necessary to encode the model, conditional on knowing the model parameters, and

\begin{align*}
\mathcal{L} = - \log_2 P \bigg(\vec{\i}, \vec{\g}, \vec{d_i}, \vec{d_j} , \mathbf{\mathcal{P}} \bigg)
\end{align*}

is the number of bits necessary to encode the model parameters.  $\mathcal{S}$ will be small if the model fits the data well, and $\mathcal{L}$ will be small if the complexity of the model (in our case, the number of worker types and markets) is small.  This implicitly defines a trade-off. As we add more worker types and markets, the model fits the data better, reducing  $\mathcal{S}$; however, we are increasing the complexity of the model and thereby increasing $\mathcal{L}$. MDL resolves this trade-off by minimizing  $\mathcal{S}+\mathcal{L}$.

We choose the assignment of workers to worker types and jobs to markets that maximizes the posterior of the distribution, equation (<ref>). This is equivalent to choosing the set of parameters that yields the smallest description length, and therefore compresses the data the most. Intuitively, we can think of $\mathcal{L}$ as a penalty term that increases with the number of parameters, and thereby prevents overly complex models. If the number of worker types and markets becomes large, $\mathcal{S}$ will increase, indicating a better model fit, but the penalty term $\mathcal{L}$ will increase as well. The chosen model will therefore be the one that maximizes the quality of the model fit relative to the cost imposed by the penalty term.

For more detail, see <cit.> and <cit.>.

§ IDENTIFICATION OF LABOR SUPPLY PARAMETERS

Taking  the first order conditions of equation <ref> with respect to each of the parameters provides intuition for how the parameters are identified.

§.§ $\nu$

ℓ_ν= 0    ⇒∑_i=1^N∑_t = 1^T  c_it [ ∑_' ('|Θ)  (ϕ_ı_i' +ξ_')  - (ϕ__it +ξ__it) ] = 0

Intuitively, $\nu$ will be larger if more workers' actual market choices deviate from the choice those workers would have made in the absence of the preference shock $\ve$. The first term in the bracket, $\sum_{\g'} \P(\g'|\Theta)  (\phi_{\i_i\g'} +\xi_{\g'})$ is the expected systematic (excluding the idiosyncratic component, $\ve$) utility of the optimal market choice for worker $i$ and, and the second term, $\phi_{\ig_{it}} +\xi_{\g_{it}}$ is the systematic utility for worker $i$ in the market they actually chose in period $t$. Intuitively, if this difference is large, it must be because some workers received large idiosyncratic preference shocks, $\ve_{i\g t}$, which caused them to accept otherwise suboptimal jobs and is indicative of a large $\nu$. We can also see this by taking limits. If $\nu$ goes to zero, the $\P(\g|\Theta)$ degenerates to a single point and therefore the difference inside the brackets would be zero. On the other hand, as $\nu$ goes to infinity, the market choice probabilities converge to a uniform distribution and the differences between expected and realized systematic utility will be large.

§.§ $\xi_{\g}$

ℓ_ξ_ 	= 0    ⇒∑_i=1^N∑_t = 1^T  c_it  1 { _it = } - ∑_i=1^N∑_t = 1^T  c_it (|ı_i ;Θ) = 0

The above expression chooses $\xi$, which enters the expression through $\P(\g|\i_i;\Theta)$, in order to equate the fraction of job switchers observed to choose market $\g$ with the probability that a given job-switcher would choose $\g$. In otherwords, $\xi$ is identified by market choices.

§.§ $\phi_{\ig}$

ℓ_ϕ_ = 0
⇒1/σ^2∑_i=1^N∑_t = 1^T logω_it-logϕ__it/ϕ__it1 { _it = , ı_i = ı} +

+ 1/ν∑_i=1^N∑_t = 1^T  c_it 1{ ı_i = ı} [ 1{ _it = } - (_it|ı_i; Θ) ] = 0

The above expression is highly intuitive. It tells us that identification of $\phi_{\ig}$ comes from two sources: earnings for all workers (first term), and market choices for job-switchers (second term). The first term is minimized when $\log \phi_{\ig}$ is close to actual log-earnings $\log \omega_{\it}$. The second term is minimized when the theoretical probability of a type $\i$ job-switcher choosing a job in market $\g$ equals the fraction of type $\i$ job-switchers who actually choose market $\g$ jobs. The relative weight of these terms in calculating the likelihood is determined by the variances of measurement error in wages and idiosyncratic shocks, $\sigma^2$ and $\nu$, respectively. Specifically, if wages are observed with considerable error (large $\sigma^2$) then we put more weight on the second term, which is identified by job changes. On the other hand, if the idiosyncratic preferences have high variance (large $\nu$), then wages are more informative than job changes.

Another thing to notice is that in cases where we observe no matches for a particular ($\i,\g$) pair, identification comes purely from the second term (because $\mathbbm{1}\{\g_{it} =\g,\i_i=\i\}=0$ in the first term). This makes sense, because we do not observe wages for matches that do not occur. Identification based on job choices in the second term relies on the assumption of a T1EV-distributed preference parameter. This is because, in order to achieve a choice probability of zero to match the count of observed matches, $\phi_{\ig} + \xi_{\g}$ will be forced towards $-\infty$. In practice, we will do something to handle zeros because we do not want to set $\phi_{\ig}+ \xi_{\g} =-\infty$. This allows us to achieve identification of the entire $\Phi$ matrix despite sparsity in observed ($\i,\g$) matches, although identification for sparse parts of $\Phi$ relies strongly on functional form assumptions. While identification based on functional form assumptions is suboptimal, we are doing so primarily for ($\i,\g$) pairs that rarely match, so imprecise estimation of these parameters will have minimal effect on our actual results. On the other hand, moving away from non-parametric identification allows us to identify a much higher degree of productivity heterogeneity.

More technically, if an ($\i,\g$) cell has zero matches, i.e. if $\mathbbm{1}\{ \g_{it} = \g, \i_i = \i \} = 0$ for all $i,t$, then the FOC above will be reduced to $ \sum_{i=1}^{N}\sum_{t = 1}^T  c_{it} \mathbbm{1}\{ \i_i = \i \} \P(\g_{it}|\i_i; \Theta) = 0$. This implies that there is no solution to the MLE problem, as $\phi_{\ig} + \xi_{\g}$ would have to go to minus infinity to make the FOC equation zero. A potential way to handle this is to add a small positive constant inside the last FOC brackets multiplied by the indicator $ \mathbbm{1} \left\{\sum_{i=1}^{N}\sum_{t = 1}^T  c_{it} \mathbbm{1}\{ \g_{it} = \g, \i_i = \i \}  = 0\right\}$.

§.§ $\lambda$

Note that we have dropped $\ig$ subscripts here, but the estimation would be approximately the same with the subscripts.

ℓ_λ= 0    ⇒1/λ (∑_i=1^N∑_t = 2^T c_it  )  - 1/1-λ ((T-1)N-∑_i=1^N∑_t = 2^T c_it ) = 0

⇒(1-λ) (∑_i=1^N∑_t = 2^T c_it  ) = λ((T-1)N-∑_i=1^N∑_t = 2^T c_it )

⇒(∑_i=1^N∑_t = 2^T c_it  ) = λ(T-1)N

⇒λ̂ = ∑_i=1^N∑_t = 2^T c_it/(T-1)N

§.§ $\sigma$

Again, we have dropped $\ig$ subscripts here, but the estimation would be approximately the same with the subscripts.

We proceed taking derivatives w.r.t. $\sigma$, knowing that $f_{\omega}(\omega|\Theta) = \frac{1}{\omega\sigma\sqrt{2\pi}}e^{-\frac{1}{2} \left(\frac{\log \omega - \log \phi_{\ig}}{\sigma}\right)^2} = \frac{1}{\omega\sigma} \phi\left(\frac{\log \omega - \log \phi_{\ig}}{\sigma}\right)$ and that $\log f_{\omega}(\omega|\Theta) = -\log(\omega \sqrt{2\pi})-\log\sigma -\sigma^{-2}\frac{1}{2} \left(\log \omega - \log \phi_{\ig}\right)^2$

ℓ_σ= 0    ⇒∑_i=1^N∑_t = 1^T ∂logf_ω(ω_it|Θ)/∂σ = 0

= -NT/σ + σ^-3 ∑_i=1^N∑_t = 1^T (logω_it - logϕ__it)^2 = 0

⇒σ̂^2 = ∑_i=1^N∑_t = 1^T (logω_it - logϕ̂__it)^2/NT

§ MEASUREMENT ERROR

The Bartik regressions in equation <ref> can be written

\begin{align*}
\Delta Earnings_g = \beta_0 + \beta_1 Bartik_g + \ve_g
\end{align*}

\begin{align*}
Bartik_{g} = \sum_m \left( Exposure_{g m} \times Shock_m \right)
\end{align*}

The earnings variable depends only on worker classifications, $g$, however the Bartik instrument depends on both worker and job classifications, $g$ and $m$. This means that worker classification error will affect both the LHS and the RHS, while job classification error will affect only the RHS.

For simplicity, Let $Y=\{\Delta Earnings_g\}_{g=1}^G$, $X=\{Bartik_g\}_{g=1}^G$, and $U=\{\ve_g\}_{g=1}^G$. Then our regression model is

\[ Y = X \beta + U\]

However we measure both $X$ and $Y$ with additive measurement error, $V_X$ and $V_Y$. Denote our measures of $X$ and $Y$, $\tilde X$ and $\tilde Y$, respectively, where

\begin{align*}
\tx &= X + V_X \\
\ty &= Y + V_Y
\end{align*}

If we estimate the regression using the noisy measures $\tilde X$ and $\tilde Y$ we obtain

\begin{align*}
\tilde \beta &= (\tx^T\tx)^{-1}(\tx^T\ty)
\end{align*}

For simplicity, let's assume that $X$, $V_X$, and $V_Y$ are orthogonal to the regression error term $\ve$. Asymptotically,

\begin{align*}
\tilde \beta &\overset{p}{\rightarrow} \frac{Cov(X+V_X, Y+V_Y)}{Var(X+V_X)} \\
&= \frac{Cov(X+V_X, X\beta+U + V_Y)}{Var(X+V_X)} \\
&= \frac{\beta Var(X) + Cov(X,U) + Cov(X,V_Y) + \beta Cov(X,V_X) + Cov(V_X,U) + Cov(V_X,V_Y)}{Var(X) + Var(V_X) + 2Cov(X,V_X)}
\end{align*}

For simplicity, and because we are focusing on the problem of measurement error rather than endogenous regressors, we assume that the regression error $U$ is independent of both X and $V_X$: $U\indep X,V_X$. This implies that $Cov(X,U)=Cov(V_X,U)=0$ and allows us to simplify the above expression to

\begin{align*}
\tilde \beta &\overset{p}{\rightarrow} \frac{\beta Var(X) + \beta Cov(X,V_X) + Cov(X,V_Y) + Cov(V_X,V_Y)}{Var(X) + Var(V_X) + 2Cov(X,V_X)}
\end{align*}

The true coefficient $\beta$ can be written

\[ \beta = \frac{Cov(X,Y)}{Var(X)}\]

and in our application we can reasonably assume $\beta>0 \Leftrightarrow Cov(X,Y)>0$.

To ascertain the direction of the bias created by measurement error we compare $\tilde \beta$ to $\hat\beta$. Theoretically, the direction of the bias is ambiguous. However, we can determine the sign of the bias under different assumptions about the covariances.

The simplest assumption would be that all of the covariances involving measurement error terms are 0: $Cov(X,V_Y) = Cov(X,V_X) = Cov(V_X,V_Y) = 0$. This is equivalent to classical measurement error, giving us the familiar attenuation bias result:

\[ \tilde \beta \overset{p}{\rightarrow}  \frac{Cov(X,Y)}{Var(X) + Var(V_X)} < \hat \beta \overset{p}{\rightarrow}  \frac{Cov(X,Y)}{Var(X) }.\]

However, we almost certainly have non-classical measurement error, so let's consider what the bias would be under more reasonable assumptions. Suppose we randomly assigned workers and jobs to groups. Then both $\tx$ and $\ty$ would simply be equal to the overall means: $\tilde X_g = \bar X \hspace{4pt} \forall g$ and  $\tilde Y_g = \bar Y \hspace{4pt} \forall g$. This means that for large values of $Y$, $\tilde Y<Y$ and similarly for $X$. This implies that $Cov(X,V_X)<0$ and $Cov(Y,V_Y)<0$. Combining this with the fact that $Cov(X,Y)>0$ implies that $Cov(X,V_Y)<0$, $Cov(Y,V_X)<0$, and $Cov(V_X,V_Y)>0$.

\begin{align*}
\tilde\beta \overset{p}{\rightarrow} \frac{\beta Var(X) + \beta \overset{<0}{\overbrace{Cov(X,V_X)}} + \overset{<0}{\overbrace{Cov(X,V_Y)}} + \overset{>0}{\overbrace{Cov(V_X,V_Y)}}}{Var(X) + \underset{>0}{\underbrace{Var(V_X)}} + \underset{<0}{\underbrace{2Cov(X,V_X)}}}
\end{align*}

In this case it is theoretically ambiguous whether $\tilde\beta>\hat\beta$ or $\tilde\beta<\hat\beta$. Empirically, we consistently find that $\tilde\beta<\hat\beta$. This means that it must be the case that the terms that tend to reduce $\tilde\beta$ — $Var(V_X)$, $\beta Cov(X,V_X)$, and $Cov(X,V_Y)$ — must dominate the terms that increase $\tilde\beta$ — $Cov(V_X,V_Y)$ and $2 Cov(X,V_X)$.

We demonstrate this point through a simulation. We simulate a shock as described in Section <ref>. We estimate a series of regressions on changes in earnings by worker type on the Bartik instrument with jobs classified by market, however in each regression we randomly misclassify some percentage of workers and jobs. We loop from 0 to 100 percent of workers misclassified in intervals of five percent, and within each loop perform the same loop from 0 to 100 percent of jobs misclassified. We present the coefficients on the Bartik instrument in Figure <ref> and the $R^2$ values in Figure <ref>. $R^2$ values decline approximately monotonically with the degree of misclassification in both the worker and job dimensions, as expected. By contrast, there is much less of a coherent story with the regression coefficients. Again, this is consistent with the theoretical prediction that the effect of misclassification on regression coefficients is indeterminate.

Coefficient estimates with worker and job misclassification

$R^2$ values with worker and job misclassification

§ PROOF THAT $A_{IJ}$ FOLLOWS A POISSON DISTRIBUTION

If an individual worker $i$ only searched for a job once, then the probability of worker $i$ matching with job $j$ would be equal to $\P_{ij} = \mathcal{P}_{\ig} d_j $ and $A_{ij}$ would follow a Bernoulli distribution:

\[ A_{ij} \sim Bernoulli(\mathcal{P}_{\ig} d_j ). \]

However, since worker $i$ searches for jobs $c_i\equiv \sum_{t=1}^T c_{it}$ times, $A_{ij}$ is actually the sum of $c_i$ Bernoulli random variables, and is therefore a Binomial random variable. Conditional on knowing $c_i$,

\[ A_{ij}|c_i \sim Binomial(c_i, \mathcal{P}_{\ig} d_j ).\]

However, we still need to take into account the fact that $c_i$ is a Poisson-distributed random variable with arrival rate $d_i$. Consequently, the unconditional distribution of $A_{ij}$ is Poisson as well:

\[ A_{ij} \sim Poisson( d_i d_j \mathcal{P}_{\ig}  ).\]

We prove this fact by multiplying the conditional density of $A_{ij}|c_i$ by the marginal density of $c_i$ to get the joint density of $A_{ij}$ and $c_i$, and then integrating out $c_i$.

P(A_ij,c_i) = Bin(c_i, d_j P_ιγ) P(A_ij|c_i)   ×  Poisson(d_i)P(c_i)

Deriving the joint distribution:

P(A_ij,c_i) =    c_iA_ij (d_j P_ιγ)^Aij(1-d_j P_ιγ)^c_i - Aij ×d_i^c_i exp(-d_i)/c_i!

We want to find out the marginal distribution of $A_{ij}$:

P(A_ij)    = ∑_c_i=0^∞P(A_ij,c_i)

= ∑_c_i=0^∞c_iA_ij (d_j P_ιγ)^Aij(1-d_j P_ιγ)^c_i - Aij ×d_i^c_i exp(-d_i)/c_i!

= ∑_c_i=0^∞c_i!/A_ij!(di-A_ij)! (d_j P_ιγ)^Aij(1-d_j P_ιγ)^c_i - Aij ×d_i^c_i exp(-d_i)/c_i!

= (d_j P_ιγ)^Aijexp(-d_i)/A_ij!  ∑_c_i=0^∞1/(di-A_ij)! (1-d_j P_ιγ)^c_i - Aij d_i^c_i

If the summation term is equal to

\begin{equation}\label{eq_bracket}
\sum_{c_i=0}^\infty \frac{1}{(di-A_{ij})!} (1-d_j P_{\iota\gamma})^{c_i - A{ij}} d_i^{c_i} = d_i^{A_{ij}} \exp{(d_i (1 - d_j P_{\iota\gamma}))}
\end{equation}

then $P(A_{ij}) = \frac{(d_i d_j P_{\iota\gamma})^{A{ij}}\exp{(-d_i d_j P_{\iota\gamma}})}{A_{ij}!}$, i.e. $A_{ij}$ would be Poisson distributed:

\[ A_{ij} \sim Poisson(d_i d_j P_{\iota\gamma}) \]

Proving (<ref>) is equivalent to proving the following equality:

1 =    1/d_i^A_ij exp(d_i (1 - d_j P_ιγ))  ∑_c_i=0^∞1/(di-A_ij)! (1-d_j P_ιγ)^c_i - Aij d_i^c_i

d_i^-A_ij exp(-d_i (1 - d_j P_ιγ))  ∑_c_i=0^∞1/(di-A_ij)! (1-d_j P_ιγ)^c_i - Aij d_i^c_i =

= ∑_c_i=0^∞exp(-d_i (1 - d_j P_ιγ))/(di-A_ij)! (1-d_j P_ιγ)^c_i - Aij d_i^c_i-A_ij

= ∑_c_i=0^∞exp(-d_i (1 - d_j P_ιγ))/(di-A_ij)! (d_i(1-d_j P_ιγ))^c_i - Aij

We assume $\lambda = d_i (1 - d_j P_{\iota\gamma})$ for simplicity and we apply a change of variables $z = c_i - A_{ij}$

= ∑_z=0^∞exp(-λ)/z! λ^z , knowing that in our problem $c_i \geq A_{ij}$, i.e. $z \geq 0$.

= 1

Since we have the p.d.f. of a Poisson r.v. inside the summation, i.e. $z \sim Poisson(\lambda)$   □

Therefore, we have

\[ A_{ij} \sim Poisson(d_i d_j P_{\iota\gamma}) \qed \]

§ WORKER AND FIRM FIXED EFFECTS

Following <cit.> and others, we decompose the variance in workers' log earnings into a component explained by worker fixed effects, a component explained by firm fixed effects, and a component explained by the covariance between worker and firm fixed effects. We find that firm effects explain 16% of the variance in log earnings in our data and the covariance  between worker and firm effects explains 11%. However, <cit.> show that estimates of the firm effects component are subject to considerable upward bias due to limited mobility of workers between firms. Therefore, building upon the approach of <cit.>, we re-estimate the model at the group level, replacing firm effects with market ($\g$) effects. Using this grouped-data approach, we find that the share of the variance explained by market effects, as opposed to firm effects, falls to 1.2% and the share of variance explained by worker–market covariance is 2.6%.

§ CUT SECTIONS THAT I DON'T WANT TO DELETE YET

§.§ Spillover effects demonstration from discussion subsection in section 2

Allowing for high-dimensional skills heterogeneity, as reflected in a high-dimensional $\Psi$ matrix, is critical in our context because it allows for flexible ripple effects in response to shocks. Suppose we are interested in understanding the effect of the increase in demand for the construction sector induced by the 2016 Olympics. Suppose we divided the economy into a small number of worker types and markets according the workers' skills in manual, cognitive, and social tasks and the jobs' task requirements along the same three dimensions. Presumably, construction demand shocks would increase the number of jobs intensive in manual tasks, and therefore increase demand for workers with a comparative advantage in manual tasks. However “manual tasks” likely lumps together diverse workers including carpenters, crane operators, truck drivers, bus drivers, and janitors. If our worker types and markets are too aggregated, then we might infer that the Olympics led to a modest increase in wages across all workers with a comparative advantage in manual tasks. However, if we are able to disaggregate worker types and markets sufficiently, we might learn that the demand shock led to drastic increases in wages for carpenters, crane operators, and truck drivers, while bus drivers and janitors were minimally affected. Failing to disaggregate sufficiently would cause us to average over heterogeneous effects and mistake isolated large effects for widespread modest effects.

As a very simple illustration of our model's mechanics, consider an economy with two sectors, two worker types, and two markets: $S=I=\Gamma=2$. Each sector uses both markets but in different proportions:

\[ \beta_{\g s} =
\begin{bmatrix}
.75 & .25 \\
.25 & .75
\end{bmatrix} \]

This means that sector 1 is intensive in tasks embedded in market $\g=1$ and sector 2 is intensive in tasks embedded in market $\g=2$, however each sector uses each market.

Initially, demand is equal to 1 in each sector: $a = [ 1 \quad 1 ]$. Let amenities $\xi = [ 0\quad 0 ]$ for simplicity. For each of the $\Psi$ matrices, we shock the demand shifter vectors by setting $a'=[2\quad 1]$. Then we compare two outcomes before and after the shock: average earnings for each worker type ($Earn$), and the fraction of each worker type matched with each market ($P_{\ig}$). We present the results in Figure <ref>.

\begin{align*}
\Psi^{Specific} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}
\end{align*}

Ψ^Specific =  1     0
0     1
Ψ^Uniform =  1     1
1     1
Ψ^Worker FE =  1     1
2     2
Ψ^Rep. Worker =  1     2
1     2

Simple simulation

Representative worker

\[	\Psi^{Rep. Worker} = \begin{bmatrix} 1 & 2 \\ 1 & 2 \end{bmatrix}	\]

\begin{align*}
\Delta Earn =
\begin{blockarray}{cc}
\i=1 & \i=2 \\
\begin{block}{[cc]}
0.044 		& 0.044 \\
\end{block}
\end{blockarray}
\end{align*}

\[\Delta P_{\ig} = \begin{bmatrix} 0.059 & -0.015 \\ 0.059 & -0.015 \end{bmatrix}	\]

Worker fixed effect

\[	\Psi^{Worker FE} = \begin{bmatrix} 1 & 1 \\ 2 & 2 \end{bmatrix}	\]

\begin{align*}
\Delta Earn =
\begin{blockarray}{cc}
\i=1 & \i=2 \\
\begin{block}{[cc]}
0.050 		& 0.035 \\
\end{block}
\end{blockarray}
\end{align*}

\[\Delta P_{\ig} = \begin{bmatrix} 0.049 & 0.002 \\ 0.068 & -0.033 \end{bmatrix}	\]

Specific skills

\[	\Psi^{Specific} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}	\]

\begin{align*}
\Delta Earn =
\begin{blockarray}{cc}
\i=1 & \i=2 \\
\begin{block}{[cc]}
0.067 		& 0.040 \\
\end{block}
\end{blockarray}
\end{align*}

\[\Delta P_{\ig} = \begin{bmatrix} 0.134 & -0.067 \\ -0.040 & 0.079 \end{bmatrix}	\]

For the clearest illustration of the mechanisms at play, compare results for specific skills to those for representative workers. In both cases, the demand shock for sector 1 represented an increase in type $\g=1$ jobs. In the specific skills case, this leads to a larger increase in earnings for type $\i=1$ workers, whose skills are a better fit for type 1 jobs.[Note that there is still an effect for type 2 workers because workers may choose a market in which they have zero productivity, as long as their idiosyncratic preference shock is large enough.] Similarly, looking at $\Delta P_{\ig}$, we see an increase in assortative matching: type 1 workers become more likely to work in type 1 jobs, while type 2 workers become more likely to work in type 2 jobs. By contrast, when we shock the economy governed by $\Psi^{Rep. Worker}$, we see that both worker types were affected equally. This is because the two worker types have the exact same skills. Our model would learn from this that there is, in fact, only one worker type and cluster all of these workers together.

§.§ Static equilibrium analysis

In this section we decompose workers' expected utility into a systematic component, composed of earnings and market-specific non-pecuniary benefits, and an idiosyncratic component based on workers' utility shocks. We show that the latter can be interpreted as an index reflecting workers' outside options.

The utility for type $\i$ worker $i$ working in a job in market $\g$ is

\[ U_{i\g|i\in\i} =   w_{\g} \psi_{\ig} + \xi_{\g} + \ve_{i\g} \]

where $\psi_{\ig}$ is a type $\i$ worker's productivity in a job in market $\g$, $w_{\g}$ is the “wage” per efficiency unit of labor paid by jobs in market $\g$, $\xi_{\g}$ is a fixed amenity value associated with all jobs in market $\g$, and $\ve_{i\g}$ is worker $i$'s idiosyncratic utility of working in a job in market $\g$,  $\ve_{i\g} \sim T1EV(0,\nu)$. $w_{\g}$ is determined in general equilibrium, but is exogenous from the perspective of an individual worker. The worker's problem is to choose a market to work for in order to maximize utility:

\[ \max_{\g} \{ w_{\g} \psi_{\ig} + \xi_{\g} + \ve_{i\g} \}\]

Let $\g^*$ denote worker $i$'s optimal choice:

\[\g^* = \argmax_{\g} \{ w_{\g} \psi_{\ig} + \xi_{\g} + \ve_{i\g} \}. \]

We can decompose worker $i$'s expected utility at their optimal choice of $\g$, $\g^*$, into two components: a “systematic” component based on earnings and amenities, and an “idiosyncratic component” determined by idiosyncratic utility.

\begin{align*}
\E[ U_{i\g^*}] 	&= \E[w_{\g^*} \psi_{\ig^*} + \xi_{\g^*} + \ve_{i\g^*}]  \\
&= \E[w_{\g^*} \psi_{\ig^*} + \xi_{\g^*}] + \E[\ve_{i\g^*}] \\
&= \underset{\text{Systematic}}{\underbrace{\E[w_{\g^*} \psi_{\ig^*} + \xi_{\g^*}]}} +  \underset{\text{Idiosyncratic }}{\underbrace{\nu \left( -\int_{\g} \P(\g | \i) \log \P(\g | \i) \right) }}
\end{align*}

where $\P(\g | \i)$ is the probability that a type $\i$ worker chooses a job in market $\g$. It is the logit choice probability resulting from the worker's choice described above and the T1EV assumption.

Each component tells us something important, but not surprising:

* Systematic — workers with more valuable skills (greater $w_{\g} \psi_{\ig}$) have higher expected utility.

* Idiosyncratic — workers who have more outside options have higher expected utility, all else equal.

It is important to unpack the idiosyncratic component. This is a statement about the distribution of $\ve_{i\g^*}$, the value of the idiosyncratic shock at the worker's optimal choice, not about $\ve_{i\g}$. We have assumed that $\ve_{i\g}$ is iid. However, consider a worker with highly-specific skills (small $ -\int_{\g} \P(\g | \i) \log \P(\g | \i)$), for example a doctor. It would take an extremely large draw of $\ve_{i\g}$ in a non-medical market to convince this doctor to take a job outside of medicine.[Recall that we have assumed that workers have idiosyncratic preferences over markets, but are indifferent about individual jobs within markets. In reality, it's possible that workers like doctors have strong preferences for individual jobs. We explore this in concurrent work in which we allow workers to have idiosyncratic preferences over individual jobs, which gives individual jobs market power.] In other words, the systematic component of utility dominates the doctor's decision and the doctor's $\ve_{i\g^*}$ will not be very positively selected. On the other hand, consider someone with less-specific skills that can be used in retail, fast food, janitorial, or other jobs. This worker's systematic component will not vary much across markets, meaning that this worker will tend to pick the market for which they received the largest $\ve_{i\g}$. Therefore, their $\ve_{i\g^*}$ will be more positively selected. This implies that in our model workers with less-specific skills receive higher utility, conditional on their average skill level, because they have more opportunities to achieve a very good idiosyncratic match.[In reality this effect might be reversed if workers with more-specific skills search in geographically broader labor markets, and we are looking into extensions that take this seriously, but for now we restrict to a single city and assume no mobility to other cities. Moreover, we assume that all workers draw $\ve_{i\g}$ from the same distribution, but allowing the distribution to vary across worker types is a potentially valuable extension.]

The expression $ -\int_{\g} \P(\g | \i) \log \P(\g | \i)$ is known as entropy and is a measure of the dispersion of a given worker's market match probabilities: if worker $i$ matches with one market with probability 1 then the entropy converges to its minimum at 0, while entropy is maximized when worker $i$ has a uniform distribution of match probabilities over markets. This matters for utility because the more jobs are good matches for worker $i$, the more opportunities there are for $i$ to receive a particularly good draw of idiosyncratic preferences $\ve_{i\g}$.

Figure <ref> displays the observed relationship between $\E[ U_{i\g^*}]$, $\E[\Phi_{\ig^*} + \xi_{\g^*}]$, and $\E[\ve_{i\g^*}]$. Note that $ \E[\ve_{i\g^*}]$ is labeled “entropy” in the figures. Each point in the figures represents a different worker type $\i$. As expected, panel (a) shows a positive relationship between expected utility and the systematic component across worker types. Panel (b) shows a negative relationship between expected utility and the idiosyncratic component. This contrasts with the positive relationship between these variables described above, however the positive relationship was conditional on $\E[\Phi_{\ig^*} + \xi_{\g^*}]$. This negative relationship does not hold $\E[\Phi_{\ig^*} + \xi_{\g^*}]$ constant. The discrepancy, therefore, reflects a negative relationship between $\E[\Phi_{\ig^*} + \xi_{\g^*}]$ and $\E[\ve_{i\g^*}]$, as shown in panel (c).
Therefore we conclude that although workers with more outside options have higher expected utility all else equal, workers with higher expected systematic utility (essentially workers with higher average skill levels) tend to have more specific skills and therefore fewer outside options.

Decomposing $\E[ U_{i\g^*}]$
$\E[ U_{i\g^*}]$ and $\E[\Phi_{\ig^*} + \xi_{\g^*}]$

$\E[ U_{i\g^*}]$ and $ \E[\ve_{i\g^*}]$

$\E[\Phi_{\ig^*} + \xi_{\g^*}]$ and $\E[\ve_{i\g^*}]$

Next, we investigate how observable characteristics of workers are related to the workers' outside options. In Figure <ref> we regress each worker type's $\E[\ve_{i\g^*}]$ on various observable characteristics.

Relationship between $\E[\ve_{i\g^*}]$ and observable characteristics
O*NET skills, separate regressions

O*NET skills, horse race

Demographics, separate regressions

§.§ O*NET skills space

In this set of figures, the x- and y-axes each reflect one dimension of O*NET skills. We can do this for 16 skill dimensions[ is defined for the U.S., but we use a crosswalk from the U.S. O*NET to the Brazilian occupation classification system created by Aguinaldo Maciente.] — Cognitive, Operational, Social and emotional, Management, Physical, Transportation, Social sciences, Accuracy, Design & engineering, Artistic, Life sciences, Information technology, Sales, Self-reliance, Information processing, Teamwork — however in  this document we focus on the cognitive and physical dimensions. Black dots represent individual worker types, while the color gradients represent the percent change in worker types' expected utility due to the shock.

Figure <ref> presents the results for four different industries. As we can see, the effect of doubling the demand shifter for construction is concentrated among workers with high levels of physical skills, while doubling the demand shifter for the “public administration, defense, education, health, and social security” sector primarily affects workers with the highest cognitive skills.

Figure <ref> is similar to Figure <ref> but considers only the financial sector shock and considers more dimensions of worker skills.

Pct $\Delta$ Expected Utility Due to Shock, by O*NET Skills — Various Sectors

Effect of shocks are quite local in that most of the effect is concentrated among a small number of worker types. Also, different shocks impact different types of workers.

Pct $\Delta$ Expected Utility Due to Shock, by O*NET Skills — Finance Sector Only

Does the shock to finance hit high skill or low skill workers? It depends on which skill we are talking about.

§ SIMULATED PANDEMIC SHOCK

Effects of exposure to simulated pandemic shock

The Covid-19 pandemic shock is modeled as a 50% reduction in demand for the Accommodations and Food sector's output.

We observe a similar process when we shock the Accommodations and Food sector instead of the Manufacturing sector.

We focus on the worker type that experiences the largest reduction in earnings as a result of the shock, $\i=269$. 38%  of $\i=246$ workers are employed in the Accommodations and Food sector, while 21% are employed in the Private Health and Education sector. If we measured exposure to the shock at the sector level, we would correctly identify these workers as having significant exposure to the Accommodations and Food sector, however we would miss their exposure to other sectors, especially Private Health and Education.

Workers in worker type $\i=269$ overwhelmingly supply their labor to a single market: $\g=233$ (74% of their labor). Therefore we would expect that the shock had a large impact on this market. Unsurprisingly  market $\g=233$ had the fourth largest reduction in the price per efficiency unit of labor $w_\g$ of any market. Therefore, workers in  worker type $\i=269$ are heavily exposed to the shock at the market level, but only moderately exposed at the sector level. But why was there such a large effect in market $\g=233$? 30% of $\g=233$'s tasks are supplied to the Accommodations and Food sector, so the market itself is heavily exposed to the Accommodations and Food sector. In fact, market $\g=233$ supplies the third greatest share of its tasks to the Accommodations and Food sector of all markets. Therefore it is not surprising that this market experienced one of the largest decreases in $w_\g$.

To better understand who the workers in worker type $\i=269$ are, Table <ref> tabulates the occupations in which we most frequently observe them employed.[These tabulations use real data, not the simulated data.]   we tabulate the occupations in which we most frequently observe $\i=246$ employed. By far the most frequent occupation is “nutritionist.” It is not surprising that these workers would be employed in both the Accommodations and Food sector and the Private Health and Education sector.

§ SHOCK DECOMPOSITION APPENDIX

in 1/2nd ,2/3rd ,3/4th ,4/5th ,5/6th ,147/148th

Pandemic Shock Decomposition: Most-Exposed Worker Type $\i$


# Auditing an Automatic Grading Model with deep Reinforcement Learning

Aubrey Condor

Zachary Pardos

University of California Berkeley<EMAIL_ADDRESS>University of
California Berkeley<EMAIL_ADDRESS>
###### Abstract

We explore the use of deep reinforcement learning to audit an automatic short
answer grading (ASAG) model. Automatic grading may decrease the time burden of
rating open-ended items for educators, but a lack of robust evaluation methods
for these models can result in uncertainty of their quality. Current state-of-
the-art ASAG models are configured to match human ratings from a training set,
and researchers typically assess their quality with accuracy metrics that
signify agreement between model and human scores. In this paper, we show that
a high level of agreement to human ratings does not give sufficient evidence
that an ASAG model is infallible. We train a reinforcement learning agent to
revise student responses with the objective of achieving a high rating from an
automatic grading model in the least number of revisions. By analyzing the
agent’s revised responses that achieve a high grade from the ASAG model but
would not be considered a high scoring responses according to a scoring
rubric, we discover ways in which the automated grader can be exploited,
exposing shortcomings in the grading model.

###### keywords:

Reinforcement Learning, Automatic Grading

##  1 Introduction

It has been shown that the use of open-ended (OE) items is beneficial for
student learning due to the generation effect [2] or in combination with self-
explanation [6]. However, assessing OE items is time consuming for teachers
[16] and consequently, educators often default to using multiple choice (MC)
questions. Automatic short answer grading (ASAG) models may help alleviate
this time burden while encouraging educators to frequently incorporate OE
items in their curriculum. To test the goodness of ASAG models, researchers
typically follow the evaluation methods of machine learning (ML) researchers:
using a hold-out or cross-validation approach where a portion of the data is
used for training and another used for testing. Results are presented with
metrics like accuracy or F1 score which signify a degree of agreement to the
human ratings used to create the held-out test data. If an ASAG model shows
concordance to human ratings, researchers generally say that the model
performs well. However, we argue that even when training data are carefully
constructed via meticulous grading from subject matter experts (SMEs), metrics
which signify high agreement to an educator’s ratings do not provide
sufficient evidence that an ASAG model’s scoring is robust.

The purpose of this work is to audit an ASAG model by constructing unique
responses that are granted high scores from a state-of-the-art ASAG model but
would not receive a high score from an educator, according to a scoring
rubric. We train a reinforcement learning (RL) agent to revise a student’s
response with the objective of obtaining a high score from an ASAG model in
the least number of revisions. A revision consists of adding a phrase or
deleting a portion of the students response. Because the RL agent has no
knowledge of the scoring rubric and learns by trial-and-error over many
thousands of revisions, we hypothesize that some of the high-scoring responses
it learns to create would not qualify as a high scoring response according to
a scoring rubric created by SMEs, providing evidence of flaws in the ASAG
model. Although a human could find ways to exploit an ASAG model similarly
through trial and error probing, the advantage of using RL is that the agent
can create many thousands of responses quickly through its revisions, and does
so specifically to achieve a high rating. We use a BERT-base multi-class
classification model as our ASAG model which is a specific type of LLM [11]
that has been used extensively in recent ASAG research [3] [5]. The novelty of
this research is not in training and evaluating the ASAG model, but in finding
ways to probe a typically used ASAG model using RL.

We analyze results from three experimental settings, distinguished by which
phrases the agent can add to a response. In all three experiments, the agent
is able to delete a section of the student’s response in the same way. To
define the phrases that the agent is able to add to a response, we reference
the scoring rubric that was created by subject matter experts for the original
human ratings. In the first experiment, the agent is able to insert any of 10
key phrases which each represent an idea determined to be important for
achieving a high score as specified in the rubric. We set the agent up for
success by giving it choices that are likely to increase a response’s rating.
In the second experiment, we set the agent up for failure as the agent can add
any of 10 unhelpful phrases that should not increase the probability of
achieving a high rating, but that include relevant terminology. In the third
experiment, the agent can add any of 20 phrases including the 10 key phrases
from the first experiment and the 10 unhelpful phrases from the second
experiment.

##  2 Related Work

###  2.1 ASAG with Deep Learning

Recent ASAG research exploits advances in deep learning methods. Haller et al.
(2023) provide a comprehensive analysis of recently published methods which
deploy deep learning approaches for ASAG. They emphasize that the progression
from engineered features of text to representation learning methods, including
the use of word embeddings, sequential models and attention-based methods, has
contributed to recent improvements in ASAG models [15]. Further, much of the
newest ASAG work makes use of large language models (LLMs). Camus and
Filighera compared the performance of LLMs for ASAG in terms of the size of
the transformer and the ability to generalize to other languages [5], and
Condor et al. explored whether a BERT ASAG model may be improved by further
pre-training on graphical representations of scoring rubrics [10] . Agarwal et
al. (2022) introduced the Multi-Relational Graph Transformer (MitiGaTe) to
prepare token representations that consider the structural context of a
sentence [1], and Zhu et al. (2022) proposed a novel BERT-based, NN framework
for ASAG by adjusting BERT embeddings with a semantic refinement layer
consisting of a bidirectional-Long Short-Term Memory (LSTM) network and a
Capsule network with position information [22]. Additionally, researchers are
investigating the robustness of such grading models: Filighera et al. (2020)
found that ASAG systems can be fooled with universal adversarial trigger
employment [14], and Condor et al. (2021) attempted to make LLM ASAG models
more generalizable to out-of-training-sample questions by incorporating
question-related text [8].

###  2.2 RL for Education

The use of RL for applications in education is not yet broadly explored. A
survey article by Singla et al. summarized that the main contributions in RL
for education have been personalizing curriculum, providing hints, adaptive
experimentation, modeling students, and content generation [20]. Notable works
include Fazazi et al. who presented a multi-agent approach to deep Q-larning
for designing an adaptive e-Learning system which customizes to a particular
learner’s characteristics [13]. MacLellan and Gupta used Proximal Policy
Optimization to learn expert models for educational tasks and compare their RL
approach to existing computational approaches [18]. Doroudi et al. reviewed a
variety of RL based attempts at instructional sequencing, and concluded that
RL has been most successful in when it is constrained by theories from the
psychological sciences [12]. Finally, Cai et al. presented MathBot, a bandit
algorithm chatbot that explains math concepts, provides practice questions,
and offers personalized feedback to students [4], and Condor and Pardos [9]
created an RL algorithm to provide formative feedback to students about their
open-ended responses in a simulated environment.

##  3 Background

###  3.1 Deep Reinforcement Learning

RL employs learning to control a dynamical system by providing feedback to an
agent via a reward system, such that the agent learns to choose an optimal
action in a state. The action consists of what the agent can do in the state,
and the state represents the current condition of the agent. When the agent
takes an action, it receives a reward as feedback from the environment. The
agent’s goal is to learn a policy to maximize its total expected sum of
rewards [21]. Traditionally, RL algorithms implement online learning by
iteratively collecting experiences while actively interacting with an
environment, but offline RL algorithms utilize previously collected data. Our
policy is trained using offline learning because as the agent will make many
mistakes while it learns, and “bad” revisions could hinder a student’s
learning progression. Our RL agent is trained via Proximal Policy Optimization
- a family of policy gradient methods for reinforcement learning [21].

###  3.2 The ASAG Model

The ASAG model that we use to provide ratings for student responses as well as
feedback to the agent through a reward function is a BERT-base multi-class
classification model. BERT is a popular language model that has been used
frequently in ASAG research. The BERT transformer language model, introduced
in [11], can be fine-tuned for downstream tasks such as classification. We use
a compressed version of the model called BERT-base due to computational
resource limitations. The model is fine-tuned as a supervised classifier using
781 human ratings of the OE question(s) as ground-truth training ratings, just
as in previous ASAG works such as [7]. The model was trained using a train-
validation-test split of 70%, 15%, 15% respectively. The held-out test set
achieved a Quadratic Weighted Kappa of 0.7919 and a ROC AUC value of 0.9185

##  4 Methods

###  4.1 The Reinforcement Learning Formulation

The agent’s training objective is to iteratively revise a response to achieve
a high grade from the ASAG model in the least number of revisions. For each
episode, we will initialize by randomly sampling a previously collected
student response. Based on the response, the agent will choose an action to
take via the current policy, i.e., either adding a phrase or deleting a
portion of the response. Next, we send the newly revised student response to
the ASAG model and receive a probability distribution of rating categories. We
calculate the reward as a function of the difference in rating class
probabilities from the previous response to the newly revised response, and if
the reward has surpassed a predefined threshold, the episode will terminate.
Otherwise, the process is repeated with the revised student response until the
reward threshold is achieved, or the agent reaches a maximum number of
revisions. Further details follow.

Repeat (for each episode):

Randomly sample student response

Get response rating from ASAG model

Repeat (for each time step):

Choose action and alter response

Get rating of altered response

Calculate reward

Until max steps or rating threshold reached

Algorithm 1 The RL Formulation

The State consists of the response that the agent is currently revising. For a
given student’s response, if the agent has already made a revision, the state
would consist of the revised response (i.e., the original response plus the
added text or without the deleted text). The Action Space consists of the
phrases that the agent may add and where it chooses to place the phrase within
the response - either in the front (before the first word) or at the end
(after the last word) of the current response. The agent may also choose to
delete any 1/5th sized section of the existing response. Thus, the action
space is size 25 for the first two experiments ((2 locations * 10 phrases) + 5
delete options), and size 45 for the third experiment ((2 locations * 20
phrases) + 5 delete options). We only allow the agent to add phrases to two
locations and limit the flexibility of its’ delete actions to keep the action
space at a reasonable size. The maximum number of revisions the agent can make
in one episode (to one response) is eight. The Policy is a BERT-base model
because of the model’s impressive ability to learn representations of text.
The input to the BERT policy is the state, and output is a probability
distribution over the action space. The Reward is a scaled difference in the
expected value of the old rating to the expected value of the new rating, with
a penalty for each revision the agent makes. We include the penalty because we
want the agent to learn how to revise the student’s response in the least
number of revision steps. We scale the difference in expected values by
multiplying by 3 because the overall difference tended to be small and we
needed to send a stronger signal to the agent. The reward formula is as such:

$3\cdot(\sum_{x=0}^{4}x_{new}\cdot p(x_{new})-\sum_{x=0}^{4}x_{old}\cdot
p(x_{old}))-1$

###  4.2 The Data Set

We used a data set from a previous research project at UC Berkeley consisting
of OE science items designed for middle school students [19]. Responses were
scored with a Knowledge Integration (KI) rubric by subject matter experts. KI
is a framework for strengthening science understanding that emphasizes
incorporating new ideas and sorting out alternative perspectives with evidence
[17]. For this project, we use one item from a unit about the physics of sound
waves that engages students to refine their ideas about concepts like
wavelengths, frequency and pitch. Students must distinguish how the pitch of
sound made by tapping a full glass of water compares to the pitch made by
tapping an empty glass [19]. The data include 1313 OE responses rated from 1
(lowest rating) to 5 (highest rating). A detailed rubric was created by
researchers and used for scoring that includes a description of the rating
level, examples of correct/incorrect mechanisms and conclusions, and examples
of student responses that would fall into each category.

###  4.3 The Experiments

We investigate how the RL agent finds ways to exploit the ASAG model by
defining three different experiments. In all three experiments, the agent can
delete any 1/5th response length section as 5 of its actions. What differs
between the experiments is the set of phrases the agent can choose to insert
either before the first word of the response or after the last word of the
response. In the first experiment, the agent may insert any of 10 key phrases
into a response. These phrases were taken directly from the SME-created rubric
as important mechanisms or conclusions that a student could include in their
response to achieve a high rating. In the second experiment, we include 10
phrases that include words related to the subject matter, but that do not
contain information that should lead to a higher score. We will refer to these
as unhelpful phrases. In the third experiment, we allow the agent to insert
any of 20 phrases including both the important phrases and unhelpful phrases.
Below are the phrases for the first two experimental setups.

Experiment 1 - Helpful Phrases: ’sound moves faster in air’, ’sound moves
slower in water’, ’water is more dense’, ’water has more mass’, ’higher
frequency in air’, ’pitch is lower in water’, ’pitch higher in empty glass’,
’air is less dense’, ’less vibration in water’, ’the pitch is different’
Experiment 2 - Unhelpful Phrases: ’I am not sure’, ’tapping the glass’, ’sound
bounces in the glass’, ’sound sinks in water’, ’sound will echo in glass’,
’the pitch is the same’, ’water blocks the sound’, ’frequency is height of
wave’, ’amplitude is number of waves’, ’sound is more dense’

##  5 Results

For each experiment, we train the agent 10 times for 75,000 time steps,
differing only in the random initialization of the policy network. Each
training run yields a different number of episodes depending on how many
revisions it takes the agent to arrive at the threshold reward, so we analyze
the first 18,250 episodes of each run. Visually, we can compare the mean
episode return over time, smoothed with a rolling average of n=200, of the 10
runs across each experiment in Figure 1. We include 95% confidence bands for
each smoothed mean as well. It is apparent that the training runs for
experiment 1 (Helpful Phrases) and experiment 3 (All Phrases) consistently
yield higher average episode returns than those for experiment 2 (Unhelpful
Phrases). We are not surprised by this result as less revisions correspond to
a higher return, and we hypothesized that the agent should be able to achieve
the high threshold rating with a lesser number of revisions using helpful
phrases than with the unhelpful phrases. We also see significant overlap in
the confidence bands between experiment 1 (Helpful Phrases) and experiment 3
(All Phrases). In the sections that follow, we provide results of an
exploratory data analysis of action sequences for the top 5% of episode
returns for each of the three experiments. When showing examples of student
responses and corresponding revisions, we show added phrases in brackets, and
deleted pieces of a response with a strike-through.

Figure 1: Mean returns of the first 18,250 episodes over 10 training runs for
each experiment, smoothed with a rolling average of n=200.

###  5.1 Experiment 1: Helpful Phrases

We analyze 9,125 total high scoring revision sequences that correspond to the
top 5% of returns over all 10 training runs in experiment 1. The mean number
of actions necessary to achieve a high ASAG rating is 3.4. Interestingly, the
agent rarely - only 21 sequences out of 9,125 (0.23%) - chooses to delete a
section of a response in the top scoring sequences. The most compelling
finding is that the agent frequently chooses to add the same phrase multiple
times within a revision sequence - the number of sequences with at least one
repeated phrase addition is 2,353 or 26% of all 9,125 sequences we analysed.
Further, in 161 revision sequences, the agent chooses to add the same phrase
at least three times in a row (1.76% of the time). For example: "[water has
more mass] in a pool its lower and slower a glass wouldnt be different [water
has more mass] [water has more mass] [water has more mass]" (after 4
revisions)

###  5.2 Experiment 2: Unhelpful Phrases

We analyze 9,146 total high scoring revision sequences that correspond to the
top 5% of returns over all 10 training runs in experiment 2. The mean number
of actions necessary to achieve a high ASAG rating is 3.12. Although the top
5% of scores for experiment two is lower than that of experiment 1 (as is
evident in Figure 1), we emphasize that the revised responses in the top 5% of
experiment two are still able to achieve the high threshold rating from the
ASAG model, using the supposedly unhelpful phrases. The most interesting
finding is that 84.3% of actions chosen across all revision sequences
correspond to adding the phrase, "sound is more dense". Further, the phrase,
"frequency is height of wave" is chosen 14.8% of the time. Even more
pronounced than that of experiment 1 is the repeating of the same action
choice multiple times within a revision sequence - this happens in 7,916 total
revision sequences (86.6%) and the majority of these cases consist of adding
the "sound is more dense" phrase repeatedly. For example: "the waves travel
farther making a higher pitch [sound is more dense] [sound is more dense]"
(after 2 revisions)

###  5.3 Experiment 3: All Phrases

We analyze 9,125 total high scoring revision sequences that correspond to the
top 5% of returns over all 10 training runs in experiment 3. The mean number
of actions necessary to achieve a high ASAG rating is 3.5. We find that 90% of
all actions taken in the top 5% consist of adding ’Helpful Phrases’ from
experiment 1, and only 10% consist of adding ’Unhelpful Phrases’ from
experiment 2. Of the actions that the agent chooses from the ’Unhelpful
Phrases’, results are consistent to that of experiment 2 in that by far, the
most frequently chosen phrase to add was "sound is more dense". This phrase
was chosen about 95% of the time an unhelpful phrase was chosen. Further,
consistent with experiments 1 and 2, we see the agent repeats the same phrase
addition at least once within a sequence in 2172 (24%) of the 9,125 revisions
analysed. For example: "[pitch is lower in water] i dont know [water has more
mass] [water has more mass] [sound is more dense]" (After 4 revisions)

##  6 Discussion

In all three experiments, it appears that the agent is able to increase ASAG
response scores by adding the same phrase multiple times. This should
certainly not be the case as repeating a phrase does not indicate an increase
in understanding. Further, the idea that the agent is able to improve a
response’s automatic grade with any of the unhelpful phrases is evidence that
there are issues to be resolved with the ASAG model. We noticed that agent
disproportionately favored incorrect phrases like "sound is more dense" which
is a typical misunderstanding of students, as specified in the scoring rubric.
The ASAG model seems to be "tricked" by this phrase, as it includes relevant
terminology like "more dense". Finally, evident from Experiment 3, although
the agent highly favors the helpful phrases, it does choose the unhelpful
phrases about 10% of the time.

Limitations of our work include that our analysis is dependent on the action
spaces we chose for the agent in each experiment. There may be a better or
different assortment of unhelpful phrases that would have been useful to
include in the action space for experiment two. Further, our analysis was
specific to a ASAG BERT model and although this is a particularly popular
option for recent ASAG research, many researchers are using different variants
of LLMs like RoBERTa or Llama. Additionally, we analyze results from one
specific question related to science understanding. Finally, as our analysis
was exploratory, it was only reasonable to find general patterns in the
agent’s revisions as opposed to examining each high scoring revision sequence.

We have found a few interesting flaws in a frequently used, state-of-the-art,
ASAG model. For this work to be practically useful, we hope that these
findings may be helpful for improving similar LLM ASAG models. As we continue
this work, we plan to use these undesirable examples to retrain the ASAG
model. For instances where the agent added incorrect phrases, or inserted the
same phrase multiple times, we can rate those responses as lower than their
original, un-revised scores, and add the altered responses and ratings to the
original data set to retrain the ASAG model. We would hypothesis that the
retrained ASAG model may not reward responses with repeated phrases or non-
useful phrases. We have shown that there are still issues to be sorted out
with such models and importantly, the creative use of deep RL may help
education researchers search for such flaws in similar scenarios with large
search spaces.

##  7 Acknowledgments

This work was supported in part by funding from the UC Berkeley Peder Sather
Center for Advanced Study.

## References

  * [1] R. Agarwal, V. Khurana, K. Grover, M. Mohania, and V. Goyal.  Multi-relational graph transformer for automatic short answer grading.  In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2001–2012, 2022.
  * [2] S. Bertsch, B. J. Pesta, R. Wiscott, and M. A. McDaniel.  The generation effect: A meta-analytic review.  Memory & cognition, 35(2):201–210, 2007.
  * [3] S. Bonthu, S. Rama Sree, and M. Krishna Prasad.  Automated short answer grading using deep learning: A survey.  In Machine Learning and Knowledge Extraction: 5th IFIP TC 5, TC 12, WG 8.4, WG 8.9, WG 12.9 International Cross-Domain Conference, CD-MAKE 2021, Virtual Event, August 17–20, 2021, Proceedings 5, pages 61–78. Springer, 2021.
  * [4] W. Cai, J. Grossman, Z. J. Lin, H. Sheng, J. T.-Z. Wei, J. J. Williams, and S. Goel.  Bandit algorithms to personalize educational chatbots.  Machine Learning, 110(9):2389–2418, 2021.
  * [5] L. Camus and A. Filighera.  Investigating transformers for automatic short answer grading.  In International Conference on Artificial Intelligence in Education, pages 43–48. Springer, 2020.
  * [6] M. T. Chi, N. De Leeuw, M.-H. Chiu, and C. LaVancher.  Eliciting self-explanations improves understanding.  Cognitive science, 18(3):439–477, 1994.
  * [7] A. Condor.  Exploring automatic short answer grading as a tool to assist in human rating.  In International Conference on Artificial Intelligence in Education, pages 74–79. Springer, 2020.
  * [8] A. Condor, M. Litster, and Z. Pardos.  Automatic short answer grading with sbert on out-of-sample questions.  In Proceedings of the 14th International Conference on Educational Data Mining, 2021.
  * [9] A. Condor and Z. Pardos.  A deep reinforcement learning approach to automatic formative feedback.  2022\.
  * [10] A. Condor, Z. Pardos, and M. Linn.  Representing scoring rubrics as graphs for automatic short answer grading.  In International Conference on Artificial Intelligence in Education, pages 354–365. Springer, 2022.
  * [11] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805, 2018.
  * [12] S. Doroudi, V. Aleven, and E. Brunskill.  Where’s the reward?  International Journal of Artificial Intelligence in Education, 29(4):568–620, 2019.
  * [13] H. El Fazazi, M. Elgarej, M. Qbadou, and K. Mansouri.  Design of an adaptive e-learning system based on multi-agent approach and reinforcement learning.  Engineering, Technology & Applied Science Research, 11(1):6637–6644, 2021.
  * [14] A. Filighera, T. Steuer, and C. Rensing.  Fooling automatic short answer grading systems.  Lecture Notes in Computer Science Artificial Intelligence in Education, page 177–190, 2020.
  * [15] S. Haller, A. Aldea, C. Seifert, and N. Strisciuglio.  Survey on automated short answer grading with deep learning: from word embeddings to transformers.  arXiv preprint arXiv:2204.03503, 2022.
  * [16] C. L. Hancock.  Implementing the assessment standards for school mathematics: Enhancing mathematics learning with open-ended questions.  The Mathematics Teacher, 88(6):496–499, 1995.
  * [17] M. C. Linn.  Designing the knowledge integration environment.  International Journal of Science Education, 22(8):781–796, 2000.
  * [18] C. J. MacLellan and A. Gupta.  Learning expert models for educationally relevant tasks using reinforcement learning.  International Educational Data Mining Society, 2021.
  * [19] B. Riordan, S. Bichler, A. Bradford, J. King Chen, K. Wiley, L. Gerard, and M. Linn.  An empirical investigation of neural methods for content scoring of science explanations.  In Proceedings of the fifteenth workshop on innovative use of NLP for building educational applications, 2020.
  * [20] A. Singla, A. N. Rafferty, G. Radanovic, and N. T. Heffernan.  Reinforcement learning for education: Opportunities and challenges.  arXiv preprint arXiv:2107.08828, 2021.
  * [21] R. S. Sutton and A. G. Barto.  Reinforcement learning: An introduction.  MIT press, 2018.
  * [22] X. Zhu, H. Wu, and L. Zhang.  Automatic short-answer grading via bert-based deep neural networks.  IEEE Transactions on Learning Technologies, 15(3):364–375, 2022.