# Increasing the Efficiency of Policy Learning for Autonomous Vehicles by
Multi-Task Representation Learning

Eshagh Kargar1 and Ville Kyrki1 1Eshagh Kargar and Ville Kyrki are with School
of Electrical Engineering, Aalto University, Finland.
<EMAIL_ADDRESS>
###### Abstract

Driving in a dynamic, multi-agent, and complex urban environment is a
difficult task requiring a complex decision-making policy. The learning of
such a policy requires a state representation that can encode the entire
environment. Mid-level representations that encode a vehicle’s environment as
images have become a popular choice. Still, they are quite high-dimensional,
limiting their use in data-hungry approaches such as reinforcement learning.
In this article, we propose to learn a low-dimensional and rich latent
representation of the environment by leveraging the knowledge of relevant
semantic factors. To do this, we train an encoder-decoder deep neural network
to predict multiple application-relevant factors such as the trajectories of
other agents and the ego car. We also propose a hazard signal in addition to
the learned latent representation as input to a down-stream policy. We
demonstrate that using the multi-head encoder-decoder neural network results
in a more informative representation than a standard single-head model. In
particular, the proposed representation learning and the hazard signal help
reinforcement learning to learn faster, with increased performance and less
data than baseline methods.

##  I INTRODUCTION

Driving in unstructured and dynamic urban environments is an arduous task.
Many moving agents such as cars, bicycles, and pedestrians affect driver’s
behavior and decisions. To drive a car, a driver, whether a human being or an
artificial agent, needs to perceive and understand other agents’ behaviors,
plans, and interactions in the environment, to react accordingly. The number
of factors in the scene makes the state space of this problem very large, and
safe autonomous driving in this complexity is an open challenge for the
research community and industry.

Figure 1: Proposed framework. A multi-head Variational Auto-Encoder is trained
using supervised learning to reconstruct a bird’s eye view image of the scene,
plan for ego car, and predict future trajectories of other vehicles. Route and
motion prediction masks are used to generate a hazard signal. Low-dimensional
encoding of the environment and the hazard signals are used as state for
reinforcement learning.

A central challenge related to the high complexity of the traffic environment
is representing the environment state. In end-to-end methods, immediate sensor
measurements are used directly as the state for the decision-making policy.
However, the high dimensionality of the sensor data makes its direct use
challenging, as a vast number of data are needed to constrain the learning
problem [1]. For that reason, mid-level representations, that render all
perceptual inputs together with static information such as HD-map and route as
bird’s eye view (BEV) images, have recently received increasing attention (see
e.g. [2]). However, even the mid-level representations may be so high-
dimensional that their use with data-hungry methods such as Reinforcement
Learning (RL) is limited.

To alleviate this, we propose a new approach to learn low-dimensional and rich
representations. In particular, we combine the recently proposed idea to learn
a low-dimensional latent space of the mid-level image [3] with the prediction
of multiple auxiliary application-relevant factors. A single latent
representation is extracted from the mid-level input representations such that
the latent representation is enforced to predict the trajectories of both the
ego vehicle and other vehicles in addition to a bird’s eye view of the scene,
using a multi-head network structure depicted in Fig. 1. All heads of the
network represent the information as images, which allows their
straightforward interpretation. Also, we use the motion prediction head result
and calculate its Gaussian likelihood with the route as an additional input to
the policy. This will give the policy information about hazardous situations.

Experiments demonstrate that the auxiliary tasks allow the latent vector to
learn more representative information from the scene. Therefore, a policy
network can be trained faster and performs better, even with less data than a
representation based on a single-head network trained for the optimal
reconstruction of the scene.

The primary contributions of this work are: (a) a multi-task network with
auxiliary heads to improve the quality of low-dimensional representations, (b)
a hazard signal calculated by Gaussian likelihood between route and predicted
trajectories of dynamic agents, and (c) an experimental study of an RL policy
learning, showing that the learned latent-vector by using auxiliary tasks and
also the hazard signal, can help the policy to be (i) trained faster, (ii)
perform better, and (iii) learn to solve the task using less data.

##  II Related Work

Reinforcement learning is a popular approach to learn a decision-making policy
in autonomous driving [3, 4, 5, 6, 7, 8]. Despite the typically data-hungry
nature of RL, Kendall et al. [9] recently demonstrated learning of a lane
following task using real-world data gathered in a single day. However, the
complexity of complex traffic environments requires great amounts of data
since the state space of the decision making problem is vast.

A solution to the high-dimensional state space is to first learn a low
dimensional representation of the scene from raw sensor data. The low
dimensional representation can then be used as input to a decision making
policy. This can be achieved e.g. by training a Variational Auto-Encoder (VAE)
to form a latent representation of sensor data such as camera images [10].

Another approach to address the problem of high-dimensional state space is to
use a mid-level representation, such as a bird’s eye view of the current
scene, as the state space. The mid-level representations can be constructed by
engineered perception modules or by learning the mapping from sensor
measurements to the mid-level representation [11]. Such representations are
useful because they can capture the entire traffic environment around the
vehicle in an interpretable fashion, but their dimensionality will still be
high. Thus, techniques that increase the amount of available data are needed
to use the mid-level representations directly. For example, Bansal et al. [2]
proposed to use data augmentation to learn to imitate a driving policy using
bird’s eye view images as input.

Similar mid-level representations can also be used for motion forecasting [12,
13, 14, 15, 16].

It is also possible to combine mid-level input with learning a low-dimensional
representation. Chen et al. [3] trained a VAE to reconstruct a bird’s eye view
image of the scene with rendered mid-level information, and then used the
latent representation as input to an RL agent.

To further constrain the learned latent representation to be useful, auxiliary
tasks that are semantically relevant to the driving problem can be used. Hawke
et al. [17] proposed to use auxiliary tasks in the sensor space of camera
images that output segmentation, monocular depth, and optical flow to learn a
better representation. The learned mid-level feature map was then used to
train a policy to output control commands using imitation learning.

Our work combines the learning of low-dimensional representations from mid-
level representations with the use of auxiliary tasks to further constrain the
learned representation. The proposed approach uses motion prediction of other
agents as one of the auxiliary tasks, which allows us to propose a novel
hazard signal that can be further used in reinforcement learning to inform of
potential collisions during the learning process.

##  III Background

Next we will outline the required theoretical concepts behind the proposed
method, including Variational Auto-Encoders (VAEs), Reinforcement learning,
and Deep Q-Networks.

###  III-A Variational Auto-Encoders

Auto-Encoders (AEs) are a type of generative neural networks with an encoder-
decoder structure aiming to learn a compact and low-dimensional representation
$z$ for high-dimensional input data $x$. Variational Auto-Encoders (VAEs)
extend AEs by mapping input data to a distribution instead of a value. To
learn compact representations, the latent distribution is subjected to a prior
$p(z)$, typically a normalized Gaussian distribution. The latent
representation is then learned by minimizing the objective function [18]

$L_{vae}(\phi,\theta)=-E_{q_{\theta}(z|x)}log(p_{\phi}(x|z))+D_{kl}(q_{\theta}(z|x)||p(z))$
(1)

where $q_{\theta}(z|x)$ is the encoder network mapping inputs to latent space,
$p_{\phi}(x|z)$ is the decoder network, and $D_{kl}$ term is the KL-divergence
between the encoder output and the prior. The first term of (1) corresponds
then to the reconstruction error. The second term enforces the representation
to be compact.

In order to improve disentanglement of the representation, $\beta$-VAE was
introduced in [19] that instead of considering the KL-divergence between
encoder and prior directly as a cost term, constrains the KL-divergence by an
upper bound. Using Karush-Kuhn-Tucker conditions, the constrained optimization
can be written using a Lagrangian factor $\beta$ as an unconstrained
optimization problem as

$L_{\beta-vae}(\phi,\theta)=-E_{q_{\theta}(z|x)}log(p_{\phi}(x|z))+\beta
D_{kl}(q_{\theta}(z|x)||p(z))$ (2)

When $\beta=1$, this corresponds to the regular VAE. Increasing $\beta$
encourages more disentanglement with the cost of reconstruction quality.

###  III-B Reinforcement Learning

Reinforcement learning aims to find an optimal control policy
$\pi:S\rightarrow A$ from states to actions that maximizes total expected
future rewards

$R(\pi)=E_{\pi}\Bigg{[}\sum_{t}\gamma^{t}r(s_{t},a_{t})\Bigg{]}$ (3)

where $s_{t}$, $a_{t}$, $r$, and $\gamma$ are state at time $t$, action at
time $t$, reward, and discount factor, respectively.

Value-function based RL solves the RL problem by determining an optimal value
function $Q:S,A\rightarrow\mathbb{R}$ that describes the expected cumulative
rewards when starting from a particular state and choosing a particular action

$Q^{*}(s,a)=\max_{\pi}E\Bigg{[}\sum_{t=0}\gamma^{t}r(s_{t},a_{t})|s_{0}=s,a_{0}=a\Bigg{]}.$
(4)

Knowing the optimal value function, an optimal policy $\pi^{*}$ can then be
determined as $\pi^{*}(s)=\operatorname*{argmax}\limits_{a}Q^{*}(s,a)$.

###  III-C Deep Q-Network

In continuous state spaces with unknown dynamics, it is usually impossible to
determine the value function exactly. Deep Q-Networks (DQNs) [20] are a
successful RL algorithm that use a deep neural network $Q(s,a;\psi)$ to
approximate the value function where $\psi$ are the parameters of the neural
network. DQN also uses a replay buffer $D=\\{(s,a,r,s^{\prime})\\}$ to store
experiences from past to expedite and stabilize learning. To further stabilize
the learning, DQN defines a target Q-network with parameters $\psi^{\prime}$
which are updated only every $\tau$ steps to the current $\psi$. To optimize
$\psi$, the Q-learning loss

$L_{DQN}(\psi)=E_{U}(D)\Bigg{[}\left(r+\gamma\max_{a^{\prime}}Q(s^{\prime},a^{\prime};\psi^{\prime})-Q(s,a,\psi)\right)^{2}\Bigg{]}$
(5)

is minimized for a uniform sample of transitions sampled from $D$.

##  IV Method

The proposed method consists of two parts as illustrated in Fig. 1. First, a
low-dimensional latent representation for bird’s eye view images is
constructed (left). Second, a driving policy is learned using the low-
dimensional representation and a hazard signal that is formed from predicted
future trajectories of other vehicles (right).

In the following, we first describe the mid-level representation used as the
input (Sec. IV-A). We then explain how the latent representation is learned
using a multi-head VAE (Sec. IV-B). We continue by defining the hazard signal
in Sec. IV-C. Finally, in Sec. IV-D we describe the policy learning.

###  IV-A Mid-Level Input Representation

Information in the mid-level input representation includes road relevant
structures, planned route, current and past poses of ego vehicle and other
vehicles, and traffic light state. Each of these is described using one or
more channels of a 11-channel image, as illustrated in Fig. 2.

In simulation experiments, the perception and route information is provided by
the CARLA simulator [21].

The information is represented as follows:

  1. 1.

Map: The HD-Map information includes drivable areas, lane lines, center of
lane lines, and curbs, as shown in Fig. 2(b–d).

  2. 2.

Route: The route from a starting point to the current destination is assumed
to originate from an external planning system such as a standard vehicle
navigator. An example is shown in Fig. 2e.

  3. 3.

Current and past poses of other vehicles: The current and past position,
orientation, and size of other vehicles are rendered on two different
channels, presented in Fig.2(f–g). We consider $1.5s$ of motion history for
dynamic targets in the scene.

  4. 4.

Current and past ego vehicle poses: The current and past position,
orientation, and size of the ego vehicle are rendered on two different
channels, described in Fig.2(h–i). We consider $1.5s$ of motion history for
ego vehicle.

  5. 5.

Traffic lights: The information for different traffic light colors are
rendered on three different channels for green, red, and yellow as shown in
Fig.2(j–l).

BEV dimensions are 25m on the left and right side, 37.5m in front, and 12.5m
behind the ego car.

Figure 2: Illustration of input channels: (a) the bird’s eye view rendered RGB
image, (b) road area, (c) lane lines, (d) lane centers, (e) route, (f) dynamic
object’s pose at the current time-step, (g) motion history of dynamic objects,
(h) ego car’s pose at the current time-step, (i) motion history of the ego
car, (j) green traffic light, (k) yellow traffic light, and (l) red traffic
light.

###  IV-B Learning Latent Representation Using Multi-Head VAE

To constrain the learning of the latent representation, it is enforced to
learn three task-relevant factors: scene reconstruction, ego vehicle plan, and
predicted motion of other vehicles. To do this, we use an encoder-decoder VAE
which takes the 11-channel scene as the input to the encoder
$q_{\theta}(z|x)$. The encoder transforms its input into a low-dimensional
latent distribution $z$. The latent distribution is decoded into the three
factors such that each factor is a separate decoder head of the neural
network. The architecture for the multi-head VAE is illustrated in Fig. 1 in
the “VAE training” box.

The three decoder networks are:

  1. 1.

Scene Reconstruction Head gets the latent vector $z$ and reconstructs a three-
channel bird’s eye view RGB image of the scene $rgb$, rendered based on the
11-channel input similar to e.g. [3]. The neural network for this head is
expressed by $p_{\phi_{1}}(rgb|z)$.

  2. 2.

Planning Head maps the latent vector to a single-channel bird’s eye view
planning mask for the ego vehicle for the next $2s$. This head is represented
by $p_{\phi_{2}}(plan|z)$.

  3. 3.

Motion Prediction Head forecasts the next $2s$ pose of dynamic agents in the
scene. It gets the latent-vector $z$ and outputs a bird’s eye view mask of
other agents’ future motion. It is expressed by $p_{\phi_{3}}(pred|z)$.

The network architecture for each of the decoder heads is the same, but the
network weights $\phi_{1},\phi_{2},\phi_{3}$ are different. The multi-head VAE
is optimized by minimizing the objective function

$\begin{split}L(\phi_{1},\phi_{2},\phi_{3})=&-w_{1}E_{q_{\theta}(z|x)}log(p_{\phi_{1}}(rgb|z))\\\
&-w_{2}E_{q_{\theta}(z|x)}log(p_{\phi_{2}}(plan|z))\\\
&-w_{3}E_{q_{\theta}(z|x)}log(p_{\phi_{3}}(pred|z))\\\
&+w_{4}D_{kl}(q_{\theta}(z|x)||p(z))\end{split}$ (6)

with $p(z)$ a normal distribution prior. The optimization is performed by
gradient descent using a dataset of known trajectories in order to be able to
train the planning and prediction heads.

###  IV-C Generation of Hazard Signal

To quantify the degree of conflict between ego car’s and other vehicles’
trajectories, we calculate a hazard signal $h$ as the log-likelihood that the
predicted motion of other vehicles and known planned route are equal under
Gaussian noise.

$h=\log P(r|pred)=\sum_{i}\log P(r_{i}|pred_{i})$ (7)

where $P(r_{i}|pred_{i})=N(p_{\phi_{3}}(pred_{i}|z),1)$ is the probability of
pixel $i$ being equal between the route $r$ and prediction.

The calculated hazard signal is used in addition to the latent encoding as
input to the RL policy as shown in Fig. 1.

###  IV-D Policy Learning Using DQN

The latent encoding of the current state and the current hazard signal value
form the input space to a DQN agent such that $s=(\mu_{z},h)$, with $\mu_{z}$
representing the mean of the current latent encoding (see Fig. 1). The action
space is a vector of three values for throttle, brake, and steering angle,
$a=(a_{t},a_{b},a_{s})$, such that each dimension is discretized into discrete
choices.

The reward function is a sum of terms related to collisions, performance,
obeying traffic rules (staying in lane, obeying traffic lights), and comfort,

$\begin{split}r=r_{c}+r_{v}+r_{o}+r_{\alpha}+r_{w}+r_{tl}+c\end{split}$ (8)

where $r_{c}$ is a collision penalty, $r_{v}$ is a speed reward term to match
desired speed, $r_{o}$ is an out-of-lane penalty, $r_{\alpha}$ is the steering
angle penalty to improve driving comfort, $r_{w}$ is penalty for high lateral
acceleration, $r_{tl}$ is the penalty term for passing red traffic lights, and
$c$ is a constant time penalty. The policy is then learned using standard DQN.

##  V Experiments

We performed simulation experiments to study the following questions:

  1. 1.

How much is the effect of auxiliary heads and the generated hazard signal?

  2. 2.

How our method with auxiliary heads and the hazard signal performs compared to
baselines?

  3. 3.

Can we decrease the dataset size by using auxiliary heads?

  4. 4.

Can latent space learn about the scene structure, future potential
trajectories for the ego agent and other agents?

In the following sections, first, the simulation environment and data
collection have been described. Then, the implementation details of the multi-
head VAE and policy network architectures and also the reward function are
detailed. After that, the effect of different heads in the multi-head VAE is
evaluated to answer question 1. The proposed method is then compared with
state-of-the-art methods to answer question 2. Dataset size effect is
evaluated next to answer question 3. Finally, a qualitative analysis of the
learned latent-vector is done to answer question 4. All experiments were
repeated for a set of five identical random seeds for each case.

###  V-A Simulation Environment and Data Collection

To collect the dataset to train the multi-head VAE, we used the CARLA
simulator [21], an open-source simulator for autonomous driving, to collect
the dataset. We designed two scenarios to collect the dataset: a roundabout
and a complex intersection shown in Fig. 3. For data collection phase for VAE
training, we start from a random position around the start positions shown in
the figure and select the destination randomly in the city. But for RL
training phase, to add stochasticity, start and end positions are considered
randomly around the positions shown in the figure.

((a))

((b))

Figure 3: Scenarios: (a) roundabout, (b) 5-way intersection.

For the data collection phase, 100 vehicles were spawned randomly in Town
number three in CARLA and near the designed scenarios. We used CARLA autopilot
mode to drive and collect a dataset.

By recording all agents’ poses in each time-step during driving, we had the
required information to create the dataset without any manual labeling. To
create the ground truth data for motion prediction and planning heads, we used
the ego car’s pose and other agents in the next time-steps, transformed them
into the current ego vehicle’s coordinate frame, and rendered them on a binary
image. So it didn’t require manual labeling and was done in a self-supervised
manner. The dataset size is around 200k frames.

For the RL policy learning phase, we used curriculum learning and increased
number of agents from zero to 100 to increase the difficulty level step-by-
step. We also set 20 percent of cars to ignore traffic lights and have
aggressive driving behavior in both data collection for multi-head VAE
training and RL policy training.

###  V-B Implementation Details

Fig. 1 shows the multi-head VAE architecture in the ”VAE training” box. The
encoder was a ResNet-18 [22] in which the first Convolutional layer had
changed to get a BEV 64x64x11 input tensor. The output feature vector of the
ResNet network had the size of 512. Then we used two fully connected layers
with 20 neurons to output $\mu$ and $\sigma$ vectors for a Gaussian
distribution on latent-space. Then the latent-vector was sampled from this
distribution. There were three decoder heads with similar architecture but
different weights. We used a network similar to ResNet-18 but in inverse order
for decoder heads. The output of planning and prediction heads had one
channel, but the reconstruction head had three channels for the output RGB
image.

The weights used for the loss terms were $w_{1}=1,w_{2}=1,w_{3}=50$, and
$w_{4}=50$.

The DQN policy, which is shown in the ”RL training” box in Fig. 1, is a
network with three fully-connected layers with 128, 64, and nine (output)
neurons that gets the input vector with the size of 21 and generate the
control commands. Output control commands of the policy network are: (1)
acceleration $\in\\{-0.3,0,0.3\\}$ which positive value is for throttle,
negative value for brake, and zero for braking and throttle, and (2) steering
$\in\\{-0.15,0,0.15\\}$.

The terms of the reward function (8) were set as follows: The collision
penalty $r_{c}$ was set to $r_{c}=-200$ if there is a collision, otherwise
$r_{c}=0$. The speed reward $r_{v}$ was set to the ego vehicle’s speed,
$10m/s$, and if $r_{v}>10m/s$ then a penalty of $-10$ will be added to the
reward function. The going out of lane penalty $r_{o}$ was set to $r_{o}=-1$
if the distance between the ego vehicle’s position and the planned route is
more than $2.5m$, otherwise $r_{o}=0$. The steering angle penalty $r_{\alpha}$
was set to $r_{\alpha}=-0.5\times\alpha^{2}$. The high lateral acceleration
penalty $r_{w}$ was set to $r_{w}=-0.2\times w$, where $w$ is the lateral
acceleration. The passing red traffic lights penalty term $r_{tl}$ (only in
the intersection scenario) was set to $r_{tl}=-10$ if the ego vehicle passes a
red traffic light, otherwise $r_{tl}=0$. Finally, the constant time penalty
$c$ was set to $-0.1$ to prevent the car from stopping.

###  V-C Effect of Different Heads and the Hazard Signal

To answer question 1 and see the effect of each head on the learned latent-
vector and the proposed hazard signal, a down-stream RL task, DQN agent, was
considered. The VAE with a reconstruction head proposed in [3] was considered
as the baseline (dqn_rec). Four other models are trained to analyze the effect
of each head and the hazard signal: (a)VAE with reconstruction and planning
heads (dqn_rec_plan), (b)VAE with reconstruction and motion prediction heads
(dqn_rec_pred), (c)VAE with reconstruction, planning, and motion prediction
heads (dqn_rec_plan_pred), and (d)VAE with auxiliary hazard signal in addition
to three heads in case $c$ (dqn_rec_plan_pred_hzrd).

All networks are trained using the full dataset. Then the encoder of each case
was used as the feature extractor for the DQN agent. The encoder weights were
fixed, and we only trained DQN weights in this phase. For case $d$, the DQN
agent also used the hazard signal, which is a Gaussian likelihood between the
route and the motion prediction result. Fig. 1 shows the full model used in
case $d$.

Fig. 4 shows the comparison. Our proposed method (dqn_rec_plan_pred_hzrd)
outperformed all other cases, achieved a higher mean reward, and solved the
task faster in both roundabout and intersection scenarios. The baseline method
cannot solve the task, but by adding the planning head, the agent can finally
solve it and reach the destination. We can also see the effect of planning and
prediction heads by comparing the VAE with reconstruction and prediction heads
(dqn_rec_pred) against the VAE with reconstruction and planning heads
(dqn_rec_plan). It shows that the motion prediction head that has information
about other dynamic agents’ future motion can be more beneficial than the
planning head and improve the down-stream task’s performance by a large
margin. We can also see that using both planning and prediction heads in
addition to the reconstruction head (dqn_rec_plan_pred) can outperform using
planning and prediction heads separately.

Figure 4: Analysis of the effect of different VAE decoder heads and the hazard
signal on the down-stream RL task’s performance in two scenarios.

###  V-D Comparison to Baselines

This section compares our method with two baseline approaches in order to
answer question 2. The proposed multi-head VAE with three decoder heads and
also the proposed auxiliary hazard signal as input to the DQN agent
(dqn_rec_plan_pred_hzrd), shown in Fig. 1, was compared with: (a) an encoder
and a policy network which are trained end-to-end using RL, similar to the DQN
work on Atari games [23], to get the BEV input tensor and generate control
commands (dqn_cnn_e2e), and (b) a single-head VAE with a reconstruction head
(dqn_rec) [3] which was trained using supervised learning and then the weights
were fixed, and the encoder was used as the feature extractor for BEV input
tensor. Then the DQN agent used the encoded latent-vector as input to generate
control commands.

Fig. 5 shows the comparison in two scenarios. As can be seen, our proposed
method surpassed other methods by a large margin. We can also see that
baseline agent cannot solve the task, but our approach solved the task quite
fast with a large margin in performance.

Figure 5: Comparison of the proposed method against baselines in two
scenarios.

###  V-E Effect of the Dataset Size

In this part we try to investigate question 3. Several models were trained
using different dataset sizes to show the benefit of using multiple decoder
heads and the hazard signal on the learned latent-vector and the down-stream
task’s performance. The full model, shown in Fig. 1, was trained using the
full dataset (dqn_rec_plan_pred_hzrd_full), half of the dataset
(dqn_rec_plan_pred_hzrd_half), and a quarter of the dataset
(dqn_rec_plan_pred_hzrd_quart). We then compared them against the baseline VAE
[3] with just a reconstruction decoder (dqn_rec) trained on the full dataset.
For our proposed method, a DQN agent was trained to get the concatenation of
the latent-vector and the hazard signal and output control commands. Note that
for the baseline, there is no hazard signal, as there is no prediction head.

The results, shown in Fig. 6 for two scenarios, present better performance of
our proposed method even when it was trained with a quarter of the dataset.
The case trained with half of the dataset can solve the task, but the model
trained with a quarter of the dataset cannot; however, it outperformed the
baseline.

Figure 6: Analysis of the effect of different dataset sizes on the down-stream
RL task in two scenarios.

###  V-F Qualitative Analysis

Figure 7: Latent-space exploration. The left plot shows the violin-plot of the
learned latent-space – mean, standard deviation, min, and max – for training
dataset. The right hand side figures show outputs of the multi-head VAE when
the $i$th latent element is changed from $\mu_{i}-\sigma_{i}$ to
$\mu_{i}+\sigma_{i}$. $\mu_{i},\sigma_{i}$ are mean and standard deviation of
the $i$th element for the whole training dataset. We show only the results of
exploring three latent elements: 4th, 17th, and 20th. A video with more
examples of latent space exploration can be found at:
https://youtu.be/5Tk8j6LXBmA.

In this section, we explore the latent-space to answer question 4. The learned
latent-vector has 20 elements some of which have almost zero standard
deviation and changing their value do not cause any difference in outputs.
Fig. 7 shows the results for three latent elements. We used a sample input
from dataset and encoded it to get the latent-vector. Then for each latent
element $i$, we changed its value from $\mu_{i}-\sigma_{i}$ to
$\mu_{i}+\sigma_{i}$ while other latent elements were fixed. By exploring
latent-space, we see changes in different factors in the scene such as road
structure, traffic light color, route, dynamic objects pose, planning, and
motion prediction. This shows the meaningfulness of the learned latent-space.
We can also see the harmony between different heads’ outputs when changing
latent values.

##  VI CONCLUSIONS

Machine learning presents an important avenue to handle the complexity of
situations in autonomous driving but its applicability is significantly
hindered by the huge amounts of data needed for learning. In this paper, we
proposed a multi-head VAE network with a bird’s eye view input and task-
relevant heads to learn efficient latent-space representations. These
representations can then be used to train a driving policy more efficiently.
Experimental comparison against baselines in two scenarios showed that the use
of task-relevant heads in representation learning improves policy learning in
three ways: the policy quality is better, the learning converges faster, and
policy learning requires less data. The proposed approach can be easily
extended to other task-relevant factors if they can be encoded as images.

In real traffic environments, multiple vehicles with different driving
policies interact with each other. In this case, generalization capability of
a representation would likely benefit from disentanglement of that
representation with respect to the different actors. The use of multi-task
learning similar to this paper thus seems to provide a valuable avenue towards
autonomous driving in complex traffic conditions.

## ACKNOWLEDGMENT

The authors wish to acknowledge CSC – IT Center for Science, Finland, for
generous computational resources. We also acknowledge the computational
resources provided by the Aalto Science-IT project.

## References

  * [1] M. Müller, A. Dosovitskiy, B. Ghanem, and V. Koltun, “Driving policy transfer via modularity and abstraction,” _arXiv preprint arXiv:1804.09364_ , 2018.
  * [2] M. Bansal, A. Krizhevsky, and A. Ogale, “Chauffeurnet: Learning to drive by imitating the best and synthesizing the worst,” _arXiv preprint arXiv:1812.03079_ , 2018.
  * [3] J. Chen, B. Yuan, and M. Tomizuka, “Model-free deep reinforcement learning for urban autonomous driving,” in _2019 IEEE Intelligent Transportation Systems Conference (ITSC)_. IEEE, 2019, pp. 2765–2771.
  * [4] B. Mirchevska, C. Pek, M. Werling, M. Althoff, and J. Boedecker, “High-level decision making for safe and reasonable autonomous lane changing using reinforcement learning,” in _2018 21st International Conference on Intelligent Transportation Systems (ITSC)_. IEEE, 2018, pp. 2156–2162.
  * [5] P. Wang and C.-Y. Chan, “Formulation of deep reinforcement learning architecture toward autonomous driving for on-ramp merge,” in _2017 IEEE 20th International Conference on Intelligent Transportation Systems (ITSC)_. IEEE, 2017, pp. 1–6.
  * [6] T. Shi, P. Wang, X. Cheng, C.-Y. Chan, and D. Huang, “Driving decision and control for automated lane change behavior based on deep reinforcement learning,” in _2019 IEEE Intelligent Transportation Systems Conference (ITSC)_. IEEE, 2019, pp. 2895–2900.
  * [7] S. Kuutti, R. Bowden, H. Joshi, R. de Temple, and S. Fallah, “End-to-end reinforcement learning for autonomous longitudinal control using advantage actor critic with temporal context,” in _2019 IEEE Intelligent Transportation Systems Conference (ITSC)_. IEEE, 2019, pp. 2456–2462.
  * [8] N. Deshpande and A. Spalanzani, “Deep reinforcement learning based vehicle navigation amongst pedestrians using a grid-based state representation,” in _2019 IEEE Intelligent Transportation Systems Conference (ITSC)_. IEEE, 2019, pp. 2081–2086.
  * [9] A. Kendall, J. Hawke, D. Janz, P. Mazur, D. Reda, J.-M. Allen, V.-D. Lam, A. Bewley, and A. Shah, “Learning to drive in a day,” in _2019 International Conference on Robotics and Automation (ICRA)_. IEEE, 2019, pp. 8248–8254.
  * [10] R. Bonatti, R. Madaan, V. Vineet, S. Scherer, and A. Kapoor, “Learning visuomotor policies for aerial navigation using cross-modal representations,” _arXiv preprint arXiv:1909.06993_ , 2019.
  * [11] M. Itkina, K. Driggs-Campbell, and M. J. Kochenderfer, “Dynamic environment prediction in urban scenes using recurrent representation learning,” in _2019 IEEE Intelligent Transportation Systems Conference (ITSC)_. IEEE, 2019, pp. 2052–2059.
  * [12] H. Cui, V. Radosavljevic, F.-C. Chou, T.-H. Lin, T. Nguyen, T.-K. Huang, J. Schneider, and N. Djuric, “Multimodal trajectory predictions for autonomous driving using deep convolutional networks,” in _2019 International Conference on Robotics and Automation (ICRA)_. IEEE, 2019, pp. 2090–2096.
  * [13] H. Cui, T. Nguyen, F.-C. Chou, T.-H. Lin, J. Schneider, D. Bradley, and N. Djuric, “Deep kinematic models for physically realistic prediction of vehicle trajectories,” _arXiv preprint arXiv:1908.00219_ , 2019.
  * [14] F.-C. Chou, T.-H. Lin, H. Cui, V. Radosavljevic, T. Nguyen, T.-K. Huang, M. Niedoba, J. Schneider, and N. Djuric, “Predicting motion of vulnerable road users using high-definition maps and efficient convnets,” _arXiv preprint arXiv:1906.08469_ , 2019.
  * [15] T. Phan-Minh, E. C. Grigore, F. A. Boulton, O. Beijbom, and E. M. Wolff, “Covernet: Multimodal behavior prediction using trajectory sets,” _arXiv preprint arXiv:1911.10298_ , 2019.
  * [16] Y. Chai, B. Sapp, M. Bansal, and D. Anguelov, “Multipath: Multiple probabilistic anchor trajectory hypotheses for behavior prediction,” _arXiv preprint arXiv:1910.05449_ , 2019.
  * [17] J. Hawke, R. Shen, C. Gurau, S. Sharma, D. Reda, N. Nikolov, P. Mazur, S. Micklethwaite, N. Griffiths, A. Shah _et al._ , “Urban driving with conditional imitation learning,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2020, pp. 251–257.
  * [18] D. P. Kingma and M. Welling, “Auto-encoding variational bayes,” _arXiv preprint arXiv:1312.6114_ , 2013.
  * [19] I. Higgins, L. Matthey, A. Pal, C. Burgess, X. Glorot, M. Botvinick, S. Mohamed, and A. Lerchner, “beta-vae: Learning basic visual concepts with a constrained variational framework,” 2016.
  * [20] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski _et al._ , “Human-level control through deep reinforcement learning,” _nature_ , vol. 518, no. 7540, pp. 529–533, 2015.
  * [21] A. Dosovitskiy, G. Ros, F. Codevilla, A. Lopez, and V. Koltun, “Carla: An open urban driving simulator,” _arXiv preprint arXiv:1711.03938_ , 2017.
  * [22] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770–778.
  * [23] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller, “Playing atari with deep reinforcement learning,” _arXiv preprint arXiv:1312.5602_ , 2013.


DMred MFblue SMpurple!80!black AEorange

# Private Interdependent Valuations:
New Bounds for Single-Item Auctions and Matroids††thanks: The work of A. Eden
was supported by the Israel Science Foundation (grant No. 533/23). The work of
M. Feldman, S. Mauras, and D. Mohan has been partially funded by the European
Research Council (ERC) under the European Union’s Horizon 2020 research and
innovation program (grant agreement No. 866132), by an Amazon Research Award,
by the NSF-BSF (grant No. 2020788), and by a grant from TAU Center for AI and
Data Science (TAD). This research was partially conducted while some of the
authors were visiting the Simons Laufer Mathematical Sciences Institute
(formerly MSRI) in Berkeley, California, during the Fall 2023 semester, which
was funded by the National Science Foundation (grant No. DMS-1928930) and by
the Alfred P. Sloan Foundation (grant G-2021-16778).

Alon Eden The Hebrew University<EMAIL_ADDRESS>Michal Feldman Tel
Aviv University<EMAIL_ADDRESS>Simon Mauras Tel Aviv University;
INRIA<EMAIL_ADDRESS>Divyarthi Mohan Tel Aviv University;
<EMAIL_ADDRESS>
We study auction design within the widely acclaimed model of interdependent
values, introduced by Milgrom and Weber [1982]. In this model, every bidder
$i$ has a private signal $s_{i}$ for the item for sale, and a public valuation
function $v_{i}(s_{1},\ldots,s_{n})$ which maps every vector of private
signals (of all bidders) into a real value. A recent line of work established
the existence of approximately-optimal mechanisms within this framework, even
in the more challenging scenario where each bidder’s valuation function
$v_{i}$ is also private. This body of work has primarily focused on single-
item auctions with two natural classes of valuations: those exhibiting
submodularity over signals (SOS) and $d$-critical valuations.

In this work we advance the state of the art on interdependent values with
private valuation functions, with respect to both SOS and $d$-critical
valuations. For SOS valuations, we devise a new mechanism that gives an
improved approximation bound of $5$ for single-item auctions. This mechanism
employs a novel variant of an “eating mechanism”, leveraging LP-duality to
achieve feasibility with reduced welfare loss. For $d$-critical valuations, we
broaden the scope of existing results beyond single-item auctions, introducing
a mechanism that gives a $(d+1)$-approximation for any environment with
matroid feasibility constraints on the set of agents that can be
simultaneously served. Notably, this approximation bound is tight, even with
respect to single-item auctions.

##  1 Introduction

A standard assumption in auction theory literature is that each bidder has a
private value for the item, typically assumed to be independent of other
bidders’ values. However, in many scenarios, a bidder’s value may crucially
depend on private information possessed by others. This is the case in
contexts such as mineral rights auctions, art auctions, and online ad
auctions, where bidders lack knowledge of their value for the item a priori,
and moreover, their values are interdependent.

The seminal work of Milgrom and Weber [26] and Wilson [31], recognized by the
2020 Nobel prize in Economics [18], introduced the interdependent values model
to formally study these intricate settings. In this model, every bidder $i$
has a private signal $s_{i}$, representing her partial information about the
item, and a public valuation function $v_{i}(\cdot)$ that maps the signals of
all bidders to $i$’s value for the item, with $v_{i}(s_{1},\ldots,s_{n})$
denoting bidder $i$’s value for the item under a signal profile
$(s_{1},\ldots,s_{n})$. For instance, in the context of art auctions, a
bidder’s signal might encapsulate her perception of the artwork’s significance
or her personal connection to it, while her valuation might also be shaped by
the information and perspectives of other bidders. Naturally, this scenario
presents a notably more complex challenge than the standard model of
independent private values. In particular, a long line of economic research
has established strong impossibilities for obtaining optimal welfare
truthfully, except in settings that satisfy a strict property called _single-
crossing_ [25, 10, 21, 2].

The approximation lens. Recent endeavors in EconCS have addressed these
challenges by adopting the algorithmic lens of approximation, leading to the
construction of truthful mechanisms that obtain approximately optimal welfare
or revenue (e.g., [30, 5, 11, 12, 1, 14, 24, 9, 19, 7]). A key result from
these studies is that when valuations satisfy submodularity over signals (SOS)
— capturing valuations with diminishing returns — it is possible to obtain a
constant-factor approximation of the optimal welfare through a truthful
auction [12, 1, 24]. A valuation function satisfies SOS if, for any $j$, the
effect of an increase in $s_{j}$ is more significant when the other signals
$s_{-j}$ are lower. This class of valuations captures a variety of natural
settings where information (signals) have decreasing marginal returns,
including those frequently explored in the literature, such as art auctions
and mineral rights auctions. Quite remarkably, these results apply to a much
broader range of auction settings than single-item auctions. In particular,
[12] provides a $4$-approximation for welfare for general combinatorial
auctions under SOS and separable valuations.

Private valuation functions. A crucial assumption that drives the above
results is that while the signals are private information, the valuation
functions mapping signals to values are publicly known. This assumption may be
quite controversial in real-world scenarios, as the way by which a bidder
assesses the value of an item, considering all available information from
others, may remain private to that bidder. This concern has led to a new line
of work studying the interdependent values model under the setting where both
the signals and the valuation functions are private. This environment proves
to be significantly more challenging than its public valuations counterpart.
For example, even in single-item auctions with valuations satisfying single-
crossing (which enables optimal welfare under public valuations), one cannot
guarantee better than the trivial $n$-approximation [14].

The state of the art results for interdependent valuations with private
signals and valuation functions are the following: (i) A truthful mechanism
for single-item auctions with SOS valuations, that gives a
$5.55$-approximation with respect to the optimal welfare [14, 15]. (ii) A
truthful mechanism for single-item auctions with valuations satisfying a
natural property called $d$-critical, that gives a (tight)
$(d+1)$-approximation with respect to the optimal welfare [14]. A valuation
$v$ is $d$-critical if, for every signal profile
$\mathbf{{s}}=(s_{1},\ldots,s_{n})$, there exist at most $d$ bidders $j$ for
whom reducing $s_{j}$ changes the value of $v(\mathbf{{s}})$.

Two primary open problems emerge from the current research landscape. First,
for single-item auctions, there exists a $5.55$-approximation, and it is known
that one cannot get a better approximation factor than $2$ [12]. Shrinking
this gap is a clear open problem. Second, work on interdependent settings with
private valuation functions has focused primarily on single-item auctions
(with some extensions to settings with identical items and unit-demand
valuations [15]). This is in stark contrast to interdependent settings with
public valuation functions, where the approximation results extend to
significantly broader settings. Providing approximation results for private
interdependent valuations, in settings beyond single-item auctions, stands as
a major open problem.

###  1.1 Our Results

In this paper, we address and make progress on both of the aforementioned open
problems. Our first result is improving the state of the art for single-item
actions with SOS valuations:

Theorem 1 (Theorem 3.1): For any single-item auction with private
interdependent, SOS valuations, there exists a truthful mechanism that gives
$5$-approximation with respect to the optimal social welfare.

Beyond improving the approximation factor for SOS valuations, a key component
of our result is a new _eating mechanism_ for this setting, which might be of
independent interest. The mechanism starts with a single unit of allocation
probability. Ideally, we envision an eating process wherein each bidder $i$
begins to consume at a moment determined by her value $v_{i}(\mathbf{{s}})$
(with those having higher valuations starting first). This approach, however,
does not yield a truthful mechanism. To address this, we implement $n$
separate eating processes, one for each bidder. The allocation probability for
bidder $i$ then depends on bidder $i$’s true value $v_{i}(\mathbf{{s}})$, and
on the other bidders’ _shadow values_ ${v}_{j}(\mathbf{{s}}_{-i},0_{i})$ that
don’t depend on $i$’s signal. The challenge is to construct this mechanism in
a way that ensures feasibility, namely that the sum of all allocation
probabilities does not exceed $1$, while still ensuring good approximation
guarantees. To this end, we formulate the eating process solution via a Linear
Program (LP) and apply LP duality to bound the allocation probabilities.

Interestingly, the RCF mechanism described in [15] employs a filtering process
that determines a bidder’s candidacy based on a random discretization and tie-
breaking order. In a way, our eating mechanism is analogous to the
probabilistic serial rule, whereas the RCF mechanism is analogous to the
random serial dictatorship rule.

Our second result concerns settings with private interdependent, $d$-critical
valuations. For this valuation class, we extend the prior results beyond
single-item auctions, to any auction setting where the set of bidders that can
be simultaneously served is subject to matroid feasibility constraints.

Theorem 2 (Theorem 4.1): For any auction setting with matroid feasibility
constraints (on the set of bidders that can be simultaneously served) and
private interdependent, $d$-critical valuations, there exists a truthful
mechanism that gives the tight $(d+1)$-approximation with respect to the
optimal social welfare.

Interestingly, the approximation ratio of $(d+1)$ is proven to be tight, even
for the single-item setting [14]. In order to extend the result for _any_
matroid feasibility constraint, we carefully generalize the mechanism for
single-item auction outlined in [14].

The high-level intuition for the single-item auction is that a bidder $i$
qualifies as a candidate for allocation if and only if her value
$v_{i}(\mathbf{{s}})$ exceeds the shadow values
${v}_{j}(\mathbf{{s}}_{-i},0_{i})$ of all other bidders $j\neq i$. Notably,
the bidder $i^{\star}$ with the true highest value always qualifies as a
candidate, with the only additional potential candidates being the $\leq d$
bidders whose signals can reduce $v_{i^{\star}}(\mathbf{{s}})$.

Building upon this intuition, we introduce a candidate filtering algorithm
that designates bidder $i$ as a candidate if and only if she belongs to the
maximal independent set, when using the shadow values of others. A key
challenge here is to show that all bidders in the true optimal set $I^{\star}$
are selected as candidates, and the only other potential candidates are those
who can reduce the value of the bidders in $I^{\star}$. We then need to
address the challenge that the set of candidates may not be feasible. To
overcome this issue, we employ the matroid partition theorem of Edmonds [17],
showing that the set of candidates can be partitioned into at most $(d+1)$
independent sets, allowing us to provide an ex-post feasible allocation by
selecting each of these independent sets with probability $1/(d+1)$.

We also note that, this mechanism can be adjusted to scenarios where every
agent $i$ has a $d_{i}$-critical valuation, with an unknown $d_{i}$. In this
case, the mechanism can be extended to obtain
$2(\max_{i}(d_{i})+1)$-approximation.

A natural open problem arising from our work is whether there exists a
truthful mechanism for private interdependent, SOS valuations with matroid
feasibility constraints. We believe that our new eating mechanism may be a
promising direction for resolving this problem, as it sidesteps the
complexities associated with random ordering (as was required in the previous
approach taken by Eden et al. [15]), which is hard to analyze in matroid
settings, as evident by the notoriously hard matroid secretary problem [3].

###  1.2 Related Work

The two most closely related works are Eden et al. [14], who are the first to
study interdependent values with private valuation functions and provide an
$O(\log^{2}n)$-approximation to the optimal welfare for single-item auctions
under SOS valuations, and Eden et al. [15], who improve this to a
$5.5$-approximation and extend the result to multi-unit auctions. In addition,
these papers also establish a $(d+1)$-approximation for single-item auctions
with $d$-critical valuations. A more general class of valuations called
$d$-self-bounding is considered in [15], for which an $O(d)$-approximation is
provided. Dasgupta and Maskin [10] study a related setting where the valuation
function is unknown to the seller but the bidders are aware of each others’
valuation functions. They design a mechanism where the bidders report a
complicated contingent bidding function, and show that under single-crossing
type conditions there is a fully efficient equilibrium.

The interdependent model with public valuations has attracted extensive work
in economics for decades, establishing strong impossibilities for obtaining
optimal welfare truthfully unless the valuations satisfy some strong condition
such as single-crossing [25, 10, 21, 2]. Many additional studies have explored
the interdependent values model in a variety of scenarios, often incorporating
single-crossing type assumptions (e.g., [8, 20, 29, 6]).

Recently, there has been a surge of research within EconCS focusing on the
interdependent values model from an algorithmic perspective. Roughgarden and
Talgam-Cohen [30] study prior-independent mechanisms that are approximately
optimal in the revenue maximization regime for single parameter settings with
downward closed constraints and further provide conditions under which
Myerson-like virtual welfare maximization obtains optimal revenue. Li [23]
provides simple VCG-based mechanisms that obtain near-optimal revenue under
MHR distributions and matroid feasibility constraints. Chawla et al. [5]
provide approximation guarantees for revenue in single-parameter settings with
matroid feasibility constraints under relaxed assumptions. These results
assume some form of single-crossing type condition in order to obtain positive
results.

Eden et al. [11] provide approximation guarantees for welfare in prior-free
single-item auction settings when the valuation functions are _approximately_
single-crossing. Eden et al. [12] were the first to study public SOS
valuations in interdependent setting and provide a $4$-approximation for any
single-parameter setting with downward closed feasibility constraints (without
any single-crossing type assumption). They also study combinatorial auctions
and provide a $4$-approximation under an additional condition of seperable
valuations. Amer and Talgam-Cohen [1] and Lu et al. [24] provide improved
approximation guarantees for the single-item setting. Eden et al. [13] study
price of anarchy bounds for simple non-truthful mechanisms, and Gkatzelis et
al. [19] show that clock auctions can obtain approximately optimal welfare
under certain assumptions on valuation functions and finite signal space.
Cohen et al. [9] study approximation guarantees for the public projects
setting with interdependent values, and Birmpas et al. [4] study a fair
division problem with interdependence.

##  2 Preliminaries

###  2.1 Interdependent Valuations and Truthful Mechanisms

We consider an auction with $n$ bidders with interdependent valuations. Every
bidder $i\in[n]$ has a private signal ${s}_{i}\in S_{i}$, capturing bidder
$i$’s private information about the item, where $S_{i}$ denotes the signal
space of bidder $i$. Wlog assume that the minimum signal in $S_{i}$ is $0$,
for every $i$. We denote by $\mathbf{S}=S_{1}\times\ldots\times S_{n}$ the
joint signal space of the bidders, and by
$\mathbf{{s}}=({s}_{1},\ldots,{s}_{n})\in\mathbf{S}$ a signal profile. As is
standard, we denote by
$\mathbf{{s}}_{-i}=({s}_{1},\ldots,{s}_{i-1},{s}_{i+1},\ldots,{s}_{n})$ the
signal profile of all bidders other than bidder $i$.

In addition to the signal, every bidder $i$ has a private monotone valuation
function ${v}_{i}:\mathbf{S}\rightarrow\mathbb{R}_{+}$, which maps every
signal profile $\mathbf{{s}}=({s}_{1},\ldots,{s}_{n})$ into a non-negative
real number, which is bidder $i$’s value for the item. We denote by
$V_{i}\subseteq\mathbb{R}_{+}^{\mathbf{S}}$ the valuation space of bidder $i$,
and by $\mathbf{V}=V_{1}\times\ldots\times V_{n}$ the joint valuation space of
all bidders. A vector $\mathbf{{v}}=({v}_{1},\ldots,{v}_{n})\in\mathbf{V}$
denotes a valuation profile.

We refer to bidder $i$’s value under signal profile $\mathbf{{s}}$ as $i$’s
real value. We sometimes refer to a low estimate of bidder $i$’s value, where
bidder $j$’s signal is zeroed out; i.e., $v_{i}(\mathbf{{s}}_{-j},0_{j})$; we
refer to this value as bidder $i$’s shadow value.

A mechanism is defined by a pair $(\mathbf{{x}},\mathbf{{p}})$ denoting the
mechanism’s allocation and payment rules, based on the bidders’ reports of
their signals and valuations. The allocation rule
$\mathbf{{x}}:\mathbf{S}\times\mathbf{V}\rightarrow[0,1]^{n}$ returns the
allocation probability ${x}_{i}(\mathbf{{s}},\mathbf{{v}})$ for every bidder
$i$, and the payment rule
$\mathbf{{p}}:\mathbf{S}\times\mathbf{V}\rightarrow\mathbb{R}_{+}^{n}$ returns
the payment ${p}_{i}(\mathbf{{s}},\mathbf{{v}})$ every bidder $i$ for reported
signals $\mathbf{{s}},\mathbf{{v}}$.

Unless specified otherwise, we access bidder valuations via value queries;
namely, given a signal profile $\mathbf{{s}}$, bidder $i$’s value oracle
${v}_{i}$ returns ${v}_{i}(\mathbf{{s}})$. A mechanism is said to be
polynomial if it makes a polynomial number of value queries.

A mechanism $(\mathbf{{x}},\mathbf{{p}})$ is said to be truthful if it is an
ex-post Nash equilibrium for the bidders to truthfully report their private
information (signals and valuations). In our query access model, truthfulness
means that it is in every bidder’s best interest to answer every query
truthfully, given that other bidders do the same.

######  Definition 2.1 (EPIC-IR).

A mechanism $(\mathbf{x},\mathbf{p})$ is ex-post incentive compatible (IC) if
for every
$i\in[n],\mathbf{{s}}\in\mathbf{S},\mathbf{{v}}\in\mathbf{V},{s}_{i}^{\prime}\in
S_{i},{v}_{i}^{\prime}\in V_{i}$

$x_{i}(\mathbf{{s}},\mathbf{{v}})\cdot
v_{i}(\mathbf{{s}})-p_{i}(\mathbf{{s}},\mathbf{{v}})\geq
x_{i}(\mathbf{{s}}_{-i},{s}_{i}^{\prime},\mathbf{{v}}_{-i},{v}^{\prime}_{i})\cdot
v_{i}(\mathbf{{s}})-p_{i}(\mathbf{{s}}_{-i},{s}_{i}^{\prime},\mathbf{{v}}_{-i},{v}^{\prime}_{i}).$
(1)

It is ex-post individually rational (IR) if for every $i\in[n]$,
$\mathbf{{s}}\in\mathbf{S}$, and $\mathbf{{v}}\in\mathbf{V}$

$x_{i}(\mathbf{{s}},\mathbf{{v}})\cdot
v_{i}(\mathbf{{s}})-p_{i}(\mathbf{{s}},\mathbf{{v}})\geq 0$ (2)

It is EPIC-IR if it is both ex-post IC and ex-post IR. An allocation
$\mathbf{{x}}$ is EPIC-IR implementable if there exists a payment rule
$\mathbf{{p}}$ such that the pair $(\mathbf{{x}},\mathbf{{p}})$ is EPIC-IR.

It is well known that even when the valuation functions are public, this is
the strongest possible solution concept when dealing with interdependent
valuations.111Dominant strategy incentive-compatibility does not make sense,
as a bidder $i$ might not be willing to win if other bidders over-bid, which
causes the winner to over-pay and incur a negative utility.

Eden et al. [14] give a sufficient condition for an allocation rule
$\mathbf{{x}}$ to be EPIC-IR implementable.

######  Proposition 2.1 (Eden et al. [14]).

An allocation rule $\mathbf{{x}}$ is EPIC-IR implementable if for every bidder
$i$, ${x}_{i}$ depends only on $\mathbf{{s}}_{-i},\mathbf{{v}}_{-i}$ and
${v}_{i}(\mathbf{{s}})$, and is non-decreasing in ${v}_{i}(\mathbf{{s}})$.

For an (EPIC-IR) implementable $\mathbf{{x}}$, the corresponding payment rule
$\mathbf{{p}}$ is given by:

$p_{i}(\mathbf{{s}},\mathbf{{v}}):=x_{i}(\mathbf{{s}}_{-i},\mathbf{{v}}_{-i},{v}_{i}(\mathbf{{s}}))\cdot{v}_{i}(\mathbf{{s}})-\int_{0}^{{v}_{i}(\mathbf{{s}})}x_{i}(\mathbf{{s}}_{-i},\mathbf{{v}}_{-i},t)\,\mathrm{d}t.$
(3)

That is, bidder $i$’s allocation may depend on all other bidders’ signals and
valuation functions, and it can only depend on bidder $i$’s signal ${s}_{i}$
or valuation function $v_{i}$ through the numerical value
$v_{i}(\mathbf{{s}})$. Eden et al. [14] show that this condition is almost
necessary in order to be EPIC-IR implementable.222The necessary conditions for
EPIC-IR implementablity are (i) $x_{i}$ is monotone in $v_{i}(\mathbf{{s}})$,
and (ii) for a given $\mathbf{{s}}_{-i}$, the set of signals
$s_{i},s^{\prime}_{i}$ and valuation functions $v_{i},v^{\prime}_{i}$ such
that
$v_{i}(s_{i},\mathbf{{s}}_{-i})=v^{\prime}_{i}(s^{\prime}_{i},\mathbf{{s}}_{-i})$
and $x_{i}(v_{i},s_{i},\mathbf{{s}}_{-i})\neq
x_{i}(v^{\prime}_{i},s^{\prime}_{i},\mathbf{{s}}_{-i})$ has measure $0$.

###  2.2 Valuations Classes

We focus on two classes of valuations which are well-studied in the context of
interdependent values with private valuation functions, namely SOS valuations
and $d$-critical valuations.

######  Definition 2.2 (SOS Valuations).

A valuations function $v:\mathbf{S}\rightarrow\mathbb{R}_{+}$ is Submodular
over signals (or SOS) if for every $i$, $s_{i}\in S_{i}$,
$\mathbf{{s}}_{-i},\hat{\mathbf{{s}}}_{-i}\in\mathbf{S}_{-i}$ such that
$\mathbf{{s}}_{-i}\preceq\hat{\mathbf{{s}}}_{-i}$, and $\delta>0$,

$\displaystyle
v(s_{i}+\delta,\mathbf{{s}}_{-i})-v(s_{i},\mathbf{{s}}_{-i})\geq
v(s_{i}+\delta,\hat{\mathbf{{s}}}_{-i})-v(s_{i},\hat{\mathbf{{s}}}_{-i}).$ (4)

The SOS class includes most valuation classes studied in the literature on
interdependent values, including the resale model (i.e., affine functions)
[27, 22], the mineral rights model [31], average value, etc.

Previous work [14, 24, 15] has shown that SOS valuations satisfy a useful
property called self-bounding, where
$\sum_{i=1}^{n}({v}(\mathbf{{s}})-{v}(\mathbf{{s}}_{-i},0_{i}))\leq{v}(\mathbf{{s}})$.
This is cast in the following lemma.

######  Lemma 2.1 (SOS functions are self-bounding [14, 24]).

For every monotone SOS valuation function
$v:\mathbf{S}\rightarrow\mathbb{R}_{+}$, and every signal profile
$\mathbf{{s}}$, we have

$\sum_{i=1}^{n}({v}(\mathbf{{s}})-{v}(\mathbf{{s}}_{-i},0_{i}))\leq{v}(\mathbf{{s}}).$

We now turn to define $d$-critical valuations.

######  Definition 2.3 ($d$-critical Valuations).

A valuation function $v:\mathbf{S}\rightarrow\mathbb{R}_{+}$ is $d$-critical
if for every $\mathbf{{s}}\in\mathbf{S},$

$\displaystyle|\\{j\ :\ {v}(\mathbf{{s}}_{-j},0_{j})<v(\mathbf{{s}})\\}|\leq
d.$ (5)

A few natural functions that lie in low levels of the $d$-critical hierarchy
are: (i) max signal is $1$-critical, (ii) any weighted matroid function over
signals with rank $d$ is $d$-critical, (iii) values derived from a social
network with $d$-bounded degrees (where every bidder’s value is an arbitrary
function of its neighbors’ signals) are $d$-critical.

Eden et al. [14] show the following impossibility for (a special case of)
$d$-critical valuations.

######  Proposition 2.2 (Eden et al. [14]).

For every EPIC-IR single-item auction for $d$-critical valuations, there
exists an instance for which the obtained welfare cannot give better than
$(d+1)$-approximation for the optimal welfare.

###  2.3 Matroid Preliminaries

In Section 4, we consider auctions where the feasible sets of bidders that can
be served are independent sets of a matroid. The definition of a matroid
follows.

######  Definition 2.4 (Matroid).

A matroid is a pair $M=([n],\mathcal{I})$, where $[n]$ is a set of elements,
and $\mathcal{I}$ is a (non-empty) collection of subsets of $[n]$, which are
the independent sets of the matroid, satisfying:

  * •

Downward closed: If $I\in\mathcal{I}$ then $A\in\mathcal{I}$ for all subsets
$A\subseteq I$.

  * •

Exchange property: If $A,B\in\mathcal{I}$ with $|A|<|B|$ then there exists
$i\in B\setminus A$ such that $A\cup\\{i\\}\in\mathcal{I}$.

######  Definition 2.5 (Rank Function).

For a subset of elements $S\subseteq[n]$, let $rank(S)=\max_{I\subseteq S\ :\
I\in\mathcal{I}}|I|$. $rank(M)=rank([n])$ is referred to as the matroid’s
rank.

The rank function is submodular [28]. That is, for every $S\subseteq
T\subseteq[n]$, and for every $i\in[n]$, $rank(S\cup\\{i\\})-rank(S)\geq
rank(T\cup\\{i\\})-rank(T).$

Greedy algorithm. Consider a matroid with weighted elements, where the weight
function $w:[n]\rightarrow\mathbb{R}^{+}$ assigns a non-negative weight to
every element $i\in[n]$. The greedy algorithm with weights $w$ operates by
sorting the elements in $[n]$ in non-increasing order of $w$ and then
sequentially adds elements to maintain an independent set. Specifically, the
algorithm starts with an empty set $I^{\star}$ and, for each element $i$ in
the specified order, adds $i$ to $I^{\star}$ if
$I^{\star}\cup\\{i\\}\in\mathcal{I}$. It is well known that the greedy
algorithm produces an independent set $I^{\star}$ with maximum weight. This is
cast in the following theorem.

######  Theorem 2.1 (Greedy is Optimal (Edmonds [17])).

Let $I^{\star}$ be the set returned by the greedy algorithm on a matroid
$M=([n],\mathcal{I})$. It holds that

  1. 1.

$|I^{\star}|=rank(M)$.

  2. 2.

$\sum_{i\in I^{\star}}w(i)=\max_{I\in\mathcal{I}}\sum_{i\in I}w(i)$.

For our result, we need the following lemma about the greedy algorithm.

######  Lemma 2.2.

Let $i\in[n]$ be some element in $M$. Consider two weight functions
$w,\hat{w}$, where $\hat{w}(i)\geq w(i)$ and $\hat{w}(j)\leq w(j)$ for every
$j\neq i$. If $i$ is selected by the greedy algorithm with weights $w$ and
some tie-breaking rule, then $i$ is also selected by the greedy algorithm with
weights $\hat{w}$ and the same tie-breaking rule.

###### Proof.

Consider the ordering $\sigma$ which results by ordering the elements
according to $w$ using some tie-breaking rule. By renaming, assume we break
ties in favor of lower-index elements. Let $I^{\star}$ be the obtained
independent set. Consider an element $i\in I^{\star}$ and consider $\hat{w}$
such that $\hat{w}(i)\geq w(i)$ and $\hat{w}(j)\leq w(j)$ for $j\neq i$. Let
$\hat{\sigma}$ and $\hat{I}^{\star}$ be the ordering and the independent set
determined according to $\hat{w}$ when breaking ties in favor of lower-index
elements. Let $A$ and $\hat{A}$ be the sets of elements that appear before $i$
when ordering the elements according to orders $\sigma$ (i.e., according to
$w$) and $\hat{\sigma}$ (i.e., according to $\hat{w}$), respectively. Since in
order $\hat{\sigma}$, $\hat{w}(i)\geq w(i)$ while $\hat{w}(j)\leq w(j)$ for
$j\neq i$, $\hat{A}\subseteq A$. We transform $\sigma$ into $\hat{\sigma}$ in
three steps, and show that after each step, $i$ is still chosen by the greedy
algorithm (see Figure 1 for a schematic depiction of the transitions).

First, consider an ordering $\sigma^{\prime}$ which reorders elements in $A$
to have the same relative ordering as in $\hat{\sigma}$, but does not change
the ordering of all other elements. In $\sigma^{\prime}$, the set of elements
ordered before $i$ is still $A$. Moreover, the first $|\hat{A}|$ elements in
order $\sigma^{\prime}$ are exactly $\hat{A}$. Let $I^{\star}_{i}$ and
$I^{\prime}_{i}$ be the sets of elements added by running the greedy algorithm
on orders $\sigma$ and $\sigma^{\prime}$, respectively, just before element
$i$’s turn. By Theorem 2.1, $|I^{\star}_{i}|=|I^{\prime}_{i}|=rank(A)$. Since
$i$ is added to $I^{\star}$ in ordering $\sigma$,
$I^{\star}_{i}\cup\\{i\\}\in\mathcal{I}\rightarrow
rank(A\cup\\{i\\})=rank(A)+1=|I^{\prime}_{i}|+1$. Again, by Theorem 2.1, it
must be that $i$ is added to $I^{\prime}_{i}$ in ordering $\sigma^{\prime}$.

For the second step, we move $i$ to be right after set $\hat{A}$ in the
ordering $\sigma^{\prime}$, bumping up one spot each element in
$A\setminus\hat{A}$. Let $\sigma^{\prime\prime}$ be the resulting ordering.
Notice that up until the position of element $i$ in the order, including, the
elements are ordered the same as in $\hat{\sigma}$. Let $I^{\prime\prime}_{i}$
be the set of elements added by the greedy algorithm in order
$\sigma^{\prime\prime}$ up until element $i$’s turn. Since up until this
point, the order of the elements in $\sigma^{\prime}$ and
$\sigma^{\prime\prime}$ is the same, $I^{\prime\prime}_{i}\subseteq
I^{\prime}_{i}$. Therefore, since $\mathcal{I}$ is downwards-closed, it must
be the case that $i$ can be added to $I^{\prime\prime}_{i}$ as well.

To finish the proof, we now order the elements after $i$ to be in the same
order as in $\hat{\sigma}$, thus recovering order $\hat{\sigma}$. Notice that
elements ordered after $i$ in an instance of the greedy algorithm cannot
determine whether $i$ is selected or not. Therefore, $i$ is selected by
running greedy on $\hat{\sigma}$ to be in $\hat{I}^{\star}$, finishing the
proof. ∎

$\hat{A}$$i$$\hat{\sigma}_{[n]\setminus(\hat{A}\cup
i)}$$\hat{\sigma}$$\hat{A}$$i$${A}\setminus\hat{A}$$\sigma_{[n]\setminus(A\cup
i)}$$\sigma^{\prime\prime}$$\hat{A}$${A}\setminus\hat{A}$$i$$\sigma_{[n]\setminus(A\cup
i)}$$\sigma^{\prime}$$A$$i$$\sigma_{[n]\setminus(A\cup i)}$$\sigma$ Figure 1:
The transitions from $\sigma$ to $\hat{\sigma}$ used in the proof of Lemma
2.2.

We will also use the following known theorem about matroids.

######  Theorem 2.2 (Matroid partition (Edmonds [16])).

Given a matroid $M$ over a ground set $[n]$, it is possible to find a
partitioning $M=I_{1}\uplus\dots\uplus I_{t}$ with $t$ pairwise disjoint
independent sets $I_{1},\dots,I_{t}\in\mathcal{I}$ if and only if

$\displaystyle\forall S\subseteq[n],\quad|S|\leq t\cdot rank(S).$ (6)

Moreover, there exist efficient algorithms to find such partitioning.

##  3 Eating Mechanism for Single-Item Auctions with SOS Valuations

In this section, we present a truthful mechanism that improves upon the state-
of-the-art approximation for single-item auctions with SOS valuations. We
start by introducing a new _eating mechanism_ , and then show that this
mechanism is truthful and provides a $5$-approximation to the optimal welfare
for SOS valuations. The main theorem of this section follows.

######  Theorem 3.1.

Mechanism 1 (the eating mechanism) is an EPIC-IR mechanism that obtains a
$5$-approximation to the optimal welfare when the bidders have interdependent
values with private SOS valuations.

The proof of Theorem 3.1 unfolds as follows. In Lemma 3.2 we show that the
mechanism is EPIC-IR, in Lemma 3.3 we show that the mechanism, if feasible,
gives $5$-approximation to the optimal welfare, and in Lemma 3.4 we prove that
the mechanism is feasible. Collectively, these lemmas prove Theorem 3.1.

Before presenting the lemmas, we give an informal description of the
mechanism, and present a linear program whose solution coincides with the
allocation probabilities produced by the eating mechanism (as shown in Lemma
3.1).

The eating mechanism. Our mechanism considers $n$ separate eating processes,
one for each bidder, where the eating process corresponding to bidder $i$
determines $i$’s share of the allocation probability. In bidder $i$’s eating
process, we use $i$’s real value, and for all other bidders $j\neq i$, we use
their shadow values (i.e., their values when $i$’s signal is zeroed out). In
particular, every bidder $j$ starts eating at a time that depends on her
(shadow) value (with higher valued bidders starting earlier). At each point in
time, all the bidders eating at that time, eat at the same speed. The eating
process ends when the total share eaten is $1$.333Note that some bidders may
not even start eating before the process ends, leading to a share of 0. Bidder
$i$ is then allocated her (normalized) share obtained in this process. Figure
2 depicts the eating process used to determine $i$’s allocation.

time$-\ln{v}_{j}(\mathbf{{s}}_{-i},0_{i})$$-\ln
v_{i}(\mathbf{{s}})$$-\ln{v}_{j^{\prime}}(\mathbf{{s}}_{-i},0_{i})$$t$ Figure
2: The eating process used to determine bidder $i$’s allocation. bidder $i$
starts eating at time $-\ln v_{i}(\mathbf{{s}})$ and all other bidders $j\neq
i$ start eating at time $-\ln{v}_{j}(\mathbf{{s}}_{-i},0_{i})$. At each point
in time, all bidders eating at that time eat at the same speed. The solid blue
line denotes bidder $i$’s share and the dashed blue line denotes $j$’s
(pretend) share. The red square denotes the time $t$ when the sum of the blue
lines adds up to $1$, thus halting the eating process.

Function $\texttt{eat}(\text{weight function
}w:[n]\rightarrow\mathbb{R}_{+}):$

  1. 1.

Each bidder $j$ starts eating at time $-\ln(w(j))$, and eats at a constant
speed of $1$.

  2. 2.

Eating stops at time $t$, when the item has been entirely eaten, that is when
$\sum_{j=0}^{n}(t+\ln w(j))^{+}=1$.

  3. 3.

Return the allocation, that is the vector y where $y_{j}=(t+\ln w(j))^{+}$.

Mechanism $\texttt{eating}:$

  1. 1.

Elicit signals $\mathbf{\hat{s}}$ and valuation functions $\mathbf{\hat{v}}$.

  2. 2.

For each bidder $i$:

Define the function $w_{i}$ where $w_{i}(i)=\hat{v}_{i}(\mathbf{\hat{s}})$ and
$w_{i}(j)=\hat{v}_{j}(\mathbf{\hat{s}}_{-i},0_{i})$ for $j\neq i$.

Set $x_{i}\leftarrow\texttt{eat}(w_{i})_{i}/4$, that is, the $i$-th coordinate
of $\texttt{eat}(w_{i})$, divided by $4$.

* 3.

Charge payments using Eq (3).

Mechanism 1 Eating Mechanism.

For the sake of the analysis, we formulate the eating process as the solution
of the following linear program ($P_{i}$):

maximize $\displaystyle y_{i}$ $\displaystyle(P_{i})$ such that $\displaystyle
y_{i}\leq y_{j}+\ln(w(i))-\ln(w(j))\quad\forall j\neq i$
$\displaystyle\textstyle\sum_{i}y_{i}\leq 1$ $\displaystyle
y_{1},\dots,y_{n}\geq 0.$

Lemma 3.1 shows that the (pre-normalized) share allocated to bidder $i$ by the
eating mechanism equals the value of the linear program $(P_{i})$.

To establish the feasibility of Mechanism 1, we will show in Lemma 3.4 that
the sum of probabilities assigned to the bidders does not exceed 1. We obtain
an upper-bound on the (pre-normalized) share of bidder $i$ in the primal
program $(P_{i})$ using a feasible solution to the dual program $(D_{i})$
presented below.

minimize $\displaystyle\alpha_{i}+\textstyle\sum_{j\neq
i}\beta_{i,j}\cdot(\ln(w(i))-\ln(w(j)))$ $\displaystyle(D_{i})$ such that
$\displaystyle\alpha_{i}+\textstyle\sum_{j\neq i}\beta_{i,j}\geq 1$
$\displaystyle\alpha_{i}\geq\beta_{i,j}\quad\forall j\neq i$
$\displaystyle\alpha_{i}\geq 0,\quad\;\beta_{i,j}\geq 0\quad\forall j\neq i.$

The following lemma shows that the value of the primal LP $(P_{i})$ of bidder
$i$ equals the (pre-normalized) share of bidder $i$ in the eating mechanism.

######  Lemma 3.1.

Given a weight function $w$, the function eat$(w)$ assigns bidder $i$ a share
that equals the value of the linear program $(P_{i})$ if it is feasible, and
$0$ otherwise. In particular, it is non-decreasing in $w(i)$, and non-
increasing in every $w(j)$ with $j\neq i$.

###### Proof.

First, we give another linear program $(P_{i}^{\prime})$ which is analogous to
the eating procedure. We show that $(P_{i})$ is feasible if and only if
$(P_{i}^{\prime})$ has a non-negative solution, in which case they both have
the same value.

maximize $\displaystyle t+\ln(w(i))$ $\displaystyle(P_{i}^{\prime})$ such that
$\displaystyle t+\ln(w(j))\leq z_{j}\qquad\forall j\in[n]\quad$
$\displaystyle\textstyle\sum_{i}z_{i}\leq 1$ $\displaystyle
z_{1},\dots,z_{n}\geq 0.$

Observe that $t$ denotes the stopping time of the eating process, given that
each bidder $j$’s share is at least $t+\ln(w_{j})$ and the total share sums up
to at most $1$. Since $t$ can be negative, $(P_{i}^{\prime})$ is always
feasible. By construction, the $i$-th coordinate of $\texttt{eat}(w)$ is equal
to $(t+\ln(w(i)))^{+}$. When $t+\ln(w(i))\geq 0$, setting $y_{j}=z_{j}$ and
$y_{i}=t+\ln(w(i))$ gives a feasible solution of the linear program $(P_{i})$.
Conversely, given a feasible solution $(y_{1},\dots,y_{n})$ to $(P_{i})$,
setting $z_{j}=y_{j}$ and $t=y_{i}-\ln(w(i))$ gives a solution to
$(P_{i}^{\prime})$ with value $t+\ln(w(i))\geq 0$.

To show the monotonicity properties, observe that increasing $w(i)$ or
decreasing $w(j)$ makes the constraints of $(P_{i})$ looser, which cannot
decrease the objective or make the program infeasible. ∎

We are now ready to prove Theorem 3.1. We first show that Mechanism 1 is
truthful.

######  Lemma 3.2.

Mechanism 1 is EPIC-IR.

###### Proof.

By Proposition 2.1, it suffices to show that $i$’s allocation depends only on
$\mathbf{\hat{s}}_{-i}$, $\mathbf{\hat{v}}_{-i}$, and
$\hat{v}_{i}(\mathbf{\hat{s}})$, and is monotone non-decreasing in
$\hat{v}_{i}(\mathbf{\hat{s}})$. The first property holds by design, and
monotonicity holds by Lemma 3.1, showing that $x_{i}$ is increasing in
$\hat{v}_{i}(\mathbf{{s}})$. ∎

Given that the mechanism is truthful, we hereafter simplify notation and write
$\mathbf{{s}}$ and $\mathbf{{v}}$ instead of $\mathbf{\hat{s}}$ and
$\mathbf{\hat{v}}$. The following lemma establishes the approximation factor
of the mechanism.

######  Lemma 3.3.

Mechanism 1 gives $5$-approximation to the optimal welfare.

###### Proof.

We define the weight function $w^{\star}(j)={v}_{j}(\mathbf{{s}})$ mapping
each bidder to their true value. First, by monotonicity of the function eat,
we have that each bidder $i$ gets an allocation probability
$x_{i}=\texttt{eat}(w_{i})_{i}/4$ which is at least
$\texttt{eat}(w^{\star})_{i}/4$, because we replaced low estimates with the
true value for each bidder $j\neq i$ (i.e., $w^{\star}(j)\geq w_{i}(j)$ for
all $j$). Hence, the expected welfare is at least

$\sum_{i=1}^{n}{v}_{i}(\mathbf{{s}})\cdot\frac{\texttt{eat}(w^{\star})_{i}}{4}.$

Let $i^{\star}$ be the bidder with the highest value, and let $y_{i^{\star}}$
be the (pre-normalized) probability share she receives from the eating
procedure with weight function $w_{i^{\star}}$. Observe that, in this eating
process, all bidders stop eating by time
$y_{i^{\star}}-\ln({v}_{i^{\star}}(\mathbf{{s}}))$, and thus the
$(1-y_{i^{\star}})$ share which has not been eaten by $i^{\star}$ has been
eaten by someone who has value at least
$\exp(\ln({v}_{i^{\star}}(\mathbf{{s}}))-y_{i^{\star}})$. Therefore, the
overall welfare is greater than or equal to

${v}_{i^{\star}}(\mathbf{{s}})\cdot\frac{y_{i^{\star}}+(1-y_{i^{\star}})e^{-y_{i^{\star}}}}{4}.$

The function $y+(1-y)e^{-y}$ has a minimum approximately equal to $0.8005$ at
$y\approx 0.44$. Therefore, after normalizing the probability shares by $4$,
the expected welfare is at least
${v}_{i^{\star}}(\mathbf{{s}})\cdot\frac{0.8005}{4}\geq{v}_{i^{\star}}(\mathbf{{s}})/5$.
∎

Finally, the following lemma confirms the mechanism’s feasibility.

######  Lemma 3.4.

Mechanism 1 is feasible when bidders have SOS valuation functions; that is,
the sum of probabilities $x_{1}+\dots+x_{n}$ is at most $1$.

###### Proof.

First, define the set $S$ of bidders $i$ who receive a positive probability
$x_{i}>0$ from the algorithm. For the sake of the analysis, observe that we
can restrict our instance to bidders in $S$, because doing so cannot decrease
the sum of probabilities. Indeed, removing $j\notin S$ does not decrease their
probability $x_{j}=0$, and when computing the probability of a bidder $i\in
S$, removing $j$ is equivalent to replacing ${v}_{j}(\mathbf{{s}}_{-i},0_{i})$
by $0$, which cannot decrease $x_{i}$ by the monotonicity property of Lemma
3.1. For simplicity of notations, we assume (without loss of generality) that
$S=[n]$, i.e. we relabel bidders and set $n$ to be the size of $S$.

We are now ready to start bounding the probabilities, and we define

$\forall i\in[n],\quad y_{i}=\texttt{eat}(w_{i})_{i}>0,\qquad\text{where
}w_{i}(i)={v}_{i}(\mathbf{{s}})\text{ and
}w_{i}(j)={v}_{j}(\mathbf{{s}}_{-i},0_{i})\text{ for }j\neq i$

and our goal is to give an upper show that $y_{1}+\dots+y_{n}\leq 4$. For all
$i$, we consider the dual $(D_{i})$ of the linear program $(P_{i})$ from Lemma
3.1. We now define a feasible solution to all dual linear programs. The main
insight is that we will choose symmetric
$\beta_{i,j}:=\gamma_{i,j}\cdot\gamma_{j,i}/n$, where $\gamma_{i,j}$’s will be
set later. This way, we will be able to swap the indices $i$ and $j$ in
${v}_{i}(\mathbf{{s}}_{-j},0_{j})$ which appear in the upper-bound:

$\displaystyle\sum_{i=1}^{n}y_{i}$
$\displaystyle\leq\sum_{i=1}^{n}\alpha_{i}+\sum_{i=1}^{n}\sum_{j\neq
i}\beta_{i,j}\cdot(\ln({v}_{i}(\mathbf{{s}}))-\ln({v}_{j}(\mathbf{{s}}_{-i},0_{i})))$
$\displaystyle=\underbrace{\sum_{i=1}^{n}\alpha_{i}}_{A}+\underbrace{\sum_{i=1}^{n}\sum_{j\neq
i}\beta_{i,j}\cdot(\ln({v}_{i}(\mathbf{{s}}))-\ln({v}_{i}(\mathbf{{s}}_{-j},0_{j})))}_{B}.$

Next, using Lemma 2.1, we know that $\sum_{j\neq
i}(1-{v}_{i}(\mathbf{{s}}_{-j},0_{j})/{v}_{i}(\mathbf{{s}}))\leq 1$. Thus, we
want to choose $\gamma_{i,j}$ appropriately to be able to bound the sum $B$:

$\forall i\neq
j,\qquad\gamma_{i,j}:=\begin{cases}\frac{1-{v}_{i}(\mathbf{{s}}_{-j},0_{j})/{v}_{i}(\mathbf{{s}})}{\ln({v}_{i}(\mathbf{{s}}))-\ln({v}_{i}(\mathbf{{s}}_{-j},0_{j}))}&\text{if
}{v}_{i}(\mathbf{{s}}_{-j},0_{j})<{v}_{i}(\mathbf{{s}})\\\ 1&\text{if
}{v}_{i}(\mathbf{{s}}_{-j},0_{j})={v}_{i}(\mathbf{{s}})\end{cases}.$

Using the fact that $-x\ln x\leq 1-x$ for all $0<x<1$, we have the following
important property:

$\forall i\neq
j,\qquad{v}_{i}(\mathbf{{s}}_{-j},0_{j})/{v}_{i}(\mathbf{{s}})\leq\gamma_{i,j}\leq
1.$

We set $\alpha_{i}:=1-\sum_{j\neq i}\beta_{i,j}$. By construction, the
inequality $\alpha_{i}+\sum_{j\neq i}\beta_{i,j}\geq 1$ is satisfied.
Moreover, we have that each $\beta_{i,j}$ is smaller than $1/n$, therefore
each $\alpha_{i}$ is at least $1/n$ and the inequalities
$\alpha_{i}\geq\beta_{i,j}$ are also satisfied.

To conclude the proof, it remains to give an upper bound on $A$ and $B$.

$\displaystyle A$ $\displaystyle=\sum_{i=1}^{n}\Big{(}1-\sum_{j\neq
i}\beta_{i,j}\Big{)}=1+\sum_{i=1}^{n}\sum_{j\neq
i}\Big{(}\frac{1}{n}-\beta_{i,j}\Big{)}$ $\displaystyle({\DMedit{\text{using
}\alpha_{i}=1-\sum_{j\neq i}\beta_{i,j}}})$
$\displaystyle=1+\frac{1}{n}\sum_{i=1}^{n}\sum_{j\neq
i}\Big{(}1-\gamma_{i,j}\cdot\gamma_{j,i}\Big{)}$
$\displaystyle({\DMedit{\text{using
}\beta_{i,j}=\gamma_{i,j}\cdot\gamma_{j,i}/n}})$ $\displaystyle\leq
1+\frac{1}{n}\sum_{i=1}^{n}\sum_{j\neq
i}\Big{(}(1-\gamma_{i,j})+(1-\gamma_{j,i})\Big{)}$
$\displaystyle(\text{because $\gamma_{i,j}+\gamma_{j,i}\leq
1+\gamma_{i,j}\cdot\gamma_{j,i}$})$ $\displaystyle\leq
1+\frac{2}{n}\sum_{i=1}^{n}\sum_{j\neq
i}(1-{v}_{i}(\mathbf{{s}}_{-j},0_{j})/{v}_{i}(\mathbf{{s}})).$
$\displaystyle(\text{because
${v}_{i}(\mathbf{{s}}_{-j},0_{j})/{v}_{i}(\mathbf{{s}})\leq\gamma_{i,j}$})$
$\displaystyle B$ $\displaystyle=\sum_{i=1}^{n}\sum_{j\neq
i}\frac{\gamma_{i,j}\cdot\gamma_{j,i}}{n}\cdot(\ln({v}_{i}(\mathbf{{s}}))-\ln({v}_{i}(\mathbf{{s}}_{-j},0_{j})))$
$\displaystyle{\DMedit{(\text{using
}\beta_{i,j}=\gamma_{i,j}\cdot\gamma_{j,i}/n)}}$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\sum_{j\neq
i}\gamma_{i,j}\cdot(\ln({v}_{i}(\mathbf{{s}}))-\ln({v}_{i}(\mathbf{{s}}_{-j},0_{j})))$
(using that $\gamma_{j,i}\leq 1$)
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\sum_{j\neq
i}(1-{v}_{i}(\mathbf{{s}}_{-j},0_{j})/{v}_{i}(\mathbf{{s}})).$ (replacing
$\gamma_{i,j}$ with its expression)

Overall, by adding together $A$ and $B$ we obtained that

$\sum_{i=1}^{n}y_{i}\leq 1+\frac{3}{n}\sum_{i=1}^{n}\sum_{j\neq
i}(1-{v}_{i}(\mathbf{{s}}_{-j},0_{j})/{v}_{i}(\mathbf{{s}})).$

Using Lemma 2.1, this last expression is upper-bounded by $4$. Recalling that,
by Lemma 3.1, $y_{i}$ is the pre-normalized share, and that $x_{i}$ is set to
$y_{i}/4$, this implies that $\sum_{i=1}^{n}x_{i}\leq 1$, proving feasibility.
∎

##  4 Optimal Mechanism for Matroid Feasibility Constraints and $d$-Critical
Valuations

In this section, we devise a mechanism for $d$-critical valuations within
settings where the feasible sets of bidders to be served form a matroid. We
show that our mechanism obtains a $(d+1)$-approximation to the optimal welfare
truthfully. This bound is optimal even for single-item settings. The main
result of this section follows.

######  Theorem 4.1.

For every setting with bidders with $d$-critical valuations, where the
feasible sets of bidders form a matroid, Mechanism 2 is an EPIC-IR mechanism
that gives a $(d+1)$-approximation to the social welfare.

Our mechanism first finds a set of potential candidates $\mathcal{C}$,
comprising the only bidders eligible for allocation. To determine whether
bidder $i$ is a candidate, the following process takes place (for each bidder
$i$ separately): the mechanism considers bidder $i$’s real value alongside the
low estimates of all other bidders $j\neq i$. Bidders are sorted in non-
increasing order of these values (breaking ties in favor of low index), and
are added greedily to a set $I_{i}$ provided an independent set is maintained.
Bidder $i$ belongs to the set of candidates $\mathcal{C}$ if $i$ belongs to
$I_{i}$.

We first show that every bidder that belongs to the optimal solution (i.e.,
the welfare-maximizing solution based on the real values) also belongs to
$\mathcal{C}$. Therefore, to establish a $(d+1)$-approximation, it suffices to
show that every bidder in $\mathcal{C}$ is served with probability $1/(d+1)$.
The set $\mathcal{C}$, however, need not be an independent set in the matroid.
We then show that the condition of Theorem 2.2 holds when restricting
attention to the bidders in $\mathcal{C}$, for $t=d+1$, and thus $\mathcal{C}$
can be partitioned into at most $d+1$ independent sets. It follows that, by
choosing each one of these $\leq d+1$ independent sets with probability
$1/(d+1)$, every bidder in $\mathcal{C}$, and thus also every bidder in the
optimal solution, is served with probability $1/(1+d)$, yielding the desired
approximation guarantee (which is tight according to Proposition 2.2).

Function $\texttt{greedy}(\text{weight function
}w:[n]\rightarrow\mathbb{R}_{+}):$

  1. 1.

Initialize $I=\emptyset$.

  2. 2.

Sort bidders $i$ by decreasing weights $w(i)$, and let $\sigma$ be the
resulting ordering, breaking ties in favor of lower-index bidders.

  3. 3.

Go over bidders according to ordering $\sigma$, for a current bidder $j$, add
$j$ to $I$ if $I\cup\\{j\\}\in\mathcal{I}$.

  4. 4.

Return the set $I$.

Mechanism CP:

  1. 1.

Elicit signals $\mathbf{\hat{s}}$ and valuation functions $\hat{v}$.
Initialize the set of candidates $\mathcal{C}=\emptyset$.

  2. 2.

For each bidder $i$:

Define the function $w_{i}$ where $w_{i}(i)=\hat{v}_{i}(\mathbf{\hat{s}})$ and
$w_{i}(j)=\hat{v}_{j}(\mathbf{\hat{s}}_{-i},0_{i})$ for $j\neq i$.

Define $I_{i}\leftarrow\texttt{greedy}(w_{i})$, then add $i$ to $\mathcal{C}$
if $i\in I_{i}$.

* 3.

Find a partitioning of $\mathcal{C}$ using at most $d+1$ independent sets
$\mathcal{I}_{\mathcal{C}}$ (which exists by Lemma 4.3). 4. Serve each set
$I\in\mathcal{I}_{\mathcal{C}}$ with probability $1/(d+1)$. 5. Charge payments
using Eq (3).

Mechanism 2 Candidate Partitioning (CP) Mechanism.

Towards proving Theorem 4.1, we first show that the mechanism is truthful.

######  Lemma 4.1.

Mechanism 2 is EPIC-IR.

###### Proof.

By Proposition 2.1, it suffices to show that the allocation depends only on
$\mathbf{\hat{s}}_{-i}$, $\mathbf{\hat{v}}_{-i}$, and
$\hat{v}_{i}(\mathbf{\hat{s}})$, and is monotone non-decreasing in
$\hat{v}_{i}(\mathbf{\hat{s}})$. We first observe that if $i$ is a candidate,
then $i$ is allocated with probability $1/(d+1)$, regardless of the
composition of $\mathcal{C}$. To determine whether $i$ is a candidate, we
consider $w_{i}(i)$’s relative position compared to every other $w_{i}(j)$,
where these values depend only on $\mathbf{\hat{s}}_{-i}$,
$\mathbf{\hat{v}}_{-i}$, and $\hat{v}_{i}(\mathbf{\hat{s}})$. An increase in
$\hat{v}_{i}(\mathbf{\hat{s}})$ boosts $w_{i}(i)$ without affecting all other
$w_{i}(j)$ values. Thus, by Lemma 2.2, if $i$ is added to $I_{i}$ for some
$\hat{v}_{i}(\mathbf{\hat{s}})$, it is also added when
$\hat{v}_{i}(\mathbf{\hat{s}})$ is increased, establishing monotonicity. This
implies the EPIC-IR property of the mechanism. ∎

Since the mechanism is EPIC-IR, hereafter, we use $\mathbf{{v}}$ and
$\mathbf{{s}}$ instead of $\mathbf{\hat{v}}$ and $\mathbf{\hat{s}}$.

Let $\sigma$ be the ordering of the bidders according to their actual values
$v_{i}(\mathbf{{s}})$, with ties broken in favor of lower-index bidders. Let
$I^{\star}$ be the independent set returned by the greedy algorithm described
above, iterating over bidders in the order of $\sigma$ (and adding bidder $i$
into $I^{\star}$ if $I^{\star}\cup{i}\in\mathcal{I}$). By Theorem 2.1,
$I^{\star}$ is a welfare-maximizing feasible set of bidders, i.e., $\sum_{i\in
I^{\star}}v_{i}(\mathbf{{s}})=\max_{I\in\mathcal{I}}\sum_{i\in
I}v_{i}(\mathbf{{s}})$.

The following lemma shows that all bidders in $I^{\star}$ will be candidates.

######  Lemma 4.2.

Let $I^{\star}$ be the welfare-maximizing set computed by the greedy algorithm
(iterating over bidders according to the order $\sigma$). It holds that
$I^{\star}\subseteq\mathcal{C}$.

###### Proof.

Consider a bidder $i\in I^{\star}$. Consider the weight functions
$w(j)=v_{j}(\mathbf{{s}})$ for all $j$, and $\hat{w}=w_{i}$ as defined in
Mechanism 2. Notice that $w(i)=v_{i}(\mathbf{{s}})=\hat{w}(i)$ and that
$w(j)=v_{j}(\mathbf{{s}})\geq{v}_{j}(\mathbf{{s}}_{-i},0_{i})=\hat{w}(j)$ for
all $j\neq i$. Notice also that $I^{\star}$ and $I_{i}$ are the independent
sets resulting from the greedy algorithm using weight functions $w$ and
$\hat{w}$, respectively, breaking ties in favor of lower-index bidders.
Therefore, by Lemma 2.2, $i\in I_{i}$, which implies that $i\in\mathcal{C}$. ∎

We next show that there exists a partitioning of $\mathcal{C}$ into at most
$d+1$ independent sets.

######  Lemma 4.3.

There exists a set of $k\leq d+1$ disjoint independent sets
$\mathcal{I}_{\mathcal{C}}=\\{I_{1},\ldots,I_{k}\\}$ such that
$I_{1}\uplus\dots\uplus I_{k}=\mathcal{C}$.

###### Proof.

We show that Eq. (6) holds for $\mathcal{C}$ with $t=d+1$, namely, that
$|S|\leq(d+1)\cdot rank(S)$ for every $S\subseteq\mathcal{C}$. We first show
that Eq. (6) holds for $S=\mathcal{C}$. Since $I^{\star}\subseteq\mathcal{C}$
(by Lemma 4.2), $rank(\mathcal{C})=rank(M)=|I^{\star}|$. Thus, to show that
Eq. (6) holds, it suffices to show that
$|\mathcal{C}|\leq(d+1)\cdot|I^{\star}|.$ For $i\notin I^{\star}$ to be a
candidate, there must be at least one $j\in I^{\star}$ such that
${v}_{j}(\mathbf{{s}}_{-j},0_{j})<v_{j}(\mathbf{{s}})$. Otherwise, by Lemma
2.2, all bidders in $I^{\star}$ will be added to $I_{i}$ when iterating over
the bidders in order $\sigma_{i}$, and since $rank(I^{\star})=rank(M)$, bidder
$i$ would not be selected.

For $i\in I^{\star}$, let $D_{i}$ be the set of bidders for which
${v}_{j}(\mathbf{{s}}_{-j},0_{j})<v_{j}(\mathbf{{s}})$. Since $v_{i}$ is
$d$-critical, $|D_{i}|\leq d$. By the above argument, $\mathcal{C}\setminus
I^{\star}\subseteq\cup_{i\in I^{\star}}D_{i}$. Therefore,

$|\mathcal{C}|=|\mathcal{C}\setminus I^{\star}|+|I^{\star}|\leq|\cup_{i\in
I^{\star}}D_{i}|+|I^{\star}|\leq
d\cdot|I^{\star}|+|I^{\star}|=(d+1)\cdot|I^{\star}|,$

where the second inequality follows from the union bound. Therefore, Eq. (6)
holds for the set $\mathcal{C}$.

Now consider a set of candidates $S\subseteq\mathcal{C}$. Since the rank
function is submodular with marginal contribution at most 1,

$rank(\mathcal{C})-rank(S)\leq|\mathcal{C}|-|S|.$

Therefore,

$\frac{|S|}{rank(S)}\leq\frac{|S|+(|\mathcal{C}|-|S|)}{rank(S)+(rank(\mathcal{C})-rank(S))}=\frac{|\mathcal{C}|}{rank(\mathcal{C})}\leq
d+1,$

satisfying Eq. (6). It follows by Theorem 2.2 that one can find a partition of
$\mathcal{C}$ into at most $d+1$ independent sets, as desired. ∎

We are now ready to prove the main theorem of this section.

###### Proof of Theorem 4.1.

By Lemma 4.1, the mechanism is EPIC-IR. By Lemma 4.3, the mechanism is well-
defined, and always outputs a feasible set of bidders. It remains to show that
the mechanism gives a $(d+1)$-approximation. Consider the welfare-maximizing
set of bidders, $I^{\star}$, which is the output of the greedy algorithm when
iterating over the bidders according to their real values. By Lemma 4.2,
$I^{\star}\subseteq\mathcal{C}$. Let $\mathcal{I}_{\mathcal{C}}$ be a set of
$k\leq d+1$ independent sets forming a partition of $\mathcal{C}$ (which
exists by Lemma 4.3). For every $i\in I^{\star}$, let
$\mathcal{I}_{\mathcal{C}}(i)$ denote the set in $\mathcal{I}_{\mathcal{C}}$
containing $i$. We have that the expected welfare is

$\displaystyle\sum_{i=1}^{n}v_{i}(\mathbf{{s}})\cdot\Pr[i\mbox{ is
allocated}]$ $\displaystyle\geq$ $\displaystyle\sum_{i\in
I^{\star}}v_{i}(\mathbf{{s}})\cdot\Pr[i\mbox{ is allocated}]$ $\displaystyle=$
$\displaystyle\sum_{i\in
I^{\star}}v_{i}(\mathbf{{s}})\cdot\Pr[\mathcal{I}_{\mathcal{C}}(i)\mbox{ is
served}]$ $\displaystyle=$ $\displaystyle\frac{1}{d+1}\sum_{i\in
I^{\star}}v_{i}(\mathbf{{s}})$ $\displaystyle=$
$\displaystyle\frac{OPT}{d+1},$

as desired. This concludes the proof of the theorem. ∎

Remark. We note that the 2 Mechanism can be applied to non-monotone critical
valuations, by changing the definition of $i$’s low estimate for $j$’s value
to be $\inf_{o_{i}\in S_{i}}v_{j}(o_{i},\mathbf{{s}}_{-i})$.

###  4.1 Bidders with Heterogeneous and Unknown $d$

Similarly to Eden et al. [14, 15], we can extend the results to the case where
each bidder $i$’s valuation is $d_{i}$-critical with a different $d_{i}$ and
$d_{i}$ is private information. We adjust the mechanism as follows.

In addition to answering value queries, each bidder $i$ also reports
$\hat{d}_{i}$. For every $i$, we compute $\bar{d}^{i}=\max_{j\neq
i}\hat{d}_{j}$. Note that $(i)$ $\bar{d}^{i}$ only depends on the reports of
bidders $j\neq i$; and $(ii)$ assuming bidders bid truthfully, all bidders
face the same $\bar{d}$, except (potentially) one bidder — the bidder $i$ with
the maximum overall $d_{i}$ value, call this bidder $\tilde{i}$. We then find
an allocation rule such that if a bidder $i\neq\tilde{i}$ becomes a candidate,
they are served with probability $1/2(\bar{d}+1)$, and if $\tilde{i}$ is a
candidate, $\tilde{i}$ is served with probability
$1/2(\bar{d}^{\tilde{i}}+1)$. This ensures truthfulness as the probability a
bidder is served depends on the reports of other bidders, and is monotone in
$\hat{v}(\hat{\mathbf{{s}}})$ (since by Lemma 2.2, being a candidate is
monotone in $\hat{v}(\hat{\mathbf{{s}}})$).

It remains to present an allocation rule that satisfies the above conditions.
This is done as follows. We flip a fair coin. If it turns head, then if
$\tilde{i}$ is a candidate, we serve $\tilde{i}$ with probability
$\frac{1}{\bar{d}^{\tilde{i}}+1}$. If it turns tails, then if
$\tilde{i}\in\mathcal{C}$, we remove $\tilde{i}$ from $\mathcal{C}$. Since all
bidders are $\bar{d}$-critical, we can apply the same argument as in Lemma
4.3, and partition $\mathcal{C}$ into at most $\bar{d}+1$ independent sets,
choosing each one with probability $\frac{1}{\bar{d}+1}$. To show that this
mechanism gives $2(\bar{d}+1)$-approximation, note that by Lemma 4.2, every
bidder in $I^{\star}$ is a candidate, and is served with probability at least
$1/2(\bar{d}+1)$.

## References

  * Amer and Talgam-Cohen [2021] Ameer Amer and Inbal Talgam-Cohen.  Auctions with Interdependence and SOS: Improved Approximation.  In _14th International Symposium on Algorithmic Game Theory (SAGT)_ , 2021.
  * Ausubel et al. [1999] Lawrence M Ausubel et al.  A generalized vickrey auction.  _Econometrica_ , 1999.
  * Babaioff et al. [2018] Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg.  Matroid secretary problems.  _J. ACM_ , 65(6):35:1–35:26, 2018.  doi: 10.1145/3212512.  URL https://doi.org/10.1145/3212512.
  * Birmpas et al. [2023] Georgios Birmpas, Tomer Ezra, Stefano Leonardi, and Matteo Russo.  Fair division with interdependent values.  _CoRR_ , abs/2305.14096, 2023.  doi: 10.48550/ARXIV.2305.14096.  URL https://doi.org/10.48550/arXiv.2305.14096.
  * Chawla et al. [2014] Shuchi Chawla, Hu Fu, and Anna Karlin.  Approximate revenue maximization in interdependent value settings.  In _15th ACM Conference on Economics and Computation (EC)_ , 2014\.
  * Che et al. [2015] Yeon-Koo Che, Jinwoo Kim, and Fuhito Kojima.  Efficient assignment with interdependent values.  _Journal of Economic Theory_ , 158:54–86, 2015.
  * Chen et al. [2022] Yiling Chen, Alon Eden, and Juntao Wang.  Cursed yet Satisfied Agents.  In _13th Innovations in Theoretical Computer Science Conference (ITCS 2022)_ , 2022.
  * Chung and Ely [2002] Kim-Sau Chung and Jeffrey C Ely.  Ex-post incentive compatible mechanism design.  2002\.  http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.8204&rep=rep1&type=pdf.
  * Cohen et al. [2023] Avi Cohen, Michal Feldman, Divyarthi Mohan, and Inbal Talgam-Cohen.  Interdependent public projects.  In _34th ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , 2023\.
  * Dasgupta and Maskin [2000] Partha Dasgupta and Eric Maskin.  Efficient auctions.  _The Quarterly Journal of Economics_ , 2000.
  * Eden et al. [2018] Alon Eden, Michal Feldman, Amos Fiat, and Kira Goldner.  Interdependent values without single-crossing.  In _19th ACM Conference on Economics and Computation (EC)_ , 2018\.
  * Eden et al. [2019] Alon Eden, Michal Feldman, Amos Fiat, Kira Goldner, and Anna R. Karlin.  Combinatorial auctions with interdependent valuations: Sos to the rescue.  In _20th ACM Conference on Economics and Computation (EC)_ , 2019\.
  * Eden et al. [2021] Alon Eden, Michal Feldman, Inbal Talgam-Cohen, and Ori Zviran.  Poa of simple auctions with interdependent values.  In _35th AAAI Conference on Artificial Intelligence (AAAI)_ , 2021\.
  * Eden et al. [2022] Alon Eden, Kira Goldner, and Shuran Zheng.  Private interdependent valuations.  In _33rd ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , 2022\.
  * Eden et al. [2023] Alon Eden, Michal Feldman, Kira Goldner, Simon Mauras, and Divyarthi Mohan.  Constant approximation for private interdependent valuations.  In _64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023_ , pages 148–163. IEEE, 2023.  doi: 10.1109/FOCS57990.2023.00018.  URL https://doi.org/10.1109/FOCS57990.2023.00018.
  * Edmonds [1965] Jack Edmonds.  Minimum partition of a matroid into independent subsets.  _J. Res. Nat. Bur. Standards Sect. B_ , 69:67–72, 1965\.
  * Edmonds [1971] Jack Edmonds.  Matroids and the greedy algorithm.  _Math. Program._ , 1(1):127–136, 1971.  doi: 10.1007/BF01584082.  URL https://doi.org/10.1007/BF01584082.
  * for the Prize in Economic Sciences in Memory of Alfred Nobel [2020] The Committee for the Prize in Economic Sciences in Memory of Alfred Nobel.  Scientifc background on the sveriges riksbank prize in economic sciences, 2020.  URL https://www.nobelprize.org/uploads/2020/09/advanced-economicsciencesprize2020.pdf.
  * Gkatzelis et al. [2021] Vasilis Gkatzelis, Rishi Patel, Emmanouil Pountourakis, and Daniel Schoepflin.  Prior-free clock auctions for bidders with interdependent values.  In _14th International Symposium on Algorithmic Game Theory (SAGT)_ , 2021.
  * Ito and Parkes [2006] Takayuki Ito and David C. Parkes.  Instantiating the contingent bids model of truthful interdependent value auctions.  In _Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems_ , page 1151–1158, 2006.
  * Jehiel and Moldovanu [2001] Philippe Jehiel and Benny Moldovanu.  Efficient design with interdependent valuations.  _Econometrica_ , 2001.
  * Klemperer [1998] Paul Klemperer.  Auctions with almost common values: The ’wallet game’ and its applications.  _European Economic Review_ , 42(3-5):757–769, 1998.  URL https://EconPapers.repec.org/RePEc:eee:eecrev:v:42:y:1998:i:3-5:p:757-769.
  * Li [2013] Yunan Li.  Approximation in mechanism design with interdependent values.  In _Proceedings of the fourteenth ACM Conference on Electronic Commerce, EC 2013, Philadelphia, PA, USA, June 16-20, 2013_ , pages 675–676. ACM, 2013.  doi: 10.1145/2492002.2482580.  URL https://doi.org/10.1145/2492002.2482580.
  * Lu et al. [2022] Pinyan Lu, Enze Sun, and Chenghan Zhou.  Better approximation for interdependent SOS valuations.  In _18th International Conference on Web and Internet Economics (WINE)_ , 2022.
  * Maskin [1992] Eric Maskin.  Auctions and privatization.  _Privatization, H. Siebert, ed. (Institut fur Weltwirtschaften der Universität Kiel: 1992)_ , 1992.
  * Milgrom and Weber [1982] Paul R Milgrom and Robert J Weber.  A theory of auctions and competitive bidding.  _Econometrica_ , 1982.
  * Myerson [1981] Roger B Myerson.  Optimal auction design.  _Mathematics of operations research_ , 6(1):58–73, 1981.
  * Oxley [2011] James Oxley.  _Matroid Theory (2nd ed.)_.  Oxford Univerity Press, 2011.
  * Robu et al. [2013] Valentin Robu, David C. Parkes, Takayuki Ito, and Nicholas R. Jennings.  Efficient interdependent value combinatorial auctions with single minded bidders.  In _IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence_ , pages 339–345, 2013.
  * Roughgarden and Talgam-Cohen [2016] Tim Roughgarden and Inbal Talgam-Cohen.  Optimal and robust mechanism design with interdependent values.  _ACM Trans. Econ. Comput._ , 2016.
  * Wilson [1969] Robert B Wilson.  Communications to the editor—competitive bidding with disparate information.  _Management science_ , 1969.