On the vertices of the core of a many-to-one assignment game

Abstract

This paper studies the structure of the core in many-to-one assignment games, where firms with limited capacity hire workers in a transferable utility framework. While it is well-established that the core of these games is always non-empty and contains firm-optimal and worker-optimal outcomes, relatively little is known about its complete geometric structure. In particular, regarding the characterization and enumeration of its extreme points. In this paper, we provide a graph-theoretic criterion for core vertices: a salary vector is a vertex of the core if and only if the base graph of its associated tight digraph is connected. We also provide a necessary and sufficient condition for each side-optimal allocation in terms of the tight digraph. Based on this characterization, we develop a lexicographic procedure that generates all core vertices as they are supported by a max-min salary vector, where workers sequentially optimize their payoffs with an indication of whether the worker in this position maximizes or minimizes his/her salary.