Takuro Yamashita
email: takuro.yamashita@tse-fr.eu

Shuguang Zhu
email: zhu.shuguang@mail.shufe.edu.cn

Thomas Mariotti

Renato Gomes

Jiangtao Li

Pierre Boyer

Takakazu Honryo

Raphaël Levy

Andras Niedermayer

Chengsi Wang

Yi-Chun Chen

Tilman Börgers

Takashi Kunimoto

On the Foundations of Ex Post Incentive Compatible Mechanisms *

 and Bergemann and Morris (2009b). Conversely, if the environment exhibits ordinal interdependence, which is typically the case with multi-dimensional environments (e.g.

Introduction

The recent literature on mechanism design provides a series of studies on the robustness of mechanisms, motivated by the idea that a desirable mechanism should not rely too heavily on the agents' common knowledge structure.1 One approach taken in the literature is to adopt stronger solution concepts that are insensitive to various common knowledge assumptions. For instance, in private-value environments, [START_REF] Segal | Optimal pricing mechanisms with unknown demand[END_REF] studies dominant-strategy incentive compatible sales mechanisms. In interdependent-value environments, [START_REF] Dasgupta | Efficient auctions[END_REF] study efficient auction rules that are independent of the details under the concept of ex post incentive compatibility.

However, a mechanism that achieves desired outcomes without the agents' common knowledge assumption does not immediately imply dominant-strategy or ex post incentive compatibility. In revenue maximization in private-value auction (under "regularity" conditions), [START_REF] Chung | Foundations of dominant-strategy mechanisms[END_REF] fill in this gap by establishing the maxmin and Bayesian foundation of the optimal dominant-strategy mechanism, in the following sense. Consider a situation where the seller in an auction (principal) only knows a joint distribution of the bidders' (agents) valua-tion profile for the auctioned object, which may be based on data about similar auctions in the past. On the other hand, he does not have reliable information about the bidders' beliefs about each other's value. For example, the bidders may have more or less information than the seller, or may simply have a "wrong" belief (from the seller's point of view) for various reasons. Thus, the seller's objective is to find a mechanism that achieves a good amount of revenue regardless of the bidders' (higher-order) beliefs. Note that, in a dominant-strategy mechanism, it is always an equilibrium for each bidder to report his true value, and therefore, it always guarantees the same level of expected revenue. On the other hand, in non-dominant-strategy mechanisms, expected revenue may vary with the bidders' (higher-order) beliefs. In the definition of [START_REF] Chung | Foundations of dominant-strategy mechanisms[END_REF], there is a maxmin foundation for a dominant-strategy mechanism if, for any nondominant-strategy mechanism, there is a possible belief of the seller with which the dominant-strategy mechanism achieves (weakly) higher expected revenue than the non-dominant-strategy mechanism. 2In this paper, we examine the existence of such foundations for ex post incentive compatible mechanisms in interdependent-value environments. Our main observation is that the key property that guarantees such foundations is what we call the cardinal vs. ordinal interdependence. To explain these concepts, imagine an auction problem, where each bidder's willingness-to-pay depends both on his own type and the other bidders' types. If one type of each bidder always has a higher valuation for the good than another type regardless of the other bidders' types (even if each type's valuation itself may vary with the others' types), then we say that the environment exhibits only cardinal interdependence. Conversely, if the types cannot be ordered in such a uniform manner with respect to the others' types, then we say that the environment exhibits ordinal interdependence. 3We first show that, in the environments with only cardinal interdependence, (both maxmin and Bayesian) foundations exist for ex post mechanisms. This includes, for example, private-value environments (in this sense, our result is a generalization of [START_REF] Chung | Foundations of dominant-strategy mechanisms[END_REF]), and the one-dimensional environments of [START_REF] Dasgupta | Efficient auctions[END_REF] and Bergemann and Morris (2009b).

Conversely, if the environment exhibits ordinal interdependence, which is typically the case with multi-dimensional environments (e.g., a player's private information comprises a noisy signal of the common value of the auctioned good and an idiosyncratic private-value parameter), then in general, ex post mechanisms do not have foundation. That is, there exists a non-ex-post mechanism that achieves strictly higher expected revenue than the optimal ex post mechanism, regardless of the agents' higher-order beliefs.

Regarding the foundation results, [START_REF] Chen | Revisiting the foundations of dominant-strategy mechanisms[END_REF] consider a general class of private-value environments where agents have multi-dimensional payoff types, and show that if the environment satisfies the uniform-shortest-path-tree property, then the maxmin (and Bayesian) foundation exists for dominant-strategy mechanisms. This property simply means that, for any allocation rule the principal desires to implement, the set of binding constraints is invariant. This holds true in the single-good auction environment of [START_REF] Chung | Foundations of dominant-strategy mechanisms[END_REF] with regularity, and in this sense, their result generalizes that of [START_REF] Chung | Foundations of dominant-strategy mechanisms[END_REF], keeping the private-value assumption. Our work is a complement to [START_REF] Chen | Revisiting the foundations of dominant-strategy mechanisms[END_REF] in that we consider interdependent-value environments. For our foundation result (Theorem 1), a similar property to their uniform-shortest-path-tree property holds, which suggests that some of their argument may be applicable even in interdependent-value environments.

Regarding the no-foundation results, there are several papers in the literature that provide examples or a restrictive class of environments in which (various versions of) foundations for dominant-strategy or ex post mechanisms do not exist. For example, for interdependent-value environments, [START_REF] Bergemann | Robust implementation in direct mechanisms[END_REF] provide examples in the context of implementation of certain ("nonseparable") social choice correspondences, [START_REF] Jehiel | The limits of ex post implementation[END_REF] provide an example for revenue maximization in sequential sales. [START_REF] Chen | Revisiting the foundations of dominant-strategy mechanisms[END_REF] also provide an instance of environment where, without their uniform-shortest-path-tree property, there might not exist a foundation for dominant-strategy mechanisms, even in private-value environments. Our work contributes to this line of research by providing a class of environments with a nofoundation result (and sufficient conditions on the primitives in that environment), and the economic intuition based on the cardinal vs. ordinal interdependence.

Other closely related papers include [START_REF] Bergemann | Robust implementation in direct mechanisms[END_REF] and Börgers (2017). In interdependent-value environments, [START_REF] Bergemann | Robust implementation in direct mechanisms[END_REF] show that any separable social choice correspondence that is implementable given any (higher-order) belief structure of the agents must satisfy ex post incentive compat-ibility. In this sense, they provide another sort of foundation for ex post incentive compatible mechanisms. Their separable social choice correspondence necessarily admits a unique non-monetary allocation for each payoff-type profile, and hence, in general, excludes revenue maximization as the principal's objective. Thus, our work is complementary to theirs in that we consider revenue maximization. [START_REF] Börgers | Foundations of dominant-strategy mechanisms: a comment on Chung and Ely (2007)[END_REF] criticizes the foundation theorems by constructing a non-dominantstrategy (or more generally, a non-ex-post) mechanism that yields weakly higher expected revenue than the optimal dominant-strategy mechanism for any belief structure of the agents, while it yields strictly higher expected revenue for some belief structures. Our no-foundation result is stronger in that it provides a strict improvement in expected revenue for any (higher-order) belief structure, though under stronger conditions on the environment.

One may wonder how the "generic constancy" result by [START_REF] Jehiel | The limits of ex post implementation[END_REF] is related (if any) to our foundation or no-foundation results. Recall that, for their result, a crucial assumption is that each agent's relative valuation -the difference in valuation between any two alternativesis everywhere strictly responsive to one's own signal. This is perhaps a reasonable assumption for example in a voting environment, but typically violated in "privategoods" environments such as in auction (see [START_REF] Bikhchandani | Ex post implementation in environments with private goods[END_REF] more about this point). In this sense, we think that their result is basically orthogonal to ours.

Model

There is a finite set of risk-neutral agents, I = {1, 2, . . . , I}. Agent i's privatelyknown payoff type is θ i ∈ Θ i ⊆ R d , where we assume |Θ i | = N for each i as in [START_REF] Chung | Foundations of dominant-strategy mechanisms[END_REF]. A payoff-type profile is written as θ = (θ 1 , . . . , θ I ) ∈ Θ 1 × . . . × Θ I = Θ. The principal's (subjective) prior belief for θ is given by f ∈ ∆(Θ), where we assume f (θ) > 0 for all θ ∈ Θ.

Each agent i's willingness-to-pay for q i ∈ Q i ⊆ R + units of the good is denoted by v i (q i , θ). We assume that 0

∈ Q i , |Q i | < ∞, 4 v i (0, θ) = 0, and v i (•, θ) is
increasing for all θ. Moreover, as a standard single-crossing condition, we assume that: Assumption 0. For each θ i = θ i , and θ -i , we have either

v i (q i , θ i , θ -i ) -v i (q i , θ i , θ -i ) > v i (q i , θ i , θ -i ) -v i (q i , θ i , θ -i ), ∀q i > q i ; or v i (q i , θ i , θ -i ) -v i (q i , θ i , θ -i ) < v i (q i , θ i , θ -i ) -v i (q i , θ i , θ -i ), ∀q i > q i .
In the first (second) case, we denote θ i

θ -i i θ i (θ i ≺ θ -i i θ i , respectively).
Clearly, the payoff environment in this paper includes the standard auction environment where v i (q i , θ i , θ -i ) = v i (θ i , θ -i )q i . Besides the preferences that are linear in q i , Assumption 0 also holds for preferences satisfying v i (q i , θ i , θ

-i ) = g i (θ i , θ -i )h i (q i ) + H i (q i , θ -i ), where h i (q i ) is a monotonic non-negative function.
Our assumption throughout the paper is that ≺

θ -i i is a total ordering over Θ i for any θ -i , although ≺ θ -i i can be different from ≺ θ -i i .
To see this, consider an auction environment in which each agent i's payoff-type comprises (c i , d i ) ∈ Θ i ⊆ R 2 , where c i denotes a "common-value" component and d i denotes an idiosyncratic "privatevalue" component, and his valuation for the good is π i (c 1 , . . . , c N ) + d i for some function π i strictly increasing in all the arguments.5 Then, for (c i , d i ), (c i , d i ) ∈ Θ i such that c i < c i and d i > d i , it is possible that, given some c -i , (c i , d i ) has a higher valuation for the good than

(c i , d i ) (i.e., π i (c i , c -i ) + d i > π i (c i , c -i ) + d i ), while
given another c -i , (c i , d i ) has a lower valuation than (c i , d i ). Such environments are said to exhibit ordinal interdependence.

Definition 1. We have ordinal interdependence if there exists i, θ -i , and

θ -i such that ≺ θ -i i =≺ θ -i i .
Paying p i ∈ R to the principal, agent i's final payoff is v i (q i , θ) -p i . The principal's objective is the total revenue, i p i . The feasible set of q = (q 1 , . . . , q I ) is denoted by Q ⊆ i Q i , where the shape of Q depends on the specific environment of interest. For example, auctions, trading, and public-goods environments are in this class, with (or without) interdependence.

Type space

The agents' private information includes their own payoff types, their (first-order) beliefs about their payoff types, and their arbitrarily higher-order beliefs. To model this, we introduce type spaces as in [START_REF] Bergemann | Robust implementation in direct mechanisms[END_REF].

A ("known-own-payoff-type") type space, denoted by T = (T i , θ i , π i ) I i=1 , is a collection of a measurable space of types T i for each agent i, a measurable function θ i : T i → Θ i that describes the agent's payoff type, and a measurable function

π i : T i → ∆(T -i ) that describes his belief about the others' types. Let β i (t i )
denote the belief hierarchy associated with type t i (i.e., it describes t i 's first-order belief about θ -i , second-order belief, and so on, up to an arbitrary higher order).

We say that T has no redundant types if for each i, mapping

t i → ( θ i (t i ), β i (t i )) is
one-to-one.

In fact, there exists a (compact) universal type space

T * = (T * i , θ * i , π * i ) I i=1 , such
that any type space without redundant types can be embedded into it, in the following sense.6

Lemma 1. Let T be a type space with no redundant types. Then, for each i, there exist subsets T i ⊂ T * i and bijections h i : T i → T i such that:

1. θ * i (h i (t i )) = θ i (t i ) for all t i ∈ T i ; and 2. t i ∈A,t -i ∈B d π * i (h(t i ))[h -i (t -i )] = t i ∈A,t -i ∈B d π i (t i )[t -i ] for all A ⊆ T i and B ⊆ T -i .
where

h -i (t -i ) = (h 1 (t 1 ), . . . , h i-1 (t i-1 ), h i+1 (t i+1 ), . . . , h I (t I )).
In what follows, we directly work with this universal type space.7 Specifically, let µ ∈ ∆(T * ) represent the principal's prior belief over T * such that µ({t| θ * (t) = θ}) = f (θ) for each θ, that is, the principal's (first-order) belief for θ is given by f (θ), as assumed above. The other information contained in µ captures the principal's belief over the agents' possible belief structures. Let M ⊆ ∆(T * ) represent the set of all such µ.

In some contexts, it may be reasonable to assume that (the principal believes that) the agents do not have extreme (non-full-support) first-order beliefs. For example, instead of assuming that each agent's belief or knowledge is exogenous, one may be interested in a situation where each agent engages in his own information acquisition (through which his belief is updated), where the information acquisition cost is a linear function of relative entropy [START_REF] Sims | Implications of rational inattention[END_REF]). Then, it is infinitely costly for each agent to know other agents' payoff types.

Formally, let M full ⊂ M denote the set of µ such that every agent i has a full-support first-order belief about the other agents. More precisely, for each

agent i with type t i , let π * 1 i (t i ) ∈ ∆(Θ -i ) denote his first-order belief, that is, π * 1 i (t i )[θ -i ] = t -i | θ * -i (t -i )=θ -i d π * i (t i )[t -i ] for each θ -i . Then, M full is the set of all µ ∈ M such that µ ({t | ∀i, θ -i , π * 1 i (t i )[θ -i ] > 0}) = 1.

Mechanism

The principal designs a mechanism, denoted by (M, q, p), where M i represents a message set for each agent i, M = M 1 × . . . × M I , q : M → Q is an allocation rule, and p : M → R I is a payment function. Each agent i reports a message m i ∈ M i simultaneously, and then he receives q i (m) units of the good and pays p i (m) to the principal. We assume that M i contains a non-participation message ∅ ∈ M i such that q i (∅, m -i ), p i (∅, m -i ) = (0, 0) for any m -i ∈ M -i .

The mechanism together with the universal type space T * (subject to the principal's belief µ) constitute an incomplete information game. Let σ * = (σ * i ) i∈I denote the corresponding equilibrium under certain solution concept, where σ * i :

T * i → M i is agent i's equilibrium strategy.
The expected revenue of mechanism Γ under the principal's belief µ is given by

R µ (Γ) = t∈T * i p i (σ * (t))dµ(t).
First, we define the Bayesian incentive compatible (hereafter BIC for short) mechanism. By revelation principle for Bayesian equilibrium (with T * ), we restrict attention to direct mechanisms with truth-telling equilibrium.

Definition 2. A BIC mechanism is a mechanism Γ = (M, q, p) such that, for each i, (i) M i = T * i , and (ii) for each t ∈ T * and t i = t i ∈ T * i :

t -i v i (q i (t), θ * (t)) -p i (t) d π * i (t i )[t -i ] ≥ 0, t -i v i (q i (t), θ * (t)) -p i (t) d π * i (t i )[t -i ] ≥ t -i v i (q i (t i , t -i ), θ * (t)) -p i (t i , t -i ) d π * i (t i )[t -i ],
denoted by BIR t i and BIC t→t i , respectively.

We now introduce a class of mechanisms with ex post incentive compatibility (an EPIC mechanism for short).

Definition 3. An EPIC mechanism is a mechanism Γ = (M, q, p) such that, for each i, (i) M i = Θ i , and (ii) for each θ ∈ Θ and θ i = θ i ∈ Θ i :

v i (q i (θ), θ) -p i (θ) ≥ 0, v i (q i (θ), θ) -p i (θ) ≥ v i (q i (θ i , θ -i ), θ) -p i (θ i , θ -i ),
denoted by EP IR

θ|θ -i i and EP IC θ→θ |θ -i i
, respectively.

The expected revenue in the truth-telling (ex post) equilibrium in an EPIC mechanism is given by:

R f (Γ) = θ i p i (θ)f (θ).
Note that this does not depend on µ, and in this sense, R f (Γ) may be interpreted as a "robustly guaranteed" expected revenue with respect to the agents' beliefs and higher-order beliefs. Let R EP f denote the maximum expected revenue among all EPIC mechanisms.

Applying the standard argument, the optimal mechanism among all EPIC mechanisms is characterized by the corresponding virtual-value maximization. To explain this, let

F i (θ i | θ -i ) = θi θ -i i θ i f ( θi | θ -i ) denote the cumulative distribu-
tion function of i's payoff types conditional on the other agents' payoff-type profile being θ -i .

Agent i's virtual valuation at payoff-type profile θ is given by:

γ i (q i , θ) = v i (q i , θ) - 1 -F i (θ i | θ -i ) f (θ i | θ -i ) v + i (q i , θ) -v i (q i , θ) , where v + i (q i , θ i , θ -i ) = min θi θ -i i θ i v i (q i , θi , θ -i
) whenever the right-hand side is welldefined; otherwise γ i (q i , θ) = v i (q i , θ). Because v i (0, θ) = 0, we have γ i (0, θ) = 0.

The following result is standard, so we omit its proof.

Lemma 2.

R EP f = max q:Θ→Q θ i γ i (q i (θ), θ)f (θ) s.t. ∀i, θ i , θ i , θ -i : θ i θ -i i θ i ⇒ q i (θ i , θ -i ) ≥ q i (θ i , θ -i ). (M)
We assume that the solution exists in this maximization problem, which we denote by q EP = (q EP i (θ)) i,θ . The corresponding payment rule is denoted by

p EP = (p EP i (θ)) i,θ . 8 Let Q + i = {q i ∈ Q i | ∃θ ∈ Θ s.t. q i = q EP i (θ)} for each i (which is a finite
subset since Θ has a finite number of elements). Define

η = min i min θ i =θ i ,θ -i , q i =q i ∈Q + i |v i (q i , θ i , θ -i ) + v i (q i , θ i , θ -i ) -v i (q i , θ i , θ -i ) -v i (q i , θ i , θ -i )|,
then we have η > 0 due to Assumption 0 and the finiteness of I, Θ and (

Q + i ) i∈I .
In particular, this implies that, by taking 0 = q i < q i ∈ Q + i , we have

|v i (q i , θ i , θ -i ) -v i (q i , θ i , θ -i )| ≥ η for all θ i = θ i and θ -i .
The following notation is extensively used in the subsequent analysis. For each i and q i > 0, define

Θ * i (q i , θ -i ) = {θ i ∈ Θ i |q EP i (θ i , θ -i ) ≥ q i }
as the set of i's payoff types whose allocation given θ -i is greater than or equal to q i in the optimal EPIC mechanism. Note that, by monotonicity, if θ i ∈ Θ * i (q i , θ -i ) and 8 p EP is given as follows. For each i, θ i and θ -i , (i) if there is no

θ i ≺ θ-i i θ i , then p EP i (θ) = v i (q EP i (θ), θ); (ii) otherwise, letting θ i ≺ θ-i i θ i be such that no θ i satisfies θ i ≺ θ-i i θ i ≺ θ-i i θ i , p EP i (θ) = v i (q EP i (θ), θ) -v i (q EP i (θ i , θ -i ), θ) + p EP i (θ i , θ -i ). θ i θ -i i θ i , then θ i ∈ Θ * i (q i , θ -i ). Let θ * i (q i , θ -i ) be the lowest element in Θ * i (q i , θ -i ) with respect to ≺ θ -i i , that is, for any θ i ∈ Θ * i (q i , θ -i ), we have θ i θ -i i θ * i (q i , θ -i ).
This θ * i (q i , θ -i ) is called i's threshold type with respect to q i given θ -i . Finally, let

Θ * -i (q i , θ i ) = {θ -i ∈ Θ -i |θ i ∈ Θ * i (q i , θ -i )}
denote the set of θ -i with which θ i is allocated greater than or equal to q i units in the optimal EPIC mechanism.

Foundations

For a non-EPIC mechanism, expected revenue may vary with the agents' belief structure, and the principal-who does not know the agents' belief structure-may not want to offer a mechanism if the expected revenue is low for some possible belief structures. Following [START_REF] Chung | Foundations of dominant-strategy mechanisms[END_REF], we say that there is a maxmin foundation for EPIC mechanisms if, for any non-EPIC mechanism Γ = (M, q, p), there exists µ ∈ M such that, for any Bayesian equilibrium σ * , the expected revenue obtained in the equilibrium is less than R EP f , that is:

t∈T * i p i (σ * (t))dµ ≤ R EP f .
If there exists a single µ ∈ M that achieves the above inequality for all Γ, then we say that there is a Bayesian foundation for EPIC mechanisms. 9

In the context where (the principal believes that) the agents have full-support 9 These definitions are consistent with the verbal explanations of the corresponding definitions in [START_REF] Chung | Foundations of dominant-strategy mechanisms[END_REF]. However, in fact, the mathematical definitions of them in [START_REF] Chung | Foundations of dominant-strategy mechanisms[END_REF] are slightly different: for example, their mathematical definition of maxmin foundation first-order beliefs, we replace M by M full in the above definitions, and we say that there is a strong maxmin / Bayesian foundation for EPIC mechanisms.

Without ordinal interdependence

First, we consider the case where, for each i, θ -i , and θ -i , ≺

θ -i i =≺ θ -i
i . This includes the private-value environment (as in [START_REF] Chung | Foundations of dominant-strategy mechanisms[END_REF]) as a special case, but also includes some interdependent-value environments. For example, assume that Θ i ⊆ R and v i (q i , θ i , θ -i ) is an increasing function of θ i for each given q i , θ -i . Because i's payoff is affected by θ -i , the environment exhibits interdependence, but it is only cardinal interdependence in the sense that a higher value of θ i corresponds to a higher type with respect to ≺ θ -i i for any θ -i .

We further assume the following "regularity" condition in the same spirit as in [START_REF] Chung | Foundations of dominant-strategy mechanisms[END_REF].

Assumption 1. There exists ε > 0 such that, for any distribution over Θ, f , such that f -f < ε (in a Euclidean distance), the monotonicity constraints (M) are says that, for any non-EPIC mechanism Γ = (M, q, p),

inf µ∈M max σ * :Bayesian equilibrium t∈T i p i (σ * (t))dµ ≤ R EP f .
To see the difference, let R(µ) denote the term inside the bracket on the left-hand side (i.e., the expected revenue given µ), and imagine a case where (i) R(µ) > R EP f for any µ, while (ii) for any ε > 0, there exists µ such that R(µ) -ε < R EP f . That is, the non-EPIC mechanism Γ is a strict improvement over the optimal EPIC mechanism, while it is not a uniform improvement. The verbal definition of [START_REF] Chung | Foundations of dominant-strategy mechanisms[END_REF] (which we follow in this paper) suggests that there is no maxmin foundation, while their mathematical definition says there is. The difference is not innocuous, because the non-EPIC mechanism we propose is indeed such a mechanism.

not binding in the problem of R EP f . In particular, this implies

R EP f = max q:Θ→Q θ i γ i (q i (θ), θ)f (θ).
Of course, the conditions on the environment that imply the above assumption can vary with the environment. For example, in an auction environment with

Q = {q ∈ {0, 1} I | i q i ≤ 1}
, the regularity assumption is satisfied if, for any i ∈ I, j ∈ {0, 1, . . . , I} \ {i} , and θ, we have

γ i (θ) ≥ γ j (θ) ⇒ ∀θ i i θ i , γ i (θ i , θ -i ) > γ j (θ i , θ -i ), (1)
where γ 0 (θ) = 0. In a digital-good environment 10 of Goldberg, Hartline, Karlin, Saks, and Wright ( 2006) with Q = {0, 1} I , the regularity assumption is satisfied under the strict monotone hazard rate condition, i.e., for each i and θ,

1-F i (θ i |θ -i ) f (θ i |θ -i )
is decreasing in θ i . In a multi-unit sales environment as in [START_REF] Mussa | Monopoly and Product Quality[END_REF], the regularity assumption is satisfied under the strict monotone hazard rate condition and concavity of each v i with respect to q i .

Remark 1. [START_REF] Chung | Foundations of dominant-strategy mechanisms[END_REF] call (1) the single-crossing condition in privatevalue environments. They show that if 1) is implied by the strict monotone hazard rate property, together with affiliation in f (which includes independent f as a special case). When there is no ordinal interdependence, we show in Appendix F.1 that 10 The seller can replicate arbitrarily many copies of the digital goods with negligible costs. Moreover, each copy of the digital goods is completely identical with the original one. Examples of digital goods can be computer software, databases, blueprints, DNA sequences, visual images, music, recipes, ideas and so on. Since the seller is no longer subject to the feasibility constraints in digital-goods auction, she sells to an agent if and only if his virtual value is nonnegative.

Θ i = {θ 1 i , . . . , θ M i } satisfying θ m i -θ m-1 i = γ > 0 for each m, then condition-(
condition-( 1) is also satisfied in interdependent-value environment if we further impose three mild restrictions on valuation functions: v i is increasing and concave in each argument, supermodular, and satisfies that an increase in an agent's payoff type has a larger effect on his own valuation function than on any other agent's.

An example that satisfies these conditions is that, v i (θ) = θ i + α j =i θ j with 0 < α < 1, for all i.

Generalizing [START_REF] Chung | Foundations of dominant-strategy mechanisms[END_REF] (for private-value auction environments), we show that no ordinal interdependence implies the strong maxmin / Bayesian foundations for EPIC mechanisms.

Theorem 1. With Assumption 1 and no ordinal interdependence, EPIC mechanisms have the strong Bayesian (and hence strong maxmin) foundation.

Our proof for Theorem 1 is a direct extension of [START_REF] Chung | Foundations of dominant-strategy mechanisms[END_REF] in the private-value setting to the interdependent-value environment. We provide a sketch of the proof here, and the formal proof in the Appendix.

First, we impose the non-singularity condition on the payoff-type distribution f , which says that f satisfies certain full-rank conditions, and consider the Bayesian mechanism design problem with a simple type space having a particular belief structure. We show that under such a belief structure, it is without loss of generality to treat all participation constraints and all "adjacent downward" incentive constraints with equality, and ignore all the other constraints. Then we show that the total expected revenue in this Bayesian problem is maximized by the optimal EPIC mechanism. The next step is to relax the non-singularity assumption by choosing a sequence of non-singular distributions which converge to the given payoff-type distribution.

Since the optimal EPIC mechanisms achieve the highest expected revenue over the sequence of simple type spaces with the particular belief structure, by taking the limit, we show that the Bayesian foundation also exists for any arbitrary payofftype distribution, as long as Assumption 1 is satisfied.11 4 With ordinal interdependence

No strong foundations

We first illustrate by two examples how ordinal interdependence could undermine the foundations of using the optimal EPIC mechanism.

Example 1. Consider a two-agent digital-goods environment, where I = 2, Θ 1 = Θ 2 = {1, 2}, and Q = {0, 1} 2 . We focus on agent 1 because the designer decides allocation rules for each agent separately in digital-goods environments. Table 1 collects payoff-type distribution f , agent 1's valuation and virtual value at each payoff type profile, and the corresponding optimal EPIC allocation for agent 1. For agent 2, assume that v 2 (θ) = θ 2 + 1 for all θ so that the optimal EPIC allocation for him is (q EP 2 (θ), p EP 2 (θ)) = (1, 2) for all θ.

Table 1:

Auction environment of Example 1. f, v 1 , γ 1 , (q EP 1 , p EP 1 ) θ 2 = 1 θ 2 = 2 θ 1 = 1 1 6 , 2, 2, (1, 1) 1 6 , 1, -1, (0, 0) θ 1 = 2 1 3 , 1, 1 2 , (1, 1) 1 3 , 2, 2, (1, 2) We have Θ * 1 (q 1 , θ 2 ) = {1, 2} if (q 1 , θ 2 ) = (1, 1) and Θ * 1 (q 1 , θ 2 ) = {2} if (q 1 , θ 2 ) =
(1, 2). Hence, the threshold payoff type of agent 1 given θ 2 = 1 (i.e., θ 1 = 2) is assigned the goods given θ 2 = 2, but the non-threshold winning payoff type of agent 1 given θ 2 = 1 (i.e., θ 1 = 1) is unassigned given θ 2 = 2. This reversal of the order over agent 1's payoff types is crucial for the no-foundation result.

Now we consider a modification of the optimal EPIC mechanism, which asks agent 1's first-order belief. More specifically, agent 1 is asked to report his payoff type θ 1 and his belief for θ 2 = 1, that is:

y(t 1 ) := π * 1 1 (t 1 )[1] = t 2 | θ * 2 (t 2 )=1 d π * 1 (t 1 )[t 2 ].
If he reports θ 1 = 1 and first-order belief y ∈ [0, 1], agent 1 obtains the goods by paying (2 -cos τ ) under θ 2 = 1, but fails to get the goods and still needs to pay (1 -sin τ ) under θ 2 = 2, where τ = arc tan 1-y y . We keep the optimal EPIC allocations for both agents in the other cases. It is easy to verify that the new mechanism is Bayesian incentive compatible over the universal type space, since every type (of the universal type space) is assigned the optimal choice among the menu of all possible options. 12 Because we are interested in the strong foundation, assume that (the principal believes that) agent 1 always has a full-support first-order belief, that is, y ∈ (0, 1) with (µ-)probability one. Then, agent 1 with θ 1 = 1 always pays strictly more than 1 regardless of his (full-support) first-order belief and agent 2's true payoff type: if θ 2 = 1, agent 1 pays 2 -cos τ for some τ ∈ (0, π 2 ), which is strictly greater than 1; if θ 2 = 2, agent 1 pays 1 -sin τ for some τ ∈ (0, π 2 ), which is strictly greater than 0. Therefore, this new mechanism raises strictly higher expected 12 More precisely, an option for agent 1 is denoted by q 1 (1), p 1 (1); q 1 (2), p 1 (2) , meaning that agent 1's allocation rule is q 1 (θ 2 ), and agent 1's payment is p 1 (θ 2 ), if agent 2 reports θ 2 = 1, 2. Thus, agent 1 chooses from the menu (1, 2 -cos τ ; 0, 1

-sin τ ) | τ ∈ [0, π 2 ] ∪ {(1, 1; 1, 2)}.
revenue than the optimal EPIC mechanism, as long as agent 1 has a full-support first-order belief.

In this example, the reason why we can increase the payment of θ 1 = 1 without violating all constraints is because: in the optimal EPIC mechanism, EP IC

1→2|θ 2 1
is satisfied with strict inequality at θ 2 = 2, while EP IR

1|θ 2 1
is satisfied with strict inequality at θ 2 = 1. This is possible only when we have ordinal interdependence, so that different subset of constraints become binding given different θ -i .13 Thus, once agent 1's belief puts strictly positive probability on θ 2 = 1 and 2, both

BIC 1→2 1
and BIR 1 1 will become strictly slack in the optimal EPIC mechanism, leaving room for payment increase. Similar reasoning applies to the next example. 2 collects payoff-type distribution f , agent 1's valuation and virtual value at each payoff type profile, and the corresponding optimal EPIC allocation for agent 1.

Example 2. Assume I = 2, Θ 1 = {0, 1, 2}, Θ 2 = {0, 1} and Q = {0, 1} 2 . Table
Clearly, agent 1's preference exhibits ordinal interdependence.

f, v 1 , γ 1 , (q EP 1 , p EP 1 ) θ 2 = 0 θ 2 = 1 θ 1 = 0 1 6 , 2, 1, (1, 2) 1 6 , 0, -4, (0, 0) θ 1 = 1 1 6 , 0, -4, (0, 0) 1 6 , 2, 1, (1, 2) θ 1 = 2 1 6 , 3, 3, (1, 2) 1 6 , 3, 3, (1, 2) We have Θ * 1 (q 1 , θ 2 ) = {0, 2} if (q 1 , θ 2 ) = (1, 0) and Θ * 1 (q 1 , θ 2 ) = {1, 2} if (q 1 , θ 2 ) = (1, 1)
. Hence, neither of these two sets is the subset of the other one, which never happens when we don't have ordinal interdependence. Now we construct a new mechanism as follows. When agent 1 reports θ 1 = 2 and first-order belief y (for θ 2 = 0), agent 1 obtains the goods by paying (3 -cos τ ) under θ 2 = 0 and obtains the goods by paying (3 -sin τ ) under θ 2 = 1, where τ = arg tan 1-y y . We keep the optimal EPIC mechanism for both agents in the other cases. As in Example 1, we can show that the new mechanism is Bayesian incentive compatible over the universal type space. Since we assume full-support beliefs, that is, y ∈ (0, 1), then the payment from agent 1 is always strictly greater than 2, the optimal EPIC payment rule, under both θ 2 = 0 and θ 2 = 1. Thus, the new mechanism raises strictly higher expected revenue than the optimal EPIC mechanism regardless of the designer's belief, resulting in no maxmin foundation for the EPIC mechanisms. 14 The two examples above identify some cases where revenue improvement is possible. The common feature of these two cases is that there exists a type of an agent whose BIC and BIR constraints (given any full-support belief of him about the other agents) are not binding. Motivated by them, we define the concept of improvability as follows.

Definition 4 ("Improvability"). Revenue from i is improvable with respect to (θ i , θ -i , θ -i ) if there exists q i and q i such that at least one of the following holds:

(i) θ i ∈ Θ * i (q i , θ -i ) ∩ Θ * i (q i , θ -i ), and θ * i (q i , θ -i ) / ∈ Θ * i (q i , θ -i ), and θ * i (q i , θ -i ) / ∈ Θ * i (q i , θ -i ); (ii) θ i ∈ Θ * i (q i , θ -i ) \ Θ * i (q i , θ -i ), and θ * i (q i , θ -i ) ∈ Θ * i (q i , θ -i ); (iii) θ i ∈ Θ * i (q i , θ -i ) \ Θ * i (q i , θ -i ), and θ * i (q i , θ -i ) ∈ Θ * i (q i , θ -i ). 14 In this example, EP IC 1→2|θ2 1 is binding at θ 2 = 1, but is strictly slack at θ 2 = 2; meanwhile EP IC 1→3|θ2 1 is binding at θ 2 = 2, but is strictly slack at θ 2 = 1. (EP IR 1|θ2 1
always holds with strict inequality, and thus is irrelevant.) Thus, as long as agent 1 has a full-support first-order belief, both BIC 1→2 1 and BIC 1→3 1 are not binding in the optimal EPIC mechanism.

These two examples essentially show that, given the optimal EPIC mechanism, if the revenue from some agent i is improvable with respect to some (θ i , θ -i , θ -i ), then the strong foundation does not exist. We summarize this result in Proposition 1, and provide in Appendix B the formal proof, which directly follows the ideas of Example 1 and 2.

Proposition 1. Under Assumption 0, improvability implies no strong foundation of EPIC mechanisms. implies improvability, and hence no strong foundations of EPIC mechanisms. We further assume the following conditions.

Assumption 2 ("Highest Payoff Type"). For each i, there exists θi ∈ Θ i such that, for each θ i ∈ Θ i and θ -i ∈ Θ -i , we have θi

θ -i i θ i . Assumption 3. There exist θ i , θ i , θ -i and θ -i such that q EP i (θ i , θ -i ) < q EP i (θ i , θ -i ) and q EP i (θ i , θ -i ) < q EP i (θ i , θ -i ).
The highest-payoff-type assumption is satisfied if Θ is a complete sublattice in R d , and v i (q i , θ) is increasing in θ. Assumption 3 says we can find at least one pair of agent i's payoff types such that not only his preference over these two payoff types get reversed (that is,

θ i ≺ θ -i i θ i and θ i θ -i i θ i
), but also the ranking of the corresponding allocations varies at the same time. Basically Assumption 3 means that ordinal interdependence has an influence on the allocation rule in a nontrivial way.

Assumption 3 is not directly on the primitives, and hence one may wonder if it is easy to satisfy/check the assumption in any given environment. In the next subsection, we obtain sufficient conditions that are more directly on the primitives (or on the objects that easy to compute based on the primitives, such as the agents' virtual values).

Theorem 2. Under Assumptions 0, 2 and 3, EPIC mechanisms have no strong foundation.

Proof. We first show that Assumptions 2 and 3 jointly lead to improvability. Then the theorem follows from Proposition 1.

Let q i = q EP i (θ i , θ -i ) and q i = q EP i (θ i , θ -i ). By Assumption 3, we have

     θ i ∈ Θ * i (q i , θ -i ), θ i / ∈ Θ * i (q i , θ -i ); θ i / ∈ Θ * i (q i , θ -i ), θ i ∈ Θ * i (q i , θ -i ).
By Assumption 2, there exists θi ∈ Θ i such that, for any other θ i ∈ Θ i and

θ -i ∈ Θ -i , we have θi θ -i i θ i .
The monotonicity conditions on q EP implies that

q EP i ( θi , θ -i ) ≥ q EP i (θ i , θ -i ) for any θ i = θi . Thus, θi ∈ Θ * i (q i , θ -i ). Similarly, we have θi ∈ Θ * i (q i , θ -i ). Thus, if we further have θ * i (q i , θ -i ) / ∈ Θ * i (q i , θ -i ), and
θ * i (q i , θ -i ) / ∈ Θ * i (q i , θ -i ), then we get improvability-(i). If we have θ * i (q i , θ -i ) ∈ Θ * i (q i , θ -i ), together with θ i ∈ Θ * i (q i , θ -i ) \ Θ * i (q i , θ -i ) we get improvability-(ii). If we have θ * i (q i , θ -i ) ∈ Θ * i (q i , θ -i ), together with θ i ∈ Θ * i (q i , θ -i )\Θ * i (q i , θ -i ) we get improvability-(iii)
. Therefore, improvability is always implied by Assumptions 2 and 3.

We conclude this subsection with the following two remarks.

Remark 2. Although Theorem 2 assumes that each agent has a full-support first-order belief about the other agents ("M full "), and hence the result refers to no strong foundation, this full-support assumption can be omitted if we use an alternative definition of (no) foundation. Specifically, let us say that the EPIC mechanism has no foundation if there exists an alternative mechanism which (i) generates at least a weakly higher expected revenue given any belief hierarchy of the agents (even including the ones without full-support first-order beliefs), and

(ii) generates a strictly higher expected revenue given some of them (see Börgers ( 2017)). Theorem 2 shows that our proposed mechanism in the proof achieves (ii), but it also achieves (i) as we will see in Section 4.3.

Remark 3. Observe that our improvement over the optimal EPIC mechanism is solely based on the property that each agent has a full-support first-order belief, regardless of whether that belief is "correct" or not. Indeed, Theorem 2 holds true even if we restrict attention to a subset of agents' beliefs which are consistent with a common prior: For example, imagine that the agents' payoff types follow a joint distribution f (i.e., the principal's prior belief), there exists an additional signal space S = i S i , and a joint distribution over the payoff types and signals

g ∈ ∆(Θ × S) such that g(•, S) = f (•) (i.e., g's marginal on Θ coincides with f ).
This g is interpreted as a common prior in the sense that each agent's belief about the others is based on Bayes' updated belief given his payoff type θ i and his signal

s i ∈ S i .
Imagine that the principal evaluates a mechanism based on the worst-case expected revenue among all (S, g) which satisfies the above conditions, and we say that the EPIC mechanism has a strong foundation if for any mechanism, there exists a full-support (S, g) with which the optimal EPIC mechanism is (weakly) better than that mechanism. 15 Then, Theorem 2 immediately shows that, under Assumptions 0, 2, and 3, the EPIC mechanism has no strong foundation.

In this sense, our main logic of improvement is different from the one in Börgers (2017), whose improvement is based on the mutually beneficial side-bets across agents with non-common priors.

A sufficient condition for Assumption 3

The goal of this subsection is to provide sufficient conditions more directly on the primitives with which Theorem 2 holds. Indeed, the following lemma provides a set of conditions on the virtual values 16 that imply Assumption 3. Together with Assumptions 0 and 2 (which are already directly on the primitives), Theorem 2 holds.

Lemma 3. Assumption 3 is satisfied if:

(i) If θ i ≺ θ -i i
θ i , then we have γ i (q i , θ i , θ -i ) ≤ γ i (q i , θ i , θ -i ) for all q i ; (ii) There exist i, θ i , θ i , θ -i and θ -i such that (a) for any q i , γ i (q i , θ i , θ -i ),

γ i (q i , θ i , θ -i ) ≤ 0; (b) for some q i , γ i (q i , θ i , θ -i ) > 0; (b') for some q i , γ i (q i , θ i , θ -i ) > 0;
(c) for any j = i, any θi and any q j , we have γ j (q j , θi , θ -i ) ≤ 0 and γ j (q j , θi , θ -i ) ≤ 0;

(iii) Q is a lower set (i.e., if q ∈ Q and q ≤ q, then q ∈ Q); and

(iv) for any i, θ, γ i (q i , θ) is strictly quasi-concave in q i .

15 [START_REF] Du | Robust mechanisms under common valuation[END_REF] and [START_REF] Brooks | Optimal auction design with common values: An informationally-robust approach[END_REF] studies the worst-case optimal auction mechanisms in this sense in (pure-)common-value environments.

16 Recall that the virtual values are straightforwardly computed based on the primitives.

The proof is given in Appendix F.2. Condition-(i) is a standard monotonicity condition on virtual values, which guarantees that the seller never sells to an agent with negative virtual value. Condition-(ii) requires that ordinal interdependence affect the virtual values in a particular way. More specifically, θ -i , θ -i are -i's types such that they themselves are not assigned (condition (c)), but important for i in the sense that i's virtual value can have opposite signs depending on θ -i or θ -i . For example, one may imagine that θ -i , θ -i include important "common value" information (and hence i's virtual value crucially depends on it), but -i have very low "private value" or "idiosyncratic" shocks so that their willingness to pay are small (and hence have negative virtual values). Condition-(iii) is satisfied in many environments of private-good assignment, such as in single-unit or multiunit auction, bilateral trading, partnership dissolution, and so on. Condition-(iv) is trivially satisfied if v i is linear in q i (e.g., auction, bilateral trade). It is also typically satisfied in many multi-unit environment, where the condition, together with γ i (0, θ) = 0, essentially says: If γ i (q i , θ) > 0 and 0 < q i < q i , then γ i (q i , θ) > 0.

We provide a more concrete example of the conditions in the above lemma in a single-unit auction context.

Example 3. Consider a single-object auction with two agents and two states.

Each agent i's payoff type is

θ i = (c i , d (1)
i , d

i ), and his valuation is

v i = c j d (1) i + (1 -c j )d (2)
i , which depends on his own private-value component and agent j's common-value component. 17 For simplicity, assume that for i = 1, 2, we have 17 Because v i does not depend on c i , any two payoff types with the same private-value component will induce the same valuation, thus Assumption 0 is violated in this example. However, by allowing each agent's valuation v i to slightly depend on one's own common-value component c i , Example 3 can easily satisfy Assumption 0.

It is worth noting that the modified mechanism in Proposition 1 also works in the current version of Example 3, even though Assumption 0 is violated. To see this, fixed arbitrary d i and

c i ∈ { 1 3 , 2 3 }, d i = (d (1) i , d (2) i ) ∈ {0, 1} × {0, 1} satisfying (c i , d (1)
i , d

i ) are mutually independent and uniformly distributed. Given c j = 2 3 , agent i's valuations for d i = (0, 0), (0, 1), (1, 0), (1, 1) are 0, 1 3 , 2 3 and 1, respectively; and the corresponding virtual values are -1, -1 3 , 1 3 and 1. While given c j = 1 3 , agent i's valuations for d i = (0, 0), (0, 1), (1, 0), (1, 1) are 0, 2 3 , 1 3 and 1, respectively; and the corresponding virtual values are -1, 1 3 , -1 3 and 1. Immediately, the monotonicity condition on virtual values (condition-(i) of Lemma 3) is satisfied, and that d i = (0, 0) is the worst private-value component for both agents (condition-(ii-c) of Lemma 3). Moreover, fixed any c i , let θi = (c i , (1, 1)), θ i = (c i , (0, 1)), θ i = (c i , (1, 0)), θ j = ( 13 , (0, 0)) and θ j = ( 2 3 , (0, 0)), and we have

γ i ( θi , θ j ) > γ i (θ i , θ j ) > 0 > γ i (θ i , θ j ), γ i ( θi , θ j ) > γ i (θ i , θ j ) > 0 > γ i (θ i , θ j ) (condition-(ii-a,b,b') of Lemma 3). By Lemma 3, we have q EP i ( θi , θ j ) = q EP i ( θi , θ j ) = q EP i (θ i , θ j ) = q EP i (θ i , θ j ) = 1, q EP i (θ i , θ j ) = q EP i (θ i , θ j ) = 0
. Thus, revenue from agent i is improvable with respect to ( θi , θ j , θ j ), and hence there is no strong foundation.

No foundations

Next, we study if EPIC mechanisms have the (not necessarily strong) foundation. The following example suggests that the same mechanism as above does not generally work, if the agents have non-full-support first-order beliefs.

Example 4. In the new mechanism proposed in Example 1, if we allow for nonfull-support beliefs, there exists a situation where agent 1 always correctly predicts agent 2's payoff types. Formally, let

C = {t ∈ T * | θ * (t) = (1, 1), π * 1 1 (t 1 )[1] = 1}, any c i = c i , we have v i (q i , θ i , θ -i ) = v i (q i , θ i , θ -i
) for all q i and all θ -i where θ i = (c i , d i ) and θ i = (c i , d i ). Due to incentive compatibility constraints, we only need to set the allocations (as well as the payments) for agent i at (θ i , θ -i ) and (θ i , θ -i ) to be the same.

C = {t ∈ T * | θ * (t) = (1, 2), π * 1 1 (t 1 )[2] = 1}
, and consider µ such that µ(C) = f (1, 1) and µ(C ) = f (1, 2). Because the optimal choice for agent 1 is τ * = 0 (or reporting y = 1 as his belief for θ 2 = 1) if t ∈ C, and τ * = π 2 (or reporting y = 0) if t ∈ C , the equilibrium payments in the new mechanism coincide with those in the optimal EPIC mechanism. Thus, without the full-support belief assumption, the new mechanism in Example 1 only weakly improves the expected revenue. Now we further modify the mechanism as follows. Unless agent 1 reports θ 1 = 1 and y = 0, the allocation is the same as the previous mechanism proposed in Example 1. If agent 1 reports θ 1 = 1 and y = 0, then the following events happen: agent 1 does not buy the good for any θ 2 , he pays M (> 3) if θ 2 = 1 (i.e., when his belief turns out to be "wrong"), and the principal offers price 3 for agent 2 (so that agent 2 buys only if θ 2 = 2, i.e., when agent 1's belief turns out to be "right"), instead of price 2. As before, the new mechanism is Bayesian incentive compatible on the universal type space T * . 18

This new mechanism achieves a weakly higher expected revenue than in the optimal EPIC mechanism. First, this weak improvement is obvious unless θ 1 = 1 and y = 0. If θ 1 = 1 and y = 0, the principal earns M > 3 from agent 1 if θ 2 = 1 (while the optimal EPIC mechanism yields total revenue 3), and earns 3 from agent 2 if θ 2 = 2 (while the optimal EPIC mechanism yields total revenue 2).

To show a strict improvement in expected revenue for any µ ∈ M, consider the case where θ 1 = 1 and θ 2 = 2. Because f (1, 2) > 0, it suffices to show that, for 18 For agent 1, the only change is that his payment increases when agent 1 reports θ 1 = 1 and y = 0, and agent 2 reports θ 2 = 1. Thus, any other type of agent 1 won't pretend to have θ 1 = 1 and y = 0; meanwhile, this change has no effect on agent 1 with θ 1 = 1 and y = 0, since he deems the probability of having θ 2 = 1 to be zero. As for agent 2, he is always offered a postedprice mechanism (depending on agent 1's report only), then his Bayesian incentive compatible constraints are satisfied.

any y ∈ [0, 1] reported by agent 1, the new mechanism achieves a strictly higher revenue than 2, the revenue in the optimal EPIC mechanism. First, as we see above, if y = 0 is reported, then the new mechanism yields 3 (from agent 2), and hence there is a strict improvement. If y > 0, then agent 2 pays 2, and agent 1 pays 1 -sin(arc tan 1-y y ) > 0, and hence, there is again a strict improvement. Notice that the key for strict improvement is to use agent 1's belief to modify the price for agent 2. If agent 1 is correct, such modification is profitable for the principal. Otherwise, the principal collects a "fine" from agent 1, which is also profitable. As suggested in the example, if an agent always correctly predicts the other agents' payoff types, we can use this agent's prediction to raise additional revenue from the other agents (and to fine him if his prediction turns out to be wrong in order for the principal to "hedge", as in the example above). Because this means that we need to be able to change an agent's allocation without changing the others' -more precisely, we reduce the allocation at the threshold payoff type in order to charge higher prices for non-threshold winning types -we assume that the feasible allocation set Q is a lower set, that is, if q is in Q and q ≤ q, then q is also in Q. Obviously, the standard auction belongs to this class of environments.

In addition, even if an agent correctly predicts the occurrence of some θ -i (or its non-occurrence), such information does not necessarily make the principal earn strictly more revenue from the other agents (for example, imagine that any j( = i)'s virtual valuation is negative given θ -i ). Thus, we need a stronger version of the improvability.

Definition 5. We have the strong improvability if there exist i, j, θ i , θ j , q j , θ -ij such that θ j ∈ Θ * j (q j , θ i , θ -ij ), and that revenue from i is improvable with respect to θ i , (θ j , θ -ij ), (θ * j (q j , θ i , θ -ij ), θ -ij ) .

Roughly, the strong improvability implies that, if agent i with θ i correctly predicts that -i's payoff types are not θ -i , then (given θ -ij ) the principal can know that j's type is not a threshold type for some q j . Such information enables the principal to earn higher expected revenue from j.

Proposition 2. Under Assumption 0, if Q is a lower set, then strong improvability implies no foundation of EPIC mechanisms.

The formal proof is given in Appendix C, which directly follows from the idea of Example 4. The main difference from Proposition 1 is that, when the agent does not have a full-support first-order belief, the principal extracts more surplus from other agents by modifying their allocations. This imposes a stronger requirement on the feasible allocation, so that makes Proposition 2 not applicable to some environments. For example, in the single-object auction, strong improvability requires that agent j is assigned the object at both (θ i , θ j , θ -ij ) and (θ i , θ * j (1, θ -j ), θ -ij ), which means agent i cannot get the good at either payoff type profile, contradicting the fact that strong improvability also means that agent i should win the object under at least one payoff type profile.

However, other environments such as a multiple-unit auction where each agent has a unit demand would satisfy the strong improvability. In the previous auction with common-value and private-value components, we assume that there are two objects and more than two agents. To get strong improvability, first

choose c -i = (c j , c -ij ), c -i = (c j , c -ij ) satisfying γ i (d i , c -i ) ≤ 0 < γ i (d i , c -i ), γ i (d i , c -i ) > 0 ≥ γ i (d i , c -i );
then let any agent k = i, j have some worst private-value component, d k , which induces negative virtual value, so that he will not get the object in the optimal EPIC mechanism; finally choose c i , d j and d j such that the smaller one of {γ j (d j , c i , c -ij ), γ j (d j , c i , c -ij )} is just above 0, and thus becomes the threshold payoff type under (c i , c -ij ). Through a similar argument with Lemma 3, we can show that revenue from i is improvable with respect to

(c i , di ), (c j , d j ), (c -ij , d -ij ) and (c j , d j ), (c -ij , d -ij
) , where di depends on which of the three cases in Definition 4 (Improvability) we actually have.

Necessary and sufficient condition

A natural question is, under which additional conditions, the ordinal interdependence implies the strong improvability, so that EPIC mechanisms do not have the foundation if and only if we do not have the ordinal interdependence. A sufficient condition is the following richness condition on Q.

Assumption 4. For each i, θ i , and θ -i , we have q EP i (θ i , θ -i ) > 0, and for each

θ i = θ i , we have q EP i (θ i , θ -i ) = q EP i (θ i , θ -i ).
A representative example is a monopoly problem with multiple buyers and multiple units of trading. 19 Assume that each agent i's payoff is given by

v i (θ i , θ -i , q i , p i ) = u i (θ i , θ -i )q i -q 2 i -p i ,
where q i (≥ 0) is the quantity assigned to agent i, and p i is agent i's payment to the principal. Assume that there is no feasibility constraint on q. The principal maximizes the expected revenue. We can see that an agent's valuation is concave in q i . The optimal EPIC mechanism is given by: max

q,p θ i f (θ)p i (θ) s.t. ∀i, θ i , θ i , θ -i : q i (θ) ≥ 0; u i (θ i , θ -i )q i (θ i , θ -i ) -q 2 i (θ i , θ -i ) -p i (θ i , θ -i ) ≥ max 0, u i (θ i , θ -i )q i (θ i , θ -i ) -q 2 i (θ i , θ -i ) -p i (θ i , θ -i ) .
By the standard argument, the problem is equivalent to:

max q,p θ i f (θ) γ i (θ)q i (θ) -q 2 i (θ) s.t. ∀i, θ i , θ -i , θ i ≺ θ -i i θ i : q i (θ) ≥ 0; q i (θ i , θ -i ) ≥ q i (θ i , θ -i ).
The virtual value γ i is given by:

γ i (θ i , θ -i ) := u i (θ i , θ -i ) - 1 -F i (θ i | θ -i ) f (θ i | θ -i ) u + i (θ i , θ -i ) -u i (θ i , θ -i ) ,
where

u + i (θ i , θ -i ) := min θi θ -i i θ i u i ( θi , θ -i ).
If we assume (i) for all i and θ, we have γ i (θ) > 0, and (ii)

γ i (θ i , θ -i ) < γ i (θ i , θ -i ) whenever θ i ≺ θ -i i
θ i , then the optimal EPIC mechanism, given by q EP i (θ) = γ i (θ) 2 , satisfies Assumption 4.

Theorem 3. Under Assumptions 0, 1 and 4, if Q is a lower set, then EPIC mech-anisms have the foundation if and only if we do not have ordinal interdependence.

Remark 4. In some contexts, the assumption that each agent is always assigned a positive quantity may be considered as a restrictive assumption. However, we adopt this assumption because it is relatively transparent, and it simplifies the proof of the theorem. Weaker conditions may suffice at the cost of less transparent statement and more complicated argument.

More specifically, imagine an environment where, given some θ -i , agent i is assigned q EP i (θ) = 0 for some subset of θ i , while for any θ i , θ i with q EP i (θ i , θ -i ),

q EP i (θ i , θ -i ) > 0, we have q EP i (θ i , θ -i ) = q EP i (θ i , θ -i ).
Assume that there exists a subset of payoff types, Θi for each i, such that those types are always assigned some non-zero quantities. Then, one can show that EPIC mechanisms do not have the foundation if ordinal interdependence occurs for those always-positive-quantity type profiles.

"Unimprovable" mechanisms?

Given our result that EPIC mechanisms could be improved when the environment exhibits significant interdependence, it seems natural to ask: Then, which mechanism(s) is (are) "unimprovable", that is, a mechanism for which no other mechanism can achieve a higher expected revenue regardless of the principal's belief µ (strictly at least for some µ)?

To simplify the analysis, we consider a "reduced form" of the multi-agent environment, where we focus on a particular agent with privately-known payoff type θ, and the other agents' payoff type profile θ -i is represented by a state variable ω ∈ Ω which becomes publicly known after the agent's report. Thus, the agent's type is a pair (θ, β), where θ is his payoff-type and β ∈ ∆(Ω) represents his belief about ω. Let T = Θ × ∆(Ω) denote the agent's type space.

We assume that the allocation is denoted by (q, p) ∈ [0, 1] × R, where q represents the probability of selling a single good, and p represents the monetary transfer from the agent to the principal. The principal's payoff is the revenue, p, and the agent's payoff given (q, p) is denoted by v(ω, θ)q -p. It is without loss of generality to focus on the class of direct mechanisms Γ = (M, q, p) where the agent participates in the mechanism and reports (θ, β) truthfully.

The following example suggests that we need to make a further restriction on the principal's belief µ; otherwise would not be a well-defined question to find unimprovable mechanisms.

Example 5. Let Ω = {0, 1} and Θ = {1}, and the agent's valuation is v(ω, θ) = θ(= 1). That is, ω does not change his value, and in this sense, it is a private-value environment. Furthermore, the agent has no payoff-relevant private information.

The optimal EPIC mechanism fully extract the valuation: q EP (ω, θ) = p EP (ω, θ) = θ(= 1).

This mechanism may seem to be "obviously optimal". However, it is (unboundedly) improvable by the following mechanism Γ = (T, q, p): q(ω, θ, β) = 1 for all ω, θ, β; p(ω, θ, β) = 1 if β(ω) > 0; and p(ω, θ, β) = P (> 0) if β(ω) = 0. It is obvious that truth-telling of θ(= 1) and β is optimal for the agent, which implies that, for any µ, the revenue is at least 1. Moreover, for µ with µ({ω, θ, β|β(ω) = 0}) > 0 (i.e., the principal believes that, with a positive probability, the agent is "completely wrong"), the principal's expected revenue is strictly greater than 1.

Actually, P can be any number greater than 1, and increasing P always implies further improvement, and hence, no "unimprovable" mechanism exists.

The above example suggests that the question of unimprovable mechanism can only make sense by (further) restricting our attention on the class of µ which does not assign a positive probability that the agent is "completely wrong".

Formally, we say that µ is strongly admissible if it is in M and it does not assign a positive probability for the agent being completely wrong:

µ({ω, θ, β|β(ω) = 0}) = 0, ∀ω, θ.
Then, based on Börgers (2017), we say that a (direct) mechanism Γ = (T, q, p) is dominated (instead of "improved") by another (direct) mechanism Γ = (T, q, p ) if (i) for any strongly admissible µ, the expected revenue in Γ is weakly higher than that in Γ, and (ii) there exists a strongly admissible µ with which the expected revenue in Γ is strictly higher. A mechanism is undominated (or "unimprovable") if it is not dominated.20 Applying this definition, the optimal EPIC mechanism where the agent always pays 1 is undominated in Example 5.

Characterizing undominated mechanisms in the general environment is an interesting question but beyond the scope of the paper, so left for future research.

Nevertheless, we believe that our idea of mechanism construction in the previous sections could be useful for this ambitious question. In order to illustrate this point, in what follows, we characterize all the mechanisms that (i) dominate the optimal EPIC mechanism and (ii) are undominated, in the context of Example 2.

Example 2 revisited

We consider the following class of mechanisms Γ = (T, q, p): q(•) = q EP (•);

p(ω, θ, β) = p EP (ω, θ) if θ ∈ {0, 1}; and, p(0, 2, β), p(1, 2, β) = a(y), b(y) if β(1) = y ∈ [0, 1].
It is a class of mechanisms in the sense that (a(y), b(y)) y∈[0,1] are the free parameters. We denote this class by Γ * . In particular, the non-EPIC mechanism constructed in Example 2 (that dominates the optimal EPIC mechanism) is in this class.

Let Γ U denote the set of all mechanisms that are undominated and that dominate the optimal EPIC mechanism.

Proposition 3. Γ is in Γ U if and only if it is in Γ * with (a(y), b(y)) y∈[0,1] satisfying (i) (a(y), b(y)) y∈[0,1]
(as a set of points on R 2 ) lies on a continuous, convex, nonincreasing curve that connects (2, 3) and (3, 2); and (ii) either lim y↑1 a(y) = 3 or lim y↓0 b(y) = 3 holds (or both).

In particular, the result says that the non-EPIC mechanism constructed in Example 2 (that dominates the optimal EPIC mechanism) is undominated. That is, if any other mechanism achieve a strictly higher expected revenue for some (strongly admissible) µ than that non-EPIC mechanism, such a mechanism necessarily achieves a strictly lower revenue for another (strongly admissible) µ. In this sense, that non-EPIC mechanism cannot be further improved.

If the environment exhibits only cardinal interdependence (and certain regularity conditions), then there exist the maxmin and Bayesian foundations for EPIC mechanisms, in the sense of [START_REF] Chung | Foundations of dominant-strategy mechanisms[END_REF]. If the environment exhibits ordinal interdependence, (and certain additional conditions), then such a foundation may not exist.

In interdependent-value environments, [START_REF] Yamashita | Implementation in Weakly Undominated Strategies: Optimality of Second-Price Auction and Posted-Price Mechanism[END_REF] provides an alternative solution concept (that is, incentive compatibility in value revelation), which is also robust to the agents' belief structure in a related sense and useful in the implementation of social choice correspondences in undominated strategies. It may be interesting to investigate similar sorts of foundation results for this alternative solution concept.

A Proof of Theorem 1

Because

θ -i i = θ -i i
for all i, θ -i , and θ -i , we denote this ordering by i with no superscript. Also, let Θ i = {θ 1 i , . . . , θ N i } (where

N = |Θ i |) so that θ n i ≺ i θ n+1 i for all n = 1, . . . , N -1.
Consider the simple type space T f = (T i , θ i , π i ) I i=1 with T i = Θ i and the agents' beliefs defined by

π i (θ n i )[θ -i ] = θ -i ∈Θ -i G i (θ n i , θ -i ) -1 G i (θ n i , θ -i ) for all θ -i ∈ Θ -i , where G i (θ n i , θ -i ) = N k=n f (θ k i , θ -i ). By convention, G i (θ N +1 i , θ -i ) = 0.
The optimal Bayesian mechanism given this simple type space achieves:

V (f ) = max (q,p):Θ→Q×R I θ∈Θ f (θ) i∈I p i (θ) s.t. ∀i ∈ I, ∀n, l ∈ {1, . . . , N }, ∀θ ∈ Θ : θ -i ∈Θ -i π i (θ n i )[θ -i ] v i (q i (θ n i , θ -i ), θ n i , θ -i ) -p i (θ n i , θ -i ) ≥ 0, (BIR n i ) θ -i ∈Θ -i π i (θ n i )[θ -i ] v i (q i (θ n i , θ -i ), θ n i , θ -i ) -p i (θ n i , θ -i ) ≥ θ -i ∈Θ -i π i (θ n i )[θ -i ] v i (q i (θ l i , θ -i ), θ n i , θ -i ) -p i (θ l i , θ -i ) . (BIC n→l i )
Because the identity function θ i is one-to-one, by Lemma 1, T f can be embedded in the universal type space T * through a bijection h such that

t n i = h i (θ n i ).
Thus, V (f ) provides an upper bound for the best expected revenue given the universal type space T * (and the principal'

s belief µ * ∈ M such that µ * (h( θ -1 (θ))) = f (θ))
. Therefore, in order to show the Bayesian foundation for EPIC mechanisms given f , it suffices to show that

V (f ) ≤ R EP f .
We first prove the claim by imposing the non-singularity condition on f , which

assumes that Ω i = (f (θ 1 i , •), . . . , f (θ N i , •)) has rank N for each i, where f (θ n i , •) = (f (θ 1 i , θ -i )) θ -i ∈Θ -i is a (I -1)N -dimensional vector.
Lemma 4. In the solution of V (f ), (BIC n→n-1 i ) holds with equality for all i and n = 1, and (BIR n i ) holds with equality for all i and n.

The lemma implies that, for all i and n:

θ -i ∈Θ -i π i (θ n i )[θ -i ] v i (q i (θ n i , θ -i ), θ n i , θ -i ) -p i (θ n i , θ -i )
and therefore, the objective becomes:

i∈I N n=1 θ -i ∈Θ -i f (θ n i , θ -i )p i (θ n i , θ -i ) = i∈I N n=1 θ -i ∈Θ -i G i (θ n i , θ -i ) -G i (θ n+1 i , θ -i ) p i (θ n i , θ -i ) = i∈I N n=1   θ -i ∈Θ -i G i (θ n i , θ -i )p i (θ n i , θ -i ) - θ -i ∈Θ -i G i (θ n+1 i , θ -i )p i (θ n i , θ -i )   = i∈I N n=1 θ -i ∈Θ -i G i (θ n i , θ -i )v i (q i (θ n i , θ -i ), θ n i , θ -i ) -G i (θ n+1 i , θ -i )v i (q i (θ n i , θ -i ), θ n+1 i , θ -i ) = i∈I θ∈Θ f (θ)γ i (q i , θ).
Therefore, under Assumption 1, we have

V (f ) = R EP f .
Proof of Lemma 4. We first show that each upward incentive constraint, (BIC n→l i )

with n < l, can be ignored without loss. Let Π i = π i (θ 1 i ), . . . , π i (θ N i ) denote the matrix of agent i's beliefs, where each π i (θ n i ) is a (I -1)N -dimensional vector.

Then:

Π i =       κ 1 i • • • 0 . . . . . . . . . 0 • • • κ N i       N ×N       1 • • • 1 . . . . . . . . . 0 • • • 1       N ×N Ω,
where

κ n i = θ -i ∈Θ -i G i (θ n i , θ -i ) -1
, and hence Π i has a rank N . Thus, there exists λ ∈ R (I-1)N such that:

Π i λ = (1, . . . , 1, 0 l-th element , . . . , 0) . If we add λ to p i (θ l i , •), each BIC n→l i
with n < l is relaxed, while no other (BIC) and (BIR) constraints are affected. Moreover, from π i (θ l i ) • λ = 0 and π i (θ l+1 i ) • λ = 0, we obtain:

θ -i ∈Θ -i G i (θ l i , θ -i )λ(θ -i ) = 0, θ -i ∈Θ -i G i (θ l+1 i , θ -i )λ(θ -i ) = 0, which implies that θ -i ∈Θ -i f (θ l i , θ -i )λ(θ -i ) = 0, that is, the principal's expected
revenue is also unaffected.

Next, we show that for any mechanism (q, p) satisfying the remaining constraints, there exists a mechanism (q , p ) which satisfies not only the remaining constraints, but also (BIR n i ) for n = 1, . . . , N and (BIC n→n-1 i ) for n = 2, . . . , N with equality, and raises at least as high expected revenue as (q, p).

Given any such mechanism (q, p), if (BIC n→n-1 i

) is satisfied with strict inequality for some i and n, then let β n→n-1 i be the amount of the slackness of this constraint (BIC n→n-1 i

). Let Π i be the matrix generated by substituting the n-th row of Π i with the vector f (θ n-1 , •). That is:

Π i =                    κ 1 i • • • 0 0 0 • • • 0 . . . . . . . . . . . . . . . . . . . . . 0 • • • κ n-1 i 0 0 • • • 0 0 • • • 0 1 0 • • • 0 0 • • • 0 0 κ n+1 i • • • 0 . . . . . . . . . . . . . . . . . . . . . 0 • • • 0 0 0 • • • κ N i                                       1 • • • 1 1 1 • • • 1 . . . . . . . . . . . . . . . . . . . . . 0 • • • 1 1 1 • • • 1 0 • • • 1 0 0 • • • 0 0 • • • 0 0 1 • • • 1 . . . . . . . . . . . . . . . . . . . . . 0 • • • 0 0 0 • • • 1                    Ω,
and hence, Π i has a rank N . Thus, there exists λ ∈ R (I-1)N such that:

Π i λ = (0, . . . , 0, 1 n-th element , 0, . . . , 0) .

Because π i (θ n-1 i ) • λ = 0 and f (θ n-1 , •) • λ = 1, we have: Similarly, if (BIR n i ) is satisfied with strict inequality for some i and n, then let β n i be the amount of the slackness of this constraint (BIR n i ). Because Π i has a rank N , there exists λ ∈ R (I-1)N such that:

π i (θ n i ) • λ = κ n i κ n-1 i π i (θ n-1 i ) • λ -κ n i f (θ n-1 , •) • λ < 0,
Π i λ = (β 1 i , . . . , β N i ) ≥ 0.
Adding λ to each p i (θ n i , •) does not affect any (BIC) constraint, while all the participation constraints are satisfied with equality in the new mechanism. The change in the total expected revenue is:

N n=1 θ -i ∈Θ -i f (θ n i , θ -i )λ(θ -i ) = θ -i ∈Θ -i λ(θ -i ) N n=1 f (θ n i , θ -i ) = θ -i ∈Θ -i λ(θ -i )G i (θ 1 i , θ -i ) = 1 κ 1 i θ -i ∈Θ -i λ(θ -i ) π i (θ 1 i )[θ -i ] =β 1 i ,
which is non-negative.

Next, we consider the case where f is singular, that is, for some i, Ω i has a rank strictly less than N . Consider a sequence of distributions over Θ, {f r } ∞ r=1 , such that each f r is full-support and f r → f (in the standard Euclidean distance).21

By Assumption 1, without loss of generality, we assume that the monotonicity constraints (M) are not binding in the problem of R EP fr .

We prove the following continuity lemma.

Lemma 5. For each ε > 0, there exists r ε ∈ N such that, for any r ≥ r ε ,

R EP fr ≤ R EP f + ε and V (f r ) ≥ V (f ) -ε.
Proof of Lemma 5. For the first inequality, recall that

R EP f = θ f (θ) • max q(θ) i γ i q i (θ), θ ,
which is obviously continuous in f .

For the second inequality, let (q, p) be a solution to the problem of V (f ).

In the following, for each r, we construct another mechanism (q, p r ) (note that we keep the same q), so that it satisfies all the constraints of the problem of V (f r ), namely:

θ -i ∈Θ -i π r i (θ n i )[θ -i ] v i (q i (θ n i , θ -i ), θ n i , θ -i ) -p r i (θ n i , θ -i ) ≥ 0, (BIR n i (r)) θ -i ∈Θ -i π r i (θ n i )[θ -i ] v i (q i (θ n i , θ -i ), θ n i , θ -i ) -p r i (θ n i , θ -i ) ≥ θ -i ∈Θ -i π r i (θ n i )[θ -i ] v i (q i (θ l i , θ -i ), θ n i , θ -i ) -p r i (θ l i , θ -i ) . (BIC n→l i (r))
Let:

S n i (r) = max    0, θ -i ∈Θ -i π r i (θ n i )[θ -i ] p i (θ n i , θ -i ) -v i (q i (θ n i , θ -i ), θ n i , θ -i )    ,
denote the size of violation of (BIR n i (r)) by p. If we consider a modified payment rule p so that p i (θ n i , •) = p i (θ n i , •) -S n i (r)1, then this new payment rule satisfies the participation constraints, but may not satisfy the incentive compatibility constraints. Thus, let:

L n→l i (r) = max 0, θ -i ∈Θ -i π r i (θ n i )[θ -i ] v i (q i (θ l i , θ -i ), θ n i , θ -i ) -p i (θ l i , θ -i ) - θ -i ∈Θ -i π r i (θ n i )[θ -i ] v i (q i (θ n i , θ -i ), θ n i , θ -i ) -p i (θ n i , θ -i ) ,
denote the size of violation of (BIC n→l i (r)) by p . As in the first part of the proof, the matrix of agent i's belief in the simple type space T fr , Π r i = π r i (θ 1 i ), . . . , π r i (θ N i ) , has a rank N , and hence, there exists λ 1 i (r), . . . , λ N i (r) ∈ R (I-1)N such that:

Π r i λ 1 i (r), . . . , λ N i (r) = L n→l i (r) N ×N ,
which we denote by L r . Or equivalently:

L r =       κ 1 i (r) • • • 0 . . . . . . . . . 0 • • • κ N i (r)       N ×N Kr       1 • • • 1 . . . . . . . . . 0 • • • 1       N ×N A Ω r λ 1 i (r), . . . , λ N i (r) . Define p r i (θ n i , •) = p i (θ n i , •) -S n i (r)1 + λ n i (r).
Then, together with q, it satisfies all the constraints of the problem of V (f r ).

We complete the proof by showing that

θ i (p r i (θ) -p i (θ))f r (θ) → 0 as r → ∞.
Because it is obvious that S n i (r) → 0, it suffices to show that:

N n=1 f r (θ n i , •) • λ n i (r) → 0.
Indeed:

N n=1 f r (θ n i , •) • λ n i (r) = tr A -1 K -1 r L r → 0, as r → ∞, because L r → 0.
Finally, contrarily to the original claim, suppose that V (f ) > R EP f , and let

ε ∈ (0, V (f )-R EP f 2
). Then, there exists r ε such that:

V (f r ) -R EP fr ≥ V (f ) -R EP f -2ε > 0,

B Proof of Proposition 1

We show that, for each of these cases, there exists a mechanism that yields a strictly higher expected revenue than the optimal EPIC mechanism.

Case (i):

θ * i (q i , θ -i ) / ∈ Θ * i (q i , θ -i ), θ * i (q i , θ -i ) / ∈ Θ * i (q i , θ -i ), θ i ∈ Θ * i (q i , θ -i ) ∩ Θ * i (q i , θ -i ).
Consider a new mechanism (M, q * , p * ) such that M i = Θ i × [0, 1], M j = Θ j for j = i, and for each (( θi , x), θ-i ) ∈ M , q * (( θi , x), θ-i ) = q EP ( θ),

p * j (( θi , x), θ-i ) = p EP j ( θ), ∀j = i,
and for p * i , we set p * i (( θi , x), θ-i ) = p EP i ( θ) unless θi ∈ Θ * i (q i , θ -i ) ∩ Θ * i (q i , θ -i ) and θ-i ∈ {θ -i , θ -i }; and for each θi ∈ Θ * i (q i , θ -i ) ∩ Θ * i (q i , θ -i ), we set

p * i (( θi , x), θ -i ) = p EP i ( θi , θ -i ) + η(1 -x), p * i (( θi , x), θ -i ) = p EP i ( θi , θ -i ) + ηψ(x),
where

ψ(x) = 1 - √ 1 -x 2 .
Intuitively, x ∈ [0, 1] is related to agent i's first-order belief over θ -i and θ -i

(more precisely, their likelihood ratio). Indeed, if agent i reports his payoff type θ i truthfully, his optimal choice of x is given by x

* (β, β ) = (β/β ) 2 1+(β/β ) 2 , where β is is at most 22 β[η(1 -x * (β, β ))] + β [-η + ηψ(x * (β, β ))] ≤ 0.
As shown in Footnote 22, the key step is to prove that in the optimal EPIC mechanism, certain deviations would lead to a payoff loss of at least η for the agent. This is where the -η term in the second bracket comes from.

Similarly, we can show that any deviation to θi ∈ Θ

* i (q i , θ -i ) \ Θ * i (q i , θ -i ) and θi / ∈ Θ * i (q i , θ -i ) ∪ Θ * i (q i , θ -i ) is not profitable either. Case (ii): θ i ∈ Θ * i (q i , θ -i ) \ Θ * i (q i , θ -i ) and θ * i (q i , θ -i ) ∈ Θ * i (q i , θ -i ).
Consider a new mechanism (M, q * , p * ) such that

M i = Θ i × [0, 1], M j = Θ j for 22
Particularly, the expected gain by deviation is

β • v i (q EP i ( θi , θ -i ), θi , θ -i ) -p EP i ( θi , θ -i ) + β • v i (q EP i ( θi , θ -i ), θi , θ -i ) -p EP i ( θi , θ -i ) -β • v i (q EP i ( θi , θ -i ), θi , θ -i ) -p EP i ( θi , θ -i ) -η • (1 -x * (β, β )) -β • v i (q EP i ( θi , θ -i ), θi , θ -i ) -p EP i ( θi , θ -i ) -η • ψ(x * (β, β )) ≤β • η • (1 -x * (β, β )) + β • η • ψ(x * (β, β )) + β • 0 -β • v i (q EP i ( θi , θ -i ), θi , θ -i ) -p EP i ( θi , θ -i ) -v i (q EP i ( θi , θ -i ), θi , θ -i ) + p EP i ( θi , θ -i ) .
Without loss of generality, we assume that q i ∈ Q + i , so that q EP i θ * i (q i , θ -i ), θ -i = q i ; otherwise we can replace q i by q

EP i θ * i (q i , θ -i ), θ -i . Because q EP i ( θi , θ -i ) ≥ q i > q EP i ( θi , θ -i ), θi θ -i i θ * i (q i , θ -i ) θ -i i
θi , then the terms in the last bracket satisfy

v i (q EP i ( θi , θ -i ), θi , θ -i ) -p EP i ( θi , θ -i ) -v i (q EP i ( θi , θ -i ), θi , θ -i ) + p EP i ( θi , θ -i ) ≥v i (q i , θ * i (q i , θ -i ), θ -i ) -p EP i (θ * i (q i , θ -i ), θ -i ) -v i (q EP i ( θi , θ -i ), θ * i (q i , θ -i ), θ -i ) + p EP i ( θi , θ -i ) + v i (q i , θi , θ -i ) -v i (q i , θ * i (q i , θ -i ), θ -i ) -v i (q EP i ( θi , θ -i ), θi , θ -i ) + v i (q EP i ( θi , θ -i ), θ * i (q i , θ -i ), θ -i ) ≥0 + η. j = i, and for each (( θi , x), θ-i ) ∈ M , q * (( θi , x), θ-i ) = q EP ( θ), p * j (( θi , x), θ-i ) = p EP j ( θ), ∀j = i,
and for p * i , we set

p * i (( θi , x), θ-i ) = p EP i ( θ) unless θi ∈ Θ * i (q i , θ -i ) \ Θ * i (q i , θ -i ) and θ-i ∈ {θ -i , θ -i }; and for each θi ∈ Θ * i (q i , θ -i ) \ Θ * i (q i , θ -i ), we set p * i (( θi , x), θ -i ) = p EP i ( θi , θ -i ) + η(1 -x), p * i (( θi , x), θ -i ) = p EP i ( θi , θ -i ) + ηψ(x), where ψ(x) = 1 - √ 1 -x 2 .
Again, x ∈ [0, 1] is related to agent i's first-order belief over θ -i and θ -i . Indeed, if agent i reports his payoff type θ i truthfully, his optimal choice of x is given by

x * (β, β ) = (β/β ) 2 1+(β/β ) 2
, where β is i's first-order belief for θ -i and β is i's firstorder belief for θ -i . Note that, given any µ ∈ M full , agent i chooses x ∈ (0, 1) with probability one.

It is obvious that, if the agents report their payoff types truthfully (and agent i chooses x optimally), then this new mechanism yields a strictly higher expected revenue than the optimal EPIC mechanism.

For any agent j = i, the new mechanism is outcome-equivalent to the optimal EPIC mechanism, and hence satisfies EPIC and EPIR.

We show the incentive compatibility of agent i with θi ∈ Θ

* i (q i , θ -i )\ Θ * i (q i , θ -i )
(for the other payoff types, the new mechanism is outcome-equivalent to the optimal EPIC mechanism, and hence satisfies EPIC and EPIR). First, obviously, any as follows (and all the other parts of the mechanism are the same as before):

q * * j ((θ i , 1), θ * j (q j , θ i , θ-ij ), θ-ij ) = q * j ((θ i , 1), θj , θ-ij ), p * * j ((θ i , 1), θ * j (q j , θ i , θ-ij ), θ-ij ) = p * j ((θ i , 1), θj , θ-ij ), p * * j ((θ i , 1), θ j , θ-ij ) = p * j (θ i , θ j , θ-ij ) + η, ∀θ j θ i , θ-ij j θ * j (q j , θ i , θ-ij ) p * * i ((θ i , 1), θ * j (q j , θ i , θ-ij ), θ-ij ) = M,
where θj is j's payoff type that is just below θ * j (q j , θ i , θ-ij ) with respect to ≺

θ i , θ-ij j ,
and M > 0 is sufficiently large.

Observe that the modified mechanism satisfies all the constraints. First, except for agents i and j, the allocations are the same as in the previous mechanism. For agent i, large fine M is irrelevant unless he assigns zero probability for θ -i (because x = 1 is not optimal for him); on the other hand, if he assigns zero probability for θ -i , then this large fine is also payoff-irrelevant for him. Finally, for agent j, we only need to check his incentive if i reports (θ i , 1) and -ij report θij : in such a case, j with payoff type θj θ i , θ-ij i θ * j (q j , θ i , θ-ij ) has no incentive of misreporting, because their on-path payoffs would be the same as in the original mechanism, while the other types' payments are higher than in the original mechanism. For θj

θ i , θ-ij i θ * j (q j , θ i , θ-ij ), his payoff by deviation is at most 23 v j (q * j ((θ i , 1), θj , θ-ij ), θ i , θj , θ-ij ) -p * j ((θ i , 1), θj , θ-ij ) ≤ v j (q * j ((θ i , 1), θj , θ-ij ), θ i , θj , θ-ij ) -p * j ((θ i , 1), θj , θ-ij ) -η,
23 By the same argument as in Footnote 22, pretending to have θ j θi, θ-ij i θ * j (q j , θ i , θ-ij ) for agent j with θj θi, θ-ij i θ * j (q j , θ i , θ-ij ) would lead to a payoff loss of at least η. Moreover, he would not misreport a different θ j θi, θ-ij i θ * j (q j , θ i , θ-ij ), because the increase in payment for

{θ j | θ j θi, θ-ij i θ * j (q j , θ i , θ-ij )} is uniform.
but the right-hand side is precisely his on-path payoff. The individual rationality constraints can be checked similarly.

Finally, we show that this modified mechanism achieves a strictly higher expected revenue than the original mechanism. First, observe that it does not yield a lower payoff given any payoff-type profile. It is obvious except when the payofftype profile is (θ i , θ * j (q j , θ i , θ-ij ), θ-ij ) and agent i chooses x = 1; if this is the realized payoff-type profile, and agent i reports x = 1, agent i pays a large fine M .

Therefore, the principal would be better off by setting M large enough.

Consider a payoff-type profile (θ i , θj , θ-ij ) such that θj

θ i , θ-ij i θ * j (q j , θ i , θ-ij ).
Due to the full-support assumption on the principal's prior belief for θ, (θ i , θj , θ-ij ) occurs with strictly positive probability; that is, the µ-measure of subset {t ∈

T * | θ * (t) = (θ i , θj , θ-ij )} is strictly positive. If agent i chooses x < 1 (at least
with a positive probability), then i pays η(1 -x)(> 0) more than in the original mechanism, and hence, strict improvement is achieved. If agent i chooses x = 1 (with probability one), then the principal increases j's payment by η as explained above, and thus, again strict improvement is achieved.

D Proof of Theorem 3

It suffices to show that ordinal interdependence implies strong improvability.

By ordinal interdependence, there exist i, θ -i , θ -i such that ≺

θ -i i =≺ θ -i i .
We first observe the following lemma.

Lemma 6. Ordinal interdependence implies that there exist j = i, θ j , θ j , and θ-ij such that ≺

θ j , θ-ij i =≺ θ j , θ-ij i .
Proof of Lemma 6. Let i = 1 without loss of generality, and for each n = 1, . . . , I, let θ n -1 = ((θ j ) n j=2 , (θ j ) I j=n+1 ). Note that θ 1 -1 = θ -1 and θ I -1 = θ -1 .

If ≺

θ n-1 -1 1 =≺ θ n -1
1 for all n = 2, . . . , I, then we have θ 1 -1 = θ I -1 , contradicting that

≺ θ -1 1 =≺ θ -1
1 . Therefore, there exists n ∈ {2, . . . , I} such that ≺

θ n-1 -1 1 =≺ θ n -1
way described below), and prove the statement. Then, we provide a continuity argument showing that, even with strong admissibility, the statement goes through.

Let β ω be the degenerate belief which puts probability 1 on having ω. Define µ EP such that µ EP {ω} × {θ} × {β ω } = f (ω, θ) for all ω, θ.

Because the agent knows the realization of ω when reporting to the principal, the optimal BIC mechanism for µ EP is the optimal EPIC mechanism. Since R µ EP (Γ) ≥ R EP f , we have (q, p)(ω, θ, β ω ) = (q EP , p EP )(ω, θ) for all ω, θ.

Suppose that there exists some ω, θ, β such that p(ω, θ, β) < p EP (ω, θ). Consider a joint belief μ satisfying:

(i) μ {ω} × {θ} × {β ω } = f (ω, θ) for all (ω, θ) = (ω, θ);

(ii) μ {ω} × { θ} × { β} = f (ω, θ).

This μ does not satisfy our strong admissibility, and we take care of this point at the end of the proof.

Given μ, we have Similarly, θ = 2 won't report θ = 0. Clearly, the new mechanism achieves weakly higher expected revenue than Γ for any µ, and strictly higher expected revenue when µ {0} × {2} × {y | ȳ < y < 1} > 0.

Now we show the converse, completing the proof of the proposition. By Lemma 8, Γ cannot dominate Γ.

F Miscellany F.1 A sufficient condition for Assumption 1

When there is no ordinal interdependence, ≺ i does not depend on θ -i for all i.

As in [START_REF] Chung | Foundations of dominant-strategy mechanisms[END_REF], we consider the auction environment where Θ i = {θ 1 i , . . . , θ M i } satisfying θ m i -θ m-1 i = γ > 0 for each m, and agent i's valuation given payoff type profile θ is v i (θ). The following lemma characterizes a class of interdependent-value environments satisfying Assumption 1.

Lemma 11. Under the following conditions,

(1) f (θ) is affiliated: for all θ and θ , we have f (θ ∨ θ )f (θ ∧ θ ) ≥ f (θ)f (θ );

(2) f (θ) has increasing hazard rate: f (θ i |θ -i ) 1-F i (θ i |θ -i ) is increasing on θ i ;

  and thus, ε = -β n→n-1 i /( π i (θ n i ) • λ) > 0. If we add ελ to p i (θ n-1 i , •), then allthe constraints for types θ l i with l = n are unaffected because π i (θ l i ) • λ = 0 for all l = n, and for type θ n i only constraint (BIC n→n-1 i) is changed, which holds with equality under the new payment rule. Because f (θ n-1 , •) • (ελ) = ε > 0, the expected revenue increases under the new payment rule.

Rb

  μ(Γ) = (ω,θ) =(ω, θ) f (ω, θ)p EP (ω, θ) + f (ω, θ)p(ω, θ, β)< (ω,θ) =(ω, θ) f (ω, θ)p EP (ω, θ) + f (ω, θ)p EP (ω, θ) = R EP f .Now, recall that the above μ does not satisfy our strong admissibility. However, it is easy to construct a sequence {µ k } k∈N , where each µ k is strongly admissible and converges to μ (in a weak-* topology), and along the sequence the expected Then, ∂Y is a continuous convex curve connecting the two points (2, 3) and (3, 2).∂Y is related with (a(y), b(y)) in the following way. On one hand, (a(y), b(y)) ∈ ∂Y for all y ∈ [0, 1]; otherwise there exists, 2 > 0 such that (a -, b -2 ) ∈ Y ⊆ Y (y),violating the definition of Y (y). On the other hand, for any (a, b) ∈ ∂Y satisfying (1-y )a+y b < (1-y )a +y b for some y and any other (a , b ) ∈ ∂Y , we must have (a, b) = (a(y ), b(y )). To prove this, suppose that (a, b) = (a(y ), b(y )), then we have (1-y )a+y b < (1-y )a(y )+y b(y ), which means that (a, b) / ∈ Y (y ). It follows that (a, b) / ∈ Y , contradicting (a, b) ∈ ∂Y . Putting a on the horizontal axis and b on the vertical axis, we define the function bsuch that (a, b ) ∈ ∂Y if 2 < a ≤ 3. Immediately, we have ∂Y = {(a, b) | b = b(a)} ∪ {(2, b) | b(a) < b ≤ 3}. Moreover, b = b(a) is convex, continuous, and non-increasing (otherwise it would violate b(y) ≥ 2 for all y). Now we show (ii). Suppose we have b = lim y→0 b(y) < 3 and ā = lim y→1 a(y) < 3, then define ȳ such that (1-ȳ)(3-ā) = ȳ(3-b). Consider the following payment rule for θ = 2, b(y) + 3 -b if 0 ≤ y ≤ ȳ a(y) + 3 -ā, b(y) if ȳ < y ≤ 1.Obviously, θ = 0, 1 won't pretend to be θ = 2. Also, θ = 2 with y, y ∈ [0, ȳ] (or y, y ∈ (ȳ, 1]) won't pretend to be each other, because the changes in payment are the same. Pick y ∈ [0, ȳ] and y ∈ (ȳ, 1], since we have (1 -y)ã(y) + y b(y) = (1 -y)a(y) + y b(y) + 3 -b = (1 -y)a(y) + yb(y) + y(3 -b) ≤ (1 -y)a(y ) + yb(y ) + (1 -y)(3 -ā) = (1 -y) a(y ) + 3 -ā + yb(y ) = (1 -y)ã(y ) + y b(y ), then the expected payment is lower by telling the truth than misreporting. By a similar argument, agent with y won't pretend to have y, either. Agent θ = 2 won't report θ = 1 because (1 -y)(3 -ã(y)) + y(3 -b(y)) ≥ (1 -y)(3 -ã(1)) + y(3 -b(1)) = (1 -y) 3 -a(1) -3 + ā + y(3 -b(1)) = (1 -y) • 0 + y(3 -p(1, 1)).

Lemma 10 .

 10 Suppose that Γ is in Γ * with (a(y), b(y)) y∈[0,1] satisfying (i) (a(y), b(y)) y∈[0,1] (as a set of points on R 2 ) lies on a continuous, convex, non-increasing curve that connects (2, 3) and (3, 2); and (ii) either lim y↓1 a(y) = 3 or lim y↓0 b(y) = 3 holds (or both). Then, Γ is in Γ U .Proof. Suppose there exists Γ that dominates Γ. Assume that the payment rules for θ = 2 in Γ and Γ are (a(y), b(y)) and (a (y), b (y)), respectively. First, we show that the two corresponding curves, denoted by b = b(a) and b = b (a ), have no interior common point: If they do, then we can find (s, t) with s ∈ (2, 3) such that, either right derivatives or left derivatives of the two curves at (s, t) are different; otherwise b = b(a) and b = b (a ) would be the same. Without loss of generality, assume that the left derivatives, given by k = ∂ -b(s) := lim a→s - b(a) -b(s) a -s , k = ∂ -b (s) := lim a →s - b(a ) -b(s) a -s , satisfies (-∞ <) k < k (< 0). Then, pick y ∈ (k, k ), and we have a (y) < s ≤ a(y), b (y) > t ≥ b(y). By Lemma 8, Γ and Γ cannot dominate each other. Thus, b = b(a) and b = b (a ) can only have common point in {(s, t) | s = 2 or t = 2}. Without loss of generality, we assume that lim y→0 b(y) = lim y→0 b (y) = 3. Additionally, we must have b (a) > b(a) for all a ∈ (2, 3); otherwise Γ cannot dominate Γ. Fixed ā ∈ (2, 3), since lim y→0 b(y) -b (y) = 0, we can find a ∈ (0, ā) such that b (a) -b(a) = 1 2 b (ā) -b(ā) . By Lemma 9, both b = b(a) and b = b (a ) have derivatives almost everywhere on [a, ā] (as convex functions, they are absolutely continuous). Suppose ∂ -b(s) ≥ ∂ -b (s) for all s ∈ [a, ā]. Then we have b (ā) -b(ā) = b (a) + ā a ∂ -b (s)ds -b(a) -ā a ∂ -b(s)ds = b (a) -b(a) + ā a ∂ -b (s) -∂ -b(s) ds ≤ b (a) -b(a) < b (ā) -b(ā), which forms a contradiction. Thus, there exists some s ∈ [a, ā] such that ∂ -b(s) < ∂ -b (s). Picking y such that ∂ -b(s) < y < ∂ -b (s), we have b (y) > b (s) > b(s) ≥ b(y), a (y) < s ≤ a(y).

Table 2 :

 2 Auction environment of Example 2.

See, for example,[START_REF] Wilson | Incentive efficiency of double auctions[END_REF].

As a stronger concept, if the same belief can be found for any non-dominant-strategy mechanism with which a dominant-strategy mechanism achieves (weakly) higher expected revenue, then there is a Bayesian foundation, because, as long as the seller is Bayesian rational and has that particular belief, he finds it optimal to offer a dominant-strategy mechanism, even though he can also offer any other mechanism.

These interdependence concepts are obviously related to the "size" of interdependence (e.g., private-value environments are special cases of cardinally interdependent cases). However, they are not necessarily corresponding to each other. For example, if a bidder's valuation in an auction is a sum of a function only of his own type and another function of the others' types, then however large is the second term, the environment never exhibits ordinal interdependence. In this sense, a more appropriate interpretation is that these interdependent concepts are related to the diversity of interdependence across types.

As it becomes clearer, the finiteness of Q i is without loss of generality (though it simplifies the notation), given that Θ is finite and we only consider finite mechanisms (including ex post incentive compatible mechanisms).

See, for example, Example 5.1 in[START_REF] Jehiel | The limits of ex post implementation[END_REF].

For constructions of universal type spaces, see[START_REF] Mertens | Formulation of Bayesian Analysis for Games with Incomplete Information[END_REF] and[START_REF] Brandenburger | Hierarchies of Beliefs and Common Knowledge[END_REF].

The results would not change even if we allow for type spaces with redundant types, but the notation would be more involved.

In[START_REF] Chung | Foundations of dominant-strategy mechanisms[END_REF], they show by example that, without the condition corresponding to Assumption 1, there may not exist a Bayesian foundation.

Instead, if there is no ordinal interdependence, we will have the same ranking of payoff types, and thus the same subset of binding constraints, for all θ -i in the optimal EPIC mechanism.

See Mussa and Rosen (1978) and[START_REF] Segal | Optimal pricing mechanisms with unknown demand[END_REF] (or their straightforward generalizations) for such environments, although they focus on private-value environments.

[START_REF] Börgers | Foundations of dominant-strategy mechanisms: a comment on Chung and Ely (2007)[END_REF] shows that the dominant-strategy mechanism of[START_REF] Chung | Foundations of dominant-strategy mechanisms[END_REF] is dominated in private-value environments with three or more agents. Characterizing the class of undominated mechanisms seems an open question.

We can always find such a sequence because the set of all non-singular distributions is a dense subset of the set of all distributions over Θ.

i (θ i , θ -i ) > 0 can be similarly shown by a symmetric argument 25 Because γ i (q i , θ + i (θ -i ), θ -i ) > 0 for some q i , we only need to consider the case q i > q + i . Since γ i (0, θ + i (θ -i ), θ -i ) = 0, by strict quasi-concavity, we have γ i (q + i , θ + i (θ -i ), θ -i ) > 0.

Takuro Yamashita also gratefully acknowledges financial support from the European Research Council (Starting Grant #714693).

any µ ∈ M full , agent i chooses x ∈ (0, 1) with probability one.

It is then obvious that, if the agents report their payoff types truthfully (and agent i chooses x optimally), then this new mechanism yields a strictly higher expected revenue than the optimal EPIC mechanism.

For any agent j = i, the new mechanism is outcome-equivalent to the optimal EPIC mechanism, and hence satisfies EPIC and EPIR.

We show the incentive compatibility of agent i with θi ∈ Θ * i (q i , θ -i )∩Θ * i (q i , θ -i )

(for the other payoff types, the new mechanism is outcome-equivalent to the optimal EPIC mechanism, and hence satisfies EPIC and EPIR). First, obviously, any

) is not profitable either, because, letting β and β be his first-order beliefs for θ -i and θ -i respectively, the expected gain by deviation

) is not profitable either, because, letting β and β be his first-order beliefs for θ -i and θ -i respectively, the expected gain by deviation is at most

Similarly, we can show that any deviation to θi ∈

Case (iii) is symmetry to case (ii), thus we omit its proof. In conclusion, EPIC mechanisms do not have the strong foundation.

C Proof of Proposition 2

Assume that (i, θ i , θ j , q j , θ-ij ) satisfies the definition of strong improvability. We use the same mechanism as in Proposition 1, except that the allocations for agent i and j change in case agent i reports θ i and x = 1. Recall that, given his truthfully reporting θ i , agent i's optimal choice of x is

1+(β/β ) 2 where β, β are his first-order beliefs for θ -i , θ -i , respectively, with θ -i = (θ j , θ-ij ) and θ -i = (θ * j (q j , θ i , θ-ij ), θ-ij ); x = 1 means that he predicts that j does not have a threshold type for q j given (θ i , θ-ij ). The allocations from agents i and j are then modified revenue also converges. Therefore, it contradicts that Γ dominates the optimal EPIC mechanism.

This lemma implies that, if Γ is in Γ U , then it must be in Γ * . The next lemma shows that, based on a similar logic, if a mechanism that dominates the optimal EPIC mechanism is further dominated by an alternative mechanism, this alternative mechanism must have a pointwise (weakly-)higher payment than that mechanism.

Lemma 8. Mechanism Γ = (T, q, p) that dominates the optimal EPIC mechanism is dominated by Γ = (T, q, p) if and only if p(ω, θ, β) ≥ p(ω, θ, β) for all (ω, θ, β).

Next, we obtain further properties of

(as a set of points on R 2 ) lies on a continuous, convex, nonincreasing curve that connects (2, 3) and (3, 2); and (ii) either lim y↑1 a(y) = 3 or lim y↓0 b(y) = 3 holds (or both).

Proof. We first show (i). By Lemma 7 and the IR constraints, we obtain:

for (ω, θ) = (0, 0), (0, 1), (1, 0), (1, 1) and any β ∈ ∆(Ω); and

for any β ∈ ∆(Ω). Recall our notation: a(y) = p(0, 2, β), and b(y) = p(1, 2, β) for y = β(1).

Due to the IC constraint that type (θ = 2, y = 0) won't pretend to be (θ = 0, y = 0), we have a(0) = 2; similarly we have b(1) = 2. For any y ∈ (0, 1), we must have a(y) ≤ 3; otherwise reporting θ = 1 is a profitable deviation. Similarly we have b(y) ≤ 3 for any y ∈ (0, 1). Notice that

for all y ∈ (0, 1). Thus, given any > 0, we have

for all y < +1 . Therefore, we have lim y↓0 a(y) = 2. Similarly, we have lim y↑1 b(y) = 2. It follows that a(y) + b(y) ≤ 5 for any y ∈ (0, 1); otherwise either (a( ), b( ))

or (a(1 -), b(1 -)) would be a profitable deviation for sufficiently small (> 0).

On the other hand, by assumption on µ, the value of a(1) (or b(0)) is irrelevant, as long as type θ = 2 with y = 1 (or y = 0) won't pretend to be y = 1 (or y = 0).

Thus, without loss of generality, we choose a(1) = b(0) = 3.

For each y ∈ [0, 1], define

which is convex and compact, and contains

, and then Y is also convex and compact. Let ∂Y be the boundary of Y which is below the line a + b = 5, that is,

(3) v i (θ) is increasing and concave:

virtual valuation satisfies the regularity conditions: ∀θ, ∀i ∈ {1, . . . I}, ∀j ∈ {0, 1, . . . I} \ {i}, we have

where γ 0 (•) ≡ 0, and

Proof. Condition (1) implies: ∀θ i < θ i , ∀θ j < θ j , ∀θ -ij , we have

Condition (4) implies: ∀θ i < θ i , ∀θ j < θ j , ∀θ -ij , we have

Write θ + i := θ i + γ. For any θi > θ i , we have

Thus, γ i ( θi , θ -i ) -γ j ( θi , θ -i ) ≥ 0 as long as γ i (θ) -γ j (θ) ≥ 0.

F.2 Proof of Lemma 3

Let q EP i (θ), p EP i (θ) i,θ denote the optimal EPIC mechanism. First, we prove that any agent with non-positive virtual value should not be assigned the good in the optimal EPIC mechanism.

Lemma 12. Under condition-(i) in Lemma 3, if γ i (q i , θ) ≤ 0 for any q i , then q EP i (θ) = 0.