Rationalizing Path-Independent Choice Rules

Path independence is a fundamental property of combinatorial choice rules. For example, consider a firm that needs to choose a subset from a set of available contracts. We say that the firm’s choice rule is path independent if the chosen set of contracts from any set remains unchanged when the firm divides the set into segments, applies the rule to each segment first, and then applies the rule to the combined set of chosen contracts from all segments. This property is desirable for at least two reasons. First, without path independence, the set of chosen contracts can depend on the order in which contracts are reviewed. Therefore, firms whose choice rules are not path independent may not only regret rejecting offers but also may suffer from the malpractice of favoritism and other manipulations. Second, path independence is intimately related to other well-known properties of interest: A choice rule is path independent if and only if it satisfies the substitutes condition and the irrelevance of rejected contracts (Aizerman and Malishevski, 1981).

Plott (1973) introduces path independence as a property of social choice formalizing an idea in Arrow’s book Social Choice and Individual Values. Although originating in social choice, path independence has found applications in different areas of economic theory, such as market design and decision theory. For example, in two-sided matching markets, when agents have path-independent choice rules, a stable matching exists (Blair, 1988).¹¹1The substitutes condition is not sufficient for the existence of a stable matching when choice rules are the primitive of the model rather than utility functions or preferences. See the discussion in Aygün and Sönmez (2013) and Chambers and Yenmez (2017). In decision theory, path independence and its stochastic versions have been studied extensively (Kalai and Megiddo, 1980).²²2See also Machina and Parks (1981) and a recent treatment by Ahn et al. (2018) Path independence has also been studied in other fields, such as discrete mathematics, law, philosophy, and systems design.³³3For discrete mathematics see Danilov and Koshevoy (2005) and Gratzer and Wehrung (2016), for law Chapman (1997) and Hammond and Thomas (1989), for philosophy Rott (2001) and Stewart (2022), and for systems design Levin (1998).

Economic agents are usually modeled as utility maximizers: They have a utility function and, given a set of contracts, they choose a subset with the highest utility. An alternative approach is to endow agents with choice rules, for example, when agents do not necessarily have a well-defined utility function or when the utility function is not observable.⁴⁴4For example, choice rules are used to model diversity policies of schools (Hafalir et al., 2013; Ehlers et al., 2014; Echenique and Yenmez, 2015). A fundamental question linking these two approaches is whether a choice rule is rationalizable by a utility function so that the choice from any set of contracts is the subset with the highest utility among all subsets. Results of this nature that connect choice rules with certain properties to utility functions with corresponding properties are called rationalization theorems.⁵⁵5It is, in general, useful to identify rationalization of given choice rules by preference relations or utility functions as an intellectual foundation for almost all economic analysis using preference relations or utility functions. See, for example, Chapter 1 of Mas-Colell et al. (1995). We provide rationalization theorems for path independent choice rules.

First, we show that a choice rule is path independent if and only if it is rationalizable by a utility function satisfying ordinal concavity (Theorem 1). Ordinal concavity is a property introduced in Murota and Shioura (2003) to study discrete optimization problems.⁶⁶6Murota and Shioura (2003) introduce semi-strict quasi M-concavity (SSQM-concavity) as an ordinal implication of M-concavity. M-concavity is a cardinal notion, and it has a weaker variant called M^♮-concavity. Analogous to weakening M-concavity to M^♮-concavity, SSQM^♮-concavity is the natural counterpart of SSQM-concavity (see Murota and Shioura (2024)). Ordinal concavity is equivalent to SSQM^♮-concavity. Roughly, it requires that when two sets of contracts are made closer to each other, the value of the utility function either increases on at least one side or remains unchanged on both sides. In this context, getting closer may either mean adding or removing a contract to or from the original set that we start with or the existence of a second contract such that we add one of the contracts and remove the other one.

Hafalir et al. (2022b) show that ordinal concavity is implied by M^♮-concavity,⁷⁷7See also Murota and Shioura (2024). which is a standard notion of concavity used in the discrete convex analysis literature. Fujishige and Yang (2003) show that the gross substitutes property of Kelso and Crawford (1982) is equivalent to M^♮-concavity.⁸⁸8M^♮-concavity is also equivalent to the single-improvement property introduced by Gul and Stacchetti (1999); see Corollary 19 of Murota and Tamura (2003). Therefore, one implication of our result is that the difference between the gross substitutes property and the substitutes condition (or path independence) can be attributed to the difference between M^♮-concavity and ordinal concavity.⁹⁹9To be more precise, this statement holds for rationalizable choice functions that satisfy the substitutes condition and for path-independent choice rules. In fact, these two classes of choice rules are the same.

Submodularity is another well-known condition that is often associated with a variety of substitutability notions. Indeed, M^♮-concavity, or equivalently the gross substitutes condition, implies submodularity (Murota and Shioura, 2001). Likewise, supermodularity is used to study complementarities in different settings (Topkis, 1998). For instance, Rostek and Yoder (2020) show that supermodularity of a utility function implies that the induced choice rule satisfies a notion of complementarities.¹⁰¹⁰10The setting in Rostek and Yoder (2020) is different from ours in that they allow for externalities in a multi-agent setting. Their Lemma 1 shows that when the utility function is quasisupermodular and satisfies a single-crossing condition, the choice rule has complementarities. Quasisupermodularity is an ordinal implication of supermodularity, and the single-crossing condition is trivially satisfied when there are no externalities as in our setting. Analogously, one could conjecture that submodularity implies the substitutes condition. However, submodularity and ordinal concavity are logically unrelated, and in fact rationalizability by a submodular function does not imply the substitutes condition or path independence.¹¹¹¹11See Claims 1 and 2. We also show that M^♮-concavity and other related notions fail to give the desired rationalization result (see Section 4). At a high level, one of our contributions is to identify an appropriate condition on utility functions that is tightly connected with path independence and the substitutes condition (Theorem 1).

In the market-design literature, another choice rule property that plays a crucial role is the law of aggregate demand (Hatfield and Milgrom, 2005). The law of aggregate demand states that when a larger set of contracts becomes available, the number of chosen contracts weakly increases. The law of aggregate demand, together with path independence, yields numerous results. It implies, for instance, the rural hospitals theorem in two-sided matching markets, which states that the number of contracts an agent gets is the same across all stable matchings (Fleiner, 2003). In addition, in the doctor-hospital matching problem, a generalization of the doctor-proposing deferred-acceptance mechanism of Gale and Shapley (1962) is strategy-proof for doctors (Hatfield and Milgrom, 2005).

In our second result, we show that a choice rule satisfies path independence and the law of aggregate demand if and only if it is rationalizable by a utility function that satisfies ordinal concavity and size-restricted concavity (Theorem 2). Size-restricted concavity is a concept of discrete concavity with a quantifier such that the implication is required only for sets of contracts with different sizes. Figure 1 illustrates the relationships between choice rules that are rationalizable by utility functions satisfying different notions of concavity.

Path independence and the law of aggregate demand are testable conditions on individual choice. Consider a data set consisting of observed choices of a decision maker, which may or may not include choices from all possible bundles. If there is a violation of path independence in the data, then we can refute the theory that the decision maker has a utility function satisfying ordinal concavity. Likewise, if there is a violation of the law of aggregate demand (even when there is no violation of path independence), then we can refute the theory that the decision maker has a utility function that satisfies ordinal concavity and size-restricted concavity.

The main difference between our work and the classical literature on social choice is that we assume the utility function (or the preference relation) is over sets of contracts, whereas in the classic setting, the utility function (or the preference relation) is over individual contracts (see Moulin (1985) for a summary). Likewise, our choice rule is combinatorial,¹²¹²12Combinatorial choice is a common characteristic of many allocation problems in the real world. It plays a crucial role in combinatorial auctions (Cramton et al., 2006; De Vries and Vohra, 2003), land allocation (Bleakley and Ferrie, 2014), and allocation of airport landing slots (Schummer and Vohra, 2013), among other cases. See Milgrom (2017) who provides in-depth discussions of practical examples and highlights the importance of the combinatorial nature of many allocation problems. whereas in the classical setting, multiple contracts represent the indecision of the agent, and the agent is eventually assigned only one contract. Therefore, our results are independent of the social choice literature on rationalizability.¹³¹³13At the same time, we note that the appeal of path independence as a normatively desirable property is not affected by these differences, and hence is as relevant in our combinatorial choice context as in the classical setting. Recall our discussion in the first paragraph of the Introduction for the interpretation of path independence in our context.

Even though path independence has been studied in the context of combinatorial choice (e.g., Echenique (2007) and Alva (2018)), there are only a few papers that study rationalizability of these choice rules. In a recent work, Yang (2020) shows that path-independent choice rules are rationalizable,¹⁴¹⁴14For a detailed discussion of rationalizability of path-independent choice rules, see Section 5 of Yang (2020) as well as Alva (2018). but he does not provide necessary or sufficient conditions for a utility function to ensure that the corresponding choice rule satisfies path independence. Less relatedly, Chambers and Echenique (2018) consider a setting with continuous transfers and characterize combinatorial demand functions that can be rationalized by quasi-linear preferences, through continuity and the law of demand.

One of the major contributions of our paper is to establish a close connection between choice rules in economics and concavity concepts in discrete mathematics. This connection allows us to shed light on economic problems with discrete optimization techniques. For instance, in an abstract setting, Eguchi et al. (2003) show that choice rules that are rationalizable by M^♮-concave functions satisfy path independence and Murota and Yokoi (2015) show that they satisfy the law of aggregate demand. On an applied front, Kojima et al. (2018) build upon their results to find M^♮-concave functions that rationalize a variety of practically relevant choice rules and establish their desirable properties including computational efficiency. Hafalir et al. (2022b) establish connections between ordinal concavity and choice rules in markets with dual objectives such as college admissions where diversity and meritocracy are typical goals. While advancing this research program further, the present paper is distinctive in that it provides conditions of discrete concavity that are equivalent to rationalizability of desirable choice rules, thus giving a complete answer to a foundational issue in this research agenda.

There is also a significant literature on menu choice (where a menu is a set of items or contracts). In this literature, a decision maker has preferences over menus anticipating consumption of an item from the available menu in the future. In this context, Kreps (1979) provides a model of preferences for flexibility and a representation of such preferences using state-dependent utility functions over individual items.¹⁵¹⁵15Other notable papers include Gul and Pesendorfer (2001) who provide a model of temptation and Dekel et al. (2001) who study an extension of Kreps (1979) that also allows preferences for commitment. Although the decision maker in the menu choice literature ultimately consumes just one item, subsets of items or contracts arise naturally as the objects of interest as the decision maker has preferences and associated choice behavior over them, leading to a combinatorial problem such as ours.

The rest of the paper is organized as follows. We define choice rules and their properties in Section 2, present our rationalization results in Section 3, discuss rationalizability by a utility function satisfying concavity notions other than ordinal concavity in Section 4, and conclude in Section 5. We provide all proofs in the Appendix.

Let $\mathcal{X}$ denote a finite set of contracts. A choice rule is a function $C:2^{\mathcal{X}}\rightarrow 2^{\mathcal{X}}$ such that, for any $X\subseteq\mathcal{X}$, we have $C(X)\subseteq X$.¹⁶¹⁶16In a typical model, $C$ is a choice rule of a single agent and $\mathcal{X}$ is the set of contracts that the agent can sign. We allow the agent to have multiple contracts with the same partner as in Alkan and Gale (2003) and Hatfield and Kominers (2012). Hatfield and Kominers (2012) consider a discrete setting like ours whereas Alkan and Gale (2003) allow fractional allocations. We study two key properties of choice rules.

Path independence plays a fundamental role in social choice, market design, and decision theory.¹⁷¹⁷17Path independence is equivalent to the following condition: for any $X,X^{\prime}\subseteq\mathcal{X}$, $C(X\cup X^{\prime})=C(C(X)\cup C(X^{\prime}))$ (Plott, 1973, Theorem 1). It has also been used in different areas such as discrete mathematics, law, philosophy, and systems design.¹⁸¹⁸18See the references in the Introduction.

As explained in the Introduction, path independence has a normative interpretation on its own. Moreover, it is equivalent to two properties that are commonly assumed in market design. A choice rule $C$ satisfies the substitutes condition (Roth and Sotomayor, 1990) if, for any $X,X^{\prime}\subseteq\mathcal{X}$,

A choice rule $C$ satisfies irrelevance of rejected contracts (Aygün and Sönmez, 2013) if, for any $X,X^{\prime}\subseteq\mathcal{X}$,

It is well known that a stable matching exists if the choice rule of every agent satisfies the substitutes condition and the irrelevance of rejected contracts.¹⁹¹⁹19Roth and Sotomayor (1990) show this result in a model of matching without contracts (i.e., there exists exactly one contract associated with each pair of a firm and a worker). Hatfield and Milgrom (2005) generalize the result to a setting with contracts. Aygün and Sönmez (2013) point out that the result goes through only under irrelevance of rejected contracts, a condition that the proof of Hatfield and Milgrom (2005) uses without explicitly assuming. Therefore, path independence guarantees the existence of stable matchings in two-sided markets (Blair, 1984).

We next introduce another important property in market design called the law of aggregate demand.²⁰²⁰20Alkan (2002) calls it cardinal monotonicity and Alkan and Gale (2003) call it size monotonicity. These papers address matching problems without contracts, while our results hold for general matching problems with contracts.

The law of aggregate demand, together with path independence, produces classic results such as the rural hospitals theorem (Fleiner, 2003) and strategy-proofness of a generalization of the doctor-proposing Gale-Shapley deferred-acceptance mechanism for doctors (Hatfield and Milgrom, 2005).

A utility function $u:2^{\mathcal{X}}\rightarrow\mathbb{R}$ assigns a value to every set of contracts.²¹²¹21$\mathbb{R}$ represents the set of real numbers. A choice rule $C$ is rationalizable by a utility function $u$ if, for any $X\subseteq\mathcal{X}$,

In other words, when a choice rule is rationalizable by a utility function, from any set of available contracts, the choice rule selects the unique subset with the highest utility.

In this section, we provide two rationalization theorems using utility functions that satisfy notions of discrete concavity. To define these notions, we introduce some notation. For any $X\subseteq\mathcal{X}$ and $x\in\mathcal{X}$, let $X+x=X\cup\{x\}$ and $X-x=X\setminus\{x\}$. Similarly, for any $X\subseteq\mathcal{X}$, let $X+\emptyset=X$ and $X-\emptyset=X$.

In other words, ordinal concavity requires that when $X$ is brought closer to $X^{\prime}$ by removing $x$ and adding $x^{\prime}$, and $X^{\prime}$ is brought closer to $X$ by adding $x$ and removing $x^{\prime}$, either at least one of the two function values strictly increases or both values remain unchanged.

Our main result is a rationalization theorem for path-independent choice rules.

The if direction easily follows from the existing literature, although we provide a self-contained proof.²²²²22See Theorem 2 of Hafalir et al. (2022b). Our main contribution is to show the only-if direction.²³²³23In Section 4, we show that the only-if direction does not hold for other concavity notions used in prior work. We note that this direction is an existence result, and its proof is constructive. In what follows, we give the main idea of our construction.²⁴²⁴24The proof presented in the main text is based on a suggestion made by one of the anonymous referees. We gratefully acknowledge their helpful comment. The Online Appendix provides our original proof.

Our utility function construction relies on the decomposition lemma of Aizerman and Malishevski (1981): for any path-independent choice rule, there exists a finite sequence of linear orders $\{\succ_{i}\}_{i=1}^{m}$ over contracts such that the choice from each set $X$ is given by the union of the most-preferred contracts according to each linear order $\succ_{i}$ (a formal statement of this lemma is given in Appendix A).²⁵²⁵25Chambers and Yenmez (2017) use the decomposition lemma to make a connection between the theory of path-independent choice rules and matching theory and utilize this connection to advance both fields. To represent each order $\succ_{i}$ numerically, we construct a value function $v_{i}$ over contracts that assigns a higher value to a more preferred contract according to $\succ_{i}$. We define the utility from a set $X$ by the weighted sum of the highest contract values among $X$ according to $v_{i}$ for each $i=1,\dots,m$. Then, for any $X$, the derived utility function assigns the highest utility to the chosen set $C(X)$ among all subsets of $X$, because $C(X)$ collects the most-preferred (equivalently, highest-valued) contracts according to each order $\succ_{i}$. Using this observation, we show that the utility function rationalizes $C$ (see step 2 in Section A.1.2).²⁶²⁶26Precisely speaking, we need to modify the utility function so that the utility from a set $X$ is smaller than that from $C(X)$ when $X\supsetneq C(X)$. See the construction of $\tilde{u}$ in equation 4. This formulation is also useful for establishing ordinal concavity because the highest contract value among a set is tractable when we add or remove one contract from the set (see step 3 in Section A.1.2).

Mathematically, the construction is similar to that of Kreps (1979) in the sense that a rationalizing utility function is defined by the weighted sum of the maximum values of multiple functions. We note that there are at least two differences between Kreps’ model and ours. First, Kreps takes a preference over sets of contracts as primitive, while we take a choice rule as primitive. Second, Kreps assumes monotonicity of preferences in the sense that the agent prefers any set to its subsets, which cannot hold for utility functions rationalizing some path-independent choice rules.²⁷²⁷27For example, let $\mathcal{X}=\{x,y\}$ and, for any $X\subseteq\mathcal{X}$ with $x\in X$, $C(X)=\{x\}$, and, otherwise when $x\notin X$, $C(X)=\emptyset$. It is easy to see that this choice rule is path independent and any utility function that rationalizes it must assign a strictly higher utility to $\{x\}$ than $\{x,y\}$, violating monotonicity.

Theorem 1 states that, for any path-independent choice rule, there exists some ordinally concave utility function. In general, there could be utility functions that are not ordinally concave while rationalizing a path-independent choice rule. In fact, it is obvious that the values assigned to sets of contracts that are never chosen can be lowered without changing the rationalized choice rule, and such changes in a utility function do not necessarily preserve ordinal concavity. This simple observation suggests that it is likely to be elusive to single out one condition on utility functions for the rationalization result.²⁸²⁸28In fact, there is a large degree of freedom in choosing utility functions for rationalizing a given path-independent choice rule. Alkan (2002) shows that the set of all chosen sets by a path-independent choice rule forms a lattice under a natural revealed preference relation. Any utility function that gives higher values to more preferred chosen subsets and gives sufficiently low values to never-chosen subsets rationalizes the choice rule. However, we also show that the rationalization result fails for many other conditions that are seemingly related to substitutability, so our rationalization result offers meaningful restrictions on rationalizing functions; see the discussions in the Introduction and Section 4.

In practice, it is often the case that a choice rule $C$ chooses subsets of cardinality of up to some constant $q\in\mathbb{Z}_{+}$, which could be interpreted as a capacity. If we consider such a choice rule in the only-if direction of Theorem 1, we can construct a rationalizing utility function $u$ whose effective domain is the subsets that have cardinality of at most $q$.²⁹²⁹29We are grateful to an anonymous referee for their suggestion, which led us to consider this case. Specifically, we can construct $u:2^{\mathcal{X}}\rightarrow\mathbb{R}\cup\{-\infty\}$ such that (i) $u(X)=-\infty$ for all $X\subseteq\mathcal{X}$ with $|X|>q$, (ii) $u$ rationalizes $C$, and (iii) for any $X,X^{\prime}\subseteq\mathcal{X}$ with $u(X)>-\infty$ and $u(X^{\prime})>-\infty$ and any $x\in X\setminus X^{\prime}$, the requirement of ordinal concavity is satisfied.³⁰³⁰30To construct such a utility function, it suffices to modify the definition of $u$ in the proof (see step 1 in Section A.1.2) so that the utility from $X\subseteq\mathcal{X}$ with $|X|>q$ is equal to $-\infty$. Even though the stronger version of ordinal concavity that we call ordinal concavity⁺⁺ is no longer satisfied, the proof of $u$ satisfying ordinal concavity still goes through with a minor modification.

Next, we introduce another concavity notion that proves crucial for rationalizable choice rules to satisfy the law of aggregate demand.

Like ordinal concavity, this condition states that either the function value strictly increases on at least one side or the function values remain unchanged on both sides when two sets move closer to each other. Size-restricted concavity differs from ordinal concavity in that it requires $X$ to have a strictly larger cardinality than $X^{\prime}$, and furthermore, only one contract is added or removed when sets are brought closer to each other. It is easy to see that size-restricted concavity is implied by M^♮-concavity but is logically independent of ordinal concavity.³¹³¹31We define M^♮-concavity in Section 4. If a utility function $u$ satisfies M^♮-concavity, then it has the following property: for any $X,X^{\prime}\subseteq\mathcal{X}$ with $|X|>|X^{\prime}|$, there exists $x\in X\setminus X^{\prime}$ such that $u(X)+u(X^{\prime})\leq u(X-x)+u(X^{\prime}+x)$. In fact, M^♮-concavity is equivalent to this property in our setting (Murota and Shioura, 2018, Corollary 1.4). It can be easily verified that size-restricted concavity is an ordinal implication of this inequality. Therefore, M^♮-concavity implies size-restricted concavity.

Our second rationalization theorem uses size-restricted concavity.

By Theorem 1, a choice rule that is rationalizable by an ordinally concave utility function satisfies path independence. To complete the if direction, we show that when the utility function also satisfies size-restricted concavity, the induced choice rule satisfies the law of aggregate demand as well. For the only-if direction, we show that the utility function we construct in the proof of Theorem 1 satisfies size-restricted concavity when the choice rule satisfies both path independence and the law of aggregate demand. This completes the proof using Theorem 1, which shows that the utility function satisfies ordinal concavity.

We note that the path independence of the choice rule and the ordinal concavity of the rationalizing utility function are indispensable in Theorem 2. More precisely, without these assumptions, the law of aggregate demand is logically unrelated to rationalizability by a size-restricted concave function.

In this section, we focus on concavity notions other than ordinal concavity that have been used in economic analysis. We show that they do not constitute a necessary and sufficient condition for rationalizing choice rules with path independence and the law of aggregate demand. We then discuss some variants of ordinal concavity and size-restricted concavity.

Concavity has been a central assumption in the analysis of economies with divisible goods. Our analysis reveals a sense in which it is essential in economies with indivisible goods as well. In particular, we show that a path-independent choice rule is rationalizable by a utility function that satisfies a particular notion of discrete concavity, namely ordinal concavity. In fact, we show that the relationship between path independence and rationalizability by a utility function with ordinal concavity is tight. In economies with divisible goods, it is often the case that maximization techniques of concave functions help us characterize equilibrium outcomes. Our rationalization theorems may prove useful in the analysis of economies with indivisible goods.

To our knowledge, the present paper is one of the first to provide rationalization theorems for combinatorial choice rules. One possible direction for future research is to provide rationalization results for other choice rules. It is not arduous to provide such results for canonical choice rules such as the responsive ones (Roth, 1985) as well as the $q$-acceptant and substitutable ones (Kojima and Manea, 2010).⁴¹⁴¹41The rationalization results are available from the authors upon request. They are not included in the present paper because the conditions on the utility functions are not naturally interpretable as concavity properties, which are the main focus of the current paper. Meanwhile, rationalization results are still an open problem for most other choice rules, such as those with type-specific quotas (Abdulkadi̇roğlu and Sönmez, 2003) and with reserves (Hafalir et al., 2013). More generally, it would be interesting to establish rationalization theorems for practically relevant choice rules.