Análise de complexidade assintótica de um algoritmo exato para o cálculo do nucleolus de um jogo cooperativo

Abstract

The problem attacked by the project is to allocate the costs of a net in a fair way among the participants and to analyze the complexity of the solution for the problem. The application is in situations where certain entities seek to reach a common objective. Because each entity possesses a cost to obtain the same service, a cooperation can be formed for the reduction of the cost. To obtain a division of this cost in a great way among the users, the value of Shapley and Nucleolus can be used as solution. The solution of the nucleolus, that is a solution belonging to the Cooperative Game Theory, it was used, therefore this allocates the costs among the users in a fairer way. An algorithm based on the lineal programming for the obtaining of the nucleolus, proposed for [Grano81], it was developed, however it was verified that such algorithm needed modifications so that the solution could be obtained, so this was extended. When verifying the results, it can be verified that the proposed algorithm resulted in fairer results than the algorithm found in the literature, where the complexity stayed the same.