DOS Seminar - Ezgi Karabulut

Primary tabs

TITLE:  Decentralized Online Integer Programming


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.



  • Workflow Status: Published
  • Created By: phand3
  • Created: 04/14/2017
  • Modified By: phand3
  • Modified: 04/14/2017


No categories were selected.


No keywords were submitted.