Job Matching with Subsidy and Taxation

Abstract

In markets for indivisible resources such as workers and objects, subsidy and taxation for an agent may depend on the set of acquired resources and prices. This paper investigates how such transfer policies interfere with the substitutes condition, which is critical for market equilibrium existence and auction mechanism performance among other important issues. For environments where the condition holds in the absence of policy intervention, we investigate which transfer policies preserve the substitutes condition in various economically meaningful settings, establishing a series of characterisation theorems. For environments where the condition may fail without policy intervention, we examine how to use transfer policies to re-establish it, finding exactly when transfer policies based on scales are effective for that purpose. These results serve to inform policymakers, market designers, and market participants of how transfer policies may impact markets, so more informed decisions can be made.

1 INTRODUCTION

Subsidies and taxes permeate markets for indivisible resources.¹ For human resources, subsidies are extended to employers fulfilling specific obligations such as hiring a large proportion of disadvantaged, local, or R&D workers (Chandra and Wong, 2016; Ehrlich and Overman, 2020; Chen et al., 2021) and hiring at least a certain number of total workers (Slattery and Zidar, 2020); income tax is often levied on the annual income of a worker or a household. For goods, in radio spectrum auctions, “weak bidders” enjoy bidding credits and favourable financing terms (Milgrom, 2004; Hazlett and Muñoz, 2009); housing policies often penalise owning multiple properties financially (Gallent et al., 2017); a farmer who operates multiple land plots may receive per-unit-area subsidy if the total area exceeds a threshold (Li, 2014).

These policies often impact demand, and alter substitutability and complementarity relationship among resources, which may lead to substantial economic consequences. In the last example above, the subsidy scheme intuitively boosts complementarity among land plots for rent. As Li (2014) reports, land owners can thus capture high rents due to stronger bargaining positions, and renters become reluctant to enter the market. The former phenomenon is an instance of the “hold-up problem” (Kominers and Weyl, 2012), the problem caused by owners of complements demanding high compensations and thus holding up efficient assembly of resources. The latter phenomenon is explained by the “exposure problem” (Milgrom, 2000; Bichler and Goeree, 2017), the problem facing agents who desire multiple complements but hesitate to make initial offers in fear of high costs for later trades. These problems caused by complementarity harm allocative efficiency and social welfare.

This paper investigates how transfer policies impact substitutability (and thus complementarity), adopting a standard definition of substitutability for indivisible resources (when utility/profit is transferable)—the (gross) substitutes condition—and discussing implications within market design models. We augment the classical job matching model of Kelso and Crawford (1982) in which a finite set of firms compete for a finite set of workers. A firm’s revenue is a function of the set of workers it hires; the transfer it receives is a function of the set and the vector of salaries; its profit is the sum of its revenue and transfer minus total salary; it selects a set of workers to maximise profit. The substitutes condition requires that, roughly speaking, a set of demanded workers should still be demanded after a rise in others’ salaries. A worker’s utility is a function of its salary and the identity of its employer. This model embeds models for object assignment and auctions: firms and workers become buyers and objects, and the only mathematical difference is that objects go to the highest bidders regardless of bidder identity (Gul and Stacchetti, 1999; Milgrom, 2000, 2004; Murota, 2016).

In such environments, the substitutes condition is sufficient for the existence of competitive equilibria (Kelso and Crawford, 1982), as well as necessary in a maximal domain sense (Gul and Stacchetti, 1999; Milgrom, 2000; Yang, 2017).² This is important because without competitive equilibrium existence, any allocation is unstable in the sense that coalitions of market participants can profit from seeking alternative arrangements (i.e. the core is empty). The substitutes condition also brings useful structure to equilibria,³ and engenders attractive incentive, computational, and other properties.⁴ lacking space, we refer to the literature (Cramton et al., 2010; Bichler and Goeree, 2017; Milgrom, 2017) for discussions of why market design with the substitutes condition is well solved while without it difficult trade-offs (e.g. among efficiency, incentive, and complexity properties) are unavoidable except in special cases (e.g. Sun and Yang, 2014).⁵

This paper first examines which transfer policies preserve the substitutes condition in various economically meaningful settings which correspond to different classes of revenue functions satisfying the condition. In the absence of transfer policies, the condition is a particularly reasonable assumption when a market is specialised (e.g. a labour market for gastroenterologists (Niederle and Roth, 2003)), when resources are relatively homogeneous (e.g. a market for unskilled workers), when resources are prepackaged to avoid complementarity (Loertscher et al., 2015), when complementing resources are fixed in the short term (e.g. a rental market for agricultural land plots given investments in machinery), etc.

Our investigation starts with simple transfer policies, under which a transfer function whose domain contains all possible sets of workers determines the amount of transfer to a firm, so transfers are unrelated to salaries. Transfer functions, revenue functions, and their sums reside in the same real vector space. A transfer function preserves the substitutes condition for a class of revenue functions if its sum with each revenue function in the class satisfies the condition. Clearly, if the zero revenue function is in the class, then requiring a transfer function to preserve the substitutes condition for the class mandates the transfer function itself to satisfy the condition.

Our research reveals exactly which transfer functions always preserve the substitutes condition, i.e. preserve the condition for all revenue functions satisfying it. It is well known that the sum of two revenue functions satisfying the substitutes condition may not satisfy it, so the class of transfer functions which always preserve the substitutes condition is strictly smaller than the class satisfying the condition; but not much more is known.⁶ Our Theorem 1 attains a characterisation: a transfer function always preserves the substitutes condition if and only if it is the sum of an additively separable transfer function and a cardinally concave transfer function.⁷

Roughly speaking, additive separability means that each worker is assigned a real number and the total transfer is the sum of the assigned numbers of hired workers; cardinal concavity means that the transfer is a concave-extensible function of the number of hired workers. The characterised class of transfer functions is consistent with certain affirmative action policies, e.g. promising a fixed amount of subsidy for hiring a particular worker. However, this class of transfer functions is quite restrictive as, for instance, it rules out subsidising the firm for hiring at least a certain number of workers or for hiring a large proportion of disadvantaged workers.

We investigate other economically interesting cases: e.g. when workers belong to disjoint groups based on factors such as specialty, location, and ethnicity. A revenue function is group separable if the revenue is the sum of revenues generated by different groups (subsidiaries/departments) and each group’s revenue function satisfies the substitutes condition; a revenue function is group concave⁸ if workers within each group are homogeneous from the production perspective and it satisfies the substitutes condition. We present characterisations of transfer functions preserving the substitutes condition for these two separate cases, and explain how to derive new characterisations from existing ones using some simple logic.

We also examine complex transfer policies, under which a complex transfer function has two arguments, the set of hired workers and their salary vector. Complex transfer policies are orders of magnitude more complex and numerous than simple ones, and in particular, render the quasilinearity (in salaries) assumption invalid. As reported in Theorem 4, we establish that a complex transfer function always preserves the substitutes condition if and only if it is the sum of a C-additively separable complex transfer function and a C-cardinally concave complex function. The former is a generalisation of additively separable transfer functions, allowing the transfer associated with each worker to vary with her salary. The latter is a cardinally concave transfer function for all practical purposes.

It is intuitive that a C-additively separable complex transfer function, which treats workers individually, gives rise to no complementarity. The surprise lies in how small the characterised class of complex transfer policies is despite the many possibilities. Essentially, the requirement of always preserving substitutability precludes a complex transfer policy from conditioning the transfer on salaries, unless it is done in an individualistic way. We also study which complex transfer functions preserve the substitutes condition for all group separable revenue functions.

All the analyses above focus on environments in which the substitutes condition is satisfied prior to the inception of transfer policies. When the condition fails, policymakers and market designers often attempt to better the situation—e.g. through carefully prepackaging objects in many radio spectrum auctions (Loertscher et al., 2015). Investigating the potential of transfer policies in re-establishing the substitutes condition, we concentrate on cardinally concave transfer functions because they are detail-free (based only on scales defined by numbers of acquired indivisible resources), always preserve the substitutes condition, and intuitively boost overall substitutability. Our research reveals that a revenue function can have the substitutes condition re-established by those transfer policies if and only if it belongs to a special class—it fails the substitutes condition only because it misses a “non-increasing returns to scale” condition. This is a surprisingly narrow class, but models policy-relevant situations, e.g. when the only source of complementarity is economies of scale. When in addition the economies of scale derive only from potential exercise of market power (not from physical and engineering reasons), interventions based on cardinally concave transfer functions not only recover substitutability but also preempt monopolistic behaviours.⁹

Our paper belongs to the vast literature on policy interventions in marketplaces (Roth, 2018). In market design, there are few studies of transfer policies, which are monetary and soft, but there is a blossoming literature on compulsory constraints. The most related study to the current paper is Kojima et al. (2020, henceforth, KSY), which in the job matching framework studies constraints on the sets of workers an employer is allowed to hire.¹⁰ KSY identifies exactly which constraints preserve the substitutes condition for, respectively, all revenue functions satisfying the substitutes condition and all group separable revenue functions.

The rest of the paper unfolds as follows. Section 2 introduces the model. Section 3 characterises which transfer functions always preserve the substitutes condition. Section 4 characterises which transfer functions preserve the substitutes condition for all group separable and group concave revenue functions, respectively; and explains how to derive new characterisations. Section 5 generalises the scope of our analysis to complex transfer functions. Section 6 investigates how the substitutes condition can be re-established by transfer policies. Section 7 summarises contents relegated to the appendix, discusses future research, and concludes.

2 THE MODEL

There is a finite set of workers  D with cardinality $|D|=M\ge 1$⁠.¹¹ A revenue function of a firm  $R:2^D\to \mathbb{R}$ maps each subset of workers to the revenue of the firm if it hires them. No restriction of monotonicity or free disposal is imposed. Appendix A details how multiple firms enter a full-fledged job matching model, assisting general-interest readers unfamiliar with related literature; it also explains why mathematically object assignment/auction models are special cases, with workers and firms replaced by objects and agents seeking to acquire them, so all results developed for job matching apply equally well to those settings.

A policymaker regulates the labour market using fiscal incentives. A transfer function  $T:2^D\to \mathbb{R}$ maps each subset of workers to the amount of transfer a firm receives if it hires them. A transfer policy corresponding to such a function is simple in the sense that it is independent of salary schedules. For ease of comprehension, more general and complex transfer policies are not investigated until Section 5. Naturally, for $A\subset D$⁠, the two cases of $T(A)>0$ and $T(A)<0$ correspond to subsidy and taxation, respectively.

Note that there is no mathematical distinction between a transfer function and a revenue function, so we can use the same taxonomy for both of them. For example, we say that a revenue function or transfer function $S:2^D\to \mathbb{R}$ is additively separable if for each $A\subset D$⁠, $S(A)=\sum _{d\in A}S(\{d\})$⁠. When the meaning is clear from the context, we also simply say “an additively separable function.”

A salary schedule is a real-valued function $s:D\to \mathbb{R}$ that specifies a salary for each worker; for each $d\in D$⁠, $s_d$ is short for $s(d)$⁠. If the firm hires $A\subset D$ while facing a salary schedule $s$⁠, a revenue function R, and a transfer function T, its profit is $V(A;s,R+T)=R(A)+T(A)-\sum _{d\in A}{s}_d$⁠, that is, its revenue plus the transfer minus the sum of salaries paid to the workers. This assumes away externality from the allocation of workers outside the firm. We define the maximal profit function  $\mathrm{\Pi }(\cdot ;R+T):{\mathbb{R}}^D\to \mathbb{R}$ and the demand correspondence  $X(\cdot ;R+T):{\mathbb{R}}^D\to \{\mathcal{A}:\mathcal{A}\subset 2^D\text{ and }\mathcal{A}\ne \mathrm{\varnothing }\}$ such that for each salary schedule $s$⁠,

Each element of $X(s;R+T)$ is referred to as a demand set.

For expositional simplicity, we intentionally leave out the possibility of expanding the range of a revenue or transfer function to $\mathbb{R}\cup \{-\mathrm{\infty }\}$ (see Hatfield et al., 2013, 2019; Fleiner et al., 2019, among others). In other words, all sets of workers are assumed to be feasible. A constraint in KSY can be viewed as a transfer function with a range of $\{0,-\mathrm{\infty }\}$⁠, which is zero-dimensional, but the range of our transfer function is the one-dimensional $\mathbb{R}$⁠. This explains why proofs in the current paper are more involved than KSY’s. For the more general case in which some sets may be designated infeasible, it is straightforward to combine findings in KSY with those in the current paper (see Appendix B).

The (gross) substitutes condition is the requirement that given any demand set, if some salaries rise, then we can find a new demand set (at the new salary schedule) which contains all workers in the original demand set whose salaries remain the same.

 

The substitutes condition is a natural assumption in modelling many real-life economic environments, where complements may be ruled out. One example is a unit-demand revenue function R, where for each $A\subset D$⁠, $R(A)=\underset{d\in A}{max}R(\{d\})$⁠; this is natural when no more than one worker/object is needed. In labour markets, most firms need workers with different skill sets to cooperate, but when a firm focuses on a particular market such as one for truck drivers, the assumption of substitutability appears reasonable. In markets for goods, substitutability seems more prevalent than complementarity, and even when complementarity is present, they might be eliminated through prepackaging or repackaging goods (Loertscher et al., 2015). Milgrom (2017) reviews more examples as well as justifications for the condition to hold and to be desired.¹²

Rich in intellectual history (Arrow et al., 1959; Milgrom, 2017) and equivalent to many alternatives (Gul and Stacchetti, 1999; Hatfield and Milgrom, 2005; Murota, 2016), the substitutes condition is key to plenty of important and desirable properties, playing a role analogous to that of concave functions for divisible resources. Given its usefulness in theory and practice, we study how policies may interfere with it.

In particular, given an environment in which all revenue functions satisfy the substitutes condition, a policymaker may worry that some fiscal policy interventions in the form of transfer functions can cause the condition to fail—a case where R satisfies it but $R+T$ does not. To address such a concern, we investigate which transfer functions preserve the substitutes condition.

 

A transfer function which always preserves the substitutes condition must itself satisfy the condition because the zero revenue function satisfies the condition. On the other hand, given two functions satisfying the substitutes condition, their sum may not. Here is one example: consider two unit-demand functions R and T and three workers $D=\{d^{\prime },d^{″},d^{‴}\}$ such that $R(A)=min\{1,|A\cap \{d^{\prime },d^{″}\}|\}$ and $T(A)=min\{1,|A\cap \{d^{″},d^{‴}\}|\}$ for each $A\subset D$⁠. Define salary schedule $s$ such that $s_{d^{\prime }}=s_{d^{″}}=0.1$ and $s_{d^{‴}}=0$⁠. Under $s$ and $R+T$⁠, $\{d^{\prime },d^{‴}\}$ is a demand set. Raise the salary of $d^{‴}$ to 1 to produce salary schedule $s^{\prime }$⁠. Under $s^{\prime }$ and $R+T$⁠, the only demand set is $\{d^{″}\}$⁠, a violation of the substitutes condition.

We are unaware of earlier attempts at characterising the class of functions that, when added to any function satisfying the substitutes condition, preserve the condition. The Introduction makes plain the value of discerning exactly which transfer functions preserve the substitutes condition for different classes of revenue functions (which correspond to scenarios in which the policymaker has different partial knowledge about firm revenue functions). The ensuing two sections address this question and provide characterisations of transfer functions that preserve the substitutes condition for various classes of revenue functions; they are followed by a section about complex transfer policies and another about using transfer policies to re-establish the substitutes condition when it fails.

3 ALWAYS PRESERVING THE SUBSTITUTES CONDITION

This section provides a characterisation of all transfer functions that always preserve the substitutes condition. First, it is easy to see from the definition of the substitutes condition that it is invariant to the addition of an additively separable function, so an additively separable function always preserves the substitutes condition.¹³

 

Accordingly, the policymaker can subsidise or tax the firm for hiring individual workers without causing the failure of the substitutes condition. Similarly, in goods markets, individual objects can be subsidised or taxed as such.

In theory, using an additively separable transfer function is equivalent to directly subsidising or taxing workers (rather than the firm) if they work for the firm.¹⁴ In real life, we observe both ways of implementation: e.g. in India, women empowerment subsidies go through firms via programs such as subsidised training (Rotemberg, 2019, Section I);¹⁵ in China, subsidies to rural teachers are part of their salaries (Lin and Wong, 2012, Page 38).

How about other types of fiscal incentives? For example, the policymaker may consider subsidising a firm when the number or proportion of minority workers meets a certain criterion, or taxing a firm if it acquires enough objects (e.g. rental housing) to undermine healthy market competition. Before providing a definitive answer for all transfer functions, we need to define some classes of transfer functions. Let us denote the set of integers between m and $m^{\prime }$⁠, where $m,m^{\prime }\in \mathbb{Z}$ and $m\le m^{\prime }$⁠, by $[m,m^{\prime }{]}_{\mathbb{Z}}:=\{m^{″}\in \mathbb{Z}:m\le m^{″}\le m^{\prime }\}$⁠.

A transfer function T is cardinal if there exists an associated function $f:[0,M{]}_{\mathbb{Z}}\to \mathbb{R}$ such that $T(A)=f(|A|)$ for each $A\subset D$⁠. In words, the transfer is said to be cardinal if it depends solely on the number of workers the firm hires. Given f and each $m\in [1,M{]}_{\mathbb{Z}}$⁠, we denote by ${\alpha }_m^f:=f(m)-f(m-1)$ the incremental transfer from hiring a worker in addition to the $m-1$ workers already hired, so $T(A)=f(0)+\sum _{m\le |A|}{\alpha }_m^f$ for each $A\subset D$⁠.

A transfer function T is cardinally concave if it is cardinal and the associated function f is extensible to a concave function on $\mathbb{R}$⁠. Equivalently, the requirement is that the corresponding finite sequence $({\alpha }_1^f,{\alpha }_2^f,\dots ,{\alpha }_M^f)$ be weakly decreasing. Note that it is possible that entries of the sequence are positive at the beginning of the sequence and negative toward the end. Such a transfer policy seems to “softly” discourage the firm from hiring too few or too many workers, a feature reminiscent of a hard interval constraint studied by KSY but more flexible.

Our first main result demonstrates that the sums of additively separable transfer functions and cardinally concave ones form the entire class that always preserve the substitutes condition.

 

All non-trivial proofs of our results, including Theorem 1, are relegated to the Online Appendix.

In addition to additively separable transfer functions, the sufficiency part of Theorem 1 further supports the idea of basing fiscal policy interventions on cardinally concave ones. Such flexibility may be useful in applications. For instance, it seems well suited for tackling the well-known “rural hospital problem,” the problem of rural hospitals having persistent difficulties in recruitment (Roth, 1986). Subsidising a rural hospital according to how many workers it hires, regardless of whom, may be more reasonable than mandating a minimum number (a policy suggested by KSY) in many real-life environments. Subsidising hiring this way is already a common approach to boosting employment in policy practice (Slattery and Zidar, 2020). Theorem 1 guarantees that these policies will not destroy substitutability.

As cardinally concave transfer functions are non-discriminatory toward workers, the necessity part of Theorem 1 highlights the difficulty of designing affirmative action policies beyond additively separable transfer functions. In particular, some of the policies we mentioned before—such as subsidising the firm only when it hires at least a certain number of minority workers—are ruled out. A reader might wonder whether this necessity claim depends on the strong requirement of preserving the substitutes condition for all revenue functions satisfying the condition. Proposition 10 of Appendix C shows that this conclusion can in fact be obtained even for a substantially smaller class of revenue functions called “binary unit-demand revenue functions,” strengthening the necessity claim. The remarks below the proposition offer more details.

The discussion above highlights the danger of employing more general transfer policies without more knowledge about the structure of the revenue functions. Let us consider examples in which more knowledge is useful: when workers or goods are homogeneous and exhibit weakly diminishing marginal productivity or valuation, the revenue functions are cardinally concave. Important real-life applications include sales of government bonds, company shares, electricity, natural gas, automobile licenses, and permits for emission and other activities (see Wilson, 1979, and a large ensuing literature on auctions of homogeneous goods). In such special but economically interesting cases, the requirement for simple transfer policies to preserve substitutability is less demanding.

Formally, transfer functions satisfying the substitutes condition is exactly the class of functions that preserve the substitutes condition for all cardinally concave revenue functions.

 

This is a simple corollary of Theorem 1, which tells us that the sum of a cardinally concave function and a function satisfying the substitutes condition satisfies the condition.

The next section analyses several other economically meaningful settings where more knowledge is available, and characterises simple transfer policies that preserve the substitutes condition for those scenarios. The section can be skipped for readers who would like to first learn about which complex transfer policies preserve the substitutes condition.

4 SUBCLASSES OF REVENUE FUNCTIONS

Fix a partition of D, which we denote by $\mathcal{P}\subset 2^D\setminus \{\mathrm{\varnothing }\}$⁠, such that $\cup \mathcal{P}:={\cup }_{P\in \mathcal{P}}P=D$⁠, and for all $P,P^{\prime }\in \mathcal{P}$ with $P\ne P^{\prime }$⁠, $P\cap P^{\prime }=\mathrm{\varnothing }$⁠. Each member of $\mathcal{P}$ is called a group. In practice, a group of workers may form based on a gender, an age group, an ethnic group, a specialty, a qualification, a location, an educational background, or a combination of several individual characteristics; grouping of objects may also be based on different properties such as functionality, quality, sourcing, etc.

Given $\mathcal{P}$⁠, we investigate which transfer functions preserve the substitutes condition for all “group separable” revenue functions in the first subsection, and for all “group concave” revenue functions in the second subsection. The last subsection demonstrates how to obtain a rich set of new results from existing ones.

4.1 Group separable revenue functions

A revenue function R is group separable if there is a family of functions $\{R_P{\}}_{P\in \mathcal{P}}$ such that each $R_P:2^P\to \mathbb{R}$ satisfies the substitutes condition, and for each $A\subset D$⁠, $R(A)=\sum _{P\in \mathcal{P}}{R}_P(A\cap P)$⁠. In words, a revenue function is group separable if workers hired from each group form a unit, each unit’s revenue as a function of the worker set in the unit satisfies the substitutes condition, and the total revenue is the sum of unit revenues. Such a revenue function satisfies the substitutes condition (see KSY, which characterises all constraints preserving the substitutes condition for this class of revenue functions).

A revenue function may be group separable, for example, because the firm owns several departments that hire from disjoint pools of workers corresponding to different specialties (so each group consists of all workers of one specialty), or because it owns several branches that hire from disjoint pools of workers corresponding to different geographical locations. For indivisible goods, a business corporation may run a group of personal care brands and a group of processed food brands independently, and a wealthy collector may value neoclassical paintings and sports memorabilia separately. It is plausible that the policymaker may learn these facts but no further details of the revenue function.

Define a vectorisation transformation  $\tau :2^D\to {\mathbb{Z}}^{\mathcal{P}}$ such that for each $A\subset D$⁠, $\tau (A)$ is an integer-valued function on $\mathcal{P}$ with $\tau (A)(P)=|A\cap P|$ for each $P\in \mathcal{P}$⁠. For each set of workers A, $\tau (A)$ represents the number of workers in A who belong to different groups. We call any $W:\tau (2^D)\to \mathbb{R}$ a vectorial function. A transfer function T is group cardinal if there exists an associated vectorial function $W:\tau (2^D)\to \mathbb{R}$ such that for each $A\subset D$⁠, $T(A)=W(\tau (A))$⁠. In this case, the transfer depends only on the number of workers hired from each group, but not on within-group identities of the workers. A group cardinal transfer function is group concave¹⁶ if it also satisfies the substitutes condition. In words, a transfer function is group cardinal if it treats workers from the same group equally, and becomes group concave if it further satisfies the substitutes condition. The word “concave” comes from the connection of this concept to M${}^{\mathrm{♮}}$-concavity in discrete convex analysis (Online Appendix OA.1 and Murota, 2016). A cardinally concave transfer function, which treats all workers homogeneously (not only within-group workers), is group concave.

The characterisation theorem for transfer functions to preserve the substitutes condition for all group separable revenue functions is as follows.

 

This result suggests that, with the knowledge of group separability of the revenue function, the policymaker can utilise a broader class of transfer functions (including group concave ones) without causing the failure of the substitutes condition. Policy interventions based on group concave functions can treat workers in different groups differently while treating those in the same group equally (note that this is in sharp contrast to cardinally concave functions in Theorem 1). For example, the policymaker can design the transfer function as a concave-extensible function of the number of workers hired from one group or the union of several groups. If this group or union consists entirely of minorities (or majorities), the policy can be used to achieve diversity or balance of the workforce.

Proposition 10 greatly strengthens the necessity part of Theorem 1; Proposition 11, also in Appendix C, does the same for Theorem 2. It states that preserving the substitutes condition for a small subclass of group separable revenue functions called “within-group binary unit-demand revenue functions” demands that the transfer functions be those identified in Theorem 2.

4.2 Group concave revenue functions

Group concavity may be a reasonable simplifying assumption for the revenue function when workers/objects within each group are, with regard to generating revenues, approximately homogeneous or indistinguishable from each other before being hired/acquired.¹⁷ The homogeneity assumption may easily hold for low-skilled workers and for mass-produced objects.

Milgrom and Strulovici (2009), in comparing “strong substitutes” (group concave revenue functions) with “weak substitutes” (which forbids workers within each group to have different salaries in its formulation), in effect establish the necessity of the substitutes condition for a variety of desirable properties: “pseudo-equilibria being competitive equilibria,” “Vickrey outcomes being core allocations,” and “the law of aggregate demand.” Similar to group separability, group concavity of the revenue function may be easy to observe for the policymaker, while further knowledge may be difficult to come by.

The main theorem for group concave revenue functions is the following.

 

A symmetry exists between Theorems 2 and 3 regarding how they connect with Theorem 1. The part reading “sum of an additively separable function and a cardinally concave function” in Theorem 1 has its first component replaced with “a group separable function” in Theorem 3, and its second component replaced with “a group concave function” in Theorem 2. The characterised class of transfer functions in Theorem 1 equals the intersection of the two characterised classes in Theorems 2 and 3. Theorem 2 degenerates into Theorem 1 when there is only one group, and Theorem 3 degenerates into Theorem 1 when each worker forms a group.

Group separability of a transfer function T is consistent with policy interventions that discriminate between workers within groups. For instance, given a group $P^{*}\in \mathcal{P}$ and a set of minority workers $A\subset D$⁠, we can consider a concave-extensible function $f:[0,|P^{*}\cap A|{]}_{\mathbb{Z}}\to \mathbb{R}$⁠, and a transfer function T satisfying $T(B):=f(|P^{*}\cap A\cap B|)$ for each $B\subset D$⁠. Note that T is degenerately group separable. Hence, in the settings of Theorem 3, such within-group affirmative action, which is not allowed in the setting of Theorem 1, preserves the substitutes condition.

A strengthening of the necessity part of Theorem 3 is stated in Proposition 12 of Appendix C: the characterisation of transfer functions in Theorem 3 can be obtained via only requiring them to preserve the substitutes condition for all “uni—and $\overline{\text{uni}}$-group spline concave revenue functions,” a small subclass of group concave revenue functions.

For the case of $|\mathcal{P}|=2$⁠, the class of permitted transfer functions is larger: a group concave function is allowed instead of merely a cardinally concave function. Mathematically, this is evidence for a structural distinction between $|\mathcal{P}|=2$ and $|\mathcal{P}|>2$⁠.

 

We conjecture that this is a characterisation result too.

4.3 Deriving new characterisations from existing ones

The characterisation results above and in Appendix C are summarised in Table 1. In this subsection, we illustrate how to derive new results based on those results and simple rules.

First, by Proposition 1, translating a class of revenue functions by additively separable revenue functions (potentially applying different translations to different revenue functions) never changes the set of transfer functions that preserve the substitutes condition for the class.

Second, by Definition 2, if one class of revenue functions is a subclass of another, then preserving the substitutes condition for the former is weakly less restrictive than for the latter. For example, the class of unit-demand revenue functions is between the class of binary unit-demand revenue functions and the class of revenue functions satisfying the substitutes condition, so, by Theorem 1 and Proposition 10, a transfer function preserves the substitutes condition for all unit-demand revenue functions if and only if it is the sum of an additively separable function and a cardinally concave one. For another example, a large class of revenue functions satisfying the substitutes condition, “endowed assignment valuations” (Hatfield and Milgrom, 2005; Ostrovsky and Paes Leme, 2015), include all unit-demand revenue functions, so the corresponding characterisation remains the same. Figure 1 in the Appendix, a Venn diagram for various classes of revenue functions, provides a handy reference for applying this rule.

The next section turns to complex transfer policies, which allow transfers to depend on salaries/prices. The logic explained in the current subsection obviously generalises.

5 COMPLEX TRANSFER POLICIES

Transfer functions account for many fiscal policies deployed or considered by policymakers. But in many other cases, transfer to an employer depends not only on the set of employees it hires, but also on the salary at which they are hired. For example, employees usually pay income taxes; this is equivalent to letting employers pay on their behalf. Employers receive “credit for increasing research activities” for wages paid to R&D workers (e.g. see Section 41 of the Internal Revenue Code of the United States); their total salary may count toward thresholds for greater tax breaks (Chen et al., 2021, Table 1). In sports leagues, many franchises pay luxury taxes, which are jointly determined by the identities of players hired and their salaries (Kaplan, 2004; Coates and Frick, 2012). Examples also abound of goods markets with complex transfer policies: subsidies for electric vehicles or taxes on residential properties often vary based on their prices.

To encompass as many real-world transfer policies as possible, we generalise transfer functions to complex ones in Subsection 5.1. Subsection 5.2 characterises the class of complex transfer functions which always preserve the substitutes condition. The class consists of two types of transfer policies and their mixture: the first type allows the transfer to be the sum of hired workers’ individualised transfers, each of which is a function of the worker’s own salary; the second type is in essence cardinally concave. Subsection 5.3 studies which complex transfer functions preserve the substitutes condition for all group separable revenue functions.¹⁸

5.1 Modelling complex transfer policies

A complex function¹⁹  $\mathrm{{\rm Y}}:2^D\times {\mathbb{R}}^D\to \mathbb{R}$ maps each ordered pair of a set of workers and a salary schedule to a real number; it is called a complex transfer function if two requirements are satisfied. First, transfer only depends on the salaries of the firm’s own employees; i.e.  $\mathrm{{\rm Y}}(A,s)=\mathrm{{\rm Y}}(A,s^{\prime })$ for all $A\subset D$ and $s,s^{\prime }\in {\mathbb{R}}^D$ with $s{|}_A=s^{\prime }{|}_A$⁠. (A salary schedule $s$ restricted to $A\subset D$ is denoted $s{|}_A$⁠.) Second, overall hiring cost is strictly increasing in the salaries of hired workers; i.e. given every $A\subset D$⁠, the hiring cost after transfer $\sum _{d\in A}{s}_d-\mathrm{{\rm Y}}(A,s)$ is strictly increasing in each $s_d$ with $d\in A$⁠. These two requirements seem to be quite reasonable while keeping the following analysis tractable.

A (simple) transfer function $T:2^D\to \mathbb{R}$ can be viewed as a complex function ${\mathrm{{\rm Y}}}^T$ satisfying ${\mathrm{{\rm Y}}}^T(A,s)=T(A)$ for all $A\subset D$ and $s\in {\mathbb{R}}^D$⁠; as ${\mathrm{{\rm Y}}}^T$ satisfies the two requirements above trivially, it is a complex transfer function. We abuse notation by defining the sum of a revenue function R and a complex function $\mathrm{{\rm Y}}$⁠,²⁰ which bear different domains, to be $(R+\mathrm{{\rm Y}}):2^D\times {\mathbb{R}}^D\to \mathbb{R}$ such that $(R+\mathrm{{\rm Y}})(A,s)=R(A)+\mathrm{{\rm Y}}(A,s)$ for all $A\subset D$ and $s\in {\mathbb{R}}^D$⁠.

Given a revenue function R and a complex function $\mathrm{{\rm Y}}$⁠, the profit function $V(\cdot ;s,R+\mathrm{{\rm Y}}):2^D\to \mathbb{R}$⁠, the maximal profit function $\mathrm{\Pi }(\cdot ;R+\mathrm{{\rm Y}}):{\mathbb{R}}^D\to \mathbb{R}$⁠, and the demand correspondence $X(\cdot ;R+\mathrm{{\rm Y}}):{\mathbb{R}}^D\to \{\mathcal{A}:\mathcal{A}\subset 2^D\text{ and }\mathcal{A}\ne \mathrm{\varnothing }\}$ are still well defined. So whether $X(\cdot ;R+\mathrm{{\rm Y}})$ or $R+\mathrm{{\rm Y}}$ satisfies the substitutes condition or not is still well defined through Definition 1; and whether $\mathrm{{\rm Y}}$ preserves the substitutes condition for a class of revenue functions through Definition 2.

Let us consider a special class of complex transfer functions which benefit the task of modelling policies such as individual income tax. A complex function $\mathrm{{\rm Y}}:2^D\times {\mathbb{R}}^D\to \mathbb{R}$ is C-additively separable if there is an associated family of individual transfer functions  $\{g^d{\}}_{d\in D}$ with $g^d:\mathbb{R}\to \mathbb{R}$ for each $d\in D$ such that $\mathrm{{\rm Y}}(A,s)=\sum _{d\in A}{g}^d(s_d)$ for all $A\subset D$ and $s\in {\mathbb{R}}^D$⁠.²¹ Here, “C” stands for “complex.” The transfer policy corresponding to a C-additively separable function calculates the amount of transfer associated with each employee—which may depend on that employee’s salary—separately, and adds them up to determine the total amount of transfer. By allowing each individual transfer amount to depend on the individual salary, C-additively separable functions generalise additively separable transfer functions.

Given a C-additively separable function $\mathrm{{\rm Y}}$⁠, we can define an associated family of individual hiring cost functions  $\{{\tilde{g}}^d{\}}_{d\in D}$ such that ${\tilde{g}}^d(s_d)=s_d-\mathrm{{\rm Y}}(\{d\},s)$ for all $d\in D$ and $s\in {\mathbb{R}}^D$⁠. It is easy to see that $\mathrm{{\rm Y}}$ is a complex transfer function if and only if every ${\tilde{g}}^d$ is strictly increasing.

We have the following generalisation of Proposition 1.

 

The first part of the proposition is more policy-relevant. It states that all C-additively separable complex transfer functions always preserve the substitutes condition. Accordingly, salary-dependent transfer policies which treat individual workers separately pose no threat to the substitutes condition. In real life, such policies are commonplace, including individual income tax, rural teacher incentive schemes, and luxury tax on non-essential items such as yachts. Proposition 3 is reassuring.

5.2 Always preserving the substitutes condition

Now we explore exactly which complex transfer policies always preserve the substitutes condition.

A complex transfer function can be quite complex: its two arguments (the set of workers and their salary schedule) may interact in convoluted ways. To investigate which ones always preserve the substitutes condition, we first lower the dimension by fixing the salary schedule part, which gives us Proposition 4, a powerful result connecting the last section and this one.

Here, we say that a class of revenue functions $\mathcal{R}$ is closed under translation (by additively separable functions) if for all $R\in \mathcal{R}$ and $s\in {\mathbb{R}}^D$⁠, $\mathcal{R}$ contains any $R^{\prime }:2^D\to \mathbb{R}$ satisfying $R^{\prime }(A)=R(A)+\sum _{d\in A}{s}_d$ for each $A\subset D$⁠. For example, the class of additively separable functions, the class of group separable functions, the class of revenue functions satisfying the substitutes condition, and the class of transfer functions which always preserve the substitutes condition, are all closed under translation.

 

According to Proposition 4, for instance, if a complex transfer function always preserves the substitutes condition, then when we fix its salary schedule part and view it as a transfer function, this function always preserves the substitutes condition. Theorem 1 characterises all those transfer functions, so we already possess substantial knowledge about this complex transfer function. Proposition 4 can also be applied in many other contexts.

The space of complex transfer policies, as modelled by complex transfer functions, is much larger than that of simple ones. One may suspect that the space of complex transfer policies which always preserve the substitutes condition is also much larger than the space for simple ones as identified in Theorem 1. This intuition, it turns out, is ill founded, as Theorem 4 demonstrates.

A complex function $\mathrm{{\rm Y}}$ is C-cardinally concave if there exists a cardinally concave transfer function T such that for all $A⊊D$ and $s\in {\mathbb{R}}^D$⁠, $\mathrm{{\rm Y}}(A,s)=T(A)$⁠; $\mathrm{{\rm Y}}(D,s)$ as a function of $s\in {\mathbb{R}}^D$ is weakly increasing; for each $s\in {\mathbb{R}}^D$⁠, $\mathrm{{\rm Y}}(D,s)\le T(D)$ and the transfer function $T^s:=\mathrm{{\rm Y}}(\cdot ,s)$ is cardinally concave.²³ Such an $\mathrm{{\rm Y}}$ is “almost cardinally concave,” identical to the cardinally concave function T except that in the extreme cases of one firm hiring all workers, the transfer may vary with salaries in a disciplined way.

 

The extreme cases of one firm hiring all workers may be duly ignored. Thus, when we compare Theorem 4 with Theorem 1, the greatly expanded domain of transfer policies under consideration here fails to offer many extra possibilities. Salary-dependent additively separable transfer policies on top of cardinally concave ones are exactly those which always preserve the substitutes condition.

Many complex transfer policies fall outside the identified class. For example, consider a progressive tax on the total salary paid to a set of workers.²⁴ When the salary of one worker in this set increases, all other workers in it essentially become more expensive for the firm and possibly less demanded. This is the intuition behind how such a tax policy causes complementarity. A characterisation result such as Theorem 4 spares us the drudgery of case-by-case reasoning.

5.3 Group separable revenue functions

Which complex transfer functions preserve the substitutes condition for all group separable revenue functions?

Given a group separable revenue function R, a group concave transfer function T, and a C-additively separable complex transfer function $\mathrm{{\rm Y}}$⁠, Theorem 2 states that $R+T$ satisfies the substitutes condition, so Proposition 3 applies, telling us that $(R+T)+\mathrm{{\rm Y}}$ still satisfies it.

 

We now show that sums such as those in Corollary 2 almost characterise the class of complex transfer functions which preserve the substitutes condition for all group separable revenue functions.

A complex function $\mathrm{{\rm Y}}$ is C-group concave if for each $s\in {\mathbb{R}}^D$⁠, the transfer function $T^s:=\mathrm{{\rm Y}}(\cdot ,s)$ is group concave; and for any fixed $\overline{s}\in {\mathbb{R}}^D$ and any $A\subset D$ such that $s{|}_P=\overline{s}{|}_P$ for each group $P\subset A$⁠, $T^s(A)=T^{\overline{s}}(A)$⁠. Such an $\mathrm{{\rm Y}}$ is “almost group concave” because it is identical to the group concave transfer function $T^{\overline{s}}$ except in the extreme cases of the firm hiring all workers in a group.

 

We are unable to provide an exact characterisation for complex transfer functions to preserve the substitutes condition for all group separable revenue functions, as analogous to Theorem 4. But Corollary 2 provides a subset of those complex transfer functions, and Proposition 5 provides a superset; these two sets are so close that we arguably offer an approximate characterisation.

6 RE-ESTABLISHING THE SUBSTITUTES CONDITION

Our investigation so far assumes that revenue functions satisfy the substitutes condition and pores over which transfer policies preserve the condition. When a revenue function fails the condition, can transfer policies help to re-establish it? Answering this theoretical question may provide guidance for policy designers when the substitutes condition is desirable (such as in auctions with multiple objects as explained in the Introduction). This section reports our findings regarding this question.

6.1 Formulating the research question

To be precise, for a revenue function R which may fail the substitutes condition, we look for a transfer function T or a complex transfer function $\mathrm{{\rm Y}}$ such that $R+T$ or $R+\mathrm{{\rm Y}}$ satisfies the condition.

 

For any revenue function R, the transfer function $-R$ re-establishes the substitutes condition. This observation, however, is of little practical value: designers may not know R, and even if they do, they may not be able to customise policies for different firms. Are there transfer policies which re-establish the substitutes condition for a wide variety of revenue functions?

Theorem 4 is a natural starting point. The identified class of transfer policies always preserve the substitutes condition, so intuitively they can never strictly reduce substitutability; all other transfer policies can destroy the condition when applied broadly, so seem less attractive. According to Proposition 3, additively separable transfer policies can neither destroy nor non-trivially re-establish the substitutes condition. Further because C-cardinally concave complex functions are for all practical purposes cardinally concave transfer functions, we are left with one non-trivial research question: whether cardinally concave transfer functions can re-establish the substitutes condition for large classes of revenue functions.

To further motivate our focus on cardinally concave transfer functions, we make several observations. First, a cardinal transfer function is detail-free, its value only depending on the number of hired workers (which is relatively difficult to manipulate for firms and easy to observe for policymakers), so seems attractive for policymaking.

Second, given two cardinal transfer functions $T^1$ and $T^2$⁠, we say that $T^2$ is more concave than  $T^1$ if $T^2-T^1$ is cardinally concave.

 

The proposition holds because if $R+T^1$ satisfies the substitutes condition, then so does $R+T^2=(R+T^1)+(T^2-T^1)$ by Theorem 1.

For any cardinal transfer function $T^1$⁠, there always exists a cardinally concave transfer function $T^2$ more concave than $T^1$⁠.²⁵ Consequently, by Proposition 6, in studying which revenue functions can have the substitutes condition re-established by cardinal transfer functions, it is without loss of generality to focus on cardinally concave transfer functions.

Third, if a cardinally concave transfer function is not strictly concave,²⁶ it degenerates into an additively separable transfer function plus a constant, which neither destroys nor non-trivially re-establishes the substitutes condition (Proposition 1). Hence, only strictly cardinally concave transfer functions have the potential to non-trivially re-establish the substitutes condition.²⁷

6.2 A new characterisation of the substitutes condition

The next subsection reveals exactly which revenue functions can have the substitutes condition re-established by cardinally concave transfer functions. To define those, we first provide a novel characterisation of the substitutes condition as the combination of three conditions.

Consider a situation in which the firm is constrained to pick a set out of a non-empty collection $\mathcal{F}\subset 2^D$⁠, called its feasibility collection as in KSY. Abusing notation, given $\mathcal{F}$⁠, a revenue function R, and a transfer function T, we define the maximal profit function Π and demand correspondence X such that for each salary schedule $s$⁠,

Thus in this context, the substitutes condition and its preservation are still well defined.

Given $m\in [0,M{]}_{\mathbb{Z}}$⁠, we say that the feasibility collection ${\mathcal{D}}_m:=\{A\subset D:|A|=m\}$ is defined by an exact constraint. Such a constraint requires the firm to hire exactly m workers.

 

The exactly constrained substitutes condition requires that under each exact constraint the demand correspondence satisfies the substitutes condition.

 

The chain-constrained substitutes condition requires that when the quota of an exact constraint is reduced by one, any demand set under the original constraint can be transformed to a demand set under the new constraint by excluding one member.

The following proposition shows that the chain-constrained substitutes condition is equivalent to the requirement that when the quota of an exact constraint is raised by one, an earlier demand set can become a new demand set by adding one outsider.

 

Consider the following definition of non-increasing returns to scale for indivisible goods: as the quota of an exact constraint rises from 0 to M, the maximal profit’s marginal change can never increase.

 

The following proposition demonstrates that Definitions 4–6 together make up the substitutes condition.

 

It is straightforward to verify that these three conditions are independent: the combination of two does not imply the third.

6.3 The main results

The combination of Definitions 4 and 5 is invariant to the addition of a cardinal transfer function because a cardinal transfer function maintains the relative profitability of worker sets of the same cardinality.

 

We cannot make the same claim about the substitutes conditions. Given a cardinal transfer function T and a revenue function R satisfying the substitutes condition, $R+T$ may or may not satisfy the condition. An example of the latter case has $T(A)=|A{|}^2$ for all $A\subset D$ and $R=0$⁠.

The main theorem of the current section states that cardinally concave transfer functions can re-establish the substitutes condition for those revenue functions satisfying both the exactly constrained substitutes condition and the chain-constrained substitutes condition, but not for any other revenue functions.

 

The theorem shows that cardinally concave transfer functions can re-establish the substitutes condition only for a specific class of revenue functions—those already close to being substitutable in that they satisfy the exactly constrained and chain-constrained substitutes conditions. Given that cardinally concave transfer functions appear to boost overall substitutability among the workers/objects, this result may be surprising.

Although the exactly constrained and chain-constrained substitutes conditions pose meaningful restrictions, they allow for interesting economic settings. Note from Proposition 8 that the only missing component of the substitutes condition is concavity in scale. For example, a firm may enjoy economies of scale because it exercises market power when large, while it views workers as otherwise substitutable. In an extreme case, the workers may be homogeneous, but the revenue as a function of the number of workers is strictly convex-extensible. In such cases, cardinally concave transfer functions non-trivially re-establishes the substitutes condition, and thus non-increasing returns to scale.

The following corollary strengthens the sufficiency part of Theorem 5. We say that a class of revenue functions $\mathcal{R}$ is bounded if $\{R(A):A\subset D\text{ and }R\in \mathcal{R}\}$ is bounded.

 

Assuming boundedness, Corollary 3 tells us that when re-establishment of the substitutes condition is possible, we can use one single cardinally concave transfer function to re-establish the substitutes condition for all firms. This observation partly alleviates the concern that the policymaker may need to customise transfer functions for different firms to re-establish the substitute condition for all of them.

7 DISCUSSION AND CONCLUSION

Studying markets for indivisible resources, this paper systematically examines the impact of transfer policies on the substitutability of demands, which carries far-reaching implications both theoretically and practically. We characterise which transfer policies, simple or complex, preserve the substitutes condition for all revenue functions satisfying the condition. In the job-matching language, such policies can have two parts: the additively separable part assigns a real number to each worker (which may depend on her salary) and sums up the numbers associated with hired workers to determine the transfer; the cardinally concave part lets the transfer depend on the total number of hired workers in a concave way.

Similarly, we present a series of characterisation results regarding which transfer policies preserve the substitutes condition for, respectively, all cardinally concave revenue functions, all group separable revenue functions, all group concave revenue functions, and so on. These classes of revenue functions pertain to economically interesting production technologies, so these results help better-informed policymakers determine whether substitutability is preserved by a transfer policy.

We also investigate how to re-establish the substitutes condition when it may not hold, characterising which revenue functions may have the condition re-established by cardinally concave transfer functions. The identified class is surprisingly small, but economically interesting due to an interpretation related to returns to scale. Other discoveries are made, including two equivalent renditions of the substitutes condition: Proposition 8 and Lemma OA.14 of the Online Appendix.

Our research informs policymakers and market designers of the impact of different transfer policies on substitutability of demands. When complementarity is worrisome, policymakers may think twice about a transfer policy failing to preserve the substitutes condition, and switch to a policy which preserves it, especially when two policies serve similar purposes. For example, affirmative action can be implemented through individual subsidies instead of subsidising an employer for hiring a large proportion of disadvantaged workers. When transfer policies are fixed and non-negotiable, our research predicts whether and how complementarity may emerge, that is, whether and how related issues such as the exposure problem may emerge. In such cases, market designers may need to update allocation mechanisms; and market participants may need to review strategies (e.g. to avoid falling prey to the exposure problem or to take advantage of others’ overcaution).

More broadly, a firm’s profit structure can be transformed not only by transfer policies but also via other factors such as transaction costs, the acquisition of another firm, the permission to enter another market, and the adoption of a new technology. Each of these can be modelled as the addition of a complex transfer function, so all insights this paper provides for transfer policies are transferrable to those economic phenomena.

To avoid overwhelming readers, we relegate some materials to the Appendix. Appendix A fully specifies the job matching model and models for object assignment and auctions. Appendix B explains how to incorporate constraints by combining results in KSY and the current paper. Appendix C strengthens the necessity parts of theorems characterising which transfer functions preserve the substitutes condition for three classes of revenue functions. Appendix D investigates a scenario in which transfer policies are not allowed to treat homogeneous objects in a group discriminately; and characterises which vectorial functions always preserve the vectorial substitutes condition, a vectorial form of the group concavity condition. On a related note, Appendix E introduces a new class of group separable plus concave revenue functions, which is quite inclusive and has a nice property: in such a case, profit maximisation is consistent with the firm delegating specific hiring decisions to the department level while only deciding on the headcount for each department. A Venn diagram for classes of revenue/transfer functions studied in this paper is drawn in Figure 1.

In Appendix F, the substitutes condition is formally shown to be critical for the existence of competitive equilibria in the presence of complex transfer policies; in particular, a maximum domain theorem (Theorem 8) is presented. Appendix G explains how our results are adaptable to more general settings in which “full substitutability” (Hatfield et al., 2019) can be assumed: trading networks (Hatfield et al., 2013, 2021), supply chains (Ostrovsky, 2008), intermediaries (Hatfield et al., 2013, 2019), markets with a structured form of complementarity (Sun and Yang, 2006, 2009), etc. Intuitively, fully substitutable “trades” can be interpreted as having underlying gross substitutable objects. In the same vein, each transfer policy on trades corresponds exactly to a policy on objects. Knowing which transfer policies preserve the substitutes condition is thus the same as knowing which ones preserve full substitutability. Fleiner et al. (2019) cover transfer policies in trading networks, and assume full substitutability under the policies; our work offers theoretical justification for the assumption.

There are still unanswered questions. Despite our best efforts, we are unable to prove the conjecture that Proposition 2 can be written as a characterisation, or to find the necessary restriction on C-group concave functions to make Proposition 5 a characterisation. Ideally, we shall figure out which complex transfer policies preserve the substitutes condition for all group concave revenue functions, or how to obtain a maximum domain theorem stronger than Theorem 8. Moreover, we are far from leaving no stone unturned, yet to consider all classes of revenue functions known to satisfy the substitutes condition; and new economically relevant classes may emerge in the future. Baldwin and Klemperer (2019) and Baldwin et al. (2020)²⁹ demonstrate “demand types” as a powerful approach to substitutability for indivisible resources; we plan to investigate how to apply the approach to study policy interventions in the future.

APPENDIX

A. Job matching, object assignment, and auctions

Appendix A, together with Section 2, explains the job matching model of Kelso and Crawford (1982) and object assignment and auction models (Gul and Stacchetti, 1999, 2000). These are standard in the market design literature but might not be familiar to general interest readers, so we present the full model to facilitate understanding.

A finite set of firms H interact in the labour market with a set of workers D. A matching is represented by a function $\mu :D\to \overline{H}$⁠, where $\overline{H}:=H\cup \{h_0\}$ and $h_0$ stands for unemployment. We abuse notation and let $\mu (h):={\mu }^{-1}(h)$ for every $h\in \overline{H}$⁠. The unemployment income schedule $s^{h_0}$ is fixed. An ordered pair of a matching and a salary schedule $(\mu ,s)$ specifies an allocation if $s_d=s_d^{h_0}$ for every d with $\mu (d)=h_0$⁠.

Each firm $h\in H$ faces a revenue function $R_h$ and a complex transfer function ${\mathrm{{\rm Y}}}_h$⁠. Its profit function, maximal profit function, and demand correspondence are explained in Subsection 5.1. A worker d who is matched to $h\in \overline{H}$ at salary $s\in \mathbb{R}$ enjoys utility  $U_{d,h}(s)$⁠. This excludes situations where workers care about the identity of their co-workers or the allocation of other workers in general. Assume that any $U_{d,h}$ is strictly increasing and continuous. A cooperative (coalitional) game can be defined accordingly (Kelso and Crawford, 1982).

An allocation $(\mu ,s)$ is individually rational if for any worker $d\in D$⁠, $U_{d,\mu (d)}(s_d)\ge U_{d,h_0}(s_d^{h_0})$⁠. A firm $h\in H$ and a set of workers $A\subset D$ form a blocking coalition against an allocation $(\mu ,s)$ if there exists a salary schedule $s^{\prime }\in {\mathbb{R}}^D$ such that (i) for any worker $d\in A$⁠, $U_{d,\mu (d)}(s_d)<U_{d,h}(s_d^{\prime })$⁠, and (ii) $V_h(\mu (h);s,R_h+{\mathrm{{\rm Y}}}_h)<V_h(A;s^{\prime },R_h+{\mathrm{{\rm Y}}}_h)$⁠. The following is consistent with classical treatment of the concept of core for cooperative games.

 

A salary system is an indexed family $S:H\to {\mathbb{R}}^D$ in the form of $(s^h{)}_{h\in H}$⁠. In a competitive equilibrium, all parties maximise their own utility/profit taking the salary system as given.

 

In this economy, a competitive equilibrium allocation is always a core allocation, and a core allocation is always (Pareto) efficient and can be supported by a salary system to form a competitive equilibrium. Non-existence of competitive equilibria thus entails instability: no core allocation exists.

In object assignment and auction models, workers are replaced by objects. Unemployment corresponds to unassigned objects. Each salary/price system assigns a single price to an object regardless of which firm/consumer receives it. With free disposal, all prices are non-negative (but not all models assume it). In a competitive equilibrium, the first requirement in Definition 8 becomes the price of unassigned objects being 0. Initial endowment is irrelevant to the definition and thus often disregarded. Alternatively, it might be assumed that there is a single seller who maximises the total payment (Ausubel and Milgrom, 2002), and then cooperative games are again well defined.

B. Job matching with constraints and transfers

Subsection 6.2, consistent with KSY, defines feasibility collections—which model constraints in an encompassing way—as well as generalised maximal profit functions and demand correspondences (facing both transfer functions and feasibility collections). A restricted revenue function  $(R,\mathcal{F})$ as an ordered pair of a revenue function and a feasibility collection satisfies the substitutes condition if the demand correspondence $X(\cdot ;R,\mathcal{F})$ satisfies it.

A hybrid policy is an ordered pair $(T,\mathcal{F})$ of a transfer function and a feasibility collection modelling constraints.

 

The following corollary can be obtained through combining the proofs of our Theorem 1 and KSY’s Theorem 1, which is a laborious but routine task. Two hybrid policies $(T,\mathcal{F})$ and $(T^{\prime },{\mathcal{F}}^{\prime })$ are equivalent if $\mathcal{F}={\mathcal{F}}^{\prime }$⁠, and for all $A\in \mathcal{F}$⁠, $T(A)=T^{\prime }(A)$⁠. They bear the same economic consequence.

 

For the necessity part of the corollary, we cannot conclude that T should be the sum of an additively separable function and a cardinally concave function because for any $A\in 2^D\setminus \mathcal{F}$⁠, the value of $T(A)\in \mathbb{R}$ can be arbitrarily assigned.

Similarly, other results in the current paper can be combined with those of KSY.

C. Strengthening the necessity parts of theorems

The necessity part of Theorem 1 can be strengthened as follows. A unit-demand revenue function R is binary unit-demand if there exist $d,d^{\prime }\in D$ and $\alpha >0$ such that $R(A)=\alpha min\{1,|A\cap \{d,d^{\prime }\}|\}$ for each $A\subset D$⁠.³¹ In other words, the revenue is $\alpha >0$ if one of the two workers d and $d^{\prime }$ is hired, and 0 otherwise; this is arguably the simplest form of substitutability between d and $d^{\prime }$⁠. Proposition 10 shows that preserving the substitutes condition for all binary unit-demand revenue functions implies that a transfer function can be decomposed into an additively separable part and a cardinally concave part.

 

It must be emphasised that the same conclusion as Proposition 10 can also be established for other small classes of revenue functions as well. A trivial example is a class obtained from adding an additively separable revenue function to all binary unit-demand revenue functions (a simple application of Proposition 1 proves the result). Such flexibility suggests that it is not easy to overcome the necessity part of Theorem 1 by excluding a subclass of revenue functions from consideration.

Consequently, when a policymaker is uninformed of the details of production technologies (revenue functions) or bound to apply the same policy to many different firms, a transfer policy failing to always preserve the substitutes condition easily runs the danger of causing problems that arise when the condition fails.

The necessity part of Theorem 2 can be strengthened as follows. To rule out triviality, we assume that there exists a group with at least two workers. We say that a binary unit-demand revenue function is within-group if its two associated workers are within the same group. A within-group binary unit-demand revenue function is group separable.

 

The necessity part of Theorem 3 can be strengthened as follows. A revenue function R is spline concave in $A\subset D$ with $A\ne \mathrm{\varnothing }$ if there exists a function $f:[0,|A|{]}_{\mathbb{Z}}\to \mathbb{R}$⁠, $m^{*}\in [1,|A|-1{]}_{\mathbb{Z}}$⁠, and $\alpha >0$ such that $f(m)=\alpha min\{m,m^{*}\}$ for each $m\in [0,|A|{]}_{\mathbb{Z}}$⁠, and $R(B)=f(|A\cap B|)$ for each $B\subset D$⁠.³² In words, if the revenue function is spline concave in a set, every additional worker in the set generates the same positive revenue for the firm until a quota is met. We say that a spline concave revenue function in some $P\in \mathcal{P}$ is uni-group; when it is in $D\setminus P$⁠, the complement of some $P\in \mathcal{P}$⁠, we say it is $\overline{\text{uni}}$-group.

Revenue functions that are uni- or $\overline{\text{uni}}$-group spline concave form a small subclass of group concave revenue functions. In general, preserving the substitutes condition for them dictates a transfer function to be the sum of a group separable function and a cardinally concave function.

 

D. The vectorial substitutes condition

We say that a vectorial function (defined in Section 4) $U:\tau (2^D)\to \mathbb{R}$ satisfies the vectorial substitutes condition if it is associated with a group concave revenue function R. Note that R’s domain is the power set of D while U’s domain contains vectors each representing the numbers of workers hired from different groups, though they are closely related. The condition is commonly used to model substitutability given homogeneous goods within groups: Milgrom and Strulovici (2009) call it the “strong-substitutes valuation” and list many applications such as the allocation of airport landing slots.

Mathematically, the vectorial substitutes condition is a more general concept than the substitutes condition. To see this, consider a situation in which we are given the finest partition $\mathcal{P}=\{\{d\}:d\in D\}$⁠, so τ becomes a bijection. Accordingly, a revenue function satisfying the substitutes condition can be viewed as a vectorial function satisfying the vectorial substitutes condition.

We study which vectorial functions always preserve the vectorial substitutes condition. In essence, answering this question tells us which group cardinal transfer functions preserve the substitutes condition for all group concave revenue functions.³³

 

A vectorial function W is V-additively separable if there exists a family of functions $\{f_P{\}}_{P\in \mathcal{P}}$ such that $f_P:[0,|P|{]}_{\mathbb{Z}}\to \mathbb{R}$ is concave-extensible for each $P\in \mathcal{P}$⁠, and $W(z)=\sum _{P\in \mathcal{P}}{f}_P(z(P))$ for each $z\in \tau (2^D)$⁠. When the partition is the finest, this concept is equivalent to the additive separability of transfer functions.

Abusing notation, for any $z\in {\mathbb{Z}}^{\mathcal{P}}$ and any collection of groups $\mathcal{Q}\subset \mathcal{P}$⁠, we denote the number of workers in $\cup \mathcal{Q}$ by $|z(\mathcal{Q})|:=\sum _{P\in \mathcal{Q}}z(P)$⁠, and the total number by $|z|:=|z(\mathcal{P})|$⁠. A vectorial function $W:\tau (2^D)\to \mathbb{R}$ is V-cardinally concave if there exists a concave-extensible function $f:[0,M{]}_{\mathbb{Z}}\to \mathbb{R}$ such that $W(z)=f(|z|)$ for each $z\in \tau (2^D)$⁠.³⁴

The next theorem tells us that the class identified above contains all vectorial functions that always preserve the vectorial substitutes condition.

 

Analogous to Propositions 10–12, Proposition 13 highlights the restrictiveness of the requirement of preserving the vectorial substitutes condition by focusing on a small class of vectorial functions. A vectorial function U is V-$\overline{\text{uni}}$-group spline concave if it is associated with a $\overline{\text{uni}}$-group spline concave revenue function. It is straightforward to show that V-additively separable, V-cardinally concave, and V-$\overline{\text{uni}}$-group spline concave vectorial functions all satisfy “M${}^{\mathrm{♮}}$-concavity,” which is equivalent to the vectorial substitutes condition (see Online Appendix OA.1 and, Murota, 2003).

 

Interestingly, the class of vectorial functions identified here is closed under addition, similar to the class of transfer functions identified by Proposition 10. In addition, the transfer function counterpart of this proposition, Proposition 12, features preserving the substitutes condition for all uni-group spline concave revenue functions, not only $\overline{\text{uni}}$-group spline concave revenue functions; the relaxation here is due to the inability of vectorial functions to discriminate among within-group workers.

When $|\mathcal{P}|=2$⁠, the characterisation for always preserving the vectorial substitutes condition is simple.

 

It has long been known that the class of all functions satisfying the vectorial substitutes condition is not closed under addition, so the fact that it is for the case of $|\mathcal{P}|=2$ may be surprising.

When the partition is the finest, i.e. every worker forms a group, Theorem 6 (as well as Proposition 14) degenerates into Theorem 1, so it is mathematically more general.

E. Delegation of hiring decisions

A by-product of our research is the discovery of a new class of revenue functions satisfying the substitutes condition. We say that a revenue function $S:2^D\to \mathbb{R}$ is group separable plus concave if $S=S^1+S^2$⁠, where $S^1$ is group separable and $S^2$ is group concave. By Theorem 2, group separable plus concave revenue functions satisfy the substitutes condition. They form a large subclass of revenue functions satisfying the substitutes condition, encompassing most subclasses mentioned in this paper as shown in Figure 1.³⁵ Such an S may originate from adding a group concave transfer function to a group separable revenue function, or adding a group separable transfer function to a group concave revenue function.

Large organisations often delegate hiring decisions to their departments, possibly because headquarters often lack the expertise and/or information to measure revenue impacts of particular candidates. We now demonstrate that the delegation is compatible with profit maximisation when the revenue function is group separable plus concave.

Let the firm maximise profit $V(\cdot ;s,S)$⁠, where $s$ is a salary schedule and S is group separable plus concave as defined above. There is a sense in which the firm can delegate most hiring decisions to the department level: each department hires workers from a particular group, while it only decides how many workers each department should hire, based on an optimisation problem in the domain of $\tau (2^D)$⁠.

Let $\{S_P^1{\}}_{P\in \mathcal{P}}$ be associated with $S^1$ and W be the vectorial function associated with $S^2$⁠. Given $s$⁠, imagine a department that hires workers from $P\in \mathcal{P}$ solving the following constrained optimisation problem for each $m\in [0,|P|{]}_{\mathbb{Z}}$⁠:

In words, each department figures out, for every possible exact quota imposed on them, its profit and demand sets.

The optimisation problem at the firm level can now be written:

The maximiser $z^{*}$ can then be used to dictate the exact quota for each group P as $z^{*}(P)$⁠, while the department associated with P employs any set in $X_P(z^{*}(P))$ accordingly. The union of such sets across $\mathcal{P}$ is an optimal solution to the firm’s profit maximisation problem.

It is quite appealing that the firm can achieve optimality without knowing $\{S_P^1{\}}_{P\in \mathcal{P}}$ or $s$⁠. Through delegation of specific hiring decisions to the department level, it only needs to optimise based on W and $\{{\mathrm{\Pi }}_P{\}}_{P\in \mathcal{P}}$⁠, and each ${\mathrm{\Pi }}_P$ can be reported by the associated department. This process may provide a suitable model of hiring decisions of a large organisation, where the top-level management determines “headcounts” for its units but not whom to fill the positions with.

F. The existence of competitive equilibria

Classical equilibrium existence results for job matching (or object assignment) such as Kelso and Crawford (1982) and Gul and Stacchetti (1999), which show that the substitutes condition is sufficient for equilibrium existence and also “necessary” in the maximal domain sense, are derived in settings where the preferences of employers (or bidders) are quasilinear in salaries (or prices). Simple transfer policies maintain this assumption, and thus the classical results continue to hold. Complex ones may invalidate the quasilinearity assumption, because they may depend on salaries in a nonlinear manner. Appendix F provides formal results to demonstrate that the substitutes condition is still critical in a job matching model with transfer policies (see Appendix A).

To guarantee the existence of competitive equilibria, complex transfer functions have to satisfy two natural regularity conditions. We say that a complex transfer function $\mathrm{{\rm Y}}$ is proper if (i) given any fixed $A\subset D$⁠, $\mathrm{{\rm Y}}(A,s)$ as a function of $s\in {\mathbb{R}}^D$ is continuous; and (ii) for any $\mathrm{\Xi }>0$ and $d\in D$⁠, there exists ${\mathrm{\Delta }}_d>0$ such that for all $s\in {\mathbb{R}}^D$⁠, $s_d>{\mathrm{\Delta }}_d$ implies $s_d-\mathrm{{\rm Y}}(A\cup \{d\},s)+\mathrm{{\rm Y}}(A,s)>\mathrm{\Xi }$ for all $A\subset D$ with $d\notin A$⁠. Given the requirement for a complex transfer function that overall hiring cost is strictly increasing in the salaries of hired workers, the first requirement of properness essentially forbids the overall hiring cost to jump up as salaries increase. The second rules out pathological cases of hiring a worker with an extremely high salary. The term $s_d-\mathrm{{\rm Y}}(A\cup \{d\},s)+\mathrm{{\rm Y}}(A,s)$ is the marginal cost of hiring d under $\mathrm{{\rm Y}}$⁠, so properness requires that when $s_d$ is sufficiently large, it is never optimal to hire d. If either one fails, even for the simple case of there being only one worker, it is easy to construct examples in which a competitive equilibrium fails to exist.

 

The proof can be copied verbatim from Kelso and Crawford (1982).

Now we introduce a maximal domain result which showcases the “necessity” of always preserving the substitutes condition. Because the space of proper complex transfer functions is unwieldy, we restrict our attention to a large subspace.

A demand correspondence $X(\cdot ;R+\mathrm{{\rm Y}})$  satisfies the law of maintained demand if for all $s\in {\mathbb{R}}^D$⁠, $A\in X(s;R+\mathrm{{\rm Y}})$⁠, and $s^{\prime }\le s$ with $s^{\prime }{|}_{D\setminus A}=s{|}_{D\setminus A}$⁠, we have $A\in X(s^{\prime };R+\mathrm{{\rm Y}})$⁠. In words, a demand set at a salary schedule should still be a demand set when salaries of workers within it decrease and all others remain the same. We say a complex transfer function $\mathrm{{\rm Y}}$  respects the law of maintained demand if for every revenue function R satisfying the substitutes condition, $X(\cdot ;R+\mathrm{{\rm Y}})$ satisfies the law of maintained demand. The space of all complex transfer functions which respect the law of maintained demand is large: for example, it contains the sum of an arbitrary transfer function and an arbitrary C-additively separable complex transfer function.

The following maximum domain theorem works with the space of all proper complex transfer functions which respect the law of maintained demand.

 

Theorem 8, combined with Theorem 7, tells us that within the space of all complex transfer functions which respect the law of maintained demand, those which always preserve the substitutes condition are exactly those safely implementable in a market with substitutes. Failure to always preserve the substitutes condition may endanger equilibrium existence and stability.

The proof of Theorem 8 is already quite complicated. Outside the space considered, a complex transfer function is so complex that we are unable to obtain tractable results. At the very least, the substitutes condition implies the existence of a competitive equilibrium, and stands as a built-in feature of many prominent algorithms such as the classical deferred-acceptance algorithm of Kelso and Crawford (1982); these should be enough reasons for choosing policies to preserve it when possible and at least alerting relevant parties to its potential failure.

G. Preserving full substitutability

Appendix G explains how the results of the current paper naturally translate into those concerning full substitutability, a condition central for the theoretical study of a wide range of research topics including matching, auctions, and trading networks (Sun and Yang, 2006, 2009; Ostrovsky, 2008; Hatfield et al., 2013, 2019; Fleiner et al., 2019). To facilitate comparison, the notations below synthesise those of Hatfield et al. (2019) and the current paper.

A firm faces a set of trades Ω with $|\mathrm{\Omega }|=M$⁠. The set Ω is partitioned into upstream trades  ${\mathrm{\Omega }}_{\uparrow }$ and downstream trades  ${\mathrm{\Omega }}_{\downarrow }$⁠, the former representing cases in which the firm is the buyer and the latter representing cases in which it is the seller. For each $\mathrm{\Psi }\subset \mathrm{\Omega }$⁠, we denote ${\mathrm{\Psi }}_{\uparrow }:=\mathrm{\Psi }\cap {\mathrm{\Omega }}_{\uparrow }$ and ${\mathrm{\Psi }}_{\downarrow }:=\mathrm{\Psi }\cap {\mathrm{\Omega }}_{\downarrow }$⁠. A trade revenue function  $u:2^{\mathrm{\Omega }}\to \mathbb{R}$ maps each subset of trades to the revenue of the firm if it executes them; a trade transfer function  $v:2^{\mathrm{\Omega }}\to \mathbb{R}$ maps each subset of trades to the amount of transfer the firm receives. A price schedule is a real-valued function $p:\mathrm{\Omega }\to \mathbb{R}$⁠; for each trade $\omega \in \mathrm{\Omega }$⁠, $p_w$ is short for $p(\omega )$⁠.

If the firm executes $\mathrm{\Psi }\subset \mathrm{\Omega }$ while facing a price schedule $p$⁠, a trade revenue function u, and a trade transfer function v, its trade profit is

that is, its revenue plus the transfer plus the sum of prices received from the downstream buyers minus the sum of prices paid to the upstream sellers. We define the maximal trade profit function  $\tilde{\mathrm{\Pi }}(\cdot ;u+v):{\mathbb{R}}^{\mathrm{\Omega }}\to \mathbb{R}$ and the trade demand correspondence  $\tilde{X}(\cdot ;u+v):{\mathbb{R}}^{\mathrm{\Omega }}\to \{\mathcal{A}:\mathcal{A}\subset 2^{\mathrm{\Omega }}\text{ and }\mathcal{A}\ne \mathrm{\varnothing }\}$ such that for each price schedule $p$⁠,

Each element of $\tilde{X}(p;u+v)$ is referred to as a trade demand set.

The following definition is called “demand-language contraction fully substitutable” by Hatfield et al. (2019, Definition A.4), which is equivalent to various other definitions of full substitutability.

 

As stated above, the first requirement of full substitutability is that given any trade demand set, if the prices of some upstream trades go up (while other prices remain the same), then there exists a new trade demand set (at the new price schedule) which contains all upstream trades in the original demand set whose prices remain the same and does not contain any downstream trades not in the original demand set. The second requirement states that given any trade demand set, if the prices of some downstream trades drop (while other prices remain the same), then there exists a new trade demand set which contains all downstream trades in the original demand set whose prices remain the same and does not contain any upstream trades not in the original demand set.

Given the importance of the condition, we pose the following question: exactly which trade transfer functions preserve full substitutability?

 

Fortunately, all such questions concerning full substitutability can be answered from what we know about the substitutes condition, because these two conditions are closely related.

Fix a bijection $t:\mathrm{\Omega }\to D$⁠. Such t points out the concrete worker (or indivisible object) behind each trade. Given a revenue function R, we say that a trade revenue function $u^R$  derives from  R if for all $\mathrm{\Psi }\subset \mathrm{\Omega }$⁠, $u^R(\mathrm{\Psi })=R(t({\mathrm{\Psi }}_{\uparrow })\cup t({\mathrm{\Omega }}_{\downarrow }\setminus {\mathrm{\Psi }}_{\downarrow }))$⁠. Similar to trade revenue functions, a trade transfer function can be derived from any transfer function.

It is easy to see that given a trade revenue function u, there exists a unique revenue function $R^u$ which u derives from: $R^u(A)=u((t^{-1}(A){)}_{\uparrow }\cup ({\mathrm{\Omega }}_{\downarrow }\setminus (t^{-1}(A){)}_{\downarrow }))$ for all $A\subset D$⁠. In addition, if two derived revenue functions u and $u^{\prime }$⁠, respectively, derive from R and $R^{\prime }$⁠, then $u+u^{\prime }$ derives from $R+R^{\prime }$⁠.

The following theorem is well known in the literature, listed as Theorem 8 of Hatfield et al. (2019).

 

We say that a trade transfer function is derived cardinally concave if it derives from a cardinally concave transfer function. Such a trade transfer function demands the transfer to depend only on the firm’s total number of workers/objects implied by the set of executed trades, in a concave-extensible way. Other classes of trade revenue/transfer functions can be similarly defined.

A corollary of our Theorem 1 provides the characterisation of all trade transfer functions which always preserve full substitutability.

 

In such a manner, all other results in this paper concerning the substitutes condition can be translated to ones concerning full substitutability.

Acknowledgments

Kojima, Sun, and Yu are co-first authors. They thank Vincent Crawford, Federico Echenique, Yuichiro Kamada, Jinwoo Kim, Paul Milgrom, Kazuo Murota, Alvin Roth, Akiyoshi Shioura, Bruno Strulovici, Zaifu Yang, Jun Zhang, Yu Zhou, two anonymous referees, and Editor Bård Harstad for helpful comments, and Yutaro Akita, Nanami Aoi, Ashley Dreyer, Yusuke Iwase, Masanori Kobayashi, Haruki Kono, Kevin Li, Leo Nonaka, Ryosuke Sato, Ryo Shirakawa, and Yutong Zhang for research assistance. We incorporated feedbacks from seminar and conference participants at Seoul National University, Stanford University, Peking University, 2019 Asian Meeting and 2020 World Congress of the Econometric Society, etc. Kojima acknowledges financial support from JSPS KAKENHI Grants-In-Aid 21H04979; Sun from NSFC Grant 72033004 and JSPS KAKENHI Grants-In-Aid 21H00696; Yu from NSFC Grants 72073072 & 72192800 and the WU Jiapei Award for Information Economics E20103521.

Supplementary Data

Supplementary data are available at Review of Economic Studies online.

References

Footnotes

Author notes