Fractional Programming in Cooperative Games

Cooperation of individuals or institutions is often coupled with benefits that can be regarded as the monetary worth or outcome of the cooperation. Therefore, the problem naturally arises how to allocate the total outcome among institutions or individuals in a fair way. Such allocation problems are studied within cooperative game theory. A general idea is to find an allocation which guarantees a payoff no less than the earning of these players working without cooperation. This motivates a classical concept for “fair‿ division, the “core‿ allocation (Chapter 2) for all individuals. However, such core allocations are not always guaranteed in many practical and theoretical cases. Even if there exists a core allocation, finding such an allocation is often hard. For example, the bin packing game (Chapter 3) does not always admit a nonempty core and finding a core allocation for the bin packing game is an NP-hard problem. In case the core is empty, in this thesis, we adopt the tax model, i.e., players can only keep a (1 − e) fraction of their total earning if they work on their own, where is called the taxation rate. This is the general idea behind sales and tax, which is quite natural and acceptable. Based on this model, we aim at finding an e-core allocation such that the taxation rate is as small as possible.