Search

This Habilitation thesis explores aspects of computation in a status of uncertainty. First, we study online problems, in which the input is not known in advance, and the algorithm must make decisions for each input item without knowledge of future input items. Second, we consider search games, in which a mobile searcher must locate an immobile hider that lies in some unknown point of the search domain. Last, we study the design and analysis of interruptible systems, in which the system must be able to produce a reasonably efficient output even if interrupted at some arbitrary point in time. A unifying theme in the study of the above topics is the power and limitations of well-known, worst-case measures such as the competitive ratio and the acceleration ratio. We argue that in certain cases, more nuanced performance measures are required, and to this end we introduce new models and techniques of analysis. We also demonstrate and exploit connections between these measures and approaches, even though they apply to seemingly unrelated domains.

International audience

To remain competitive, organizations in all industries need to keep up with emerging digital technologies. Such technologies can drastically change the way organizations function, by providing stakeholders with new and improved ways to communicate and interact. As a result, stakeholders play an increasingly crucial role in the value chain, which posits opportunities—such as better alignment between products or services and consumer demands—as well as threats, since the organizational networks become more complex, and the multiple levels of communication and interactivity become harder to manage. It becomes, thus, crucial to understand how and when the adoption of digital technologies influences the complexity of organizational networks in their multiple levels of interaction and communication, and vice versa. In this paper, we explore how organizational networks evolve over time during digital transformation projects, and how the organizational network affects—and is affected by—the initiation, process, and outcome of digital transformation. We conduct a longitudinal study at a multinational military command (AirTrans), which coordinates the air operations of 7 European nations and has initiated a digital transformation project. AirTrans handles the air transport missions of the 7 participating nations, including cargo and human transport, air-to-air refueling, and aeromedical evacuations; it operates 24/7/365 from 13 bases in the participating nations, performs an average of 60 missions per day, and manages 60% of all military air transport assets in Europe. Apart from the 7 participating nations, the stakeholders of AirTrans include military broker agencies, hospitals, regulatory agencies such as the NATO, and humanitarian agencies. We explore the inter-organizational and inter-personal networks between the various stakeholders using multi-level social network analysis at the beginning, during, and at the end of the digital transformation project, to understand how the organizational network evolves at the various involved levels over time, and how it affects the processes of digital transformation. As the aim of AirTrans is to combine knowledge from the participating nations in a way that brings value to these nations through its operations, its performance depends on the ability to collect information, transform it into knowledge, and share it with the involved stakeholders. Hence, we adopt Knowledge-Based View of the organization as our focal theory, which considers knowledge as the most important resource of an organization. We construct the longitudinal inter-personal network through a series of semi-structured interviews at AirTrans, the participating nations, and the other stakeholders during the initiation, process, and end of the digital transformation project using Network Canvas, and we use longitudinal organizational data of the various AirTrans operations to construct the inter-organizational network. Our findings shed light onto the relation between the various levels of organizational networks and the process of digital transformation and provide insights on how organizational networks affect the process and outcome of digital transformation and vice versa, enabling the design of digital transformation strategies by incorporating social network interventions.

Most of the existing literature on legislative networks has been largely focused on the strength, formation, and nature of ties amongst legislators. Since most of such studies have been focused on the U.S. political context, it has become customary to address the legislative behavior of MPs and how they align with the ideological boundaries. Concurrently, little research has been conducted on the formation and dissolvement of stable political alliances, such as coalitions. Moreover, most of the existing studies assume that legislative behavior is based on signaling effects. Yet, the effect of information exposure (i.e. signals) and the trail of legislative behavior based on such information, however, has received scant attention. Our aim is to address that lacuna by investigating the network effect of information exposure on coalition formation and legislative behavior through data from a natural experiment. In 2015, after one year of the Ukrainian Parliament procedures, new legislation was enforced on MPs, which required them to declare all their assets publicly. Despite such an abrupt (and unpleasant for them) change, most MPs filled the declarations demonstrating their wealth to the public for the first time. This event was clearly unexpected and was received as similar to a natural or social disaster. Within a few months, the exposure of information turned many MPs from “perhaps rich” to “definitely rich”. We base our analysis on the—strong, but demonstratively justified—assumption that the wealth of MPs became public for the first time through their declarations (it was the first time in history that the actual magnitude and variation of assets were revealed to the public). If there is indeed an effect of signaling, then network effects should have become stronger, since the social theory of homophily predicts that similar actors will form ties and behave similarly (i.e. rich MPs will have similar behavior, and rich and not-so-rich MPs will have a different one). On the other hand, one could hypothesize that the revelation of the information of wealth could make the less wealthy MPs aware of the benefits they can get if they behave in certain ways. Thus, they could replicate the behavior of their wealthy colleagues to accumulate wealth. We investigate how the behavior of MPs actually changed after the declarations became public, and we further explore the effect of declarations on coalition formation. We employ autologistic actor attribute models (ALAAMs)—which represent a variation of exponential random graph models (ERGMs), where the dependent variable is a behavior—to investigate the social influence of wealth revelation in the legislating behavior of Ukrainian MPs after the event of information exposure. Our findings enhance understandings on the organizational processes within networks and elucidate the mechanisms of homophily on the event of information exposure.