HIAS-E-138

Shutting-out-proofness 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

Shutting-out-proofness in object allocation problems
with money∗
Hiroki Shinozaki†
February 13, 2024

Abstract
We study the problem of allocating heterogeneous objects to agents with money.
Each agent can receive several objects and has a quasi-linear utility function. The
owner of the objects is only interested in his revenue from an allocation. An (allocation) rule is shutting-out-proof if no group of agents together with the owner ever
beneﬁts from shutting out other groups of agents and arranging payments among
themselves. We show that on any domain that includes all the additive valuation
functions, a Vickrey rule satisﬁes shutting-out-proofness if and only if all the valuation functions in the domain satisfy the substitutes condition (Kelso and Crawford,
1982). Our result sheds a new light on the relationship between the desirable properties of a Vickrey rule and the substitutes condition (Ausubel and Milgrom, 2002;
Milgrom, 2004).

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

Keywords. Shutting-out-proofness, Collusion, Vickrey rules, Substitutes condition,
Combinatorial auctions

1

Introduction

1.1

PurposeWe study the problem of allocating heterogeneous objects to agents with money. Eachagent can receive several objects and has a quasi-linear utility function. A valuation func∗

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

tion speciﬁes the valuation (the willingness to pay) of each set of objects. Note that aquasi-linear utility function is characterized by a valuation function. A class of valuation
functions is called a domain. We consider the model where the set of agents can vary
while the set of objects is ﬁxed. An economy is a pair consisting of a set of agents andvaluation functions of the agents. A (consumption) bundle is a pair of a set of objects
that an agent receives and a payment that he makes. An allocation for a given economy
speciﬁes a bundle for each agent in the economy. We assume that the owner of the objects
in only interested in his revenue (i.e., the sum of payments) from an allocation, and so hedoes not care who get what objects. An (allocation) rule is a function that associates anallocation with each economy.
Important examples of the problem are combinatorial auctions such as public procurement auctions, spectrum auctions, etc. One of the biggest concerns of practical auctions
is to prevent agents from collusion (Klemperer, 2002). There is a plenty of research thatstudies collusion among a group of agents in auctions (Graham and Marshall, 1987; McAfee
and McMillan, 1992; Pavlov, 2008; Che and Kim, 2009; Che et al., 2018; Shinozaki, 2022,
etc.).
In contrast, to the best of our knowledge, there is no research prior to this paper andour companion papers (Shinozaki, 2023a,b) that studies rules preventing collusion between
a group of agents and the owner of the object. In practical auctions such as public procurement auctions in Japan, collusion between a group of agents and the owner is pervasive
as well as collusion among only a group of agents (McMillan, 1991, 2003). There are several types of such collusion, e.g., a group of agents together with the owner may beneﬁt
from misrepresenting the agents’ valuation functions and arranging payments among themselves, or they may beneﬁt from shutting out rival agents and arranging payments among
themselves.
In this paper, we focus on collusion between a group of agents and the owner suchthat they beneﬁt from shutting out other groups of agents and arranging payments among
themselves.1 Such collusion will suppress new entrants into a market, which is one of thebiggest concerns of practical auction design as well as preventing collusion (Klemperer,
2002).
1

In our companion papers (Shinozaki, 2023a,b), we study collusion such that a group of agents andthe owner beneﬁt from misrepresenting the agents’ valuation functions and arranging payments among
themselves.

2

In a practical auction, the planner (typically equivalent to the owner) is often able toselect the participants of the auction, and so it is easy to conduct such collusion (McMillan,
1991, 2003). In fact, there are several examples of such collusion in the Japanese public
procurement auctions that are detected and punished by the law. For example, in 2023,
the former vice mayor of Kushima City, Miyazaki, Japan (corresponding to the owner),
together with a president and employees of several construction companies (corresponding
to a group of agents), was arrested for collusion such that they jointly shut out some groupof companies in a procurement auction for public construction. 2
The purpose of this paper is to study the class of rules that prevent a group of agents
together with the owner from shutting out other groups of agents.

1.2

Main result

We propose a new property of a rule that prevents a set of agents and the owner fromshutting out other agents. A rule satisﬁes shutting-out-proofness if, given an economy, no
subset of the agents in the economy together with the owner ever beneﬁts from shuttingout other agents outside the economy and arranging payments among themselves. We
also propose a new property that we call aggregate utility monotonicity. A rule satisﬁes
aggregate utility monotonicity if, given an economy, the sum of utilities from an outcome
allocation of the rule among each subset of the agents in the economy and the owner weakly
increases when other agents entry into the economy. First, we establish the equivalence
between shutting-out-proofness and aggregate utility monotonicity (Proposition 1): On
any domain, a rule satisﬁes shutting-out-proofness if and only if it satisﬁes aggregate
utility monotonicity.
We are interested in the class of rules satisfying shutting-out-proofness together withthe other desirable and standard properties: strategy-proofness, eﬃciency, individual rationality, and no subsidy.3 A rule is a Vickrey rule (Vickrey, 1961) if it allocates the objects
to the agents so as to maximize the sum of valuations, and the payment of each agent isequal to the impact on the other agents. It is well known that the Vickrey rules are the2

A news article (in Japanese) that reports the collusion incident is: https://www3.nhk.or.jp/lnews/
miyazaki/20231207/5060017062.html.
3
A rule satisﬁes strategy-proofness if no agent ever beneﬁts from misrepresenting his valuation functions.
It satisﬁes eﬃciency if the object allocation chosen by the rule always maximizes the sum of valuations.
It satisﬁes individual rationality if no agent ever gets worse oﬀ than the non-participation. It satisﬁes no
subsidy if the payment of each agent is always non-negative.

3

only rules satisfying strategy-proofness, eﬃciency, individual rationality, and no subsidy(Holmstròm, 1979; Chew and Serizawa, 2007), Thus, we focus on the Vickrey rules, andstudy whether and when a Vickrey rule satisﬁes shutting-out-proofness.
A valuation function satisﬁes the substitutes condition (Kelso and Crawford, 1982) if
the increase of a price of an object does not decrease the demand of the other objects. A
valuation function is additive if it is an additive function. Note that each additive valuation
function satisﬁes the substitutes condition.
The main result of this paper (Theorem 1) is as follows: On any domain that includes
all the additive valuation functions, a Vickrey rule satisﬁes shutting-out-proofness if andonly if all the valuation functions in the domain satisfy the substitutes condition. Recall
that shutting-out-proofness is equivalent to aggregate utility monotonicity (Proposition 1).
Thus, Theorem 1 also implies that a Vickrey rule on any domain that includes all the
additive valuation functions satisﬁes aggregate utility monotonicity if and only if all thevaluation functions in the domain satisfy the substitutes condition.

1.3

Related literature

There are several papers that study collusion only among agents. Some papers study theequilibrium properties of a speciﬁc rule such as a ﬁrst-price and a second-price rules in thepresence of collusion among agents (Graham and Marshall, 1987; McAfee and McMillan,
1992; Pesendorfer, 2000; Marshall and Marx, 2007, 2009, etc.), while others study rulesthat prevent collusion among agents (Pavlov, 2008; Che and Kim, 2009; Che et al., 2018;
Shinozaki, 2022, etc.). This paper is close to the latter papers in that we also study rulesthat prevent collusion, but is diﬀerent from those papers in that we focus on collusion
between a group of agents and the owner, while they do collusion among a group of agents.
As already noted, there has been no previous study that investigates rules preventing collusion between a group of agents and the owner, and this paper together with ourcompanion papers (Shinozaki, 2023a,b) are the ﬁrst to study such rules. In contrast withthis paper, Shinozaki (2023a,b) both study two-sided collusion-proofness which requires nogroup of agents together with the owner ever beneﬁt from misrepresenting the agents’ valuation functions and arranging payments among themselves. Shinozaki (2023b) establishes
that the only rules satisfying two-sided collusion-proofness, strategy-proofness, individual
rationality, and no subsidy are the constant rules which output the same outcome for4each valuation proﬁle, while a Vickrey rule can prevent speciﬁc two-sided collusion such as
two-sided collusion without side payments and all-inclusive two-sided collusion. Shinozaki(2023a) characterizes the ﬁrst-price rules in the single object model as the only rules thatsatisfy Bayesian incentive compatibility, eﬃciency, individual rationality, and no subsidy,
and prevent “self-imposing” two-sided collusion under which no single agent has unilateralincentives to deviate from the collusion.
There are some papers that study corruption in auctions by the owner (Celentani
and Ganuza, 2002; Compte et al., 2005; Menezes and Monteiro, 2006; Arozamena andWeinschelbaum, 2009, Lengwiler and Wolfstetter, 2010; Burguet, 2017, etc.) They study
speciﬁc rules such as a ﬁrst-price and a second-price rules or optimal rules in models
where the owner has a chance to bribe agents, and investigate the equilibrium propertiesof speciﬁc rules or derive optimal rules. Note that collusion between a group of agentsand the owner that we consider in this paper can be regarded as a kind of corruption by
the owner. The diﬀerence between this paper and these paper lies in the attitude towardcorruption. Indeed, we interpret corruption (i.e., collusion between a group of agents andthe owner) as a phenomenon that should be prevented, and investigate rules that prevent
such corruption. In contrast, they take the possibility of corruption as given, and study
the equilibrium properties of rules or derive optimal rules in the presence of corruption.
It is known in the literature that a Vickrey rule on a domain including all the additive
valuation functions satisﬁes the desirable properties such as core allocation property, utility
monotonicity, loser-collusion-proofness, and false-name-proofness (Yokoo et al., 2004) if
and only if all the valuation functions in the domain satisfy the substitutes condition(Ausubel and Milgrom, 2002; Ausubel, 2004).4 Our main result (Theorem 1) sheds a
new light on the relationship between the desirable properties of a Vickrey rule and thesubstitutes condition, i.e., the equivalence between shutting-out-proofness (or aggregate
utility monotonicity) of a Vickrey rule and the substitutes condition.

4

A rule satisﬁes core allocation property if an outcome allocation of a rule is always a core allocation.
It satisﬁes utility monotonicity if the utility of each agent weakly increases when some agents leave froman economy. It satisﬁes loser-collusion-proofness if no group of losers ever beneﬁts from misrepresenting
their valuation functions. It satisﬁes false-name-proofness if no agent ever beneﬁts from introducing “falsename” agents.

5

1.4

Organization

The rest of this paper is organized as follows. Section 2 introduces the model. Section 3
introduces the Vickrey rules. Section 4 presents the main result. Section 5 discusses indetail the relationships between shutting-out-proofness and the other desirable propertiesof a Vickrey rule under the substitutes condition. Section 6 concludes. All the proofs arerelegated to the Appendix.

2

Model

The set of potential agents is N. Let N = {N ⊆ N : 0 < |N | < ∞}. Let 0 indicate theowner of the objects. The owner holds m ≥ 1 heterogeneous objects. Let M = {1, . . ., m}denote the set of objects. Let M denote the power set of M , i.e., M = 2M . A set ofobjects that an agent i ∈ N receives is Ai ∈ M. The amount of a payment that an agenti ∈ N makes is ti ∈ R. Then, the (consumption) set of an agent i ∈ N is M × R, and a(consumption) bundle of an agent i ∈ N is a pair zi = (Ai , ti ) ∈ M × R.
An agent i ∈ N has a quasi-linear utility function ui : M × R → R such that for somevaluation function vi : M → R+ , (i) vi (∅) = 0, (ii) for each pair Ai , A′i ∈ M with
Ai ⊇ A′i , vi (Ai ) ≥ vi (A′i ), and (iii) for each zi = (Ai , ti ) ∈ M × R, ui (zi ; vi ) = vi (Ai ) − ti .
The second condition (ii) above corresponds to free disposal. Note that a quasi-linear
utility function is fully speciﬁed by a valuation function. Thus, we identify a set of quasilinear utility functions with a set of valuation functions. Our generic notation for a classof valuation functions is V. We call V a domain.
We introduce the two classes of valuation functions that will play important role in thispaper.
Given vi ∈ V and a price vector p = (pa )a∈M ∈ Rm
+ , the demand set for vi at p is(((({∑ ) )}∑ ) )pa ; vi .
pa ; vi ≥ ui A′i ,D(vi , p) = Ai ∈ M : ∀A′i ∈ M, ui Ai ,
a∈Ai

a∈A′i

First, a valuation function vi satisﬁes the substitutes condition (Kelso and Crawford,
1982) if, for each price vector p ∈ Rm
+ , each a ∈ M , each ε ∈ R++ , and each Ai ∈ D(vi , p),6

there is A′i ∈ D(vi , p + εea ) such thatAi ∩ (M \{a}) ⊆ A′i ,where ea denotes the a-th unit vector whose a-th component is 1, and all the other components are 0. Let VSub denote the class of valuation functions satisfying the substitutes
condition. We call VSub the substitutes domain.
Second, a valuation function vi is additive if it is an additive function, i.e., for eachpair Ai , A′i ∈ M with Ai ∩ A′i = ∅, we have vi (Ai ∪ A′i ) = vi (Ai ) + vi (A′i ). Let VAdd
denote the class of additive valuation functions. We call VAdd the additive domain. Notethat VAdd ⊆ VSub , i.e., each additive valuation function satisﬁes the substitutes condition.
When m = 1, VAdd = VSub , and both the domains are equal to the class of all valuation
functions.
Given N ∈ N , a valuation proﬁle for N is vN = (vi )i∈N ∈ V N .
Given a domain V, an economy on V is a triple e = (N, M, vN ), where N ∈ N andvN ∈ V N . The set of objects M are ﬁxed throughout the paper, and so we may omit M
from an economy. Thus, an economy is a pair e = (N, vN ). Given V, let E(V) denote theclass of economies on V. We may omit a domain V from E(V), and let E denote the classof all economies on V.
Given N ∈ N , a (feasible) object allocation for N is AN = (Ai )i∈N ∈ MN suchthat ∪i∈N Ai ⊆ M . Let XN denote the set of all object allocations for N . Also, given
N ∈ N , a (feasible) allocation for N is zN = (zi )i∈N = (Ai , ti )i∈N ∈ (M × R)n suchthat (Ai )i∈N ∈ XN . Let ZN denote the set of all allocations for N . Given an allocationzN = (zi )i∈N ∈ ZN for N ∈ N and N ′ ∈ N with N ′ ⊆ N , let zN ′ = (zi )i∈N ′ .
The owner of the objects is only interested in his revenue from an allocation. Thus, he
has a quasi-linear utility function u0 from ∪N ∈N ZN to R such that for each N ∈ N and∑each zN = (Ai , ti )i∈N ∈ ZN , u0 (zN ) = i∈N ti .
An (allocation) rule on V is a function f : E → ∪N ∈N ZN such that for each e =(N, vN ) ∈ E, f (e) ∈ ZN . Given a rule f on V, let xf : E → ∪N ∈N XN denote the object
allocation rule associated with f , and tf : E → ∪N ∈N RN the associated payment rule.
Given a rule f on V, e = (N, vN ) ∈ E, and i ∈ N , let fi (e) = (xfi (e), tfi (e)) denote an
outcome bundle of agent i for e under f .
We introduce the properties of rules.
7

The following is a new property which requires that given an economy e = (N, vN ),no subset of N together with the owner ever beneﬁt from shutting out other agents andarranging payments among themselves.
′

Shutting-out-proofness. For each pair N, N ′ ∈ N with N ∩ N ′ = ∅ and each vN ∪N ′ ∈ V N ∪N ,′′there are no N ′′ ∈ N with N ′′ ⊆ N and (pi )i∈N ′′ ∈ RN such that for each i ∈ N ′′ ,ui (fi (N, vN ); vi ) − pi > ui (fi (N ∪ N ′ , vN ∪N ′ ); vi ),andu0 (f (N, vN )) +∑pi > u0 (f (N ∪ N ′ , vN ∪N ′ )).

i∈N ′′

The following is also a new property which requires that given an economy e = (N, vN ),the sum of utilities from an outcome allocation of a rule among each subset of N and theowner weakly increase by the entry of other agents outside the economy. 5
Aggregate utility monotonicity. For each pair N, N ′ ∈ N with N ∩ N ′ = ∅, each′

N ′′ ∈ N with N ′′ ⊆ N , and each vN ∪N ′ ∈ V N ∪N , we have∑ui (fi (N ∪ N ′ , vN ∪N ′ ); vi ) + u0 (f (N ∪ N ′ , vN ∪N ′ )) ≥i∈N ′′∑ui (fi (e); vi ) + u0 (f (e)).

i∈N ′′

The following property requires that no agent ever beneﬁt from misrepresenting his
valuation functions.
Strategy-proofness. For each e = (N, vN ) ∈ E, each i ∈ N , and each vi′ ∈ V, we haveui (fi (e); vi ) ≥ ui (fi (N, (vi′ , vN \{i} )); vi ).

The following property requires that a rule select an allocation that maximize the sum
5Note that our aggregate utility monotonicity is diﬀerent from the following natural monotonicity
property of aggregate utility which requires that the aggregate utility weakly increase when a set of agents′
expands: For each pair N, N ′ ∈ N with N ∩ N ′ = ∅ and each vN ∪N ′ ∈ V N ∪N , we have∑∑ui (fi (N ∪ N ′ , vN ∪N ′ ); vi ) + u0 (f (N ∪ N ′ , vN ∪N ′ )) ≥ui (fi (N, vN ); vN ) + u0 (f (N, vN )).
i∈N ∪N ′i∈N

In general, our aggregate utility monotonicity is independent of the above monotonicity property, i.e., theformer does not necessarily imply the latter, and vice versa.

8

of valuations, i.e., a (Pareto) eﬃcient allocation.
Eﬃciency. For each e = (N, vN ) ∈ E, we have xf (e) ∈ arg max∑

xN ∈XNi∈N vi (xi ).

The following property requires that each agent ﬁnd his outcome bundle of a rule atleast as desirable as the non-participation under which he obtains the utility of zero.
Individual rationality. For each e = (N, vN ) ∈ E and each i ∈ N , ui (fi (e); vi ) ≥ 0.

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

We are interested in the class of rules satisfying shutting-out-proofness, strategy-proofness,eﬃciency, individual rationality, and no subsidy, and study such a class of rules in thispaper.

3

Vickrey rule

In this section, we introduce the Vickrey rules (Vickrey, 1961).
Given an economy e = (N, vN ) ∈ E, letw(e) = max

xN ∈XN∑vi (xi )i∈Ndenote the maximal sum of valuations for the economy e. For notational convenience, letw(∅, v∅ ) = 0. Note that a rule f on V is eﬃcient if and only if for each e = (N, vN ) ∈ E,∑
w(e) = i∈N vi (xfi (e)).
Under a Vickrey rule, the objects are allocated so as to maximize the sum of valuations,and each agent pays the impact on the other agents.
Deﬁnition 1. A rule f on V is a Vickrey rule (Vickrey, 1961) if, for each e = (N, vN ) ∈ E,
xf (e) ∈ arg max
xN ∈XN9∑i∈Nvi (xi ),and for each i ∈ N
tfi (e) = w(N \{i}, vN \{i} ) −∑vj (xfj (e)).

j∈N \{i}The following fact states that on any domain that includes the additive domain, theVickrey rules are the only rules satisfying strategy-proofness, eﬃciency, individual rationality, and no subsidy.
Fact 1 (Holmstròm, 1979; Chew and Serizawa, 2007). Let V be a domain such thatV ⊇ VAdd . A rule on V satisﬁes strategy-proofness, eﬃciency, individual rationality, andno subsidy if and only if it is a Vickrey rule.
Thanks to Fact 1, we can restrict our attention to the class of Vickrey rules. Then, westudy whether and when a Vickrey rule satisﬁes shutting-out-proofness in the next section.

4

Main result

In this section, we present the main result of this paper.
First, the next result states that a rule on any domain satisﬁes shutting-out-proofness
if and only if it satisﬁes aggregate utility monotonicity. That is, shutting-out-proofness isequivalent to aggregate utility monotonicity on any domain.
Proposition 1. Let V be a domain. Let f be a rule on V. The following two statements
are equivalent.
(i) f satisﬁes shutting-out-proofness.
(ii) f satisﬁes aggregate utility monotonicity.
The next result is the main result of this paper which states that a rule on any domainthat includes the additive domain satisﬁes shutting-out-proofness (or equivalently, aggregate utility monotonicity by Proposition 1) if and only if all the valuation functions in thedomain satisfy the substitutes condition.
Theorem 1. Let V be a domain such that V ⊇ VAdd . Let f be a Vickrey rule on V. The
following three statements are equivalent.
(i) f satisﬁes shutting-out-proofness.

10(ii) f satisﬁes aggregate utility monotonicity.
(iii) We have V ⊆ VSub .
A corollary of Theorem 1 and Fact 1 is that the substitutes domain is the uniquemaximal domain that includes the additive domain for the existence of a rule satisfying
shutting-out-proofness (or aggregate utility monotonicity), strategy-proofness, eﬃciency,
individual rationality, and no subsidy.
Corollary 1. Let V be a domain such that V ⊇ VAdd . The following three statements areequivalent.
(i) There is a rule on V satisfying shutting-out-proofness, strategy-proofness, eﬃciency,
individual rationality, and no subsidy.
(ii) There is a rule on V satisfying aggregate utility monotonicity, strategy-proofness,eﬃciency, individual rationality, and no subsidy.
(iii) We have V ⊆ VSub .

5

Discussion

In this section, we discuss the relationships between shutting-out-proofness and the otherdesirable properties of a Vickrey rule under the substitutes condition.
First, we introduce the properties that a Vickrey rule satisﬁes under the substitutes
condition.
Given e = (N, vN ) ∈ E, an allocation zN = (zi )i∈N = (xi , ti )i∈N ∈ Z for N is a core∑
allocation for e if w(N ) = i∈N vi (xi ), and there exists no N ′ ∈ N with N ′ ⊆ N such∑that w(N ′ ) >i∈N ′ ui (zi ; vi ) + u0 (zN ′ ). The following property requires that an outcome
allocation of a rule be a core allocation.
Core allocation property. For each e ∈ E, f (e) is a core allocation for e.

The next property requires that each agent get weakly better oﬀ when some agents
leave from the economy.
Utility monotonicity. For each e = (N, vN ) ∈ E, each N ′ ∈ N with N ′ ⊆ N , and each11i ∈ N ′ , we haveui (fi (N ′ , vN ′ ); vi ) ≥ ui (fi (e); vi ).
The next property requires that no group of losers who receive no object ever beneﬁt
from misrepresenting their valuation functions.
Loser-collusion-proofness. For each e = (N, vN ) and each N ′ ∈ N with N ′ ⊆ N and′′N
Afi (e) = ∅ for each i ∈ N ′ , there is no vNsuch that for each i ∈ N ′ ,′ ∈ V′ui (fi (N, (vN′ , vN \N ′ )); vi ) > ui (fi (e); vi )(1)

Finally, the following property was introduced by Yokoo et al. (2004), which requiresthat no agent ever beneﬁt from introducing “false-name” agents.
False-name-proofness. For each e = (N, vN ) ∈ E and each N ′ ∈ N with N ∩ N ′ = ∅,′there is no vN ′ ∈ V N such thatvi(∪j∈N ′ ∪{i}

Afj (N ∪ N ′ , vN ∪N ′ )

)

−

∑

tfj (N ∪ N ′ , vN ∪N ′ ) > ui (fi (e); vi ).

j∈N ′ ∪{i}

The following fact states that a Vickrey rule on any domain that includes the additive
domain satisﬁes any of the above four properties if and only if all the valuation functionsin the domain satisfy the substitutes condition. Thus, under a Vickrey rule, the above four
properties are all equivalent.
Fact 2 (Ausubel and Milgrom, 2002; Milgrom, 2004). Let V be a domain such thatV ⊇ VAdd . Let f be a Vickrey rule on V. The following ﬁve statements are equivalent.
(i) f satisﬁes core allocation property.
(ii) f satisﬁes utility monotonicity.
(iii) f satisﬁes loser-collusion-proofness.
(iv) f satisﬁes false-name-proofness.
(v) We have V ⊆ VSub .
Our result (Theorem 1) adds a new property to the list of desirable properties of a
Vickrey rule under the substitutes condition in Fact 2: shutting-out-proofness (or equivalently, aggregate utility monotonicity). By Theorem 1 and Fact 2, shutting-out-proofness12and aggregate utility monotonicity are both equivalent to any of the above four properties
under a Vickrey rule. By Fact 1, we can also conclude that shutting-out-proofness (oraggregate utility monotonicity) is equivalent to any of the four properties under a rulesatisfying strategy-proofness, eﬃciency, individual rationality, and no subsidy.
In the remaining part of this section, we show that if we drop either strategy-proofness
or eﬃciency, then shutting-out-proofness (or aggregate utility monotonicity) is no longer
equivalent to any of the above four properties. Thus, shutting-out-proofness (or aggregate
utility monotonicity) itself is an independent property of the other desirable properties ofa Vickrey rule under the substitutes condition.
First, we demonstrate that if we drop strategy-proofness, then shutting-out-proofness
is independent of core allocation property, i.e., shutting-out-proofness does not necessarily
imply core allocation property, and vice versa.
Example 1 (Core allocation property is independent of shutting-out-proofness).
Let m = 1. Let V = VSub .
(i) Let f be a third-price rule on V.6 Then, it satisﬁes shutting-out-proofness, but violatescore allocation property. Note that it also satisﬁes eﬃciency, individual rationality and no
subsidy, but violates strategy-proofness.
(ii) Let f be a rule on V such that for each e = (N, vN ) ∈ E, if |N | = 1, then f (e) is
equivalent to the outcome of a ﬁrst-price rule for e,7 and otherwise, it is equivalent to
the outcome of a second-price rule for e.8 Then, it satisﬁes core allocation property, butviolates shutting-out-proofness. Note that it also satisﬁes eﬃciency, individual rationality,and no subsidy, but violates strategy-proofness.
The next example shows that if we drop eﬃciency, then utility monotonicity is independent of shutting-out-proofness.
Example 2 (Utility monotonicity is independent of shutting-out-proofness). Let
m = 1. Let V = VSub .
A rule f on V is a third-price rule if for each e = (N, vN ) ∈ E, an agent with the highest valuation
wins the object, he pays the third-highest valuation (if |N | ≤ 2, then he pays nothing), and each loser pays
nothing.
7
A rule f on V is a ﬁrst-price rule if for each e ∈ E, an agent with the highest valuation wins the object,
he pays his own valuation, and each loser pays nothing.
8
A rule f on V is a second-price rule if an agent with the highest valuation wins the object, he pays
the second-highest valuation (if |N | = 1, then he pays nothing), and each loser pays nothing. Note that asecond-price rule is equivalent to a Vickrey rule in the single object setting.
613

(i) Let f be a rule on V such that for each e = (N, vN ) ∈ E, if |N | = 1, then f (e) is
equivalent to the outcome of the no-trade rule for e,9 and otherwise, it is equivalent to theoutcome of a second-price rule for e. Then, it satisﬁes shutting-out-proofness, but violates
false-name-proofness. Note that it also satisﬁes strategy-proofness, individual rationality,and no subsidy, but violates eﬃciency.
(ii) Let f be a rule on V such that for each e = (N, vN ) ∈ E, if |N | = 1, then f (e) is
equivalent to the outcome of a second-price rule for e, and otherwise, it is equivalent to
the outcome of the no-trade rule for e. Then, it satisﬁes false-name-proofness, but violates
shutting-out-proofness. Note that it also satisﬁes strategy-proofness, individual rationality,and no subsidy, but violates eﬃciency.
The next example shows that if we drop strategy-proofness, then loser-collusion-proofness
is independent of shutting-out-proofness.
Example 3 (Loser-collusion-proofness is independent of shutting-out-proofness).
Let m = 1. Let V = VSub .
(i) Let f be a rule on V such that for each e = (N, vN ) ∈ E, if |N | ≤ 2, then f (e) is equivalent to the outcome of a third-price rule, and otherwise, it is equivalent to the outcome ofa second-price rule. Then, it satisﬁes shutting-out-proofness, but violates loser-collusionproofness. It also satisﬁes eﬃciency, individual rationality and no subsidy, but violates
strategy-proofness.
(ii) Let f be a rule on V such that for each e = (N, vN ) ∈ E, if |N | ≤ 2, then f (e) is
equivalent to the outcome of a ﬁrst-price rule for e, and otherwise, it is equivalent to theoutcome of a second-price rule for e. Then, it satisﬁes loser-collusion-proofness, but violates
shutting-out-proofness. It also satisﬁes eﬃciency, individual rationality, and no subsidy,
but violates strategy-proofness.
Finally, the next example shows that if we drop eﬃciency, then false-name-proofness is
independent of shutting-out-proofness.
Example 4 (False-name-proofness is independent of shutting-out-proofness).
Let m = 1. Let V = VSub .
(i) Let f be a rule on V deﬁned in Example 2 (i). Then, it satisﬁes shutting-out-proofness,
9

A rule f on V is the no-trade rule if for each e = (N, vN ) ∈ E and each i ∈ N , fi (e) = (∅, 0).

14

but violates false-name-proofness. It also satisﬁes strategy-proofness, individual rationality, and no subsidy, but violates eﬃciency.
(ii) Let f be a rule on V deﬁned in Example 2 (ii). Then, it satisﬁes false-name-proofness,but violates shutting-out-proofness. It also satisﬁes strategy-proofness, individual rationality, and no subsidy, but violates eﬃciency.

6

Conclusion

In this paper, we have considered collusion between a group of agents and the owner suchthat they beneﬁt from shutting out other groups of agents with the possibility of arranging
payments among themselves. We have proposed a new property of a rule that prevents suchcollusion (shutting-out-proofness) , and established that a Vickrey rule on a domain that
includes the additive domain satisﬁes shutting-out-proofness if and only if all the valuation
functions in the domain satisfy the substitutes condition (Theorem 1). Our result provides
a new insight into the relationship between the desirable properties of a Vickrey rule andthe substitutes condition (Ausubel and Milgrom, 2002; Milgrom, 2004).
In our formulation of shutting-out-proofness, we allow a group of agents and the ownerto arrange payments among themselves. Such a “bribe” (i.e., side payments) is typicalin practical collusion between agents and the owner,10 but it is also possible that they
may not arrange payments in fear of detection of the collusion by the antitrust authority.
Then, it would be interesting to investigate when a Vickrey rule satisﬁes a weaker versionof shutting-out-proofness without the possibility of arranging payments among themselves.

AppendixA

Proof of Proposition 1

In this section, we prove Proposition 1.

10

For example, a news article reports that the former mayor of Shika Town, Ishikawa, Japan, and thepresident of a construction company in Shika Town were arrested for leakage of the minimum bid price fromthe former mayor and a bribe from the president of a construction company in a Japanese procurement
auction for public construction. See: https://www.asahi.com/articles/ASRD902DKRD8PISC00S.html.

15

A.1

(i) implies (ii)First, we show that (i) implies (ii). We show the contrapositive. Suppose that f violates
aggregate utility monotonicity. Then, there exist a pair N, N ′ ∈ N with N ∩ N ′ = ∅,′N ′′ ∈ N with N ′′ ⊆ N , and vN ∪N ′ ∈ V N ∪N such that∑ui (fi (N, vN ); vi )+u0 (f (N, vN )) >i∈N ′′∑ui (fi (N ∪ N ′ , vN ∪N ′ ); vi )+u0 (f (N ∪ N ′ , vN ∪N ′ )).

i∈N ′′

Then, we can choose ε ∈ R++ such that|N ′′ |ε < u0 (f (N, vN )) +∑(ui (fi (N, vN ); vi ) − ui (fi (N ∪ N ′ , vN ∪N ′ ); vi ))i∈N ′′− u0 (f (N ∪ N ′ , vN ∪N ′ )).

(1)

For each i ∈ N ′′ , let pi = ui (fi (N, vN ); vi ) − ui (fi (N ∪ N ′ , vN ∪N ′ ); vi ) − ε. Then, for eachi ∈ N ′′ , by ε > 0,ui (fi (N, vN ); vi ) − pi = ui (fi (N ∪ N ′ , vN ∪N ′ ); vi ) + ε > ui (fi (N ∪ N ′ , vN ∪N ′ ); vi ).
We also have∑u0 (f (N, vN )) +pi − u0 (f (N ∪ N ′ , vN ∪N ′ ))i∈N ′′= u0 (f (N, vN )) +∑()
ui (fi (N, vN ); vi ) − ui (fi (N ∪ N ′ , vN ∪N ′ ); vi ) −u0 (f (N ∪ N ′ , vN ∪N ′ )) − |N ′ |εi∈N ′′> 0,
where the last inequality follows from (1). Thus, f violates shutting-out-proofness.

A.2■(ii) implies (i)We show that (ii) implies (i). Again, we show the contrapositive. Suppose that f violates
shutting-out-proofness. Then, there exist a pair N, N ′ ∈ N with N ∩ N ′ = ∅, N ′′ ∈ N′′′with N ′′ ⊆ N , vN ∪N ′ ∈ V N ∪N , and (pi )i∈N ′′ ∈ RN such that for each i ∈ N ′′ ,ui (fi (N, vN ); vi ) − pi > ui (fi (N ∪ N ′ , vN ∪N ′ ); vi ),16andu0 (f (N, vN )) +∑pi > u0 (f (N ∪ N ′ , vN ∪N ′ )).

i∈N ′′

Summing up these inequalities yield∑ui (fi (N, vN ); vi ) + u0 (f (N, vN ))i∈N ′′=∑()∑
ui (fi (N, vN ); vi ) − pi +u0 (f (N, vN )) +pii∈N ′′>∑i∈N ′′ui (fi (N ∪ N ′ , vN ∪N ′ ); vi ) + u0 (f (N ∪ N ′ , vN ∪N ′ )).

i∈N ′′■

Thus, f violates aggregate utility monotonicity.

B

Proof of Theorem 1

In this section, we prove Theorem 1. Note that Proposition 1 implies that (i) is equivalentto (ii). Thus, it suﬃces to show that (ii) implies (iii) and (iii) implies (ii).
We begin with the following lemma. Although it follows from Theorem 8.1 of Milgrom(2004), we give a self-standing proof for completeness.
Lemma 1. For each e = (N, vN ) ∈ E and each N ′ ∈ N with N ′ ⊆ N , we have∑ui (fi (e); vi ) + u0 (f (e)) = w(e) −

i∈N ′

∑ (

)

w(e) − w(N \{i}, vN \{i} ) .

i∈N \N ′Proof. For each i ∈ N , we havetfi (e) = w(N \{i}, vN \{i} ) −∑vj (xfj (e)) = w(N \{i}, vN \{i} ) − (w(e) − vi (xfi (e))), (1)j∈N \{i}where the second equality follows from eﬃciency (i.e., w(e) =∑fj∈N vj (xj (e))). Then,

)
∑ f
∑(
f
u0 (f (e)) =ti (e) =w(N \{i}, vN \{i} ) − (w(e) − vi (xi (e)))
=

∑(

i∈N

i∈N

) ∑
w(N \{i}, vN \{i} ) − w(e) +vi (xfi (e))

i∈N= w(e) −

∑(

i∈N

)
w(e) − w(N \{i}, vN \{i} ) ,

i∈N

17

(2)

where the second equality follows from (1), and the last one from eﬃciency. Also, for eachi ∈ N , we haveui (fi (e); vi ) = vi (xfi (v)) −=∑(w(N \{i}, vN \{i} ) −∑vj (xfj (e)))

j∈N \{i}vj (xfj (e)) − w(N \{i}, vN \{i} ) = w(e) − w(N \{i}, vN \{i} ),

(3)

j∈N

where the last equality follows from eﬃciency. Then,∑ui (fi (e); vi ) + u0 (f (e))

i∈N ′= w(e) −

∑(

) ∑(
)
w(e) − w(N \{i}, vN \{i} ) +w(e) − w(N \{i}, vN \{i} ) (by (2) and 3)
i∈N ′

i∈N

= w(e) −∑ ()w(e) − w(N \{i}, vN \{i} ) ,i∈N \N ′as desired.
Given a domain V, w satisﬁes bidder submodularity on V if for each e = (N, vN ) ∈ E
with vN ∈ V N , each N ′ ∈ N with N ′ ⊆ N , and each i ∈ N ′ , we havew(N ′ , vN ′ ) − w(N ′ \{i}, vN ′ \{i} ) ≥ w(N, vN ) − w(N \{i}, vN \{i} ).
We invoke the following fact which states that on any domain V that includes the
additive domain, w satisﬁes bidder submodularity on V if and only if the domain V is
included in the substitutes domain.
Fact 3 (Ausubel and Milgrom, 2002; Milgrom, 2004). Let V be a domain such thatV ⊇ VAdd . The following two statement are equivalent.
(i) w satisﬁes bidder submodularity on V.
(ii) We have V ⊆ VSub

B.1(ii) implies (iii)

We show that (ii) implies (iii). We prove the contrapositive. Suppose that (iii) does
not hold, i.e., V ̸⊆ VSub . Then, by Fact 2, f violates core allocation property. Then, by

18

eﬃciency of f , there exist a pair N, N ′ ∈ N with N ′ ⊆ N and vN ∈ V N such thatw(N ′ , vN ′ ) >∑ui (fi (N, vN ); vi ) + u0 (f (N, vN )).

(1)

i∈N ′

By Lemma 1, we have∑ui (fi (N, vN ); vi ) + u0 (f (N, vN )) = w(N, vN ).

i∈N

Thus, by (1), we must have N ′ ̸= N . Thus, by N ′ ⊆ N , N ′ ⊊ N . Also, by Lemma 1, wehave∑ui (fi (N ′ , vN ′ ); vi ) + u0 (f (N ′ , vN ′ )) = w(N ′ , vN ′ ).

(2)

i∈N ′

Combining (1) and (2), we get∑ui (fi (N ′ , vN ′ ); vi )+u0 (f (N ′ , vN ′ )) = w(N ′ , vN ′ ) >

i∈N ′

∑

ui (fi (N, vN ); vi )+u0 (f (N, vN )).

i∈N ′Thus, by N ′ ⊊ N , f violates aggregate utility monotonicity, i.e., (ii) does not hold.

B.2■(iii) implies (ii)

We show that (iii) implies (ii). Suppose (iii) holds, i.e., V ⊆ VSub . By Fact 3, w satisﬁes
bidder submodularity on V. Let N, N ′ ∈ N be a pair such that N ∩ N ′ = ∅. Let N ′′ ∈ N′

be such that N ′′ ⊆ N . Let vN ∪N ′ ∈ V N ∪N . By bidder submodularity on V, we have∑ (i∈N \N ′′≥w(N, vN ) − w(N \{i}, vN \{i} )

∑ (

)

)
w(N ∪ N ′ , vN ∪N ′ ) − w(N ∪ N ′ \{i}, vN ∪N ′ \{i} ) .

i∈N \N ′′19(3)

Let N ′ = {i1 , . . ., iK }. For each k ∈ {1, . . ., K}, let N ′ (k) = {i1 , . . ., ik }. For notational
convenience, let N ′ (0) = ∅. We havew(N ∪ N ′ , vN ∪N ′ ) − w(N, vN ) =
≥

K (
∑
k=1
K (
∑
k=1

=

w(N ∪ N ′ (k), vN ∪N ′ (k) ) − w(N ∪ N ′ (k − 1), vN ∪N ′ (k−1) )′′w(N ∪ N , vN ∪N ′ ) − w(N ∪ N \{ik }, vN ∪N ′ \{ik } )

∑(

)

)
w(N ∪ N ′ , vN ∪N ′ ) − w(N ∪N ′ \{i}, vN ∪N ′ \{i} ) ,

i∈N ′

(4)
where the inequality follows from bidder submodularity on V. Then, we have(∑′w(N ∪ N , vN ∪N ′ ) −′′w(N ∪ N , vN ∪N ′ ) − w(N ∪ N \{i}, vN ∪N ′ \{i} )i∈N ∪N ′ \N ′′= w(N ∪ N ′ , vN ∪N ′ ) −−∑(w(N ∪ N ′ , vN ∪N ′ ) − w(N ∪ N ′ \{i}, vN ∪N ′ \{i} )≥ w(N ∪ N ′ , vN ∪N ′ ) −−w(N ∪ N ′ , vN ∪N ′ ) − w(N ∪ N ′ \{i}, vN ∪N ′ \{i} )i∈N \N ′′

i∈N ′

∑(

∑ (

∑ (

w(N ∪ N ′ , vN ∪N ′ ) − w(N ∪ N ′ \{i}, vN ∪N ′ \{i} )i∈N ′≥ w(N, vN ) −

∑ (

)

)

w(N, vN ) − w(N \{i}, vN \{i} )i∈N \N ′′

)

)

)

)
w(N, vN ) − w(N \{i}, vN \{i} ) .

(by (3))(by (4))i∈N \N ′′Thus, by Lemma 1, we get∑ui (fi (N ∪ N ′ , vN ∪N ′ ); vi )+u0 (f (N ∪ N ′ , vN ∪N ′ )) ≥i∈N ′′∑ui (fi (N, vN ); vi )+u0 (f (N, vN )),i∈N ′′■

as desired.

References[1] Arozamena, L. and F. Weinschelbaum (2002), “The eﬀect of corruption on bidding
behavior in ﬁrst-price auctions.” European Economic Review , 53(6): 645–657.

20)

[2] Ausubel, L. M. and P. Milgrom (2002), “Ascending auctions with package bidding.”
The B.E. Journal of Theoretical Economics, 1(1): 1–44.
[3] Burguet, R. (2017), “Procurement design with corruption.” American Economic Journal: Microeconomics, 9(2): 315–341.
[4] Celentani, M. and J.-J. Ganuza (2002), “Corruption and competition in procurement.”
European Economic Review , 46(7): 1723–1303.
[5] Che, Y.-K. and J. Kim (2009), “Optimal collusion-proof auctions.” Journal of Economic Theory, 144(2): 565–603.
[6] Che, Y.-K., D. Condorelli, and J. Kim (2018), “Weak cartels and collusion-proof
auctions.” Journal of Economic Theory, 178: 398–435.
[7] Chew, S. H. and S. Serizawa (2007), “Characterizing the Vickrey combinatorial auction
by induction.” Economic Theory, 33(2): 393–406.
[8] Compte, O., A. Lambert-Mogiliansky, and T.Verdier (2005), “Corruption and competition in procurement auctions.” The RAND Journal of Economics, 36(1): 1–15.
[9] Graham, D. A. and R. Marshall (1987), “Collusive bidder behavior at single-object
second-price and English auction.” Journal of Political Economy, 95(6): 1217–1239.
[10] Holmström, B. (1979), “Groves’ scheme on restricted domains.” Econometrica, 47(5):1137–1144.
[11] Kelso, A. S. and V. P. Crawford (1982), “Job matching, coalition formation, and grosssubstitutes.” Econometrica, 50(6): 1483–1504.
[12] Klemperer, P. (2002), “What really matters in auction design.” Journal of Economic
Perspectives, 16(1): 169–189.
[13] Lengwiler, Y. and E. Wolfstetter (2010), “Auctions and corruption: An analysis of bid
rigging by a corrupt auctioneer.” Journal of Economic Dynamics & Control , 34(10):1872–1892.
[14] Marshall, R. and L. Marx (2007), “Bidder collusion.” Journal of Economic Theory,
133(1): 374–402.
21

[15] Marshall, R. and L. Marx (2009), “The vulnerability of auctions to bidder collusion.”
The Quarterly Journal of Economics, 124(2): 883–910.
[16] McAfee, R. P. and J. McMillan (1992), “Bidding rings.” American Economic Review ,82(3): 579–599.
[17] McMillan, J. (1991), “DANGO: JAPAN’S PRICE-FIXING CONSPIRACIES.” Economics & Politics, 3(3): 201–218.
[18] McMillan, J. (2003), “Reinventing the bazaar: A natural history of markets.” New
York: W.W. Noron.
[19] Menezes, F. M. and P. K. Monteiro (2006), “Corruption and auctions.” Journal of
Mathematical Economics, 42(1): 97–108.
[20] Milgrom, P. (2004), “Putting auction theory to work.” Cambridge University Press.
[21] Pavlov, G. (2008), “Auction design in the presence of collusion.” Theoretical Economics, 3(3): 383–429.
[22] Pesendorfer, M. (2000), “A study of collusion in ﬁrst-price auctions.” Review of Economic Studies, 67(3): 381–411.
[23] Shinozaki, H. (2022), “Characterizing pairwise strategy-proof rules in object allocation
problems with money.” ISER Discussion Paper No. 1187,[24] Shinozaki, H. (2023a), “Two-sided collusion-proofness and ﬁrst-price rules.” Working
paper,[25] Shinozaki, H. (2023b), “Two-sided collusion-proofness in object allocation problems
with money.” Working paper.
[26] Vickrey, W. (1961), “Counterspeculation, auctions, and competitive sealed tenders.”
Journal of Finance, 16(1): 8–37.
[27] Yokoo, M., Y. Sakura, and S. Matsubara (2004), “The eﬀect of false-name bids in combinatorial auctions: New fraud in internet auctions.” Games and Economic Behavior ,46(1): 174–188.

22