Strategy-proofness and competitive equilibriumwith transferable utility: Gross substitutes revisited∗
Keisuke Bando†

Kenzo Imamura‡Tomoya Kazumura§

Abstract
We study the strategy-proofness (SP) of the competitive equilibrium selection (CE) mechanism in many-to-one matching with continuous transfersand quasilinear utility. The gross substitutes condition is known to guarantee the existence of CE and SP mechanisms. We show the converse: If a CE
and SP mechanism exists, then the valuation of each firm must satisfy thegross substitutes condition. Various conditions for the existence of competitive equilibria have been proposed in the literature. Our results suggest that
only the gross substitutes condition guarantees the existence of CE and SP
mechanisms. We provide additional implications of our results for investment
incentives and policy design. We also examine the two other models—the one
with non-quasilinear utility and the one with discrete transfers. In contrast,
the gross substitutes condition is not necessary in either model.

1

Introduction

The existence of competitive equilibria has been extensively studied in many economic
models. In the literature of matching theory, attention has been paid to many-toone matching models. These models consider matching between two types of agents,
such as firms and workers, sellers and buyers, hospitals and doctors, or schools and∗This work was partially supported by JSPS KAKENHI Grant Numbers 19K13643, 21H00696,
21H04979, 22H00062, 23K01312, 23K12443, and JST ERATO Grant Number JPMJER2301, Japan.
†
Department of Economics, University of Tokyo, email: imamurak@e.u-tokyo.ac.jp.
‡
Department of Industrial and Systems Engineering, Faculty of Science and Technology, Keio
University, email: bando@ae.keio.ac.jp.
§
Graduate School of Economics, Kyoto University, email: pge003kt@gmail.com.

1

students. In a many-to-one matching model with continuous transfers and quasilinear utility, Kelso and Crawford (1982) showed the gross substitutes condition (GS),which excludes the complementarity among workers in a firm’s valuation, guarantees
the existence of competitive equilibria. While GS is known to be a necessary conditionin the maximal domain sense (Gul and Stacchetti, 1999), competitive equilibria canexist even if GS is violated. Recent developments in this field have revealed that various conditions other than GS can guarantee the existence of competitive equilibria.
For example, Sun and Yang (2006) proposed the gross substitutes and complements
condition (GSC) and showed that, unlike GS, competitive equilibria exist even whencertain types of complement are allowed under GSC. Baldwin and Klemperer (2019)presented general conditions that include both GS and GSC as special cases.
GS offers an additional advantage: GS guarantees the existence of mechanismsthat select a competitive equilibrium (CE) and are strategy-proof for workers (SP)(Hatfield et al., 2018). SP is a central notion of incentive compatibility in the literature
on matching theory. SP mechanisms are strategically simple because workers do notneed to consider how other workers will report, since truthful reporting is a weakly
dominant strategy. Moreover, a CE and SP mechanism provides incentives for workers
to invest efficiently (Hatfield et al., 2018). While the literature has focused on theexistence of competitive equilibria, there has been less focus on SP mechanisms.
This naturally leads to the question: Are there conditions, aside from GS, that canguarantee the existence of CE and SP mechanisms?
We show that GS is necessary for the existence of CE and SP mechanisms (Theorem 1). Therefore, various conditions guarantee the existence of CE mechanisms,
but GS is the only one if we also require SP. Furthermore, our result differs from amaximal domain result. Specifically, our necessity states that if at least one firm’svaluation violates GS, then a CE and SP mechanism does not exist, regardless ofother firms’ valuations. This necessity is useful for checking the existence of desired
mechanisms for a given firm valuation profile. Section 4.1 discusses this point in moredetail.
Our result has additional implications—investment incentives and policy design.
First, our results show that GS is crucial for the existence of mechanisms that induce
efficient investment by workers. Agents typically make certain choices before participating in mechanisms. For example, workers invest considerable time and effort inacquiring skills prior to job matching. This investment can have a significant impact2

on individual and social welfare. Hatfield et al. (2018) showed the strong link between
SP and efficient investment. Together with their result and ours, we show that GS
is necessary and sufficient for the existence of CE mechanisms that induce efficientinvestment by workers. Second, it helps in the design of institutions or policies. A
government often imposes a tax or subsidy on a firm (Kojima et al., 2024).1 In thiscase, if the policy intervention leads to a violation of GS, our results immediately
imply that SP cannot be satisfied (even if the existence of competitive equilibria canbe guaranteed). Therefore, if the CE and SP mechanism is desirable for policymakers,a policy must be designed so that a valuation of each firm satisfies GS.
The unique properties of the matching model with continuous transfers and quasilinear utility are the key to our result. The proof consists of two steps. First, weshow that the existence of worker-optimal competitive equilibria is necessary for the
existence of CE and SP mechanisms (Proposition 1). The rural hospital theorem,
which holds without any assumptions in our model (Jagadeesan et al., 2020), plays
an important role in proving this. We then use the characterization of GS by local
properties (Reijnierse et al., 2002), which is based on M ♮ -concavity, a concept fromdiscrete convex analysis (Murota and Shioura, 1999).
We examine the other two models—the one with non-quasilinear utility and theone with discrete transfers. We illustrate that GS is not necessary in either model.
In a model with continuous transfers and non-quasilinear utility, the rural hospitaltheorem may not hold. In a model with discrete transfers, the equivalence between
the existence of worker-optimal competitive equilibria and that of the CE and SP
mechanisms may not hold. Thus, we cannot extend our proof to these models. We
illustrate that a CE and SP mechanism exists even if GS is violated. These findings
highlight how continuous transfers and quasilinear utility produce clear results.

1.1

Related literature

Our research is most closely related to the works of Hatfield et al. (2018) and Jagadeesan et al. (2018). Hatfield et al. (2018) showed that in our setting, GS is a sufficient condition for the existence CE and SP mechanisms. This generalizes a resultin the one-to-one matching model provided by Demange (1982) and Leonard (1983).
Jagadeesan et al. (2018) provided an alternative proof using the rural hospital theo1

Kojima et al. (2024) provide a necessary and sufficient condition for a policy to preserve GS.

3rem, which also plays an important role in our results. These studies demonstrated
the sufficiency of GS. We show the necessity: If a CE and SP mechanism exists, theneach firm’s valuation must satisfy GS.
There has been considerable research on the sufficient conditions for the existenceof competitive equilibria. The classical condition was GS introduced by Kelso andCrawford (1982), and later generalized to GSC by Sun and Yang (2006). Teytelboym(2014) further generalized GSC. Hatfield et al. (2013) generalized GSC in the trading networks model, including our model. Recently, Baldwin and Klemperer (2019)
substantially generalized these conditions by introducing the concept of unimodular
demand types.2 Furthermore, Shinozaki and Serizawa (2024) introduced a condition
that is not a special case of the one Baldwin and Klemperer (2019) proposed. This
series of studies has revealed that various conditions other than GS can ensure theexistence of CE mechanisms. Our contribution is to show that if SP is also required,
GS is the only condition.
CE and SP mechanisms have also been investigated in the model with continuoustransfers and non-quasilinear utility. Demange and Gale (1985) proved the existenceof CE and SP mechanisms in the one-to-one matching model.3 Fleiner et al. (2019)studied the trading networks model with frictions and showed the existence of competitive equilibria under full substitutability.4 Schlegel (2022) studied a CE and SP
mechanism in this model. His result implies that GS and the additional conditions
together guarantee the existence of CE and SP mechanisms in the many-to-one matching model. However, in contrast to the result in the model with the quasilinear utility,
GS is not necessary in this model. We discuss this point in more detail in Section 5.
The other issues were also studied in our model. The first is workers’ investments.
Hatfield et al. (2018) showed the close connection between SP and socially efficientinvestment. In our model, their result implies that for any CE mechanism, it induces
socially efficient investment by workers if and only if it is SP. Thus, we find throughour results that GS is the necessary and sufficient condition for the existence of CE
mechanisms to induce efficient investments by workers (Corollary 3). The second2

Danilov et al. (2001) provided a mathematically similar sufficient condition.
Worker-optimal competitive equilibrium mechanisms can be characterized by desirable properties, including SP (see, e.g., (Miyake, 1998; Morimoto and Serizawa, 2015; Zhou and Serizawa, 2018;
Kazumura et al., 2020)).
4Baldwin et al. (2023) and Nguyen and Vohra (2022) provided general conditions in a model ofexchange economies with indivisible goods.
34

is policy intervention. Kojima et al. (2024) characterized policy interventions that
preserve GS. While they focused on the existence of competitive equilibria, our results
can add insights into CE and SP mechanisms (see Section 4.1).
The model of matching with contracts proposed by Hatfield and Milgrom (2005)
is closely related to our model. In this model, substitutability and stable matchings
are the counterparts of GS and competitive equilibria, respectively. They showedthat substitutability is not a sufficient condition for the existence of stable and SP
mechanisms. Moreover, they showed that an additional condition called the law of
aggregate demand, together with substitutability, guarantees the existence of stable
and SP mechanisms. Furthermore, it is known that each of the two conditions is nota necessary condition (see, e.g., (Hatfield and Kojima, 2010; Kominers and Sönmez,
2016)). Hirata and Kasuya (2017) studied stable and SP mechanisms without assuming any conditions on firms’ preferences, such as substitutability. They showed that
if a worker-optimal stable matching always exists, then a stable and SP mechanism
must select it.5 However, they also demonstrated that the existence of worker-optimal
stable matchings is neither a necessary nor a sufficient condition for the existence ofstable and SP mechanisms. In contrast, optimality for workers is both necessary andsufficient in our model. Compared to this series of studies, the model with continuoustransfers and quasilinear utility gives surprisingly clear results.
The remainder of the paper is organized as follows. Section 2 introduces the modeland concepts. Section 3 presents our main results and proofs. Section 4 presents
applications of Theorem 1. Section 5 investigates other models.

2

Preliminaries

2.1

Model

Let F and W be the sets of firms and workers, respectively. Each worker is matchedwith a firm or remains unmatched, and receives some amount of money. Given w ∈ W ,a typical consumption bundle is a pair (f, sw ) ∈ F × R. Each firm is matched with aset of workers or remains unmatched, and pays some amount of money. Given f ∈ F ,5

Hatfield and Kojima (2010) introduced unilateral substitutability, which is weaker than substitutability, and showed that it is sufficient to guarantee the existence of worker-optimal stablematchings. Kasuya (2021) showed that unilateral substitutability is necessary in the maximal domain sense.

5

a typical consumption bundle is a pair (W ′ , sf ) ∈ 2W × R.
Each worker w ∈ W has a valuation over firms, vw : F → R, normalized sothat vw (∅) = 0. The set of possible valuations for worker w is Vw ≡ RF . We let
V ≡ Πw∈W Vw be the set of possible (worker) valuation profiles. The valuation vw
induces a quasilinear utility function uw (·|vw ) : F × R → R,
uw (f, s|vw ) = vw (f ) + s.
The utility function uw (·|vw ) of worker w ∈ W induces a demand correspondence
as follows. For each price vector p ∈ RF ×W ,Dw (p|vw ) = {f ∈ F | uw (f, p(f,w) |vw ) ≥ uw (f ′ , p(f ′ ,w) |vw ) for all f ′ ∈ F }where p(∅,w) ≡ 0.
Each firm f ∈ F has a valuation over sets of workers, vf : 2W → R, normalized sothat vf (∅) = 0. The valuation vf induces a quasilinear utility function uf : 2W × R →R,
uf (W ′ , s) = vf (W ′ ) − s.
We fix the valuation vf throughout this paper and use uf (·) instead of uf (·|vf ). The
utility function uf of firm f ∈ F induces a demand correspondence as follows. For
each price vector p ∈ RF ×W ,Df (p) = {W ′ ∈ 2W | uf (W ′ , p(f,W ′ ) ) ≥ uf (W ′′ , p(f,W ′′ ) ) for all W ′′ ⊆ W }P
where p(f,W ′ ) ≡ w∈W ′ p(f,w) for all W ′ ̸= ∅ and p(f,W ′ ) ≡ 0 for W ′ = ∅.
For any µ ⊆ F × W , we denote µw = {f ′ ∈ F | (f ′ , w) ∈ µ} and µf = {w′ ∈ W |(f, w′ ) ∈ µ} for each w ∈ W and f ∈ F . We say that µ ⊆ F × W is a (many-to-one)matching if |µw | ≤ 1 for all w ∈ W . With abuse of notation, we denote µw = f when
µw = {f } for some f ∈ F given a matching µ. Let M denote the set of all matching.
For each f ∈ F , w ∈ W , and p(f,w) ∈ R, (f, w, p(f,w) ) is called a contract. A setof contracts A is called an outcome when each worker has at most one contract in A.
For each outcome A and w ∈ W , let Aw = {(f, w, p(f,w) )|(f, w, p(f,w) ) ∈ A} be the setof contracts in A involving w. The utility function of a worker uw naturally extend
to outcome as uw (A|vw ) = vw (f ) + p(f,w) if Aw = {(f, w, p(f,w) )} and uw (A|vw ) = 0
if Aw = ∅. A pair (µ, p) ∈ 2F ×W × RF ×W is called an arrangement when µ is a6matching. The utility function of a worker uw also naturally extend to arrangement
as uw ((µ, p)|vw ) ≡ vw (µw ) + p(µw ,w) .
An arrangement (µ, p) is a competitive equilibrium at v ∈ V if µw ∈ Dw (p|vw )for all w ∈ W and µf ∈ Df (p) for all f ∈ F . A price vector p ∈ RF ×W is acompetitive equilibrium price vector at v ∈ V if (µ, p) is a competitive equilibrium
at v ∈ V for some matching µ. A matching µ is a competitive equilibrium matchingat v ∈ V if (µ, p) is competitive equilibrium at v ∈ V for some p ∈ RF ×W . A
competitive equilibrium (µ, p) at v ∈ V is a worker-optimal competitive equilibrium
at v ∈ V if uw ((µ, p)|vw ) ≥ uw ((µ′ , p′ )|vw ) for all w ∈ W and competitive equilibrium(µ′ , p′ ) at v ∈ V . For a (worker-optimal) competitive equilibrium (µ, p) at v ∈V , {(f, w, p(f,w) ) | (f, w) ∈ µ} is called a (worker-optimal) competitive equilibriumoutcome at v ∈ V . A matching µ is efficient at v ∈ V if µ maximizes the totalPP
surplus: i.e., µ ∈ arg maxµ′ ∈M w∈W vw (µ′w ) + f ∈F vf (µ′f ). It is known that any
competitive equilibrium matching is efficient.
.

2.2

Mechanism

A mechanism is defined as a function φ that specifies an outcome φ(v) for eachvaluation profile v ∈ V . A mechanism φ is a competitive equilibrium selection (CE)if for all v ∈ V , φ(v) is a competitive equilibrium outcome at v. A CE mechanism φ
is worker-optimal if for all v ∈ V , φ(v) is a worker-optimal competitive equilibriumoutcome at v.
Now, we introduce the property of a mechanism that is central to our analysis.
Definition 1. A mechanism φ is strategy-proof for workers (SP) if for all v ∈ V ,w ∈ W , and vw′ ∈ Vw , we haveuw (φ(v)|vw ) ≥ uw (φ(vw′ , v−w )|vw ),where v−w = vW \{w} ∈ VW \{w} .
SP states that reporting the true valuation vw is a weakly dominant strategy for
any worker w under φ.

7

2.3

Gross substitutes

Kelso and Crawford (1982) introduced the gross substitutes condition. Intuitively,
this excludes the complementarity among workers in a firm’s valuation.
Definition 2. A firm f ’s valuation vf satisfies the gross substitutes condition (GS) if
for any two price vectors p, p′ with p ≤ p′ and W ′ ∈ Df (p), there exists W ′′ ∈ Df (p′ )such that {w ∈ W ′ : p(f,w) = p′(f,w) } ⊆ W ′′ .
GS states that if a firm f demands a set of workers (contained in a demand set) at
a given price vector, then even if the salaries of other workers increase, f will continue
to demand that set.

3

Results

3.1

Optimality of CE and SP

To prove our main result, we first show that a worker-optimal competitive equilibrium
is a key to the existence of CE and SP mechanisms. Jagadeesan et al. (2018) showedthat if a worker-optimal competitive equilibrium exists for any valuation profile, thena CE and SP mechanism exists. We show the converse: The existence of the workeroptimal competitive equilibria is necessary for that of CE and SP mechanisms.
The rural hospital theorem is crucial for our necessity. This theorem states that
if a worker receives strictly positive utility in some competitive equilibrium, then she
is matched in every competitive equilibrium matching. Equivalently, if a worker isunmatched in some competitive equilibrium matching, then she receives zero utility,
which is the same as being unmatched, in every competitive equilibrium.
Lemma 1 ((Jagadeesan et al., 2020)). For any valuation profile v, competitive equilibria (µ, p) and (µ′ , p′ ) at v, and worker w, uw ((µ, p)|vw ) > 0 implies µ′w ̸= ∅.
It is worth noting that the rural hospital theorem holds in our model without any
assumption about firms’ valuations. This contrasts with the other models, such as
the one with non-quasilinear utility. In fact, optimality is not necessary in this model.
We will discuss this point more in detail in Section 5.
Proposition 1. If a CE and SP mechanism exists, then a worker-optimal competitive
equilibrium exists for all valuation profile v ∈ V .
8

Proof. Suppose not: i.e., a CE and SP mechanism φ exists, and a worker-optimalcompetitive equilibrium does not exist for some valuation profile v. Let B = φ(v).
Then, there exist a competitive equilibrium outcome A and a worker w ∈ W suchthat uw (A|vw ) > uw (B|vw ). Let (µ, p) and (µ′ , p′ ) be competitive equilibria for A
and B, respectively. We let ϵ be such that uw (A|vw ) > ϵ > uw (B|vw ). Consider
a valuation ṽw with ṽw (f ) = vw (f ) − ϵ for all f ∈ F . We show that (µ, p) is acompetitive equilibrium at ṽ = (ṽw , v−w ). By the construction of ṽ, we have ṽŵ = vŵ
for any ŵ ∈ W with ŵ ̸= w. This implies µŵ ∈ Dŵ (p|ṽŵ ) for any ŵ ∈ W with ŵ ̸= w.
Since vf is fixed for all f ∈ F , we have µf ∈ Df (p). For all f ∈ F , µw ∈ Dw (p|vw )implies uw (µw , p(µw ,w) |vw ) ≥ uw (f, p(f,w) |vw ), which implies uw (µw , p(µw ,w) |vw ) − ϵ ≥uw (f, p(f,w) |vw ) − ϵ. Thus, we have uw (µw , p(µw ,w) |ṽw ) ≥ uw (f, p(f,w) |ṽw ) for all f ∈ F .
Note uw (A|vw )−ϵ > 0, which implies uw (µw , p(µw ,w) |ṽw ) > uw (∅, p(∅,w) |ṽw ) = 0. These
facts together imply µw ∈ Dw (p|ṽw ).
Note uw (A|ṽw ) = uw (A|vw ) − ϵ > 0 by the construction of ϵ. Since (µ, p) is acompetitive equilibrium at (ṽw , v−w ), w is matched with some firm at any competitive equilibrium matching at (ṽw , v−w ) by Lemma 1. Since φ is CE, φ(ṽw , v−w ) is acompetitive equilibrium outcome for some competitive equilibrium (µ̂, p̂) at (ṽw , v−w ).
Then, we haveuw (φ(ṽw , v−w )|ṽw ) = ṽw (µ̂w ) + p̂(µ̂w ,w)= vw (µ̂w ) − ϵ + p̂(µ̂w ,w)= uw (φ(ṽw , v−w )|vw ) − ϵ≥ 0,where the second equality follows from µ̂w ̸= ∅, and the fourth inequality follows fromuw (φ(ṽw , v−w )|ṽw ) ≥ 0 by the definition of CE. Thus, we have uw (φ(ṽw , v−w )|vw ) ≥ ϵ.
By the construction of ϵ, we have uw (φ(ṽw , v−w )|vw ) > uw (B|vw ) = uw (φ(v)|vw ). This
contradicts that φ is SP.
Together with the sufficiency by Jagadeesan et al. (2018), we can characterize the
CE and SP mechanisms using the optimality of competitive equilibrium.
Corollary 1. A CE and SP mechanism exists if and only if a worker-optimal competitive equilibrium exists for all valuation profile v ∈ V .

9

3.2

Necessity for CE and SP: Gross substitutes

Now we provide our main result.
Theorem 1. If a CE and SP mechanism exists, then a valuation vf satisfies GS for
any f ∈ F .
Together with the sufficiency by Hatfield et al. (2018), we find that GS is theunique condition for the existence of CE and SP mechanisms.
Corollary 2. A CE and SP mechanism exists if and only if a valuation vf satisfies
GS for any f ∈ F .
Several points related to Theorem 1 should be mentioned. First, our result is usefulfor checking the existence of CE and SP mechanisms. Specifically, our necessity statesthat if at least one firm’s valuation violates GS, then a CE and SP mechanism does
not exist, regardless of other firms’ valuations. Note that our necessity differs fromthe usual maximal domain. A condition is a maximal domain for desired mechanisms
if, for any violation of this condition by a firm, there always exist valuations of otherfirms that satisfy the condition such that there are no desired mechanisms at the
profile. GS is known to be a maximal domain for the existence of CE mechanisms (Guland Stacchetti, 1999). Our necessity is useful for checking the existence of desired
mechanisms for a given firm valuation profile. Consider a firm valuation profile wherea valuation of some firm violates GS. Since GS is the maximal domain for the existenceof competitive equilibria, we cannot determine whether a CE mechanism exists forthis profile. However, we can immediately determine from Theorem 1 that a CE andSP mechanism does not exist. We will illustrate this point in Section 4.1.
Second, our result also has implications for efficient investment. Agents typicallymake certain choices before participating in mechanisms. For example, workers invest
considerable time and effort in acquiring skills prior to job matching. This investment
can have a significant impact on individual and social welfare. Hatfield et al. (2018)
showed the strong link between SP and socially efficient investment. Together with
their result and ours, we show that GS is the necessary and sufficient condition for CE
mechanisms to induce socially efficient investment by workers. This point is discussed
in more detail in Section 4.2.
Third, our result has implications for policy design. A government often imposesa tax or subsidy on a firm (Kojima et al., 2024). In this case, if the policy intervention
10

leads to a violation of GS, Theorem 1 immediately implies that SP cannot be satisfied(even if the existence of competitive equilibria can be guaranteed). Therefore, if the
CE and SP mechanism is desirable for policymakers, a policy must be designed sothat a valuation of each firm satisfies GS. Furthermore, Kojima et al. (2024) characterized policy interventions that preserve GS. While they focused on the existenceof competitive equilibria, our results can add insights into CE and SP mechanisms.
Example 3 in Section 4.1 illustrates this point.
Finally, we provide a variant of Theorem 1. The proof of Theorem 1 exploits thefact that a worker can have a positive valuation for firms. Therefore, we allow for the
possibility of negative salaries in a competitive equilibrium. This may seem unnaturalin the context of worker-firm matching. Theorem 1 still holds even if we restrict thevaluation of each worker to be non-positive by assuming that vf is non-decreasingfor each f ∈ F .6 Furthermore, in this case, salaries will be non-negative at every
competitive equilibrium. We provide an example (Example 6) as an application ofthis result in Section 4.1.
Proposition 2. Suppose that Vw = RF≤0 for any w ∈ W and vf is non-decreasing for
any f ∈ F .7 If a CE and SP mechanism exists, then a valuation vf satisfies GS for
any f ∈ F .

3.3

Proof sketch of Theorem 1

In this section, we provide a proof sketch of Theorem 1. First, we illustrate that two
types of violations of GS lead non-existence of CE and SP mechanisms (Examples 1
and 2). Then, we see that any violation of GS can be attributed to these two types ofviolations. This follows from the characterization of GS by local properties (Reijnierse
et al., 2002).
The first example is the violation of submodularity, which is implied by GS in ourmodel.8 The following example illustrates that the violation of submodularity would
lead to the non-existence of CE and SP mechanisms.
Example 1. Let F = {f } and W = {w1 , w2 }. The valuation profile is given as
A firm’s valuation vf is non-decreasing if vf (W ′ ) ≥ vf (W ′′ ) for any W ′ , W ′′ ⊆ W with W ′′ ⊆ W ′ .
Let R≤0 denote the set of non-positive real numbers.
8
A valuation vf is submodular if for all X, Y ⊆ W , we have vf (X)+vf (Y ) ≥ vf (X∪Y )+vf (X∩Y ).

6

7

11

follows:
vf (∅) = vf ({w1 }) = vf ({w2 }) = 0, vf ({w1 , w2 }) = 1,
vw1 (f ) = vw2 (f ) = 0.
Note that µ with µf = {w1 , w2 } is a unique efficient matching, and thus a competitive
equilibrium matching has to be µ. There are two competitive equilibria (µ, p) and(µ, q) such that p = (p(f,w1 ) , p(f,w2 ) ) = (1, 0) and q = (0, 1). However, any (µ, r)with r(f,w1 ) , r(f,w1 ) ≥ 1 is not a competitive equilibrium since r(f,w1 ) + r(f,w1 ) > 1. Thismeans that a worker-optimal competitive equilibrium does not exist for this valuation
profile. Thus, Proposition 1 implies that there is no CE and SP mechanism in thisexample.
The second example was provided by Kelso and Crawford (1982). While GS
implies submodularity in our model, the converse does not hold. Kelso and Crawford(1982) illustrates this fact using the following example. We show that there is no CE
and SP mechanism in this example.
Example 2. Let F = {f } and W = {w1 , w2 , w3 }. The valuation profile is given as
follows:
vf (∅) = 0, vf ({w1 }) = vf ({w2 }) = 4, vf ({w3 }) = 4.25,
vf ({w1 , w2 }) = 7.5, vf ({w1 , w3 }) = vf ({w2 , w3 }) = 7,
vf ({w1 , w2 , w3 }) = 9,
vw1 (f ) = vw2 (f ) = 0, vw3 (f ) = −3.
While vf is submodular, it violates GS: We have Df (p) = {{w1 , w2 }} for p =(p(f,w1 ) , p(f,w2 ) , p(f,w3 ) ) = (3, 3, 3) and Df (q) = {{w3 }} for q = (3.5, 3, 3). Note that µwith µf = {w1 , w2 } is a unique efficient matching, and thus a competitive equilibrium
matching has to be µ. There are two competitive equilibria (µ, p) and (µ, q) such thatp = (3.5, 2.75, 3) and q = (2.75, 3.5, 3). Consider any (µ, r) with r(f,w1 ) , r(f,w2 ) ≥ 3.5.
If {w1 , w2 } ∈ Df (r), we have r(f,w3 ) ≥ 3.75, which imply Dw3 (r|vw3 ) = {f }. Thus,(µ, r) is not a competitive equilibrium. This means that a worker-optimal competitive
equilibrium does not exist for this valuation profile. Thus, Proposition 1 implies that
there is no CE and SP mechanism in this example.
12

The violation of GS can be attributed to the two types of violations illustratedin Examples 1 and 2. This follows from the characterization of GS by two local
properties (Reijnierse et al., 2002).
Proposition 3 ((Reijnierse et al., 2002)). A firm’s valuation vf satisfies GS if andonly if the following two conditions hold.
Condition 1. For any X ⊆ W , w1 , w2 ∈ W \ X with w1 ̸= w2 ,vf (X ∪ {w1 , w2 }) + vf (X) ≤ vf (X ∪ {w1 }) + vf (X ∪ {w2 }).
Condition 2. For any X ⊆ W , w1 , w2 , w3 ∈ W \ X such that w1 , w2 , and w3 are
distinct,vf (X ∪ {w1 , w2 }) + vf (X ∪ {w3 })≤ max{vf (X ∪ {w1 , w3 }) + vf (X ∪ {w2 }), vf (X ∪ {w2 , w3 }) + vf (X ∪ {w1 })}.
The conditions above are “local” in the sense that they focus only on two sets X, Y
with max(|X \ Y |, |Y \ X|) ≤ 2.9 This characterization is related to M ♮ -concavity,
a concept from discrete convex analysis (Murota and Shioura, 1999). In the modelwith continuous transfers and quasilinear utility, Fujishige and Yang (2003) showedthat GS is equivalent to M ♮ -concavity of a valuation. Proposition 3 utilizes thisequivalence. See Murota (2016) for more details.
Based on Proposition 3, any violations of GS can be classified into that of Conditions 1 or 2. A firm’s valuation vf in Example 1 violates Condition 1. A firm’svaluation vf in Example 2 satisfies Condition 1 but violates Condition 2. The proofof Theorem 1 generalizes the intuition of these examples.

3.4

Proof of Theorem 1

Proof. We begin with a lemma.
9

In general, we need additional conditions on domf = {X : f (X) > −∞} for this result. In
our model, we have domf = 2W , and thus these conditions are always satisfied. The condition
domf = 2W also holds in the models studied by Kelso and Crawford (1982); Gul and Stacchetti(1999); Reijnierse et al. (2002). For general models with domf ̸= 2W , see (Murota, 2016).

13

Lemma 2 ((Jagadeesan et al., 2020)). Let (µ, p) be any competitive equilibrium. For
any competitive equilibrium matching µ′ , (µ′ , p) is a competitive equilibrium.
Suppose toward a contradiction that there exists a firm f such that vf violates
GS. Then either Condition 1 or Condition 2 in Proposition 3 is violated. We haveP
two cases to consider. To simplify notation, define uf (X, p) ≡ vf (X) − w∈X p(f,w)
for each X ⊆ W , and p ∈ RF ×W .
Case 1: vf violates Condition 1.
There exist X ⊆ W and w1 , w2 ∈ W \ X with w1 ̸= w2 such that
vf (X ∪ {w1 , w2 }) + vf (X) > vf (X ∪ {w1 }) + vf (X ∪ {w2 }).
Consider the following worker valuation profile v;
vw (f ) = α for all w ∈ X ∪ {w1 , w2 },vw (f ) < − max 2|vf (Z)| for all w ∈ W \ (X ∪ {w1 , w2 }), andZ∈2W

vw (f ′ ) < − max 2|vf ′ (Z)| for all w ∈ W and f ′ ∈ F \ {f },Z∈2Wwhere α ≡ − minZ⊆Y ⊆X∪{w1 ,w2 } vf (Y ) − vf (Z). Note α ≥ 0.
Consider a matching µ with µf = X ∪ {w1 , w2 } and µf ′ = ∅ for all f ′ ∈ F \ {f }.
We show that there exists a competitive equilibrium (µ, p) such thatp(f,w1 ) = vf (X ∪ {w1 , w2 }) − vf (X ∪ {w2 }),p(f,w2 ) = vf (X ∪ {w2 }) − vf (X),p(f,w) = −α for all w ∈ X,
p(f,w) = −vw (f ) for all w ̸∈ X ∪ {w1 , w2 }, andp(f ′ ,w) = −vw (f ′ ) for all w ∈ W and f ′ ∈ F \ {f }.
By the construction of p, we have f ∈ Dw (p|vw ) for each w ∈ X ∪ {w1 , w2 }. Also, we
have ∅ ∈ Dw (p|vw ) for each w ̸∈ X ∪ {w1 , w2 }. For any f ′ ∈ F \ {f }, w ∈ W \ {w},14and Y ⊆ W , we haveuf ′ (Y, p) − uf ′ (Y ∪ {w}, p)=p(f ′ ,w) − (vf ′ (Y ∪ {w}) − vf ′ (Y ))= max 2|vf ′ (Z)| − (vf ′ (Y ∪ {w}) − vf ′ (Y ))
Z∈2W

≥0.
Thus, we have ∅ ∈ Df ′ (p) for each f ′ ∈ F \ {f }. We show that X ∪ {w1 , w2 } ∈ Df (p).
Note that for all Y with Y ∩ (W \ (X ∪ {w1 , w2 })) ̸= ∅, we have uf ((X ∪ {w1 , w2 }) ∩Y, p) ≥ uf (Y, p). Thus, it suffices to show that for all Y ⊆ X ∪ {w1 , w2 }, we haveuf (X ∪ {w1 , w2 }, p) ≥ uf (Y, p). For all Y ⊆ X ∪ {w1 , w2 } and w ∈ X \ Y , we haveuf (Y ∪ {w}, p) − uf (Y, p)=vf (Y ∪ {w}) − vf (Y ) + α≥0,where the second inequality follows from p(f,w) = −α. This implies uf (X, p) ≥uf (∅, p) = 0 and uf (X ∪ Z, p) ≥ uf (Z, p) for all Z ⊆ W . Thus, it suffices to show
uf (X ∪ {w1 , w2 }, p) ≥ uf (Y, p) for Y ∈ {X, X ∪ {w1 }, X ∪ {w2 }}.
For X,
uf (X ∪ {w1 , w2 }, p)=vf (X ∪ {w1 , w2 })− ((vf (X ∪ {w1 , w2 }) − vf (X ∪ {w2 })) + (vf (X ∪ {w2 }) − vf (X)))
X−
p(f,w)w∈X

X=vf (X) −p(f,w)w∈X=uf (X, p).

15

For X ∪ {w2 },uf (X ∪ {w2 }, p)= vf (X ∪ {w2 }) − ((vf (X ∪ {w2 }) − vf (X)) −X

p(f,w) )w∈X= vf (X) −X

p(f,w)w∈X= uf (X, p)= uf (X ∪ {w1 , w2 }, p).
For X ∪ {w1 },uf (X ∪ {w1 }, p)= vf (X ∪ {w1 }) − (vf (X ∪ {w1 , w2 } − vf (X ∪ {w2 })) −X

p(f,w)w∈X< vf (X) −X

p(f,w)w∈X= uf (X, p)= uf (X ∪ {w1 , w2 }, p),
where the second inequality follows from the assumption of Case 1.
Similarly, we can show that there exists a competitive equilibrium (µ, q) such thatq(f,w1 ) = vf (X ∪ {w1 }) − vf (X),q(f,w2 ) = vf (X ∪ {w1 , w2 }) − vf (X ∪ {w1 }),q(f,w) = −α for all w ∈ X,
q(f,w) = −vw (f ) for all w ̸∈ X ∪ {w1 , w2 }, andq(f ′ ,w) = −vw (f ′ ) for all w ∈ W and f ′ ∈ F \ {f }.
Suppose that there exists a worker-optimal competitive equilibrium (µ′ , r). By Lemma 2,(µ, r) is also a competitive equilibrium. Note uw ((µ′ , r)|vw ) = uw ((µ, r)|vw ) for
any w ∈ W . Since (µ′ , r) is a worker-optimal competitive equilibrium, we have16

r(f,w1 ) ≥ p(f,w1 ) and r(f,w2 ) ≥ q(f,w2 ) . However, we have X ∪ {w1 , w2 } ̸∈ Df (r) sinceuf (X ∪ {w1 , w2 }, r)=vf (X ∪ {w1 , w2 })− ((vf (X ∪ {w1 , w2 }) − vf (X ∪ {w2 })) + (vf (X ∪ {w1 , w2 }) − vf (X ∪ {w1 }))X−
r(f,w)w∈X<vf (X) −X

r(f,w)w∈X=uf (X, r),where the second inequality follows from the assumption of Case 1. This contradicts
that (µ, r) is a competitive equilibrium. Thus, a worker-optimal competitive equilibrium does not exist for this valuation profile v. By Proposition 1, there is no CE andSP mechanism in this case.
Case 2: While vf satisfies Condition 1, vf violates Condition 2.
There exist X ⊆ W and w1 , w2 , w3 ∈ W \ X such that w1 , w2 , and w3 are distinct,
andvf (X ∪ {w1 , w2 }) + vf (X ∪ {w3 })> max{vf (X ∪ {w1 , w3 }) + vf (X ∪ {w2 }), vf (X ∪ {w2 , w3 }) + vf (X ∪ {w1 })}.
Consider the following worker valuation profile v;
vw (f ) = β for all w ∈ X ∪ {w1 , w2 },vw3 (f )= − max{vf (X ∪ {w1 , w3 }) − vf (X ∪ {w1 }), vf (X ∪ {w2 , w3 }) − vf (X ∪ {w2 })},
vw (f ) < − max 2|vf (Z)| for all w ∈ W \ (X ∪ {w1 , w2 , w3 }), andZ∈2W

vw (f ′ ) < − max 2|vf ′ (Z)| for all w ∈ W and f ′ ∈ F \ {f },Z∈2Wwhere β ≡ − minZ⊆Y ⊆X∪{w1 ,w2 ,w3 } vf (Y ) − vf (Z). Note β ≥ 0.
Consider a matching µ with µf = X ∪ {w1 , w2 } and µf ′ = ∅ for all f ′ ∈ F \ {f }17We show that there exists a competitive equilibrium (µ, p) such thatp(f,w1 ) = vf (X ∪ {w1 , w2 }) − vf (X ∪ {w2 }),p(f,w2 ) = vf (X ∪ {w2 , w3 }) − vf (X ∪ {w3 }),p(f,w3 ) = vf (X ∪ {w2 , w3 }) − vf (X ∪ {w2 }),p(f,w) = −β for all w ∈ X,
p(f,w) = −vw (f ) for all w ̸∈ X ∪ {w1 , w2 , w3 }, andp(f ′ ,w) = −vw (f ′ ) for all w ∈ W and f ′ ∈ F \ {f }.
Note f ∈ Dw (p|vw ) for each w ∈ X ∪ {w1 , w2 }, ∅ ∈ Dw (p|vw ) for each w ̸∈ X ∪{w1 , w2 }, and ∅ ∈ Df ′ (p) for each f ′ ∈ F \ {f }. We show that X ∪ {w1 , w2 } ∈ Df (p).
By p(f,w) = −β for all w ∈ X, a similar argument in Case 1 implies that it suffices toshow that uf (X ∪ {w1 , w2 }, p) ≥ uf (Y, p) forY ∈ {X, X ∪ {w1 }, X ∪ {w2 }, X ∪ {w3 }, X ∪ {w2 , w3 }, X ∪ {w1 , w3 }, X ∪ {w1 , w2 , w3 }}.
For X ∪ {w1 , w2 , w3 },uf (X ∪ {w1 , w2 }, p) − uf (X ∪ {w1 , w2 , w3 }, p)= (vf (X ∪ {w2 , w3 }) − vf (X ∪ {w2 })) − (vf (X ∪ {w1 , w2 , w3 }) − vf (X ∪ {w1 , w2 }))≥ 0,
where the second inequality follows from that vf satisfies Condition 1.
For X ∪ {w2 },uf (X ∪ {w1 , w2 }, p) − uf (X ∪ {w2 }, p) = 0
by the definition of p(w1 ,f ) .
For X ∪ {w1 },uf (X ∪ {w1 , w2 }, p) − uf (X ∪ {w1 }, p)= (vf (X ∪ {w1 , w2 }) − vf (X ∪ {w1 })) − (vf (X ∪ {w2 , w3 }) − vf (X ∪ {w3 }))
> 0,

18

where the second inequality follows from the assumption of Case 2.
For X ∪ {w3 },uf (X ∪ {w1 , w2 }, p) − uf (X ∪ {w3 }, p) = 0
since uf (X ∪ {w3 }, p) = uf (X ∪ {w2 }, p).
For X ∪ {w2 , w3 },uf (X ∪ {w1 , w2 }, p) − uf (X ∪ {w2 , w3 }, p) = 0
since uf (X ∪ {w2 , w3 }, p) = uf (X ∪ {w2 }, p).
For X ∪ {w1 , w3 },uf (X ∪ {w1 , w2 }, p) − uf (X ∪ {w1 , w3 }, p)= vf (X ∪ {w1 , w2 }) − (vf (X ∪ {w2 , w3 }) − vf (X ∪ {w3 }))− (vf (X ∪ {w1 , w3 }) − (vf (X ∪ {w2 , w3 }) − vf (X ∪ {w2 })))
= vf (X ∪ {w1 , w2 }) + vf (X ∪ {w3 }) − (vf (X ∪ {w1 , w3 }) + vf (X ∪ {w2 }))> 0,
where the last inequality follows from the assumption of Case 2.
For X,
uf (X ∪ {w1 , w2 }, p) − uf (X, p)= (vf (X ∪ {w1 , w2 }) − vf (X))
− (vf (X ∪ {w1 , w2 }) − vf (X ∪ {w2 })) − (vf (X ∪ {w2 , w3 }) − vf (X ∪ {w3 }))= (vf (X ∪ {w2 }) − vf (X)) − (vf (X ∪ {w2 , w3 }) − vf (X ∪ {w3 }))≥ 0,
where the second inequality follows from that vf satisfies Condition 1.

19

Similarly, we can show that there exists a competitive equilibrium (µ, q) such thatq(f,w1 ) = vf (X ∪ {w1 , w3 }) − vf (X ∪ {w3 }),q(f,w2 ) = vf (X ∪ {w1 , w2 }) − vf (X ∪ {w1 }),q(f,w3 ) = vf (X ∪ {w1 , w3 }) − vf (X ∪ {w1 }),q(f,w) = −β for all w ∈ X,
q(f,w) = −vw (f ) for all w ̸∈ X ∪ {w1 , w2 , w3 }, andq(f ′ ,w) = −vw (f ′ ) for all w ∈ W and f ′ ∈ F \ {f }.
Note that p(f,w1 ) ≥ q(f,w1 ) and q(f,w2 ) ≥ p(f,w2 ) by the assumption of Case 2. Suppose that there exists a worker-optimal competitive equilibrium (µ′ , r). By Lemma 2,(µ, r) is also a competitive equilibrium. Note uw ((µ′ , r)|vw ) = uw ((µ, r)|vw ) for
any w ∈ W . Since (µ′ , r) is a worker-optimal competitive equilibrium, we haver(f,w1 ) ≥ p(f,w1 ) and r(f,w2 ) ≥ q(f,w2 ) . Note that µf = X ∪ {w1 , w2 } ∈ Df (r) must holdsince this is necessary so that (µ, r) is a competitive equilibrium. Then, we haveuf (X ∪ {w1 , w2 }, r) ≥ uf (X ∪ {w3 }, r).
This implies
vf (X ∪ {w1 , w2 }) − ((vf (X ∪ {w1 , w2 }) − vf (X ∪ {w2 }))X
r(f,w)− (vf (X ∪ {w1 , w2 }) − vf (X ∪ {w1 })) −w∈X≥ vf (X ∪ {w1 , w2 }) −X

r(f,w)w∈X∪{w1 ,w2 }≥ vf (X ∪ {w3 }) − r(f,w3 ) −X

r(f,w) ,w∈X

where the first inequality follows from r(f,w1 ) ≥ p(f,w1 ) and r(f,w2 ) ≥ q(f,w2 ) . Thus, we

20

have
r(f,w3 )≥ (vf (X ∪ {w1 , w2 }) + vf (X ∪ {w3 })) − (vf (X ∪ {w1 }) + vf (X ∪ {w2 }))> max{vf (X ∪ {w1 , w3 }) + vf (X ∪ {w2 }), vf (X ∪ {w2 , w3 }) + vf (X ∪ {w1 })}− (vf (X ∪ {w1 }) + vf (X ∪ {w2 }))= max{vf (X ∪ {w1 , w3 }) − vf (X ∪ {w1 }), vf (X ∪ {w2 , w3 }) − vf (X ∪ {w2 })},
where the second inequality follows from the assumption of Case 2. Thus, we have
Dw3 (r|vw3 ) = {f }, which contradicts that (µ, r) is a competitive equilibrium. Thismeans that a worker-optimal competitive equilibrium does not exist for this valuation
profile v. By Proposition 1, there is no CE and SP mechanism in this case.

Proof of Proposition 2
The proof of Theorem 1 can be applied to Proposition 2 with small modifications.
First, we assume vf is non-decreasing in Proposition 2, which implies α, β = 0 and− max{vf (X ∪ {w1 , w3 }) − vf (X ∪ {w1 }), vf (X ∪ {w2 , w3 }) − vf (X ∪ {w2 })} ≤ 0.
Thus, all valuations of workers in the proof become non-positive. Second, it is easy
to see that Proposition 1 holds when Vw = RF≤0 for any w ∈ W .

4

Applications

4.1

Checking CE and SP

In this section, we illustrate that our results can determine the existence of the desired
mechanisms. In each example, CE mechanisms exist. However, some valuations
violate GS. Therefore, our results show that there is no CE and SP mechanism.
Case of single firmFirst, we consider the case where there is a single firm in a market. While thiscase is very simple, it is theoretically valuable because it guarantees the existence21

of competitive equilibria regardless of the firm’s valuation. Moreover, it also haspractical relevance. Policies such as subsidies to a particular group in auctions canbe discussed.
Proposition 4. Suppose F = {f }. Then, a competitive equilibrium exists for anyv ∈ V and vf ∈ Vf .
Proof. For each worker valuation profile v ∈ V , consider
W ′ ∈ arg max(vf (W ′ ) +W ′ ⊆WX

vw (f )).

w∈W ′Then, (µ, p) is a competitive equilibrium at ν where µf = W ′ and p(f,w) = −vw (f )for each w ∈ W .
It is worth noting that Proposition 4 does not follow from the existence theorem
by Baldwin and Klemperer (2019). While a firm’s valuation violates GS in Examples
1 and 2, CE mechanisms exist in the case of a single firm by Proposition 4. However,there is no CE and SP mechanism in these examples by Theorem 1.
The case of a single firm includes some important applications. Consider thesetting of an auction where a single seller (firm) has multiple and homogeneous items
and sells them to unit-demand buyers (workers). Suppose that the seller only cares
about revenue, and her reservation values are zero. Thus, vf (W ′ ) = 0 for all W ′ ⊆ W .
It is easy to see that vf satisfies GS, and the CE and SP mechanism exists.
In practice, to address equity issues, governments often provide support for small
businesses and certain targeted groups in government procurement and allocation
programs (Athey et al., 2013). Here, we consider a policy in which a government
offers financial incentives to the seller based on the number of minority buyers who
can obtain the items. A policy intervention is represented by a function tf : 2W → R.
Example 3. Let Wm ⊆ W be the set of minority buyers. A policy intervention tf isdefined as:α if |W ′ ∩ W | ≥ a,m′tf (W ) =
0 otherwise,
where α > 0 and 1 ≤ a ≤ |Wm |.
22

vf1
vf2
vf2

∅
0
0
0

{wd } {wn1 } {wn2 } {wd , wn1 }
18
3
3
22
1
11
11
13
12
6
6
20

{wd , wn2 } {wn1 , wn2 } W
22
4 24
13
20 23
20
10 25

Table 1: Firms’ valuations in Example 4
It is easy to see that vf +tf violates GS. Therefore, tf leads to the non-existence ofCE and SP mechanisms by Theorem 1, even though a competitive equilibrium exists
in the case of the single seller. This observation leads to a natural question: Whatkind of policy intervention tf can preserve GS? Kojima et al. (2024) showed that if tf
is represented by sums of additively separable and cardinally concave functions, then
GS can be preserved (for all valuations satisfying it).
Case of multiple firms
Second, we consider the case where there are multiple firms in a market. In thiscase, various conditions other than GS can guarantee the existence of competitive
equilibria.
Example 4. Suppose that there are three firms F = {f1 , f2 , f3 }, one doctor and twonurses W = {wd , wn1 , wn2 }. Firms’ valuations are given in Table 1. Sun and Yang
(2006) provided this example. Intuitively, from the viewpoint of each firm, nurses
are substitutes, but a doctor and nurses are complements. They showed that GSC
guarantees the existence of competitive equilibria, and every firm’s valuation violate
GS but satisfies GSC in Example 4.10 Thus, a CE mechanism exists, but a CE andSP mechanism does not exist by Theorem 1 in this example.
Example 5. Suppose that there are two firms F = {f1 , f2 } and three workers W ={w1 , w2 , w3 }. Each firm has a valuation defined byα if {w , w } ⊆ W ′ ,12′
vf1 (W ) =0 otherwise,

vf2 (W ′ ) =10β if {w , w } ⊆ W ′ ,23

0 otherwise,

The model by Sun and Yang (2006) is a little different from ours. In our model, workers areagents, while in their model they are treated as items. Precisely, the existence of a competitive
equilibria under GSC in our model follows from the result by Hatfield et al. (2013).

23

for each W ′ ⊆ W where α, β > 0. Note that each firm’s valuation satisfies neither
GS nor GSC. Nevertheless, it can be confirmed that the demand type induced fromvaluations of firms and workers is unimodular defined by Baldwin and Klemperer(2019). Thus, their existence theorem implies that a competitive equilibrium exists
for any valuation profile of workers. However, Theorem 1 implies that a CE and SP
mechanism does not exist in this example.
Example 6. Consider a situation where the set of workers is partitioned, and for eachfirm, a set of workers is valuable only when the set is in the partition.11 Formally, let
W = {W1 , . . . , Wn } be a partition of W and suppose that each f ∈ F has a valuation
vf such that for each W ′ ∈ 2W ,′vf (W )


> 0

if W ′ ∈ W,

= maxW ′′ ∈W∪{∅},W ′′ ⊆W ′ vf (W′′) otherwise.

Note that for each f , vf is non-decreasing. Assume that each worker has a nonpositive valuation, that is, Vw = RF≤0 for each w ∈ W . Then, there is a competitive
equilibrium for each v ∈ V .
The existence of a competitive equilibrium can be shown by constructing a oneto-one matching economy.12 Let v ∈ V . Let W ∗ be the set of n workers such thateach worker i ∈ W ∗ corresponds to a set Wi of workers in W. For each i ∈ W ∗ , letPvi∗ = w∈Wi vw . Each firm f ∈ F has a valuation vf∗ over W ∗ such that for eachi ∈ W ∗ , vf∗ (i) = vf (Wi ).
For this one-to-one economy, it is known that there is a competitive equilibrium(µ∗ , p∗ ) at v ∗ . Note that p∗ ≥ 0 since firms’ valuations are non-negative and nondecreasing and workers’ valuations are non-positive. Given this equilibrium, let µ bea matching in the original economy such that for each f ∈ F , µf = Wµ∗f . Let p be a11This example is inspired by Shinozaki and Serizawa (2024). They study an auction model withmulti-demand agents, and show that if a mechanism satisfies SP, envy-freeness and other conditions,the set of objects is partitioned into multiple bundles and the mechanism selects a competitive
equilibrium allocation with respect to the bundles. The main difference between their result and our
example is that a partition is endogenously determined in their result while the partition is given
exogenously in our example.
12
The demand type induced from valuations of firms and workers in this example is not unimodular. Thus, the sufficient condition of Baldwin and Klemperer (2019) cannot be applied to thisexample.

24

price vector such that for each i ∈ W ∗ , each w ∈ Wi and each f ∈ F ,p(f,w) =∗∗−v (f ) + p(µ∗i ,i) +vi (f )w

−v (f ) +|Wi |p∗(µ∗ ,i) +vi∗ (µi )

w

i

|Wi |

if f = µw ,− t(f, w) otherwise,

wheret(f, w) =min{|vw (f )|, λ}−v (f ) −w

if p∗(f,i) − (p∗(µ∗ ,i) + vi∗ (µ∗i )) ≥ 0,p∗(f,i) −(p∗(µ∗ ,i) +vi∗ (µ∗i ))
i
|Wi |

i

if p∗(f,i) − (p∗(µ∗ ,i) + vi∗ (µ∗i )) < 0,
i

P
∗
∗
∗
where λ solves the equationw′ ∈Wi min{|vw′ (f )|, λ} = vi (f ) − (p(f,i) − (p(µ∗i ,i) +vi∗ (µ∗i ))). By the construction of p, for each w ∈ W and f ∈ F , uw (µw , p(µw ,w) | vw ) ≥ 0
and uw (µw , p(µw ,w) | vw ) ≥ uw (f, p(f,w) | vw ). Thus, µf ∈ Dw (p | vw ). Further, by
the definition of firms’ valuations, for each f ∈ F , µf ∈ Df (p). Hence, (µ, p) is acompetitive equilibrium (in the original economy) at v.
It is also true that p ≥ 0. To see this, let i ∈ W ∗ , w ∈ Wi , and f ∈ F . If f = µw
or p∗(f,i) − (p∗(µ∗ ,i) + vi∗ (µ∗i )) ≥ 0, then by p∗(µ∗ ,i) + vi∗ (µ∗i ) ≥ 0, p(f,w) ≥ 0. Supposeiif ̸= µw and p∗(f,i) − (p∗(µ∗ ,i) + vi∗ (µ∗i )) < 0. Then,ip(f,w) = −vw (f ) += −vw (f ) +=p∗(f,i)|Wi |p∗(µ∗ ,i) + vi∗ (µi )
i

|Wi |
∗
p(µ∗ ,i) + vi∗ (µi )
i

|Wi |

− t(f, w)+ vw (f ) +p∗(f,i) − (p∗(µ∗ ,i) + vi∗ (µ∗i ))
i

|Wi |

.

Since p∗(f,i) ≥ 0, p(f,w) ≥ 0. Thus, p ≥ 0.
If there is W ′ ∈ W such that |W ′ | ≥ 2, firms’ valuations violate GS. Thus, in sucha case, there is no CE and SP mechanism by Proposition 2.

4.2

Investment

Agents typically make certain investments before participating in mechanisms. The
design of a mechanism can affect the incentives for workers to invest because it partly
determines the return on their investment. Hatfield et al. (2018) characterized themechanisms that provide incentives for socially efficient ex ante investment in the25general model, including ours. Since their characterization is based on SP, we obtaina close relationship between GS and investment efficiency through our results.
We follow the model of Hatfield et al. (2018). Before participating in the mechanism, each worker makes an investment decision that shapes her valuation acrossfirms. This investment decision is modeled as a choice of the valuation vw . The
cost associated with this investment is defined by a cost function cw : Vw → R.
We slightly abuse notation and write µ(A) to mean that µ(A) is a matching associated with an outcome A. A mechanism φ is efficient if µ(φ(v)) is an efficientmatching at v for any v ∈ V . The ex ante utility of worker w given an outcome–investment pair (A, v) is uw (A|vw ) − cw (vw ) where v ∈ V . The social welfare (or total surplus) of an outcome A at a valuation profile v ∈ V is denoted by
P
P
V(A|v) ≡ w∈W vw (µ(A)w ) + f ∈F vf (µ(A)f ). We define the ex ante social welfarePof an outcome–investment pair (A, v) as V(A|v) − w cw (vw ).
Definition 3. A mechanism φ induces efficient investment by workers if for all w ∈ W
and v−w ∈ VW \{w} ,arg max{uw (φ(vw′ , v−w ) − cw (vw′ )|vw′ )} = arg max{V(φ(vw′ , v−w )|(vw′ , v−w )) − cw (vw′ )}.
′ ∈V
vw
w

′ ∈V
vw
w

A mechanism induces efficient investment for workers if, assuming that workers
report truthfully, for every valuation profile v−w of other workers, and for every costfunction cw , the valuations that maximize the utility of w are exactly those thatmaximize social welfare.
Hatfield et al. (2018) clarified the relationship between SP and inducing efficientinvestment.
Proposition 5 ((Hatfield et al., 2018)). Consider an efficient mechanism φ. The
following statements are equivalent:
1. The mechanism φ induces efficient investment by workers.
2. The mechanism φ is SP.
By noting that CE mechanisms are efficient, together with our results, we cancharacterize the valuations of a firm to guarantee the existence of mechanisms thatare CE and induce efficient investment by workers.
Corollary 3. A mechanism that is CE and induces efficient investment by workers
exists if and only if a valuation vf satisfies GS for any f ∈ F .
26

5

Other models

5.1

Model with non-quasilinear utility

The following example shows that Theorem 1 does not hold in the model with continuous transfers and non-quasilinear utility.
Example 7. Let F = {f } and W = {w1 , w2 }. Firm f has a utility function uf over
2W × R defined by



2−p


uf ({w1 , w2 }, p) = − (1+ϵ)(p − 1)ϵ−p + 1

if p < 1 − ϵif 1 − ϵ ≤ p ≤ 1
if p > 1,

and for i = 1, 2,
uf ({wi }, p) = 1 − p
1where ϵ > 0 is sufficiently small so that 2+ϵ< 1 − ϵ, equivalently, ϵ2 + ϵ < 1. The
utility function induces a demand correspondence Df as in Section 2.1. Then, thegross substitutes condition can be defined for Df in the same way as Definition 2.
Figure 1 illustrates the demand of f . Note that Df violates the gross substitutes
1) = {{w2 }}.
condition since Df (1 − ϵ, 0) = {{w1 , w2 }} and Df (1 − ϵ, 2+ϵWe assume that each worker has a quasilinear utility. Since there is a single firm,
we use vw to represent vw (f ).
We define a mechanism as follows.
∅
if − vw1 , −vw2 > 1,





{(f, w1 , 1)}
if − vw1 ≤ 1, −vw2 > 1,




1
{(f, w , −v )}< −vw2 ≤ 1,
if − vw2 > −vw1 , 2+ϵ1
w2
φ(vw1 , vw2 ) =
1
1
1


{(f, w1 , 2+ϵ), (f, w2 , 2+ϵ)} if − vw1 , −vw2 ≤ 2+ϵ
,




1


if − vw1 ≥ −vw2 , 2+ϵ< −vw1 ≤ 1,
{(f, w2 , −vw1 )}
{(f, w , 1)}
if − v ≥ 1, −v > 1.
2

w2

w1

Note that −vwi is the minimum salary at which wi (i = 1, 2) is willing to match f , i.e.,{f } ∈ Dwi (p) if and only if pwi ≥ −vwi . For (vw1 , vw2 ) ∈ R2 , if −vw1 ≤ 1 and −vw2 >1, then ({(f, w1 )}, (1, −vf2 )) is a competitive equilibrium since {w1 } ∈ Df (1, −vf2 )
27

pw2

{w1}

1

∅

1−ϵ
1
2+ϵ

−ϵ

{w2}

{w1, w2}
1
2+ϵ

−ϵ

1−ϵ

1

pw1

Figure 1: A representation of Df in price space. Each labeled region represents
the set of price vectors in which f demands the set of workers corresponding to
the label. Black lines represent the set of price vectors in which f is indifferent
among more than one set of workers. For example, Df (p) = {{w1 }, {w2 }} for all1
p ∈ {(pw1 , pw2 ) | 2+ϵ< pw1 = pw2 < 1}.
1< −vw2 ≤ 1, then ({(f, w1 )}, (−vw2 , −vw2 ))by Figure 1, and if −vw2 > −vw1 and 2+ϵ
is a competitive equilibrium since {w1 } ∈ Df (−vw2 , −vw2 ) by Figure 1. We can checkthat φ selects a competitive equilibrium outcome for the other cases. Thus, φ is a
CE mechanism.
We show that φ is SP. For each (vw1 , vw2 ) ∈ R2 , let φwi (vw1 , vw2 ) = {(f, w, pw ) ∈φ(vw1 , vw2 ) | w = wi } be the allocation to wi under φ (i = 1, 2). Fix any vw2 ∈ R.
Consider the following three cases.
1. Then,(1) Suppose that −vw2 ≤ 2+ϵ

φw1 (vw′ 1 , vw2 ) =
{(f, w , 1 )}1
if − vw′ 1 ≤ 2+ϵ∅1.
if − vw′ 1 > 2+ϵ

1 2+ϵThis implies that uw1 (φ(vw1 , vw2 )|vw1 ) ≥ uw1 (φ(vw′ 1 , vw2 )|vw1 ) for all vw1 , vw′ 1 ∈
R.

28

1
(2) Suppose that 2+ϵ< −vw2 ≤ 1. Then,{(f, w , −v )}1w2
φw1 (vw′ 1 , vw2 ) =∅

if − vw′ 1 < −vw2
if − vw′ 1 ≥ −vw2 .

This implies that uw1 (φ(vw1 , vw2 )|vw1 ) ≥ uw1 (φ(vw′ 1 , vw2 )|vw1 ) for all vw1 , vw′ 1 ∈R.
(3) Suppose that −vw2 > 1. Then,
φw1 (vw′ 1 , vw2 ) =
{(f, w , 1}

if − vw′ 1 ≤ 1

∅if − vw′ 1 > 1.

1

This implies that uw1 (φ(vw1 , vw2 )|vw1 ) ≥ uw1 (φ(vw′ 1 , vw2 )|vw1 ) for all vw1 , vw′ 1 ∈R.
The above argument shows that reporting truthfully is (weakly) dominant for w1 .
Similarly, reporting truthfully is (weakly) dominant for w2 . Therefore, φ is a CE andSP mechanism while Df violates GS.
This example also illustrates that the rural hospital theorem (Lemma 1) does
not hold in the model with non-quasilinear utility: ({(f, w1 ), (f, w2 )}, (1 − ϵ, 0)) and1({(f, w2 )}, (1 − ϵ − η, 2+ϵ)) are competitive equilibria at (vw1 , vw2 ) = (1 − ϵ − η, 0) withsmall η > 0.

5.2

Model with discrete transfers

Crawford and Knoer (1981) and Kelso and Crawford (1982) studied a discrete market,
which differs from our model in that the transfers or the workers’ salaries are discretevariables. The following example shows that Theorem 1 does not hold in a modelwith discrete transfers and quasilinear utility.
Example 8. Let F = {f } and W = {w1 , w2 }. We assume that each agent has aquasilinear utility where possible valuations and salaries are given by integers. The
valuation of f is give by vf ({w1 , w2 }) = 1, vf ({wi }) = 0 for i = 1, 2. Clearly, vf
violates GS.
In this example, a mechanism is defined as a function φ that specifies an outcome
φ(vw1 , vw2 ) for each valuation profile (vw1 , vw2 ) ∈ Z2 where vwi denotes wi ’s valuation29

to f . Note that a mechanism is defined on Z2 rather than R2 since we assume thateach worker has an integer valuation.
We define a mechanism as follows:{(f, w1 , 1), (f, w2 , 0)} if − vw1 ≤ 1, −vw2 ≤ 0,
{(f, w , 0)}
if − vw1 > 1, −vw2 ≤ 0,
2
φ(vw1 , vw2 ) ={(f, w1 , 0)}
if − vw1 ≤ 0, −vw2 ≥ 1,




∅
if − v , −v ≥ 1.
w1

w2

For (vw1 , vw2 ) ∈ Z2 , if −vw1 ≤ 1 and −vw2 ≤ 0, then ({(f, w1 ), (f, w2 )}, (1, 0)) is acompetitive equilibrium by {w1 , w2 } ∈ Df (1, 0), and if −vw1 > 1 and −vw2 ≤ 0, then({(f, w2 )}, (−vw1 , 0)) is a competitive equilibrium by {w2 } ∈ Df (−vw1 , 0). We cancheck that φ selects a competitive equilibrium outcome for the other cases. Thus, φis a CE mechanism.
We show that φ is a SP mechanism. Fix any vw2 ∈ Z. Consider the following twocases.
(1) Suppose that −vw2 ≤ 0. Then,
φw1 (vw′ 1 , vw2 ) =
{(f, w , 1)}

if − vw′ 1 ≤ 1,

∅if − vw′ 1 > 1.

1

This implies that uw1 (φ(vw1 , vw2 )|vw1 ) ≥ uw1 (φ(vw′ 1 , vw2 )|vw1 ) for all vw1 , vw′ 1 ∈Z.
(2) Suppose that −vw2 > 0. Then,
φw1 (vw′ 1 , vw2 ) =
{(f, w , 0)}

if − vw′ 1 ≤ 0,

∅if − vw′ 1 > 0.

1This implies that uw1 (φ(vw1 , vw2 )|vw1 ) ≥ uw1 (φ(vw′ 1 , vw2 )|vw1 ) for all vw1 , vw′ 1 ∈Z.
The above argument shows that reporting truthfully is (weakly) dominant for w1 .

30

Moreover, for any vw1 ∈ Z,
φw2 (vw1 , vw′ 2 ) =
{(f, w , 0)}

if − vw′ 2 ≤ 0,

∅if − vw′ 2 > 0,2which implies that uw2 (φ(vw1 , vw2 )|vw2 ) ≥ uw2 (φ(vw1 , vw′ 2 )|vw2 ) for all vw2 , vw′ 2 ∈ Z.
Therefore, φ is a CE and SP mechanism while vf violates GS.
This example also illustrates that Proposition 1 does not hold in the model withdiscrete transfers: While ({(f, w1 ), (f, w2 )}, (1, 0)) and ({(f, w1 ), (f, w2 )}, (0, 1)) arecompetitive equilibria at (v1 , v2 ) = (0, 0), any arrangement ({(f, w1 ), (f, w2 )}, (p(f,w1 ) , p(f,w2 ) ))with p(f,w1 ) , p(f,w2 ) ≥ 1 cannot be a competitive equilibrium at (v1 , v2 ).

References
Athey, S., D. Coey, and J. Levin (2013): “Set-asides and subsidies in auctions,”
American Economic Journal: Microeconomics, 5, 1–27.
Baldwin, E., R. Jagadeesan, P. Klemperer, and A. Teytelboym (2023):“The equilibrium existence duality,” Journal of Political Economy, 131, 1440––1476.
Baldwin, E. and P. Klemperer (2019): “Understanding preferences:“demandtypes”, and the existence of equilibrium with indivisibilities,” Econometrica, 87,
867–932.
Crawford, V. P. and E. M. Knoer (1981): “Job matching with heterogeneousfirms and workers,” Econometrica, 49, 437–450.
Danilov, V., G. Koshevoy, and K. Murota (2001): “Discrete convexity andequilibria in economies with indivisible goods and money,” Mathematical Social
Sciences, 41, 251–273.
Demange, G. (1982): “Strategyproofness in the assignment market game,” Working
Paper.
Demange, G. and D. Gale (1985): “The strategy structure of two-sided matchingmarkets,” Econometrica, 53, 873–888.
31

Fleiner, T., R. Jagadeesan, Z. Jankó, and A. Teytelboym (2019): “Trading
networks with frictions,” Econometrica, 87, 1633–1661.
Fujishige, S. and Z. Yang (2003): “A note on Kelso and Crawford’s gross substitutes condition,” Mathematics of Operations Research, 28, 463–469.
Gul, F. and E. Stacchetti (1999): “Walrasian equilibrium with gross substitutes,” Journal of Economic Theory, 87, 95–124.
Hatfield, J. W. and F. Kojima (2010): “Substitutes and stability for matchingwith contracts,” Journal of Economic Theory, 145, 1704–1723.
Hatfield, J. W., F. Kojima, and S. D. Kominers (2018): “Strategy-proofness,investment efficiency, and marginal returns: An equivalence,” Becker Friedman
Institute for Research in Economics Working Paper.
Hatfield, J. W., S. D. Kominers, A. Nichifor, M. Ostrovsky, and
A. Westkamp (2013): “Stability and competitive equilibrium in trading networks,” Journal of Political Economy, 121, 966–1005.
Hatfield, J. W. and P. R. Milgrom (2005): “Matching with contracts,” American Economic Review, 95, 913–935.
Hirata, D. and Y. Kasuya (2017): “On stable and strategy-proof rules in matching markets with contracts,” Journal of Economic Theory, 168, 27–43.
Jagadeesan, R., S. D. Kominers, and R. Rheingans-Yoo (2018): “Strategyproofness of worker-optimal matching with continuously transferable utility,”
Games and Economic Behavior, 108, 287–294.
——— (2020): “Lone wolves in competitive equilibria,” Social Choice and Welfare,55, 215–228.
Kasuya, Y. (2021): “Unilateral substitutability is necessary for doctor-optimal stability,” Economics Letters, 207, 110047.
Kazumura, T., D. Mishra, and S. Serizawa (2020): “Strategy-proof multiobject mechanism design: Ex-post revenue maximization with non-quasilinear preferences,” Journal of Economic Theory, 188, 105036.
32

Kelso, A. S. and V. P. Crawford (1982): “Job matching, coalition formation,and gross substitutes,” Econometrica, 1483–1504.
Kojima, F., N. Sun, and N. N. Yu (2024): “Job matching with subsidy andtaxation,” Review of Economic Studies, 91, 372–402.
Kominers, S. D. and T. Sönmez (2016): “Matching with slot-specific priorities:
Theory,” Theoretical Economics, 11, 683–710.
Leonard, H. B. (1983): “Elicitation of honest preferences for the assignment of
individuals to positions,” Journal of Political Economy, 91, 461–479.
Miyake, M. (1998): “On the incentive properties of multi-item auctions,” International Journal of Game Theory, 27, 1–19.
Morimoto, S. and S. Serizawa (2015): “Strategy-proofness and efficiency with
non-quasi-linear preferences: A characterization of minimum price Walrasian rule,”
Theoretical Economics, 10, 445–487.
Murota, K. (2016): “Discrete convex analysis: A tool for economics and gametheory,” Journal of Mechanism and Institution Design, 1, 151–273.
Murota, K. and A. Shioura (1999): “M-convex function on generalized polymatroid,” Mathematics of Operations Research, 24, 95–105.
Nguyen, T. and R. Vohra (2022): “(Near) Substitute Preferences and Equilibria
with Indivisibilities,” Working Paper.
Reijnierse, H., A. van Gellekom, and J. A. Potters (2002): “Verifying grosssubstitutability,” Economic Theory, 20, 767–776.
Schlegel, J. C. (2022): “The structure of equilibria in trading networks withfrictions,” Theoretical Economics, 17, 801–839.
Shinozaki, H. and S. Serizawa (2024): “Efficiency, fairness, and strategyproofness in constrained object allocation problems with money,” Working Paper.
Sun, N. and Z. Yang (2006): “Equilibria and indivisibilities: Gross substitutes
and complements,” Econometrica, 74, 1385–1402.

33

Teytelboym, A. (2014): “Gross substitutes and complements: A simple generalization,” Economics Letters, 123, 135–138.
Zhou, Y. and S. Serizawa (2018): “Strategy-proofness and efficiency for nonquasi-linear and common-tiered-object preferences: Characterization of minimum
price rule,” Games and Economic Behavior, 109, 327–363.

34