A cost allocation framework for LP and GLP games

Cost allocation problems within the GLPG class of games (Generalized Linear Programming Games) are considered in this paper. We assume that a group of agents participate in a common project and each agent defines his requirements for his expected benefit resulting from the project. Then, the joint cost of the project must be allocated amongst the agents in order to satisfy a set of required properties

Rozważono zagadnienie alokacji kosztów w ramach klasy problemów modelowanych jako GLPG (Generalized Linear Programming Games) – uogólnione gry kooperatywne bazujące na zadaniach programowania liniowego. Zakładamy, że grupa agentów uczestniczy we wspólnym przedsięwzięciu, a każdy agent określa pewne wymagania związane z jego uczestnictwem. Wówczas pojawia się problem podziału łącznych kosztów realizacji przedsięwzięcia na każdego z uczestniczących agentów przy zapewnieniu zdefiniowanych ograniczeń tych agentów. W artykule sformułowano ogólny szkielet algorytmu do wyznaczania alokacji łącznych kosztów, oparty na klasie metod alokacji generowanych przez tzw. ścieżki. Proponowane podejście jest uogólnieniem pewnych ważnych mechanizmów alokacji, bazujących na teorii gier kooperatywnych, w tym na wycenie Aummana–Shapleya. Zgodnie z naszą wiedzą dotychczas nie został opracowany żaden wydajny algorytm umożliwiający wyznaczanie alokacji dla problemów modelowanych jako gry kooperatywne bazujące na programowaniu liniowym (LPG i GLPG). Spotykane w literaturze podejścia polegają na obliczeniach niedokładnych przy jednocześnie wymaganym większym nakładzie obliczeniowym.