*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
