Local to global… and back again

Recently, I have had some reason to reflect on the perspective that I adopt within my research. Here, I want to explore these thoughts further.

A one-line summary of my approach could be: “local to global and back again”. The sub-text would then read: “… and implications for system design”. Of course, these could possibly be some of the most overloaded words in (technical) English literature, so it is worth elaborating.

Let’s start with a “system” or “network”. These terms have slightly different meanings in some fields (a network often brings to mind something to do with a graph), but for my purposes the distinction is too fine. For me, they are inter-changeable and conjure up something with a (potentially large) number of interacting components. The notion of interaction here is crucial and is what brings to the fore ideas of global behavior; i.e., what happens when all of these components are acting and interacting in concert. It then follows that local behavior is concerned with how each component behaves in isolation.

These ideas of global/local system behavior draw from the tradition of von Bertalanffy’s General System Theory and some of the more modern formalisms in the field of multi-agent systems. Pulling more from these traditions leads to the ideas of emergent behavior and complex systems theory, which are now playing such an important role in physics, engineering and biology.

But most of the engineered systems that I study and design are usually not considered to be complex; there is typically limited emergent behavior. This, I think, is largely due to the top-down approach to design, and the assumptions we make on the behavior of components. To be more concrete, consider wireless communication system engineering; a field that I have been drifting in and out of for the last few years. Here, the goal is to design systems to support reliable communication via electromagnetic propagation in the context of, for example, cellular communications (think mobile phones) or sensor networks. Engineers that are building these networks are interested in global system metrics such as data rates (e.g., download speeds) that are available to each user and, importantly, set up the whole network in the first place to ensure that the metrics meet the targets that ensure their customers are happy with their service—a top-down kind of approach.

One reason why a top-down approach has worked so well in communications engineering is that the models that govern the behavior of the whole system are, compared to most other fields, very good. It is possible to largely ignore, for instance, the individual behavior of each human user in the design of the system, which (ask any social scientist) are complex.

However, I’m wondering if times are changing. The idea of an internet of things is pushing towards the situation where it is necessary to work less with a large network of largely homogeneous users with similar requirements and more in the setting where users (in a very general sense) want a range of services with different quality and availability. For instance, in robotics for manufacturing it is probably important to ensure that your robot has a high-bandwidth, low delay link to avoid accidents. Or in sensor networks it may be possible to support delay-tolerant links, as long as power consumption is low. The question is then: how do we figure out where resources should go?

In the case that nothing happens very quickly–i.e., the class of users in the network are not changing rapidly and sufficient resources to support them are available–there is not a great need to adopt a different methodology. However, this does not seem to always hold and how resources should be allocated will depend greatly on the context.

On the other hand, what if the context–for example, the classes of users in the system–is changing rapidly? And what if it is difficult to identify which users want which services? In this setting, the unfortunate situation arises where it is necessary to ask users what they want.

The consequences of having to ask (or elicit) what services (or preferences) each user has only become clear to me after studying a different problem that arises in transportation: the design of on-demand transport services. These services include taxis and also companies such as Uber, where the idea is that passengers are able to be transported to and from flexible locations at the times they would like. Quite naturally, there is a need to ask passengers for details such as where and when they want to travel. There are also a number of other preferences that people have when they travel in someone else’s vehicle: driver history; driver reputation; vehicle-type; and price. These preferences can be difficult to obtain as either passengers would prefer not to reveal them (e.g., the maximum price they would like to pay) or they are prepared to trade-off some preferences for others (e.g., perceived journey safety and the time they would like to be picked up). It is not hard to see that enumerating all the trade-offs and encouraging passengers to truthfully report their preferences is a difficult problem.

Fortunately, there are tools from mechanism design (such as auctions) that provide a means to obtain reliable estimates of individual preferences. However, these tools can be viewed as a way to solve the problem locally. For on-demand transport services, mechanism design can help to price and allocate passengers to vehicles within a given region, but within a city, a country, or worldwide a more difficult problem arises: how should the particular mechanism that is used in each region be decided? At this point, we are left with having to solve what is known as the mechanism selection problem. Machine learning enthusiasts might argue that it is simply a matter of estimating parameters for the mechanism in each region and optimizing accordingly. To some extent I am in agreement with this approach; however, the fact that the success of companies such as Uber varies dramatically throughout the world despite such a machine learning strategy suggests that there is more going on.

In fact, it would seem that the reason no single mechanism (even if it is tuned) works universally is that it is not possible to characterize people by a small number of parameters. In other words, people are complex and how they behave as individuals and in groups depends on a range of factors that are difficult to model, ranging from their culture to what they had for breakfast.

The complexity of individuals has implications more generally for the design of engineered systems that interact with people. Even for systems that rely heavily on machine learning. Let’s return to the on-demand transport example and suppose that we are running a taxi company and have adopted a pricing strategy that depends on the time of day and whether or not it is a holiday. After some experimentation, we have found price levels that allow us to match supply and demand, and ensure that drivers are able to obtain a reasonable income and passengers are able to reliably obtain a journey. This is working well, but one day we find out that in another country a company is dynamically pricing based on instantaneous estimates of passenger demand and driver supply. Inspired, we begin to collect data in order to introduce our own dynamic pricing scheme. Unfortunately, one week after the introduction of our new pricing scheme, we observe that there is a drop in the number of passengers using the service, as well as a defection of drivers to our competitors. What has happened?

The kind of problem experienced by our on-demand transport company can be viewed as the mechanism implementation problem. Here, in setting our new pricing mechanism, we relied on passenger and driver preferences when they interacted with the old mechanism. By changing the mechanism, we changed how we interacted with the passengers and drivers and as such, require new data for their preferences. The mechanism implementation problem is concerned with how to move from one mechanism to another, while accounting for how the individuals interacting with the mechanism change. In other words, how their preferences are changing in response to how the mechanism changes. From a more general perspective, the mechanism selection and implementation problems are difficulties that arise when we design systems locally, but are ultimately interested in how they perform globally.

For some time, I have been interested in how to think about and design systems from a global perspective when it is difficult even to characterize individual components. By components, I mean blocks of a system either concerned with obtaining information (measurement), sending this information somewhere (communicating), or using the information to make a decision (optimization). The design of each of these blocks, even in isolation, is often not easy. For instance, it is not inaccurate to say that much of statistics is concerned with the measurement problem. The purpose of information and communication theory, as well as linguistics, is to understand and design communication components. Optimization theory, game theory, and operations research could also be said to provide ways of dealing with optimization components.

So, in our global system, how do we understand all of these blocks in concert? What are the kinds of tools that we need to apply? There are no easy answers here, and the techniques will depend on the structure of the thing to be measured, the communication mechanism, and the structure of the optimization problem.

What we can say is that a system that (1) aims to measure something; (2) sends the information over a link; and (3) informs a decision, is not what occurs in classical information or communication theory. The difference is that there is semantic content: we care about what is actually being sent over the communication link–it’s purpose is to inform a decision. To clarify things, consider a communication link that is designed to send information reliably at a rate R. As long as the capacity of the link is greater than R, our design can be considered a success–our link is reliable.

On the other hand, in our measurement-communication-optimization system, the communication link must be designed quite differently. In fact, it is coupled to the other two components and it is not always possible to decouple the communication from measurement and optimization. Of course, in the most desirable situation where decoupling is possible, if we can show that achieving a given rate solves our problem then we are done. Even so, the challenge lies in obtaining such a decoupling condition. Famously, Shannon obtained such a result in his source-channel separation theorem, to decouple source and channel coding. But what about the more general situation? How do we account for the case when the measurements consist of information elicited from strategic agents, or from a dynamical system in the case of nano-scale communication? How do we characterize the solution of the optimization problem in terms of the quality of the measurement procedure and the robustness of the communication link.

I will leave these as open questions. What I do know is that technology such as the internet of things is leading us towards systems where local and global behavior are intertwined in complex ways. Moving from a local to global perspective and back again is something we need to get used to.

Advertisements