[a]Jacques Bloch

# Tensor-network study of the 3d $O(2)$ model at non-zero chemical potential
and temperature

Robert Lohmayer  Maximilian Meister

###### Abstract

We present results of tensor-network simulations of the three-dimensional
$O(2)$ model at non-zero chemical potential and temperature, which were
computed using the higher-order tensor-renormalization-group method (HOTRG).
This necessitated enhancements to the HOTRG blocking procedure to reduce the
truncation error in the case of anisotropic tensors. Moreover, the
construction of the truncated vector spaces was adapted to strongly reduce the
effect of systematic errors in the computation of observables using the
finite-difference method. Our (improved) HOTRG results for the evolution of
the number density with the chemical potential are in agreement with results
obtained with the worm algorithm, and both the Silver Blaze phenomenon at zero
temperature and the temperature dependence of the number density can be
adequately reproduced.

##  1 Introduction

In this talk we present first tensor-network results for the three-dimensional
$O(2)$ model in thermal equilibrium at non-zero chemical potential and
temperature [1]. We validate our results using benchmark data obtained with
the worm algorithm [2, 3, 4].

Simulations of classical or quantum spin systems in thermal equilibrium on a
d-dimensional lattice are typically performed using importance sampling Monte
Carlo (MC) methods, which are stochastic in nature. Recently an alternative,
deterministic method has been considered which reformulates the partition
function $Z$ as a fully contracted tensor network. On such a tensor network,
the higher-order tensor-renormalization-group method (HOTRG) is used to
compute observables numerically.

An important motivation to consider tensor-network methods is the possibility
to apply these methods when the action is complex, for example in the presence
of a chemical potential, and MC simulations fail because of the sign problem
[5].

To reformulate the partition function as a tensor network, one introduces dual
variables and integrates out the original degrees of freedom. This procedure
is similar to that encountered when applying the worm algorithm. However, the
computation of observables is very different. Whereas the worm algorithm uses
a closed-path Monte Carlo sampling, the tensor-network methods are based on
approximations using singular value decompositions (SVD) and are deterministic
in nature [6, 7, 8]. Although the application of tensor methods to statistical
physics models is quite new, it has already been applied to a variety of spin
models and gauge theories [9, 10, 11, 12, 13, 14, 15], mainly in two
dimensions but some also in three and four dimensions, see Ref. [16] for a
review. Herein we present the first tensor-network study of the three-
dimensional $O(2)$ model [1].

##  2 Tensor formulation of the 3d $\boldsymbol{O(2)}$ model

The $O(2)$-symmetric action of this three-dimensional quantum model with
chemical potential is given by

$\displaystyle
S=-\beta\sum_{k=1}^{V}\sum_{\nu=1}^{3}\cos(\theta_{k}-\theta_{k+\hat{\nu}}-i\mu\delta_{\nu
3})$ (1)

where $k$ is a linear index defined on the cubic $N_{s}^{2}\times N_{t}$
lattice, $V$ is its volume, $\beta$ is the coupling, $\mu$ the chemical
potential acting in the time direction, and $\hat{\nu}$ a unit step in the
$\nu$-direction. The partition function for the model is

$\displaystyle
Z=\int_{0}^{2\pi}\frac{d\theta_{1}}{2\pi}\dots\int_{0}^{2\pi}\frac{d\theta_{V}}{2\pi}\,e^{-S(\theta_{1},\cdots,\theta_{V})}.$
(2)

When $\mu$ is non-zero, the action is complex and MC simulations encounter a
strong sign problem. To reformulate the partition function as a fully
contracted tensor network, one factorizes the Boltzmann probability over the
lattice links and rewrites the exponential factor on each link using the
Jacobi-Anger expansion

$\displaystyle
e^{\beta\cos\theta}=\sum_{n=-\infty}^{\infty}I_{n}(\beta)\,e^{in\theta},$ (3)

where $I_{n}(\beta)$ are modified Bessel functions of the first kind. This
procedure introduces new link variables $n_{k,\nu}$ on all links connecting
the sites $k$ and $k+\hat{\nu}$. The partition function can then be reordered
such that the multidimensional spin integral factorizes in individual spin
integrals

$\displaystyle\int_{0}^{2\pi}\frac{d\theta}{2\pi}e^{in\theta}=\delta_{n,0},\quad
n\in\mathbb{Z}.$ (4)

Once the spins are integrated out, the partition function can be reformulated
as a complete contraction of a tensor network,

$\displaystyle
Z=\sum_{\\{n\\}}\prod_{k=1}^{V}T_{n_{k-\hat{1},1}n_{k,1}n_{k-\hat{2},2}n_{k,2}n_{k-\hat{3},3}n_{k,3}}$
(5)

with local tensors of order six,

$\displaystyle
T_{n_{k-\hat{1},1}n_{k,1}n_{k-\hat{2},2}n_{k,2}n_{k-\hat{3},3}n_{k,3}}=\sqrt{e^{\mu(n_{k,3}+n_{k-\hat{3},3})}\prod_{\nu=1}^{3}I_{n_{k,\nu}}(\beta)I_{n_{k-\hat{\nu},\nu}}(\beta)}\,\,\times\underbrace{\delta_{\Delta
n_{k},0}}_{\text{current conservation}}$

where $\Delta n_{k}$ is the discretized divergence of the $O(2)$ current,

$\displaystyle\Delta n_{k}=\sum_{\nu=1}^{3}(n_{k,\nu}-n_{k-\hat{\nu},\nu}).$

Although formally $n\in\mathbb{Z}$, one truncates the range of $n$ in practice
by keeping only the $D$ largest weights $I_{n}(\beta)\,e^{\mu
n\delta_{\nu,3}}$ in the construction of the initial local tensor, which then
has total dimension $D^{6}$.

To compute thermodynamic observables one has to compute derivatives of $\ln Z$
with respect to the parameters of the model. In the tensor formulation one can
either perform numerical derivatives using finite differences of computed
values of $\ln Z$ or one can take analytical derivatives of the tensor
network, which then yields a formula involving the pure tensor and one or more
so-called impurity tensors. Both methods have their own problems, which are
related to systematic errors in the contraction of tensor networks.

##  3 Higher order tensor renormalization group

In HOTRG the full tensor-network contraction is performed using an iterative
blocking procedure [8]. An example of this procedure for a $4\times 4$ lattice
in two dimensions is shown in Fig. 1. In this procedure two adjacent tensors
of coarsening level $i$ are contracted over their shared link in direction
$\nu$ to yield a tensor of coarsening level $i+1$,

$\displaystyle T^{(i)}\odot_{\nu}T^{(i)}\to T^{(i+1)}.$ (6)

When the tensor network has been blocked iteratively until only a single
tensor remains, the latter is traced over its forward-backward directions to
produce the partition function.

$\to$ $\to$ $\to$ $\to$

$T^{(0)}\to{\color[rgb]{0,0,.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,.75}T^{(1)}}$

$\to$
$T^{(1)}\to{\color[rgb]{.9,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{.9,0,0}T^{(2)}}$
$\to$
$T^{(2)}\to{\color[rgb]{0,0,.75}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,.75}T^{(3)}}$
$\to$
$T^{(3)}\to{\color[rgb]{.9,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{.9,0,0}T^{(4)}}$
$\to$ $T^{(4)}$

Figure 1: Typical blocking procedure in 2d HOTRG using alternating contraction
directions. After each blocking a new local tensor is constructed.

$\longrightarrow$ $\stackrel{{\scriptstyle
U^{(y)},U^{(z)}}}{{\longrightarrow}}$

$T^{(i)}$ $T^{(i)}$ $\longrightarrow$ $M$ $\stackrel{{\scriptstyle
U^{(y)},U^{(z)}}}{{\longrightarrow}}$ $T^{(i+1)}$

Figure 2: Contraction of two local tensors in the three-dimensional case. On
the left two local tensors with modes of dimension $D$ are contracted over
their shared link along the $x$-direction to yield the tensor $M$ with fat
modes of dimensions $D^{2}$ in the directions perpendicular to the contraction
direction. The frames are then applied to the fat modes to construct the new
local tensor $T$ on the right, where all modes have again dimension $D$.

However, if we look at the dimensionality of the tensor contractions we notice
that some additional approximations are required. When contracting two local
tensors, as shown in Fig. 2 for three dimensions, the modes perpendicular to
the contraction direction can be gathered in fat modes and the dimensionality
of the new blocked tensor grows. Two tensors $T$ of dimension $D^{6}$ are
contracted along the $x$-direction into a tensor $M$ of dimension $D^{10}$
where the fat modes have dimension $D^{2}$,

$\displaystyle T^{(i)}\odot_{x}T^{(i)}\longrightarrow M.$ (7)

The tensor $M$ cannot be used as such in further blockings because this would
give rise to an exponential growth of the tensor dimension and of the
computational cost. To keep the dimensionality under control, the $D^{2}$
dimensional fat modes of $M$ are truncated by projecting them on
$D$-dimensional subspaces, such that the new local tensor again has dimension
$D^{6}$. This is achieved using $D^{2}\times D$ semi-orthogonal matrices that
are constructed using the singular value information obtained from SVDs of the
matrix unfoldings of $M$ with respect to all its fat modes, in analogy to the
higher order singular value decomposition (HOSVD) [6]. However, a peculiarity
of the HOTRG blocking procedure is that the forward and backward fat modes
must be projected on the same subspaces.

The procedure is illustrated in Fig. 2 for a contraction in the $x$-direction
where the truncation is performed using the $D^{2}\times D$ matrices $U^{(y)}$
and $U^{(z)}$, also called frames, and which yields the new local tensor

$\displaystyle M\stackrel{{\scriptstyle
U^{(y)},U^{(z)}}}{{\longrightarrow}}T^{(i+1)}.$ (8)

##  4 Results

###  4.1 Specific heat

Using HOTRG we computed the first and second order derivatives of $\ln Z$ with
respect to $\beta$, which yield the internal energy and the specific heat

$\displaystyle C_{\rm v}=\frac{\beta^{2}}{V}\frac{\partial^{2}\ln
Z}{\partial\beta^{2}}.$ (9)

Computing susceptibilities using HOTRG is quite challenging as second-order
finite differences are very sensitive to the systematic errors on $\ln Z$.
This is illustrated in the left panel of Fig. 3 where we show the specific
heat computed with second-order finite differences on a $32^{3}$ lattice using
the triad TRG [17], which is a state-of-the-art cost-effective variant of
HOTRG introducing additional approximations. Even with $D=72$ one has to take
$\Delta\beta$ so large to overcome these systematic errors, that a clean
investigation of the phase transition region is not possible. For this reason
we developed a stabilized finite-difference (SFD) method for the standard
HOTRG procedure, see Sec. 4.4 for more details. Although the bond dimension
can only be taken up to $D=15$ with HOTRG, the SFD method allows us to reduce
$\Delta\beta$ from 0.01 to $10^{-6}$ and the observable is now quite smooth
and accurate, as can be seen in the same plot. To verify the results obtained
with the SFD method we also investigated the convergence of the transition
peak for increasing $D=9,11,13,15$. The right panel of Fig. 3 shows that
already for $D=15$ the results are very stable. Although the accuracy of
$\beta_{c}$ is still far from that obtained with Monte Carlo methods, the
reproduction of a clean transition peak is an achievement that is far from
trivial with tensor-network methods.

Figure 3: Specific heat $C_{\rm v}$ versus coupling $\beta$ on a $32^{3}$
lattice. Left panel: Comparison of triad TRG with D=72 and a second-order
finite difference of $\ln Z$ with step size $\Delta\beta=0.01$, and HOTRG with
D=15 using a stabilized second-order finite-difference scheme with
$\Delta\beta=10^{-6}$. The peak suggests that the critical coupling is between
$\beta=0.45$ and $\beta=0.46$. For reference, we show the infinite-volume MC
result $\beta_{\rm{c}}=0.454165$ from [18] by the black dashed line. Right
panel: Convergence of the stabilized finite-difference results for HOTRG with
$D=9,11,13,15$.

###  4.2 Number density and Silver Blaze

One of the main motivations to use tensor-network methods is the possibility
to investigate systems with complex actions, which are not accessible to
standard importance sampling Monte Carlo methods due to the sign problem. In
the presence of a chemical potential, the $O(2)$ model has a strong sign
problem, and reweighting, which is a Monte Carlo based algorithm to circumvent
the sign problem, notoriously fails.

To validate the HOTRG method in this situation we first looked at the number
density

$\displaystyle\rho=\frac{1}{V}\frac{\partial\ln Z}{\partial\mu}$ (10)

as a function of the chemical potential at zero temperature, i.e., with
$N_{t}=N_{s}$. As can be seen in Fig. 4, the density remains zero until the
chemical potential reaches a critical value $\mu_{c}$ which corresponds to the
mass of the lowest excitation.111The variation of $\mu_{c}$ with $\beta$ in
Fig. 4 is a renormalization effect as the lattice spacing is inversely
proportional to the coupling for $\beta\leq\beta_{c}$, such that
$\mu_{c}=ma(\beta)=\xi^{-1}(\beta)$. This property is called the _Silver
Blaze_ [19] and is very hard to reproduce numerically as it is intrinsically
coupled to the sign problem in the original spin formulation of the partition
function [5]. The tensor-network method, on the other hand, does very well to
reproduce this property, and the results agree well with those obtained
previously with the worm algorithm [4].

Figure 4: Number density $\rho$ versus chemical potential $\mu$ for $T=0$ on a
$64^{3}$ lattice. The data obtained using the triad TRG with $D=50$ (symbols)
are compared with those of the worm algorithm (smooth lines). We clearly see
the Silver Blaze property of the 3d $O(2)$ model as $\rho$ is zero until $\mu$
reaches a critical value $\mu_{c}$.

###  4.3 Non-zero temperature and chemical potential

The tensor-network method can also be used to investigate the model with
chemical potential at non-zero temperature, where the time extent of the
lattice is reduced such that $N_{t}<N_{s}$. Due to the HOTRG blocking
procedure it is natural to choose $N_{t}=2^{n}$. In Fig. 5 we show the number
density on a $64^{2}\times N_{t}$ lattice with $N_{t}=2,4,8,16$ at
$\beta=0.44$. For large $N_{t}$ the results are close to the $T=0$ results of
Fig. 4, but as $N_{t}$ is lowered, higher temperatures are reached and the
number density becomes non-zero as soon as $\mu>0$. This confirms that the
Silver Blaze property no longer holds away from zero temperatures. At non-zero
temperature, the HOTRG results, which were computed with $D=13$, an improved
contraction order and stabilized finite differences, agree well with the
results obtained with the worm algorithm. These two improvements to the HOTRG
method are briefly discussed below in Sec. 4.4.

Figure 5: Temperature dependence of $\rho$ versus $\mu$ on a $64^{2}\times
N_{t}$ lattice with $N_{t}=2,4,8,16$ at $\beta=0.44$. We compare the tensor
data obtained using HOTRG with $D=13$, an improved contraction order and
stabilized finite differences with data obtained using the worm algorithm
(solid lines).

###  4.4 Improvements to standard HOTRG

We briefly describe two improvements to the standard HOTRG method which were
used to produce some of the results presented in this paper.

One problem with the standard HOTRG method is that it blocks the lattice by
alternating between the different lattice directions. For anisotropic tensors
this by no means guarantees to produce a good global truncation error [1]. We
therefore developed an _improved contraction order_ where the contraction
direction is chosen such that the (approximate) truncation error is minimized
in each coarsening step. This procedure only requires a sub-leading additional
cost, is especially useful in case of anisotropic tensors and naturally suits
the blocking of asymmetric lattices. Although this procedure is local, it has
in general a very positive effect on the global truncation error.

The second improvement is related to the computation of observables. The
impurity method has a systematic error due to the common truncation frames
used for the pure and impure tensors [1]. This error is especially serious in
the case of second-order impurities used to compute susceptibilities. On the
other hand, the finite-difference method suffers from jumps in $\ln Z$ at
nearby parameter values used in the finite-difference formulas, which are
caused by level crossings or (almost) degenerate singular values. This
generates a very large scatter in the observables, especially in
susceptibilities. To resolve this problem we developed a _stabilized finite-
difference_ method. At each blocking step one first computes the HOSVD
factorizations of the blocked tensors for the nearby parameter values used in
the finite-difference formula. Then, one analyzes the spaces of singular
vectors and performs orthogonal transformations to construct $D$-dimensional
subspaces for the nearby parameter values with large singular value content
and maximal overlap.

##  5 Outlook

We also made some further improvements that still need some more validation
and development.

In the hierarchical tensor HOTRG (HT-HOTRG) method we use an additional HOSVD
factorization of the local tensor to improve the HOTRG efficiency in 3d and 4d
[20]. The basic idea is similar to that of the triads but our approach gathers
the backward and forward mode of each direction in a super-mode which is then
truncated to a smaller dimension using a HOSVD approximation.

In the iterative Super-Q method we implemented an improved construction of the
truncation frames to reduce the total truncation error of the blocked tensor
at each coarsening step, whereas the standard HOTRG procedure is restricted to
(partially) reducing the truncation error on the individual modes.

In the future we will extend the stabilized finite differences to
factorization schemes like triad-TRG and HT-HOTRG. This is not so
straightforward because the additional approximations of these schemes undo
the stabilization effects of the SFD method. In another project we will
investigate how to use environment information in three- and four-dimensional
systems to improve the local truncations in HOTRG, similarly to HOSRG [8].

In other contributions to these proceedings we present tensor-network results
of the strong-coupling $U(N)$ model in 3d and 4d [20] and of an effective
$Z_{3}$ model for QCD at non-zero chemical potential [21].

In a current project we study the strong-coupling $SU(3)$ gauge theory, which
requires the use of Grassmann-HOTRG to handle the baryon-meson system.

## Acknowledgments

We thank Raghav G. Jha for his collaboration on this project.

## References

  * Bloch  _et al._ [2021] J. Bloch, R. G. Jha, R. Lohmayer, and M. Meister, Tensor renormalization group study of the three-dimensional $O(2)$ model, Phys. Rev. D104, 094517 (2021).
  * Prokof’ev and Svistunov [2001] N. Prokof’ev and B. Svistunov, Worm Algorithms for Classical Statistical Models, Phys. Rev. Lett. 87, 160601 (2001).
  * Banerjee and Chandrasekharan [2010] D. Banerjee and S. Chandrasekharan, Finite size effects in the presence of a chemical potential: A study in the classical non-linear O(2) sigma-model, Phys. Rev. D81, 125007 (2010).
  * Langfeld [2013] K. Langfeld, Phase diagram of the quantum O(2)-model in 2+1 dimensions, Phys.Rev. D87, 114504 (2013).
  * Aarts [2012] G. Aarts, Complex Langevin dynamics and other approaches at finite chemical potential, PoS LATTICE2012, 017 (2012).
  * De Lathauwer  _et al._ [2000] L. De Lathauwer, B. De Moor, and J. Vandewalle, A multilinear singular value decomposition, SIAM Journal on Matrix Analysis and Applications 21, 1253 (2000).
  * Levin and Nave [2007] M. Levin and C. P. Nave, Tensor renormalization group approach to two-dimensional classical lattice models, Phys. Rev. Lett. 99, 120601 (2007).
  * Xie  _et al._ [2012] Z. Y. Xie, J. Chen, M. P. Qin, J. W. Zhu, L. P. Yang, and T. Xiang, Coarse-graining renormalization by higher-order singular value decomposition, Phys. Rev. B86, 045139 (2012).
  * Akiyama  _et al._ [2019] S. Akiyama, Y. Kuramashi, T. Yamashita, and Y. Yoshimura, Phase transition of four-dimensional ising model with higher-order tensor renormalization group, Phys. Rev. D100, 054510 (2019).
  * Yu  _et al._ [2014] J. F. Yu, Z. Y. Xie, Y. Meurice, Y. Liu, A. Denbleyker, H. Zou, M. P. Qin, and J. Chen, Tensor renormalization group study of classical XY model on the square lattice, Phys. Rev. E89, 013308 (2014).
  * Zou  _et al._ [2014] H. Zou, Y. Liu, C.-Y. Lai, J. Unmuth-Yockey, A. Bazavov, Z. Y. Xie, T. Xiang, S. Chandrasekharan, S. W. Tsai, and Y. Meurice, Progress towards quantum simulating the classical O(2) model, Phys. Rev. A90, 063603 (2014).
  * Yang  _et al._ [2016] L.-P. Yang, Y. Liu, H. Zou, Z. Y. Xie, and Y. Meurice, Fine structure of the entanglement entropy in the O(2) model, Phys. Rev. E93, 012138 (2016).
  * Bazavov  _et al._ [2015] A. Bazavov, Y. Meurice, S.-W. Tsai, J. Unmuth-Yockey, and J. Zhang, Gauge-invariant implementation of the Abelian Higgs model on optical lattices, Phys. Rev. D92, 076003 (2015).
  * Kuramashi and Yoshimura [2019] Y. Kuramashi and Y. Yoshimura, Three-dimensional finite temperature Z2 gauge theory with tensor network scheme, JHEP 2019 (8), 023.
  * Kuramashi and Yoshimura [2020] Y. Kuramashi and Y. Yoshimura, Tensor renormalization group study of two-dimensional U(1) lattice gauge theory with a $\theta$ term, JHEP 2020 (4), 089.
  * Meurice  _et al._ [2020] Y. Meurice, R. Sakai, and J. Unmuth-Yockey, Tensor field theory with applications to quantum computing, arXiv:2010.06539 [hep-lat] (2020).
  * Kadoh and Nakayama [2019] D. Kadoh and K. Nakayama, Renormalization group on a triad network, arXiv:1912.02414 [hep-lat] (2019).
  * Xu  _et al._ [2019] W. Xu, Y. Sun, J.-P. Lv, and Y. Deng, High-precision Monte Carlo study of several models in the three-dimensional U(1) universality class, Phys. Rev. B 100, 064525 (2019).
  * Cohen [2003] T. D. Cohen, Functional integrals for QCD at nonzero chemical potential and zero density, Phys. Rev. Lett. 91, 222001 (2003).
  * Milde  _et al._ [2021] P. Milde, J. Bloch, and R. Lohmayer, Tensor-network simulation of the strong-coupling U(N) model,  _proceedings of "The 38th International Symposium on Lattice Field Theory"_ , PoS LATTICE2021, 462 (2021).
  * Unmuth-Yockey  _et al._ [2021] J. Unmuth-Yockey, J. Bloch, R. Lohmayer, and S. Schweiß, Effective $Z_{3}$ model for finite-density QCD with tensor networks,  _proceedings of "The 38th International Symposium on Lattice Field Theory"_ , PoS LATTICE2021, 062 (2021).


|  Self-assembly and percolation in magnetic colloids
---|---
|  Hauke Carstensen,a Anne Krämer,a Vassilios Kapaklis,a and Max Wolffa
|  We study the self-assembly of branching-chain networks and crystals in a
binary colloidal system with tunable interactions. The particle positions are
extracted from microscope images and order parameters are extracted by image
processing and statistical analysis. With these, we construct phase diagrams
with respect to particle density, ratio and interaction. In order to draw a
more complete picture, we complement the experiments with computer
simulations. We establish a region in the phase diagram, where bead ratios and
interactions are symmetric, promoting percolated structures.

##

††footnotetext: a Department of Physics and Astronomy, Uppsala University, Box
516, SE-75120 Uppsala, Sweden; E-mail<EMAIL_ADDRESS>
##  1 Introduction

Self-assembly is the spontaneous formation of ordered structures on all
length-scales 1 and a new route for the design of materials with complex
functionality 2. For small building blocks and finite temperatures entropy
will allow a system to reach the global minimum in free energy and
thermodynamic equilibrium. For systems dominated by the interaction between
the constituents this may not be the case and the system can get trapped in a
metastable state or become kinetically arrested 3.

Colloidal systems consist of microscopic beads solved in a carrier liquid.
Typically, the size of these beads is large and thermal energy becomes
negligible. The systems’ phase behaviour is defined by the interactions
between the beads, making them interesting for the study of phase formation
and self-assembly. By coating the bead surface with polymers, soft steric
interactions may be introduced 4. More long-ranged interactions that are
possible to realize, are Coulomb interactions. The self-assembly of charged
colloids was studied for beads of different size 5, aspect ratio 6 as well as
opposite charge 7. Even more rich in behaviour are magnetic interactions,
since these are of dipolar nature and may be altered by external magnetic
fields 8. The anisotropy of the interaction leads to the formation of clusters
in form of rings or chains with a head to tail orientation of the individual
particles 9. With decreasing temperature or increasing density the size of
such clusters grows and networks may form. These are challenging to study for
nanometer sized particles as they require frozen samples to allow studies with
transmission electron microscopy 10 or computer simulations 11, 12. For larger
particles the assembly process is easier to follow 13 and rings, chains and
small networks were reported. Illustrative in this context is the study of cm
sized particles with different magnetic moments and their pattern formation
and segregation 14, 15. It was shown that by shaking and quenching magnetic
particle systems larger open networks may be formed 16, 17. All the above
mentioned studies where done without externally applied magnetic field. Time
dependent magnetic fields, however, allow precise tuning of the interactions
18 and control of the self-assembly process 19 as well as the study of the
kinetics of self-assembly 20 and even the motion of self-assembled magnetic
surface swimmers 21. By dispersing the magnetic beads in a ferrofluid matrix,
an effective moment may be introduced, leading to tunable particle
interactions. The local self-assembly of such systems has been studied 22 and
a phase diagram of the local coordination was presented 23. For a two
dimensional systems with in plane magnetic field and depending on the
interaction between the beads cubic or hexagonal phases may form 24.

In technology, magnetic liquids are applied, for example, in loud speakers 25,
tunable photonic 26, 27, 28 or plasmonic structures 29 and tunable shock
absorbers 30. These applications require knowledge on phase formation, not
only on the local length-scales but also global, e.g. the formation of
clusters or extended networks. On intermediate length-scales colloidal
crystals or networks may form, which for micrometer-sized particles allow
tuning of the viscosity in so called magneto-rheological materials 31, 32.

An important concept in this context is jamming, which allows relating changes
in macroscopic material properties, e.g. viscosity, to topological constrains
33. In the case of attractive interactions a phase diagram of jamming has been
established 34 and it was shown that the jamming transition in systems with
attractive and repulsive interactions, fall into different universality
classes 35, 36. Similar to jamming, percolation, may affect the macroscopic
properties of a system. In the percolated state all parts of a system are
connected with each other. The jamming as well as percolation transition are
characterised by critical densities 37. The critical density for percolation
was calculated for different coordinations in two and three dimensions 38 and
is very similar to jamming happening at a critical random-close-packing
density 33. The influence of a long range repulsion and short range attraction
on the percolation transition was investigated systematically by Monte-Carlo
simulations 39. These show that long-ranged repulsion increases the average
cluster size and lowers the volume fraction for the percolation threshold.

In this communication, we report on the self-assembly and percolation of a
binary, two dimensional system of magnetic beads with tunable interactions in
an out-of-plane magnetic field. We classify the cluster formation with respect
to the coordination of the individual beads, the crystal symmetry and
percolation. We find that the critical density for percolation depends on the
interaction between the beads as well as the bead ratio and report the lowest
critical density for a bead ratio of 1:1 with attraction between the two
species of beads and repulsion among beads of the same type.

##  2 Experimental details

Monodisperse micrometer-sized spherical particles (beads) – one magnetic and
one non-magnetic – are suspended in a water-based ferrofluid. The beads,
purchased from Microparticles GmbH, are composed of polystyrene and have a
diameter of 10 $\mu$m. The magnetic beads are coated by a shell of magnetic
nano-particles. The ferrofluid (FF) consists of 10 nm iron oxide (Fe3O4)
nanoparticles, dispersed in water and purchased from LiquidResearch. In
suspension, the beads exhibit an apparent magnetic behaviour mediated by the
surrounding ferrofluid 40, 24, 41. The effective magnetic susceptibility of
the suspended beads is modified by the susceptibility of the ferrofluid. This
effect is in analogy to the concept of effective densities for objects in
fluids, as described by the Archimedes principle, resulting in an apparent
reduction of the susceptibility of the magnetic beads. The non-magnetic beads
form magnetic voids in the ferrofluid matrix and may be assigned an effective
magnetic susceptibility. By changing the concentration of magnetic nano-
particles in the ferrofluid, the effective moments and thus the interaction
between the beads can be tuned.

Fig. 1: Panel (a) depicts the transmission microscope setup. The panel to the
upper right shows the magnetic flux density. Panel (b) is a typical microscope
image with the magnetic and non-magnetic beads in darker and brighter color,
respectively. The particles have been identified automatically by evaluating
their brightness (bottom right).

In the limit, $\chi_{\text{M}}<<1$ and $\chi_{\text{FF}}<<1$, with
$\chi_{\text{M}}$ and $\chi_{\text{FF}}$ being the susceptibilities of the
magnetic beads and the ferro-fluid, respectively, the effective bead
susceptibilities $\chi_{\text{M,eff}}$ and $\chi_{\text{N,eff}}$, for the
magnetic and non-magnetic beads, respectively, are 23, 22, 24, 42:

$\displaystyle\chi_{\text{M,eff}}$
$\displaystyle\propto\chi_{\text{M}}-\chi_{\text{FF}}$ (1)
$\displaystyle\chi_{\text{N,eff}}$ $\displaystyle\propto-\chi_{\text{FF}}$ (2)

If the beads are confined along one dimension and a magnetic field is applied
along the confinement direction, the interaction between the beads can be
classified as follows:

  * •

The interaction between identical beads is repulsive but tunable in strength,
by changing the concentration of magnetic nano-particles in the ferrofluid.

  * •

For $\chi_{\text{M,eff}}=0$ and $\chi_{\text{N,eff}}=0$ the magnetic and non-
magnetic beads, respectively, are non-interacting.

The interaction between the two types of beads can be further modified in the
following ways 24:

  * •

For $\chi_{\text{N,eff}}<0<\chi_{\text{M,eff}}$ the coupling is anti-
ferromagnetic and an attractive force is present between magnetic and non-
magnetic beads.

  * •

For $\chi_{\text{M,eff}}<0$ and $\chi_{\text{N,eff}}<0$ the interaction
between all particles is repulsive.

This tunable interaction allows systematical study of the structure formation
in this binary system, with the ground states in the local ordering having
been established previously 23, 43, 24, 41. Here, we focus on the structures
formation on larger length-scales and percolation phenomena.

The samples were prepared by mixing 20 $\mu l$ ferrofluid, 5 $\mu l$ (1% w/w)
magnetic beads dispersion and 1 $\mu l$ (2.5% w/w) non-magnetic beads
dispersion. This results in approximately equal numbers of magnetic and non-
magnetic beads present in the sample. However, the beads may be
inhomogeneously distributed and the local densities and ratios vary spatially
within each sample. This enables systematical study of the effect of density
and bead ratio on the self-assembly. To vary the interaction between the
microbeads, a series of samples with varying FF concentration were prepared.
All of the samples were confined between two glass slides separated by an oil-
covered 25 $\mu$m thick Mylar ring and studied by transmission optical
microscopy. An out-of-plane magnetic field, with a maximum strength of 14 mT,
was applied using a pair of Helmholtz coils. The magnetic flux density was
calculated with finite element methods, implemented in FEMM 44, 24. Fig. 1(a)
shows a sketch of the experimental setup and the upper right panel results of
the field calculation, indicating that the magnetic field is homogeneous over
the area of the sample. The sample was loaded into the sample cell at zero
field and all microscope images were taken at an out-of-plane field of 0.14
mT. After loading the samples and before acquiring the images with the
microscope, the field is cycled (switched on and off) repeatedly in order to
approach an equilibrium structure. Subsequently, microscope images are
recorded and bead positions are automatically extracted, identifying circlular
structures using image processing routines in MATLAB®. The bead types are
distinguished by their apparent brightness in the images. In addition, the
automatic detection was made more robust, utilizing a neural network algorithm
trained on three images with labeled data (bead positions and types).

Fig. 2: Microscope images (top row) and simulated data (bottom row) for
varying bead densities $\rho$, bead ratios $r$, and interactions
$\chi_{\text{FF}}/\chi_{\text{M}}$.

To complement the experiments, we performed computer simulations. Magnetic and
non-magnetic beads are placed sequentially at random positions (without
overlaps). The size of the simulated rectangular area was chosen to match the
size of a typical microscope image ($50\times 37$ bead diameters) and periodic
boundary conditions were applied. We further assume zero temperature,
justified by the large size of the beads and the negligible Brownian motion as
well as significant viscosity of the ferrofluid (zero bead momentum), no
inertia and an overdamped equation of motion. The beads’ magnetic moment is
described as out-of-plane dipoles. To avoid overlapping of particles a hard
sphere potential was used and particles are placed next to each other once
they touch. In each simulation step the bead displacements are calculated from
the force acting upon each bead, resulting from the presence of all other
beads, according to:

$F_{j}=m_{j}c\sum_{k}\frac{m_{k}}{r_{j,k}^{-4}}$ (3)

where $m_{j}$ and $m_{k}$ are the dipole moments of beads separated by a
distance $r_{j,k}$. As the dipolar forces decay rapidly with distance, we
calculate the forces applying a cutoff of six bead diameters. Furthermore, the
dipole force is scaled by $c=0.01$ to keep the displacements in each step much
smaller then one bead diameter. Our simulations minimise the total energy of
the system and typically converge after 15000 iteration steps.

##  3 Results

Representative microscope images are shown in Fig. 2 (top row). The bead
density $\rho$ defined as the image area coverage by beads, bead type ratio
$r=N_{\text{M}}/N_{\text{N}}$ with $N_{\text{M,N}}$ the number of magnetic (M)
and non-magnetic (N) beads, and relative susceptibility
$\chi_{\text{FF}}/\chi_{\text{M}}$, for which an image was recorded, is stated
above each column of images. Panel (a) shows an image recorded for large
values of $\chi_{\text{FF}}/\chi_{\text{M}}$. In this case the interaction
between all beads is repulsive and they separate well. The blue beads
(magnetic) are slightly closer to each other, as the force between them is
smaller compared to the non-magnetic ones. No clustering or percolation is
visible. Panel (b) was extracted for equal bead ratio and
$\chi_{\text{FF}}/\chi_{\text{M}}=0.5$, resulting in the strongest attractive
force between magnetic and non-magnetic beads. Two different beads have a
strong tendency to stick together and tile. As the bead ratio is one, they
form clusters with four-fold symmetry. Panel (c) shows an image taken at a
very unequal bead ratio and $\chi_{\text{FF}}/\chi_{\text{M}}=0.33$. Beads of
different kinds attract each other and organize in flower-like structures.
However, the excess of one particle species can not be fully compensated,
leading to repulsion and many isolated beads. Panel (d) shows the case of
unequal bead ratio of 1/4 and $\chi_{\text{FF}}/\chi_{\text{M}}=0.25$. As in
panel (c), beads with a large effective moment are coordinated by the beads
with smaller moment. However, in this case the excess of one bead species is
smaller and in a second step more beads with large dipole moments, attach to
the shell of the cluster. As a result larger clusters are formed with local
six fold symmetry but still several isolated beads are visible. Panel (e)
shows a picture taken with small $\chi_{\text{FF}}/\chi_{\text{M}}$ and a bead
ratio closer to one. Here it is possible to compensate for the differences in
moment and the repulsion between clusters is overcome, forming networks or
percolated structures. One might say that one type of beads is the glue
keeping the other type, with repulsive interaction, together. The lower panels
in Fig. 2 show computer simulations performed for identical parameters as in
the upper panels. The simulations look similar to the microscope images, with
slightly larger density fluctuations being present in the experimental data.
Considering the good visual agreement we have performed more computer
simulations and systematically varied all parameters, $\rho$, $r$ and
$\chi_{\text{FF}}/\chi_{\text{M}}$.

Fig. 3: Results from computer simulations performed for a bead concentration
of 38.2 %. Panel (a): Dipole energy per bead plotted versus bead ratio and
relative susceptibility. The white line indicates the region of lowest energy
and the symbols mark lowest energies for square ($r=1:1$), honeycomb ($r=1:2$)
and kagome ($r=1:3$) lattice. Panels (b), (c) and (d) represent the order
parameter for percolation, the coordination of individual beads, quantified by
the bond order parameter, as well as the most prominent symmetry,
respectively. The red squares indicate parameters for which experimental data
is available.

##  4 Discussion

Fig. 3(a) depicts the dipole energy per bead plotted as a color map over the
bead ratio and relative susceptibility, for a bead density of 38.2%. This
density was chosen as it is close to the critical concentration for
percolation as explained later. Negative energies are regions in which the
particles have a tendency to form clusters, while in the areas of positive
dipole energies, they are isolated. The minimization of dipole energy results
from competing attractive and repulsive interactions. Beads of identical
magnetic susceptibility experience a repulsive force and the distance between
them maximises to minimise the free energy. At the same time, magnetic and
non-magnetic beads attract each other, compensating their collective moment
and form an in-plane dipole giving rise to an anisotropic short-ranged force
field in the plane (decaying faster than $r^{-4}$). The region of lowest
energy is indicated by the white line and the white symbols denote the local
minimum energy configuration of the beads, which arrange in square, honeycomb
and kagome lattices for bead ratios $r$ of 1:1, 1:2 and 1:3, respectively. The
coordination number of the beads is shown in Fig. 3(c). In a chain each bead
has two and for hexagonal packing six neighbors. For crystallisation or
percolation an average coordination number of at least two is required and
open networks may preferentially form for coordination numbers around three. A
clear correlation is seen, between larger coordination numbers and low dipole
energies per particle, being in line with the formation of large clusters for
low dipole energies.

To analyse the coordination of individual beads in more detail, Fig. 3(d)
shows the symmetry around beads. Blue, green and red colors indicate regions
in which predominantly 6-fold, 5-fold and 4-fold symmetry is found,
respectively. The intensity of the color represents how often the respective
symmetry is found and quantified by the bond order parameter 45 for a $s$-fold
symmetry, defined as $\phi_{j}=\frac{1}{n}\sum\exp(s\cdot i\cdot\theta_{k})$,
for each bead $j$ having 3 or more neighbors, where $\theta_{k}$ are the
angles of the connecting lines to direct neighbors, with respect to a
reference vector. For beads with less than 3 neighbors, the parameter is zero
($\phi_{j}=0$). The average over all beads within one image is
$\Phi_{s}=<|\phi_{j}|>$ and is presented in the colormap. For the apparent
moments of the beads being almost equal but of opposite direction four fold
symmetries are found. For highly asymmetric moments hexagonal packing is
dominant. Interestingly the symmetry is almost independent of the bead ratio,
as individual beads, which are left over, remain isolated. This relates well
to the fact that large bond order parameters are found in regions of low
average dipole moments. Another interesting observation is the five fold
symmetry found in the intermediate region. This symmetry hinders the formation
of large crystals and should promote the formation of open networks and
percolated structures. Fig. 3(b) depicts the percolation plotted as a map with
respect to the bead ratio and relative susceptibility. To extract a
percolation order parameter the average cluster size is weighted by the number
of beads in each cluster, to become statistically more robust and is
normalized to the total number of beads. This quantity can be used as order
parameter and varies between zero (isolated beads) and one (all beads
connected). Clearly, highly asymmetric bead ratios do not form percolated
structures, which are predominantly found for bead ratios of 1:1 and 1:2.

Fig. 3 presents results for a bead density of 38.2% but data has been
evaluated for bead densities between 12.7% and 50.9%. Fig. 4 depicts the
percolation order parameter plotted on a grey-scale versus bead density and
interaction, for ratios of 1:1 (panel a) and 1:2 (panel b). The figure was
created from simulations. Regions of predominantly hexagonal and cubic
symmetry are identified for bond order parameters $\Phi_{6}$ and $\Phi_{4}$
larger than 0.4, indicated by the blue and red color respectively. Fig. 4(c)
depicts simulation images extracted for $\chi_{\text{FF}}/\chi_{\text{M}}=0.5$
at three densities, indicated by the purple circles in Fig. 4(a). For low
densities, clusters and/or chains form but do not connect to each other, as
their mass is large and their total moment compensated. At higher densities
crystallites form and become connected. Fig. 4(d) depicts simulation images
extracted for a density of 38.2 % and three values of
$\chi_{\text{FF}}/\chi_{\text{M}}$ indicated by the green bars in Fig. 4(b).
It turns out that in the intermediate region, where neither cubic nor
hexagonal symmetries dominate, open percolated structures form, promoted by
the large defect density (centre panel, Fig. 4(d)). The transition to
percolated structures with respect to density is relatively sharp for all
interaction parameters (Fig. 4(a) and (b)), allowing the extraction of the
critical density for percolation, which is plotted versus
$\chi_{\text{FF}}/\chi_{\text{M}}$ in Fig. 5. Bead ratios of 1:1, 1:2 and 1:3
are marked by purple red and green color, respectively.

Fig. 4: The percolated, hexagonal and square phases plotted over interaction
and density for ratios $r=1:1$ (a) and r=1:2 (b). (c) The transition from
isolated beads to percolated with increasing bead density for $r=1:1$. (d) The
transition from square to hexagonal configuration with varying interaction for
$r=1:2$.

The critical density for percolation has been calculated for triangles,
squares, honeycomb and kagome lattices in two dimensions 38 and is in all
cases close to 45%. For a bead ratio of 1:1 we find a lower value of the
critical density for percolation, of about 30%, for
$\chi_{\text{FF}}/\chi_{\text{M}}=0.5$ (top right panel, Fig. 5). Here the
interaction between the two species of beads is attractive and one type acts
as glue for the other. The fact that the lowest critical density for
percolation is found for values of $\chi_{\text{FF}}/\chi_{\text{M}}<0.5$ may
be related to crystal tilling effects. At
$\chi_{\text{FF}}/\chi_{\text{m}}=0.5$ large cubic ($\rho\approx 79$%)
crystals form leading to larger critical densities for percolation, as it
critically depends on the links between crystals. At small values of
$\chi_{\text{FF}}/\chi_{\text{M}}$, the critical density for percolation
becomes large ($>60\%$), as the repulsion between magnetic beads is
dominating. A qualitative similar behaviour is found for a bead ratio of 1:2,
however, with the lowest value of the critical density for percolation found
at lower $\chi_{\text{FF}}/\chi_{\text{M}}$. For bead ratios of 1:3
percolation is only found for densities larger than 50%. The strong repulsion
between the magnetic beads requires three non-magnetic beads to compensate,
favouring hexagonal dense packed ($\rho>90\%$) arrangements.

Fig. 5: Critical densities for percolation plotted versus interaction of
magnetic and non-magnetic beads for bead ratios of 1:1, 1:2 and 1:3.

##  5 Conclusion

In conclusion, we presented a statistical approach in the analysis of
microscopy images and computer simulations, for extracting information on the
self-assembly in a two dimensional binary colloidal dispersion with tunable
interactions. Magnetic and non-magnetic beads are dissolved in a ferrofluid
and investigated in an out of plane magnetic field. Depending on the
concentration of magnetic nano-particles in the matrix the interaction between
the two types of beads is repulsive or attractive. We find a low critical
density for percolation, for attractive forces between the beads and bead
ratios approximately equal to one, indicating formation of extended and open
networks. Our results are of high relevance for a range of research and
technological fields, spanning across physics, chemistry, materials science,
biology, epidemics and even large-scale integration of nano-electronic devices
46. Material systems with controllable interactions, like the one presented
here, can serve as an excellent model system as they allow for simple imaging
of their microstates, providing statistically relevant information on the
self-assembly and formation of percolating structures.

## Author Contributions

MW, VK and HC together developed the conceptualization and methodology of the
project. The investigations and formal analysis were done by HC and AK. HC
also developed the software, validated and visualised the results. The project
was supervised by MW and VK, who also acquired the funding and administered
the project. The original draft was written by HC and then edited by MW and VK
and reviewed by all authors.

## Conflicts of interest

There are no conflicts to declare.

## Acknowledgements

We thank Niklas Johansson and Anders Olsson, for constructing parts of the
experimental setup. We acknowledge financial support from STINT (contract
number: IG2011-2067), Swedish research council (contract number: A0505501),
the Carl Tryggers Stiftelse (Contract number: CT 13:513) as well as ABB group.

## Notes and references

  * Whitesides and Grzybowski 2002 G. M. Whitesides and B. Grzybowski, _Science_ , 2002, 295, 2418\.
  * Whitesides and Boncheva 2002 G. M. Whitesides and M. Boncheva, _PNAS_ , 2002, 99, 4769.
  * Klokkenburg _et al._ 2006 M. Klokkenburg, R. P. Dullens, W. K. Kegel, B. H. Erné and A. P. Philipse, _Phys. Rev. Lett._ , 2006, 96, 037203.
  * Qiu _et al._ 2007 D. Qiu, T. Cosgrove and A. M. Howe, _Langmuir_ , 2007, 23, 475–481.
  * Cademartiri _et al._ 2012 R. Cademartiri, C. A. Stan, V. M. Tran, E. Wu, L. Friar, D. Vulis, L. W. Clark, S. Tricard and G. M. Whitesides, _Soft Matter_ , 2012, 8, 9771–9791.
  * Demirörs _et al._ 2010 A. F. Demirörs, P. M. Johnson, C. M. van Kats, A. van Blaaderen and A. Imhof, _Langmuir_ , 2010, 26, 14466–14471.
  * Kitaev and Ozin 2003 V. Kitaev and G. A. Ozin, _Adv. Mater._ , 2003, 15, 75–78.
  * Du _et al._ 2013 D. Du, D. Li, M. Thakur and S. L. Biswal, _Soft Matter_ , 2013, 9, 6867–6875.
  * Kantorovich _et al._ 2008 S. Kantorovich, J. J. Cerda and C. Holm, _Phys. Chem. Chem. Phys._ , 2008, 10, 1883.
  * Butter _et al._ 2003 K. Butter, P. H. H. Bomans, P. M. Frederik, G. J. Vroege and A. P. Philipse, _Nature materials_ , 2003, 2, 88.
  * Weis and Levesque 1993 J. J. Weis and D. Levesque, _Phys. Rev. Lett._ , 1993, 71, 2729–2732.
  * Kantorovich _et al._ 2015 S. Kantorovich, A. O. Ivanov, L. Rovigatti, J. M. Tavares and F. Sciortinoe, _Phys. Chem. Chem. Phys._ , 2015, 17, 16601.
  * Wen _et al._ 1999 W. Wen, F. Kun, K. F. Pál, D. W. Zheng and K. N. Tu, _Phys. Rev. E_ , 1999, 59, R4758–R4761.
  * Stambaugh _et al._ 2003 J. Stambaugh, D. P. Lathrop, E. Ott and W. Losert, _Phys. Rev. E_ , 2003, 68, 026207.
  * Stambaugh _et al._ 2004 J. Stambaugh, Z. Smith, E. Ott and W. Losert, _Phys. Rev. E_ , 2004, 70, 031304.
  * Blair and Kudrolli 2003 D. L. Blair and A. Kudrolli, _Phys. Rev. E_ , 2003, 67, 021302\.
  * Kr"ogel _et al._ 2018 A. Kr"ogel, P. A. Sanchez, R. Maretzki, T. Dumont, E. S. Pyanzina, S. S. Kantorovich and R. Richter, _Soft Matter_ , 2018, 14, 1001.
  * Pham _et al._ 2017 A. T. Pham, Y. Zhuang, P. Detwiler, J. E. S. Socolar, P. Charbonneau and B. B. Yellen, _Phys. Rev. E_ , 2017, 95, 052607.
  * Alert _et al._ 2014 R. Alert, J. Casademunt and P. Tierno, _Phys. Rev. Lett._ , 2014, 113, 198301.
  * Straube and Tierno 2014 A. V. Straube and P. Tierno, _Soft Matter_ , 2014, 10, 3915–3925.
  * Snezhko _et al._ 2009 A. Snezhko, M. Belkin, I. Aranson and W. Kwok, _Phys. Rev. Lett._ , 2009, 102, 118103.
  * Erb _et al._ 2009 R. Erb, H. Son, B. Samanta, V. Rotello and B. Yellen, _Nature_ , 2009, 457, 999–1002.
  * Khalil _et al._ 2012 K. Khalil, A. Sagastegui, Y. Li, M. Tahir, J. Socolar, B. Wiley and B. Yellen, _Nat. Commun._ , 2012, 3, 794.
  * Carstensen _et al._ 2015 H. Carstensen, V. Kapaklis and M. Wolff, _Phys. Rev. E_ , 2015, 92, 012303.
  * Rosensweig _et al._ 2008 R. Rosensweig, Y. Hirota, S. Tsuda and K. Raj, _Journal of Physics: Condensed Matter_ , 2008, 20, 204147.
  * He _et al._ 2010 L. He, Y. Hu, H. Kim, J. Ge, S. Kwon and Y. Yin, _Nano Lett._ , 2010, 10, 4708–4714.
  * He _et al._ 2012 L. He, M. Wang, J. Ge and Y. Yin, _Acc. Chem. Res._ , 2012, 45, 1431–1440.
  * Saado _et al._ 2002 Y. Saado, M. Golosovsky, D. Davidov and A. Frenkel, _Phys. Rev. B_ , 2002, 66, 195108.
  * Fan _et al._ 2013 F. Fan, S. Chen, W. Lin, Y.-P. Miao, S.-J. Chang, B. Liu, X.-H. Wang and L. Lin, _Appl. Phys. Lett._ , 2013, 103, 161115.
  * Nguyen and Choi 2009 Q.-H. Nguyen and S.-B. Choi, _Smart Mater. Struct._ , 2009, 18, 035012\.
  * Park _et al._ 2010 B. J. Park, F. F. Fang and H. J. Choi, _Soft Matter_ , 2010, 6, 5246–5253.
  * Wang and Liao 2011 D. Wang and W. Liao, _Smart Mater. Struct._ , 2011, 20, 023001\.
  * O’Hern _et al._ 2003 C. S. O’Hern, L. E. Silbert, A. J. Liu and S. R. Nagel, _Phys. Rev. E_ , 2003, 68, 011306.
  * Trappe _et al._ 2001 V. Trappe, V. Prasad, L. Cipelletti, P. N. Segre and D. A. Weitz, _Nature_ , 2001, 411, 772.
  * Drocco _et al._ 2005 J. A. Drocco, M. B. Hastings, C. J. O. Reichhardt and C. Reichhardt, _Phys. Rev. Lett._ , 2005, 95, 088001.
  * Koeze and Tighe 2018 D. J. Koeze and B. P. Tighe, _Phys. Rev. Lett._ , 2018, 121, 188002\.
  * Achlioptas _et al._ 2009 D. Achlioptas, R. M. D’Souza and J. Spencer, _Science_ , 2009, 323, 1453.
  * Scher and Zallen 1970 H. Scher and R. Zallen, _J. Chem. Phys._ , 1970, 53, 3759.
  * Valadez-Pérez _et al._ 2013 N. Valadez-Pérez, R. Castañeda-Priego and Y. Liu, _RSC Advances_ , 2013, 3, 25110.
  * Skjeltorp 1984 A. Skjeltorp, _Physica B+C_ , 1984, 127, 411–416.
  * Carstensen _et al._ 2018 H. Carstensen, V. Kapaklis and M. Wolff, _The European Physical Journal E_ , 2018, 41, 9.
  * Carstensen 2018 H. Carstensen, _PhD thesis_ , Uppsala University, 2018.
  * Yang _et al._ 2013 Y. Yang, L. Gao, G. P. Lopez and B. B. Yellen, _ACS Nano_ , 2013, 7, 2705–2716.
  * Meeker 2021 D. Meeker, _Finite Element Method Magnetics (FEMM)_ , http://www.femm.info/wiki/HomePage, 2021.
  * Pham _et al._ 2016 A. T. Pham, R. Seto, J. Schönke, D. Y. Joh, A. Chilkoti, E. Fried and B. B. Yellen, _Soft Matter_ , 2016, 12, 7735–7746.
  * Grimmett 1989 G. Grimmett, _Percolation_ , Springer-Verlag New York, 1989.


# Characterization of Incentive Compatibility of an Ex-Ante Constrained Player

Bonan Ni, Pingzhong Tang

###### Abstract

We consider a variant of the standard Bayesian mechanism, where players
evaluate their outcomes and constraints in an ex-ante manner. Such a model
captures a major form of modern online advertising where an advertiser is
concerned with her/his expected utility over a time period and her/his type
may change over time. We are interested in the incentive compatibility (IC)
problem of such Bayesian mechanism. Under very mild conditions on the
mechanism environments, we give a full characterization of IC via the taxation
principle and show, perhaps surprisingly, that such IC mechanisms are fully
characterized by the so-called auto-bidding mechanisms, which are pervasively
fielded in the online advertising industry.

##  1 Introduction

In online advertisement industry, where a publisher sells advertisement slots
to some advertisers, it is typical for each advertiser to have her own account
which records her remaining budget, the amount of advertisement slots
allocated so far and possibly the amount of conversions generated through her
advertisements. Slot auctions happen at almost the same frequency as user
requests, which makes it almost impossible (and indeed unnecessary) for
advertisers to evaluate utility of each auction separately. As a result, in
industry, certain kinds of contracts are signed between the platform and the
advertiser to guarantee overall allocation and payment over a relatively long
time period, typically one day or one week. For example, one popular form of
contract is to limit the total amount of money spent on advertising, which is
called budget constraint in the related literature. Another popular contract
form limits the return-over-investment ratio (ROI), and examples of this form
include Google’s target CPA bidding and Facebook’s cost cap.

In the probability space consisting of all auction events over the given time
period, the constraints imposed by such contracts are expressed in an ex-ante
manner. That is, satisfaction of the constraint is evaluated by taking the
expectation over the whole probability space. Most constraints in classic
mechanism design literature, however, are interim constraints, which are
separately evaluated for each possible type of each player. When an ex-ante
constraint on overall expectation is binding, it is possible for the player to
design more complicated misreport strategy: instead of separately maximizing
the utility for each of her own type, the player can make contingent plans
about the type report over her whole type space, so that her constraint
remains satisfied, but her utility is overall better off than always reporting
truthfully. Such possibility poses new challenges to the design of incentive
compatible mechanisms.

In this paper, we analyze the general mechanism design problem with an ex-ante
constraint on the outcome and payment, which is not limited to the design of
single-item auctions. From a fixed player’s perspective, the mechanism is
abstracted into a pair of interim rules (but with ex-ante utility model and
constraints), and we characterize interim rules of any incentive compatible
mechanism. Our first characterization in Section 4 states that, it is without
loss of generality to use the following implementation of incentive compatible
mechanism: the designer maximizes some new value-minus-payment utility on
behalf of the player for every type realization of the mechanism, where the
new value is defined by linearly combining a utility term and a constraint
term using some factors that are fixed across all type realization of the
mechanism. For example, when the player is a value maximizer with budget
constraint, it suffices to determine factors $(\alpha,\beta)$ and maximize
$\alpha$ times value minus $\beta$ times payment. This characterization
justifies the auto-bidding technique in online advertising, where an
advertiser’s evaluations for the advertisement slot’s value and contribution
to constraint are combined linearly to give input to an auction. Our second
characterization, given in Section 6, shows that incentive compatibility can
be characterized using a multi-dimensional payment identity, and the new
payment identity differs from the one in classic quasi-linear mechanism design
literature (Myerson 1981; Manelli and Vincent 2007) only by linearly combining
the utility and constraint terms.

##  2 Related works

Many recent works study the the mechanism design problems for players with
various ex-ante constraints, typically under the context of online
advertisement auction. Unlike the widely used constraint of individual
rationality which is separately evaluated for every possible type of the
player (interim IR) (Ashlagi, Daskalakis, and Haghpanah 2016) or every profile
of all players’ types (ex-post IR) (Ashlagi, Daskalakis, and Haghpanah 2019),
an ex-ante constraint is evaluated by taking expectation over the whole game’s
probability space. Two of the most widely discussed ex-ante constraints are
budget constraint (Chen, Kroer, and Kumar 2021; Zhou, Chakrabarty, and Lukose
2008), which is to limit the overall expectation of payment (the term ‘budget
constraint’ is also used for interim or ex-post constraint on payment (Burkett
2016), and the budget level can be private (Che and Gale 1998), but in this
paper we focus on an ex-ante constraint known to the designer), and ROI
constraint, which is to limit the ratio given by the player’s expected utility
over her expected payment (Balseiro et al. 2021; Golrezaei, Lobel, and Paes
Leme 2021; Heymann 2019). Given the constraint, the player seeks to maximize
her utility without violating the constraint. In many works the player’s
utility is still given by the standard quasi-linear utility, which is the
value she wins from the outcome minus payment. Another player model which
becomes increasingly popular assumes that the player’s utility is just the
value she wins, and the trade-off between value and payment is completely
controlled by the ex-ante constraint (Babaioff et al. 2021). This model plus a
budget constraint resembles the classic model of Fisher’s market (Brainard and
Scarf 2005), where the player maximizes the value of items she wins, under the
constraint that the money spent on the items does not exceed a given limit.

To solve the mechanism design problem with ex-ante constrained players, the
technique called auto-bidding is widely proposed (Balseiro et al. 2021;
Aggarwal, Badanidiyuru, and Mehta 2019; Deng et al. 2021; Wen et al. 2021; Li
et al. 2020). Typically, the mechanism is implemented by running an auction
which repeatedly asks for a single bid from the player, and decide allocation
and payment according to the bid. Auto-bidding repeatedly decides the bid on
behalf of the player, so that the total utility over multiple rounds is
maximized without violating the constraint. An important result is that, under
certain settings, the optimal bidding rule is to always linearly combine the
current item’s contribution to utility and contribution to the constraint
using some factors that are fixed across all rounds. Many previous works
obtain this result under different restrictions: (Aggarwal, Badanidiyuru, and
Mehta 2019) assumes finite rounds of game and a posted price auction, and
(Balseiro et al. 2021; Babaioff et al. 2021) assumes specific forms of the
player’s utility and the ex-ante constraint. Some other works capture the
sequential revelation of players’ types, and design dynamic mechanisms or
control strategies that achieve low regret over multiple rounds (Golrezaei et
al. 2021; Balseiro and Gur 2019).

Another literature investigates the technique called pacing. Pacing can be
similarly seen as certain control technique deciding input to a repeated
auction, but its goal is often to smooth the usage of the player’s budget over
a certain time period (Agarwal et al. 2014). Smoothing the budget usage does
not necessarily involve the maximization of the player’s utility, which makes
it less natural to define the corresponding incentive compatibility problem.
However, some works define pacing as trying to use up the budget by uniformly
scaling the bid (Conitzer et al. 2018; Balseiro et al. 2017), which actually
maximizes the player’s utility given some certain player models.

##  3 Model

To study the incentive compatibility of the mechanism, we focus our attention
to an arbitrarily chosen player and analyze the incentive problems from her
own perspective, without concerning any component of the mechanism that does
not affect the chosen player’s action. Methodologically, all analysis in the
paper considers the mechanism’s interim rules with respect to a single fixed
player. When there are multiple players, all the results in this paper can be
applied to each of them, so that each player has her corresponding incentive
compatibility characterization about her interim rules.

Denote by $V\subseteq\mathbb{R}^{d}$ the player’s type space, by
$Q\subseteq\mathbb{R}^{D}$ the mechanism’s outcome space. When analyzing
incentive compatibility, it is without loss of generality to consider only
direct mechanisms, which take the player’s type report as the only input from
the player. Therefore, from the player’s perspective, we consider a pair of
interim rules $(x,p)$ as the mechanism’s abstraction, where $x:V\rightarrow Q$
denotes the mapping from type report to outcome, and
$p:V\rightarrow\mathbb{R}$ denotes the mapping from type report to expected
payment. The outcome space $Q$ are chosen so that both $x$ and $p$ are
deterministic functions: any possible lottery over outcomes must be encoded by
a corresponding single point in $Q$. For example, if we choose $Q=[0,1]^{2}$,
any possible lottery to allocate two items to the player can be encoded by a
single point in $Q$.

Denote by $\Delta V$ the set of Borel probability measures on $V$. The
player’s type distribution is given by some probability measure $\rho\in\Delta
V$. We say that a subset $E\subseteq V$ has positive measure if $\rho(E)>0$,
and a condition holds for almost every $v$ if every subset where the condition
fails does not have positive measure. Unless otherwise specified, all
expectations in this paper are taken with respect to $\rho$.

Denote by $s:V\rightarrow\Delta V$ a strategy the player can take. The player
model is given by the combination of a utility function and an ex-ante
constraint, and is encoded by tuple $(u,f,c_{1},c_{2},C)$. We assume that the
player is risk-neutral, so that the utility is also evaluated by taking ex-
ante expectation. The utility extracted from the outcome is given by function
$u:Q\times V\rightarrow\mathbb{R}$, and overall utility is given by the ex-
ante expectation of utility from outcome minus a constant $c_{1}\in\\{0,1\\}$
times payment. Given interim rules $(x,p)$ and report strategy $s$, the ex-
ante utility is given by

$U(x,p,s)\coloneqq\mathbb{E}_{v,v^{\prime}\sim
s(v)}[u(x(v^{\prime}),v)-c_{1}\cdot p(v^{\prime})].$ (1)

Note that for any $c_{1}>0$, we can rescale $u$ into $u^{\prime}=u/c_{1}$, so
that maximizing $\mathbb{E}[u(x(v^{\prime}),v)-c_{1}\cdot p(v^{\prime})]$ is
equivalent to maximizing
$\mathbb{E}[u^{\prime}(x(v^{\prime}),v)-p(v^{\prime})]$. Therefore, it is
without loss of generality to consider $c_{1}\in\\{0,1\\}$ instead of
$c_{1}\geq 0$.

The ex-ante constraint is decided by function $f:Q\times
V\rightarrow\mathbb{R}$, constant $c_{2}\in\\{0,1\\}$ and constant
$C\in\mathrm{R}$. The constraint is given by:

$\mathbb{E}_{v,v^{\prime}\sim s(v)}[f(x(v^{\prime}),v)-c_{2}\cdot
p(v^{\prime})]\geq C.$ (2)

And we say that the ex-ante constraint is binding when reporting truthfully,
if

$\mathbb{E}_{v}[f(x(v),v)-c_{2}\cdot p(v)]=C$

Throughout this paper, we only analyze strategy $s$ for which the expectation
in equation (1) and (2) exist. In fact, it is sufficient to consider
strategies which are some random lotteries over a finite number of
deterministic report rules $h:V\rightarrow V$, with each $h$ being measurable.

An ex-ante constraint can be thought of as a contract between the mechanism
designer and the player, so that even without any prior distributional
knowledge, the player is convinced that the overall outcome and payment are
under some specific control. Our definition of incentive compatibility
requires that the constraint is always satisfied by truth-telling, therefore
an alternative interpretation is that when violating the constraint, the
player’s utility is $-\infty$. This player model covers a wide range of buyer
models in online advertising and auto-bidding literature, including:

  * •

Value maximizer with ROI constraint: letting
$c_{1}=0,f=u/(1+\gamma),c_{2}=1,C=0$, where $\gamma$ is the lowest acceptable
ROI for the buyer.

  * •

Utility maximizer with budget constraint: letting $c=1,f=0$, $c_{2}=1$, and
$-C$ be the buyer’s budget limit.

Also, the model naturally covers the buyer of a multi-item auction. With $D$
equal to the number of items and $d=2^{D}$, we can use each dimension of $V$
to represent the player’s valuation for a subset of the items, and each
dimension of $Q$ to represent the allocation probability of an item.

We make the following technical assumptions on $V$, $Q$, functions of the
player model $u,f$, and the interim rules $(x,p)$.

######  Assumption 1.

$V$ is a compact subset of $\mathbb{R}^{d}$, and $Q$ is a compact subset of
$\mathbb{R}^{D}$. $u,f,x,p$ are all continuous.

By assuming compact $V,Q$ and continuous $u,f,x,p$, we make the values of
$u,f,p$ bounded.

We focus on deriving characterizations of the mechanism’s incentive
compatibility. The incentive compatibility for the player with ex-ante
constraint is defined as follows:

######  Definition 1.

An interim rule pair $(x,p)$ is incentive compatible, if

$\mathbb{E}_{v}[f(x(v),v)-c_{2}\cdot p(v)]\geq C,$

AND, for any strategy $s:V\rightarrow\Delta V$ s.t. the expectations
$U(x,p,s)$ and $\mathbb{E}_{v,v^{\prime}\sim
s(v)}[f(x(v^{\prime}),v)-c_{2}\cdot p(v^{\prime})]$ exist, at least one of the
following two inequalities hold:

  1. 1.

$\mathbb{E}_{v}[u(x(v),v)-c_{1}\cdot p(v)]\geq U(x,p,s)$.

  2. 2.

$\mathbb{E}_{v,v^{\prime}\sim s(v)}[f(x(v^{\prime}),v)-c_{2}\cdot
p(v^{\prime})]<C$.

As explained in the beginning of the section, we abstract the mechanism into a
pair of interim rules $(x,p)$. For incentive compatible interim rule pair
$(x,p)$, reporting truthfully does not violate the ex-ante constraint, and
maximizes utility among all report strategies that does not violate the
constraint.

##  4 Auto-bidding and taxation principle

Following the idea of taxation principle, we give our first characterization
of incentive compatibility. Denote by $Q_{x}\subseteq Q$ the range of $x$. The
classic taxation principle tells that, incentive compatibility mechanisms can
be implemented by designing payment rule that is some mapping from $Q_{x}$ to
$\mathbb{R}$, and decide outcome by choosing the optimal outcome in $Q_{x}$ on
behalf of the player. Theorem 1 tells that, a similar implementation can be
used for player with an ex-ante constraint:

######  Theorem 1.

Under Assumption 1, interim rule pair $(x,p)$ is incentive compatible if and
only if at least one of the following two conditions holds:

  1. 1.

The ex-ante constraint is binding when reporting truthfully, and there exists
function $p_{x}:Q_{x}\rightarrow\mathbb{R}$ s.t. for almost every $v\in V$,

$p_{x}(x(v))=c_{2}\cdot p(v),$

and for almost every $v\in V$,

$x(v)\in\operatorname*{argmax}_{q\in Q_{x}}[f(q,v)-p_{x}(q)],$ (3)

and if there exists $v^{\prime}\neq v$ s.t.
$f(x(v),v)-p_{x}(x(v))=f(x(v^{\prime}),v)-p_{x}(x(v^{\prime}))$, then we have
$u(x(v),v)-c_{1}\cdot p(v)\geq u(x(v^{\prime}),v)-c_{1}\cdot p(v^{\prime})$.

  2. 2.

There exists constant $r\in\mathbb{R}_{\geq 0}$ and function
$p_{x}:Q_{x}\rightarrow\mathbb{R}$ s.t. for almost every $v\in V$,

$p_{x}(x(v))=(c_{1}+rc_{2})p(v),$

and for almost every $v\in V$,

$x(v)\in\operatorname*{argmax}_{q\in Q_{x}}[u(q,v)+r\cdot f(q,v)-p_{x}(q)],$
(4)

and if $r>0$, the ex-ante constraint is binding when reporting truthfully.

Theorem 1 can be seen as a generalization of the widely used auto-bidding
technique: the game runs by offering a price $p_{x}(q)$ for every possible
outcome $q\in Q_{x}$, and to report optimally on behalf of the player, the
controller either maximizes contribution to constraint per round
$[f(\cdot,v)-p_{x}(\cdot)]$, or maximizes a goal which is some fixed linear
combination of the utility and the contribution to constraint. We show in
Theorem 3 that, under some additional assumptions, the corresponding interim
rules are characterized by an equality similar to the multi-dimensional
version of standard payment identity, which generalizes the discovery in auto-
bidding literature, that the underlying auction mechanism should be truthful
for quasi-linear players.

To prove Theorem 1, we first provide some useful lemmas. For any $r\geq 0$,
define set $V^{+}(r)$ and $V^{-}(r)$ by

$\displaystyle V^{+}(r)\coloneqq$ $\displaystyle\big{\\{}v|v\in V,\exists
v^{\prime}\in V:$ $\displaystyle f(x(v^{\prime}),v)-c_{2}\cdot
p(v^{\prime})<f(x(v),v)-c_{2}\cdot p(v),$
$\displaystyle[u(x(v^{\prime}),v)-c_{1}\cdot
p(v^{\prime})]-[u(x(v),v)-c_{1}\cdot p(v)]$
$\displaystyle>-r\cdot[f(x(v^{\prime}),v)-c_{2}\cdot p(v^{\prime})]$
$\displaystyle+r\cdot[f(x(v),v)-c_{2}\cdot p(v)]\big{\\}}$ $\displaystyle
V^{-}(r)\coloneqq$ $\displaystyle\big{\\{}v|v\in V,\exists v^{\prime}\in V:$
$\displaystyle f(x(v^{\prime}),v)-c_{2}\cdot
p(v^{\prime})>f(x(v),v)-c_{2}\cdot p(v),$
$\displaystyle[u(x(v^{\prime}),v)-c_{1}\cdot
p(v^{\prime})]-[u(x(v),v)-c_{1}\cdot p(v)]$
$\displaystyle>-r\cdot[f(x(v^{\prime}),v)-c_{2}\cdot p(v^{\prime})]$
$\displaystyle+r\cdot[f(x(v),v)-c_{2}\cdot p(v)]\big{\\}}$

The following lemma tells that, such subsets of $V$ are measurable.

######  Lemma 1.

Under Assumption 1, for any $r\geq 0$, $V^{+}(r)$ and $V^{-}(r)$ are both
measurable.

###### Proof.

For any $r\geq 0$, we prove that $V^{+}(r)$ is open subset of $V$, and
similarly $V^{-}(r)$ is open subset of $V$, therefore both sets are
measurable.

By continuity of $x,p,f,u$, for any $v,v^{\prime}$ s.t.
$f(x(v^{\prime}),v)-c_{2}\cdot p(v^{\prime})<f(x(v),v)-c_{2}\cdot p(v)$ and
$[u(x(v^{\prime}),v)-c_{1}\cdot p(v^{\prime})]-[u(x(v),v)-c_{1}\cdot
p(v)]>-r\cdot[f(x(v^{\prime}),v)-c_{2}\cdot
p(v^{\prime})]+r\cdot[f(x(v),v)-c_{2}\cdot p(v)]$, there exists some
$\epsilon>0$ so that for any $v^{\prime\prime}\in V\cap B(v,\epsilon)$ where
$B(v,\epsilon)$ is the open ball centered at $v$ with radius $\epsilon$, we
have $f(x(v^{\prime}),v^{\prime\prime})-c_{2}\cdot
p(v^{\prime})<f(x(v^{\prime\prime}),v^{\prime\prime})-c_{2}\cdot
p(v^{\prime\prime})$ and $[u(x(v^{\prime}),v^{\prime\prime})-c_{1}\cdot
p(v^{\prime})]-[u(x(v^{\prime\prime}),v^{\prime\prime})-c_{1}\cdot
p(v^{\prime\prime})]>-r\cdot[f(x(v^{\prime}),v^{\prime\prime})-c_{2}\cdot
p(v^{\prime})]+r\cdot[f(x(v^{\prime\prime}),v^{\prime\prime})-c_{2}\cdot
p(v^{\prime\prime})]$. This gives $v^{\prime\prime}\in V^{+}(r)$, therefore
$V^{+}(r)$ is open subset of $V$. ∎

And the following lemma allows us to construct some measurable deterministic
deviation:

######  Lemma 2.

Under Assumption 1, for any $E\subseteq V$ with $\rho(E)>0$, for any $n>0$,
any $(\alpha_{1},\alpha_{2},\ldots,\alpha_{n})\in\mathbb{R}^{n}$ and
$(\beta_{1},\beta_{2},\ldots,\beta_{n})\in\mathbb{R}^{n}$, suppose for every
$v\in E$, there exists $v^{\prime}\in V$ s.t. for any $1\leq i\leq n$, we have
that

$\displaystyle\gamma_{i}(v,v^{\prime})\coloneqq$
$\displaystyle\alpha_{i}\cdot[u(x(v^{\prime}),v)-c_{1}\cdot p(v^{\prime})]$
$\displaystyle-$ $\displaystyle\alpha_{i}\cdot[u(x(v),v)-c_{1}\cdot p(v)]$
$\displaystyle+$ $\displaystyle\beta_{i}\cdot[f(x(v^{\prime}),v)-c_{2}\cdot
p(v^{\prime})]$ $\displaystyle-$
$\displaystyle\beta_{i}\cdot[f(x(v),v)-c_{2}\cdot p(v)]$

is positive, then there exists function $h:E\rightarrow V$ s.t. for any $1\leq
i\leq n$ and function $g_{i}(v)\coloneqq\gamma_{i}(v,h(v))$, the integration
$\int_{E}g_{i}d\rho$ exists and is positive.

###### Sketched proof.

$\rho(E)>0$ gives that, we can find some $\epsilon>0$ and some $E_{\epsilon}$
with $\rho(\epsilon)>0$, so that for any $v\in E$, there exists $v^{\prime}\in
V$ s.t. any $1\leq i\leq n$, we have $\gamma_{i}(v,v^{\prime})\geq\epsilon$.
By compactness of $V$, we can obtain that $V\setminus E_{\epsilon}$ is open in
$V$, therefore $E_{\epsilon}$ is closed in $V$.

For any $v\in E_{\epsilon}$ and any $1\leq i\leq n$, since $x,p,u,f$ are all
continuous, for every $v\in E_{\epsilon}$ we can find such an open set
$E_{v}\subseteq V$ that contains $v$: there exists some $v^{\prime}$ s.t. for
every $1\leq i\leq n$ and every $v^{\prime\prime}\in E_{v}$, we have
$\gamma_{i}(v^{\prime\prime},v^{\prime})>0$. The set

$\\{E_{v}|v\in E_{\epsilon}\\}$

is an open cover of $E_{\epsilon}$. Since $V$ is compact and $E_{\epsilon}$ is
closed in $V$, we can find some finite subcover of $E_{\epsilon}$. By
assigning each $v\in E_{\epsilon}$ to some element of the finite subcover, we
can define function $h:E_{\epsilon}\rightarrow V$ whose range is finite. For
$v\in E\setminus E_{\epsilon}$ we can simply make $h(v)=v$. This makes the
integration of $g_{i}$ exist for every $1\leq i\leq n$. ∎

Given the above two lemmas, we are able to prove the following lemma, which is
essential for our characterizations of incentive compatibility. In fact, the
lemma itself gives if and only if condition of incentive compatibility.

######  Lemma 3.

Under Assumption 1, the interim rule pair $(x,p)$ is incentive compatible, if
and only if $\mathbb{E}_{v}[f(x(v),v)-c_{2}\cdot p(v)]\geq C$, and at least
one of the following two conditions holds:

  1. 1.

The ex-ante constraint is binding when reporting truthfully, and for almost
every $v\in V$, for every $v^{\prime}\in V$, $f(x(v),v)-c_{2}\cdot p(v)\geq
f(x(v^{\prime}),v)-c_{2}\cdot p(v^{\prime})$, and if $f(x(v),v)-c_{2}\cdot
p(v)=f(x(v^{\prime}),v)-c_{2}\cdot p(v^{\prime})$, we have
$u(x(v),v)-c_{1}\cdot p(v)\geq u(x(v^{\prime}),v)-c_{1}\cdot p(v^{\prime})$.

  2. 2.

There exists $r\geq 0$ s.t. for almost every $v\in V$, for every
$v^{\prime}\in V$,

$\displaystyle[u(x(v^{\prime}),v)-c_{1}\cdot
p(v^{\prime})]-[u(x(v),v)-c_{1}\cdot p(v)]$ (5) $\displaystyle\leq$
$\displaystyle-r\cdot[f(x(v^{\prime}),v)-c_{2}\cdot p(v^{\prime})]$
$\displaystyle+r\cdot[f(x(v),v)-c_{2}\cdot p(v)],$

and if $r>0$, the ex-ante constraint is binding when reporting truthfully.

###### Proof.

Sufficiency: Suppose the first condition holds. A strategy $s$ obtains
strictly higher utility than reporting truthfully only if there exists some
$E\subseteq V$ with $\rho(E)>0$ s.t. for every $v\in E$, it reports some
$v^{\prime}\neq v$ with positive probability, and
$\mathbb{E}_{v}[u(x(v),v)-c_{1}\cdot
p(v)]<\mathbb{E}_{v}[u(x(v^{\prime}),v)-c_{1}\cdot p(v^{\prime})]$. However,
for almost every $v\in E$ and any such $v^{\prime}$ we have
$\mathbb{E}_{v}[f(x(v),v)-c_{2}\cdot
p(v)]<\mathbb{E}_{v}[f(x(v^{\prime}),v)-c_{2}\cdot p(v^{\prime})]$, which
means such a strategy $s$ violates the ex-ante constraint. Therefore, no
strategy $s$ gets higher utility than truthfully reporting without violating
the constraint.

Suppose the second condition holds. If $r=0$, reporting truthfully maximizes
ex-post utility $[u(x(\cdot),v)-c_{1}\cdot p(\cdot)]$ for any $v\in V$.
Therefore, every $s$ does not obtain higher expected utility than truthfully
reporting.

If $r>0$, suppose there exists strategy $s$ s.t. reporting according to $s$
does not violate the ex-ante constraint, but gives strictly higher utility
than reporting truthfully. This means, for any $r\geq 0$, we have

$\displaystyle\mathbb{E}_{v,v^{\prime}\sim s(v)}[u(x(v^{\prime}),v)-c_{1}\cdot
p(v^{\prime})]$ $\displaystyle>$
$\displaystyle\mathbb{E}_{v}[u(x(v),v)-c_{1}\cdot p(v)],$ $\displaystyle
r\cdot\mathbb{E}_{v,v^{\prime}\sim s(v)}[f(x(v^{\prime}),v)-c_{2}\cdot
p(v^{\prime})]$ $\displaystyle\leq$ $\displaystyle
r\cdot\mathbb{E}_{v}[f(x(v),v)-c_{2}\cdot p(v)]$

By subtraction between the equations and rearrangement of terms, we have:

$\displaystyle\mathbb{E}_{v,v^{\prime}\sim s(v)}[u(x(v^{\prime}),v)-c_{1}\cdot
p(v^{\prime})]$ $\displaystyle-\mathbb{E}_{v}[u(x(v),v)-c_{1}\cdot p(v)]$
$\displaystyle>$ $\displaystyle-r\cdot\mathbb{E}_{v,v^{\prime}\sim
s(v)}[f(x(v^{\prime}),v)-c_{2}\cdot p(v^{\prime})]$
$\displaystyle+r\cdot\mathbb{E}_{v}[f(x(v),v)-c_{2}\cdot p(v)]$

However, we have equation (5) for almost every $v\in V$ and every
$v^{\prime}$, which leads to contradiction. We conclude that such $s$ does not
exist, which means $(x,p)$ is incentive compatible.

Necessity: Suppose $(x,p)$ is incentive compatible, but both conditions in
Lemma 3 are violated.

If the ex-ante constraint is binding, violation of the first condition can be
further divided into 2 cases:

Case 1: There exists some $E\subseteq V$ with $\rho(E)>0$ s.t. for every $v\in
E$, there exists some $v^{\prime}\in V$ s.t. $f(x(v),v)-c_{2}\cdot
p(v)=f(x(v^{\prime}),v)-c_{2}\cdot p(v^{\prime})$, and $u(x(v),v)-c_{1}\cdot
p(v)<u(x(v^{\prime}),v)-c_{1}\cdot p(v^{\prime})$. Then, by Lemma 2 there
exists some strategy which misreports on $E$ and reports truthfully on
$V\setminus E$, which gives higher utility than reporting truthfully without
violating the ex-ante constraint, and this contradicts with incentive
compatibility.

Case 2: There exists some $E\subseteq V$ with $\rho(E)>0$ s.t. for every $v\in
E$, there exists some $v^{\prime}\in V$ with $f(x(v),v)-c_{2}\cdot
p(v)<f(x(v^{\prime}),v)-c_{2}\cdot p(v^{\prime})$. Note that for almost every
$v\in E$ and the corresponding $v^{\prime}$, we have $u(x(v),v)-c_{1}\cdot
p(v)\geq u(x(v^{\prime}),v)-c_{1}\cdot p(v^{\prime})$, otherwise there exists
some strategy which misreports on $F$, so that the utility is higher than
truthfully reporting, and the ex-ante constraint remains satisfied.

Since equation (5) does not hold for almost every $v\in V$ when $r=0$, there
exists some $F\subseteq V$ with $\rho(F)>0$ s.t. for every $v\in F$, there
exists some $v^{\prime}\in V$ with $u(x(v),v)-c_{1}\cdot
p(v)<u(x(v^{\prime}),v)-c_{1}\cdot p(v^{\prime})$. Similarly, for almost every
$v\in F$ and the corresponding $v^{\prime}$, we have $f(x(v),v)-c_{2}\cdot
p(v)>f(x(v^{\prime}),v)-c_{2}\cdot p(v^{\prime})$.

For any $r\geq 0$, define $\rho^{+}(r)$ and $\rho^{-}(r)$ by

$\displaystyle\rho^{+}(r)\coloneqq\rho(V^{+}(r)),$
$\displaystyle\rho^{-}(r)\coloneqq\rho(V^{-}(r)).$

Note that $\rho^{-}$ is non-decreasing in $r$, while $\rho^{+}$ is non-
increasing in $r$. Moreover, the existence of $F$ gives $\rho^{+}(0)>0$, and
the existence of $E$ gives $\rho^{-}(r)>0$ for some sufficiently large $r$. If
for any $r\geq 0$ we have $\rho^{+}>0$, then there exists $r^{*}$ s.t.
$\rho^{+}(r^{*})>0,\rho^{-}(r^{*})>0$.

If there exists $r$ s.t. $\rho^{+}(r)=0$, define

$r_{0}\coloneqq\inf\\{r|\rho^{+}(r)=0\\}.$

Note that we have $\rho^{+}(r_{0})=0$. Suppose we have $\rho^{+}(r_{0})>0$,
then for sequence $(r_{i})_{i\geq 1}$ given by $r_{i}=r_{0}-2^{-i}$, we have
$V^{+}(r_{1})\subseteq V^{+}(r_{2})\subseteq\cdots$ and $\cup_{i\geq
1}V^{+}(r_{i})=V^{+}(r_{0})$, therefore
$\lim_{i\to\infty}\rho^{+}(r_{i})=\rho^{+}(r_{0})>0$, and there exists $i>0$
s.t. $\rho^{+}(r_{0}-2^{-i})>0$, which contradicts with the definition of
$r_{0}$. Suppose $\rho^{-}(r_{0})=0$, then equation (5) holds for almost every
$v\in V$ given $r=r_{0}$, thus the second condition is satisfied. Otherwise,
$\rho^{-}(r_{0})>0$ implies the existence of some $r^{*}<r_{0}$ s.t.
$\rho^{+}(r^{*})>0,\rho^{-}(r^{*})>0$.

Therefore, if both conditions are not satisfied, we can get $r^{*}$ with
$\rho^{+}(r^{*})>0,\rho^{-}(r^{*})>0$. Define $F_{1}\coloneqq V^{+}(r^{*})$
and $F_{2}\coloneqq V^{-}(r^{*})$, both with positive measure, and there
exists functions $h_{1}:F_{1}\rightarrow V$, $h_{2}:F_{2}\rightarrow V$ s.t.
by Lemma 2, for changes in utilities and LHS of ex-ante constraint defined as

$\displaystyle\Delta U_{1}=$ $\displaystyle\mathbb{E}_{v\in
F_{1}}[u(x(h_{1}(v)),v)-c_{1}\cdot p(h_{1}(v))]$
$\displaystyle-\mathbb{E}_{v\in F_{1}}[u(x(v),v)-c_{1}\cdot p(v)],$
$\displaystyle\Delta U_{2}=$ $\displaystyle\mathbb{E}_{v\in
F_{2}}[u(x(h_{2}(v)),v)-c_{1}\cdot p(h_{2}(v))]$
$\displaystyle-\mathbb{E}_{v\in F_{2}}[u(x(v),v)-c_{1}\cdot p(v)],$
$\displaystyle\Delta C_{1}=$ $\displaystyle\mathbb{E}_{v\in
F_{1}}[f(x(h_{1}(v)),v)-c_{2}\cdot p(h_{1}(v))]$
$\displaystyle-\mathbb{E}_{v\in F_{1}}[f(x(v),v)-c_{2}\cdot p(v)],$
$\displaystyle\Delta C_{2}=$ $\displaystyle\mathbb{E}_{v\in
F_{2}}[f(x(h_{2}(v)),v)-c_{2}\cdot p(h_{2}(v))]$
$\displaystyle-\mathbb{E}_{v\in F_{2}}[f(x(v),v)-c_{2}\cdot p(v)],$

we have $\Delta U_{1}>0,\Delta C_{2}>0$, and $\Delta U_{1}+r^{*}\cdot\Delta
C_{1}>0,\Delta U_{2}+r^{*}\cdot\Delta C_{2}>0$. If $\Delta C_{1}\geq 0$, then
directly applying $h_{1}$ on $F_{1}$ contradicts with incentive compatibility.
Otherwise, for $0<\mu_{1}<\mu_{2}\ll 1$ s.t. $\mu_{1}\Delta
C_{1}+\mu_{2}\Delta C_{2}=0$, the change in expected utility by reporting
according to $h_{1}$ w.p. $\mu_{1}$ on $F_{1}$, according to $h_{2}$ w.p.
$\mu_{2}$ on $F_{2}$, and otherwise truthfully is given by

$\displaystyle\mu_{1}\Delta U_{1}+\mu_{2}\Delta U_{2}$ $\displaystyle>$
$\displaystyle-\mu_{1}r_{0}\cdot\Delta C_{1}-\mu_{2}r_{0}\cdot\Delta C_{2}$
$\displaystyle=$ $\displaystyle 0.$

This contradicts with incentive compatibility. ∎

Given Lemma 1 \- 3, the proof of Theorem 1 is quite straightforward:

###### Proof of Theorem 1.

In fact, each of the two conditions in the theorem is equivalent to a
corresponding condition in Lemma 3. We only give proof for equivalence of the
second condition, because equivalence of the first condition is almost
identical in shape and idea with the standard taxation principle in quasi-
linear player case.

Suppose the second condition of the theorem holds. Then, for almost every
$v\in V$, equation (5) is naturally satisfied for all $v^{\prime}\in V$, and
we have $r>0$ only if the ex-ante constraint is binding. By Lemma 3, $(x,p)$
is incentive compatible. This proves sufficiency of the condition.

Suppose $(x,p)$ is incentive compatible by satisfying the second condition of
Lemma 3. Then, for almost every $v$, for every $v^{\prime}$ s.t.
$x(v^{\prime})=x(v)$, (5) gives

$(c_{1}+rc_{2})\cdot p(v^{\prime})\geq(c_{1}+rc_{2})\cdot p(v).$

Consider $p_{x}$ defined by:

$p_{x}(q)\coloneqq\inf_{v:x(v)=q}(c_{1}+rc_{2})p(v)$

Then, for almost every $v\in V$, we have $(c_{1}+rc_{2})p(v)\leq p_{x}(x(v))$.
By definition of infimum, for almost every $v\in V$, we have
$p_{x}(x(v))=(c_{1}+rc_{2})p(v)$. With such a $p_{x}$, inequality (5) implies
equation (4) for almost every $v\in V$, which finishes our proof. ∎

##  5 Differential properties of incentive compatible mechanisms

For the rest of this paper, we make the following assumption on $\rho$:

######  Assumption 2.

The boundary of $V$ has zero probability, that is, $\rho(\partial V)=0$.

Therefore, when taking any expectation over $V$ with respect to $\rho$, it
suffices to consider only $\mathring{V}$, the interior of $V$. Note that the
assumption implies that $\mathring{V}\neq\emptyset$.

And we make the following assumptions, that the terms in the player’s utility
and constraint are all differentiable:

######  Assumption 3.

For every $v\in\mathring{V}$, the single variable functions
$u(x(\cdot),v),f(x(\cdot),v)$ and $p(\cdot)$ are differentiable at $v$.

Therefore, we can define the vector-valued functions $\hat{u}$ and $\hat{f}$
by

$\hat{u}(v)\coloneqq\nabla_{v^{\prime}}[u(x(v^{\prime}),v)-c_{1}\cdot
p(v^{\prime})]|_{v^{\prime}=v},\ \ \forall v\in\mathring{V}$

and

$\hat{f}(v)\coloneqq\nabla_{v^{\prime}}[f(x(v^{\prime}),v)-c_{2}\cdot
p(v^{\prime})]|_{v^{\prime}=v},\ \ \forall v\in\mathring{V}.$

The following theorem gives necessary condition of incentive compatibility in
terms of the mechanism’s differential properties:

######  Theorem 2.

Under Assumption 1, 2 and 3, the interim rule pair $(x,p)$ is incentive
compatible only if at least one of the following two conditions hold:

  1. 1.

The ex-ante constraint is binding when reporting truthfully, and for almost
every $v\in\mathring{V}$, $\hat{f}(v)=\mathbf{0}$.

  2. 2.

There exists constant $r\in\mathbb{R}_{\geq 0}$ s.t. for almost every
$v\in\mathring{V}$, $\hat{u}(v)+r\cdot\hat{f}(v)=0$, and if $r>0$, the ex-ante
constraint is binding when reporting truthfully.

To prove Theorem 2, we first state the following useful lemma.

######  Lemma 4.

Given bivariate function $g:V\times V\rightarrow\mathbb{R}$ s.t. for any
$v\in\mathring{V}$, the single variable function $g(\cdot,v)$ is
differentiable at $v$, suppose there exists some $E\subseteq\mathring{V}$ with
$\rho(E)>0$ s.t. for any $v\in E$, we have
$\nabla_{v^{\prime}}g(v^{\prime},v)|_{v^{\prime}=v}\neq\mathbf{0}$, then for
any $v\in E$, there exists $v^{\prime}\in V$ s.t $g(v^{\prime},v)>g(v,v)$.

###### Proof.

For any $v\in E$, since $v\in\mathring{V}$, there exists $\epsilon_{0}>0$ s.t.
the open ball $B(v,\epsilon_{0})\subseteq V$.
$\nabla_{v^{\prime}}g(v^{\prime},v)|_{v^{\prime}=v}\neq\mathbf{0}$ implies the
existence of some unit vector $y\in S^{d-1}$ s.t. $\lim_{\epsilon\downarrow
0}\frac{g(v+\epsilon y,v)-g(v,v)}{\epsilon}>0$. Therefore, we can find
$\epsilon_{1}<\epsilon_{0}$ s.t. $g(v+\epsilon_{1}y,v)>g(v,v)$. ∎

Then we are ready to prove Theorem 2.

###### Proof of Theorem 2.

Suppose $(x,p)$ is incentive compatible, but neither of the two conditions
hold.

If the constraint is unbinding when reporting truthfully, by Assumption 2, the
second condition is violated only if there exists some
$E\subseteq\mathring{V}$ with $\rho(E)>0$ s.t. for every $v\in E$,
$\hat{u}(v)\neq\mathbf{0}$. By Lemma 4 for any $v\in E$ there exists
$v^{\prime}\in V$ s.t. $u(x(v^{\prime}),v)-c_{1}\cdot
p(v^{\prime})>u(x(v),v)-c_{1}\cdot p(v)$. By Lemma 3 such $(x,p)$ is not
incentive compatible, contradiction.

If the constraint is binding when reporting truthfully, by Assumption 2, the
first condition of Theorem 2 is violated only if there exists some
$E\subseteq\mathring{V}$ with $\rho(E)>0$ s.t. for every $v\in E$,
$\hat{f}(v)\neq\mathbf{0}$. By Lemma 4 for any $v\in E$ there exists
$v^{\prime}\in V$ s.t. $f(x(v^{\prime}),v)-c_{2}\cdot
p(v^{\prime})>f(x(v),v)-c_{2}\cdot p(v)$. Such $(x,p)$ violates the first
condition of Lemma 3. The second condition of Theorem 2 is violated only if
for any $r\geq 0$, there exists some $E\subseteq\mathring{V}$ with $\rho(E)>0$
s.t. for every $v\in E$, $\hat{u}(v)+r\cdot\hat{f}(v)\neq\mathbf{0}$. By Lemma
4 for any $v\in E$ there exists $v^{\prime}\in V$ s.t.

$\displaystyle[u(x(v^{\prime}),v)-c_{1}\cdot
p(v^{\prime})]-[u(x(v),v)-c_{1}\cdot p(v)]$ (6) $\displaystyle>$
$\displaystyle-r\cdot[f(x(v^{\prime}),v)-c_{2}\cdot
p(v^{\prime})]+r\cdot[f(x(v),v)-c_{2}\cdot p(v)],$

which violates the second condition of Lemma 3. Therefore such $(x,p)$ is not
incentive compatible, contradiction.

We conclude that, to make $(x,p)$ incentive compatible, at least one of the
two conditions in Theorem 2 holds. ∎

Theorem 2 gives necessary condition of incentive compatibility in terms of
differential properties of the interim rules $(x,p)$ and functions $(u,f)$
given by the player model. Using Theorem 2 as a starting point, the next
section gives another characterization of incentive compatibility under some
additional assumptions, and the characterization is identical in shape with
the payment identity in classic mechanism design (Myerson 1981; Manelli and
Vincent 2007).

##  6 Quasi-linear player model

In this section, we restrict our attention to $u(\cdot,\cdot)$ and
$f(\cdot,\cdot)$ which are linear in their second argument:

######  Assumption 4.

There exist functions $u^{*},f^{*}:Q\rightarrow\mathbb{R}^{d}$ s.t. for any
$v\in V$ and any $q\in Q$, we have

$\displaystyle u(q,v)=u^{*}(q)\cdot v,$ $\displaystyle f(q,v)=f^{*}(q)\cdot
v.$

Moreover, the $u^{*}$ and $f^{*}$ are differentiable on $\mathring{V}$, and
can be continuously extended to $V$.

For technical simplicity, we also include the following assumptions. The first
assumption holds for any $\rho$ which can be expressed by a positive
probability density function on $V$. With these assumptions, the first
condition of Theorem 2 is ruled out, and we can refer to $\hat{u}$ or
$\hat{f}$ as if they are defined on $V$.

######  Assumption 5.

$V$ is connected. Moreover, for any $E\subseteq V$ with $\rho(E)=1$, $E$ is
dense in $V$.

######  Assumption 6.

There exists some $E\subseteq V$ with $\rho(E)>0$ s.t. for any $v\in V$,
$\hat{f}(v)\neq\mathbf{0}$,

######  Assumption 7.

$\hat{u}$ and $\hat{f}$ are continuous on $\mathring{V}$, and can be
continuously extended to $V$.

We define the surrogate outcome function $\tilde{u}$ and surrogate utility
function $\tilde{U}$, which are central in our last characterization of
incentive compatibility.

######  Definition 2.

The surrogate outcome $\tilde{u}:Q\rightarrow\mathbb{R}^{d}$ is defined to be:

$\tilde{u}(q)\coloneqq u^{*}(q)+r\cdot f^{*}(q).$

The surrogate utility $\tilde{U}:V\rightarrow\mathbb{R}$ is defined to be:

$\tilde{U}(v)\coloneqq\tilde{u}(x(v))\cdot v-(c_{1}+rc_{2})\cdot p(v)$

Note that the global constant $r$ is a parameter of surrogate outcome and
surrogate utility, and such an $r$ exists if and only if $(x,p)$ is incentive
compatible. When $r=0$, the surrogate utility is equal to the player’s
original utility. When $r>0$, the surrogate utility is a linear combination of
a utility term and a constraint term, which again mirrors the results in auto-
bidding literature.

With the additional assumptions, we are ready to give our second
characterization of incentive compatibility.

######  Theorem 3.

Under Assumption 1 \- 7, the interim rule pair $(x,p)$ is incentive compatible
if and only only if, for surrogate outcome $\tilde{u}$ and surrogate utility
$\tilde{U}$ given by Definition 2, we have:

  * •

$\tilde{u}$ and $\tilde{U}$ satisfy $\nabla\tilde{U}(v)=\tilde{u}(x(v)),\ \
\forall v\in V,$ AND

  * •

$\tilde{U}$ is convex, AND

  * •

if $r>0$, the ex-ante constraint is binding when reporting truthfully.

###### Proof.

By Theorem 2 and Assumption 6, $(x,p)$ is incentive compatible only if there
exists constant $r\in\mathbb{R}_{\geq 0}$ s.t. for almost every
$v\in\mathring{V}$, $\hat{u}(v)+r\cdot\hat{f}(v)=0$, and if $r>0$, the ex-ante
constraint is binding when reporting truthfully.

By Assumption 4, $\hat{u}$ and $\hat{f}$ can be given by:

$\displaystyle\hat{u}(v)=\nabla[u^{*}(x(v))]\cdot v-c_{1}\cdot\nabla p(v)$
$\displaystyle\hat{f}(v)=\nabla[f^{*}(x(v))]\cdot v-c_{2}\cdot\nabla p(v)$

For almost every $v\in\mathring{V}$, $\hat{u}(v)+r\cdot\hat{f}(v)=0$. Then,
equation

$\nabla[u^{*}(x(v))]\cdot v-c_{1}\nabla p(v)+r\cdot\nabla[f^{*}(x(v))]\cdot
v-rc_{2}\cdot\nabla p(v)=0$ (7)

holds for almost every $v$. By Assumption 2, 5 and 7, equation (7) holds for
almost every $v$ if and only if it holds for all $v\in V$. Note that by
definition of surrogate outcome, (7) can be further rewritten as

$\nabla[\tilde{u}(x(v))]\cdot v=(c_{1}+rc_{2})\nabla p(v)$

Consider an arbitrary point $v_{0}\in V$. For any $v\in V$ and any path $L$
from $v_{0}$ to $v$, by integral by parts we have

$[\tilde{u}(x(t))\cdot
t]|_{v_{0}}^{v}-\int_{L}\tilde{u}(x(t))\cdot\mathrm{d}t=(c_{1}+rc_{2})\cdot
p(t)|_{v_{0}}^{v}.$

By definition of surrogate utility, this can be rewritten as

$\tilde{U}(v)-\tilde{U}(v_{0})=\int_{L}\tilde{u}(x(t))\cdot\mathrm{d}t,\ \
\forall v_{0},v\in V.$

Therefore, $\tilde{U}$ is a potential function on $V$ whose gradient is given
by $\tilde{u}\circ x$. In differential form, we have

$\nabla\tilde{U}(v)=\tilde{u}(x(v)),\ \ \forall v\in V.$ (8)

By Lemma 3, $(x,p)$ is incentive compatible if and only if equation (5) holds
for almost every $v$ and every $v^{\prime}$. Note that equation (5) can be
rewritten as

$[\tilde{u}(x(v^{\prime}))\cdot
v-(c_{1}+rc_{2})p(v^{\prime})]-[\tilde{u}(x(v))\cdot v-(c_{1}+rc_{2})p(v)]\leq
0.$

By definition of $\tilde{U}$ and equation (8), we have:

$\displaystyle[\tilde{u}(x(v^{\prime}))\cdot v-(c_{1}+rc_{2})p(v^{\prime})]$
$\displaystyle-[\tilde{u}(x(v))\cdot v-(c_{1}+rc_{2})p(v)]$ $\displaystyle=$
$\displaystyle(\tilde{u}(x(v^{\prime}))-\tilde{u}(x(v)))\cdot
v-(\tilde{u}(x(v^{\prime}))\cdot v^{\prime}-\tilde{U}(v^{\prime}))$
$\displaystyle+(\tilde{u}(x(v))\cdot v-\tilde{U}(v))$ $\displaystyle=$
$\displaystyle\tilde{U}(v^{\prime})-\tilde{U}(v)-\nabla\tilde{U}(v^{\prime})\cdot(v^{\prime}-v)$

Therefore, $(x,p)$ is truthful if and only if for almost every $v$, for every
$v^{\prime}$, we have
$\tilde{U}(v^{\prime})-\tilde{U}(v)-\nabla\tilde{U}(v^{\prime})\cdot(v^{\prime}-v)\leq
0$. By assumption of continuous $\tilde{u}$, $x$ and $p$, and that such $v$ is
dense in $V$, we conclude that
$\tilde{U}(v^{\prime})-\tilde{U}(v)-\nabla\tilde{U}(v^{\prime})\cdot(v^{\prime}-v)\leq
0$ holds for all $v\in V$, which is equivalent to $\tilde{U}$ being convex. ∎

## Acknowledgments

We sincerely acknowledge Xiao Han, who is a researcher in Theoretical
Probability, for his constructive advice on the proofs.

## References

  * Agarwal et al. (2014) Agarwal, D.; Ghosh, S.; Wei, K.; and You, S. 2014.  Budget pacing for targeted online advertisements at LinkedIn.  _Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining_.
  * Aggarwal, Badanidiyuru, and Mehta (2019) Aggarwal, G.; Badanidiyuru, A.; and Mehta, A. 2019.  Autobidding with Constraints.  In Caragiannis, I.; Mirrokni, V.; and Nikolova, E., eds., _Web and Internet Economics_ , 17–30. Cham: Springer International Publishing.  ISBN 978-3-030-35389-6.
  * Ashlagi, Daskalakis, and Haghpanah (2016) Ashlagi, I.; Daskalakis, C.; and Haghpanah, N. 2016.  Sequential Mechanisms with Ex-Post Participation Guarantees.  In _Proceedings of the 2016 ACM Conference on Economics and Computation_ , EC ’16, 213–214. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450339360.
  * Ashlagi, Daskalakis, and Haghpanah (2019) Ashlagi, I.; Daskalakis, C.; and Haghpanah, N. 2019.  Sequential Mechanisms With ex post Individual Rationality.
  * Babaioff et al. (2021) Babaioff, M.; Cole, R.; Hartline, J. D.; Immorlica, N.; and Lucier, B. 2021.  Non-quasi-linear Agents in Quasi-linear Mechanisms.  In _ITCS_.
  * Balseiro and Gur (2019) Balseiro, S.; and Gur, Y. 2019.  Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium.  _Management Science_ , 65: 3952–3968.
  * Balseiro et al. (2017) Balseiro, S.; Kim, A.; Mahdian, M.; and Mirrokni, V. 2017.  Budget Management Strategies in Repeated Auctions.  15–23.
  * Balseiro et al. (2021) Balseiro, S. R.; Deng, Y.; Mao, J.; Mirrokni, V. S.; and Zuo, S. 2021.  The Landscape of Auto-Bidding Auctions: Value versus Utility Maximization.  In _Proceedings of the 22nd ACM Conference on Economics and Computation_ , EC ’21, 132–133. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450385541.
  * Brainard and Scarf (2005) Brainard, W. C.; and Scarf, H. E. 2005.  How to Compute Equilibrium Prices in 1891.  _American Journal of Economics and Sociology_ , 64(1): 57–83.
  * Burkett (2016) Burkett, J. 2016.  Optimally constraining a bidder using a simple budget.  _Theoretical Economics_ , 11: 133–155.
  * Che and Gale (1998) Che, Y.-K.; and Gale, I. 1998.  Standard Auctions with Financially Constrained Bidders.  _The Review of Economic Studies_ , 65(1): 1–21.
  * Chen, Kroer, and Kumar (2021) Chen, X.; Kroer, C.; and Kumar, R. 2021.  _The Complexity of Pacing for Second-Price Auctions_ , 318.  New York, NY, USA: Association for Computing Machinery.  ISBN 9781450385541.
  * Conitzer et al. (2018) Conitzer, V.; Kroer, C.; Sodomka, E.; and Stier-Moses, N. 2018.  Multiplicative Pacing Equilibria in Auction Markets.  In _WINE_.
  * Deng et al. (2021) Deng, Y.; Mao, J.; Mirrokni, V.; and Zuo, S. 2021.  _Towards Efficient Auctions in an Auto-Bidding World_ , 3965–3973.  New York, NY, USA: Association for Computing Machinery.  ISBN 9781450383127.
  * Golrezaei et al. (2021) Golrezaei, N.; Jaillet, P.; Liang, J. C. N.; and Mirrokni, V. 2021.  Bidding and Pricing in Budget and ROI Constrained Markets.  arXiv:2107.07725.
  * Golrezaei, Lobel, and Paes Leme (2021) Golrezaei, N.; Lobel, I.; and Paes Leme, R. 2021.  _Auction Design for ROI-Constrained Buyers_ , 3941–3952.  New York, NY, USA: Association for Computing Machinery.  ISBN 9781450383127.
  * Heymann (2019) Heymann, B. 2019.  Cost per Action Constrained Auctions.  In _Proceedings of the 14th Workshop on the Economics of Networks, Systems and Computation_ , NetEcon ’19. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450368377.
  * Li et al. (2020) Li, B.; Yang, X.; Sun, D.; Ji, Z.; Jiang, Z.; Han, C.; and Hao, D. 2020.  Incentive Mechanism Design for ROI-constrained Auto-bidding.  arXiv:2012.02652.
  * Manelli and Vincent (2007) Manelli, A. M.; and Vincent, D. R. 2007.  Multidimensional mechanism design: Revenue maximization and the multiple-good monopoly.  _Journal of Economic Theory_ , 137(1): 153–185.
  * Myerson (1981) Myerson, R. B. 1981.  Optimal Auction Design.  _Mathematics of Operations Research_ , 6(1): 58–73.
  * Wen et al. (2021) Wen, C.; Xu, M.; Zhang, Z.; Zheng, Z.; Wang, Y.; Liu, X.; Rong, Y.; Xie, D.; Tan, X.; Yu, C.; Xu, J.; Wu, F.; Chen, G.; and Zhu, X. 2021.  A Cooperative-Competitive Multi-Agent Framework for Auto-bidding in Online Advertising.  _CoRR_ , abs/2106.06224.
  * Zhou, Chakrabarty, and Lukose (2008) Zhou, Y.; Chakrabarty, D.; and Lukose, R. 2008.  Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems.  In _Proceedings of the 17th International Conference on World Wide Web_ , WWW ’08, 1243–1244. New York, NY, USA: Association for Computing Machinery.  ISBN 9781605580852.