HIAS-E-137

Shill-proof rules in object allocation problems with money

Hiroki Shinozaki
Hitotsubashi University

February 13, 2024

Hitotsubashi Institute for Advanced Study, Hitotsubashi University
2-1, Naka, Kunitachi, Tokyo 186-8601, Japan
tel:+81 42 580 8668 http://hias.hit-u.ac.jp/
HIAS discussion papers can be downloaded without charge from:https://hdl.handle.net/10086/27202
https://ideas.repec.org/s/hit/hiasdp.html

Shill-proof rules in object allocation problems withmoney∗
Hiroki Shinozaki†
February 13, 2024

Abstract
We consider the object allocation problem with money. The seller owns multiple
units of an object, and is only interested in her revenue from an allocation. Eachbuyer receives at most one unit of the object, and has a quasi-linear utility function
with private valuations. We study incentives of the seller to increase her revenue by
introducing false-name buyers, i.e., shill bidding. An (allocation) rule is shill-proof
if the seller never beneﬁts from introducing false-name buyers. A rule is a binary
posted prices rule if there is a proﬁle of posted prices such that whenever a buyer
receives the object, she pays either her posted price or zero, and her payment is equal
to zero when she does not receive the object. We show that if a rule satisﬁes shillproofness, strategy-proofness, and non-imposition, then it is a binary posted prices
rule. This result shows that the cost of preventing the seller from shill bidding isequivalent to the rigidity of the payment of each buyer, which highlights the diﬃculty
in preventing the seller from shill bidding. It extends to a model of non-quasi-linear
utility functions with interdependent valuations.

JEL Classiﬁcation Numbers. D44, D47, D71, D82

Keywords. Shill-proofness, Shill bidding, Strategy-proofness, Posted prices rule, Binary posted prices rule, Multi-unit auctions∗

The author gratefully acknowledges ﬁnancial support from the Japan society for the Promotion of
Sciences (23K18777).
†
Hitotsubashi Institute for Advanced Study, Hitotsubashi University. Email: shinozakiecon@gmail.com

1

1

Introduction

1.1

PurposeIn recent years, a countless number of goods are traded via online platforms. Internet
auctions are one of the most typical electric commerce, and the market size of internet
auctions is huge. Indeed, in 2022, the Gross Merchandise Value of eBay, one of the biggest
auction houses in the world, amounted to 73.9 million dollars. 1
A characteristic of internet auctions is that buyers and sellers are able to trade goods
anonymously, i.e., they do not need to reveal their identity in transactions. This anonymity
enables a seller to make additional buyer accounts to drive up a hammer price. Such a
bidding by a seller is called shill bidding. Shill bidding is undesirable from the point ofview of buyers as it unfairly raises the prices that they pay. Indeed, most auction houses
announce the policy that shill bidding is prohibited, and sellers whose shill bidding is
detected are punished by the auction houses or the law.2 Nevertheless, shill bidding is still
pervasive in real-life internet auctions because of the ease of conducting it for a seller andthe diﬃculty of detecting for an auction house. Several empirical as well as experimental
results support that shill bidding is pervasive in real-life auctions (Kosmopoulou and De
silva, 2007; Engelberg and Willaims, 2009; McCannon and Minuci, 2020; Carlson and Wu,
2022, etc.). For example, Engelberg and Williams (2009) estimated that in Event Ticket
Auctions in eBay that ended between September 8, 2004 and September 23, 2004, 1.39
percent of all bids are particular shill bids by sellers.
There are at least two possible approaches to preventing the seller from shill bidding:one is to develop the technology of detecting shill bids, and the other is to design a rule that
does not give a seller an incentive to do shill bidding. 3 We take the latter approach, andinvestigate the class of rules that prevent a seller from shill bidding in the object allocation
problem with money.

1

See the following: https://investors.ebayinc.com/investor-news/press-release-details/
2023/eBay-Inc.-Reports-Better-Than-Expected-Fourth-Quarter-2022-Results/default.aspx.
2
For example, the following is the announcement of the policy for shill bidding by
https://www.ebay.com/help/policies/selling-policies/selling-practices-policy/
eBay:
shill-bidding-policy?id=4353.
3Computer scientists have recently taken the former approach and developed detection techniques ofshill bidding. See Majadi et al. (2017) for a comprehensive survey on this line of research.

2

1.2

Main result

We study the object allocation problem with money. The seller owns m ≥ 1 units of an
object. A (consumption) bundle of a buyer is a pair consisting of a consumption of theobject and a payment. Each buyer can receive at most one unit of the object, and has aquasi-linear utility function with private valuations over the set of consumption bundles.
Note that a quasi-linear utility function is identiﬁed with a valuation of the object. We
consider a model where the set of buyers can vary, and a domain is a set of valuations of
all the potential buyers. An economy is a pair consisting of a set of buyers and a valuation
proﬁle for the set of buyers. An allocation for a given economy speciﬁes a bundle for eachbuyer in the economy. We assume that the seller is only interested in her revenue froman allocation, and so she does not care who receives the object. An (allocation) rule on a
domain is a mapping which associates an allocation with each economy.
We introduce a new property of rules which prevents the seller from shill bidding. A
rule satisﬁes shill-proofness if, for a given economy, the seller is never able to increase
her revenue by introducing false-name buyers with arbitrary valuations (i.e., by shill bidding). We introduce the two standard properties of rules in the literature. A rule satisﬁes
strategy-proofness if, for a given economy, no buyer in the economy ever beneﬁts frommisrepresenting her valuations. It satisﬁes non-imposition if, for a given economy, a buyer
in the economy who views the object as valueless enjoys the utility of zero. Note that
non-imposition is so mild property that almost all standard rules satisfy it. We regard
shill-proofness together with strategy-proofness and non-imposition as our basic desiderata, and investigate the class of rules satisfying those.
We introduce a new class of rules which extends a posted prices rules under which eachbuyer who receives the object pays her posted price, and each buyer who does not receive
it pays nothing.4 A rule is a binary posted prices rule if there is a proﬁle of posted prices
such that for each economy, if a buyer in the economy receives the object, then she pays
either her posted price or zero, and otherwise, she pays nothing. Note that the diﬀerence
between a binary posted prices rule and a posted prices rule lies in the ﬂexibility in thepayment of each buyer: a binary posted prices rule allows the payment of each buyer who
receives the object to be either her posted price or zero, while a posted prices rule requires
4

Recently, several authors have studied the particular subclass of posted prices rules called the priority
rules (Klaus and Nichifor, 2020, 2021; Shinozaki, 2022; Kawasaki et al., 2023). See Section 2.4 for thedetailed discussion.

3

the payment of each buyer who receives the object to be her posted price.
A domain is said to be rich if the class of valuations of each buyer is some interval
whose lower bound is zero. The main result of this paper is as follows. We establish that if
a rule on a rich domain satisﬁes shill-proofness, strategy-proofness, and non-imposition,then it is a binary posted prices rule. (Theorem 1).
Note that a binary posted prices rule gives little ﬂexibility to each buyer’s payment as
it must take one of the two values (i.e., it must be either her posted price or zero). Thus,
Theorem 1 shows that the cost of preventing the seller from shill bidding is equivalent to
the rigidity of the payment of each buyer, which highlights the diﬃculty in preventing aseller from shill bidding.
We assume that each buyer has a quasi-linear utility function with private valuations
in our model, and so in Theorem 1 as well. This assumption is only for the expositional
simplicity, and Theorem 1 carries over to a model of non-quasi-linear utility functions withinterdependent valuations (Proposition 7). In particular, it holds for a model of quasilinear utility functions with private, common, or interdependent valuations and that of
non-quasi-linear utility functions with private or interdependent valuations.

1.3

Organization

The rest of this paper is organized as follows. Section 2 reviews the related literature. Section 3 introduces the model. Section 4 introduces the binary posted price rules. Section 5
presents the main result. Section 6 discusses the several extensions of the main result.
Section 7 concludes. All the proofs are relegated to the Appendix.

2

Related literature

In this section, we review the related literature, and discuss how this paper contributes to
it.

2.1

Shill bidding by the seller

There are several papers that study the seller’s shill bidding as in this paper. Graham
et al. (1990) study the equilibrium of an English auction in a private valuations model,
and show that the seller may beneﬁt from shill bidding in an equilibrium. Chakraborty
4and Kosmopoulou (2004) identify the equilibrium of an English auction in a common
valuation model, and show that the seller’s equilibrium expected revenue under an English
auction may get worse oﬀ by the possibility of shill bidding. Lamy (2009) shows thatin an interdependent valuations model, the seller’s equilibrium expected revenue under asecond-price auction may get worse oﬀ with the possibility of shill bidding than without shillbidding. Levin and Peck (2023) study shill bidding by the seller in a common valuations
model, and compare the revenue from optimal shill bidding behavior under an English
auction and that under a Sophi auction.
The main diﬀerence between this paper and the previous papers that study shill biddingby the seller lies in the attitude toward shill bidding. The previous papers allow thepossibility of shill bidding, and study the equilibrium properties or the seller’s optimal
behavior in the presence of shill bidding under their speciﬁc rules. In contrast, we regard
shill bidding as a fraud that should be prevented, and study the class of rules preventing
the seller from shill bidding. Our main result (Theorem 1) contributes to this line ofresearch by identifying the cost of preventing the seller from shill bidding: the rigidity ofthe payment of each buyer.

2.2

Shill bidding by the buyers

In this paper, we study shill bidding by the seller. In contrast, some papers study rulesthat prevent the buyers from shill bidding (a shill bid by a buyer is called a false-name bid
in the literature). A rule is false-name-proof (Yokoo et al., 2004) if no buyer ever beneﬁts
from introducing false-name buyers. Yokoo et al. (2004) identiﬁes a suﬃcient condition fora Vickrey rule (Vickrey, 1961) to satisfy false-name-proofness in a heterogeneous objects
model. Sher (2012) identiﬁes the optimal shill bidding of a buyer under a Vickrey rule ina heterogeneous objects model.
The result by Yokoo et al. (2004) implies that in our setting of multiple units ofidentical objects and unit-demand buyers, a Vickrey rule satisﬁes false-name-proofness aswell as strategy-proofness, non-imposition, and eﬃciency. In contrast, our main result(Theorem 1) shows the diﬃculty in preventing the seller from shill bidding, and implies
the non-existence of a rule satisfying shill-proofness, strategy-proofness, eﬃciency, andnon-imposition (Corollary 1). Our result contributes to this line of research by suggestingthat preventing the seller from shill bidding is more diﬃcult than preventing the buyers
5from it.

2.3

Other frauds by the seller

Shill bidding is one of the possible frauds by the seller. The classes of rules that prevent theseller from frauds diﬀerent from shill bidding have been studied. Muto and Shirata (2017)
study the seller’s incentive to destruct the objects to increase her utility, and show that norule satisﬁes eﬃciency and strategy-proofness that simultaneously prevents the seller fromdestructing the objects. Akbarpour and Li (2020) study the seller’s incentive to change
outcome allocation of a rule without being detected by the buyers, and characterize theﬁrst-price rules as the unique static rules preventing such a fraud and satisfying Bayesian
incentive compatibility and eﬃciency, and the English rules as the unique dynamic rules
preventing it and satisfying strategy-proofness and eﬃciency. Shinozaki (2024b) studies
the seller’s incentive to collude with buyers to shut out other buyers, and shows that a
Vickrey rule prevents such collusion if and only if the substitutes condition of Kelso andCrawford (1982) holds. This paper complements this line of research by studying the classof rules that prevent the seller from a diﬀerent fraud from theirs: shill bidding.

2.4

Posted prices rules

Recently, several papers have characterized the priority rules in object allocation problems
with money (Klaus and Nichifor, 2020, 2021; Shinozaki, 2022; Kawasaki et al., 2023). 5
Note that the class of priority rules is a subset of that of posted price rules, which isin turn a subset of that of binary posted prices rules. Klaus and Nichifor (2020; 2021)
establish that in a model with unit-demand buyers, the priority rules are the only rules
satisfying consistency, strategy-proofness, and non-imposition together with the other auxiliary properties.6 Kawasaki et al. (2023) extend the results by Klaus and Nichifor (2020;2021) to a model with multi-demand buyers. Shinozaki (2022) shows that in a single
object model, the priority rules are the only rules satisfying pairwise strategy-proofness
5

A rule is a priority rule if there are a priority over buyers and a proﬁle of posted prices such that abuyer with the highest priority among the ones who are willing to pay their posted prices for the object
receives the object and pays her posted price, a buyer with the second highest priority receives the object
and pays her posted price, and the process continues until no buyer would like to receive the object withher posted price or the objects are exhausted.
6
A rule satisﬁes consistency if whenever some buyers leave an economy with their bundles, the outcome
bundles of the rule for all remaining buyers remain the same in the reduced economy.

6and non-imposition.7 Note that consistency implies shill-proofness, but the converse is
not necessarily true. Note also that in general, pairwise strategy-proofness does not imply
shill-proofness, and vice versa. Thus, the results in this paper neither imply nor are impliedby the results of these papers. This paper contributes to this line of research by proposing
a new variant of a posted prices rule (i.e., a binary posted prices rule) and providing a new
foundation of a (binary) posted prices by shill-proofness.

3

Model

We study the object allocation problem with money. We consider a model where the setof buyers can vary. The set of potential buyers is N. Let N = {N ⊆ N : 0 < |N | < ∞}denote the family of all non-empty and ﬁnite subsets of the set of potential buyers. The
single seller owns m ≥ 1 units of an object. Each buyer can receive at most one unit of
the object. Let M = {0, 1}. The amount of a payment made by a buyer i ∈ N is ti ∈ R.
The consumption set of a buyer i ∈ N is M × R. A (consumption) bundle of a buyeri ∈ N is an element of her consumption set, i.e., it is a pair zi = (xi , ti ) ∈ M × R.
A valuation of a buyer i ∈ N is vi ∈ R+ . Our generic notation for a class of valuationsof a buyer i ∈ N is Vi ⊆ R+ . Note that a valuation of a buyer is private information only
known for her. Each buyer i ∈ N has a quasi-linear utility function ui : M × R → R suchthat for some valuation vi ∈ Vi , we have that for each zi = (xi , ti ) ∈ M × R, ui (zi ; vi ) =vi xi − ti . The assumptions of quasi-linear utility functions and private valuations are only
for the simplicity of exposition, and the main result of this paper will extend to the caseof non-quasi-linear utility functions with interdependent valuations. 8
Note that under the assumption of quasi-linear utility functions with private valuations,a utility function is equivalent to a valuation. Thus, we identify a class of utility functions
as that of valuation functions.
Given N ∈ N , let VN = ×i∈N Vi . A valuation proﬁle for N ∈ N is a tuple vN =(vi )i∈N ∈ VN . Let VN = ×i∈N Vi . We call VN a domain.
Given a domain VN , an economy on VN is a pair e = (N, vN ) such that N ∈ N andvN ∈ VN . Let E(VN ) denote the class of economies on VN . Note that the total number
7

A rule satisﬁes pairwise strategy-proofness if no pair of agents ever beneﬁts from misrepresenting theirvaluations.
8
For the detailed discussion, see Section 6.5.

7

of units of the object that the seller owns is ﬁxed at m ≥ 1 throughout the paper, and isomitted in an economy.
Given N ∈ N , a (feasible) object allocation for N is a tuple xN = (xi )i∈N ∈ M N
Psuch that i∈N xi ≤ m. Note that we focus only on deterministic object allocations. Let
XN denote the set of object allocations for a given N ∈ N . Given N ∈ N , a (feasible) allocation for N is a tuple zN = (zi )i∈N = (xi , ti )i∈N ∈ (M × R)N such that (xi )i∈N ∈ XN .
Let ZN denote the set of allocations for a given N ∈ N .
The seller is only interested in her revenue from an allocation. Thus, she has the(publicly known) quasi-linear utility function u0 : ∪N ∈N ZN → R such that for each N ∈ N
Pand each zN = (xi , ti )i∈N ∈ ZN , u0 (zN ) = i∈N ti .
Given a domain VN , an (allocation) rule on VN is a mapping f : E(VN ) → ∪N ∈N ZN
such that for each e = (N, vN ) ∈ E(VN ), f (e) ∈ ZN .
We introduce the properties of rules. The following is a new property of rules which
requires that the seller never beneﬁt from introducing false-name buyers (i.e., shill bidding).
Shill-proofness. For each e = (N, vN ) ∈ E(VN ), there exist no N ′ ∈ N with N ∩ N ′ = ∅PPfand vN ′ ∈ VN ′ such that i∈N tfi (N ∪ N ′ , vN ∪N ′ ) >i∈N ti (e).
Note that the set of buyers N ′ in the above deﬁnition consists of false-name buyers introduced by the seller, and their payments made by the seller are received by herself. Thus, the payments of the buyers in N ′ do not aﬀect the seller’s revenue, and thePseller’s revenue after introducing the false-name buyers N ′ is i∈N tfi (N ∪ N ′ , vN ∪N ′ ), notPf′i∈N ∪N ′ ti (N ∪ N , vN ∪N ′ ).
Next, we introduce the two standard properties of rules in the literature. The next
property requires that no buyer ever beneﬁt from misrepresenting her valuations.
Strategy-proofness. For each e = (N, vN ) ∈ E(VN ), each i ∈ N , and each vi′ ∈ Vi , wehave ui (fi (e); vi ) ≥ ui (fi (N, (vi′ , vN \{i} )); vi ).

The next property requires that if a buyer is not interested in the object (i.e., if her
valuation is zero), then her utility from an outcome bundle of a rule be equal to zero.

8

Non-imposition. For each e = (N, vN ) ∈ E(VN ) and each i ∈ N , if vi = 0, then ui (fi (e); vi ) =0.

Note that non-imposition is a mild property that almost all standard rules satisfy.
We regard shill-proofness, strategy-proofness, and non-imposition as our basic desiderata, and study the class of rules satisfying the three properties.
In addition, we introduce the three standard properties.
Given e = (N, vN ) ∈ E(VN ), an allocation zN = (zi )i∈N ∈ ZN for N is (Pareto) eﬃ′
cient for e if there is no other allocation zN= (zi′ )i∈N ∈ ZN for N such that (i) for each′i ∈ N , ui (zi′ ; vi ) ≥ ui (zi ; vi ), (ii) u0 (zN) ≥ u0 (zN ), and (iii) at least one of the inequalities

in (i) and (ii) is strict. The following remark states that under the assumption of quasilinear utility functions with private valuations, eﬃciency of an allocation is equivalent to
the maximization of the sum of valuations.
Remark 1. Let e = (N, vN ) ∈ E(VN ) and zN = (xi , ti )i∈N ∈ ZN . Then, zN is eﬃcient fore if and only if we havexN = (xi )i∈N ∈ arg max
x′N ∈XN

X

vi xi .

i∈N

First, the next property requires that a rule select an eﬃcient allocation for each economy.
Eﬃciency. For each e ∈ E, f (e) is eﬃcient for e.

Second, the next property requires that no buyer ever get worse oﬀ than the nonparticipation under which she enjoys the utility of zero.
Individual rationality. For each e = (N, vN ) ∈ E(VN ) and each i ∈ N , ui (fi (e); vi ) ≥ 0.

Third, the next property requires that the payment of each buyer be non-negative.
No subsidy. For each e = (N, vN ) ∈ E(VN ) and each i ∈ N , tfi (e) ≥ 0.

The next remark states that the combination of individual rationality and no subsidy
implies non-imposition.
9Remark 2. Let VN be a domain. Let f be a rule on VN satisfying individual rationality
and no subsidy. Then, it satisﬁes non-imposition.

4

Binary posted prices rule

In this section, we introduce the new class of rules that we call the binary posted prices
rules.
First, as a benchmark, we introduce the posted prices rules.
Deﬁnition 1. A rule f on VN is a posted prices rule if there is a proﬁle of posted prices(pfi )i∈N ∈ RN+ such that for each e = (N, vN ) ∈ E(VN ) and each i ∈ N , the following hold.
• If xfi (e) = 1, then tfi (e) = pfi and vi ≥ tfi (e).
• If xfi (e) = 0, then tfi (e) = 0.
The ﬁrst condition above states that if a buyer receives the object, then she pays her
posted price and is willing to pay her posted price. The second one states that if a buyer
does not receive the object, then she pays nothing. Note that a posted price may depend
on a rule and the identity of a buyer, but does not depend on a valuation proﬁle and the
population in an economy.
Then, we introduce a new variant of a posted prices rule that allows a buyer to pay her
posted price or zero for the object.
Deﬁnition 2. A rule f on VN is a binary posted prices rule if there is a proﬁle ofposted prices (pfi )i∈N ∈ RN+ such that for each e = (N, vN ) ∈ E(VN ) and each i ∈ N , thefollowing hold.
• If xfi (e) = 1, then tfi (e) ∈ {pfi , 0} and vi ≥ tfi (e).
• If xfi (e) = 0, then tfi (e) = 0.
Clearly, a posted prices rule is a binary posted prices rule, but the converse is notnecessarily true. Thus, the class of posted prices rules is a proper subset of that of binary
posted prices rules.
We give several examples of binary posted prices rules in the following example.

10

Example 1 (Binary posted prices rules). The following rules belong to the class ofbinary posted prices rules.
• A rule f on VN is the no trade rule if for each e = (N, vN ) ∈ E(VN ) and each i ∈ N ,fi (e) = (0, 0).
• A rule f on VN is an oligarchical rule if there is a set of buyers N̂ f ∈ N such that|N̂ f | ≤ m, and for each e = (N, vN ) ∈ E(VN ), we have that for each i ∈ N̂ f ∩ N ,fi (e) = (1, 0), and for each i ∈ N \N̂ f , fi (e) = (0, 0). An oligarchical rule with
|N f | = 1 is said to be a dictatorial rule.
• Given an economy e = (N, vN ) ∈ E(VN ) and a proﬁle of prices pN = (pi )i∈N ∈ RN+,
let N + (e, pN ) = {i ∈ N : vi ≥ pi } denote the set of buyers in N whose valuations
are no smaller than their own prices. A rule f on VN is a priority rule if there area priority ≻f over N and a proﬁle of posted prices (pfi )i∈N ∈ RN+ such that for eache = (N, vN ) ∈ E(VN ), the following hold.
– The buyer i1 ∈ N with the highest priority according to ≻f among N + (e, pfN )receives the object and pays pfi1 .
– The buyer i2 ∈ N with the second highest priority according to ≻f among
N + (e, pfN ) receives the object and pays pfi2 .
···– The buyer ik ∈ N with the k-th highest priority according to ≻f among N + (e, pfN )receives the object and pays pfik , where k = |N + (e, pfN )|.
– Each buyer in N \N + (e, pfN ) receives (0, 0).
• Let f be a rule on VN such that for each e = (N, vN ) ∈ E(VN ), the following hold.
– If 1 ∈ N , v1 ≥ 1, and maxi∈N \{1} vi ≤ 1, then f1 (e) = (1, 1).
– If 1 ∈ N , v1 < 1, and maxi∈N \{1} vi ≤ 1, then f1 (e) = (0, 0).
– If 1 ∈ N and maxi∈N \{1} vi > 1, then f1 (e) = (1, 0).
– For each i ∈ N \{1}, fi (e) = (0, 0).

11

The last rule in the above example shows that the payment of a buyer who receives
the object under a binary posted prices rule may depend on the other buyers’ valuations
unlike a posted prices rule.

5

Main result

In this section, we provide the main result of this paper.
First, we introduce the following standard domain richness condition.
Deﬁnition 3. A domain VN is rich if for each i ∈ N, there is v i ∈ R++ ∪ {∞} such thateither Vi = [0, v i ) or Vi = [0, v i ].
The following is the main result of this paper which states that on any rich domain, if
a rule satisﬁes shill-proofness, strategy-proofness, and non-imposition, then it is a binary
posted prices rule.
Theorem 1. Let VN be a rich domain. Let f be a rule on VN satisfying shill-proofness,strategy-proofness, and non-imposition. Then, it is a binary posted prices rule.
Theorem 1 states that under strategy-proofness and non-imposition, a rule satisﬁes
shill-proofness only if the payment of a buyer is either her posted price or zero. Thus, itshows that the cost of preventing the seller from shill bidding is equivalent to the rigidityof the payment of each buyer.
An impossibility result for the existence of a rule on a rich domain satisfying shillproofness, eﬃciency, strategy-proofness, and non-imposition follows from Theorem 1.
Corollary 1. Let VN be a rich domain. No rule on VN satisﬁes shill-proofness, eﬃciency,
strategy-proofness, and non-imposition.
In the following three examples, we show the independence of the properties in Theorem 1, i.e., we show that if we drop one of the three properties in Theorem 1, then there isa rule that satisﬁes the other properties and is diﬀerent from a binary posted prices rule.
In the following examples, let VN be an arbitrary rich domain.
Example 2 (Dropping shill-proofness). Let f be a rule on VN such that for eache = (N, vN ) ∈ E(VN ), the following hold.

12• If 1 ∈ N , then 9

f1 (e) =(1, maxi∈N \{1} vi ) if v1 ≥ maxi∈N \{1} vi ,(0, 0)otherwise.

• For each i ∈ N \{1}, fi (e) = (0, 0).
It is not a binary posted prices rule. It satisﬁes strategy-proofness and non-imposition, butviolates shill-proofness.
Example 3 (Dropping strategy-proofness). Let f be a rule on VN such that for eache = (N, vN ) ∈ E(VN ), (i) f (e) is eﬃcient for e, and (ii) for each i ∈ N ,tfi (e) =



 vi

if xfi (e) = 1,

0

if xfi (e) = 0.

It is not a binary posted prices rule. It satisﬁes shill-proofness and non-imposition, butviolates strategy-proofness.
Example 4 (Dropping non-imposition). Let f be a rule on VN such that for eache = (N, vN ) ∈ E(VN ) and each i ∈ N , fi (e) = (0, −1). It is not a binary posted prices rule.
It satisﬁes shill-proofness and strategy-proofness, but violates non-imposition.

6

Extensions

In this section, we discuss several extensions of the main result (Theorem 1).

6.1

Restricting shill bidding behavior

In this subsection, we study the consequence of restricting the seller’s shill bidding behavior.
Recall that in our deﬁnition of shill-proofness, we allow the seller to introduce an arbitrary number of false-name buyers. In practice, however, the seller may avoid introducing
many false-name buyers in fear of detection of such buyers. The next property weakens
shill-proofness so that the seller may introduce only a single false-name buyer.
9

If N = {1}, then let maxi∈N \{1} vi = 0.

13

Single shill-proofness. For each e = (N, vN ) ∈ E(VN ), there exist no i ∈ N\N andPPfvi ∈ Vi such that j∈N tfj (N ∪ {i}, vN ∪{i} ) >j∈N tj (e).

An interesting question is whether Theorem 1 is still valid even if we weaken shillproofness to single shill-proofness. The next example gives a negative answer to thisquestion, i.e., it shows that the binary posted prices rules are not the only rules satisfying
single shill-proofness, strategy-proofness, and non-imposition.
Example 5. Let VN be a rich domain. For simplicity, for each i ∈ N, let v i = 2. Let f bea rule on VN such that for each e = (N, vN ) ∈ E(VN ), the following hold.
• Suppose that N = {i} for some i ∈ {2, 3}. If vi ≥ 1, then fi (e) = (1, 1), and otherwise, fi (e) = (0, 0).
• Suppose that N = {i} for some i ∈ N\{2, 3}. Then, fi (e) = (0, 0).
• Suppose N = {1, i} for some i ∈ {2, 3}. Then, f1 (e) = (0, 0). If vi ≥ 1, thenfi (e) = (1, 1), and otherwise, fi (e) = (0, 0).
• Suppose N = {2, 3}. If v2 ≥ 1, then f2 (e) = (1, 1) and f3 (e) = (0, 0). If v2 < 1
and v3 ≥ 1, then f2 (e) = (0, 0) and f3 (e) = (1, 1). If v2 < 1 and v3 < 1, thenf2 (e) = f3 (e) = (0, 0).
• Suppose N = {1, 2, 3}. If v2 ≥ 1, v3 ≥ 1, and v2 + v3 < 3, thenf1 (e) =(1, 1 ) if v1 ≥ 1 ,22
(0, 0)if v1 < 12 ,and f2 (e) = f3 (e) = (0, 0). If v2 ≥ 1, v3 ≥ 1, and v2 + v3 ≥ 3, thenf1 (e) =(1, 1 ) if v1 ≥ 1 ,33
(0, 0)if v1 < 13 ,and f2 (e) = f3 (e) = (0, 0). If v2 < 1 or v3 < 1, then f1 (e) = f2 (e) = f3 (e) = (0, 0).
• In any other case, fi (e) = (0, 0) for each i ∈ N .
14

It is not a binary posted prices rule as the payment of buyer 1 can be 0, 13 , or 12 . It satisﬁes
single shill-proofness, strategy-proofness, and non-imposition. Note that it violates shillproofness.
In contrast with Theorem 1, the next proposition states that Corollary 1 remains valid
even if we weaken shill-proofness to single shill-proofness.
Proposition 1. Let VN be a rich domain. No rule on VN satisﬁes single shill-proofness,eﬃciency, strategy-proofness, and non-imposition.

6.2

Reserve priceIn practice, the seller often uses a reserve price in order to avoid a too low revenue. In thissubsection, we incorporate the seller’s reserve price into our model, and extend the main
result (Theorem 1) to a model with a reserve price.
First, we introduce a property that respects the seller’s reserve price r ∈ R+ . The
following property requires that a buyer receive the object only when her payment is nosmaller than a reserve price r.
Respecting reserve price r. Given r ∈ R+ , for each e = (N, vN ) ∈ E(VN ) and eachi ∈ N , if xfi (e) = 1, then tfi (e) ≥ r.

Second, we introduce a variant of a posted prices rule (not a binary posted prices rule)that takes a reserve price r into account. Given a reserve price r ∈ R+ , a rule f on VN is aposted prices rule with reserve price r if there is a proﬁle of posted prices (pfi )i∈N ∈ RN+
such that for each e = (N, vN ) ∈ E(VN ) and each i ∈ N , the following hold.
• If xfi (e) = 1, then tfi (e) = max{pfi , r} and vi ≥ tfi (e).
• If xfi (e) = 0, then tfi (e) = 0.
The following result extends Theorem 1 to a model with a reserve price r ∈ R++ .
Proposition 2. Let VN be a rich domain. Let r ∈ R++ . Let f be a rule on VN satisfying
shill-proofness, respecting reserve price r, strategy-proofness, and non-imposition. Then,
it is a posted prices rule with reserve price r.

15

Proposition 2 states that the resulting class of rules from shill-proofness, respecting
reserve price r ∈ R++ , strategy-proofness, and non-imposition is that of posted prices
rules with reserve price r, not that of binary posted prices rules with reserve prices r. This
contrasts with Theorem 1 which states that the resulting class of rules from shill-proofness,strategy-proofness, and non-imposition is that of binary posted prices rules.
In Proposition 2, we assume that a reserve price r is positive. If r = 0, then any binary
posted prices rule respects reserve price r. Thus, Theorem 1 does not change even if we
require a rule satisfy respecting reserve price r = 0, i.e., if a rule on a rich domain satisﬁes
shill-proofness, respecting reserve price r = 0, strategy-proofness, and non-imposition, thenit is a binary posted prices rules.

6.3

Bayesian incentive compatibility

In this subsection, we study how the main result (Theorem 1) changes when we weaken
strategy-proofness to Bayesian incentive compatibility.
First, we introduce Bayesian incentive compatibility. To do so, we need to introduce
the distribution of valuations. Given N ∈ N , the valuation proﬁle vN for N is distributed
according to a distribution function FN with a density function fN such that for eachvN ∈ VN , fN (vN ) > 0.
A distribution is said to be independent if for each i ∈ N, the valuation vi of buyer
i is distributed according to Fi with a density function fi , and for each N ∈ N and eachvN ∈ VN , FN (vN ) = ×i∈N Fi (vi ) and fN (vN ) = ×i∈N fi (vi ). Further, an independent distribution is said to be symmetric if for each pair i, j ∈ N, Vi = Vj and Fi = Fj .
Given a rule f on VN , N ∈ N , a buyer i ∈ N , and a pair vi , vi′ ∈ Vi , letihEvN \{i} ui (fi (N, (vi′ , vN \{i} )); vi ) vi
Z=ui (fi (N, (vi′ , vN \{i} )); vi )fN \{i} (vN \{i} |vi )dvN \{i}vN \{i} ∈VN \{i}denote the expected utility of buyer i when her valuation is vi and her report is vi′ , wherefN \{i} (·|vi ) is a conditional density function of vN \{i} given vi .
The next property requires that the truth-telling be a Bayesian Nash equilibrium in a
direct revelation game associated with a rule.

16

Bayesian incentive compatibility. For each N ∈ N , each i ∈ N , and each pair vi , vi′ ∈ Vi ,we havehi

EvN \{i} ui (fi (N, (vi , vN \{i} )); vi ) vi ≥ EvN \{i}hui (fi (N, (vi′ , vN \{i} )); vi ) vi

i.

Note that strategy-proofness implies Bayesian incentive compatibility, but the converse
is not necessarily true. Note also that in the deﬁnition of Bayesian incentive compatibility,
we allow a distribution to be dependent or independent but asymmetric.
The following example shows that if we weaken strategy-proofness to Bayesian incentive
compatibility, then Theorem 1 is no longer valid, i.e., it shows that a rule satisfying shillproofness, Bayesian incentive compatibility, and non-imposition is not necessarily a binary
posted prices rule.
Example 6. Let VN be a rich domain such that for each i ∈ N, Vi = [0, 1]. Supposethat the distribution is independent and symmetric, and for each i ∈ N, Fi is a uniform
distribution on Vi = [0, 1]. Let f be a rule on VN such that for each e = (N, vN ) ∈ E(VN ),the following hold.
• Suppose N = {1}. If v1 ≥ 12 , then f1 (e) = (1, 12 ), and otherwise, f1 (e) = (0, 0).
• Suppose N = {1, 2}. If v1 ≥ 12 and v2 ≥ 12 , then f1 (e) = (1, 41 ), and otherwise,
f1 (e) = (0, 0).
• Suppose 1 ∈ N and N ∈ N \{{1}, {1, 2}}. Then, f1 (e) = (0, 0).
• For each i ∈ N \{1}, fi (e) = (0, 0).
It is not a binary posted prices rule. It satisﬁes shill-proofness, Bayesian incentive compatibility, and non-imposition. Note that it violates strategy-proofness.
The next proposition states that even if we weaken strategy-proofness to Bayesian
incentive compatibility, an impossibility result in Proposition 1 remains true.
Proposition 3. Let VN be a rich domain. No rule on VN satisﬁes single shill-proofness,
Bayesian incentive compatibility, eﬃciency, and non-imposition.
Since shill-proofness implies single shill-proofness, we obtain the following.

17

Corollary 2. Let VN be a rich domain. No rule on VN satisﬁes shill-proofness, Bayesian
incentive compatibility, eﬃciency, and non-imposition.
Note that in Proposition 3 and Corollary 2, we do not require that a distribution
be independent or symmetric. Thus, they hold not only for independent and symmetric
distributions but also for dependent or asymmetric distributions.
Almost all standard rules (e.g., a ﬁrst-price rule, a third price rule, and an all-payrule) satisfy Bayesian incentive compatibility, eﬃciency, and non-imposition in a single
object setting. Thus, Proposition 3 and Corollary 2 imply that such rules violate single
shill-proofness and shill-proofness.
Since Bayesian incentive compatibility is weaker than strategy-proofness (i.e., the latter implies the former), Proposition 1 follows from Proposition 3. Thus, we only prove
Proposition 3, and do not give the proof of Proposition 1.
.

6.4

Characterization

Theorem 1 states that only the binary posted prices rules satisfy shill-proofness, strategyproofness, and non-imposition. In this subsection, we study whether the converse of Theorem 1 (i.e., all the binary posted prices rules satisfy the three properties) is also true.
First, the next proposition states that all the binary posted prices rules satisfy individual
rationality and no subsidy, and so by Remark 2, they do non-imposition as well. We omit
a straightforward proof.
Proposition 4. Let VN be a domain. Any binary posted prices rule on VN satisﬁes individual rationality, no subsidy, and non-imposition.
The next two examples show that some binary posted prices rules violate shill-proofness
and strategy-proofness. Thus, the converse of Theorem 1 is not necessarily true.
Example 7 (Binary posted prices rule violates shill-proofness). Let VN be a richdomain. For simplicity, let v i = 2 for each i ∈ N. Let f be a binary posted prices rule on
VN associated with a proﬁle of posted prices (pfi )i∈N such that pfi = 1 for each i ∈ N, andfor each e = (N, vN ) ∈ E(VN ), the following hold.
• If |N | = 1, then for i ∈ N , fi (e) = (0, 0).
18

• If |N | ≥ 2, then f (e) is equivalent to the outcome of a priority rule for e associatedwith a priority ≻f over N such that 1 ≻f 2.
We show that f violates shill-proofness. By richness, we can choose v{1,2} ∈ V{1,2} suchthat v1 > 1 and v2 > 1. Let e = ({1}, v1 ) ∈ E(VN ). Then, f1 (e) = (0, 0). By 1 ≻f 2 andv1 > 1 = pf1 , f1 ({1, 2}, v{1,2} ) = (1, 1), and so tf1 ({1, 2}, v{1,2} ) = 1. Thus, tf1 ({1, 2}, v{1,2} ) =1 > 0 = tf1 (e), and f violates shill-proofness.
Example 8 (Binary posted prices rule violates strategy-proofness). Let VN be arich domain. For simplicity, let v i = 3 for each i ∈ N. Let f be a binary posted prices ruleon VN associated with a proﬁle of posted prices (pfi )i∈N such that pfi = 1 for each i ∈ N,
and for each e = (N, vN ) ∈ E(VN ), the following hold.
• If 1 ∈ N , thenf1 (e) =(1, 1) if v1 ≥ 2,(0, 0) otherwise.

• For each i ∈ N \{1}, fi (e) = (0, 0).
We show that f violates strategy-proofness. By richness, we can choose v1 ∈ V1 suchthat v1 = 1.5. Let e = ({1}, v1 ) ∈ E(VN ). Then, f1 (e) = (0, 0). Again, by richness, we canchoose v1′ ∈ V1 such that v1′ = 2. Then, f1 ({1}, v1′ ) = (1, 1). By v1 = 1.5 > 1, we haveu1 (f1 ({1}, v1′ ); v1 ) > u1 (f1 (e); v1 ). Thus, f violates strategy-proofness.
Given the above examples, in the remaining part of this subsection, we identify acondition under which a binary posted prices rule satisﬁes shill-proofness and strategyproofness.
The next proposition gives a necessary and suﬃcient condition for a binary posted
prices rule to satisfy shill-proofness and strategy-proofness. Note that it holds on any
domain that is not necessarily rich. We omit a straightforward proof.
Proposition 5. Let VN be a domain. A binary posted prices rule on VN satisﬁes shillproofness and strategy-proofness if and only if for each e = (N, vN ) ∈ E(VN ), the following
hold.
• For each N ′ ∈ N with N ∩ N ′ = ∅ and each vN ′ ∈ VN ′ , we haveX f
X fti (N ∪ N ′ , vN ∪N ′ ) ≤ti (e).
i∈N

i∈N

19

• If xfi (e) = 1, then for each vi′ ∈ Vi with vi′ > tfi (e), xfi (N, (vi′ , vN \{i} )) = 1.
• If xfi (e) = 1, then for each vi′ ∈ Vi with xfi (N, (vi′ , vN \{i} )) = 1, tfi (e) = tfi (N, (vi′ , vN \{i} )).
Note that the ﬁrst condition in Proposition 5 is a restatement of the deﬁnition of shillproofness. In fact, the class of binary posted prices rule leaves room for the choice ofposted prices (pfi )i∈N and ﬂexibility in deﬁning an object allocation rule, which makes it
diﬃcult to identify a closed-form necessary and suﬃcient condition for a binary posted
prices rule to satisfy shill-proofness. The second and the third conditions are concernedwith strategy-proofness of a binary posted prices rule. The second one prevents proﬁtable
manipulation of a rule such that a buyer who receives no object gets better oﬀ by receiving
the object as a result of a false report of a valuation. Note that the rule in Example 8
violates strategy-proofness because of this type of manipulation. The third one prevents
proﬁtable manipulation such that a buyer can lower her posted price without changing her
consumption of the object.
Theorem 1 and Propositions 4 and 5 together enable us to obtain a characterization of
the class of rules satisfying shill-proofness, strategy-proofness, and non-imposition.
Proposition 6. Let VN be a rich domain. A rule on VN satisﬁes shill-proofnes, strategyproofnes, and non-imposition if and only if it is a binary posted prices rule such that foreach e = (N, vN ) ∈ E(VN ), the following hold.
• For each N ′ ∈ N with N ∩ N ′ = ∅ and each vN ′ ∈ VN ′ , we haveX f
X fti (N ∪ N ′ , vN ∪N ′ ) ≤ti (e).
i∈Ni∈N• If xfi (e) = 1, then for each vi′ ∈ Vi with vi′ > tfi (e), xfi (N, (vi′ , vN \{i} )) = 1.
• If xfi (e) = 1, then for each vi′ ∈ Vi with xfi (N, (vi′ , vN \{i} )) = 1, tfi (e) = tfi (N, (vi′ , vN \{i} )).
Recall that in Example 1 in Section 4, we introduce several examples of binary posted
prices rules. It is straightforward to show that these binary posted prices rules satisfy
the conditions in Proposition 6. Thus, Proposition 6 implies that these rules satisfy shillproofness, strategy-proofness, and non-imposition.

20

6.5

Non-quasi-linear utility functions with interdependent valuations

In this subsection, we show that the main result (Theorem 1) extends to a setting of
non-quasi-linear utility functions with interdependent valuations.
We brieﬂy introduce a model of non-quasi-linear utility functions with interdependentvaluations. Each buyer i ∈ N has a type θi ∈ Rk+i , where 1 ≤ ki < ∞. Our generic notation
for a class of types of a buyer i ∈ N is Θi ⊆ Rk+i . A type of a buyer is private information
only known for her.
Given N ∈ N , let ΘN = ×i∈N Θi . Let ΘN = ×i∈N Θi . We call ΘN a domain.
Given i ∈ N, let Ni = {N ∈ N : i ∈ N } denote the family of sets of buyers that include
buyer i. Each buyer i ∈ N has a utility function ui : M × R × ∪N ∈Ni ΘN → R ∪ {−∞}
such that for some budget bi : ∪N ∈Ni ΘN → R+ ∪ {∞}, we have that for each zi =(xi , ti ) ∈ M × R, each N ∈ Ni , and each θN ∈ ΘN , if ti ≤ bi (θN ), then ui (zi , θN ) > − ∞,and if ti > bi (θN ), then ui (zi , θN ) = −∞. Note that we allow a utility function of a buyer (i)to exhibit income eﬀects, (ii) to face hard budget constraints, and (iii) to depend on otherbuyers’ types. For each N ∈ Ni and each θN ∈ ΘN , we normalize that ui ((0, 0), θN ) = 0.
We assume that a utility function of a buyer i ∈ N satisﬁes the following properties.
Weak desirability of the object. For each N ∈ Ni , each θN ∈ ΘN , and each ti ∈ Rwith ti ≤ bi (θN ), we have ui ((1, ti ), θN ) ≥ ui ((0, ti ), θN ).
Money monotonicity. For each N ∈ Ni , each θN ∈ ΘN , each xi ∈ M , and each pairti , t′i ∈ R with ti < t′i ≤ bi (θN ), we have ui ((xi , ti ), θN ) > ui ((xi , t′i ), θN ).
Finiteness. For each N ∈ Ni , each θN ∈ ΘN , and each ti ∈ R with ui ((0, ti ), θN ) ≥ ui ((1, bi (θN )), θN ),there is wi (ti , θN ) ∈ R such that ui ((1, wi (ti , θN )), θN ) = ui ((0, ti ), θN ).
Given i ∈ N, N ∈ Ni , and θN ∈ ΘN such that ui ((0, 0), θN ) ≥ ui ((1, bi (θN )), θN ), wecall wi (θN ) ∈ R with ui ((1, wi (θN )), θN ) = ui ((0, 0), θN ) the valuation for θN . Note thatsuch wi (θN ) exists by ﬁniteness. For notational convenience, if ui ((1, bi (θN )), θN ) > ui ((0, 0), θN ),then let wi (θN ) = ∞.
Given i ∈ N, N ∈ Ni , and θN ∈ ΘN , the truncated valuation for θN is vi (θN ) =21

min{wi (θN ), bi (θN )}. Note that vi (θN ) ∈ R+ . A truncated valuation vi (θN ) plays the samerole as a valuation vi in a model of quasi-linear utility functions with private valuations
that we have studied so far.
Given a domain ΘN , an economy on ΘN is a pair e = (N, θN ) such that N ∈ N andθN ∈ ΘN . Let E(ΘN ) denote the class of economies on ΘN .
An object allocation and an allocation for N ∈ N are deﬁned in the same way as before.
The seller’s utility function u0 is also deﬁned in the same way as before.
Given a domain ΘN , an (allocation) rule on ΘN is a mapping f : E(ΘN ) → ∪N ∈N ZN
such that for each e = (N, θN ) ∈ E(ΘN ), f (e) ∈ ZN .
We introduce the properties of rules. All the properties that we have introduced so
far except for strategy-proofness are deﬁned in the same way as before. The following
property is a counterpart of strategy-proofness for a model with interdependent valuations.
It requires that the truth-telling be an ex-post Nash equilibrium in a direct revelation gameassociated with a rule.
Ex-post incentive compatibility. For each e = (N, θN ) ∈ E(ΘN ), each i ∈ N , and eachθi′ ∈ Θi , we have ui (fi (e); θN ) ≥ ui (fi (N, (θi′ , θN \{i} )); θN ).

Note that in a model with private valuations, ex-post incentive compatibility is equivalent to strategy-proofness.
A posted prices rule and a binary posted prices rule are deﬁned by means of a truncatedvaluation vi (θ) instead of a valuation vi in a model of quasi-linear utility functions withprivate valuations.
Given a buyer i ∈ N, N ∈ Ni , and θN \{i} , let Vi (θN \{i} ) = {vi (θi , θN \{i} ) : θi ∈ Θi } denote the set of truncated valuations for (θi , θN \{i} ) given θN \{i} . Note that Vi (θN \{i} ) ⊆ R+ .
We introduce a counterpart of a rich domain for a model of non-quasi-linear utility
functions with interdependent valuations. A domain Θ N is rich if for each i ∈ N and eachθN \{i} ∈ ΘN \{i} , there is v i (θN \{i} ) ∈ R++ such that either Vi (θN \{i} ) = [0, v i (θN \{i} )) orVi (θN \{i} ) = [0, v i (θN \{i} )]. Note that the upper bound v i (θN \{i} ) of Vi (θN \{i} ) may dependon other buyers’ types θN \{i} .
The following classes of utility functions are examples of those with rich domains. Notethat almost all classes of utility functions of interest can be expressed as rich domains.

22• A utility function ui of a buyer i ∈ N is quasi-linear with private valuations(Vickrey, 1961) if for each N ∈ Ni and each θN ∈ ΘN , (i) bi (θN ) = ∞, (ii) vi (θN ) =vi (θi ), and (iii) for each zi = (xi , ti ) ∈ M × R, we have ui (zi , θN ) = vi (θi )xi − ti .
Note that this corresponds to a utility function that we have studied so far.
• A utility function ui of a buyer i ∈ N is quasi-linear with common valuations(Wilson, 1969) if there is a probability distribution G over [v, v] × ΘN with a density function g such that for each θN ∈ ΘN , (i) bi (θN ) = ∞, (ii) vi (θN ) = vi (θi ) =R
E(ṽ,θ̃N \{i} ) [ṽ|θi ] = (ṽ,θ̃N \{i} ) ṽgN (ṽ, θ̃N |θ̃i = θi )d(ṽ, θ̃N \{i} ), where gN (·|θi ) is a conditional density function of (v, θN ) given θi , and (iii) for each zi = (xi , ti ) ∈ M × R,
we have ui (zi , θN ) = vi (θi )xi − ti . Note that whether a domain is rich for quasi-linear
utility functions with common valuations depends on a distribution G.10
• A utility function ui of a buyer i ∈ N is quasi-linear with interdependent valuations (Milgrom and Weber, 1982) if for each N ∈ Ni and each θN ∈ ΘN , (i) bi (θN ) =∞, and (iii) for each zi = (xi , ti ) ∈ M × R, we have ui (zi , θN ) = vi (θN )xi − ti .
• A utility function ui of a buyer i ∈ N is quasi-linear with soft budgets (Saitoh
and Serizawa, 2008) if for each N ∈ Ni and each θN ∈ ΘN , (i) bi (θN ) = ∞, and (ii)there are an income Ii (θN ) ∈ R+ ∪ {∞}, an interest rate r ∈ R+ , and ṽi (θN ) ∈ R+
such that for each zi = (xi , ti ) ∈ M × R, we haveui ((zi , ti ), θN ) =ṽi (θN )xi − ti

if ti ≤ Ii (θN ),ṽi (θN )xi − Ii (θN ) − (1 + r)(ti − Ii (θN )) if ti > Ii (θN ).

Note that ṽi (θN ) is in general diﬀerent from vi (θN ).11
• A utility function ui of a buyer i ∈ N is quasi-linear with public soft budgets
if for each N ∈ Ni and each θN ∈ ΘN , (i) bi (θN ) = ∞, and (ii) there are an income
Ii ∈ R+ ∪ {∞}, an interest rate r ∈ R+ , and ṽi (θN ) ∈ R+ such that for each zi =For example, suppose that v = 0 and v = 1, and Θi = [0, 1] for each i ∈ N. If G is a uniform
distribution (i.e., for each N ∈ N and each (v, θN ) ∈ [0, 1]|N |+1 , gN (v, θN ) = 1), then a domain is notrich. In contrast, if G has a density function g such that for each N ∈ N and each (v, θN ) ∈ [0, 1]|N |+1 ,g(v, θN ) = v × (×i∈N θi ), then a domain is rich.
i (θN )
11
Indeed, if ṽi (θN ) ≤ Ii (θN ), then vi (θN ) = ṽi (θN ), and otherwise, vi (θN ) = ṽi (θN )+rI
.
1+r
10

23

(xi , ti ) ∈ M × R we have,ui ((zi , ti ), θN ) =ṽi (θN )xi − ti

if ti ≤ Ii ,ṽi (θN )xi − Ii − (1 + r)(ti − Ii ) if ti > Ii .

• A utility function ui of a buyer i ∈ N is quasi-linear with hard budegets (Dobzinski et al., 2012; Hafalir et al., 2012, etc.) if for each N ∈ Ni , each θN ∈ ΘN , andeach zi = (xi , ti ) ∈ M × R, we haveui (zi , θN ) =vi (θN )xi − ti

if ti ≤ bi (θN ),−∞

if ti > bi (θN ),• A utility function ui of a buyer i ∈ N is quasi-linear with public hard budegets(Dobzinski et al., 2012, Lavi and May, 2012, etc.) if (i) there is bi ∈ R+ ∪ {∞} suchthat for each N ∈ Ni and each θN ∈ ΘN , bi (θN ) = bi , and (ii) for each N ∈ Ni , eachθN ∈ ΘN , and each zi = (xi , ti ) ∈ M × R, we haveui (zi , θN ) =vi (θN )xi − ti

if ti ≤ bi ,−∞

if ti > bi ,• A utility function ui of a buyer i ∈ N exhibits income eﬀects with private valuations (Saitoh and Serizawa, 2008; Sakai, 2008, etc.) if for each N ∈ Ni and eachθN ∈ ΘN , vi (θN ) = vi (θi ).
• A utility function ui of a buyer i ∈ N exhibits positive income eﬀects (Baisa,
2020, Malik and Mishra, 2021, etc.) if for each N ∈ Ni , each θN ∈ ΘN , and each pairti , t′i ∈ R such that ti < t′i and ui ((0, t′i ), θN ) ≥ ui ((1, bi (θN )), θN ), we have wi (ti , θN )−ti > wi (t′i , θN ) − t′i .
• A utility function ui of a buyer i ∈ N exhibits negative income eﬀects (Shinozaki
et al., 2022) if for each N ∈ Ni , each θN ∈ ΘN , and each pair ti , t′i ∈ R such thatti < t′i and ui ((0, t′i ), θN ) ≥ ui ((1, bi (θN )), θN ), we have wi (ti , θN )−ti < wi (t′i , θN )−t′i .
Now, we are ready to introduce the result in a model of non-quasi-linear utility functions
with interdependent valuations. The next proposition states that Theorem 1 carries over24

to a model of non-quasi-linear utility functions with interdependent valuations. Since its
proof is essentially same as that of Theorem 1, we omit it.
Proposition 7. Let ΘN be a rich domain. Let f be a rule on ΘN satisfying shill-proofness,
ex-post incentive compatibility, and non-imposition. Then, it is a binary ﬁxed prices rule.
Recall that we introduced several examples of the classes of utility functions with richdomains. Proposition 7 holds for the classes of utility functions such as quasi-linear utility
functions with independent, common, or interdependent valuations and non-quasi-linear
utility functions with independent or interdependent valuations.

7

Conclusion

In this paper, we have studied the class of rules that prevent the seller from raising her
revenue from introducing false-name buyers (i.e., shill bidding) in the object allocation
problem with money. The main result of this paper (Theorem 1) shows that only thebinary posted prices rules satisfy shill-proofness, strategy-proofness, and non-imposition.
Thus, if the planner would like to prevent the seller from shill bidding, then she must
accept the rigidity of the payment of each buyer.
Finally, we discuss a possible direction of future research given our main result. Our
result highlights the diﬃculty in preventing the seller’s shill bidding, and so suggests theimportance of technology that detects the seller’s shill bidding. To study how the seller does
shill bidding under several rules of importance will help the researchers develop eﬀective
detection technology of shill bidding. In our companion paper (Shinozaki, 2024a), we study
how the seller optimally does shill bidding under a Vickrey rule and a pay as bid rule withprivate valuations. To further study the seller’s shill bidding behavior under various rules
and modeling assumptions will be an important topic of future research.

AppendixA

Proof of Theorem 1

In this section, we prove Theorem 1. The proof is in a series of lemmata.
25

The following lemma shows that the combination of strategy-proofness and non-imposition
implies the combination of individual rationality and no subsidy.12
Lemma 1. Let VN be a rich domain. Let f be a rule on V satisfying strategy-proofness
and non-imposition. Then, it satisﬁes individual rationality and no subsidy.
Proof. First, we show that f satisﬁes individual rationality. Let e = (N, vN ) ∈ E(VN ) andi ∈ N . By contradiction, suppose 0 > ui (fi (e); vi ). By richness, we can choose vi′ ∈ Vsuch that vi′ = 0. By non-imposition, ui (fi (N, (vi′ , vN \{i} )); vi′ ) = 0. Thus, by vi′ = 0,
fi (N, (vi′ , vN \{i} )) ∈ {(1, 0), (0, 0)}. Thus,ui (fi (N, (vi′ , vN \{i} )); vi ) ≥ 0 > ui (fi (e); vi ),where the ﬁrst inequality follows from vi ≥ 0. However, this contradicts strategy-proofness.
Second, we show that f satisﬁes no subsidy. Let e = (N, vN ) ∈ E(VN ) and i ∈ N . By
contradiction, suppose tfi (e) < 0. By richness, there is vi′ ∈ V such that vi′ = 0. Then, by
non-imposition, ui (fi (N, (vi′ , vN \{i} )); vi′ ) = 0. By tfi (e) < 0 and vi′ = 0, we haveui (fi (e); vi′ ) > 0 = ui (fi (N, (vi′ , vN \{i} )); vi′ ),which contradicts strategy-proofness.
The following lemma shows that under a rule satisfying strategy-proofness and nonimposition, if a buyer does not receive the object, then she makes no payment.
Lemma 2. Let VN be a rich domain. Let f be a rule on VN satisfying strategy-proofness
and non-imposition. Let e = (N, vN ) ∈ E(VN ) and i ∈ N . If xfi (e) = 0, then tfi (e) = 0.
Proof. Suppose xfi (e) = 0. By Lemma 1, f satisﬁes no subsidy. Thus, tfi (e) ≥ 0. Also, byLemma 1, f satisﬁes individual rationality. Thus, ui (fi (e)) ≥ 0. By xfi (e) = 0, tfi (e) ≤ 0.
Thus, tfi (e) = 0.
The following lemma shows that under a rule satisfying strategy-proofness and nonimposition, if a buyer receives the object, then her valuation is no smaller than her payment.
12

Klaus and Nichifor (2020) show in a model with non-negative payments that the combination ofstrategy-proofness and non-imposition implies individual rationality (see their Lemma 1). Note that theya priori assume that the model includes only non-negative payments. We generalize their lemma byshowing that the combination also implies no subsidy in a model where the payments are not necessarily
non-negative.

26

Lemma 3. Let VN be a rich domain. Let f be a rule on VN satisfying strategy-proofness
and non-imposition. Let e = (N, vN ) ∈ E(VN ) and i ∈ N . If xfi (e) = 1, then vi ≥ tfi (e).
Proof. Suppose by contradiction that xfi (e) = 1, but vi < tfi (e). Then, 0 > ui (fi (e); vi ).
By Lemma 1, f satisﬁes individual rationality. Thus, ui (fi (e); vi ) ≥ 0, a contradiction.
The following lemma states that under a rule satisfying strategy-proofness and nonimposition, if a buyer receives the object in an economy that includes only her, then her
payment is independent of her own valuation.
Lemma 4. Let VN be a rich domain. Let f be a rule on VN satisfying strategy-proofness
and non-imposition. Let i ∈ N. For each pair vi , vi′ ∈ Vi with xfi ({i}, vi ) = xfi ({i}, vi′ ) = 1,
we have tfi ({i}, vi ) = tfi ({i}, vi′ ).
Proof. By contradiction, suppose that there is a pair vi , vi′ ∈ Vi such that xfi ({i}, vi ) =xfi ({i}, vi′ ) = 1, but tfi ({i}, vi ) ̸= tfi ({i}, vi′ ). Without loss of generality, let tfi ({i}, vi′ ) < tfi ({i}, vi ).
Then, by xfi ({i}, vi ) = xfi ({i}, vi′ ) = 1,
ui (fi ({i}, vi′ ); vi ) > ui (fi ({i}, vi ); vi ),which contradicts strategy-proofness.
In the remaining part of this section, let VN be a rich domain, and f a rule on VN
satisfying shill-proofness, individual rationality, and non-imposition.
For each i ∈ N, let pfi ∈ R be such that if there is vi ∈ Vi such that xfi ({i}, vi ) = 1,
then pfi = tfi ({i}, vi ), and otherwise, pfi = 0. By Lemma 4, pfi is well-deﬁned. By Lemma 1,
f satisﬁes no subsidy, so that pfi ∈ R+ .
The following lemma states that if a buyer receives the object and her payment is
positive, then she also receives the object in an economy that only includes her.
Lemma 5. Let e = (N, vN ) ∈ E(VN ) and i ∈ N . If xfi (e) = 1 and tfi (e) > 0, thenxfi ({i}, vi ) = 1.
Proof. Suppose by contradiction that xfi (e) = 1 and tfi (e) > 0, but xfi ({i}, vi ) = 0. Then,by Lemma 2, tfi ({i}, vi ) = 0. Then, {i} ⊊ N , andtfi (e) > 0 = tfi ({i}, vi ),27

which contradicts shill-proofness.
The following lemma states that if a buyer receives the object and her payment is
positive, then her payment in an economy that only includes her is greater than zero andno greater than her maximal possible valuation.
Lemma 6. Let e = (N, vN ) ∈ E(VN ) and i ∈ N . If xfi (e) = 1 and tfi (e) > 0, then0 < pfi ≤ v i .
Proof. Suppose xfi (e) = 1 and tfi (e) > 0. By Lemma 5, xfi ({i}, vi ) = 1. Thus, by Lemma 4,
tfi ({i}, vi ) = pfi . By Lemma 1, f satisﬁes individual rationality. Thus, pfi ≤ vi . By
vi ∈ Vi ⊆ [0, v i ], vi ≤ v i . Thus, pfi ≤ v i . Further, if pfi = 0, then {i} ⊊ N , andtfi (e) > 0 = pfi = tfi ({i}, vi ),which contradicts shill-proofness. Thus, we have pfi > 0.
The following lemma states that if a buyer receives the object and her payment is
positive in an economy, then her payment is equivalent to her payment in an economy that
only includes her.
Lemma 7. Let e = (N, vN ) ∈ E(VN ) and i ∈ N . If xfi (e) = 1 and tfi (e) > 0, then tfi (e) =pfi .
Proof. Suppose by contradiction that xfi (e) = 1 and tfi (e) > 0, but tfi (e) ̸= pfi . By thedeﬁnition of pfi , {i} ⊊ N .
First, suppose tfi (e) < pfi . By Lemma 6, 0 < pfi ≤ v i . Thus, by richness, we can choosevi′ ∈ Vi such that tfi (e) < vi′ < pfi . Then, by xfi (e) = 1, strategy-proofness, and Lemma 2,
fi (N, (vi′ , vN \{i} )) = fi (e). By individual rationality (which follows from Lemma 1) andLemma 4, xfi ({i}, vi′ ) = 0. Thus, by Lemma 2, tfi ({i}, vi′ ) = 0. By tfi (e) > 0, we havetfi (N, (vi′ , vN \{i} )) = tfi (e) > 0 = tfi ({i}, vi′ ),which contradicts shill-proofness.
Second, suppose tfi (e) > pfi . By pfi ≥ 0, tfi (e) > 0. By xfi (e) = 1 and tfi (e) > 0,
Lemma 5 implies xfi ({i}, vi ) = 1. Thus, by Lemma 4, tfi ({i}, vi ) = pfi . By tfi (e) > pfi ,28

we havetfi (e) > pfi = tfi ({i}, vi ),which contradicts shill-proofness.
Now, we are in a position to complete the proof of Theorem 1. Let e = (N, vN ) ∈ E(VN )and i ∈ N . If xfi (e) = 1, then by Lemma 7, either tfi (e) = pfi or tfi (e) = 0, and by Lemma 3,
vi ≥ tfi (e). If xfi (e) = 0, then by Lemma 2, tfi (e) = 0. Thus, f is a binary posted prices
■

rule.

B

Proof of Proposition 2

In this section, we prove Proposition 2. Let r ∈ R++ . Let f be a rule satisfying shillproofness, respecting reserve price r, strategy-proofness, and non-imposition. Then, by
Theorem 1, it is a binary posted prices rule. Let (pfi )i∈N be a proﬁle of posted prices
associated with f . Let e = (N, vN ) ∈ E(VN ) and i ∈ N be such that xfi (e) = 1. Then,tfi (e) ∈ {pfi , 0}. Since f respects reserve price r, tfi (e) ≥ r > 0. Thus, tfi (e) = pfi . By
tfi (e) ≥ r, pfi ≥ r. Thus, tfi (e) = pfi = max{pfi , r}. Thus, f is a posted prices rule with■reserve price r.

C

Proof of Proposition 3

In this section, we prove Proposition 3. We begin with the four lemmata concerning theproperties of Bayesian incentive compatible rules.
The following lemma is an analogue of Lemma 1 for a rule satisfying Bayesian incentive
compatibility and non-imposition in an economy that consists of only a single buyer.
Lemma 8. Let VN be a rich domain. Let f be a rule on VN satisfying Bayesian incentive
compatibility and non-imposition. Let i ∈ N and vi ∈ Vi . We have (i) ui (fi ({i}, vi ); vi ) ≥ 0
and (ii) tfi ({i}, vi ) ≥ 0.
Proof. Note that in an economy with a single buyer, Bayesian incentive compatibility isequivalent to strategy-proofness : both require that for each e = ({i}, vi ) ∈ E and eachvi′ ∈ Vi , ui (fi (e); vi ) ≥ ui (fi ({i}, vi′ ); vi ). Thus, by the same proof as in Lemma 1, we havethat for each i ∈ N and each vi ∈ Vi , ui (fi ({i}, vi ); vi ) ≥ 0 and tfi ({i}, vi ) ≥ 0.
29

The next lemma is an analogue of Lemma 2 for a rule satisfying Bayesian incentive
compatibility and non-imposition in an economy that consists of only a single buyer. Since
its proof is same as that of Lemma 2 given Lemma 8, we omit it.
Lemma 9. Let VN be a rich domain. Let f be a rule on VN satisfying Bayesian incentive compatibility and non-imposition. Let i ∈ N and vi ∈ Vi . If xfi ({i}, vi ) = 0, thentfi ({i}, vi ) = 0.
The next lemma states that under a rule satisfying Bayesian incentive compatibility,
eﬃciency, and non-imposition, if a buyer receives the object in an economy that includes
only her, then her payment is equal to zero.
Lemma 10. Let VN be a rich domain. Let f be a rule on VN satisfying Bayesian incentive
compatibility, eﬃciency, and non-imposition. Let i ∈ N and vi ∈ Vi . If xfi ({i}, vi ) = 1,
then tfi ({i}, vi ) = 0.
Proof. By contradiction, suppose xfi ({i}, vi ) = 1, but tfi ({i}, vi ) > 0. Then, by richness, we
can choose vi′ ∈ Vi such that 0 < vi′ < tfi ({i}, vi ). We show that xfi ({i}, vi′ ) = 0. Suppose bycontradiction that xfi ({i}, vi′ ) = 1. Then, by Lemma 8, tfi ({i}; vi′ ) ≤ vi′ . By vi′ < tfi ({i}, vi ),tfi ({i}, vi′ ) < tfi ({i}, vi ). By xfi ({i}, vi′ ) = xfi ({i}, vi ) = 1, we haveui (fi ({i}; vi′ ); vi ) > ui (fi ({i}, vi ); vi ),which contradicts Bayesian incentive compatibility. Thus, xfi ({i}, vi′ ) = 0. However, byvi′ > 0, eﬃciency implies that xfi ({i}, vi′ ) = 1, which contradicts xfi ({i}, vi′ ) = 0.
The following lemma states that under a rule satisfying single shill-proofness, Bayesian
incentive compatibility, eﬃciency, and non-imposition, the revenue of the seller is always
non-positive.
Lemma 11. Let VN be a rich domain. Let f be a rule on VN satisfying single shillproofness Bayesian incentive compatibility, eﬃciency, and non-imposition. For each e =P(N, vN ) ∈ E(VN ) and each i ∈ N , i∈N tfi (e) ≤ 0.
Proof. We do the proof by induction on the number of buyers in an economy.
Induction base. For each e = (N, vN ) ∈ E(VN ) with |N | = 1 and i ∈ N , by Lemmata 930and 10, tfi (e) = 0.
Induction hypothesis. Suppose that for each e = (N, vN ) ∈ E(VN ) with |N | = n ≥ 1,P
fi∈N ti (e) ≤ 0.
Induction step. Let e = (N, vN ) ∈ E(VN ) be such that |N | = n + 1, where n ≥ 1. For
each i ∈ N , by single shill-proofness and the induction hypothesis, we haveX

tfj (e) ≤j∈N \{i}X

tfj (N \{i}, vN \{i} ) ≤ 0.

j∈N \{i}Summing up these inequalities over all the buyers in N , we have(|N | − 1)

X f
X X f
ti (e) =tj (e) ≤ 0.
i∈N j∈N \{i}i∈N

By |N | ≥ 2, we get

X fti (e) ≤ 0,i∈N

as desired.
Now, we invoke the following two facts.
First, the following is a version of the revenue equivalence theorem by Myerson (1981).
Fact 1 (Myerson, 1981). Let VN be a rich domain. Let f, g be a rule on VN satisfying
Bayesian incentive compatibility, eﬃciency, and non-imposition. For each N ∈ N ,
E vN

hX

tfi (N, vN )i

= E vNi∈NhXtgi (N, vN )

i
.

i∈N

Given an economy e = (N, vN ) ∈ E(VN ), let v k (e) denote the k-th highest valuation
among vN . For notational convenience, let v k (e) = 0 if k > |N |. A rule f on VN is a
Vickrey rule (Vickrey, 1961) if for each e = (N, vN ) ∈ E(VN ), (i) f (e) is eﬃcient for e,and (ii) for each i ∈ N , tfi (e) = xfi (e)v m+1 (e). Note that for each e = (N, vN ) ∈ E(VN ),the revenue of the seller for e under a Vickrey rule f on E(VN ) isX fti (e) = mv m+1 (e).
i∈N31

Second, the following fact states that a Vickrey rule satisﬁes Bayesian incentive compatibility, eﬃciency, and non-imposition.13
Fact 2 (Vickrey, 1961). Let VN be a domain. A Vickrey rule on VN satisﬁes Bayesian
incentive compatibility, eﬃciency, and non-imposition.
We complete the proof of Proposition 3. Suppose by contradiction that there is a rule
f on a rich domain VN satisfying single shill-proofness, Bayesian incentive compatibility,
eﬃciency, and non-imposition. Let N ∈ N be such that |N | > m. Let g be a Vickrey
rule on VN . By our assumption, f satisﬁes Bayesian incentive compatibility, eﬃciency, andnon-imposition, and by Fact 2, g does so as well. Thus, by Fact 1, we have
E vN

hX

i
i
hX
tfi (N, vN ) = EvN
tgi (N, vN ) = mEvN [v m+1 (N, vN )] > 0,

i∈N

(1)

i∈N

where the inequality follows from |N | > m. In contrast, Lemma 11 implies that
E vN

hX

i
tfi (N, vN ) ≤ 0,i∈N■which contradicts (1).

References[1] Akbarpour, M. and S. Li (2020), “Credible auctions: A trilemma.” Econometrica,
88(2): 425–467.
[2] Baisa, B. (2020), “Eﬃcient multi-unit auctions for normal goods.” Theoretical Economics, 15(1): 361–413.
[3] Carlson, J. I. and T. Wu (2022), “Shill bidding and information in eBay auctions.”
Journal of Economic Behavior and Organization, 202: 341–360.
[4] Chakraborty, I. and G. Kosmopoulou (2004), “Auctions with shill bidding.” Economic
Theory, 24(2): 271–287.

13

A Vickrey rule further satisﬁes strategy-proofness, individual rationality, and no subsidy (Vickrey,1961).

32

[5] Dobzinski, S., R. Lavi, and N. Nisan (2012), “Multi-unit auctions with budget limits.”
Games and Economic Behavior , 74(2): 486–503.
[6] Engelberg, J. and J. Williams (2009), “eBay’s proxy bidding: A license to shill.”
Journal of Economic Behavior and Organization, 72(1): 509–526.
[7] Graham, D. A., R. C. Marshall, and J. F. Richard (1990), “Phantom bidding against
heterogeneous bidders.” Economics Letters, 32(1): 13–17.
[8] Hafalir, I. E., R. Ravi, and A. Sayedi (2012), “A near Pareto optimal auction withbudget constraints.” Games and Economic Behavior , 74(2): 699–708.
[9] Kawasaki, M., R. Sakai, and T. Kazumura (2023), “Serial dictatorship rules in multiunit object assignment problems with money.” Kyoto University, Graduate School of
Economics Discussion Paper Series No. E-23-007..
[10] Kelso, A. S. and V. P. Crawford (1982), “Job matching, coalition formation, and grosssubstitutes.” Econometrica, 50(6): 1483–1504.
[11] Klaus, B. and A. Nichifor (2020), “Serial dictatorship mechanisms with reservation
prices.” Economic Theory, 70(3): 665–684.
[12] Klaus, B. and A. Nichifor (2021), “Serial dictatorship mechanisms with reservation
prices: heterogeneous objects.” Social Choice and Welfare, 57(1): 145–162.
[13] Kosmopoulou, G. and D. G. De Silva (2007), “The eﬀect of shill bidding upon prices:
Experimental evidence.” International Journal of Industrial Organization, 25(2): 291–
313.
[14] Lamy, L. (2009), “The shill bidding eﬀect versus the linkage principle.” Journal of
Economic Theory, 144(1): 390–413.
[15] Lavi, R. and M. May (2012), “A note on the incompatibility of strategy-proofness andPareto-optimality in quasi-linear settings with public budgets.” Economics Letters,
115(1): 100–103.
[16] Levin, D. and J. Peck (2023), “Misbehavior in common value auctions: Bidding ringsand shills.” American Economic Journal: Microeconomics, 15(1): 171–200.

33

[17] Majadi, N., J. Trevathan, H. Gray, V. Estivill-Castro, and N. Bergmann (2017), “Realtime detection of shill bidding in online auctions: A literature review.” Computer
Science Review , 25: 1–18.
[18] Malik, K. and D. Mishra (2021), “Pareto eﬃcient combinatorial auctions: Dichotomous preferences without quasilinearity.” Journal of Economic Theory, 191: 105128.
[19] McCannon, B. C. and E. Minuci (2020), “Shill bidding and trust.” Journal of Behavioral and Experimental Finance, 26: 100279.
[20] Milgrom, P. and R. J. Weber (1982), “A theory of auctions and competitive bidding.”
Econometrica, 50(5): 1089–1122.
[21] Muto, N. and Y. Shirata (2017), “Manipulation via endowments in auctions withmultiple goods.” Mathematical Social Sciences, 87: 75–84.
[22] Myerson, R. B. (1981), “Optimal auction design.” Mathematics of Operations Research, 6(1): 58–73.
[23] Saitoh, H. and S. Serizawa (2008), “Vickrey allocation rule with income eﬀect.” Economic Theory, 35(2): 391–401.
[24] Sakai, T. (2008), “Second price auctions on general preference domains: Two characterizations.” Economic Theory, 37(2): 347–356.
[25] Sher, I. (2012), “Optimal shill bidding in the VCG mechanism.” Economic Theory,50(2): 341–387.
[26] Shinozaki, H. (2022), “Characterizing pairwise strategy-proof rules in object allocation
problems with money.” ISER Discussion Paper No. 1187.
[27] Shinozaki, H. (2024a), “Optimal shill bidding by the seller under private valuations.”
Working paper.
[28] Shinozaki, H. (2024b), “Shutting-out-proofness in object allocation problems withmoney.” Working paper.
[29] Shinozaki, H., T. Kazumura, and S. Serizawa. (2022), “Multi-unit object allocation
problems with money for (non)decreasing incremental valuations: Impossibility andcharacterization theorems.” ISER Discussion Paper No. 1097.
34

[30] Vickrey, W. (1961), “Counterspeculation, auctions, and competitive sealed tenders.”
Journal of Finance, 16(1): 8–37.
[31] Wilson, R. (1969), “Competitive bidding with disparate information.” Management
Science, 15(7): 446–448.
[32] Yokoo, M., Y. Sakurai, and S. Matsubae (2004), “The eﬀect of false-name bids in combinatorial auctions: new fraud in internet auctions.” Games and Economic Behavior ,46(1): 174–188.

35