Millennium Nucleus Center Information and Coordination in Networks – ICR

The lack of information or coordination between agents interacting in large networks is common in countless daily situations. A typical example can be found when people in Santiago have to move towards their respective workplaces. Each driver decides the best route considering a diversity of variables: some are constant (for example, the distance to the destination point or the speed limits on different streets), others depend on the behavior of the various agents involved (congestion due to heavy traffic) and additional factors that can be external to the system (crashes, power outages at traffic lights, etc.). The problem is that the information each agent has at hand during the decision-making process is local, incomplete and stochastic, so it is impossible to determine with certainty the best route to your destination.

In situations like this, optimal solutions cannot be found, at least not in an efficient way; for this reason, much of their investigation consists in the development of algorithms that find approximate solutions (close to optimal), that are robust (useful for different scenarios of uncertainty), dynamic (updated as the system evolves) or online (renewed according to the amount of information available). Consequently, the main objective of ICR is to consolidate a focal point of world-class research within the fields of Algorithms, Combinatorial, Game Theory and Optimization, considering its connections to network problems that are characterized by lack of information and lack of coordination. Our group has three lines of investigation relevant to the issues described:

• The algorithmic game theory that studies efficient algorithms to determine the behavior of a group of agents that optimize separate objectives.
• The study of big data problems, from online algorithms that work with partial information to the compressed representation of data.
• Research on the structure of large networks, their dynamics and their protocols