Many-to-one assignment games (Sotomayor, 1992) are extensions of one-to-one assignment games (Shapley and Shubik, 1972) inasmuch (only) one type of the players (the row players) are allowed to be paired with more than one player of the other type (the column players) up to given capacities. It is known that, similarly to the one-to-one case, the core of many-to-one assignment games is non-empty and has the two side-optimal special vertices.

We consider many-to-one assignment games as special linear production games (Owen, 1975) and investigate the Owen set, that is, the set of core allocations obtained from the dual optimal solutions of the linear programming problem whose optimum value gives the value of the grand coalition. Although the Owen set is known to coincide with the core in one-to-one assignment games, we find that in many-to-one assignment games the Owen set is typically a lower dimensional subset of the core.

We show that the Owen set of a many-to-one assignment game induced by an mxn (m<=n) non-negative pairwise profit matrix can be described as the core of an associated incomplete one-to-one assignment game induced by an incomplete nxn pairwise profit matrix. This facilitates the application of various results known for the core of one-to-one assignment games to the Owen set of many-to-one assignment games. For example, based on the graph-theoretic characterization of the side-optimal core vertices (Solymosi, 2023), we show that the same allocation maximizes (simultaneously) the n column payoffs in the Owen set and in the core of a many-to-one assignment game, but the columns-minimum Owen set allocation is not necessarily an extreme point of the core.

Joint work with Regina Radanovits.

Retour page d'accueil du séminaire