# Estimation of Missing Data in Intelligent Transportation System

Bahareh Najafi 0000-0002-1030-592X  University of Toronto
Toronto, Canada
<EMAIL_ADDRESS>Saeedeh Parsaeefard  University of Toronto
Toronto, Canada
<EMAIL_ADDRESS>Alberto Leon-Garcia  University of Toronto
Toronto, Canada
<EMAIL_ADDRESS>
###### Abstract

Missing data is a challenge in many applications, including intelligent
transportation systems (ITS). In this paper, we study traffic speed and travel
time estimations in ITS, where portions of collected data are missing due to
sensor instability and communication errors at collection points. These
practical issues can be remediated by missing data analysis, which are mainly
categorized as either statistical or machine learning (ML)-based approaches.
Statistical methods require the priori probability distribution of the data
which is unknown in our application. Therefore, we focus on an ML-based
approach, Multi-Directional Recurrent Neural Network (M-RNN). M-RNN utilizes
both temporal and spatial characteristics of the data. We evaluate the
effectiveness of this approach on a TomTom dataset containing spatio-temporal
measurements of average vehicle speed and travel time in the Greater Toronto
Area (GTA). We evaluate the method under various conditions, where the results
demonstrate that M-RNN outperforms existing solutions, e.g., spline
interpolation and matrix completion, by up to 58$\%$ decreases in Root Mean
Square Error (RMSE).

###### Index Terms:

ITS, missing data analysis, multi-directional recurrent neural network,
spatio-temporal measurements

##  I Introduction

Traffic flow estimation is essential in the ITS in a system implemented at
scale in a large city, the accuracy will be highly dependent on how data is
collected from diverse sources such as cameras and Bluetooth sensors. This
heterogeneity in the source of gathered data along with their different
placements and capabilities, e.g., precision, capacity, data sampling rate,
image resolution of the cameras, leads variation in spatio-temporal
measurements. Moreover, for any type of data collection, the problem of
missing data can occur throughout a distributed urban network due to
malfunctioning sensors or communication errors among the collection points
[1]. Furthermore, full coverage is not provided on some roads due to
construction activities, which leads to missing data. Therefore, we need to
address this challenge in our application scenario by accurately estimating
missing values. Generally, two groups of methods are used for the estimation
of missing data: Statistical approaches and ML-based approaches. Statistical
methods such as Bayesian models e.g., Bayesian principal component analysis
[2], [3] infer the missing points using a learned scheme based on the
statistical characteristics of the observed data. They usually assume a prior
probability distribution for the observed value and missing data are permuted
based on a probability distribution function (PDF). The traffic stream of
vehicles is affected by several environmental factors and does not necessarily
follow a particular PDF. As for ML-based approaches for estimating missing
data, some research has been conducted on missing data analysis in ITS. Given
the ability of RNN-based models, particularly Gated Recurrent Unit (GRU), to
capture the temporal long-term dependencies in time series, coupled with
dynamic nature of traffic data, GRU is an applicable choice for estimation of
missing values in ITS. As such, the authors in [4] incorporate pattern of
missing data into RNN for multivariate time series prediction with missing
values. Moreover, a bidirectional and unidirectional Long Short Term Memory
(LSTM) network has been used in [5] to predict network-wide traffic speed for
one future timestamp. Previous studies [6] demonstrated the superiority of
both LSTM unit and GRU over the traditional RNN unit. Based on their
experiments, GRU can outperform LSTM in terms of convergence in CPU time,
parameter updates, and generalization.

From another perspective, both statistical and ML-based techniques can be
roughly divided into prediction-based methods, interpolation-based methods,
imputation-based methods, and matrix completion-based methods [7, 1].
Concerning prediction-based methods, for each missing data point, a predicted
value is calculated by using the extracted method from historical data [8].
Interpolation-based methods utilize temporal characteristics of data to
estimate the missing values [9], [8]. On the other hand, imputation-based
methods such as [10, 1] use spatial characteristics of the data by leveraging
traffic data of the adjacent roads or other roads with a similar flow
variation within the same time slot to fill in the missing values. Other
recent works, e.g., matrix-completion based methods [11, 12, 13, 14] utilize
both the temporal as well as the spatial characteristics in the data to
estimate the missing points. The method requires synchronized inputs from all
sensors [7]. This requirement is less likely satisfiable in ITS. Since the
average speed of different roads are mostly recorded only at the time of
congestion, and not all segments experience the same level of congestion
simultaneously.

Prediction-based methods do not take advantage of the subsequent sequence of
traffic measurements that follow the timestamp where there is a missing value
[3]. Interpolation-based and imputation-based methods only utilize temporal or
spatial characteristics of the data, respectively, and ignore the benefit of
using both dimensions at the same time. In summary, studying missing data
analysis in ITS is under-developed. Therefore, the focus of our paper is to
select an approach based on the spatio-temporal features of the traffic
dataset. As such, we rely on a novel neural network-based architecture called
Multi-directional Recurrent Neural Network (M-RNN), inspired by [7]. The
advantages of M-RNN for missing data estimation can be summarized as follows:
1) The architecture exploits the correlation within the time sequences of
multivariate features associated with a road segment as well as the
correlation among multiple features of the segment through using Bidirectional
GRU [6] and fully connected layer, respectively. 2) Bi-GRU captures both
forward and backward dependencies in each data stream. 3) The model utilizes
deep structure GRU (with several hidden layers) which has a higher level of
representation capability of the data stream [15] [5]. 4) The model adopts a
mechanism to deal with different sampling rate in case of data heterogeneity.
To the best of our knowledge, this is the first time that bi-directional GRU
has been used as part of deep learning-based model to estimate the missing
multivariate features of traffic data stream in ITS. We examine the results of
M-RNN under different conditions and compare the performance to the ideal
counterpart solutions. The rest of the paper is organized as follows. In
subsection II-A, characteristics of our utilized traffic dataset are described
and compared to a publicly available medical dataset used in [7]. We present
the problem formulation and our solution approach in subsection II-B and II-C,
respectively. Then, implementation results are illustrated in Sections III,
and we conclude in Section IV.

##  II System Setup

In order to facilitate the discussion of our proposed method to our traffic
dataset, we first adjust the problem formulation provided in [7] to ITS. In
the rest of the paper, we refer to TomTom traffic dataset [16] as TT dataset.
TT dataset consists of $N$ road segments. Each road segment is specified by
geographic coordinates of its starting and ending points. There exist D
streams of multivariate time series-based measurements (average speed and
travel time) of length T that consist of a timestamp $t$ and measurements $x$
for each road segment $n$, where $x_{t}^{d}(n)$ represents actual measurement
of measurement stream $d$ at timestamp $t$ for a particular road segment $n$.
Additionally, $L_{d}(n)$ is defined as the length of a sequence of data stream
$d$ belonging to road segment $n$, where the measurements are conducted. Each
sample is identified as
${x_{t}^{d_{1}}(n),x_{t}^{d_{2}}(n),...,x_{t}^{d_{m}}(n)}$, where m is the
number of features for a road segment. The time interval between two
consecutive timestamps are usually not equal ($t_{m+1}-t_{m}\neq
t_{n+1}-t_{n}$). Timestamps in a sequence are sorted in ascending order
$(t_{n}>t_{n-1})$. Generally, there could be some values in each stream that
are not observed and considered as missing.

Figure 1: System Pipeline for ITS in Our Setup

###  II-A Dataset

The TT dataset contains space mean speed 111Space mean speed is defined as the
harmonic mean of speeds passing a point during a period of time. It also
equals the average speeds over a length of roadway. [17] and average travel
time during peak congestion for several hundreds of approximately one
kilometer long, road segments across the Greater Toronto Area. In contrast to
most data sources used for traffic parameter estimation, the TT dataset
includes the traffic measurements for highways as well as signalized road
segments. The measurements are collected on a minute basis during congestion,
where the average space mean speed is less than $70\%$ of vehicular speed
during free-flow conditions. Therefore, the collected per-minute measurements
do not contain a value for every road segment. We select a three-hour interval
from 4:30pm to 7:30pm on 8 September 2017 which is expected to have a high
proportion of collected records. During this interval, we select road segments
with a significant number of mutual timestamps where measurements for a
sufficient number of the segments are conducted. There should be a trade-off
among the number of road segments $N$ and $L_{d}(n)$. Groups of neighbouring
road segments in a traffic network are usually influenced by each other in a
short period and thus, experience higher number of mutual congestion
intervals. Road segments that are far apart from centres of congestion are
less likely to share the same congestion period with the underlying segments
and consequently have a lower potential to be selected as samples for our
experiment. Therefore, the higher the $L_{d}(n)$ of mutually congested
interval, the lower the number of road segments $N$.

There are two strongly correlated features in the TT dataset: average speed
(${d_{1}}$) and travel time (${d_{2}}$). M-RNN takes advantage of the
correlation between the time values of a particular data stream $d$ associated
with a road segment $n$, as well as the correlation across the streams
(${d_{1}}$) and (${d_{2}}$) of the underlying road $n$, where
$L_{d_{1}}(n)=L_{d_{2}}(n)=L_{d}(n)$. We demonstrate the performance of our
results with varying numbers of samples $N$ and $L_{d}(n)$. We assume that
data is Missing at Random (MAR), which is a reasonably valid assumption in our
scenario. In the case of MAR, the missingness mechanism does not depend on
unobserved data, and thus the underlying mechanism can be ignored when
estimating these values [18].

###  II-B Missing Data Presentation and Estimation

Our system pipeline is illustrated in Fig. 1. Data is collected from several
sensors, e.g., loop detectors [19], cameras on a minute basis. Next, we sort
the data into a series of two-dimensional arrays. Each array presents
measurements that correspond to a road segment $n$. Each row consists of
$x_{t}^{d_{1}},x_{t}^{d_{2}},..,$ and each column shows
$x_{t^{\prime}}^{d}(n)$, where $t^{\prime}=1,2,..,L_{d}(n)$.

In general, the collected data may come from heterogeneous sensors, and the
corresponding measurements can be recorded on a different aggregation level.
Therefore, we demonstrate three forms of two-dimensional arrays to highlight
that the method is capable of handling all the cases. S1 can be a
representative of homogeneous data that consists of a large number of $D$ and
low-frequency measurements (a small number of $L_{D}(n)$). The number of $D$
and $L_{D}(n)$ depicted in Fig. 1 does not indicate the actual length of
features and time series, respectively, and is just used for comparison among
the three instances. S2 indicates heterogeneous data where the records for
different stream of a road segment $n$ may come from multiple sources and
subsequently with different sampling frequencies. The third instance, S3,
demonstrates homogeneous data with small $D$ and large $L_{D}(n)$, compared to
S1 and S2. Our study includes S3. Moreover, the multiplication sign inside the
circle in box 2 of Fig. 1 indicates missing data points for all three
instances of input arrays.

The underlying extracted arrays are the input to the pre-processing block. In
this step, we need to produce three arrays in order to use as an input to the
AI engine: $Z(n),$ $M(n)$ and $\Delta(n)$. $Z(n)$ consists of $x_{t}^{d}(n)$
for $d=1,2,..,D$ and $t=1,2,..,L_{d}(n)$ for each road segment $n$. We set
$x_{t}^{d}$ equal to zero, where the data point is missing. $M(n)$ is an array
containing 0s and 1s that indicate the coordinates of missing and observed
records, respectively, corresponding to array $Z(n).$ As for $\Delta(n)$, each
element of the array, $\delta_{t}^{d}(n)$, is defined to be the actual time
passed from timestamp $t$ since the last measurement is conducted for each
road segment $n$. More detailed information on how to calculate
$\delta_{t}^{d}(n)$ can be found in [7]. The $\Delta(n)$ is defined to handle
different sampling rate associated with data heterogeneity. The triplet of
generated arrays will then proceed to the AI engine where the M-RNN will be
applied, the missing records will be estimated, and the respective RMSE will
be calculated. The entire dataset $\mathcal{D}$ consists of the sequence of
timestamps and the streams of measurements for all road segments that are
sampled from an unknown distribution $\mathcal{F}$, and is mathematically
represented as follows in equation 1.

$\displaystyle\mathcal{D}=\sum_{n=1}^{N}\\{\mathcal{X}(n),\mathcal{S}(n)\\},$
(1)

where $\mathcal{X}(n)=\\{x_{t}^{d}(n),\forall d,\forall t,\forall n\\}$ and
$\mathcal{S}(n)=\\{t1,t2,...,L_{d}(n),\forall n\\}$.

Our goal is to find the best estimate ($\hat{x}_{t}^{d}$), with minimum RMSE
for a particular missing measurement at time $t$, where the estimate form and
loss function $\mathcal{L}(x_{t}^{d},\hat{x}_{t}^{d})$ to be defined as
follows:

$\begin{split}&\hat{x}_{t}^{d}=f_{t}^{d}(\mathcal{X},\mathcal{S})\\\
&\mathcal{L}(x_{t}^{d},\hat{x}_{t}^{d})=(\hat{x}_{t}^{d}-x_{t}^{d})^{2}\end{split}$
(2)

Then, the optimization problem is to find the function $f_{d}^{t}$ that solves
the following equation [7].

$\displaystyle\min_{\text{f}}\operatorname{\mathbb{E}}_{\mathcal{F}}\left[\sum_{t=1}^{T}\sum_{d=1}^{D}(1-m_{t}^{d})\mathcal{L}(\mathcal{X}_{t}^{d},\widehat{\mathcal{X}}_{t}^{d})\right]$
$\displaystyle=\min_{\text{f}}\operatorname{\mathbb{E}}_{\mathcal{F}}\left[\sum_{t=1}^{T}\sum_{d=1}^{D}(1-m_{t}^{d})(x_{t}^{d}-f_{t}^{d}(\mathcal{X},\mathcal{S}))^{2}\right],$
(3)

where $\text{f},\mathcal{F},\hat{x}$ are desired estimator function, unknown
distribution which the measurements are sampled from, and the estimated value
for the missing point respectively. Besides, $m$ is an element of the array
$\mathbf{M}$ which is defined in the pre-processing box of Fig. 1.

###  II-C Multi-directional Recurrent Neural Network (M-RNN)

Our objective is to minimize the RMSE of each estimated value
$\hat{x}_{t}^{d}$ with respect to the missing value $x_{t}^{d}$ for each road
segment $n$ that is sampled from TT dataset. In contrast to interpolation-
based and imputation-based methods, M-RNN utilizes the correlation from within
the stream and the correlation across the streams of average speed and travel
time in TT dataset.

Fig. 2 illustrates the M-RNN architecture in the time domain. It comprises of
one interpolation block and one imputation block which the former comes before
the latter in order to improve the accuracy of estimation [7]. The input to
interpolation block consists of feature vector $x$, which are individual
columns of array $Z$ explained in section II-B. The output of the block
(${x}_{t}^{d},\forall d$) is built using a Bi-GRU, where its input to forward,
and backward hidden states comes from t – 1 and t + 1 respectively. The
imputation block is constructed by one fully connected layer; both blocks are
trained simultaneously and the output of imputation block, $\hat{x}_{t}$ is
the final estimate of the missing measurement at time $t$. Estimation of
missing values using M-RNN can be implemented in two ways: 1) single
imputation, 2) multiple imputations. Imputing data points using multiple
imputations is applied to reduce uncertainty by generating multiple imputed
values. Due to the negligible uncertainty level in our data, and in order to
reduce complexity, we select to run our experiments under single imputation.
Once $\hat{x}_{t}^{d}$ is estimated, the RMSE will be calculated through
$\mathcal{L}(x_{t}^{d},\hat{x}_{t}^{d})$. The total loss for the entire
dataset $\mathcal{D}$ is calculated based on equation II-C [7], where $L_{n}$
and $m_{t}^{d}(n)$ are the length of time sequence for road segment $n$, and
an element of the mask array $\mathbf{M}$, corresponding to timestamp $t$ and
road $n$, respectively.

$\displaystyle\mathcal{L}(\\{\widehat{\boldsymbol{X}}_{t}^{d},\boldsymbol{X}_{t}^{d}\\})=$
$\displaystyle\sum_{n=1}^{N}\left[\frac{\sum_{t=1}^{L_{n}}\sum_{d=1}^{D}m_{t}^{d}(n)\times(\hat{x}_{t}^{d}(n)-x_{t}^{d}(n))^{2}}{\sum_{t=1}^{L_{n}}\sum_{d=1}^{D}m_{t}^{d}(n)}\right]$
(4)

Figure 2: M-RNN architecture in time domain [7]

##  III Performance Evaluation

We compare the performance result of M-RNN with single imputation, with two
other methods: Spline interpolation and matrix completion of [20]. Table I
illustrates the hyperparameters that are optimized in our experiments. We use
RMSE as a measure of estimation accuracy of the missing values on TT dataset.
In the pre-processing step, we select to remove missing points associated to
each feature independently according to probability $\tau$, also named as
missing threshold. Next, we apply it to all road segments under experiment.

Before moving forward, it is worthwhile to compare the datasets in [7], where
the M-RNN is initially applied, and TT dataset. In [7], the authors applied
their model on several publicly available medical datasets, including MIMIC-
III [21] and Deterioration [22]. In terms of data collection method,
representation model, and temporal condition, there are differences between
the TT dataset and the datasets in [7]. The TT is a complete dataset
consisting of historical aggregated (per minute) time-series-based
measurements, whereas the medical datasets have a lower level of aggregation,
where features are measured less frequently, every few weeks. Moreover, there
is a significant level of sparsity in these medical datasets; many
measurements were not conducted, which consequently leads to high missing
rates. Medical datasets, on the other hand, have an enormous number of
samples. 20000-30000 patients are involved in their experiments. Each patient
has between 20-40 recorded features that are far larger than the two features
in our case. However, we note some additional features might exist in other
traffic datasets, e.g., time mean speed, traffic flow, density [23], [17],
occupancy percentile [23], volume per lane per mile, and may improve the
estimation accuracy of missing points. Another difference between the medical
datasets and TT dataset is the level of uncertainty. There is a high amount of
uncertainty in medical measurements [7] due to individual, systematic and
clinical factors. In the TT dataset, the uncertainty level is negligible.
There exists a feature in our dataset that indicates the quality of each
record, given as a percentage. All utilized instants in our study have values
higher than $95\%$ of the underlying feature.

TABLE I: Parameters and optimized hyperparameters used in our experiments Parameter |  Value
---|---
Number of road segments (samples) |  382
Number of data streams |  2
Length of time sequence |  85
Optimization method |  Adam [24]
Depth of the network |  4
Number of layers per block |  2
Number of hidden nodes per each layer in interpolation block |  2
Number of hidden nodes per each layer in imputation block |  2
TABLE II: Performance evaluation of M-RNN vs. counterpart methods Category | Algorithm | $RMSE_{x}$ |  $\hat{\eta}_{M-RNN/X}$ $(\%)$
---|---|---|---
M-RNN | M-RNN [7] | 0.01278 | -
Interpolation | Spline | 0.01938 | 51.64
Matrix completion | [20] | 0.02021 | 58.13

Table II shows the average RMSE for all three methods, where we use 5 cross-
fold validation. We have defined $\hat{\eta}_{M-RNN/X}$ in equation 5 as a
means to calculate the improvement made by M-RNN approach in terms of RMSE
reduction compared to the existing method.

$\displaystyle\hat{\eta}_{M-RNN/X}=\frac{\left|RMSE_{M-RNN}-RMSE_{X}\right|}{RMSE_{M-RNN}}\times
100,$ (5)

where $\left|\ast\right|$ indicates absolute value of $\ast$. From table II,
M-RNN significantly outperforms the other two methods.The second-best
performer is the Spline interpolation, since TomTom has frequent measurements
coupled with a strong correlation among features. We do not compare M-RNN to
imputation-based methods, since these methods perform well in the presence of
high dimensional data, and there are only two features in TT dataset. We have
conducted further experiments to examine the proposed method under two
probability distribution functions of missing data, increasing variance of
missing points under Gaussian distribution, increasing the missing threshold
($\tau$), decreasing the number of $L_{D}(n)$ per road segment $n$ and
decreasing the number of $N$. The results are illustrated in figures 3\- 5.

Fig. 3 illustrates the performance of M-RNN for various values of $\tau$.
$\tau$ indicates the probability for a data point to be marked as missing. As
can be seen in the plot, M-RNN is remarkably robust to the changes in $\tau$.
As $\tau$ increases, the rate of improvements of RMSE in M-RNN
($\hat{\eta}_{\scriptscriptstyle M-RNN/X}$) increases compared to Spline
interpolation.

Fig. 4 reveals the evaluation result of the model versus number of
$L_{d}(n)=L$. It is highlighted that the performance of M-RNN downgrades as
the number of $L_{d}(n)$ decreases, since the interpolation block of M-RNN in
Fig. 2 exploits the correlation among successive measurements associated with
a single road. Therefore, the underlying block performs more effectively in
the presence of a high sampling rate.

Fig. 5 illustrates the functionality of our trained model under different
numbers of road segments ($N$). The RMSE is an ascending function of number of
segments $N$, as the method requires sufficient number of samples to learn the
parameters. From Fig. 5, for $\mathbf{n}<275$ (vertical line), both Spline
interpolation and matrix completion outperform M-RNN. It is noted that the
underlying number depends on the unique characteristics of the dataset,
including the number $D$ in conjunction with the intra-stream and inter-stream
correlation plus the number of samples $N$ and more importantly, the way we
optimize the model.

Figure 3: Estimation accuracy versus missing threshold ($\tau$) Figure 4:
Estimation accuracy versus number of measurements per segment ($L_{n}$) Figure
5: Estimation accuracy versus number of road segments ($N$)

##  IV Conclusion

Traffic flow estimation is of high importance in intelligent transportation
system. However, the challenge of missing data is inevitable for all data
collection methods due to several reasons. Therefore, an accurate estimation
of missing values is essential so that we can take full advantage of our data.
In this paper, we exploit a deep learning based approach, M-RNN, for
estimating missing data points on TomTom traffic dataset that consists of
spatio-temporal features for several hundred segments in GTA. The utilized
method takes advantage of inter-stream and intra-stream correlations in the
data. Several experiments of the method under various conditions demonstrate
significant performance improvement in terms of RMSE reduction, compared to
Spline interpolation and matrix completion. We will utilize M-RNN on other ITS
datasets, and also extend our work to address cases, where data is missing not
at random (MNAR) in future works.

## References

  * [1] Q. Shang, Z. Yang, S. Gao, and D. Tan, “An imputation method for missing traffic data based on fcm optimized by pso-svr,” _Journal of Advanced Transportation_ , vol. 2018, 2018.
  * [2] C. M. Bishop, “Bayesian pca,” in _Advances in neural information processing systems_ , 1999, pp. 382–388.
  * [3] M. N. Nounou, B. R. Bakshi, P. K. Goel, and X. Shen, “Bayesian principal component analysis,” _Journal of Chemometrics: A Journal of the Chemometrics Society_ , vol. 16, no. 11, pp. 576–595, November 2002.
  * [4] Z. Che, S. Purushotham, K. Cho, D. Sontag, and Y. Liu, “Recurrent neural networks for multivariate time series with missing values,” _Scientific reports_ , vol. 8, no. 1, pp. 1–12, 2018.
  * [5] Z. Cui, R. Ke, Z. Pu, and Y. Wang, “Deep bidirectional and unidirectional lstm recurrent neural network for network-wide traffic speed prediction,” _arXiv preprint arXiv:1801.02143_ , 2018.
  * [6] J. Chung, C. Gulcehre, K. Cho, and Y. Bengio, “Empirical evaluation of gated recurrent neural networks on sequence modeling,” _arXiv preprint arXiv:1412.3555_ , 2014.
  * [7] J. Yoon, W. R. Zame, and M. van der Schaar, “Estimating missing data in temporal data streams using multi-directional recurrent neural networks,” _IEEE Transactions on Biomedical Engineering_ , vol. 66, no. 5, pp. 1477–1490, March 2018.
  * [8] M. Zhong, P. Lingras, and S. Sharma, “Estimation of missing traffic counts using factor, genetic, neural, and regression techniques,” _Transportation Research Part C: Emerging Technologies_ , vol. 12, no. 2, pp. 139–166, April 2004.
  * [9] J. Van Lint, S. Hoogendoorn, and H. J. van Zuylen, “Accurate freeway travel time prediction with state-space neural networks under missing data,” _Transportation Research Part C: Emerging Technologies_ , vol. 13, no. 5-6, pp. 347–369, October 2005.
  * [10] L. Qu, Y. Zhang, J. Hu, L. Jia, and L. Li, “A bpca based missing value imputing method for traffic flow volume data,” in _2008 IEEE Intelligent Vehicles Symposium_. IEEE, June 2008, pp. 985–990.
  * [11] H. Tan, G. Feng, J. Feng, W. Wang, Y.-J. Zhang, and F. Li, “A tensor-based method for missing traffic data completion,” _Transportation Research Part C: Emerging Technologies_ , vol. 28, pp. 15–27, March 2013.
  * [12] L. Li, Y. Li, and Z. Li, “Efficient missing data imputing for traffic flow by considering temporal and spatial dependence,” _Transportation research part C: emerging technologies_ , vol. 34, pp. 108–120, September 2013.
  * [13] B. Ran, H. Tan, Y. Wu, and P. J. Jin, “Tensor based missing traffic data completion with spatial–temporal correlation,” _Physica A: Statistical Mechanics and its Applications_ , vol. 446, pp. 54–63, March 2016.
  * [14] H. Tan, J. Feng, Z. Chen, F. Yang, and W. Wang, “Low multilinear rank approximation of tensors and application in missing traffic data,” _Advances in Mechanical Engineering_ , vol. 6, p. 157597, February 2014.
  * [15] A. Graves, N. Jaitly, and A.-r. Mohamed, “Hybrid speech recognition with deep bidirectional lstm,” in _2013 IEEE workshop on automatic speech recognition and understanding_. IEEE, 2013, pp. 273–278.
  * [16] H. T. H. TomTom, “Traffictm and iq routestm data provides the very best routing,” _White Paper_ , 2010.
  * [17] D. Helbing, “Fundamentals of traffic flow,” _Physical Review E_ , vol. 55, no. 3, p. 3735, March 1997.
  * [18] D. B. Rubin, “Inference and missing data,” _Biometrika_ , vol. 63, no. 3, pp. 581–592, December 1976.
  * [19] D. L. Gerlough and M. J. Huber, “Traffic flow theory,” Tech. Rep., 1976.
  * [20] R. Mazumder, T. Hastie, and R. Tibshirani, “Spectral regularization algorithms for learning large incomplete matrices,” _Journal of machine learning research_ , vol. 11, no. Aug, pp. 2287–2322, August 2010.
  * [21] A. E. Johnson, T. J. Pollard, L. Shen, H. L. Li-wei, M. Feng, M. Ghassemi, B. Moody, P. Szolovits, L. A. Celi, and R. G. Mark, “Mimic-iii, a freely accessible critical care database,” _Scientific data_ , vol. 3, p. 160035, May 2016.
  * [22] A. M. Alaa, J. Yoon, S. Hu, and M. Van der Schaar, “Personalized risk scoring for critical care prognosis using mixtures of gaussian processes,” _IEEE Transactions on Biomedical Engineering_ , vol. 65, no. 1, pp. 207–218, April 2017.
  * [23] A. D. May, _Traffic flow fundamentals_ , 1990.
  * [24] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.


# Ex-post implementation with interdependent values 111We are thankful to
Debasis Mishra for his invaluable guidance and support. We also thank Arunava
Sen and Stephen Morris for insightful comments.

Saurav Goyal 222Economics and Planning Unit, Indian Statistical Institute
(Delhi) Aroon Narayanan 333Department of Economics, MIT

###### Abstract

We characterize ex-post implementable allocation rules for single object
auctions under quasi-linear preferences with convex interdependent value
functions. We show that requiring ex-post implementability is equivalent to
requiring that the allocation rule must satisfy a condition that we call
eventual monotonicity (EM), which is a weakening of monotonicity, a familiar
condition used to characterize dominant strategy implementation.

Keywords: ex-post implementation, interdependent value auction, eventual
monotonicity, optimal auction

JEL Classification: D44

##  1 Introduction

We study the single object auction model when agents have interdependent
values. In our model, each agent $i$ has a private signal $s_{i}$ about her
value and her (ex-post) value for the object depends on the private signals of
all the $n$ agents: $v_{i}(s_{1},\ldots,s_{n})$. The only assumptions we make
on the value function $v_{i}$ is that it is convex and non-decreasing in the
signal $s_{i}$. Thus, $v_{i}$ allows for a rich class of interdependence: the
additive model of [3]; the max model of [1]; and the private values model in
[8]. We define a new property for allocation rules that we call eventual
monotonicity (EM). We show that an allocation rule is ex-post implementable
(i.e., there exists a transfer rule such that the allocation rule and the
transfer rule form an ex-post incentive compatible mechanism) if and only if
it satisfies eventual monotonicity.

This novel property is a weakening of the monotonicity property that
characterizes dominant strategy implementation [8]. Towards understanding this
property, let $\ell_{v_{i}}(s_{-i})$ denote the supremum of all signals of
agent $i$ for which $v_{i}$ takes the same value as it does when $i$ has the
lowest possible signal.444We assume that the signal space for each agent is an
interval, so this supremum is also over an interval. Eventual monotonicity is
then the following requirement: for any $s_{-i}$ and any pair of signals
$s_{i}>s^{\prime}_{i}$ for agent $i$ with $s_{i}>\ell_{v_{i}}(s_{-i})$, the
allocation probablity of agent $i$ at $s^{\prime}_{i}$ is no less than the
allocation probability at $s_{i}$. This requirement captures two conditions.
First, the allocation probability of agent $i$ must be increasing beyond
$\ell_{v_{i}}(s_{-i})$. Two, while it does not need to be increasing below
$\ell_{v_{i}}(s_{-i})$, it must be the case that the allocation probability
for any type above $\ell_{v_{i}}(s_{-i})$ is more than the allocation
probability for any type below $\ell_{v_{i}}(s_{-i})$. See Figure 1 below for
an illustration.

Extending Myerson’s monotonicity characterization to interdependent values
models may be useful in solving optimal auction problems in these models with
ex-post incentive compatibility as the solution concept. The interdependent
values model is considered to be a model that reflects many realistic problems
where agents have imperfect information about values: [7, 3, 1] contain
several motivating examples.555[1] describes a setting where an agent’s signal
denotes her private use. If an agent comes to know of various uses of the
object, she makes the best use of it. This is captured in their max model, a
common value model, given by $v_{i}(s_{1},\ldots,s_{n})=\max s_{j}$. Our
results cover their model.

Our characterization and a payment equivalence formula provide a handy method
of deriving an expression for the revenue of the revenue-maximizing mechanism
in terms of maximizing an objective function within the class of eventually
monotone allocation rules. The tractability of deriving the exact optimal EPIC
mechanism in general will depend on the form of the value functions. We show
that for strictly increasing value functions, the usual Myersonian approach
works. We are also able to show that the BIC and IIR inclusive posted price
mechanism studied in [3], and shown to be optimal in [1], can in fact be
achieved in expectation by an EPIC and EPIR mechanism using the
characterization that we develop, under the condition that the object must be
sold.

Relation to the literature. Much of the literature on interdependent values
model focuses on Bayesian incentive compatibility (BIC) and interim individual
rationality (IIR). However, BIC has been criticized for its reliance on the
specific priors of the agents, and hence raises questions of robustness. We
use the stronger and more robust concepts of ex-post incentive compatibility
(EPIC) and ex-post individual rationality (EPIR) instead. While many
interesting but specific models of interdependent values have been studied, a
general characterization of ex-post implementability paralleling that for
private values has proved elusive, partly because of the difficulty in
identifying the set of binding constraints. [6] shows that the Vickrey auction
may not be ex-post implementable without the single-crossing property for the
value functions 666The single-crossing property ensures that the agent with
the highest signal is also the agent with the highest value, which ensures
that efficient auctions produce monotonic, and hence implementable, allocation
rules. Our result is orthogonal - we show that under convexity there is an
exact characterization of implementable rules.. [5] demonstrates that with
multidimensional types and interdependent values, there are no non-trivial
(non-constant) ex-post implementable deterministic social choice functions,
while [2] shows that this is not the case for private values. We fill this gap
in the literature by providing a characterization of ex-post implementability
in models of interdependent values.

The paper closest to ours is [9], which provides sufficient conditions under
which allocation rules are ex-post implementable. Building on a result from
[4], they show that under increasing differences across signals, monotonicity
of the allocation rule in own signal is sufficient for ex-post implementation.
However they do not provide a characterization.

The rest of the paper proceeds as follows. Section 2 specifies the setting of
the problem. Section 3 builds the characterization. Section 4 explores the
problem of revenue maximization, both in general and in specific models.

##  2 Model

Let $N=\\{1,2,...,n\\}$ be the set of agents. There is one good to be
allocated. The agents have quasi-linear interdependent preferences for the
good. Each agent receives signals from
$S_{i}=[\underline{s_{i}},\overline{s_{i}}]$. Let $v_{i}:S^{n}\to\mathbb{R}$
be the valuation function of each agent $i$. $v_{i}(s_{i},s_{-i})\equiv
v_{i}(s_{1},s_{2},...,s_{n})$ denotes the valuation of agent $i$ at signal
profile $(s_{1},s_{2},...,s_{n})$. We assume that $v_{i}(s_{i},s_{-i})$ is
convex, continuous and non-decreasing in $s_{i}$ on
$[\underline{s_{i}},\overline{s_{i}}]$, for all $i$. For every $i\in N$ and
for every $s_{-i}$, define

$\displaystyle\ell_{v_{i}}(s_{-i})$ $\displaystyle:=\sup\\{s_{i}\in
S_{i}:v_{i}(s_{i},s_{-i})=v_{i}(\underline{s}_{i},s_{-i})\\}$

Since $v_{i}$ is convex, continuous, and non-decreasing,
$\ell_{v_{i}}(s_{-i})$ is the supremum of the interval where $v_{i}$ is
constant. For instance, in the max value function studied in [1],
$v_{i}(s_{i},s_{-i})=\max_{j}s_{j}$ and $\ell_{v_{i}}(s_{-i})=\max_{j\neq
i}s_{j}$.

We invoke the revelation principle to focus only on direct mechanisms. Thus a
mechanism in this setting is the tuple $(q,p)$ where $q_{i}:S^{n}\to[0,1]$ is
the allocation rule for agent $i$ and $p_{i}:S^{n}\to\mathbb{R}$ is the
payment rule for agent $i$.

######  Definition 1.

An allocation rule $q$ is ex-post implementable if there exists a payment rule
$p$ such that the following holds $\forall i$ $\forall s_{-i}$:

$u_{i}(s_{i},s_{-i})\geq
u_{i}(s_{i}^{\prime},s_{-i})+[v_{i}(s_{i},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i})]q_{i}(s_{i}^{\prime},s_{-i}),\
\forall\ s_{i},s_{i}^{\prime}$

where
$u_{i}(s_{i},s_{-i})=q_{i}(s_{i},s_{-i})v_{i}(s_{i},s_{-i})-p_{i}(s_{i},s_{-i})$
is the net payoff function for agent $i$. In this case, we say that the
mechanism $(q,p)$ is ex-post incentive compatible (EPIC).

##  3 Eventual monotonicity and ex-post implementation

Our main result characterizes ex-post implementable allocation rules. The
approach we take to derive this result is fairly standard - we derive a
necessary condition and then show that it also turns out to be sufficient.
Here the appropriate necessary condition is a suitable modification of
monotonicity.

######  Definition 2.

The allocation rule $q$ is eventually monotone if $\forall i$, $\forall
s_{-i}$ and for every $s_{i}>s^{\prime}_{i}$ with
$s_{i}>\ell_{v_{i}}(s_{-i})$, we have

$q_{i}(s_{i},s_{-i})\geq q_{i}(s^{\prime}_{i},s_{-i})$

Figure 1 illustrates what an EM rule might look like.

Figure 1: An eventually monotone rule

Now we are ready to state and prove our main result.

######  Theorem 1.

An allocation rule $q$ is ex-post implementable if and only if it is
eventually monotone.

It is direct to note that EPIC is equivalent to dominant strategy incentive
compatibility (DSIC) under private values, and that eventual monotonicity is
just monotonocity. Hence, we obtain the standard characterization of dominant-
strategy implementable rules as a corollary of the above theorem.

##  4 Optimal mechanisms

In this section, we assume that the signals of the agents are independent and
identically distributed, each drawn from some distribution $F$ with full
support on $S$. We will first derive a condition for revenue maximization, and
then explore its implications for some value functions.

Building on Theorem 1, we get the following characterization of EPIC
mechanisms.

######  Proposition 1.

A mechanism $(q,p)$ is ex-post incentive compatible if and only if $q$ is
eventually monotone and $p$ is given by 777Note that $v_{i}$ need not be
differentiable with respect to $s_{i}$ everywhere, but convexity ensures that
it always has a sub-gradient, which is equal to its derivative whenever the
latter exists (which is almost everywhere). We write $\frac{\partial
v_{i}(x,s_{-i})}{\partial x}$ to denote the derivative of
$v_{i}(\cdot,s_{-i})$ with respect to the first argument at $x$ whenever it is
differentiable. Else, it is some selection from the subgradient of
$v_{i}(\cdot,s_{-i})$ at $x$.:

$\displaystyle p_{i}(s_{i},s_{-i})=\ $ $\displaystyle
p_{i}(\underline{s},s_{-i})-q_{i}(\underline{s},s_{-i})v_{i}(\underline{s},s_{-i})$
$\displaystyle+q_{i}(s_{i},s_{-i})v_{i}(s_{i},s_{-i})-\int^{s_{i}}_{\underline{s}}\frac{\partial
v_{i}(x,s_{-i})}{\partial x}q_{i}(x,s_{-i})\ dx$

The following generalization of the private values version of virtual value is
well-known in the literature.

######  Definition 3.

The virtual value of an agent at a signal profile is given by

$J_{i}(s_{i},s_{-i})=v_{i}(s_{i},s_{-i})-\frac{1-F(s_{i})}{f(s_{i})}\frac{\partial
v_{i}(s_{i},s_{-i})}{\partial s_{i}}$

Also, we consider rules that ensure that the agents continue to want to
participate ex-post.

######  Definition 4.

A mechanism is ex-post individually rational (EPIR) if the following holds
$\forall i$ $\forall s_{i}$ $\forall s_{-i}$:

$u_{i}(s_{i},s_{-i})\geq 0$

We say that a mechanism $(q,p)$ is optimal if it is EPIC and EPIR and
generates more expected revenue than any other EPIC and EPIR mechanism. We
then have the following formula for the revenue in an optimal mechanism.

######  Lemma 1.

The optimal mechanism maximizes

$\int_{s\in S^{n}}\Bigl{[}\sum_{i\in N}J_{i}(s)q_{i}(s)\Bigr{]}\ f(s)\ ds$

within the class of eventually monotone allocation rules.

###  4.1 Strictly increasing value functions

When the value functions are strictly increasing in each agent’s own signal,
then it is direct to observe that EM reduces to monotonicity. In this case the
optimization problem identified in Lemma 1 can be solved by the standard
ironing technique of [8]. We state this observation in the following
proposition:

######  Proposition 2.

Suppose each agent’s value function is strictly increasing in her own signal.
Then, the optimal mechanism allocates the object to the agent with the highest
ironed virtual value, and charges the payments that ex-post implements this
allocation rule.

Note also that the case of private values is covered by this result.

###  4.2 Additive signals

Using the framework developed above, we derive a result for the additive
signals model, which is closely related to the one studied in [3]. In this
model, the value functions are given by
$v_{i}(s_{1},s_{2},...,s_{n})=c_{1}s_{1}+c_{2}s_{2}+...+c_{n}s_{n}$ with
$c_{i}\geq 0$ for all $i$. An example of such a model is the simple additive
value case - where each agent’s value for the object is the simple sum of the
signals of each agent. Denote by $c_{i}\frac{1-F(s_{i})}{f(s_{i})}$ the
adjusted hazard rate of agent $i$.

######  Proposition 3.

Suppose the distribution $F$ of the signals satisfies the monotone hazard rate
property. Then a mechanism is optimal if and only if at every signal profile
it allocates the object with probability $1$ to the agent with the lowest
adjusted hazard rate if that agent’s virtual value is non-negative and does
not allocate the object otherwise.

An interesting corollary of this theorem is the following: when the weights
$c_{i}$ are the same for every agent (i.e. the simple additive values case)
and the distribution of signals has a monotone hazard rate, the mechanism
allocates the object to the agent with the highest signal. This is because the
agent with the lowest adjusted hazard rate at any profile must also have the
highest signal, by the monotone hazard rate assumption.

###  4.3 Max function

[1] derive the optimal Bayesian incentive compatible (BIC) and interim
individually rational (IIR) mechanism for the maximum value function,
$v_{i}(s_{1},s_{2},...,s_{n})=\max(s_{1},s_{2},...,s_{n})$. We use our
framework to identify the optimal mechanism for this form of interdependence,
under the assumption that the object must be sold.

######  Proposition 4.

When it is mandatory to sell the object, mechanisms that allocate the object
with probability $c_{i}$ to agent $i$ at all signal profiles, for some $c_{i}$
such that $\sum_{i}c_{i}=1$, are optimal.

Each of these optimal mechanisms guarantees the same revenue in expectation as
the BIC and IIR equal allocation rule of [1], which allocates with probability
$\frac{1}{n}$ to each agent at every profile. Since their optimal mechanism is
not ex-post IR, our result identifies an ex-post IR implementation of their
mechanism.

## References

  * [1] Dirk Bergemann, Benjamin Brooks and Stephen Morris  “Countering the winner’s curse: Optimal auction design in a common value model”  In _Theoretical Economics_ 15.4, 2020, pp. 1399–1434  DOI: https://doi.org/10.3982/TE3797
  * [2] Sushil Bikhchandani  “Ex post implementation in environments with private goods”  In _Theoretical Economics_ 1, 2006, pp. 369–393
  * [3] Jeremy Bulow and Paul Klemperer  “Prices and the Winner’s Curse”  In _RAND Journal of Economics_ 33.1, 2002, pp. 1–21  URL: https://ideas.repec.org/a/rje/randje/v33y2002ispringp1-21.html
  * [4] Jacques Crémer and Richard P. McLean  “Optimal Selling Strategies under Uncertainty for a Discriminating Monopolist when Demands are Interdependent”  In _Econometrica_ 53.2 [Wiley, Econometric Society], 1985, pp. 345–361  URL: http://www.jstor.org/stable/1911240
  * [5] Philippe Jehiel, Moritz Meyer-ter-Vehn, Benny Moldovanu and William R. Zame  “The Limits of ex post Implementation”  In _Econometrica_ 74.3, 2006, pp. 585–610  DOI: https://doi.org/10.1111/j.1468-0262.2006.00675.x
  * [6] Eric Maskin  “Auctions and Privatization”  In _Privatization_ J.C.B. Mohr Publisher, 1992, pp. 115–136  J.C.B. Mohr Publisher
  * [7] Paul R. Milgrom and Robert J. Weber  “A Theory of Auctions and Competitive Bidding”  In _Econometrica_ 50.5 [Wiley, Econometric Society], 1982, pp. 1089–1122  URL: http://www.jstor.org/stable/1911865
  * [8] Roger Myerson  “Optimal Auction Design”  In _Mathematics of Operations Research_ 6.1, 1981, pp. 58–73  URL: https://EconPapers.repec.org/RePEc:inm:ormoor:v:6:y:1981:i:1:p:58-73
  * [9] Levent Ülkü  “Implementation in an interdependent value framework”  In _Mathematical Social Sciences_ 68, 2014, pp. 64–70  DOI: https://doi.org/10.1016/j.mathsocsci.2014.01.002

##  Appendix A Proofs

###### Proof of Theorem 1.

Suppose $q$ is ex-post implementable. Then, there exists a payment rule $p$
such that $(q,p)$ is EPIC. Let $s_{i}^{\prime\prime}\geq s_{i}^{\prime}$. EPIC
implies

$q_{i}(s_{i}^{\prime\prime},s_{-i})v_{i}(s_{i}^{\prime\prime},s_{-i})-p_{i}(s_{i}^{\prime\prime},s_{-i})\geq
q_{i}(s_{i}^{\prime},s_{-i})v_{i}(s_{i}^{\prime\prime},s_{-i})-p_{i}(s_{i}^{\prime},s_{-i})$

and

$q_{i}(s_{i}^{\prime},s_{-i})v_{i}(s_{i}^{\prime},s_{-i})-p_{i}(s_{i}^{\prime},s_{-i})\geq
q_{i}(s_{i}^{\prime\prime},s_{-i})v_{i}(s_{i}^{\prime},s_{-i})-p_{i}(s_{i}^{\prime\prime},s_{-i})$

Adding these two together,

$(q_{i}(s_{i}^{\prime\prime},s_{-i})-q_{i}(s_{i}^{\prime},s_{-i}))(v_{i}(s_{i}^{\prime\prime},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i}))\geq
0$ (1)

Let $s_{i}^{\prime\prime}>s_{i}^{\prime}>\ell_{v_{i}}(s_{-i})\geq s_{i}$. Then
$v_{i}(s_{i}^{\prime\prime},s_{-i})>v_{i}(s_{i}^{\prime},s_{-i})>v_{i}(s_{i},s_{-i})$.
Hence by 1, we must have

$q_{i}(s_{i}^{\prime\prime},s_{-i})\geq q_{i}(s_{i}^{\prime},s_{-i})\geq
q_{i}(s_{i},s_{-i})$

Thus, $q$ must be eventually monotone.

For the converse, suppose $q$ is eventually monotone. Let $p$ be given by

$p_{i}(s_{i},s_{-i})=p_{i}(\underline{s},s_{-i})+q_{i}(s_{i},s_{-i})v_{i}(s_{i},s_{-i})-q_{i}(\underline{s},s_{-i})v_{i}(\underline{s},s_{-i})-\int^{s_{i}}_{\underline{s}}\frac{\partial
v_{i}(x,s_{-i})}{\partial x}q_{i}(x,s_{-i})\ dx$

Fix $i\in N,\ s_{-i}$, and consider $s_{i},\ s_{i}^{\prime}\in S$. We need to
prove that the following quantity is non-negative.

$\rho\coloneqq
u_{i}(s_{i},s_{-i})-u_{i}(s_{i}^{\prime},s_{-i})-[v_{i}(s_{i},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i})]q_{i}(s_{i}^{\prime},s_{-i})$
$=(q_{i}(s_{i},s_{-i})v_{i}(s_{i},s_{-i})-p_{i}(s_{i},s_{-i}))-(q_{i}(s_{i}^{\prime},s_{-i})v_{i}(s_{i},s_{-i})-p_{i}(s_{i}^{\prime},s_{-i}))$
$=\int_{\underline{s}}^{s_{i}}\frac{\partial v_{i}(x,s_{-i})}{\partial
x}q_{i}(x,s_{-i})\ dx-\int_{\underline{s}}^{s_{i}^{\prime}}\frac{\partial
v_{i}(x,s_{-i})}{\partial x}q_{i}(x,s_{-i})\ dx-
q_{i}(s_{i}^{\prime},s_{-i})[v_{i}(s_{i},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i})]$

Let us proceed by taking cases.

Case: $s_{i}\geq s_{i}^{\prime}>\ell_{v_{i}}(s_{-i})$

$\rho=\int_{s_{i}^{\prime}}^{s_{i}}\frac{\partial v_{i}(x,s_{-i})}{\partial
x}q_{i}(x,s_{-i})\ dx-
q_{i}(s_{i}^{\prime},s_{-i})[v_{i}(s_{i},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i})]$
$\geq\int_{s_{i}^{\prime}}^{s_{i}}\frac{\partial v_{i}(x,s_{-i})}{\partial
x}q_{i}(s_{i}^{\prime},s_{-i})\ dx-
q_{i}(s_{i}^{\prime},s_{-i})[v_{i}(s_{i},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i})]$
$=q_{i}(s_{i}^{\prime},s_{-i})\int_{s_{i}^{\prime}}^{s_{i}}dv_{i}(x,s_{-i})-q_{i}(s_{i}^{\prime},s_{-i})[v_{i}(s_{i},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i})]=0$

Case: $s_{i}>\ell_{v_{i}}(s_{-i})\geq s_{i}^{\prime}$

$\rho=\int_{\ell_{v_{i}}(s_{-i})}^{s_{i}}\frac{\partial
v_{i}(x,s_{-i})}{\partial x}q_{i}(x,s_{-i})\ dx-
q_{i}(s_{i}^{\prime},s_{-i})[v_{i}(s_{i},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i})]$
$\geq\int_{\ell_{v_{i}}(s_{-i})}^{s_{i}}\frac{\partial
v_{i}(x,s_{-i})}{\partial x}q_{i}(s_{i}^{\prime},s_{-i})\ dx-
q_{i}(s_{i}^{\prime},s_{-i})[v_{i}(s_{i},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i})]$
$=q_{i}(s_{i}^{\prime},s_{-i})\int_{\ell_{v_{i}}(s_{-i})}^{s_{i}}dv_{i}(x,s_{-i})-q_{i}(s_{i}^{\prime},s_{-i})[v_{i}(s_{i},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i})]$
$=q_{i}(s_{i}^{\prime},s_{-i})[v_{i}(s_{i},s_{-i})-v_{i}(\ell_{v_{i}}(s_{-i}),s_{-i})]-q_{i}(s_{i}^{\prime},s_{-i})[v_{i}(s_{i},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i})]$
$=q_{i}(s_{i}^{\prime},s_{-i})[v_{i}(s_{i},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i})]-q_{i}(s_{i}^{\prime},s_{-i})[v_{i}(s_{i},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i})]=0$

Case: $\ell_{v_{i}}(s_{-i})>s_{i}\geq s_{i}^{\prime}$

$\rho=-q_{i}(s_{i}^{\prime},s_{-i})[v_{i}(s_{i},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i})]=0$

Case: $s_{i}<s_{i}^{\prime}<\ell_{v_{i}}(s_{-i})$

$\rho=0$

Case: $s_{i}<\ell_{v_{i}}(s_{-i})<s_{i}^{\prime}$

$\rho=-\int_{\ell_{v_{i}}(s_{-i})}^{s_{i}^{\prime}}\frac{\partial
v_{i}(x,s_{-i})}{\partial x}q_{i}(x,s_{-i})\ dx-
q_{i}(s_{i}^{\prime},s_{-i})[v_{i}(s_{i},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i})]$
$\geq-
q_{i}(s_{i}^{\prime},s_{-i})\int_{\ell_{v_{i}}(s_{-i})}^{s_{i}^{\prime}}\frac{\partial
v_{i}(x,s_{-i})}{\partial x}\ dx-
q_{i}(s_{i}^{\prime},s_{-i})[v_{i}(s_{i},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i})]$
$=-q_{i}(s_{i}^{\prime},s_{-i})[v_{i}(s_{i}^{\prime},s_{-i})-v_{i}(\ell_{v_{i}}(s_{-i}),s_{-i})]-q_{i}(s_{i}^{\prime},s_{-i})[v_{i}(s_{i},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i})]$
$=-q_{i}(s_{i}^{\prime},s_{-i})[v_{i}(s_{i}^{\prime},s_{-i})-v_{i}(s_{i},s_{-i})]-q_{i}(s_{i}^{\prime},s_{-i})[v_{i}(s_{i},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i})]=0$

Case: $\ell_{v_{i}}(s_{-i})<s_{i}<s_{i}^{\prime}$

$\rho=-\int_{s_{i}}^{s_{i}^{\prime}}\frac{\partial v_{i}(x,s_{-i})}{\partial
x}q_{i}(x,s_{-i})\ dx-
q_{i}(s_{i}^{\prime},s_{-i})[v_{i}(s_{i},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i})]$
$\geq-q_{i}(s_{i}^{\prime},s_{-i})\int_{s_{i}}^{s_{i}^{\prime}}\frac{\partial
v_{i}(x,s_{-i})}{\partial x}\ dx-
q_{i}(s_{i}^{\prime},s_{-i})[v_{i}(s_{i},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i})]$
$=-q_{i}(s_{i}^{\prime},s_{-i})[v_{i}(s_{i}^{\prime},s_{-i})-v_{i}(s_{i},s_{-i})]-q_{i}(s_{i}^{\prime},s_{-i})[v_{i}(s_{i},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i})]=0$

Thus we have ex post incentive compatibility of $(q,p)$, and hence $q$ is ex-
post implementable. ∎

###### Proof of Proposition 1.

Let $(q,p)$ be an EPIC mechanism. We already know from Theorem 1 that $q$ must
be eventually monotone. So all we need to show is that the payments take the
form specified in the hypothesis.

Let $u_{i}$ denote the utility of agent $i$ from $(q,p)$. Since the value
functions are convex, it is reasonable to expect that the net payoff functions
$u_{i}$ are convex. This is indeed the case.

######  Claim 1.

For each $i$, $u_{i}$ is convex in $s_{i}$.

###### Proof of Claim 1.

Consider any $s_{1},s_{3}\in S$. Let $s_{2}=\lambda s_{1}+(1-\lambda)s_{3}$,
where $\lambda\in(0,1)$. By convexity of $S,\ s_{2}\in S$. By incentive
compatibility,

$u_{i}(s_{1},s_{-i})\geq
u_{i}(s_{2},s_{-i})+[v_{i}(s_{1},s_{-i})-v_{i}(s_{2},s_{-i})]q_{i}(s_{2},s_{-i})$
(2) $u_{i}(s_{3},s_{-i})\geq
u_{i}(s_{2},s_{-i})+[v_{i}(s_{3},s_{-i})-v_{i}(s_{2},s_{-i})]q_{i}(s_{2},s_{-i})$
(3)

Multiplying 2 with $\lambda$ and 3 with $1-\lambda$ and summing

$\displaystyle\lambda u_{i}(s_{1},s_{-i})$
$\displaystyle+(1-\lambda)u_{i}(s_{3},s_{-i})$ $\displaystyle\geq
u_{i}(s_{2},s_{-i})+q_{i}(s_{2},s_{-i})[\lambda
v_{i}(s_{1},s_{-i})+(1-\lambda)v_{i}(s_{3},s_{-i})-v_{i}(s_{2},s_{-i})]$
$\displaystyle\geq u_{i}(s_{2},s_{-i})$

where the last inequality follows from convexity of $v_{i}$. ∎

The next step of the proof uses the convexity of $u_{i}$ to establish the
relationship between $u_{i}$ and $v_{i}$.

######  Claim 2.

Given ex-post incentive compatibility, $\frac{\partial u_{i}}{\partial
s_{i}}=\frac{\partial v_{i}}{\partial s_{i}}q_{i}(s_{i},s_{-i})$ almost
everywhere.

###### Proof of Claim 2.

By convexity of $u_{i}$ and $v_{i}$, they are not differentiable at most in a
pair of measure $0$ subsets. Since their union will continue to be measure
$0$, we must have that $u_{i}$ and $v_{i}$ are together differentiable almost
everywhere.

Let $s_{i}$ be an interior point where $u_{i}$ and $v_{i}$ are both
differentiable and let $\epsilon>0$. By incentive compatibility,

$\frac{u_{i}(s_{i}+\epsilon,s_{-i})-u_{i}(s_{i},s_{-i})}{\epsilon}\geq\frac{v_{i}(s_{i}+\epsilon,s_{-i})-v_{i}(s_{i},s_{-i})}{\epsilon}q_{i}(s_{i},s_{-i})$
(4)

$\frac{u_{i}(s_{i},s_{-i})-u_{i}(s_{i}+\epsilon,s_{-i})}{\epsilon}\geq\frac{v_{i}(s_{i},s_{-i})-v_{i}(s_{i}+\epsilon,s_{-i})}{\epsilon}q_{i}(s_{i}+\epsilon,s_{-i})$
(5)

Rewriting 5, we get,

$\frac{v_{i}(s_{i}+\epsilon,s_{-i})-v_{i}(s_{i},s_{-i})}{\epsilon}q_{i}(s_{i}+\epsilon,s_{-i})\geq\frac{u_{i}(s_{i}+\epsilon,s_{-i})-u_{i}(s_{i},s_{-i})}{\epsilon}$
(6)

Let $\epsilon\rightarrow 0$ and use the sandwich theorem on 4 and 6 to get,

$\frac{\partial u_{i}}{\partial s_{i}}=\frac{\partial v_{i}}{\partial
s_{i}}q_{i}(s_{i},s_{-i})$

∎

We use the fundamental theorem of calculus to derive what $p$ must look like.

######  Claim 3.

The payment rule $p$ must be of the form

$p_{i}(s_{i},s_{-i})=p_{i}(\underline{s},s_{-i})+q_{i}(s_{i},s_{-i})v_{i}(s_{i},s_{-i})-q_{i}(\underline{s},s_{-i})v_{i}(\underline{s},s_{-i})-\int^{s_{i}}_{\underline{s}}\frac{\partial
v_{i}(x,s_{-i})}{\partial x}q_{i}(x,s_{-i})\ dx$

###### Proof of Claim 3.

From Claim 2 and using the fundamental theorem of calculus888Specifically, the
fundamental theorem of Lebesgue integral calculus for absolutely continuous
functions.,

$u_{i}(s_{i},s_{-i})=u_{i}(\underline{s},s_{-i})+\int_{\underline{s}}^{s_{i}}\frac{\partial
v_{i}}{\partial x}q_{i}(x,s_{-i})\ dx$

which gives us the required equality. ∎

For the converse, suppose $q$ is eventually monotone and the payments formula
take the form specified. The proof of the converse of Theorem 1 shows that
$(q,p)$ is EPIC, and hence we are done.

∎

###### Proof of Lemma 1.

As is standard in the case of private values, in this setting as well IR
reduces to ensuring IR of the lowest type.

######  Claim 4.

Given ex-post incentive compatibility, a mechanism is individually rational if
and only if $p_{i}(\underline{s},s_{-i})\leq
q_{i}(\underline{s},s_{-i})v_{i}(\underline{s},s_{-i})$

###### Proof of Claim 4.

This is a consequence of the following:

$u_{i}(s_{i},s_{-i})=-p_{i}(\underline{s},s_{-i})+q_{i}(\underline{s},s_{-i})v_{i}(\underline{s},s_{-i})+\int^{s_{i}}_{\underline{s}}\frac{\partial
v_{i}(x,s_{-i})}{\partial x}q_{i}(x,s_{-i})\ dx\geq 0\ \forall\ s_{i}$

$\Leftrightarrow$ $p_{i}(\underline{s},s_{-i})\leq
q_{i}(\underline{s},s_{-i})v_{i}(\underline{s},s_{-i})$

∎

Using Proposition 1, the expression for expected revenue in any EPIC mechanism
is

$\sum_{i\in N}\int_{s\in S}p_{i}(s)f(s)\ ds$ $=\sum_{i\in N}\int_{s\in
S}\left\\{p_{i}(\underline{s},s_{-i})+q_{i}(s_{i},s_{-i})v_{i}(s_{i},s_{-i})-q_{i}(\underline{s},s_{-i})v_{i}(\underline{s},s_{-i})-\int^{s_{i}}_{\underline{s}}\frac{\partial
v_{i}(x,s_{-i})}{\partial x}q_{i}(x,s_{-i})\ dx\right\\}f(s)\ ds$

$\displaystyle=\sum_{i\in N}\int_{s_{-i}\in S_{-i}}\int_{s_{i}\in
S_{i}}[p_{i}(\underline{s},s_{-i})+q_{i}(s_{i},s_{-i})v_{i}(s_{i},s_{-i})-q_{i}(\underline{s},s_{-i})v_{i}(\underline{s},s_{-i})-$
$\displaystyle\int^{s_{i}}_{\underline{s}}\frac{\partial
v_{i}(x,s_{-i})}{\partial x}q_{i}(x,s_{-i})\ dx]f(s_{i})\ ds_{i}\ f(s_{-i})\
ds_{-i}$

$\displaystyle=$ $\displaystyle\sum_{i\in N}\int_{s_{-i}\in
S_{-i}}\Bigl{\\{}\int_{\underline{s}}^{\overline{s}}q_{i}(s_{i},s_{-i})v_{i}(s_{i},s_{-i})f(s_{i})\
ds_{i}$
$\displaystyle-\int_{\underline{s}}^{\overline{s}}\Bigl{[}\int_{\underline{s}}^{s_{i}}\frac{\partial
v_{i}(x,s_{-i})}{\partial x}q_{i}(x,s_{-i})\ dx\Bigr{]}f(s_{i})\
ds_{i}\Bigr{\\}}\ f(s_{-i})\ ds_{-i}$ $\displaystyle+\ \sum_{i\in
N}\int_{s_{-i}\in
S_{-i}}[p_{i}(\underline{s},s_{-i})-q_{i}(\underline{s},s_{-i})v_{i}(\underline{s},s_{-i})]f(s_{-i})\
ds_{-i}$

Changing the order of integration, we can write,

$\int_{\underline{s}}^{\overline{s}}q_{i}(s_{i},s_{-i})v_{i}(s_{i},s_{-i})f(s_{i})\
ds_{i}-\int_{\underline{s}}^{\overline{s}}\left\\{\int_{\underline{s}}^{s_{i}}\frac{\partial
v_{i}(x,s_{-i})}{\partial x}q_{i}(x,s_{-i})\ dx\right\\}f(s_{i})\ ds_{i}$

$=\int_{\underline{s}}^{\overline{s}}\left\\{v_{i}(s_{i},s_{-i})-\frac{1-F(s_{i})}{f(s_{i})}\frac{\partial
v_{i}(s_{i},s_{-i})}{\partial s_{i}}\right\\}f(s_{i})q_{i}(s_{i},s_{-i})\
ds_{i}$

Thus, expected revenue is

$\sum_{i\in N}\int_{s_{-i}\in S_{-i}}\left\\{\int_{s_{i}\in
S_{i}}[J_{i}(s_{i},s_{-i})f(s_{i})q_{i}(s_{i},s_{-i})]\ ds_{i}\right\\}\
f(s_{-i})\ ds_{-i}$ $+\ \sum_{i\in N}\int_{s_{-i}\in
S_{-i}}[p_{i}(\underline{s},s_{-i})-q_{i}(\underline{s},s_{-i})v_{i}(\underline{s},s_{-i})]f(s_{-i})\
ds_{-i}$

The second term in the above expression is non-positive under EPIR. Thus, in
order to maximize revenue we must set
$p_{i}(\underline{s},s_{-i})=q_{i}(\underline{s},s_{-i})v_{i}(\underline{s},s_{-i})$.
As a result, the optimal mechanism maximizes the first term, which reduces to:

$\int_{s\in S^{n}}\Bigl{[}\sum_{i\in N}J_{i}(s)q_{i}(s)\Bigr{]}\ f(s)\ ds$

∎

###### Proof of Proposition 3.

If we were to pointwise maximize the revenue, we would not allocate the object
at signal profiles where the virtual value of each agent is negative. At other
profiles, note that the virtual value of agent $i$ is $J_{i}(s)=[\sum_{j\in
N}c_{j}s_{j}-c_{i}\frac{1-F(s_{i})}{f(s_{i})}]$. Thus,

$\displaystyle\sum_{i\in N}J_{i}(s)q_{i}(s)$ $\displaystyle=\sum_{i\in N}\
[\sum_{j\in N}c_{j}s_{j}-c_{i}\frac{1-F(s_{i})}{f(s_{i})}]q_{i}(s)$
$\displaystyle=\ \sum_{j\in N}s_{j}c_{j}\sum_{i\in N}q_{i}(s)-\sum_{i\in
N}c_{i}[\frac{1-F(s_{i})}{f(s_{i})}q_{i}(s)]$

The first term above is unchanged given a fixed total probability of
allocation. Again pointwise maximizing, we can allocate with probability 1 to
the agent with the lowest adjusted hazard rate and maximize the entire term at
a given signal profile.

Since the hazard rate is monotone non-increasing, once an agent starts winning
by having the lowest adjusted hazard rate, she continues to win at higher
signals. Thus this pointwise-maximizing allocation rule also turns out to be
non-decreasing, and hence the maximizer within the class of non-decreasing
allocation rules. ∎

###### Proof of Proposition 4.

We invoke the optimality of the inclusive posted price under must-sell shown
by Bergemann Brooks Morris (2019). For this we first show that ex post
incentive compatibility is sufficient for interim incentive compatibility.

EPIC means $\forall i$, $\forall s_{-i}$, $\forall s_{i},s_{i}^{\prime}$,

$u_{i}(s_{i},s_{-i})\geq
u_{i}(s_{i}^{\prime},s_{-i})+[v_{i}(s_{i},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i})]q_{i}(s_{i}^{\prime},s_{-i})$

$\Rightarrow\int_{s_{-i}}u_{i}(s_{i},s_{-i})dG(s_{-i})\geq\int_{s_{-i}}u_{i}(s_{i}^{\prime},s_{-i})+[v_{i}(s_{i},s_{-i})-v_{i}(s_{i}^{\prime},s_{-i})]q_{i}(s_{i}^{\prime},s_{-i})\
dG(s_{-i})\ \ \ \ \forall s_{i},s_{i}^{\prime},\ \forall i$

Now, we show that ex post individual rationality is sufficient for interim
individual rationality.

EPIR means $\forall i$, $\forall s_{-i}$, $\forall s_{i}$,

$u_{i}(s_{i},s_{-i})\geq 0$

$\Rightarrow\int_{s_{-i}}u_{i}(s_{i},s_{-i})\ dG(s_{-i})\geq 0\ \ \ \ \forall
s_{i},\ \forall i$

Since the allocation rule $q_{i}(s)=\frac{1}{N},\ \forall i$, is monotone and
hence eventually monotone, it is ex-post implementable. The corresponding
payments are,

For agent $j$ such that $s_{j}\geq s_{i},\forall i$

$p_{j}(s)=\frac{1}{N}s_{j}-\int_{\mathrm{max}\ s_{-j}}^{s_{j}}\frac{1}{N}dx$
$=\frac{\mathrm{max}\ s_{-j}}{N}$

and for all $i\neq j$

$p_{i}(s)=\frac{s_{j}}{N}$

Thus the tuple $(q,p)$ is both EPIC and EPIR, and hence IIR and IIC.

We now show that in expectation, this payment scheme gives the same revenue as
the inclusive posted price mechansim in Bergemann Brooks Morris (2019).

The expression for expected revenue is

$\sum_{i\in N}\int_{s\in S}p_{i}(s)f(s)\ ds$

Changing the order of summation,

$=\int_{s\in S}\left\\{\sum_{i\in N}p_{i}(s)\right\\}f(s)ds$ $=\int_{s\in
S}\left\\{\frac{N-1}{N}s_{(N)}+\frac{1}{N}s_{(N-1)}\right\\}f(s)ds$

$=\frac{N-1}{N}E(s_{(N)})+\frac{1}{N}E(s_{(N-1)})$

$=\frac{(N-1)}{N}\int_{s\in S}xN(F(x))^{N-1}f(x)dx+\frac{1}{N}\int_{s\in
S}xN{N-1\choose N-2}(1-F(x))(F(x))^{N-2}f(x)dx$

$=(N-1)\int_{s\in S}x(F(x))^{N-1}f(x)dx+(N-1)\int_{s\in
S}x(1-F(x))(F(x))^{N-2}f(x)dx$

$=(N-1)\int_{s\in S}x(F(x))^{N-2}f(x)dx$

$=\int_{\underline{s}}^{\overline{s}}x\ d(F^{N-1}(x))$

It is direct to show that any mechanism in the class of mechanisms identified
in this theorem has the same revenue as the equal sharing mechanism, and hence
we are done.

∎