TITLE:  Decentralized Online Integer Programming

ABSTRACT: 

We consider a set of collaborative agents that need to coordinate their actions so as to socially optimize the sum of their objectives while satisfying a common resource constraint. The objective functions of the players are unknown to them a priori and are revealed in an online manner over time. Given a resource allocation, each player’s action is determined by solving an integer program. Due to privacy issues, players want to share limited information while solving this problem in a decentralized way. A cardinality resource constraint links all player actions. The resulting problem is an online optimization problem to optimally allocate the resource among the players prior to observing the item values. The performance of an online algorithm is measured by regret, defined as the difference between the total gain of the best-fixed decision considering all data in hindsight and the total gain incurred by the online decisions we make. A good online algorithm is expected to have regret as a sublinear function of the number of rounds, T. In this research, we show that for any deterministic online algorithm for the resource allocation problem, there exist objective function coefficients that guarantee O(T) regret. Furthermore, for the case when the players' integer programs satisfy a special concavity condition, we propose a randomized online algorithm for the resource allocation problem that guarantees an upper bound of O(\sqrt T) on the expected regret.