A necessary and sufficient condition for weak Maskin monotonicity in an allocation problem with indivisible goods

Adding one condition, Morrill (2013) characterizes an allocation rule whose outcome is equivalent to the DA algorithm for every substitutable priority.

Kojima and Manea (2010) provide two characterizations of the DA rules: An allocation rule is the DA rule for some acceptant substitutable priorities if and only if (1) it satisfies non-wastefulness and individually rational monotonicity and (2) it satisfies non-wastefulness, weak Maskin monotonicity and population monotonicity.

Ehlers and Klaus (2014, (2016) provide alternative characterizations of the DA rules based on strategy-proofness in a model with variable resources. Ehlers and Klaus (2016) show that an allocation rule is the DA rule for some acceptant substitutable priorities if and only if it satisfies unavailable-type-invariance, individual rationality, weak non-wastefulness, resource monotonicity, truncation-invariance, and strategy-proofness. Ehlers and Klaus (2014) show that an allocation rule is the DA rule for some responsive priorities if and only if it satisfies unavailable-type-invariance, individual rationality, weak non-wastefulness, two-agent conflict resolution, truncation-invariance, and strategy-proofness. Resource monotonicity and two-agent conflict resolution describe the effect when resources are changed. As resources are fixed in our model, a straightforward comparison of our results with theirs is not possible.

A preference relation \(R_{i}\) on \(O\cup \{\emptyset \}\) is anti-symmetric if \(\forall a,b\in O\cup \{\emptyset \},[aR_{ib}, bR_{ia}\Rightarrow a=b]\).

The no improvement property of unmatched agents is somewhat similar to the rural hospital theorem: if an agent is unmatched in some stable matching, then he is also unmatched in all stable matchings. In other words, unmatched agents cannot be strictly better off within the set of stable matchings.

An allocation rule is non-bossy if for each \(R\in \mathcal {R}^{N}\), each \(i\in N\), and each \(\tilde{R}_{i}\in \mathcal {R}\), if \(\varphi _{i}(R)=\varphi _{i}(\tilde{R}_{i},R_{-i})\), then \(\varphi (R)=\varphi (\tilde{R}_{i},R_{-i})\). Clearly, weak non-bossiness is weaker than non-bossiness. Takamiya (2001) shows that an allocation rule is strategy-proof and non-bossy if and only if it satisfies Maskin monotonicity.

For details of their setting, see Kojima and Manea (2010).

For each \(i\in N\), let denote \(R^{\emptyset }_{i}\) the preference that ranks \(\emptyset \) first. An allocation rule \(\varphi \) satisfies population monotonicity: for each \(R\in \mathcal {R}^{N}\), each \(N'\subseteq N\), and each \(i\in N'\), \(\varphi _{i}(R_{N'},R^{\emptyset }_{N\setminus N'})R_{i}\varphi _{i}(R)\).

The concept of underdemanded objects is generalized to “essentially underdemanded objects”, which is introduced by Tang and Yu (2014). In our main result, we can also replace unmatched agents by agents with essentially underdemanded objects.

In our model, reshuffling invariance by Barbera et al. (2012) is defined as follows. For each \(R\in \mathcal {R}^{N}\), each \(i \in N\), and each \(R'_{i} \in \mathcal {R}\), \(U(\varphi _{i}(R), R'_{i}) = U(\varphi _{i}(R), R_{i})\) implies \(\varphi _{i}(R'_{i}, R_{-i})=\varphi _{i}(R)\). In a more general model than ours, they show that reshuffling invariance is always implied by strategy-proofness. They also provide domains of preferences in which reshuffling invariance together with a monotonicity condition implies strategy-proofness.