# Matrix Product State Pre-Training for Quantum Machine Learning

James Dborin  _London Centre for Nanotechnology, University College London,
London, United Kingdom_ Fergus Barratt  _London Centre for Nanotechnology,
University College London, London, United Kingdom_ _Department of Mathematics,
King’s College London, London, United Kingdom_ Vinul Wimalaweera  _London
Centre for Nanotechnology, University College London, London, United Kingdom_
Lewis Wright  _Department of Mathematics, King’s College London, London,
United Kingdom_ Andrew G. Green  _London Centre for Nanotechnology, University
College London, London, United Kingdom_

###### Abstract

Hybrid Quantum-Classical algorithms are a promising candidate for developing
uses for NISQ devices. In particular, Parametrised Quantum Circuits (PQCs)
paired with classical optimizers have been used as a basis for quantum
chemistry and quantum optimization problems. Training PQCs relies on methods
to overcome the fact that the gradients of PQCs vanish exponentially in the
size of the circuits used. Tensor network methods are being increasingly used
as a classical machine learning tool, as well as a tool for studying quantum
systems. We introduce a circuit pre-training method based on matrix product
state machine learning methods, and demonstrate that it accelerates training
of PQCs for both supervised learning, energy minimization, and combinatorial
optimization.

##  1 Introduction

Parametrised Quantum Circuits (PQCs) have been the focus of attempts to
demonstrate quantum computational advantage on NISQ devices, for problems of
both scientific and commercial interest. Typically these efforts involve
parametrising a quantum circuit with a series of rotation angles, and using a
classical optimizer to find a set of angles which minimizes a given cost
function. The quantum device is used to estimate the cost function associated
with a particular set of parameters, where it is assumed to be hard to
calculate the cost function classically. Algorithms based on these methods are
often called hybrid quantum-classical algorithms.

A major hurdle in developing useful hybrid algorithms is the problem of
vanishing gradients. It has been shown that the size of initial gradients
decrease exponentially towards zero as the number of qubits and the depth of
the circuits increases, when parameters are randomly initialised [1]. Other
circuit metrics have been demonstrated to produce these so-called barren
plateaus, such as ansatz expressibility [2], the entanglement between hidden
and visible nodes in the circuit [3, 4], and circuit noise [5].

The existence of the barren plateau has motivated attempts to improve PQC
learning algorithms to avoid training costs growing exponentially. These
include developing gradient free algorithms [6, 7], defining local cost
functions as targets for learning algorithms [8], and initialisation schemes
[9].

Here we introduce a novel initialisation scheme based on tensor network
algorithms. Tensor network based methods are the state of the art for
numerical simulations of 1D and 2D spin systems [10], and also for the
simulation of quantum circuits [11]. Tensor networks have been used to solve
optimization problems such as portofolio optimization, and are found to be
competitive with commercial solvers [12, 13]. Recently, tensor network based
methods have also been used as the basis for machine learning algorithms.
Matrix Product States (MPS) have been trained as a classifier for several
machine learning tasks [14, 15]. The 2D generalisation of MPS, Projected
Entangled Pair States (PEPS), have also been used for image
classification[16]. Both Tree Tensor Networks (TTN) and MERA networks have
also been used as image classifiers [17, 18].

Figure 1: Outline of the MPS initialisation procedure. a) _Classical Training
-_ A MPS is optimized as an approximate solution to a given problem instance,
by variationally minimizing a cost function over the tensors, $A_{i}$.
Classical data points, $x_{i}$, are lifted into a higher dimensional Hilbert
space by way of a mapping $\phi(x_{i})=(\cos(x_{i}),\sin(x_{i}))$. b)
_Canonicalise -_ The minimized MPS is put into canonical form, where the
tensors are isometries from the space of incoming arrows to the space of out
going arrows. Any MPS can be put in this form, due to a gauge freedom in the
MPS[19]. c) _Embed and Compile -_ The isometric tensors are exactly embedded
into unitary matrices. This can be further decomposed approximately using
gates available on the quantum device. d) _Quantum Training -_ The compiled
unitaries are placed in a circuit along the diagonals, and the other gates in
the circuit are initialised to the identity. This ensures that this circuit is
as good an approximation to the optimal solution as the MPS is after the
compilation process. The optimizer is then able to vary all the parameters,
including those in the gates initialised to the identity.

In this work, we optimize tensor networks as candidate ground states, as
classifiers, and as solutions to combinatorial optimization problems. We use
these networks to seed a PQC with an effective set of starting parameters,
before continuing to train the quantum circuit. By beginning training in a
part of the parameter space that is close to the target state, the number of
steps to reach the desired minima can be reduced. In this way the impact of
the barren plateau is reduced and limited quantum resources can be used more
effectively during training. From here onwards this procedure will be known as
_MPS Pretraining_.

##  2 MPS Pretraining

MPS pretraining involves three steps:

  * 1.

Train a tensor network

  * 2.

Compile the tensor network into gates

  * 3.

Initialise a circuit with these gates

Fig. 1 outlines this procedure.

###  2.1 MPS Optimization

Given a problem instance, such as a Hamiltonian or a labeled data set, and a
cost function where the minimum corresponds to the state of interest, the
first step is to produce a MPS that minimizes the given cost function. The
bond dimension of a MPS, denoted $\chi$, is a parameter that determines the
complexity of the MPS model. Higher bond dimension models tend to produce
better results, at the cost of greater training complexity. This training is
done purely classically, and software exists both to efficiently contract and
optimize these states, for example we refer the reader to Refs. [20, 11, 21,
22]. In the following we discuss MPS algorithms, but the insights apply to
other tensor network architectures.

There are a variety of algorithms that can be used to optimize MPS. To find
the ground states of Hamiltonians the DMRG algorithm is known to be very
effective [23]. Similar optimisation algorithms include imaginary-time TEBD
and TDVP, both of which are used in this work [24, 25]. In Ref. [14] a DMRG-
inspired machine learning algorithm is introduced which we adapt for this
work. Note that in principle gradient descent can always be performed directly
on all the tensors in the tensor network. This more closely reflects classical
machine learning algorithms. However these quantum-inspired learning
algorithms tend to perform as well in practice, and often perform better for
quantum-based problems such as energy minimisation.

###  2.2 MPS Compilation

Having trained a MPS to minimize a cost function, the next step is to
represent the MPS as a set of rotation angles in a PQC. As opposed to other
classical machine learning methods, low bond dimension tensor networks permit
efficient representations on quantum circuits [26]. MPS have a gauge freedom
which means that any MPS can be brought into _canonical form_ in which each
tensor is an isometry [19]. These can then easily be embedded in unitary
matrices. Bond dimension 2 MPS can be expressed as a staircase of 2 qubit
unitary gates [26]. The rotation angles are extracted from these unitaries
with some compilation scheme. For 2 qubit unitaries we use the KAK
Decomposition [27], which decomposes 2 qubit unitaries into 4 single qubit
gates with 3 rotation angles each, and 3 different 2-qubit interaction gates.
If necessary these gates can be further decomposed into hardware efficient
gates. Restricted gate sets can be used as compilation targets, and the
rotation angles can be found variationally [28]. Later we suggest an
approximate compilation scheme, based on insights from Ref. [29], which
ensures that the largest unitary matrices that need to be compiled are 2-qubit
gates.

Often brick wall circuits are used as ans atze for PQC research, being the
most general way to parametrise a quantum circuit limited to nearest neighbour
interactions. To initialise a brick wall circuit with a pretrained MPS, the
gates on the diagonal of the brick wall must be initialised with the angles
extracted in the compilation of the MPS. All of the off-diagonal gates are
initialised to the identity. This ensures that before quantum training begins,
the circuit represents exactly as good a candidate for the target state as the
MPS is after compilation is completed. The optimizer is then free to vary the
angles of all of the gates. We demonstrate that starting with this
initialisation accelerates training, requires fewer gradient updates, and
avoids local minima.

##  3 Results

###  3.1 Combinatorial Optimization

We test the initialisation scheme on the Max Cut optimisation problem which is
often used as a benchmark for QAOA algorithms [30]. In the Max Cut problem a
graph, $G(E,V)$, is provided along with weights, $w_{ij}$, on each edge. The
task is to find a set of vertices, $S$, such that the total weight of the
edges connecting $S$ to their complement is maximized. This is equivalent to
finding the ground state of the Hamiltonian,

$H=\sum_{\langle i,j\rangle}w_{ij}(1-Z_{i}Z_{j})$ (1)

where $Z$ is the Pauli Z matrix.

We use imaginary time TEBD to find a bond dimension 2 approximation to the
ground state for an instance of the Max Cut problem on a graph with 6
vertices. In Fig. 2 we show the results of training with this initialisation
for depth 6, 9, and 12 circuits. Optimization was performed for an imaginary
time of $3\times 10^{-2}$, with a time step of $1\times 10^{-3}$. We only
optimize the MPS for short periods of time because for small problem instances
low bond dimension MPS can often get close to the optimal answer. To more
closely match the performance on large problem instances which require quantum
circuits that cannot be easily simulated we do not fully optimize the MPS.

Figure 2: Max Cut optimization a) _Max Cut Graph -_ The 6 node max cut problem
graph with the edge weights. The Max Cut Hamiltonian is given as
$H=\sum_{\langle i,j\rangle}w_{ij}(1-Z_{i}Z_{j})$, where $w_{ij}$ is the
weight along the edge connecting node $i$ to node $j$. Each node is encoded as
a qubit. b)_Quantum Circuit Ansatz -_ For all circuits the diagonal unitaries
were expressed fully using the KAK decomposition[27], whereas off diagonal
unitary matrices were made with combinations of Y rotations and controlled X
rotations. Circuits were optimized using gradient descent with decaying
learning rate. c) _MPS Pretraining results -_ Compared to randomly initialised
circuits, of depth 6, 9, and 12, the circuits initialised with MPS-compiled
angles converge with fewer gradient steps, and converge to a better ground
state estimate than than the randomly initialised counterparts. In the MPS
initialised circuits there is almost no change in performance as depth
increases, whereas increasing depth with randomly initialised parameters slows
down optimization.

We compare training starting from MPS pretrained circuits to that starting
from random initialisations of the same ansatz. Instead of the standard QAOA
scheme, we use a brick wall circuit made up of independent 2-qubit gates.
These sorts of circuits have been explored for optimisation problems and their
performance is competitive with QAOA [31].

The MPS initialised circuits start off at a better energy than the random
counterparts, which is to be expected. However the initial steps from the MPS
initialised states are noticeably larger than those taken from randomly
initialised circuits. These circuits reach a minimum with fewer gradient
descent updates, and reach better minima than the any of the randomly
initialised states. In the random state there is a notable decrease in
performance between the depth 9 and depth 12 ansatz, where the depth 12 gets
stuck in a local minimum. No drop in performance is observed in the MPS
initialised circuits.

###  3.2 Finding Ground States

We also implement MPS pretraining for the purpose of finding ground states of
electronic Hamiltonians, a common benchmark in hybrid quantum classical
algorithm research. We use imaginary time TDVP to estimate the ground state of
the electronic Hamiltonian of $H_{2}$ and $LiH$. The Hamiltonians are
constructed using the OpenFermion package [32]. The same is done for the
Transverse Field Ising Model (TFIM) which is a widely studied Hamiltonian in
condensed matter physics.

In all these cases imaginary time TDVP was used to construct a MPS
approximation to the ground state, and this MPS is used to initialise a
quantum circuit. For the $H_{2}$ and $LiH$ problems, the MPS converges to the
same ground state as the optimized quantum circuit, suggesting either low bond
dimension MPS are good approximations to these ground states, or the brick
wall circuits do not offer significantly more expressivity in this problem. To
demonstrate that even in cases where low bond dimension MPS are not as
effective, we run the TDVP algorithm for a shorter time, meaning a worse
approximation is used to initialise the circuits. These results are given in
Fig. 3.

In all three cases we find significant decreases in the number of iterations
needed to reach the lowest energy states, compared to the randomly initialised
circuits. We also compared circuits initialised to the identity, with all
rotation angles set to 0. In each case the zero initialised circuit failed to
optimized, and quickly ended up in a local minima.

Fig. 3b compares the performance of the MPS pretrained circuit with a randomly
initialised circuit in finding the ground state of the $H_{2}$ electronic
Hamiltonian. Optimisation of the MPS initialised circuit required fewer
function evaluations than the randomly initialised circuits, while both found
effectively the same ground state, differing by less that $1\times 10^{-8}$ at
depth 10. The number of function evaluations needed for the MPS initialised
circuit grows more slowly as a function of depth than for the randomly
initialised circuit, implying that even relatively poor approximations of the
ground state still initialise close to the target state. We see similar
results for the LiH and TFIM Hamiltonians, Fig. 3c and d resprectively.

Figure 3: Initialising VQE with MPS a) _Quantum Circuit Ansatz -_ The
structure of the circuits used for these experiments. Shown is a depth 6
circuit on 4 qubits. Each unitary, $U$, is decomposed into 15 rotation angles
using the KAK Decomposition. The single qubit gates are made up of three
independent rotations, Z followed by Y followed by Z. All the angles in the
circuit are independent. All optimization was performed using the BFGS
algorithm. b) _$H_{2}$ Optimisation -_ For all depths the circuits produced a
good estimate for the ground state energy, $E-E_{min}<1\times 10^{-8}$. The
MPS initialised circuits required thousands of fewer function evaluations at
each depth, and the number of iterations is growing more slowly with depth
than for the randomly initialised circuits. c) _LiH Optimisation -_ For the
depth tested approximately half as many function evaluations are required to
optimize the cost function when using MPS initialisation. The initial
gradients are larger in the MPS case, and the optimization begins closer to
the minima. d) _TFIM Optimisation -_ At all depths tested the MPS
initialisation converged after fewer iterations, and to lower ground state
energies.

###  3.3 Machine Learning

Finally we pretrain quantum circuits to classify clothing labels using the
Fashion MNIST dataset. The images were compressed so small circuits could be
used to classify each image. This compression is done using principle
component analysis on the training data set, and projecting the training
images onto the principle components. The set of training images is collected
into a matrix, $\bf{X}$. We compute the covariance matrix of the training
dataset, given by

$\bf{\Sigma}=\bf{X}^{T}\bf{X}$ (2)

Then we perform an SVD on the matrix $\bf{\Sigma}$

$\bf{\Sigma}=\bf{U}\bf{\Lambda}\bf{U^{\dagger}}$ (3)

The principle components are identified as the columns of $\bf{U}$. To
compress an image so that an $N$ qubit circuit can be used to classify the
image we take the $N$ top principle components,
$\\{\vec{u}_{1},\vec{u}_{2},\cdots,\vec{u}_{N}\\}$, and take the inner product
between each image (reshaped into a vector) and the principle component. The
input to the $i^{th}$ qubit from the $j^{th}$ image in the training set is
given by

$\tilde{x}_{i,j}=\langle\vec{x}_{j},\vec{u}_{i}\rangle$ (4)

Each projection was used as the input to a single qubit, so to use $N$ qubits,
we projected an image onto the $N$ most significant principle components. The
individual $\tilde{x}_{i}$ values are used as rotation angles in parametrised
Y gates, Fig. 4a. This method, as opposed to other compression methods, such
as pooling, gives greater flexibility in the number of qubits that can be
used. The circuits used here were trained as binary classifiers. They were
trained to distinguish between t-shirts and trousers. In Fig. 4b we show the
training set loss and accuracy at each epoch during training.

The MPS pretrained circuit is compared to both a random initialisation and an
initialisation such that the circuit evaluates to the identity matrix. Ref.
[9] suggests the identity initialisation increases the size of initial
gradients and is commonly used in quantum chemistry research. In this case all
angles were set to zero, as all gates used were parameterised rotations. For
an ansatz with static gates, more care must be taken so that the entire
circuit evaluates to the identity.

The MPS initialised circuit has a lower loss and higher accuracy on the
training set during training than either the identity initialisation or the
random initialisation.

Figure 4: Fashion MNIST Results. a) _Quantum Circuit Ansatz -_ The circuit
used in these classification experiments. U and W are defined in the same way
as in Fig. 2a. The classifier ansatz is given by a brick wall circuit, and the
data is introduced using Y rotations, parametrised by angles
$\vec{\tilde{x}}$. A single component of this vector, $\tilde{x}_{i}$, is
given by the projection of a single image onto the $i^{th}$ principle
component of the training dataset. A decision function is defined as the
probability of measuring the all-zero bit string. We use binary cross-entropy
loss defined on the training dataset, $\tilde{\bf{X}}$, as a target to
optimize the decision boundary. The circuit classifies the image with label 0
if $f(\vec{\tilde{x}})<0.5$ and 1 otherwise. Optimization is performed using
the _adam_ optimizer. b) _Results with MPS Initialisation -_ The loss and
binary accuracy on the training set during training is given as a function of
the number of epochs trained for. An epoch is defined as the number of batched
gradient updates required such that the entire training set has been processed
once. In each case the number of qubits is the same as the depth. The MPS was
trained for 5 epochs before being compiled to a quantum circuit and training
is continued. The MPS initialised circuits took no more than 2 epochs to
optimize, whereas the other initialisation schemes required 4 or more. As well
as starting at a higher binary accuracy, the binary accuracy of the MPS
initialised circuits also increased faster during early epochs, indicating
that the local loss landscape of the MPS initialised circuits may be more easy
to optimize over.

##  4 Compilation

For situations where bond dimension 2 MPS ansatz are not able to optimize a
cost function, higher bond dimensions need to be used to capture a wider range
of quantum states. Higher bond dimension MPS tensors are compiled to unitaries
over more than 2 qubits, each doubling of the bond dimension requires another
qubit in the representation of each tensor. This raises the problem of
compiling high bond dimension MPS.

An approximate compilation scheme has been proposed which has been
demonstrated to effectively represent states of physical interest in tensor
network simulations [29]. Many-qubit unitary matrices are decomposed into a
reverse stair-case of nearest neighbour unitary matrices, Fig. 5a. When
compiling an MPS into a circuit in this way, the diagonals adjacent to the
central diagonal in a brick wall circuit are also initialised, and not set to
the identity, Fig. 5b. Training higher bond dimension MPS can then be viewed
as a way to initialise more of the initial brick wall circuit. This
compilation process is not exact, and hence errors will accumulate throughout
this process and worsen the initialisation of the circuit.

a)

b)

Figure 5: Approximate high bond dimension compilation. a) The approximate
decomposition of a 4-qubit unitary into a reverse stair case with 3 2-qubit
unitaries. b) Using this decomposition is equivalent to initialising the
diagonals adjacent to the main diagonal in a brick wall circuit. The circuit
shown is a bond dimension 4 MPS which is decomposed into 2 diagonals in a
brick wall circuit. Doubling the bond dimension adds another diagonal layer to
the compilation.

##  5 Discussion

###  5.1 Comparison to other methods

Below we compare conceptually similar ideas which have been proposed to
overcome barren plateaus and accelerate the training of variational quantum
circuits. This is not an exhaustive list but highlighting these examples helps
highlight the benefits of MPS pre-training.

####  5.1.1 Warm-Start QAOA

The MPS initialisation method introduced here is one of many proposed methods
to improve the training of PQCs. This solution is very similar in methodology
to the warm-start QAOA algorithm [33]. Relaxations are applied to the
optimization problem which make the problem efficiently solvable, and this is
used to initialise the QAOA algorithm. The relative merits of these two
methods ultimately depends on the relative effectiveness of relaxation methods
and MPS based methods to approximate the optimal solution for optimization
problems. There is currently no way to concretely answer this question, but
there have been results demonstrating that tensor network based methods are
competitive with state of the art commercial solvers for optimization problems
[12, 13].

####  5.1.2 Layer-Wise Learning

Another procedure that has shown promising results is layer wise learning[34,
31]. Layers in a quantum circuit are trained one at a time, keeping all other
layers fixed. Finally layers are grouped together and trained simultaneously
before training the entire circuit. The reasoning behind this method is very
similar to that proposed here, to initialise the entire circuit with an
approximation to the optimal solution, but instead of using MPS, the
approximation is generated by sequential optimisation of layers in a PQC. Once
again the question remains as to whether the layer wise trained approximation
is better than MPS based approximations. Consider the fact that depth 1 or 2
nearest neighbour circuits, which are often considered in layer wise training
regimes, can be faithfully represented with a bond dimension 2 MPS, and in
fact this set of states is a restriction on the set of states that can be
represented with a bond dimension 2 MPS. Layer wise training could be
reformulated as sequential training of finite correlation length MPS, with the
bond dimension of the restricted MPS growing with each trained layer. Seeing
as the MPS initialisation scheme that we have introduced requires no
restriction on the set of accessible states it should be the case that better
initialisation states are accessible with the methods introduced here. It has
been demonstrated that layer-wise learning suffers from abrupt transitions in
trainability [35]; there exist circuit ansatz and cost functions where, below
a threshold depth, piece wise training fails to minimize the cost function.

It has not escaped our attention that insights from tensor network
optimisation techniques could be used to augment this initialisation method
with a training scheme similar to layer wise learning. In the DMRG algorithm,
the bond dimension of the MPS is gradually increased. A similar approach with
brick wall circuits would involve sequentially training diagonals either side
of the central diagonal. It remains to be seen if this training scheme could
be as effective as layer wise learning in training a circuit combined with MPS
pretraining.

####  5.1.3 Entanglement Restriction

The authors of [4] note that the impacts of vanishing gradients can be
mitigated by restricting entanglement between hidden and visible qubits in a
PQC. A qubit is visible if the output of that qubit is used to calculate a
cost function, and it is hidden if it is ignored. They propose a number of
schemes, including starting with no entanglement between hidden and visible
nodes, having a fixed entanglement, and learning circuits which have low
entanglement. The quantum circuit MPS formalism used in this work can easily
be extended to the regime with hidden and visible qubits. In this case our
initialisation scheme would resemble a fixed entanglement initialisation
scheme, where the entanglement between the hidden and visible nodes is fixed
by the bond dimension of the tensor network. They additionally propose
including additional terms to the cost function, one to restrict entanglement
growth between hidden and visible nodes, and one to add Langevin noise which
acts to mitigate the effect of vanishing gradients. Both these schemes could
be implementing on top of the initialisation scheme proposed here.

###  5.2 Alternative Tensor Network Structures

There are many tensor network geometries that are used to represent states
with properties that are not effectively captured by MPS. Many of these have
circuit counterparts which could be initialised in the same way. For example
MERA networks [36] have been proposed as a basis for quantum machine learning

MPS have a freedom in the location of the _othogonality centre_ when put in
canonical form. In all results above, the MPS are put into left or right
canonical form. The circuits to represent these states have a depth at least
as large as the number of qubits. However choosing a _mixed canonical_ form
actually reduces the circuit depth needed to initialise the MPS, Fig. 6. A
circuit initialised in this way may have larger initial gradients, as
gradients vanish as a function of circuit depth.

Figure 6: Gauge freedom and circuit depth. The decomposition of a centre-gauge
MPS into a quantum circuit. This circuit has a lower depth than left or right
canonical MPS, used throughout this work. This may additionally mitigate the
effect of vanishing gradients. Tensors are isometries from the space of
incoming arrows to the space of outgoing arrows. For bond dimension 2 there
exist low depth circuits that can exactly represent the central tensor, $C$
[26]. For higher bond dimension MPS the central tensor would need to be
approximately compiled.

###  5.3 Consequences for tensor network simulations

It is interesting to note that the bond dimension of the MPS needed to
represent the circuit increases as training proceeds. Deep brick wall circuits
represent a restricted class of high bond dimension tensor networks.
Ordinarily any variational calculations with these extremely large bond
dimension tensor networks would be impractical on quantum devices because of
the difficulty in optimizing these circuits. To simulate spin systems with
high bond dimension tensor networks it would be possible to simulate up to the
classically feasible limit, translate the tensor network into circuits, and
then seed a higher bond dimension simulation with the classical tensor network
as is done here. This could open up the possibility of very large bond
dimension tensor network simulations of spin systems on NISQ devices.

##  6 Acknowledgements And Contributions

JD, FB, and AGG were supported by the EPSRC through grants EP/L015242/1,
EP/L015854/1 and EP/S005021/1. This work is supported by the Engineering and
Physical Sciences Research Council grant number EP/L015242/1. VM is supported
by ESPRC Prosperity Partnership grant EP/S516090/1. LW and FB are supported by
the EPSRC CDT in Cross-Disciplinary Approaches to Non-Equilibrium Systems
(CANES) via grant number EP/L015854/1. The project was conceived in group
discussions. JD and FB wrote code to translate MPS into circuits, and to
continue training. VM wrote classical MPS training methods inspired by DMRG.
The manuscript was written by JD and FB.

## References

  * [1] J. McClean et al. “Barren plateaus in quantum neural network training landscapes” In _Nature Communications_ 9, 2018
  * [2] Zoe Holmes, Kunal Sharma, M. Cerezo and Patrick J. Coles “Connecting ansatz expressibility to gradient magnitudes and barren plateaus”, 2021
  * [3] C. Marrero, Mária Kieferová and N. Wiebe “Entanglement Induced Barren Plateaus” In _ArXiv_ abs/2010.15968, 2020
  * [4] Taylor L Patti, Khadijeh Najafi, Xun Gao and Susanne F Yelin “Entanglement devised barren plateau mitigation” In _arXiv preprint arXiv:2012.12658_ , 2020
  * [5] Samson Wang et al. “Noise-induced barren plateaus in variational quantum algorithms” In _arXiv preprint arXiv:2007.14384_ , 2020
  * [6] Mateusz Ostaszewski, Edward Grant and Marcello Benedetti “Quantum circuit structure learning” In _arXiv preprint arXiv:1905.09692_ , 2019
  * [7] B’alint Koczor and S. Benjamin “Quantum Analytic Descent” In _arXiv: Quantum Physics_ , 2020
  * [8] M. Cerezo et al. “Cost-Function-Dependent Barren Plateaus in Shallow Quantum Neural Networks” In _ArXiv_ abs/2001.00550, 2020
  * [9] E. Grant, L. Wossnig, M. Ostaszewski and Marcello Benedetti “An initialization strategy for addressing barren plateaus in parametrized quantum circuits” In _arXiv: Quantum Physics_ 3, 2019, pp. 214
  * [10] R. Orus “A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States” In _Annals of Physics_ 349, 2014, pp. 117–158
  * [11] C. Roberts et al. “TensorNetwork: A Library for Physics and Machine Learning” In _ArXiv_ abs/1905.01330, 2019
  * [12] Samuel Mugel et al. “Dynamic Portfolio Optimization with Real Datasets Using Quantum Processors and Quantum-Inspired Tensor Networks” In _ArXiv_ abs/2007.00017, 2020
  * [13] J. Alcazar and A. Perdomo-Ortiz “Enhancing Combinatorial Optimization with Quantum Generative Models”, 2021
  * [14] E.. Stoudenmire and D. Schwab “Supervised Learning with Quantum-Inspired Tensor Networks” In _ArXiv_ abs/1605.05775, 2016
  * [15] T. Bradley, E.. Stoudenmire and John Terilla “Modeling Sequences with Quantum States: A Look Under the Hood” In _ArXiv_ abs/1910.07425, 2019
  * [16] Song Cheng, Lei Wang and Pan Zhang “Supervised Learning with Projected Entangled Pair States” In _ArXiv_ abs/2009.09932, 2020
  * [17] William J. Huggins, Piyush Patel, K. Whaley and E.. Stoudenmire “Towards Quantum Machine Learning with Tensor Networks” In _ArXiv_ abs/1803.11537, 2018
  * [18] E. Grant et al. “Hierarchical quantum classifiers” In _npj Quantum Information_ 4, 2018, pp. 1–8
  * [19] David Perez-Garcia, Frank Verstraete, Michael M Wolf and J Ignacio Cirac “Matrix product state representations” In _arXiv preprint quant-ph/0608197_ , 2006
  * [20] Matthew Fishman, Steven R. White and E. Stoudenmire “The ITensor Software Library for Tensor Network Calculations”, 2020 arXiv:2007.14822
  * [21] Johannes Hauschild and Frank Pollmann “Efficient numerical simulations with Tensor Networks: Tensor Network Python (TeNPy)” Code available from https://github.com/tenpy/tenpy In _SciPost Phys. Lect. Notes_ SciPost, 2018, pp. 5 DOI: 10.21468/SciPostPhysLectNotes.5
  * [22] Johnnie Gray “quimb: a python library for quantum information and many-body calculations” In _Journal of Open Source Software_ 3.29, 2018, pp. 819 DOI: 10.21105/joss.00819
  * [23] U. Schollwoeck “The density-matrix renormalization group in the age of matrix product states” In _Annals of Physics_ 326, 2011, pp. 96–192
  * [24] J. Haegeman et al. “Time-dependent variational principle for quantum lattices.” In _Physical review letters_ 107 7, 2011, pp. 070601
  * [25] S. Paeckel et al. “Time-evolution methods for matrix-product states.” In _arXiv: Strongly Correlated Electrons_ , 2019
  * [26] Fergus Barratt et al. “Parallel Quantum Simulation of Large Systems on Small Quantum Computers” In _arXiv: Quantum Physics_ , 2020
  * [27] Robert R. Tucci “An Introduction to Cartan’s KAK Decomposition for QC Programmers” In _arXiv: Quantum Physics_ , 2005
  * [28] Kunal Sharma, S. Khatri, M. Cerezo and Patrick J. Coles “Noise resilience of variational quantum compiling” In _New Journal of Physics_ 22, 2020, pp. 043006
  * [29] Sheng-Hsuan Lin et al. “Real- and imaginary-time evolution with compressed quantum circuits” In _arXiv: Quantum Physics_ , 2020
  * [30] Edward Farhi, Jeffrey Goldstone and Sam Gutmann “A quantum approximate optimization algorithm” In _arXiv preprint arXiv:1411.4028_ , 2014
  * [31] X. Liu et al. “Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers”, 2021
  * [32] Jarrod R McClean et al. “OpenFermion: the electronic structure package for quantum computers” In _Quantum Science and Technology_ 5.3 IOP Publishing, 2020, pp. 034014
  * [33] D.. Egger, Jakub Mareček and Stefan Woerner “Warm-starting quantum optimization” In _arXiv: Quantum Physics_ , 2020
  * [34] A. Skolik et al. “Layerwise learning for quantum neural networks” In _ArXiv_ abs/2006.14904, 2020
  * [35] Ernesto Campos, Aly Nasrallah and Jacob Biamonte “Abrupt transitions in variational quantum circuit training” In _Physical Review A_ 103.3 APS, 2021, pp. 032607
  * [36] Glen Evenbly and Guifré Vidal “Tensor network states and geometry” In _Journal of Statistical Physics_ 145.4 Springer, 2011, pp. 891–918


# A Report on the Euphemisms Detection Shared Task

Patrick Lee  Anna Feldman  Jing Peng
Montclair State University
New Jersey, USA
<EMAIL_ADDRESS>

###### Abstract

This paper presents The Shared Task on Euphemism Detection for the Third
Workshop on Figurative Language Processing (FigLang 2022) held in conjunction
with EMNLP 2022. Participants were invited to investigate the euphemism
detection task: given input text, identify whether it contains a euphemism.
The input data is a corpus of sentences containing potentially euphemistic
terms (PETs) collected from the GloWbE corpus Davies and Fuchs (2015), and are
human-annotated as containing either a euphemistic or literal usage of a PET.
In this paper, we present the results and analyze the common themes, methods
and findings of the participating teams.

##  1 Introduction

Euphemisms are mild or indirect expressions that are used in place of other
ones when discussing potentially offensive or sensitive topics. Their
linguistic functions include (politeness, concealment, and neutralization of
unappealing words/phrases). Despite being an important element of language
use, their figurative nature poses a challenge for natural language processing
(NLP).

There are numerous challenges to working with euphemisms. One is the
phenomenon of the “euphemism treadmill”, by which words/phrases gain or lose
euphemistic meanings over time Pinker (2003). Another is that researchers may
not agree on what euphemisms are. For example, Zhu and Bhat (2021); Zhu et al.
(2021) treat code words as euphemisms, but our working definition does not.
Even when restricted to our working definition, however, annotators were found
to sometimes disagree in the task of labeling example sentences as euphemistic
Gavidia et al. (2022). For all these reasons, the words/phrases in this shared
task are referred to as potentially euphemistic terms (PETs). The main
challenge, which is the focus of this shared task, is the ambiguity of PETs:
the same words/phrases that may be euphemistic in one context may be literal
in another. For example,

_Asked to choose between jobs and the environment, a majority – at least in
our warped, first-past-the-post system – will pick jobs._ (non-euphemistic)

_This summer, the budding talent agent was between jobs and free to babysit
pretty much any time._ (euphemistic)

We propose the Shared Task on Euphemism Detection: given input text, identify
whether it contains a euphemism; i.e., distinguish between euphemistic and
literal usages of the same PETs in different contexts. The data used is a
corpus of texts containing PETs, collected by Gavidia et al. (2022), which
contains parallel euphemistic and literal examples for a range of PETs. 46
participants spanning 13 teams attempted the task, and we received 9 system
descriptions.

Due to a lack of extensive research in this area, it is unclear how NLP
techniques, such as language models (LMs), will perform on euphemism
detection. The purpose of this shared task is to (1) explore the ability of
NLP techniques for this task and (2) investigate what methods could further
improve upon their performance.

##  2 Related Work

There is not much work on automatic detection of euphemisms. The most directly
related work is by Magu and Luo (2018), Felt and Riloff (2020), Kapron-King
and Xu (2021), Zhu et al. (2021) and Zhu and Bhat (2021). Felt and Riloff
(2020) present the first effort to recognize euphemisms and dysphemisms
(derogatory terms) using NLP. The authors use the term _x-phemisms_ to refer
to both. They first identify three sensitive topics (lying, stealing, and
firing). They use a weakly supervised algorithm for semantic lexicon induction
Thelen and Riloff (2002) to generate lists of near-synonym phrases for each
topic semi-automatically. Felt and Riloff (2020) experiment with two methods
to classify phrases as euphemistic, dysphemistic, and neutral: 1) dictionary-
based method addressing affect, connotation, intensity, arousal, and
dominance; 2) contextual sentiment analysis to classify x-phemisms. The
important product of this work is a gold-standard dataset of human x-phemism
judgements. The important lesson here is that Felt and Riloff (2020) show that
sentiment connotation and affective polarity are useful for identifying
x-phemisms, but not sufficient. While the performance of Felt and Riloff
(2020)’s system is relatively low and the range of topics is very narrow, this
work certainly inspires further investigations.

Zhu et al. (2021) define two tasks: 1) euphemism detection (based on the input
keywords, produce a list of candidate euphemisms) 2) euphemism identification
(take the list of candidate euphemisms produced in (1) and output an
interpretation). Zhu et al. (2021) select sentences matched by a list of
keywords, create masked sentences (mask the keywords in the sentences) and
apply the masked language model proposed in BERT Devlin et al. (2018) to
filter out generic (uninformative) sentences and then generate expressions to
fill in the blank. These expressions are ranked by relevance to the target
topic.

Euphemisms are also related to the language of politeness (e.g., Danescu-
Niculescu-Mizil et al. (2013); Rababah (2014)), which plays a role in
applications involving dialogue and social interactions in different contexts.

Other shared tasks have proposed a similar classification task on other types
of figurative language. Ghosh et al. (2020) report on a sarcasm detection task
run on conversation data from Twitter and Reddit, while Madabushi et al.
(2022) report on an idiom detection and embedding task.

##  3 Task Setting

Participants were given a dataset of PET-containing texts created by Gavidia
et al. (2022). In this section, we describe the dataset and the classification
task.

###  3.1 Dataset Description

The corpus of PETs was formed by taking a list of PETs (single and multi-word
expressions, collected from a variety of sources) and extracting texts from
the GloWBe corpus Davies and Fuchs (2015) (only the US-English portion) which
contained them. Each text sample comprised up to 3 sentences: the sentence
that the PET appeared in, as well as the preceding and following sentences, if
available. In total, the dataset contains 1,965 text samples spanning 129
different PETs and 7 topics/categories. Of these, 1,382 were annotated to
contain a euphemistic usage of a PET, and the remaining 583 a literal usage.
Thus, the dataset is imbalanced (an aspect which multiple teams explicitly
considered in their approaches). The full details of the data, including the
distribution amongst the PETs and topics, can be found in the original paper
Gavidia et al. (2022).

The training and test sets were created using an 80-20 split. The range of
PETs which appeared in each split was balanced as much as possible, given that
several PETs only appeared once as a euphemistic or literal example. Details
of the split are summarized in Table 1.

Split |  Rows | Euphemistic | Literal
---|---|---|---
|  |  Rows |  PETs |  Rows |  PETs
Train |  1572 |  1106 |  122 |  466 |  54
Test |  393 |  276 |  121 |  117 |  55
Table 1: Train-Test Split Details

A simplified version of the dataset was created for the participants, where
each row contained only (1) the text sample with the PET denoted in brackets,
and (2) its label (a ’1’ for euphemistic, and a ‘0’ for literal). This version
omitted information about each row, such as meta-information about the PET:
the specific morphological variant present in the row, the topic category
(e.g., "death", "politics", etc.), and whether it always appeared in the
dataset as a euphemism (“always-euphs”) or only sometimes (“sometimes-euphs”).
This information, however, was available to the participants via a Github link
to the full dataset (which several teams chose to leverage).

###  3.2 Task Description

The shared task was set up as a competition on
Codalab111https://codalab.lisn.upsaclay.fr/competitions/5726. Participants
were invited to develop systems trained on the training data (see Table 2 for
some examples) and submit answer labels on the test set, which would be
compared to the labels in the original dataset for evaluation. The evaluation
metric used to rank submissions was the macro-F1 score.

Text | Label
---|---
More likely it’ll harm them. With less products to make, Foxxcom will have to <lay off> workers. With more workers seeking jobs those other factories will be able to resist demands for higher wages. | 1
We do NOT need some self-imposed book cop telling us what to read or not to read. <Lay off>. Get over it. | 0
After about 30 minutes of waiting, a fight broke out between an older African American man and an African American woman of <a certain age>. After making a lot of noise and landing a few blows to their respective bodies, the armed security guards escorted them out of the terminal. | 1
Table 2: Example Rows from the Dataset

##  4 Participants and Results

8 teams that participated in the task also submitted descriptions of their
systems, with one author additionally exploring a zero-shot/few-shot variant
of the task. A summary of their performances is shown in Table 3. In this
section, we describe the methods used by the best-performing teams, and
analyze the common themes between the approaches and motivations of all the
submissions.

Rank | Username | Macro-F1 |  Title of Paper
---|---|---|---
1 | vgangal | 0.88 |  EUREKA: Euphemism Recognition Enhanced Through KNN-based Methods and Augmentation Keh et al. (2022)
2 | ilker | 0.87 |  Detecting Euphemisms with Literal Descriptions and Visual Imagery Kesen et al. (2022)
3 | Wanderer | 0.85 |  A Prompt Based Approach for Euphemism Detection Maimaitituoheti (2022)
4 | liuyiyi | 0.84 |  Euphemism Detection by Transformers and Relational Graph Attention Network Wang et al. (2022)
5 | peratham.bkk | 0.82 |  TEDB System Description to a Shared Task on Euphemism Detection 2022 Wiriyathammabhum (2022)
6 | PaulTrust | 0.79 |  Bayes at FigLang 2022 Euphemism Detection shared task: Cost-Sensitive Bayesian Fine-tuning and Venn-Abers […] Trust and Kadusa (2022)
7 | devika | 0.74 |  An Exploration of Linguistically-Driven and Transfer Learning Methods for Euphemism Detection Tiwari and Parde (2022)
8 | gunetsk99 | 0.72 |  Adversarial Perturbations Augmented Language Models for Euphemism Identification Kohli et al. (2022)
Table 3: Results of submitted systems to the Shared Task on Euphemism
Detection

###  4.1 Best Submissions

The best-performing team Keh et al. (2022) (macro-F1 0.881) explores a variety
of data and modeling modifications, and combine the best-performing ones into
an ensemble of three models to improve upon a baseline RoBERTa-large model Liu
et al. (2019). On the data side, they explore two methods of data
augmentation, and find that adding examples containing similar/opposite word
senses to PETs (for positive and negative examples) works best; this
highlights the potential significance of sense-based approaches for this task.
They also explore identifying and correcting 25 potentially mislabeled rows
from the dataset, reporting an improvement of 0.0036 points over the base
model and a final score $\sim$0.007 higher when using their “cleaned” dataset.
While it is unclear how this cleaning would affect other systems in general,
their investigation hints at the potential for not only human disagreement but
also human error in labeling figurative language. On the modeling side, they
find that classifying on the tokens of the PETs, rather than the [CLS] token,
yields significant a performance increase. They also experiment with two
methods of incorporating extra context and find that k-Nearest Neighbor (kNN)
(5NN in this case) augmentation yields slight improvements. They report the
best improvement by combining the following three models: (1) a RoBERTa-large
model classifying on the PET token(s), (2) the same, but using their sense-
augmented dataset, and (3) the same as (1), but interpolating the
classification probabilities of its base model and the 5NN classifier.

The second-best performing team Kesen et al. (2022) achieved a macro-F1 of
0.872 using additional supervision and, interestingly, incorporating visual
imagery into their approach. Using DeBERTa-v3 He et al. (2021) as their
baseline (the “large” version of which performs best), they incorporate
additional supervision by including PETs themselves, as well as their
(manually collected) literal descriptions, in their inputs. The authors found
this to greatly improve performance, reasoning that such direct supervision
could help mitigate ambiguity inherent to the task. This is a similar result
to Keh et al. (2022), where extra attention on the PETs themselves is
effective. They then obtain imageries of both the PETs and their literal
descriptions using a text-to-image model, and obtain image embeddings using a
pretrained visual encoder. These are incorporated into training, and yields
statistically significant performance improvements. Qualitative analysis of
the images for each PET reveals insights into how LMs might understand
figurative expressions.

###  4.2 Analysis of Methods

Below, we describe approaches that we observed in multiple submissions. Since
the objective was to explore different aspects of this task, we find these
insights to be valuable, even if they did not score high.

####  4.2.1 Using PET Embeddings Directly

Multiple teams found that explicitly involving the tokens of the PET for
classification led to significant improvement. Kesen et al. (2022) and Wang et
al. (2022) include the PET in their inputs by concatenating it to each input
text prior to learning. Keh et al. (2022) run their final classification on
the PET embedding, rather than that of the [CLS] token. These changes were a
significant feature of these teams’ best approaches. It appears that providing
direct supervision/focusing the modeling procedure on the PET helps, perhaps
because the PET is the semantic focus of the task (rather than other words in
the data, which are not always important).

####  4.2.2 Using the Literal Meanings of PETs

Each PET is detailed in Gavidia et al. (2022) to have a literal meaning or
paraphrase, which is the more offensive or unpleasant “real meaning” that the
PET substitutes. Several teams chose to integrate literal meanings of each
input PET into their methods, though they opted to generate their own literal
meanings, rather than use the ones from the original paper. This seemed to be
effective, as the two best-performing teams found it to improve performance —
Kesen et al. (2022) appended literal meanings to their inputs and used them to
generate image embeddings, while Keh et al. (2022) used literal meanings to
select examples for data augmentation — in conjunction with direct supervision
on the PET (4.2.1). Tiwari and Parde (2022) paraphrased PETs with their
literal meanings in attempt to obtain sentiment shifts, but this did not work
well for classification, likely because the paraphrasing mechanism did not
produce quality paraphrases that could serve as literal meanings for the PETs.

####  4.2.3 Addressing Data Imbalance/Inadequacy

Multiple teams addressed the fact that the dataset was imbalanced (see 1).
Maimaitituoheti (2022) found that their approach scored an F1 of 0.914 versus
0.789 on the euphemistic and literal examples, respectively, suggesting that
the model performance could indeed be skewed towards the higher-volume
euphemistic examples.

Trust and Kadusa (2022) experimented with multiple modeling enhancements, such
as Bayesian modeling, exclusively to address the imbalance issue and found
that they improved performance. Kohli et al. (2022) sought to address the
imbalance by using adversarial perturbations to augment the ‘0’ label, and
found it to increase performance slightly. As aforementioned, Keh et al.
(2022) augment the dataset by strategically selecting sentences from other
corpora (albeit for general augmentation, rather than to achieve a balance)
and similarly report slight performance increases, but, like Kohli et al.
(2022), they do not exclusively use the augmented data in their final
approach. These results generally support the intuition that addressing data
inadequacies helps models learn, but only partially for this shared task.

####  4.2.4 Incorporating Additional Context

While this task necessitates making use of contextual differences between
input texts, several teams attempted to incorporate additional information
from the context. Wang et al. (2022) model syntactic connections between the
PET and other words in the text as a relational graph, finding that using this
as an input to BERT is effective (though no baseline or example parse is
provided). As aforementioned in Section 4.1, Keh et al. (2022) slightly
improve performance by using the k-nearest neighbors for each input as
additional context. Kohli et al. (2022) finds that simply using longer input
sequence lengths than standard BERT allows for (512) generally improves
performance, although it is not clear at what sequence length this would cease
to be the case. All these methods to incorporate more input context seemed to
generally improve performance.

####  4.2.5 Linguistic Transparency

Some teams attempted solutions that would promote model explainability. Kesen
et al. (2022) claim that images of PETs and their literal meanings are a way
to gain insight into how models interpret PETs, but while this is an
interesting way to probe models’ current understanding of figurative
expressions, it is unclear how models might use these images to enhance
classification in an understandable way. The two-model ensemble used by Wang
et al. (2022) attempt to incorporate linguistic (semantic and syntactic)
information of the PET and its context, though without compelling examples of
how these may help classification, the improvements seem somewhat
unexplainable. Finally, Tiwari and Parde (2022) interestingly pursued an
approach that is based exclusively on the linguistic intuition that euphemisms
produce sentiment shifts, but using these shifts alone for this task was
ineffective.

On the other hand, methods which found success using transformers are not very
transparent. Wiriyathammabhum (2022) test various transformers and obtain
their best result by combining a CNN variant with the highest-performing one,
but it is not clear what this network is learning, as is typically the case
with neural networks. Furthermore, Keh (2022) find that transformers work
decently for this task in the zero-shot setting (see 4.2.6), but admit that
it’s not clear what BERT is learning in order to do so.

####  4.2.6 Zero/Few-shot Learning

Maimaitituoheti (2022) train a RoBERTa model using prompt-tuning because it
has been shown to work well (better than regular fine-tuning) with few-shot
examples. While our task was not formulated as a zero/few-shot task, several
PETs appeared only a few times in the data and were effectively few-shot
examples. Keh (2022) notably re-formulate the task for the zero/few-shot
setting. When PETs were randomly selected to be zero-shot examples, RoBERTa-
large achieved a score of 0.740, showing that the model was able to “learn”
something about euphemisms (not simply memorizing) and apply it to examples
with PETs unseen during training. They also show that few-shot examples
benefit the model greatly, with 3-shot performance (0.825) nearly matching the
baseline performance (0.836). Furthermore, they found that GPT3, which
typically works well in the zero/few-shot setting, worked badly for this task.

##  5 Discussion and Findings

Here, we describe some common findings of the submitted systems that may be
useful for future work.

###  5.1 More Data is Better

Having more examples of each PET generally led to better performance. Kesen et
al. (2022) and Keh et al. (2022) improved performance by augmenting the
dataset. Maimaitituoheti (2022) showed that performance on the euphemistic
label is better, likely because there were many more examples than the non-
euphemistic label. Compellingly, Keh (2022) showed in their zero/few-shot task
that 3-shot learning was much better than 1-shot. The results of this task
call for larger datasets of euphemisms, perhaps from a variety of different
sources.

###  5.2 BERT Works

All teams experimented with some variation of BERT and reported decent scores
using unmodified BERT models, the highest being 0.839 Kesen et al. (2022)
using RoBERTa-large. The zero-shot investigation by Keh (2022), too, shows
that RoBERTa picks up something during training that is generalizable to other
euphemisms. Overall, pre-trained transformers seem to provide a solid baseline
from which to launch euphemism work.

###  5.3 Linguistic Intuitions

Because euphemisms (as well as other types of figurative language) are often
commonly used expressions, it is likely that large language models have some
existing “knowledge” about these collocations. One could interpret the success
of using PET embeddings directly Kesen et al. (2022); Wang et al. (2022) as
evidence that models can leverage this knowledge for the task.

Another linguistic notion is that euphemisms’ function may lead to changes in
sentiment, which has been found to potentially be useful for identifying
euphemisms Felt and Riloff (2020); Lee et al. (2022), but it remains somewhat
unclear whether it is useful for the disambiguation proposed in this task.
Wiriyathammabhum (2022) do find that transformers pre-trained specifically on
sentiment were more helpful than those pre-trained on other tasks (e.g.,
sarcasm or hate speech detection). Tiwari and Parde (2022) try a non-
transformer-based approach based on the intuition that PETs should produce
higher sentiment shifts in euphemistic sentences when paraphrased with its
literal meaning, but found it was difficult to generate such paraphrases. This
corroborates our own past experimentation Lee et al. (2022), and it seems that
future approaches based on sentiment shifts have to address the need for
better paraphrasing mechanisms, or consider using them to supplement a larger
input feature set.

##  6 Conclusions and Future Work

We present the results of “The Shared Task on Euphemism Detection for the
Third Workshop on Figurative Language Processing” and summarize the various
systems submitted, as well as common findings. Overall, we find that results
are promising: even when dealing with the difficult issue of an especially
polite and indirect form of figurative language, current NLP techniques such
as transformers and augmentation seem to work quite well. Teams explored a
variety of intriguing methods to enhance the baseline performance of these
models, some of which were even linguistically transparent. If one considers
that labeling euphemisms is subject to human disagreement, the F1-scores
achieved by the teams are even more compelling since they may be near, if not
already at, the level of human agreement on the task. The results of this
shared task establish a baseline for future work on euphemisms and figurative
language in general.

Future work on this task could be expanding on the dataset to include more
examples and a wider range of PETs, testing further enhancements, and
improving performance by ensembling various combinations of the best-
performing improvements. Future work for euphemism detection in general could
be to expand from the disambiguation task; e.g. identifying where euphemisms
are in a text, providing interpretations of a euphemism, or even euphemistic
language generation.

## Limitations

While the data used denoted where the target PET was in each text sample, this
information is not provided in raw text. Identifying the PET in a text sample
is a challenge that future approaches, especially those seeking to focus
models on the PET, will need to consider. Additionally, this shared task was
run on a dataset that could be significantly expanded and balanced. The
dataset also contained potentially subjective labels that were only made by
two human annotators; this could be made more robust by ensembling more
annotators. Finally, this task was based on a dataset comprising only of texts
of US English, and it is unclear how these results would transfer cross-
lingually to other kinds of euphemisms.

## Ethics Statement

When we created the shared task, we tried to be compliant with the ACL Ethics
Policy. Euphemisms are expressions that ‘hide’ prejudices by using softened
language. Models capable of recognizing and interpreting euphemisms should be
better at detecting biases related to gender, age, race, or socioeconomic
background, detrimental to the society.

## Acknowledgements

This material is based upon work supported by the National Science Foundation
under Grants No. 1704113 and No. 2226006.

## References

  * Danescu-Niculescu-Mizil et al. (2013) Cristian Danescu-Niculescu-Mizil, Moritz Sudhof, Dan Jurafsky, Jure Leskovec, and Christopher Potts. 2013.  A computational approach to politeness with application to social factors.  _arXiv preprint arXiv:1306.6078_.
  * Davies and Fuchs (2015) Mark Davies and Robert Fuchs. 2015.  Expanding horizons in the study of world englishes with the 1.9 billion word global web-based english corpus (glowbe).  _English World-Wide_ , 36(1):1–28.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Felt and Riloff (2020) Christian Felt and Ellen Riloff. 2020.  Recognizing euphemisms and dysphemisms using sentiment analysis.  In _Proceedings of the Second Workshop on Figurative Language Processing_ , pages 136–145.
  * Gavidia et al. (2022) Martha Gavidia, Patrick Lee, Anna Feldman, and Jing Peng. 2022.  Cats are fuzzy pets: A corpus and analysis of potentially euphemistic terms.
  * Ghosh et al. (2020) Debanjan Ghosh, Avijit Vajpayee, and Smaranda Muresan. 2020.  A report on the 2020 sarcasm detection shared task.
  * He et al. (2021) Pengcheng He, Jianfeng Gao, and Weizhu Chen. 2021.  Debertav3: Improving deberta using electra-style pre-training with gradient-disentangled embedding sharing.  _arXiv preprint arXiv:2111.09543_.
  * Kapron-King and Xu (2021) Anna Kapron-King and Yang Xu. 2021.  A diachronic evaluation of gender asymmetry in euphemism.  _arXiv preprint arXiv:2106.02083_.
  * Keh (2022) Sedrick Scott Keh. 2022.  Exploring Euphemism Detection in Few-Shot and Zero-Shot Settings.  In _Proceedings of the 3rd Workshop on Figurative Language Processing_. Association for Computational Linguistics.
  * Keh et al. (2022) Sedrick Scott Keh, Rohit K. Bharadwaj, Emmy Liu, Simone Tedeschi, Varun Gangal, and Roberto Navigli. 2022.  EUREKA: EUphemism Recognition Enhanced through Knn-based methods and Augmentation.  In _Proceedings of the 3rd Workshop on Figurative Language Processing_. Association for Computational Linguistics.
  * Kesen et al. (2022) Ilker Kesen, Aykut Erdem, Erkut Erdem, and Iacer Calixto. 2022.  Detecting Euphemisms with Literal Descriptions and Visual Imagery.  In _Proceedings of the 3rd Workshop on Figurative Language Processing_. Association for Computational Linguistics.
  * Kohli et al. (2022) Guneet Kohli, Prabsimran Kaur, and Jatin Bedi. 2022.  Adversarial Perturbations Augmented Language Models for Euphemism Identification.  In _Proceedings of the 3rd Workshop on Figurative Language Processing_. Association for Computational Linguistics.
  * Lee et al. (2022) Patrick Lee, Martha Gavidia, Anna Feldman, and Jing Peng. 2022.  Searching for pets: Using distributional and sentiment-based methods to find potentially euphemistic terms.  _arXiv preprint arXiv:2205.10451_.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Madabushi et al. (2022) Harish Tayyar Madabushi, Edward Gow-Smith, Marcos Garcia, Carolina Scarton, Marco Idiart, and Aline Villavicencio. 2022.  Semeval-2022 task 2: Multilingual idiomaticity detection and sentence embedding.
  * Magu and Luo (2018) Rijul Magu and Jiebo Luo. 2018.  Determining code words in euphemistic hate speech using word embedding networks.  In _Proceedings of the 2nd workshop on abusive language online (ALW2)_ , pages 93–100.
  * Maimaitituoheti (2022) Abulimiti Maimaitituoheti. 2022.  A Prompt Based Approach for Euphemism Detection.  In _Proceedings of the 3rd Workshop on Figurative Language Processing_. Association for Computational Linguistics.
  * Pinker (2003) Steven Pinker. 2003.  _The Blank Slate: The modern denial of human nature_.  Penguin.
  * Rababah (2014) Hussein Abdo Rababah. 2014.  The translatability and use of x-phemism expressions (x-phemization): Euphemisms, dysphemisms and orthophemisms) in the medical discourse.  _Studies in literature and language_ , 9(3):229–240.
  * Thelen and Riloff (2002) Michael Thelen and Ellen Riloff. 2002.  A bootstrapping method for learning semantic lexicons using extraction pattern contexts.  In _Proceedings of the 2002 conference on empirical methods in natural language processing (EMNLP 2002)_ , pages 214–221.
  * Tiwari and Parde (2022) Devika Tiwari and Natalie Parde. 2022.  An Exploration of Linguistically-Driven and Transfer Learning Methods for Euphemism Detection.  In _Proceedings of the 3rd Workshop on Figurative Language Processing_. Association for Computational Linguistics.
  * Trust and Kadusa (2022) Paul Trust and Provia Kadusa. 2022.  Bayes at FigLang 2022 Euphemism Detection shared task: Cost-Sensitive Bayesian Fine-tuning and Venn-Abers Predictors for Robust Training under Class Skewed Distributions.  In _Proceedings of the 3rd Workshop on Figurative Language Processing_. Association for Computational Linguistics.
  * Wang et al. (2022) Yuting Wang, Yiyi Liu, Ruqing Zhang, Yixing Fan, and Jiafeng Guo. 2022.  Euphemism Detection by Transformers and Relational Graph Attention Network.  In _Proceedings of the 3rd Workshop on Figurative Language Processing_. Association for Computational Linguistics.
  * Wiriyathammabhum (2022) Peratham Wiriyathammabhum. 2022.  TEDB System Description to a Shared Task on Euphemism Detection 2022\.  In _Proceedings of the 3rd Workshop on Figurative Language Processing_. Association for Computational Linguistics.
  * Zhu and Bhat (2021) Wanzheng Zhu and Suma Bhat. 2021.  Euphemistic phrase detection by masked language model.
  * Zhu et al. (2021) Wanzheng Zhu, Hongyu Gong, Rohan Bansal, Zachary Weinberg, Nicolas Christin, Giulia Fanti, and Suma Bhat. 2021.  Self-supervised euphemism detection and identification for content moderation.  _arXiv preprint arXiv:2103.16808_.


# Optimal Multi-Dimensional Auctions: Conjectures and Simulations

Alexey Kushnir<EMAIL_ADDRESS>Tepper School of Business, Carnegie
Mellon University4765 Forbes AvePittsburghPennsylvaniaUSA15213 and  James
Michelson<EMAIL_ADDRESS>Department of Philosophy, Carnegie Mellon
University5000 Forbes AvePittsburghPennsylvaniaUSA15213

###### Abstract.

We explore the properties of optimal multi-dimensional auctions in a model
where a single object of multiple qualities is sold to several buyers. Using
simulations, we test some hypotheses conjectured by Belloni et al. (Belloni et
al., 2010) and Kushnir and Shourideh (Kushnir and Shourideh, 2022). As part of
this work, we provide the first open-source library for multi-dimensional
auction simulations written in Python.

optimal auctions, mechanism design, multiple-dimensional types, exclusion
region, exclusive buyer mechanism, open-source software

##  1\. Introduction

The mechanism design literature has a good understanding of revenue-maximizing
auctions in one-dimensional settings. In his seminal paper on optimal
auctions, Myerson (Myerson, 1981) analyzed the problem of selling a single
object to multiple-buyers whose values are one-dimensional and independently
distributed. He showed that the object should be optimally allocated to a
buyer with the highest “virtual value” whenever it is non-negative. The
virtual value is a function of buyer’s value that depends only on the buyer’s
type distribution. It also determines buyer’s reserve price and, hence, the
set of buyer’s types that do not receive the object, i.e., the exclusion
region.

The analysis of the revenue-maximizing multi-dimensional auctions has proved
to be much more difficult. Most papers in the literature focus on the problem
of a monopolist offering several objects to buyers when the cost function is
separable across buyers.111One of few papers that studies optimal mechanisms
for selling multiple objects to multiple buyers is by Armstrong (Armstrong,
2000). He showed that in a simple setting with a binary distribution of types
the analysis proves to be very difficult. The optimal auction takes one of two
formats: either objects are sold independently, or a degree of bundling is
introduced in the sense that the probability a bidder wins one object is
increasing in her value for the other. In this case, buyers can be dealt one-
by-one and the problem effectively becomes how to sell several objects to a
single buyer. Armstrong (Armstrong, 1996) showed that in almost any optimal
auction, it is optimal not to sell with positive probability. This property is
considered to be general in the literature. Rochet and Chone (Rochet and
Choné, 1998) and Manelli and Vincent (Manelli and Vincent, 2007) show that it
is applicable to a wide range of multi-dimensional settings (see also
(Daskalakis, 2015)). These papers also argue that optimal selling mechanism
are quite complex, often requiring randomly assigning objects to buyers.

The pioneering work Belloni et al. (Belloni et al., 2010) challenged the above
papers suggesting that the optimal multi-dimensional mechanisms with multiple
buyers might have quite different properties. They consider a model where a
single object of multiple quality grades is sold to multiple buyers who have
multi-dimensional types. Using simulations, they show that some optimal
mechanisms sell with probability one. Also, they show that the class of
“exclusive buyer mechanisms” performs quite well relative to the numerical
optimal mechanisms in their simulations. These mechanism are simple in the
sense that they do not not involve randomization and can be implemented via a
modified second-price auction (in dominant strategies). In this paper, we
revisit Belloni et al. (Belloni et al., 2010)’s results to verify several
broad messages from their work.

  1. 1.

The optimal auction revenue can be well approximated by the optimal exclusive
buyer mechanism.

  2. 2.

In some multi-buyer settings the measure of buyers’ types that receive no
object (the exclusion region) in the optimal auction has measure zero in
contrast to the corresponding single-buyer setting.

We show via simulations that there are environments where both statements do
not hold. These results lead us to propose a new conjecture that was first
suggested by Kushnir and Shourideh (Kushnir and Shourideh, 2022) in a
different setting where there are two objects need to be allocated to two
buyers (as in (Armstrong, 1996)).

  1. 3.

The exclusion region of the optimal allocation is independent of the number of
buyers.

Overall, our simulations allow us to explore interesting properties of multi-
dimensional optimal auctions in the case when an auctioneer wants to sell one
object of different quality grades to multiple buyers. To accomplish this we
develop an open-source software library written entirely in Python which
enables researchers to establish new general properties of optimal multi-
dimensional mechanisms.

The paper proceeds as follows. Section 2 introduces the model. We outline how
we approach the simulation results in Section 3. In Section 4, we formally
present our main conjectures. These conjectures are tested using several
settings in Section 5. Section 6 concludes.

##  2\. Model

We consider a setting similar to the one in Belloni (Belloni et al., 2010).
There is one object that needs to be allocated to $N$ buyers. The object can
be tailored to buyers’ needs with $j=1,...,J$ possible quality grades. With
slight abuse of notation, we denote $N=\\{1,...,N\\}$ and $J=\\{1,...,J\\}$.

Each buyer $i\in N$ has a multi-dimensional type
$v^{i}=(v^{i}_{1},...,v^{i}_{J})$ that determines the buyer’s willingness to
pay for the various quality grades of the object. We assume that buyer’s types
are distributed according to $F$ with support $V\equiv\Pi_{j\in
J}[\underline{v}_{j},\overline{v}_{j}]$. The valuations are independently
distributed across buyers, but the valuations for different quality grades
could be potentially correlated for each buyer. Also, $v^{-i}$ and
$F^{-i}(v^{-i})$ refer the vector of buyers’ valuations except buyer $i$ and
the distribution of buyers’ valuations except buyer $i$. We also assume that
buyer’s utility is linear. If we denote the probability that buyer $i$
receives the object of grade $j$ as $q^{i}_{j}$ and needs to pay $m_{i}$,
buyer $i$’s utility equals

$u^{i}=\sum^{J}_{j=1}v_{j}^{i}q_{j}^{i}-m^{i}.$

The costs of producing the object of quality $j$ is constant and denoted
$c_{j}$. When marginal costs are constant one could consider an equivalent
model with zero marginal costs by replacing $v_{j}-c_{j}$ with a shifted
distribution of $v_{j}$. We keep Belloni et al. (Belloni et al., 2010)’s
notation with non-zero marginal costs for easy comparison.

Using the direct revelation principle, we restrict our attention to direct
mechanisms with allocation $q=(q^{1},...,q^{N})$ and payment
$m=(m^{1},...,m^{N})$, where for each $i\in N$

$\displaystyle q^{i}:V^{N}\rightarrow\Delta(J),\hskip
14.22636ptm^{i}:V^{N}\rightarrow\mathbb{R}.$

We also denote interim probability that buyer $i$ is awarded the object of
quality $j$ as
$Q^{i}_{j}(v^{i})=\int_{V^{N-1}}q_{j}^{i}(v^{i},v^{-i})dF^{-i}(v^{-i})$ and
interim payments as
$M^{i}(v^{i})=\int_{V^{N-1}}m^{i}(v^{i},v^{-i})dF^{-i}(v^{-i}).$ Overall,
buyer $i$’s utility from reporting type $\widehat{v}^{i}$ when her true type
is $v^{i}$ equals

$U^{i}(\widehat{v}^{i},v^{i})=\sum^{J}_{j=1}v_{j}^{i}Q_{j}^{i}(\widehat{v}^{i})-M^{i}(\widehat{v}^{i}).$

A mechanism $(q,m)$ is incentive compatible if truthtelling is a Bayes-Nash
equilibrium, i.e.,

(IC) $U^{i}(v^{i},v^{i})\geq U^{i}(\widehat{v}^{i},v^{i})\text{\hskip
14.22636pt for all }\widehat{v},v\in V\text{ and }i\in N.$

Also, a mechanism $(q,m)$ is individual rational if

(IR) $U^{i}(v^{i},v^{i})\geq 0\text{\hskip 14.22636pt for all }v\in V\text{
and }i\in N.$

The seller’s problem can be formulated as follows

$\displaystyle\max_{q,m}\int_{V^{N}}\sum_{i\in
N}\left[m^{i}(v)-\sum_{j=1}^{J}c_{j}q_{j}^{i}(v)\right]dF(v)$
$\displaystyle\text{s.t.}\left\\{\begin{array}[]{l}(\ref{IC}),(\ref{IR}),\text{
and }\\\ \sum_{i\in N}\sum_{j\in J}q_{j}^{i}(v)\leq 1,q_{j}^{i}(v)\geq
0\text{\hskip 14.22636pt for all }v\in V,i\in N,j\in J.\end{array}\right.$

This problem can be rewritten in a more convenient way. First, we restrict
ourselves to symmetric allocations222This is only for the simplicity of
exposition. We do consider asymetric settings in our simulations.. Hence, we
drop index $i$ from $Q^{i}_{j}$, $M^{i}$, $U^{i}$, $v^{i}$, $q^{i}_{j}$, and
$m^{i}$. With some abuse of notation, we also denote buyer’s utility from
truthtelling as $U(v)\equiv U(v,v)$. Then, the incentive compatibility
constraints can be rewritten as

(ICC)
$U(v)-U(\widehat{v})\geq\sum_{j}Q_{j}(\widehat{v})(v_{j}-\widehat{v}_{j})\text{\hskip
14.22636pt for all }\widehat{v},v\in V,$

and the individual rationality constraints can be rewritten as

(IRR) $U(v)\geq 0\text{\hskip 14.22636pt for all }v\in V.$

There is no reason to leave any rents to the buyer with the lowest type.
Hence, $U(\underline{v})=0$. At the same time, the incentive compatibility
constraints imply that $U$ is convex and non-decreasing and, hence,
$U(\underline{v})=0$ guarantees that all individual rationality constraints
are satisfied.

Finally, using the seminal result due to Border (Border, 1991), the
feasibility constraints can be rewritten in terms of interim probabilities of
buyers getting the object as

(B) $\left\\{\begin{array}[]{l}Q_{j}(v)\geq 0\text{\hskip 14.22636pt for all
}v\in V,j\in J\\\ N\int_{A}\sum_{j\in J}Q_{j}(v)dF(v)\leq
1-\left(\int_{V\backslash A}dF(v)\right)^{N}\text{ for all }A\subset
V\end{array}\right..$

Finally, the optimization problem can be rewritten in terms of optimization
over $Q$ and $U$. The seller’s problem can be formulated as follows

($P^{*}$) $\left\\{\begin{array}[]{l}OPT_{*}=\max_{Q,U}\int_{V}\sum_{j\in
J}(v_{j}-c_{j})Q_{j}(v)-U(v)dF(v)\\\\[5.69054pt] \text{subject to
}(\ref{B}),\,(\ref{ICC}),\,U(\underline{v})=0.\end{array}\right..$

##  3\. Simulations

We adopt and improve the original finite-dimensional approximation algorithm
of Belloni et al. (Belloni et al., 2010) by focusing on local and downward-
sloping incentive-compatibility constraint (ICC) violations. Although these
local constraints are often violated in this approximate setting, we
drastically reduce the number of times all incentive-compatible constraints
need to be checked.

In order to approximate an optimal solution to $P^{*}$, we discretize the type
space $V$333This presentation mirrors Belloni et al. (Belloni et al., 2010,
§3).. Let $T$ denote a positive integer that controls the granularity of the
discretization. For each $j\in J$, let $V_{T}(j)$ denote the discretization of
the interval $[\underline{v}_{j},\overline{v}_{j}]$ given by
$V_{T}(j)=\\{\underline{v}_{j},\underline{v}_{j}+\epsilon,\underline{v}_{j}+2\epsilon,\dots,\overline{v}_{j}\\}$
where $\epsilon=\min_{j\in J}\\{(\overline{v}_{j}-\underline{v}_{j})/T\\}$.
Our discretized version of the type space $V$ is given by $V_{T}:=\prod_{j\in
J}V_{T}(j)$. Furthermore, we define a probability density function on $V_{T}$
by setting $\hat{f}(v)=f(v)/(\sum_{t\in V_{T}}f(t))$. We thus obtain a linear
program which is a finite-dimensional approximation of $P^{*}$ for each $T>0$
by replacing $V$ with $V_{T}$.

Figure 1: We iteratively grow the local region of the discretized type space
checked for downwards-sloping constraint violations. Notice that immediately
adjacent (ICC) constraints are always checked ($\times$) when the local region
increases in size around a point ($\bullet$).

Belloni et al. (Belloni et al., 2010, Algorithm 11) use a plane-putting
algorithm which works with a randomly chosen subset of incentive-compatibility
(ICC) and Border (B) constraints at each iteration. Belloni et al. (Belloni et
al., 2010, Lemma 10) provide an efficient reduction in the growth in $T$ of
the Border constraints (B) from $O(2^{T^{J}})$ to $O(T^{J}\log(T^{J}))$. We
adopt their solution to checking (B) constraints; however, our approach to
checking (ICC) constraints involves iteratively growing the ‘local’ region of
the type space around each point $v$ in the distcretized set of types $V_{T}$.
We do two things. First, all the immediately adjacent points in the
discretized type space are always checked for incentive compatbility.
Secondly, downwards-sloping points in the discretized type space are also
checked. Furthermore, the downwards-sloping region of the type space grows
until all (ICC) constraints are ultimately satisfied. This procedure is
illustrated in Figure 3. Thus, for a fixed-size local region aroud each point
in the discretized type space, we first satisfy local (ICC) and (B)
constraints as in the iterative plane-cutting algorithm of Belloni et al.
(Belloni et al., 2010). Then we run the separation oracle with all (ICC) and
(B) constraints. We then restart the solver with any previously violated
constraints, this time increasing the size of the local region around each
point in the discretized type space. This procedure iterates until no
constraints are violated. This modified version of Belloni et al.’s (Belloni
et al., 2010) algorithm is described in Algorithm 1.

$L=1,S=\emptyset,A=\emptyset,\overline{OPT}=\infty$;

violated_any_icc $\leftarrow$ TRUE;

while  _violated_any_icc_ do

violated_local_icc $\leftarrow$ TRUE;

while  _violated_local_icc_ do

$k=1,A^{k}=A,S^{k}=S$;

Solve the linear program associated with $S^{k}$. Let $OPT^{k}$ denote the
optimal value.;

Solve the separation oracle using only local (ICC) constraints in region $L$.
Let $A^{k}$ donate all violated local (ICC) and (B) constraints.;

if  _$A^{k}=\emptyset$_ then

violated_local_icc $\leftarrow$ FALSE;

Break;

end if

Select a subset $I^{k}\subset S^{k}$ of inactive (ICC) and (B) constraints;

if  _$OPT^{k} <\overline{OPT}$_ then

$S^{k+1}\leftarrow(S^{k}\setminus I^{k})\cup A^{k}\cup A$;

$\overline{OPT}\leftarrow OPT^{k}$;

else

$S^{k+1}\leftarrow S^{k}\cup A^{k}\cup A$;

end if

$k\leftarrow k+1$;

end while

Solve the separation oracle using all (ICC) constraints. Let $A^{*}$ donate
all violated (ICC) constraints.;

if  _$A^{*}=\emptyset$_ then

violated_any_icc $\leftarrow$ FALSE;

Break;

end if

$A\leftarrow A\cup A^{*}$;

$S\leftarrow S^{k}$;

$L\leftarrow L+1$;

end while

Algorithm 1 Iterative plane-cutting algorithm with local and downwards-sloping
(ICC) constraints

Our algorithm is written in Python 3.10 and uses Google’s open source linear
programming solver ‘GLOP’ available in their or-tools package (ortools).
Algorithm 1 recovers similar optimal values to that of Belloni et al. (Belloni
et al., 2010).

##  4\. Conjectures

The principal message of Belloni et al. (Belloni et al., 2010) is that the
revenue maximizing mechanisms in multiple-buyer settings could have quite
different qualitative features compared to the revenue maximizing mechanisms
in the single-buyer case. We investigate this message through several
conjectures.

The mechanism design literature analyzing single-buyer settings (see Armstrong
(Armstrong, 1996), Rochet and Chone (Rochet and Choné, 1998), Manelli and
Vincent (Manelli and Vincent, 2007)) argues that optimal revenue-maximizing
allocation mechanisms could be quite complicated. The optimal allocation
mechanism is characterized by bunching regions, i.e., different buyers’ types
receiving the same allocation of objects. In some cases, the optimal
allocation mechanism has to be random, i.e., buyers receive objects only with
some probability (see also Daskalakis et al. (Daskalakis et al., 2017)). In
contrast, Belloni et al. (Belloni et al., 2010) propose the class of
“exclusive buyer mechanisms” that performs quite well relative to the
numerical optimal mechanisms in their simulations. In an exclusive buyer
mechanism, buyers compete in the second-price auction for the right to be the
only buyer to get the object. The winner then chooses quality $q_{j}$ of the
object to acquire at price $p_{j}$. In other words, denote buyer $i$’s
function of its value

$\beta^{i}=\max(v_{1}^{i}-p_{1},...,v_{J}^{i}-p_{J}).$

In the exclusive buyer mechanism, buyer $i$ with the highest value $\beta^{i}$
wins the object and chooses the object quality grade $j$ for price
$\max_{l\neq i}(v^{l}_{j},p_{j})$.444Note that Belloni et al. (Belloni et al.,
2010) used a slightly different language to define an “exclusive buyer
mechanism.” They consider only the case with two objects and assumed that the
second-price auction could be augmented with a reserve price. At the same
time, one of the object qualities is allocated at no additional costs in their
original formulation. Both formulations are equivalent.

###### Conjecture 0.

The optimal auction revenue can be well approximated by the optimal exclusive
buyer mechanism.

A further important insight by Belloni et al. (Belloni et al., 2010) is that
for some multi-dimensional settings the optimal selling mechanism with
multiple buyers has no exclusion region. This is in sharp contrast to
Armstrong (Armstrong, 1996) and Rochet and Chone (Rochet and Choné, 1998) who
show that it is optimal not to sell with positive probability in multi-
dimensional settings with a single-buyer.

###### Conjecture 0.

In some multi-buyer settings the measure of buyers’ types that receive no
object (the exclusion region) in the optimal auction has measure zero in
contrast to the corresponding single-buyer setting.

We will see below (see Section 5) that we are able to reject both conjectures.
These conclusions, together with other simulations that we performed, bring us
to investigate another conjecture that connects the exclusion region in
optimal mechanisms for the single-buyer and multiple-buyer settings. This
conjecture was first proposed by Kushnir and Shourideh (Kushnir and Shourideh,
2022) in a different setting where there are two objects need to be allocated
to two buyers (as in (Armstrong, 1996)).

###### Conjecture 0.

The exclusion region of the optimal allocation is independent of the number of
buyers $N=1,2,3,...$

In the next section, we provide simulation results addressing these
conjectures.

##  5\. Results

To study the above conjectures, we consider several settings. All settings
concern either single or multiple buyers ($N=1,2,3$) who want to buy a single-
good of two possible quality grades ($J=2$). In all simulations that follow
each dimension of the type space $V$ is discretized into $T=20$ intervals.

Let us consider first a setting where buyer types are uniformly distributed on
$[2,3]\times[2,3]$. This is an extension of the environment that was analyzed
by Pavlov (Pavlov, 2011) for the optimal mechanism in the single-buyer case.

###### Setting 1.

Uniform distribution on $[2,3]\times[2,3]$, costs $c_{1}=0$, $c_{2}=0$, $N=2$
buyers, and $J=2$ qualities.

Figure 5 presents the results of our simulations. The first graph shows the
probability of obtaining object of quality 1, the second graph shows the
probability of obtaining object of quality 2, and the last graphs depicts the
exclusion region, i.e. the set of buyer’s types that does not receive any
object.

Figure 2: The optimal auction in Setting 1. The first figure and the second
figure show the interim allocation probabilities for quality 1 ($Q_{1}$) and
quality 2 ($Q_{2}$). The third figure depicts the exclusion region – the set
of buyer values that receive object with zero probability.

We can observe that the exclusion region in the optimal auction is not
rectangular. Hence, the allocation rule cannot be replicated with an exclusive
buyer mechanism introduced by Belloni et al. (Belloni et al., 2010). The
optimal auction has different qualitative properties with respect to the
exclusion region. Belloni et al. report the optimal auction revenue and the
revenue in the optimal exclusive buyer mechanism coincide in their simulated
setting (see Tables 2 and 3 in (Belloni et al., 2010)) subject to
computational error (i.e., $<10^{-6}$). We also find that, despite qualitative
difference, the difference in the revenue of optimal auction and the revenue
of the optimal exclusive buyer mechanism is around one percent.

To analyze Conjecture 2 we consider the following setting.

###### Setting 2.

Uniform distribution on $[6,8]\times[9,11]$, costs $c_{1}=0.9,c_{2}=5$,
$N=1,2$ buyers, $J=2$ qualities

The above setting for $N=2$ is the main simulation setting of Belloni et al.
(Belloni et al., 2010, Figure 1). Using simulations, they discovered that
there is no exclusion region in the case of multiple buyers. This is in stark
contrast with the findings of Armstrong (Armstrong, 1996) and Rochet and Chone
(Rochet and Choné, 1998) in the single-buyer case. To verify Belloni et al.
(Belloni et al., 2010) claim that the nature of the optimal selling mechanisms
are different for the single-buyer and multiple-buyer cases, we decided to run
simulations in the same setting, but only for $N=1$ buyer. The results for
both runs are presented in Figure 5.

Figure 3: The optimal mechansims for Setting 2. The first graph shows the
allocation for quality 1 ($Q_{1}$) and quality 2 ($Q_{2}$) for the single-
buyer case. The second figure shows the allocation for quality 1 ($Q_{1}$) and
quality 2 ($Q_{2}$) for the two-buyer case.

The figure illustrates that it is always optimal to sell the object in both
$N=1$ and $N=2$. This is different to the seminal result by Armstrong
(Armstrong, 1996) and Rochet and Chone (Rochet and Choné, 1998)!

Though this might seem to be a contradictory result, it is important to note
that Armstrong (Armstrong, 1996) and Rochet and Chone (Rochet and Choné, 1998)
consider a different setting than (Belloni et al., 2010). The two early papers
consider a problem of selling two objects to single buyer with each object
having one quality grade. However, Belloni et al. (Belloni et al., 2010)
consider the setting with only one object that might be of several quality
grades. The original Armstrong’s result requires the set of possible types to
be strictly convex. Clearly, the uniform distribution $[6,8]\times[9,11]$
clearly does not satisfy this condition. Rochet and Chone (Rochet and Choné,
1998) requires that the cost function of producing the objects to be smooth
(see Theorem 1 in (Rochet and Choné, 1998)). This assumption is not satisfied
in the setting considered by Belloni et al. (Belloni et al., 2010).

Armstrong (Armstrong, 1996) argues that if the set of possible buyer types is
strictly convex, then if the measure of exclusion region is zero, there has to
be a unique type that receives zero utility in optimal allocation. Then, if we
increase the tariff by $\epsilon$ uniformly among all buyer types, there
number of types that will be excluded is proportional to $\epsilon^{2}$. At
the same time, the revenue increases proportional to $\epsilon$. Hence, a
uniform increase of the tariff by $\epsilon$ increases revenue. Armstrong’s
logic does not hold for the example presented above. The set of types is not
strictly convex. In addition, one could notice that Figure 5 suggests that the
whole interval $6\times[9,p^{*}]$ for some $p^{*}\in[9,11]$ receives the same
zero utility in equilibrium. The measure of this interval is zero. However, if
one increases tariff by $\epsilon$, one would exclude a mass of types
proportional to $\epsilon$ not $\epsilon^{2}$. This breaks down Armstrong’s
logic. This is a surprising and novel observation to the best of our
knowledge.

During the analysis of the previous conjectures, we noticed that the exclusion
region in the optimal auction does not depend on the number of buyers (see
Conjecture 3). Hence, we decided to extensively test this conjecture in
numerous simulaton setting including symmetric distributions buyers’ types,
asymetric distributions of buyers’ types, and correlated distributions of
buyers’ types. Some of these settings are presented below.

###### Setting 3.

We consider several settings all with $J=2$ qualities:

  1. a)

Symmetric uniform, truncated normal, and beta555We use the beta distribution
given by probability density function
$f(x;a,b)=\frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)}x^{a-1}(1-x)^{b-1}$ where
$a=1,b=2$. distributions on $[0,1]\times[0,1]$, $c_{1}=0,c_{2}=0$, $N=1,2,3$
buyers;

  2. b)

Non-symmetric distributions (uniform $\times$ beta, uniform $\times$ truncated
normal, beta $\times$ truncated normal) on $[0,1]\times[0,1],$
$c_{1}=0,c_{2}=0$, $N=1,2,3$ buyers; and,

  3. c)

Mixture of ($\alpha=\frac{1}{3},\frac{1}{2},\frac{2}{3}$) uniform and
$(1-\alpha)$ beta distributions on $[0,1]\times[0,1],$ $c_{1}=0,c_{2}=0,$
$N=1,2,3$ buyers.

The results of these simulations are depicted below in Figure 5. Every graph
of the exclusion region is the same for $N=1,2,3$ buyers. The uniformity of
these and other our simulation results across a diversity of settings provides
strong support for Conjecture 3. To the best of our knowledge this is an
interesting and novel feature of optimal multi-dimensional auctions that was
originally proposed in a working paper by Kushnir and Shourideh (Kushnir and
Shourideh, 2022) in a different setting where there are two objects need to be
allocated to two buyers (as in (Armstrong, 1996)).

Overall, we do not consider simulations as definitive evidence for or against
the above conjectures. Rather, we consider our simulations as empirical
evidence which should guide future theoretical research in multi-dimensional
mechansism design.

Figure 4: The exclusion regions in optimal auctions corresponding to settings
3. The top figures depict a) the exclusion region for symmetric uniform,
truncated normal, and beta distributions with $N=1,2,3$ buyers. The middle
figures depict b) the exclusion region for uniform $\times$ beta, uniform
$\times$ truncated normal, beta $\times$ truncated normal distributions for
$N=1,2,3$ buyers. Lastly, the figures in the bottom row depict c) the
exclusion region for the mixture of
$\alpha=\frac{1}{3},\frac{1}{2},\frac{2}{3}$ uniform and $(1-\alpha)$ beta
distributions for $N=1,2,3$ buyers.

##  6\. Conclusion

We used simulations to study the properties of revenue maximizing auctions in
multi-dimensional settings. We showed that the set of buyer exclusive
mechanisms, proposed by Belloni et al. (Belloni et al., 2010), does not
approximate well the optimal revenue auction in some environments. We also
highlight that the absence of an exclusion region in main simulation example
in Belloni et al. (Belloni et al., 2010) is not due to the difference in the
properties of the optimal auctions in the single-buyer and multiple-buyer
case. Instead, Belloni et al. (Belloni et al., 2010)’s setting with only one
object of multiple qualities grades is different from classical settings in
Armstrong (Armstrong, 1996) and Rochet and Chone (Rochet and Choné, 1998),
where two objects each having one quality type are allocated. Hence, the
classical result about the presence of an exclusion region in single-buyer
setting does not apply to Belloni et al. (Belloni et al., 2010) setting. The
observation that in multi-dimensional settings the exclusion region in the
optimal auctions could be absent is novel in the literature. Our simulations
also support the conjecture first proposed by Kushnir and Shourideh (Kushnir
and Shourideh, 2022) that the exclusion region does not depend on the number
of buyers.

We treat our simulation results as guidance for future theoretical work. Our
next step is to identify conditions under which the exclusion region has
measure zero in optimal multi-dimensional auctions in Belloni et al. (Belloni
et al., 2010)’s setting. Additionally, we plan to analyze the conditions when
the exclusion region does not change with the number of buyers. Furthermore,
we have chosen to open-source our numerical library for simulating multi-
dimensional auctions to enable other researchers to explore their own
conjectures. We hope that other researchers use this library to explore their
own hypotheses and conjectures concerning multi-dimensional auctions.

## References

  * (1)
  * Armstrong (1996) Mark Armstrong. 1996\.  Multiproduct nonlinear pricing.  _Econometrica_ 64, 1 (1996), 51–75.
  * Armstrong (2000) Mark Armstrong. 2000\.  Optimal multi-object auctions.  _The Review of Economic Studies_ 67, 3 (2000), 455–481.
  * Belloni et al. (2010) Alexandre Belloni, Giuseppe Lopomo, and Shouqiang Wang. 2010\.  Multidimensional mechanism design: Finite-dimensional approximations and efficient computation.  _Operations Research_ 58, 4-part-2 (2010), 1079–1089.
  * Border (1991) Kim C. Border. 1991\.  Implementation of reduced form auctions: A geometric approach.  _Econometrica: Journal of the Econometric Society_ (1991), 1175–1187.
  * Daskalakis (2015) Constantinos Daskalakis. 2015\.  Multi-item auctions defying intuition?  _ACM SIGecom Exchanges_ 14, 1 (2015), 41–75.
  * Daskalakis et al. (2017) Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. 2017\.  Strong duality for a multiple-good monopolist.  _Econometrica_ 85, 3 (2017), 735–767.
  * Kushnir and Shourideh (2022) Alexey Kushnir and Ali Shourideh. 2022.  Optimal Auctions in Multi-Dimensional Environments. (2022).
  * Manelli and Vincent (2007) Alejandro M Manelli and Daniel R Vincent. 2007.  Multidimensional mechanism design: Revenue maximization and the multiple-good monopoly.  _Journal of Economic theory_ 137, 1 (2007), 153–185.
  * Myerson (1981) Roger B. Myerson. 1981\.  Optimal auction design.  _Mathematics of Operations Research_ 6, 1 (1981), 58–73.
  * Pavlov (2011) Gregory Pavlov. 2011\.  Optimal mechanism for selling two goods.  _The BE Journal of Theoretical Economics_ 11, 1 (2011).
  * Perron and Furnon ([n. d.) ]ortools Laurent Perron and Vincent Furnon. [n. d.].  _OR-Tools_.  Google.  https://developers.google.com/optimization/
  * Rochet and Choné (1998) Jean-Charles Rochet and Philippe Choné. 1998.  Ironing, sweeping, and multidimensional screening.  _Econometrica_ 66, 4 (1998), 783–826.