Virtual Demand and Stable Mechanisms

ABSTRACT

We study conditions for the existence of stable, strategy-proof mechanisms in a many-to-one matching model with discrete salary space (the discrete Kelso-Crawford model). Workers and firms want to match many-to-one and agree on the terms of their match. Firms demand different sets of workers at different salaries. Workers have preferences over different firm-salary combinations. Workers' preferences are monotone in salaries. We show that for this model, a descending auction mechanism is the only candidate for a stable mechanism that is strategy-proof for workers. Moreover, we identify a maximal domain of demand functions for firms, such that the mechanism is stable and strategy-proof.

For each demand function in our domain, we can construct a related demand function that we call a virtual demand function. Replacing demand functions by virtual demand functions will not change the outcome of our mechanism. Known conditions (gross substitutability and the law of aggregate demand) can be applied to the virtual demand profile to check whether the mechanism is stable and strategy-proof. Our result gives a sense in which gross substitutability and the law of aggregate demand are necessary for the existence of a stable and strategy-proof mechanism.

In the special case, where demand functions are generated by quasi-linear profit functions, demand functions and virtual demand functions agree. Thus for this case, our domain reduces to the domain of demand functions under which workers are gross substitutes.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Matchings and factors

• Theory of computation

  • Theory and algorithms for application domains

    • Algorithmic game theory and mechanism design

      • Computational pricing and auctions

      • Market equilibria