Abstract
In this paper, we extend the notion of person-by-person (pbp) optimization to binary decision spaces. The novelty of our approach is the adaptation to a dynamic team context of notions borrowed from the pseudo-boolean optimization field as completely local-global or unimodal functions and submodularity. We also generalize the concept of pbp optimization to the case where groups of m decisions makers make joint decisions sequentially, which we refer to as mbm optimization. The main contribution is a description of sufficient conditions, verifiable in polynomial time, under which a pbp or an mbm optimization algorithm converges to the team-optimum. As a second contribution, we present a local and greedy algorithm characterized by approximate decision strategies (i.e., strategies based on a local state vector) that return the same decisions as in the complete information framework (where strategies are based on full state vector). As a last contribution, we also show that there exists a subclass of submodular team problems, recognizable in polynomial time, for which the pbp optimization converges for at least an opportune initialization of the algorithm.
Original language | English |
---|---|
Pages (from-to) | 3011-3028 |
Number of pages | 18 |
Journal | SIAM Journal on Control and Optimization |
Volume | 50 |
Issue number | 5 |
DOIs | |
Publication status | Published - 2012 |
Externally published | Yes |
Keywords
- team theory
- person-by-person optimality
- approximation algorithms
- ALGORITHMS
- FRAMEWORK
- SYSTEMS