Faculty of Management, Tel-Aviv University

June 09, 2011, 11:15, Room GC B3 424 (click here for the map)

<p>We consider a <em>cooperative game with transferable utility</em>, defined on a set of players N, whose characteristic function V depends only on a vector of some quantitative properties of the players, and is otherwise independent of their identity. As a result, the game can be defined on any virtual coalition of players, not necessarily subsets of N, as long as each player is associated with a vector of properties. We call such games regular games. Many games considered in the literature are regular. We assume that the characteristic function of the game is sub-additive, i.e., the cost of two disjoint coalitions is at least as large as the cost of their union, implying economies of scope. Sub-additivity implies that a natural outcome of any bargaining process is the formation of a single coalition N called the grand coalition. </p> <p> A central question in cooperative games is how to fairly allocate the cost V(N) among the players of N. The literature refers to a few concepts of fairness. Here we focus on the known concept of the core: core allocations guarantee that no coalition has an incentive to quit the grand coalition. A fundamental problem is that the core may be empty. The literature describes just a couple of methods for proving the non-emptiness of the core. In this talk we present what we believe is a novel condition that guarantees the non-emptiness of the core. We refer to a property called homogeneity of degree one, which means that when k coalitions, associated with exactly the same set of vectors of properties, cooperate, the resulting cost is k times the cost of a single coalition. Homogeneity of degree one implies lack of economies of scale. We prove that if the characteristic function of a regular game is sub-additive and homogeneous of degree one, then the core of the game is non-empty. </p> <p> We then present a few examples for such games which naturally emerge when servers in queuing systems cooperate in order to outsource some of the activities, while the rest of the activities are optimally assigned to the servers in the system. The existing conditions for showing the non-emptiness of the core fail here, while the conditions stated above are satisfied, proving that the cores of these games are non-empty.</p>

*Shoshana Anily holds her Ph.D. in Management Science from the Columbia Business School, an MA degree is statistics and B.Sc. degree in mathematics, both from Tel Aviv University. Upon graduation she joined the University of British Columbia, and in 1989 she returned to her home country and joined Tel Aviv University. She is a professor of decisions and Operations Research at the Leon Recanati Graduate School of Business Administration of Tel Aviv University, Israel. Her research interests include performance analysis of heuristics, routing problems, inventory control, production, scheduling, and cost allocation problems in a supply chains. She spent some periods as a visiting professor at Columbia University, EPFL and the CRT at the University of Montreal.*