Deterministic Implementation in Single-Item Auctions

1 Introduction

The central objective of mechanism design is to identify and characterize the set of outcomes that can be implemented by suitable mechanisms. Since the foundational contributions of [Hurwicz, 1960; Hurwicz, 1972], a substantial literature has developed across diverse market environments and under multiple solution concepts [Clarke, 1971; Dobzinski et al., 2022; Feldman and Shabtai, 2023; Groves, 1973; Myerson, 1979; Myerson, 1981; Myerson, 1982; Vickrey, 1961; You and Juarez, 2021].

This paper advances that agenda in the setting of singleitem auctions by studying the implementability of deterministic auctions, where allocation and payment rules are deterministic. Determinism is important in many applications, including antique auctions, spectrum sales, and platform marketplaces, where transparency, compliance, or operational simplicity may rule out randomization [Klemperer, 2004; Liu et al., 2024]. Recent work on single-item auctions shows that, for revenue maximization, optimal auctions can often be chosen as deterministic DSIC mechanisms in discrete settings, despite allowing randomized BIC mechanisms [Giannakopoulos and Hahn, 2024]. These optimality results, however, leave open a complementary question that is central to implementability: beyond the outcomes induced by optimizing a fixed objective, when does determinism preserve (or fail to preserve) the full set of achievable trade-offs and reduced forms? A precise account of the power and limitations of deterministic auctions is therefore both practically relevant and theoretically significant.

∗Corresponding author.

We take two complementary views. First, an outcomespace view that charts the set of achievable (revenue, welfare) pairs, together with its Pareto frontier. Second, a reducedform view that characterizes the interim allocations implementable by deterministic mechanisms. These two views allow us to assess determinism at the level of aggregate tradeoffs and at the level of allocation structure.

1.1 Implementation with Respect to (Revenue, Welfare) Pairs

Our first objective is to characterize which (revenue, welfare) pairs are attainable by deterministic DSIC auctions. For randomized auctions, the picture is well understood: one first identifies the extreme points and then takes convex combinations to generate the full attainable set. [Myerson and Satterthwaite, 1983] characterize the extreme points for the single-buyer case. [Likhodedov and Sandholm, 2003] extend this to multiple buyers. This program does not carry over to deterministic auctions, because a convex combination of two deterministic auctions is not necessarily deterministic. As a result, the results and techniques of [Likhodedov and Sandholm, 2003] do not apply, and the set of extreme points for deterministic auctions is not continuous.

We show that deterministic DSIC and deterministic BIC are not equivalent with respect to (revenue, welfare) pairs. There exists a pair that is implementable by a deterministic BIC auction but not by any deterministic DSIC auction. Prior results on revenue inequivalence between DSIC and BIC do not apply here, since they are confined to two-item environments [Tang and Wang, 2016; Yao, 2017]. To further delineate the boundary of this separation, we identify a restricted class of distributions under which randomized BIC auctions and deterministic DSIC auctions remain equivalent with respect to (revenue, welfare) pairs. In the continuous case, we obtain two levels of equivalence: under regularity we match the Pareto frontier, and under stronger distributional conditions (in the i.i.d. case) we match the entire attainable region.

1.2 Implementation with Respect to Interim Allocations

Our second objective is to characterize which interim allocations can be implemented by deterministic auctions. Here, "interim allocation" refers to the expected allocation probability, taken over the randomness in the other players' types, in the same sense as defined in [Myerson, 1981]. [Border, 1991] gives a necessary and sufficient condition, now called Border's theorem, for when an interim allocation (the "reduced form" in Border's terminology) is implementable by a randomized BIC auction. Building on this, [Manelli and Vincent, 2010] show that any interim allocation of a randomized BIC auction is also implementable by a randomized DSIC auction. Further, [Chen et al., 2019] prove that for continuous atomless priors, every interim allocation implementable by a randomized BIC auction is also implementable by a deterministic BIC auction. To the best of our knowledge, no analogous result is known for deterministic DSIC auctions. We show that an analogous equivalence fails for deterministic DSIC auctions. To show this separation, we introduce new techniques, most notably a deterministic version of Border's theorem.

1.3 Our Results

We study the power and limitations of deterministic auctions in single-item environments through two outcome notions: (revenue, welfare) pairs and interim allocations.

• Revenue-welfare outcomes. We characterize which (revenue, welfare) pairs are attainable by deterministic DSIC auctions. In discrete settings, we exhibit a counterexample (via computational enumeration) showing a pair that is implementable by a deterministic BIC auction but not by any deterministic DSIC auction, establishing a non-equivalence between the two. In contrast, under continuous regular priors, every Pareto-optimal (revenue, welfare) pair achievable by randomized BIC auctions is implementable by a deterministic DSIC auction. Moreover, in the i.i.d. continuous case, under Condition (1) (see Theorem 3), every (revenue, welfare) pair implementable by randomized BIC auctions is also implementable by a deterministic DSIC auction.
• Interim allocations. We provide a deterministic analogue of Border's theorem for two bidders under a strict monotonicity condition, yielding a necessary and sufficient condition under which an interim allocation is implementable by a deterministic DSIC auction. Using this characterization, we show that randomized BIC and deterministic DSIC auctions are not equivalent. For three bidders with constant interim allocations, we further derive a necessary and sufficient condition for implementability under deterministic DSIC.

1.4 RelatedWork

[Diakonikolas et al., 2012] define the subset of (revenue, welfare) pairs that are undominated in both coordinates as Pareto points, and call their collection the Pareto curve, i.e., the upper-right boundary of the attainable set. They show that even with two buyers facing asymmetric discrete priors, this curve need not be concave, and that deciding whether a given point is achievable by a deterministic auction is NP-hard. In contrast, we prove that under continuous and regular priors, the Pareto frontier of randomized BIC mechanisms coincides with that of deterministic DSIC mechanisms.

[Arigapudi, 2018] studies the related implementability problem in a symmetric environment. They give necessary and sufficient conditions under which the interim allocation of a symmetric BIC auction is implementable by a symmetric DSIC auction. We consider the two-buyer case without symmetry and our results specialize to theirs. Moreover, our theorem (Theorem 4) does not assume that the target interim allocation is implementable by any deterministic BIC mechanism. On the randomized side, [Border, 2007] extend Border's theorem to asymmetric settings, and [Che et al., 2013] provide a clean network-flow proof. For deterministic implementability, [Bikhchandani et al., 2006] show that a deterministic social choice function over multi-dimensional types is DSIC if and only if it is weakly monotone. [Gershkov et al., 2013] further broaden equivalence results for randomized BIC and randomized DSIC mechanisms.

The study of attainable (revenue, welfare) outcomes is a recurring theme in auction theory (e.g., [Bergemann et al., 2015; Ma, 2022]). [Hartline and Roughgarden, 2008] design an auction that maximizes buyer surplus (welfare minus revenue), which corresponds to an extreme point of the outcome space. [Pai, 2009] analyzes competition among sellers, yielding a revenue-utility trade-off for buyers. [Kleinberg and Yuan, 2013] establish lower bounds on the revenue-towelfare ratio under various feasibility constraints. In a similar spirit, [Bachrach et al., 2014] optimize a composite objective "λ1 · revenue + λ2 · welfare + λ3 · click yield" to balance stakeholder goals, and [Shen and Tang, 2017] propose a parametric family that optimizes a linear combination of revenue and welfare inside monotone transformations, achieving near-optimal revenue with practical implementability.

[Giannakopoulos and Hahn, 2024] study discrete singleitem optimal auction design and show that, for revenue maximization (and more generally linear objectives), an optimal deterministic DSIC mechanism can be chosen via an LPduality/KKT characterization. Our paper is complementary: instead of identifying an optimizer for a fixed objective, we characterize which (revenue, welfare) trade-offs and interim allocations are implementable under determinism, and we obtain separations between deterministic BIC and deterministic DSIC. Since their techniques are tailored to optimality for a given objective, they do not imply our implementability questions or preclude the separations we establish.

2 Preliminaries

There are n buyers competing for a single indivisible item. Let [n] = {1, 2, · · · , n} represent the set of buyers. Buyer i has a private valuation vi ∈ R≥0, drawn independently from a (not necessarily identically distributed) prior distribution Fi with density function fi. We use v = (v1, v2, · · · , vn) to denote the valuation profile of all n buyers and v-i = (v1, · · · , vi-1, vi+1, · · · , vn) to denote the valuation profile of all buyers except buyer i. Each buyer i submits a bid bi ∈ R≥0, and the bid profile is given by b = (b1, b2, · · · , bn), with b-i = (b1, · · · , bi-1, bi+1, · · · , bn) representing the bid profile of all buyers except buyer i. Throughout, we restrict attention to truthful (incentive-compatible) mechanisms. We use xi(v) : Rn≥0 → [0, 1], pi(v) : Rn≥0 → R≥0 to denote the ex-post allocation and the ex-post payment, respectively. An auction is deterministic if xi(v) ∈ {0, 1} for any i and any v. With a slight abuse of notation, we use xi(vi), pi(vi) to denote interim allocation and interim payment, respectively. The intended meaning will be clear from context. xi(vi) and pi(vi) are defined as expectations over v-i. Specifically, the interim allocation can be expressed as xi(vi) = ∫v-i xi(vi, v-i)f-i(v-i)dv-i where f-i(v-i) = ∏j̸=i fj(vj) and dv-i = dv1 · · · dvi-1dvi+1 · · · dvn. The interim payment can be expressed as pi(vi) = ∫v-i pi(vi, v-i)f-i(v-i)dv-i.

We consider the BIC, DSIC, and interim Individually Rational (IR) constraints in mechanism design. A mechanism is BIC if truth-telling is the optimal strategy for each buyer, given that they have probabilistic beliefs about the valuations of other buyers. A mechanism is DSIC if truth-telling always maximizes a buyer's utility, regardless of the actions of other buyers. A mechanism is interim IR if each buyer receives a non-negative expected utility from participating. Formally, these constraints are defined as follows:

• BIC constraint: vi ·xi(vi)-pi(vi) ≥ vi ·xi(bi)-pi(bi), for all i, vi, bi ∈ R≥0;
• DSIC constraint: vi · xi(vi, b-i) - pi(vi, b-i) ≥ vi · xi(bi, b-i) - pi(bi, b-i), for all i, vi, bi ∈ R≥0, and b-i ∈ Rn-1 ≥0 ;
• Interim IR constraint: vi · xi(vi) - pi(vi) ≥ 0, for all i, vi.

According to [Myerson, 1981], a BIC auction is characterized by the following conditions: xi(vi) is nondecreasing (monotone) in vi for all i, and the payment function satisfies the identity pi(vi) = vi · xi(vi) - ∫ vi 0 xi(t)dt+pi(0). Under interim IR, we normalize pi(0) = 0.

According to [Nisan et al., 2007], a DSIC auction is characterized by the following conditions: xi(vi, b-i) is nondecreasing (monotone) in vi for all i and any given b-i, and the payment function satisfies vi · xi(vi, b-i) - ∫ vi 0 xi(t, b-i)dt. Notably, any DSIC auction is also BIC.

The formulas for expected welfare and expected revenue are as follows:

where ϕi(vi) = vi - 1-Fi(vi) fi(vi) , known as the "virtual value" in [Myerson, 1981]. We also use the quantile space [Bulow and Roberts, 1989]. Let qi = Fi(vi) ∈ [0, 1], and with a slight abuse of notation, let vi(qi) = F -1 i (qi), the inverse function of Fi(vi). Then, in the quantile space, we have

where ˆ ϕi(qi) = vi(qi)-(1-qi)v′i (qi), and ˆxi(qi) : [0, 1] → [0, 1] is the interim allocation when Fi(vi) = qi in the quantile space.

A point P is a Pareto point of the range of the (revenue, welfare) pairs if there is no point P ′ ̸= P in the range that dominates P (coordinate-wise).

Definition 1 (Implementability). Fix a prior profile F = (Fi)i∈[n] and a class of feasible mechanisms M. For each mechanism M = (x, p) ∈ M, let xM = (xMi )i∈[n] denote its interim allocation profile, where xMi (vi) := Ev-i∼F-i [xi(vi, v-i)], and let REV(M) and WEL(M) denote the expected revenue and expected welfare induced by M, respectively.

1. A pair (R,W) ∈ R2≥0 is said to be M-implementable if there exists a mechanism M ∈ M such that (REV(M), WEL(M)) = (R, W ).
2. An interim allocation profile ¯x = (¯xi)i∈[n] is said to be M-implementable if there exists a mechanism M ∈ M such that, for every bidder i ∈ [n], xMi (vi) = ¯xi(vi) for all vi except possibly on a set of types with probability zero under Fi.

We present a variant of Border's theorem [Border, 1991; Che et al., 2013] that, in our setting, characterizes exactly when an interim allocation is implemented by a randomized BIC auction.

Border's theorem: an interim allocation profile (x1(·), · · · , xn(·)) can be implemented by a randomized BIC auction if and only if

In the i.i.d. symmetric case, in quantile space, it simplifies to

where ˆx denotes the common interim allocation function.

The inequality compares two probabilities that must be consistent in any feasible single-item allocation. Fix thresholds (v1, · · · , vn) and consider the event that every bidder i's type exceeds vi. The left-hand side, ∑i ∫ ∞ ti=vi xi(ti)fi(ti)dti, is the ex-ante probability that the mechanism allocates the item to some bidder from within the set of "above-threshold" types (counting bidder-by-bidder).

The right-hand side, 1 - ∏i Fi(vi), is the probability that at least one bidder is above her threshold. Since only one item can be allocated, the probability of allocating the item to an above-threshold bidder can never exceed the probability that such a bidder exists. Border's theorem states that this family of inequalities (for all thresholds) is not only necessary but also sufficient for interim implementability. In our paper, this characterization lets us work directly with interim allocation rules in value/quantile space: we propose candidate interim allocations ˆx, verify feasibility by checking the corresponding Border constraints (e.g., the symmetric quantile form ∫ 1 q ˆx(t)dt ≤ 1-qn n ), and then optimize linear objectives such as welfare and (virtual) revenue over this feasible set. Finally, tightness of a Border constraint has a clean meaning: equality at (v1, · · · , vn) means there is no slack in the event "someone is above threshold", i.e., whenever at least one bidder exceeds her threshold, the mechanism allocates the item with probability 1 to an above-threshold bidder. Strict inequality indicates that with positive probability the mechanism leaves allocation probability "unused" relative to that event (for example, it sometimes does not allocate to any above-threshold bidder even though one exists). This interpretation is key for understanding the randomized benchmark region and for contrasting it with the additional structure imposed by deterministic DSIC implementability later in the paper.

Due to space limitations, some lemmas and most of the proofs are included in the full version of the paper 1 .

3 Implementation with Respect to (Revenue, Welfare) Pairs

3.1 Nonequivalence of Deterministic BIC and Deterministic DSIC Auctions with Respect to Pareto Points in the Discrete Case

In Section 2, values are drawn from continuous distributions. Here we consider an i.i.d. discrete prior: each vi takes values in V = {v1 , · · · , vm} with probability vector π = (π1, · · · , πm), where πk = Pr[vi = vk ]. A deterministic mechanism (xi, pi) specifies an ex post allocation xi(v) ∈ {0, 1} and payment pi(v) for every profile v ∈ V n . We evaluate it by expected welfare and expected revenue under the prior π:

Equivalently, Ev∼πn[·] denotes a finite sum over all v = (v1, · · · , vn) ∈ V n , where each coordinate vi = vki is weighted by πki . Hence the profile v has weight ∏i∈[n] πki .

We give an example in the i.i.d. discrete case to derive the following theorem.

1 The full paper is available at https://arxiv.org/pdf/2512.17386.

Theorem 1. There exists a Pareto point P that is implemented by a deterministic BIC auction but cannot be implemented by any deterministic DSIC auction in the i.i.d. discrete case.

Suppose that there are two identical buyers, each with three types: t1 = 100, t2 = 10, t3 = 1, occurring with probabilities p1 = 0.8, p2 = 0.15, p3 = 0.05 respectively. For each type of buyer 1 and buyer 2, the item can be allocated to no one, to buyer 1, or to buyer 2. Thus, we have to check 39 = 19683 deterministic allocation profiles. Similar to [Diakonikolas et al., 2012], to consider Paretooptimal points, we can assume without loss of generality that payments are specified on the finite type space. Therefore, we can enumerate all deterministic allocation rules on the finite type space and, for each, compute supporting payments and check BIC/DSIC/IR 2 . Through experiments, we find that (WEL = 96.2275, REV = 85) is a Pareto-optimal point among all outcomes implementable by deterministic BIC mechanisms (see Figure 1). Only partial figure is provided here since the complete figure is too large. The Pareto-

optimal point (WEL = 96.2275, REV = 85) can be achieved only by four deterministic BIC auctions, with i ∈ {1, 2} and j ∈ {1, 2}, as shown in Table 1. However, none of these auctions is DSIC.

Note that in Table 1, buyer j and buyer i denote any buyer. Therefore, the four deterministic auctions are: (1) i = 1, j = 1; (2) i = 1, j = 2; (3) i = 2, j = 1; (4) i = 2, j = 2. Here, we use the case i = 2, j = 1 to illustrate that this deterministic auction is BIC but not DSIC. For buyer 1, we can get the interim allocation, that is x1(1) = 0.05, x1(10) = 0.15 and x1(100) = 0.2. For buyer 2, we can get the interim allocation, that is x2(1) = 0, x2(10) = 0 and x2(100) = 1. Clearly, the allocation functions of both buyers are monotonic. The welfare generated by buyer 1 is 0.05 × 1 × 0.05 + 0.15 × 10 × 0.15 + 0.2 ×

2 Otherwise, there would be infinitely many feasible actions.

100 × 0.8 = 16.2275; the welfare generated by buyer 2 is 0 × 1 × 0.05 + 0 × 10 × 0.15 + 1 × 100 × 0.8 = 80; the total welfare is 16.2275 + 80 = 96.2275. As for revenue, we have to design payment rules for both buyers. However, unlike the case with continuous types, when types are discrete, there can be multiple possible payment rules that satisfy BIC. Based on the established allocation rule, we can formulate an optimization problem that maximizes the seller's expected revenue while incorporating the BIC constraints as part of the feasible set. By solving this constrained optimization problem, we can derive the corresponding payment functions for both buyers. Finally, we can get the interim payment, that is p1(1) = 0.05, p1(10) = 1.05, p1(100) = 6.05, p2(1) = 0, p2(10) = 0, p2(100) = 100. The revenue generated by buyer 1 is 0.05×0.05+1.05×0.15+6.05×0.8 = 5; the revenue generated by buyer 2 is 0×0.05+0×0.15+100×0.8 = 80; the total revenue is 5 + 80 = 85.

Although the interim allocation rules are monotone (hence the mechanism is BIC), the ex-post allocation rule is not monotone in a bidder's own report for fixed opponent reports, so it cannot be DSIC. For instance, fixing buyer 2's report at v2 = 1, buyer 1 wins when v1 = 1, loses when v1 = 10, and wins again when v1 = 100, which violates the monotonicity requirement for deterministic DSIC implementability. Hence, none of these four auctions can satisfy the DSIC constraints, even though they all achieve the same Pareto-optimal (revenue, welfare) pair under BIC.

3.2 Equivalence of Deterministic DSIC and Randomized BIC Auctions with Respect to Pareto Points for Regular Distributions

In this subsection, we assume that the buyers' prior distributions are continuous and atomless, but not necessarily identical.

Theorem 2. If each buyer's prior distribution is regular, i.e., the virtual value ϕ(v) = v - 1-F(v) f(v) is increasing, then any Pareto point implementable by a randomized BIC auction is also implementable by a deterministic DSIC auction.

We prove the theorem in two steps. In the first step, starting from a randomized BIC mechanism, we transform its allocation rule by modifying only one buyer's interim allocation at a time, while keeping the other buyers' interim allocations fixed. We repeat this procedure for all n buyers. Under the regularity condition, each transformation weakly improves both expected welfare and expected revenue, so the final mechanism weakly dominates the original one in the (REV,WEL) space. In the second step, we show that the last (transformed) allocation rule admits a deterministic DSIC implementation. Since the original point is already Pareto-optimal among outcomes achievable by randomized BIC mechanisms, the weak improvement must be tight. Therefore, the deterministic DSIC mechanism implements the same Pareto point.

3.3 Equivalence of Deterministic DSIC and Randomized BIC Auctions with Respect to All (Revenue, Welfare) Pairs for i.i.d Distributions

In this subsection, we focus on the i.i.d case with a continuous and atomless distribution F and utilize the quantile space. Since buyers' private valuations are independently drawn from a common distribution F , we omit the subscripts on vi and qi and write them simply as v and q. We provide sufficient conditions under which the range of (revenue, welfare) pairs achievable by deterministic auctions is equal to that of randomized BIC auctions.

Theorem3. If the prior distributionF is third-order differentiable and satisfies the following condition, then any (revenue, welfare) pair that is implementable by a randomized auction is also implementable by a deterministic DSIC auction.

It is not hard to verify that all uniform distributions and power-law distributions F (v) = 1-v-α with α ≤ 1, including the equal-revenue distributions, satisfy the condition.

The proof sketch is as follows: we first characterize the boundary of randomized BIC auctions, then we prove that each (revenue, welfare) pair on the boundary can be implemented by a deterministic auction (see Lemmas 1 - 2). Finally we prove that each (revenue, welfare) pair strictly between the revenue-maximizing boundary and the revenue-minimizing boundary at the same welfare level can be implemented by a deterministic auction (see Lemma 4).

We begin by analyzing the boundary of (revenue, welfare) pairs for randomized BIC auctions. For convenience, we assume that F has full support on [0, 1]. By [Maskin and Riley, 1984], it is without loss of generality to only consider symmetric auctions. Define P (q) = ∫ 1 q ˆx(t)dt and we have

Note that P ′ (q) = -ˆx(q) ≤ 0 and P ′′ (q) = -ˆx′ (q) ≤ 0 for a randomized BIC auction. By the feasibility from Border's theorem, P(q) is bounded by P(q) ≤ 1-qn n . We fix WEL = c where c is a constant, and then compute the range of REV. Thus, the optimization problem is

We define a class of auctions called "piecewise auctions". We show that any point on the boundary of the feasible range can be implemented by a piecewise auction.

Definition 2 (Piecewise auctions). A (symmetric, randomized) BIC auction is a piecewise auction if it satisfies one of the following two conditions:

1. There exists 0 ≤ r1 < r2 ≤ 1 such that

• P ′ (q) = 0, for 0 < q ≤ r1,
• P ′ (q) = -k, for r1 < q ≤ r2, where k is a constant and 0 ≤ k ≤ rn 2 -rn 1 n(r2-r1) ,
• P(q) = 1-qn n , for r2 < q ≤ 1.
• There exists 0 ≤ r1 < r2 ≤ 1 such that
• P ′ (q) = 0, for 0 < q ≤ r1,
• P(q) = 1-qn n , for r1 < q ≤ r2,

According to the piecewise auctions we defined, we introduce the following Lemmas. Lemma 1 shows that any maximum and any minimum solutions of optimization problem (2) must be a piecewise auction, so all boundary points of the (REV,WEL) region induced by randomized BIC auctions are attained by piecewise auctions. Lemma 3 then constructs, for each piecewise auction, a deterministic DSIC mechanism whose total interim allocation at every valuation coincides with that of the piecewise auction; together with Lemma 2, which states that identical total interim allocations imply identical revenue and welfare, this implies that every boundary point can be implemented by a deterministic DSIC auction.

Lemma 1. If the condition (1) is satisfied, then any maximum and any minimum solutions of optimization problem (2) are a piecewise auction.

Lemma 2. For any common prior distribution, if two auctions with interim allocation profile (x1(v), x2(v), · · · , xn(v)) and (y1(v), y2(v), · · · , yn(v)) respectively satisfy for any v,

then the two auctions' revenue and welfare are the same.

By Lemma 2, we can get Lemma 3.

Lemma 3. All (revenue, welfare) pairs of piecewise auctions can be implemented by deterministic DSIC auctions.

Lemma 4 further shows that, for any fixed welfare level, piecewise auctions span a continuous interval in the revenue dimension, so all interior points on the same welfare line are also implemented by piecewise auctions (and hence by deterministic DSIC mechanisms). Therefore, the entire (REV,WEL) region attainable by randomized auctions can be implemented by deterministic DSIC auctions, which completes the proof of Theorem 3.

Lemma 4. One piecewise auction can continuously transfer to another through a sequence of piecewise auctions with the welfare fixed.

4 Implementations with Respect to Interim Allocations

4.1 Two Buyers

In this subsection, we analyze the necessary and sufficient condition such that an interim allocation profile can be implemented by a deterministic DSIC auction, also known as Border's Theorem in the deterministic case. We focus on the two-buyer case, with continuous and atomless prior distributions, which are not necessarily symmetric. The analysis is conducted in the quantile space.

Theorem 4. A strictly increasing interim allocation profile (ˆx1(q1), ˆx2(q2)) is implementable by a deterministic DSIC auction if and only if

Moreover, if the item is always sold for the deterministic DSIC auction, then (3) turns into

The proof sketch is as follows: we work on the quantile space [0, 1]2 and represent any deterministic allocation rule as a three-coloring C ∈ {0, 1, 2}, where 0, 1, and 2 indicate no sale, buyer 1 wins, and buyer 2 wins, respectively. We then perform a measure-preserving rearrangement to obtain a new coloring C ′ that keeps each buyer's interim allocation unchanged. Concretely, for each q1, the measure of points colored 1 in column q1 remains ˆx1(q1), and for each q2, the measure of points colored 2 in row q2 remains ˆx2(q2). This rearrangement produces a structured geometry where the plane is separated by two monotone boundary curves q2 = ˆx1(q1) and q1 = ˆx2(q2), and each buyer's winning set has a threshold form. In this form, monotonicity in each buyer's own quantile is immediate, so the induced allocation can be implemented by a deterministic DSIC auction via the standard critical-threshold characterization. Finally, single-item feasibility requires the two winning regions to be disjoint, which is equivalent to the two monotone boundaries not crossing, and this gives ∀q, ˆx2(ˆx1(q)) ≤ q.

Nonequivalence of Randomized BIC and Deterministic DSIC Auctions with Respect to Interim Allocations

Based on Theorem 4, we can prove the nonequivalence between randomized BIC and deterministic DSIC auctions with respect to interim allocations. A straightforward approach is to consider the sum of interim allocations given a valuation v.

Corollary 1. There exists an interim allocation profile (x1(v), · · · , xn(v)) that is implementable by a randomized BIC auction, but there is no deterministic DSIC auction with interim allocation profile (y1(v), · · · , yn(v)) such that for any v,

4.2 Three Buyers with Constant Interim Allocations

Theorem 4 becomes extremely complex when extended to cases with three or more buyers. Suppose there are three buyers with constant interim allocations, i.e. xi(v) = ci, ∀v, i = 1, 2, 3. We provide a necessary and sufficient condition for interim allocations to be implemented by a deterministic DSIC auction.

Theorem 5. The constant interim allocation profile for 3 buyers is implementable by a deterministic DSIC auction if and only if

Proof. We first prove the "only if" direction: given constant interim allocation rule x1, x2, x3 in a deterministic DSIC auction, then condition (5) holds.

Due to the property of deterministic DSIC and constant interim allocation rule, we have the following statement:

It means that a buyer's allocation rule does not depend on his own value. In the following proof we ignore the unsatisfactory set which is measured 0 and has no effect to results.

Define three valuation domain sets: A = {(b, c) : x1(v1, b, c) = 1} for ∀v1, B = {(a, c) : x2(a, v2, c) = 1} for ∀v2 and C = {(a, b) : x3(a, b, v3) = 1} for ∀v3. Each set represents two players' valuation profile when the mechanism allocates the item to the remaining player.

Define the projection of set A in each dimension as Ab = {b : ∃c s.t. (b, c) ∈ A} and Ac = {c : ∃b s.t. (b, c) ∈ A}. Define Ba,Bc,Ca,Cb similarly.

We next claim that Ba∩Ca = ∅, Ab∩Cb = ∅, Ac∩Bc = ∅. Suppose Ba ∩ Ca ̸= ∅, let a∗ be an element in Ba ∩ Ca. Assume (a∗ , c∗ ) ∈ B and (a∗ , b∗ ) ∈ C. By definition of B, x2(a∗ , b∗ , c∗ ) = 1, while by definition of C, x3(a∗ , b∗ , c∗ ) = 1 which leads to a contradiction. So Ba and Ca do not overlap. Same argument applies for Ab and Cb, Ac and Bc.

The interim allocation c1 = |A| is bounded by |Ab||Ac| ≤ y1(1 - y2), since Ab and Ac are projections of A.

Thus, the interim allocation profile c1, c2, c3 is implementable implies that there exists y1, y2, y3 ∈ [0, 1] such that

We have

That is, (1-c2)y2 1 + (c2 - c1 + c3 - 1)y1 + c1(1 - c3) ≤ 0. Due to the formula above has a solution for y1, we have

That is, (c1 + c2 + c3 - 1)2 ≥ 4c1c2c3. Note that

1 ≥ Ev1,v2,v3 [x1(v1, v2, v3) + x2(v1, v2, v3) + x3(v1, v2, v3)]

= Ev1 [x1(v1)] + Ev2 [x2(v2)] + Ev3 [x3(v3)]

= c1 + c2 + c3.

Consequently, we have 1 - c1 - c2 - c3 ≥ 2√c1c2c3.

For the "if" direction: define ∆ = (c1 + c2 + c3 - 1)2 - 4c1c2c3 and suppose ∆ ≥ 0. We choose y1 = 1+c1-c2-c3+√∆ 2(1-c2) , y2 = 1+c2-c1-c3+√∆ 2(1-c3) , y3 = 1+c3-c2-c1+√∆ 2(1-c1) .

Then, we construct an auction with the following allocation rule, which is deterministic DSIC.

• x1(v1, v2, v3) = 1 if and only if v2 ≤ y1 and v3 > y2.
• x2(v1, v2, v3) = 1 if and only if v3 ≤ y2 and v1 > y3.
• x3(v1, v2, v3) = 1 if and only if v1 ≤ y3 and v2 > y1.

Finally, we have to prove that "Except for a zero measure of (b, c) ∈ [0, 1]2 , either x1(v, b, c) = 0, ∀v or x1(v, b, c) = 1, ∀v":

According to the definition of deterministic DSIC auction, given (b, c), there exist a critical value cr(b, c) such that

• x1(v, b, c) = 0, if v < cr(b, c),
• x1(v, b, c) = 1, if v > cr(b, c),
• x1(v, b, c) = 0 or x1(v, b, c) = 1, if v = cr(b, c).

Define A1 = {(b, c)|cr(b, c) = 0}, A2 = {(b, c)|cr(b, c) < 1}. Clearly A1 ⊆ A2. Note that

Hence |A1| = |A2|, and since A1 ⊆ A2, we must have |A2\A1| = 0. But A2\A1 = {(b, c) : 0 < cr(b, c) < 1}. Therefore, except for a zero-measure set of (b, c), we have cr(b, c) ∈ {0, 1}, which implies x1(v, b, c) is constant in v (up to the boundary point v = 0 or v = 1, which does not affect interim allocations). This completes the proof.

5 Discussion

We study the implementation power of deterministic singleitem auctions from two complementary perspectives: attainable (revenue, welfare) trade-offs and implementable interim allocation rules. Our results delineate a clear gap between deterministic BIC and deterministic DSIC, while also identifying distributional regimes where deterministic DSIC can match the outcomes of randomized benchmarks. Two natural directions follow. First, it remains open how far the current distributional assumptions can be weakened, and whether broader families of priors admit the same outcome equivalence. Second, our interim-allocation characterization is currently limited to two bidders (and a restricted three-bidder case). Extending it to general n, even under structured restrictions such as constant or low-complexity reduced forms, would substantially sharpen the boundary of deterministic implementability.

Acknowledgments

Zihe Wang was supported by the National Natural Science Foundation of China (Grant No. 62572476), the Fund for Building World-Class Universities (Disciplines) of Renmin University of China, and the Key Laboratory of Interdisciplinary Research of Computation and Economics (Shanghai University of Finance and Economics), Ministry of Education.