# optimal_auction_design_for_mixed_bidders__3a6d0b5b.pdf

Optimal Auction Design for Mixed Bidders

Xiaohui Bei1, Pinyan Lu2, Zhiqi Wang2, Tao Xiao3, Xiang Yan3

1School of Physical and Mathematical Sciences, Nanyang Technological University 2Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics 3Huawei Taylor Lab xhbei@ntu.edu.sg, lu.pinyan@mail.shufe.edu.cn, wangzhiq@126.com, xiaotao21@huawei.com, xyansjtu@163.com

The predominant setting in classic auction theory considers bidders as utility maximizers (UMs), who aim to maximize quasi-linear utility functions. Recent autobidding strategies in online advertising have sparked interest in auction design with value maximizers (VMs), who aim to maximize the total value obtained. In this work, we investigate revenuemaximizing auction design for selling a single item to a mix of UMs and VMs. Crucially, we assume the UM/VM type is private information of a bidder. This shift to a multiparameter domain complicates the design of incentive compatible mechanisms. Under this setting, we first characterize the optimal auction structure for auctions with a single bidder. We observe that the optimal auction moves gradually from a first-price auction to a Myerson auction as the probability of the bidder being a UM increases from 0 to 1. We also extend our study to multi-bidder setting and present an algorithm for deriving the optimal lookahead auction with multiple mixed types of bidders.

Introduction In the past decades, online advertising has experienced significant success through effective auction design. The role of online advertising auctions in generating revenue for many IT companies is immense. At the same time, the scale and complexity of the online advertising market have led to the development and adoption of more efficient auction designs for the online environment. The classical auction theory mainly builds upon the utility maximizer (UM) model; the objective of a UM is to maximize her (quasi-linear) utility, which is the difference between the allocated value and the payment. In the meanwhile, the growing adoption of autobidding in online advertising has motivated a new value maximizer (VM) paradigm (Aggarwal, Badanidiyuru, and Mehta 2019; Balseiro et al. 2021; Deng et al. 2021). Unlike the UMs, the objective of a VM is to maximize the total value she receives. VM can be used to model, for example, a company s advertising department that cannot collect the unspent budget (Lu, Xu, and Zhang 2023). Consider an ad exchange (ADX) in online ads systems, which is the auctioneer facing bids from the demand-side platforms (DSPs). Modern DSPs provide

Copyright 2025, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

auto-bidding services for advertisers, meaning DSPs know the bidder s value and type, whereas ADX does not. In this scenario, a well-designed auction format can assist in generating more profits and facilitating better resource allocation. Besides advertising auctions, art auctions also involve both UM and VM. Art pieces are unique and often hold sentimental or historical value, making collectors or enthusiasts more inclined to purchase them at higher prices. Hence, they could be considered VMs in this context. However, some other bidders buy the art pieces for their potential investment value. These bidders should be modeled as UMs, resulting in the coexistence of UMs and VMs in art auctions. Note that VMs are usually more willing to spend money in an auction, which means there is a large potential for the mechanism to extract more revenue from them. In most previous works, UMs and VMs are usually considered separately. That is, all bidders in an auction are assumed to have the same UM/VM type. However, since different advertisers usually have different bidding strategies, a practical online advertising platform observes a mixture of UMs and VMs participating in an auction simultaneously, and moreover, the auctioneer cannot distinguish them. The presence of both UMs and VMs brings additional challenges designing Incentive Compatible (IC) and Individually Rational (IR) mechanisms. Specifically, relying on the bidders who bid their own types makes them able to benefit by misreporting both of their values and/or UM/VM types. The problem moves to the multi-parameter from the singleparameter domain, where people have little understanding of the optimal auction design in most settings. In this work, we investigate the revenue-maximizing optimal auction design for mixed bidders under the Bayesian setting1. Our main results are:

We provide a neat characterization of IC auctions in the presence of both UMs and VMs simultaneously. We then express the revenue as a function only related to the allocation for UMs. Unlike the single-parameter environment in which the objective is linear with respect to the allocation function, our characterization and revenue expression are more complex in the mixed bidder setting. We then apply the variation method to solve the optimal allocation function and present an algorithm to compute

1Mechanism based on known prior of bidder s types and values.

The Thirty-Ninth AAAI Conference on Artificial Intelligence (AAAI-25)

the optimal mechanism for a single bidder. We also provide an analytical description of the optimal mechanism when the bidder s value follows uniform distribution; Finally, we provide an algorithm to solve the optimal lookahead auction in the multiple mixed bidders setting.

Additional Related Works (Lv et al. 2023) takes the first steps on truthful auction designs for mixed bidders. They consider bidders types and values are private but fixed. Then the mechanism can achieve a constant approximation to the optimal social welfare. In comparison, we consider a Bayesian setting where bidders types and values follow a known distribution independently. The objective function in this paper is revenue, and we can achieve optimal. Other related literature includes works designing mechanisms for UMs and VMs separately, for which we only survey some representative ones. For UMs, Myerson did the most seminal work on auction theory and designed the optimal mechanism for selling a single item to multiple bidders whose values follow independent random distributions (Bayesian setting) (Myerson 1981). His approach can be extended to a broader scenario called singleparameter environment2. Other mechanism designs for UMs include position auctions(Varian 2007; Edelman, Ostrovsky, and Schwarz 2007; Chawla and Hartline 2013), multidimensional screening(Chawla et al. 2010; Daskalakis, Deckelbaum, and Tzamos 2015; Hart and Reny 2015), and approximate mechanisms(Hart and Nisan 2017; Jin et al. 2020). For VMs, most existing literature focuses on the efficiency of some special auction format (Deng et al. 2022, 2023; Lu, Xu, and Zhang 2023) or designing new mechanisms (Balseiro et al. 2023, 2021).

Preliminaries

We first introduce the auction model with two types of bidders. Next, we present the multi-parameter mechanism settings for the optimal auction design problem and the IR and IC constraints.

Auction Model

We consider the standard Bayesian single-item auction model. In this model, one auctioneer, also referred to as the seller, sells one item to n potential buyers, also known as bidders. Our model includes two types of bidders: UM and VM. The type of the i-th bidder, ti {U, V }, represents UM and VM, respectively. The private value of the i-th bidder is vi. The class of the i-th bidder is the pair of the type and the value, denoted as θi = (ti, vi). Let v = (vi)i [n], t = (ti)i [n], and θ = (θi)i [n]. A UM s utility is the difference between the allocated value and the payment, while a VM s utility is simply the allocated value. Each bidder, whether UM or VM, seeks to maximize their utility. We assume that the distribution of each bidder s θi is identical and known. Each bidder is a UM with probability q and a VM with probability 1 q, independently. If a bidder s type is

2We provide a brief introduction about the single parameter environment in full version.

UM, her value vi follows the distribution FU, with probability density function (pdf) f U( ), independently and identically. If the bidder is a VM, her value follows the distribution FV , with pdf f V ( ), independently and identically. In this paper, we assume FU is regular3, and there is no assumption on FV .

Multi-Parameter Mechanisms We consider a multi-parameter mechanism, where bidders submit bids that include both their values and their types. Let bi = (ˆti, ˆvi) represent the bid of the i-th bidder, and b = (bi)i [n] represent the bid profile. After receiving the bids, the mechanism determines x(b) = (xi(b))i [n] and p(b) = (pi(b))i [n], representing the allocation and payments, respectively. Let ui(b) denote the utility of the i-th bidder under the bid profile b. According to the definition of the two types of bidders, we have

ui(b) = xi(b)vi pi(b) if ti = U, xi(b) vi if ti = V .

Denote M = (x, p), which is the pair of allocation and payment functions. Since there is only one item to be sold, Pn i=1 xi(b) 1, b. In this paper, we focus on designing a mechanism that satisfies the following IR and IC constraints.

(Ex-post) IR Constraints If the i-th bidder bids truthfully, the payment should not be larger than her value, whatever the other bidders bid.

i, b i, pi(θi, b i) vi xi(θi, b i),

where b i is the bids of all bidders except the i-th bidder. Note that although the utility of the VMs is not related to the payments, the IR constraints require their payment to be less than their value, which prevents us from extracting a large amount of revenue from them.

(Ex-ante) IC Constraints We consider the Bayesian Incentive Compatibility (BIC) constraints in our model. That is,

i,ˆb, Eθ i[ui(ˆb, θ i)] Eθ i[ui((ti, vi), θ i)],

where θ i is the classes of all bidders except the i-th bidder.

Revenue Maximization The seller aims to maximize the revenue, which is the sum of payments from all bidders. We denote the revenue by REV(M) = Pn i=1 pi(b). The problem can be viewed as the following optimization problem

max x( ),p( ) Eθ[

i=1 pi(θ)] (REV OPT)

i=1 xi(θ) 1, θ

x( ), p( ) satisfy IR and IC constraints, xi(θ), pi(θ) 0, θ.

3A distribution F is regular if the virtual value function φ(v) = v 1 F(v)

f(v) is monotone increasing where f( ) is the pdf.

Characterization of the IC Auctions Structure In this section, we characterize the Incentive Compatible (IC) auctions with mixed bidder types. Precisely, given any fixed interim allocation for UMs that is monotonically increasing and continuous, we characterize the interim payments for both bidder types and the interim allocation for VMs for a revenue-maximizing auction. This characterization is more intricate compared to the single-parameter auctions due to the complexity of two dimensional parameters affecting the IC constraints. Note that an IR and IC singleparameter mechanism that allows bidders to only bid values and not their classes cannot achieve any reasonable revenue for mixed bidders, particularly when bidders are more likely to be VMs. (See full version for a detailed discussion.) Denote

x U i (vi) = Eθ i[xi((U, vi), θ i)],

p U i (vi) = Eθ i[pi((U, vi), θ i)], as the interim allocation and payment for the i-th bidder respectively if her type is UM and value is vi. Similarly, let

x V i (vi) = Eθ i[xi((V, vi), θ i)],

p V i (vi) = Eθ i[pi((V, vi), θ i)], be the interim allocation and payment for a VM with value vi respectively. Denote v U = sup{supp(FU)}4. We have the following characterization. Theorem 1. Given x U i ( ) which is monotonically increasing and continuous. Denote

p U i (vi) x U i (vi) x U i (vi) > 0; vi x U i (vi) = 0, as the expected payment per unit of UMs with value vi. The following payment and allocation rules are revenue-optimal under the IR and IC constraints:

p U i (vi) = vi x U i (vi) Z vi

x U i (u)du;

x V i (vi) =

x U i (g 1 i (vi)) if 0 vi gi(v U),

R v U 0 x U (u)du v U vi , 1} if gi(v U) < vi v U,

1 if vi > v U; p V i (vi) = vi x V i (vi). This characterization theorem allows us to transform the optimization (REV OPT) into a simpler optimization problem solely for the interim allocation for UMs. The remaining of this section shows the proof of this theorem. We start by characterizing the IC payment rules.

Payment Rules We follow a similar idea as (Myerson 1981) to first characterize the unique IR and IC payment rule for any given allocation rule. This structural result helps us express the auction revenue as a function of the allocation rule. Since the bidders can deviate in two dimensions (types and value), there are four groups of IC constraints: UMUM, VM-VM, UM-VM, and VM-UM, where A-B means a bidder of type A cannot benefit from bidding type B and a possibly different value.

4For distribution F with pdf f( ), supp(F) = {v|f(v) > 0}.

UM-UM: We first focus on the constraints that any UM i cannot benefit from bidding the true type ti = U, but an untruthful ˆv rather than the true value vi. Formally,

ˆv, vi x U i (ˆv) p U i (ˆv) vi x U i (vi) p U i (vi).

Such constraints are exactly the same as those in the singleparameter auction setting. Thus, by Myerson s Lemma we have: Lemma 1 (Myerson 1981). For given x U i ( ), the only payment satisfying the IC constraints for the UMs is:

p U i (vi) = vi x U i (vi) Z vi

x U i (u)du.

Moreover, the expected utility of a UM with value vi is:

vi, u U i (vi) = vi x U i (vi) p U i (vi) = Z vi

x U i (u)du.

The payment function here is called Myerson s payment for UMs. Recall that we define

gi(vi) = p U i (vi) x U i (vi) = vi

R vi 0 x U i (u)du x U i (vi) ,

as the expected payment per unit of UMs with value vi, then Myerson s payment can be expressed as:

pi((U, vi), θ i) = xi((U, vi), θ i) gi(vi).

Payment for VMs. We can also show that the optimal payment function for VMs must be the first price payment. That is, the payment of the winner equals to the value she bids times her allocation. Indeed, it can be easily verified that for any IR and IC mechanism, increasing p V i (vi) to vix V i (vi) for a VM will not violate the IR and IC constraints. Thus, a revenue-optimal mechanism should always have the first price payment for VMs.

Allocation Rules for VMs Next, we discuss x V i ( ) satisfying the IC constraints for given x U i ( ). Under Myerson s and the first price payment for UMs and VMs respectively derived in the last subsection, we consider the other three groups of IC constraints:

VM-VM: The interim allocation for the VMs should be monotone:

ˆv vi, x V i (ˆv) x V i (vi).

UM-VM: A UM will not misreport her type as VM with a higher value, since her utility will be non-positive then. As for misreporting a lower value, the IC constraints require:

ˆv vi, u U i (vi) = Z vi

x U i (u)du (vi ˆv) x V i (ˆv).

VM-UM: A VM would only misreport as a UM with ˆv such that vi gi(ˆv) (IR constraints for VM). Then we have the IC constraints for such ˆv:

ˆv, s.t. gi(ˆv) v, x U i (ˆv) x V i (vi).

From these constraints, we can see that the IC condition for x V i is closely related to gi( ). The following lemma characterizes several basic properties of gi( ):

Lemma 2. The gi( ) function has the following properties: gi( ) is monotone increasing; v1, v2, we have x U i (v1) = x U i (v2) if and only if gi(v1) = gi(v2); If x U i ( ) is continuous, then gi( ) is also continuous; Given any fixed gi( ), we have

x U i (v) = C exp Z v

g i(u) u gi(u)du ,

for some constant C. The last property in Lemma 2 suggests that to optimize x U i ( ), we can instead focus on optimizing gi( ). The proof of this lemma can be found in the full version. When x U i ( ) is given, the following lemma characterizes a necessary condition of IC x V i ( ).

Lemma 3 (Necessary condition of IC x V i ( )). For any given x U i ( ), suppose x V i ( ) satisfies the IC constraints, then for any vi, v, v, such that gi(v) vi gi(v), we have

x U i (v) x V i (vi) x U i (v).

Specially, if there exists v , such that gi(v ) = vi, then x V i (vi) = x U i (v ).

Proof: According to the VM-UM IC constraints, we have x V i (vi) x U i (v), which is the first inequality. For the second inequality, we have

x V i (vi) u U i (v) v vi (UM-VM IC constraints)

u U i (v) v gi(v) (vi gi(v))

= x U i (v) v p U i (v)

v p U i (v) x U i (v) = x U i (v).

With the help of Lemma 3 and mild assumptions on x U i ( ), we can derive a necessary and sufficient condition of x V i ( ).

Lemma 4 (Necessary and sufficient condition of IC x V i ( ) for continuous x U i ( )). When x U i ( ) is continuous, the necessary and sufficient condition for IC x V i ( ) is that:

1. x V i ( ) is monotonically increasing; 2. 0 vi gi(v U), x V i (vi) = x U i (g 1 i (vi));

3. gi(v U) < vi v U, x V (vi)

0 x U(u)du v U vi .

Proof: We first show that the allocation is well-defined. Specifically, by the second property of Lemma 2, we know that x U i (g 1 i (vi)) exists and is unique, even when g 1 i (vi) is a set of values. For necessity, x V i ( ) should be monotone increasing from the VM-VM IC constraints. Condition (2) holds by Lemma 3 and the continuity of x U i , and condition (3) holds due to the UM-VM IC constraints for UM with value v U. For the sufficiency, the VM-VM and VM-UM constraints both hold for the monotonicity of x U i ( ), x V i ( ) and gi( ). It

suffices to show that the UM-VM constraints hold. We first consider the UMs with value 0 vi gi(v U). They will not deviate to a VM with a value larger than gi(v U). For any value ˆv gi(v U) we have

(vi ˆv) x V i (ˆv) =(vi gi(g 1 i (ˆv))) x U i (g 1 i (ˆv))

=vi x U i (g 1 i (ˆv)) p U i (g 1 i (ˆv))

u U i (vi).

The second equality is because gi(vi) x U i (vi) = p U i (vi) for any vi. The third inequality is from the UM-UM IC constraints which can be guaranteed only by Myerson s payments.

If vi > gi(v U), then for any ˆv vi and ˆv [g(v U), v U] we have:

(vi ˆv) x V (ˆv) (vi ˆv)

0 x U(u)du v U ˆv

v U g(v U) Z v U

= vi x U(v U) p U(v U)

The second inequality holds as ˆv g(v U), and the last inequality holds as the UM-UM IC constraints which is guaranteed by the Myerson s payment.

Lemma 4 reveals an important connection between UM and VM in an IR and IC auction: the interim allocation and payment must be identical for a UM with value vi and a VM with value gi(vi).

With Lemma 4, the proof of the Theorem 1 is straightforward. When x U i ( ) is given, the revenue is monotone increasing with respect to the value of x V i ( ). Therefore, to maximize the revenue as stated in Theorem 1, the third property of Lemma 4 should be utilized to take the maximum.

Optimal Auction Design for a Single Bidder

We now solve the revenue-maximization problem for a single bidder. This can be achieved by first expressing the revenue objective in terms of x U i ( ), then applying a variational method to optimize it. We also provide a numerical algorithm to solve the ordinary differential equation (ODE) arising from the variational method, and demonstrate that our theory aligns with the results in the literature in two extreme scenarios. Additionally, we derive the optimal mechanism in closed form for the case where the value distributions follow a uniform distribution, which is detailed in the full version.

Problem Reformulation We express the revenue w.r.t. x U i ( ) in the multi-bidder case:

REV(M) = Eθ[

0 q p U i (v)f U(v) + (1 q) p V i (v)f V (v)dv

0 q x U i (v)φU(v)f U(v)

+ (1 q) x V i (v) v f V (v)dv,

where the second equality is from the revenue equivalence and p V i (v) = x V i (v) v. We define

h U i (v) = q φU(v)f U(v), h V i (v) = (1 q) v f V (v).

Then the revenue can be expressed as

x U i (v)h U i (v) + x V i (v)h V i (v) dv.

For the single-bidder case, we omit the subscript i. Note that to maximize the revenue, we should always allocate the item to the UM when she has the largest value in the support. Denote v = infv{x U(v) = 1}. The optimal x V ( ) in Theorem 1 can then be expressed as:

x U(g 1(v)) if 0 v g(v), 1 if v > g(v).

Thus, the second term satisfies Z +

x V (v)h V (v)dv

x U(g 1(v))h V (v)dv + Z +

g(v) h V (v)dv

x U(v)g (v)h V (g(v))dv + Z +

g(v) h V (v)dv,

where the last equality holds as we substitute v by g 1(v) in the first integral. Thus, the revenue can be expressed as

REV(M) = Z v

x U(v)h U(v) + x U(v)g (v)h V (g(v)) dv

v h U(v)dv + Z +

g(v) h V (v)dv. (1)

Optimizing x U( ) Applying Theorem 1 to Eqn. (1) and denote y(v) = R v 0 x U(u)du, we have x U(v) = y (v) and g(v) = v y(v)

which means x U (v) = y (v) and g (v) = y(v)y (v)

(y (v)2) . The revenue becomes

REV(M) = Z v

y h U(v) + y y

v h U(v)dv + Z +

g(v) h V (v)dv. (2)

If we fix y(v) and let y (v) = x U(v) = 1 to be the initial value, then g(v) = v y(v) is also fixed. This makes the last two integrals in the revenue as constants, and our target is now to maximize the first integral. Define

f(v, y, y , y ) = y y

y ) + y h U(v).

The optimization problem becomes

0 f(v, y, y , y )dv (3)

s.t. y (v) is monotone increasing, 0 y (v) 1 v, y (0) = 0, y (v) = 1.

Applying the Euler-Lagrange equation

dv f y + d2

dv2 f y = 0, (4)

=h U (v) y y

Substituting them into Eqn. (4) leads to

= h U (v) . (5)

This is a second-order ODE. With the initial value provided in the optimization (3), the ODE has a unique solution. The parameter v is yet to be determined and is associated with the revenue. By solving ODE (5), we can determine y( ). Subsequently, substituting this into Eqn. (2) gives us REV(M) as a function of v. Finally, we can search all possible values of v to find the one with the optimal revenue. While a general second-order ODE may be difficult to solve, in the following we present a numerical algorithm 1 to obtain the optimal auction. We first discretize the integral interval with gap ε. If y(v) and y (v) are known, we invoke RK(v) = (y(v + ε), y (v + ε), y (v + ε)) as an extrapolation method oracle for the solution of ODE (5). It can be implemented by any numerical ODE algorithm, such as the Runge-Kutta methods. We define

REV(v) = y (v) h U(v) + y(v)y (v)

y (v) h V v y(v)

which is used to compute the revenue in our numerical algorithm. Different from the argument above, we choose y (ε) as the parameter to be optimized for convenience.

Two Extreme Scenarios We validate our solution by solving the optimal auction in two extreme cases, q = 1 and q = 0, meaning the bidder is

Algorithm 1: Find the optimal allocation for a single bidder

v U sup{supp(F U)}, v V sup{supp(F V )} for all possible parameter C do REV(C) 0, y(ε) ε C, y (ε) C for j = 2ε, 3ε, . . . , v U do (y(j), y (j), y (j)) RK(j ε) REV(C)+ = ε REV(j) if y (j) > 1 then break end if end for REV(C)+ = R v U

j h U(v)dv + R v V

y (j) h V (v)dv

end for return the C with the highest REV(C)

of type UM or VM with probability 1. We will demonstrate that these solutions precisely correspond to the optimal auction formats established in the literature. First, rather than solving the ODE (5) directly, we can utilize the fact that y /y = g (v)/(v g(v)) as derived by definition, and transform ODE (5) into:

0 v v, g (v)h V (g(v))

v g(v) = h U (v). (6)

This is a first-order ODE. Once g(v) is solved according to ODE (6), we can obtain x U( ) by the last property of Lemma 2:

x U(v) = C(v) exp Z v

g (u) u g(u)du , (7)

where C(v) is a constant determined by the initial condition v. By inserting this into Eqn. (2) we can derive REV(M) as a function of v. This allows us to search all possible v values to identify the v that maximizes our revenue. When q = 0, we have h U(v) 0, h U = 0. Thus, g (v) = 0 and g(v) 0 from ODE (6). By substituting it into Eqn. (7) we have x U(v) = x V (v) 1, which is the first price auction. When q = 1, we have h V (v) 0. According to ODE (6), g(v) = v, 0 v v, which leads to

x U(v) = 0 0 v < v, 1 v v.

This is a posted price mechanism which is exactly Myerson s auction for a single bidder (after searching for the revenue-maximizing v).

Optimal Auction Design for Multiple Bidders We now turn to the general multi-bidder case. In this section, we first show the necessary and sufficient conditions for the feasibility of an interim allocation in the mixed bidder setting. Nonetheless, these conditions are too intricate to optimize x U i ( ). We then introduce the concept of the lookahead auction for mixed bidders, simplifying the characterization of interim feasibility. To determine the revenueoptimal lookahead auction, we apply the variational method with interim feasibility constraints to Equation (1).

Interim Feasibility and Lookahead Auctions

For the single-bidder scenario, the constraints on x U i ( ) are simply 0 x U i (v) 1 for any v. In the multi-bidder case, we must also consider the implementability of an interim allocation. We first provide the following necessary and sufficient conditions for interim feasibility which is known as Border s theorem :

Proposition 1 ((Border 1991)). Denote the set of all possible bidder s classes as T. A set of interim allocation {x U i ( ), x V i ( )}i [n] is implementable if and only if S1, S2, . . . , Sn T we have:

i=1 E[xti i (vi)|θi Si] Pr(θi Si)

Pr θ ( i [n] : θi Si).

The constraints in Border s theorem are overly complex for optimizing x U i ( ) using the variational approach. As noted in Lemma 4, the interim allocations and payments are identical for a UM with value v and a VM with value gi(v). This insight leads us to introduce the concept of the lookahead auction in our mixed bidder setting as follows:

Definition 1 (Lookahead Auction). For bidder i with value vi, define the score as gi(vi) if this bidder is a UM, and vi if a VM. A lookahead auction for mixed bidders satisfies:

Symmetry: i, j and t U, V , xt i(v) xt j(v); Allocation: If the item is allocated, it goes to the bidder with the highest score.

Since we only consider symmetric mechanisms, we omit the subscript i. The following lemma characterizes the interim feasibility of x U( ) for a lookahead auction.

Lemma 5 (Interim feasibility inequality). An interim allocation (x U( ), x V ( )) of a lookahead auction is implementable if and only if for all θi = (t, v), we have xt(v) Pr [i has the highest score|θi] .

The proof is straightforward and we put it in full version.

Characterization of the Optimal Auction

For a single bidder, selling to a UM with positive virtual value is profitable without reducing revenue from VMs. Thus, x U(v) can reach 1 for sufficiently large v. However, in a lookahead auction, even a UM with value v U may lose to a VM with a value exceeding g(v U). Lemma 5 implies that the optimal implementable allocation function for VM when v [g(v U), v U] is:

x V (v) = min

q + (1 q) F V (v) n 1 ,

0 x U(u)du v U v

(8) For v [v U, v V ], we set x V (v) to maximize revenue while satisfying the interim feasibility inequality. Let y(v) =

R v 0 x U(u)du. The revenue is then:

0 y h U(v) + y y

x V (v) h V (v)dv

Treating y(v U) and y (v U) as initial values, g(v U) becomes fixed, making the second integral constant. We focus on optimizing the first integral. Using the definition from the previous section, the optimization problem becomes:

0 f(v, y, y , y )dv (9)

s.t. y (v)is monotone increasing, y (v) (q FU(vi) + (1 q) FV (v y

y ))n 1, y (v) 0 v, y (0)= 0.

By complementary slackness, the Euler-Lagrange equation (4) is violated under the optimal solution only when the interim feasibility constraint binds. Let y1(v) be the solution to ODE (4), and y2(v) be the solution to the ODE derived from the interim feasibility constraints:

y (v) = (q FU(v) + (1 q) FV (v y

y ))n 1. (10)

The optimal y(v) is then determined by the function with the smaller derivative between y1(v) and y2(v). The Euler-Lagrange equation (5) is a second-order ODE, but problem (9) only provides one initial value, y (0) = 0. This introduces a parameter C that affects revenue. For a fixed C, we can determine the optimal y( ) and corresponding REV(M). The optimal auction can then be found by searching all possible C values and selecting the one that maximizes revenue. In summary, Algorithm 2 numerically solves the revenueoptimal lookahead auction for multiple bidders. We discretize the integral interval with step size ε. Given y(v) and y (v), we use RK1(v) = (y(v + ε), y (v + ε), y (v + ε)) as an extrapolation oracle for ODE (5) s solution. Similarly, RK2(v) serves as an oracle for ODE (10) s solution. REV(v) is defined in the previous section with y (ε) as the parameter to be determined. Figure 1 illustrates the optimal allocation for both bidder types when n = 2, q = 0.4, and both FU and FV follow uniform distributions on [0, 1]. The green line represents the interim feasibility constraints, showing the probability of a score v being highest among all bidders. In the first phase, the Euler-Lagrange equation binds for both bidder types, with the yellow line below the green line, indicating possible non-allocation even with the highest score. The second phase begins when these lines coincide, binding the interim feasibility inequality and ensuring allocation for the highest score in this range. For VMs, the third phase s optimal allocation is determined by Eqn. (8).

Algorithm 2: Search optimal allocation for multiple bidders

v U sup{supp(F U)}, v V sup{supp(F V )} for all possible parameter C do REV(C) 0, y(ε) ε C, y (ε) C for j = 2ε, 3ε, . . . , v U do (y1(j), y 1(j), y 1 (j)) RK1(j ε) (y2(j), y 2(j), y 2 (j)) RK2(j ε) k arg mini{y i(j)|i {1, 2}} (y(j), y (j), y (j)) (yk(j), y k(j), y k(j)) REV(C)+ = REV(j) end for if v V v U y(v U )

y (v U ) then

REV(C)+ = R v V

v U y(v U )

x V (v) h V (v)dv

end if end for return The C with the highest REV(C)

Figure 1: Optimal allocation when n = 2, q = 0.4, the value of UMs and VMs both follow uniform distribution on [0, 1]

Future Directions

This work investigates optimal auction design for mixed bidders. We characterize allocation and payment rules under IR and IC constraints and design optimal auctions for single bidders and optimal lookahead auctions for multiple bidders.

It remains unknown whether the optimal auction in the multi-bidder case is a lookahead auction. Given their ease of implementation and proven optimality for UMs with iid values, we conjecture that it is also optimal for the mixed bidders with iid classes.

Another future direction is applying the simple versus optimal paradigm to our settings. While our derived optimal mechanism is complex and randomized, simpler alternatives like second-price auctions with reserves may provide constant approximations to the optimal for mixed-bidder auctions.

Acknowledgments This work was partially supported by the Ministry of Education, Singapore, under its Academic Research Fund Tier 1 (RG98/23).

References Aggarwal, G.; Badanidiyuru, A.; and Mehta, A. 2019. Autobidding with constraints. In Web and Internet Economics: 15th International Conference, WINE 2019, New York, NY, USA, December 10 12, 2019, Proceedings 15, 17 30. Springer. Balseiro, S.; Deng, Y.; Mao, J.; Mirrokni, V.; and Zuo, S. 2023. Optimal Mechanisms for a Value Maximizer: The Futility of Screening Targets. Available at SSRN 4351927. 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, 132 133. Border, K. C. 1991. Implementation of reduced form auctions: A geometric approach. Econometrica: Journal of the Econometric Society, 1175 1187. Chawla, S.; and Hartline, J. D. 2013. Auctions with unique equilibria. In Proceedings of the fourteenth ACM conference on Electronic commerce, 181 196. Chawla, S.; Hartline, J. D.; Malec, D. L.; and Sivan, B. 2010. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the forty-second ACM symposium on Theory of computing, 311 320. Daskalakis, C.; Deckelbaum, A.; and Tzamos, C. 2015. Strong duality for a multiple-good monopolist. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, 449 450. Deng, Y.; Mahdian, M.; Mao, J.; Mirrokni, V.; Zhang, H.; and Zuo, S. 2023. Efficiency of the Generalized Second-Price Auction for Value Maximizers. ar Xiv preprint ar Xiv:2310.03105. Deng, Y.; Mao, J.; Mirrokni, V.; Zhang, H.; and Zuo, S. 2022. Efficiency of the first-price auction in the autobidding world. ar Xiv preprint ar Xiv:2208.10650. Deng, Y.; Mao, J.; Mirrokni, V.; and Zuo, S. 2021. Towards efficient auctions in an auto-bidding world. In Proceedings of the Web Conference 2021, 3965 3973. Edelman, B.; Ostrovsky, M.; and Schwarz, M. 2007. Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. American economic review, 97(1): 242 259. Hart, S.; and Nisan, N. 2017. Approximate revenue maximization with multiple items. Journal of Economic Theory, 172: 313 347. Hart, S.; and Reny, P. J. 2015. Maximal revenue with multiple goods: Nonmonotonicity and other observations. Theoretical Economics, 10(3): 893 922. Jin, Y.; Lu, P.; Qi, Q.; Tang, Z. G.; and Xiao, T. 2020. Tight revenue gaps among simple and optimal mechanisms. ACM SIGecom Exchanges, 17(2): 54 61.

Lu, P.; Xu, C.; and Zhang, R. 2023. Auction Design for Value Maximizers with Budget and Return-on-Spend Constraints. In International Conference on Web and Internet Economics, 474 491. Springer. Lv, H.; Zhang, Z.; Zheng, Z.; Liu, J.; Yu, C.; Liu, L.; Cui, L.; and Wu, F. 2023. Utility maximizer or value maximizer: mechanism design for mixed bidders in online advertising. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, 5789 5796. Myerson, R. B. 1981. Optimal auction design. Mathematics of operations research, 6(1): 58 73. Varian, H. R. 2007. Position auctions. international Journal of industrial Organization, 25(6): 1163 1178.