Unlike mono-agent systems, multi-agent planing ad- dresses the problem of resolving conflicts between individ- ual and group interests. In this paper, we are using a Decen- tralized Vector Valued Markov Decision Process (2V-DEC- MDP) in order to solve this problem. It uses an utility func- tion which is returning a vector representing both individ- ual and group interest. The individual interest of an agent, computed off-line, is based on its optimal policy. The group interest is computed on-line by the agents using their own local observations. In order to take into account both cri- teria in a decision process and to find a good trade-off be- tween the group interest and the agent's one, we developed a regret-based algorithm based on the Tchebychev Norm.