Existence of the weak and strong core in a sharing model with arbitrary graph structures

Abstract We consider a model where agents are nodes on a graph and two agents are potential partners if they are connected by an edge in the graph. Agents have to be matched in pairs, and each pair must complete a task that requires one unit of effort. Each agent has symmetric preferences around an ideal effort level. An allocation consists of pairs of agents and a sharing arrangement of the effort for each pair. We associate three natural optimization problems—integer matching, fractional matching, and fractional covering—with any given instance of our problem. We show that a strong core allocation exists if and only if the optimal values of the associated integer matching, fractional matching, and fractional covering problems coincide. A weak core allocation is shown to exist if the optimal values of the integer and fractional matching problems coincide, and always exists for bipartite and complete graphs.