Updates

Some news:

1. I have finished my contract in the Laboratoire de Mathématiques at Université Blaise Pascal in Clermont-Ferrand and will begin a new position in Département Télécommunications INSA Lyon in the middle of November working with Jean-Marie Gorce and Leonardo Cardoso.

2. With Gareth Peters, Ido Nevat, Mahyar Shirvanimoghaddam and Iain B. Collings, I have a new paper accepted:

Malcolm Egan, Gareth W. Peters, Ido Nevat, Mahyar Shirvanimoghaddam and Iain B. Collings, “A ruin theoretic design approach for wireless cellular network sharing with facilities”, to appear in Transactions on Emerging Telecommunications Technologies.

This paper concerns network sharing in facilities, which I have been discussing here and here.

3. With Andrea Tassi, Robert Piechocki and Andy Nix, I have a new paper accepted in SigTelCom2017:

Andrea Tassi, Malcolm Egan, Robert J. Piechocki and Andrew Nix, “Wireless vehicular networks in emergencies: a single frequency network approach”, in Proc. SigTelCom2017, to appear.

In related news, last week I was in Prague and presented some related work with Andrea, Robert and Andrew on mmWave communications for vehicular networks. The talk was targeted at the computer scientists working on multi-agent coordination algorithms for intelligent transport systems in the Artificial Intelligence Center in the Czech Technical University in Prague.

4. In December, I will be presenting at the CFE-CMStatistics Conference in Seville Spain. My talk is entitled: Simulation of a general class of alpha-stable processes, which is based on work with Nourddine Azzaoui, Gareth Peters and Arnaud Guillin. Here is the abstract:

The heavy-tail and extremal dependence properties of \alpha-stable processes have lead to their extensive use in fields ranging from finance to engineering. In these fields, the stochastic integral representation plays an important role both in characterizing \alpha-stable processes as well as for the purposes of simulation and parameter estimation. In order use the stochastic integral representation, constraints on the random measure must be imposed. A key constraint is the independently scattered condition, where disjoint increments of the random measure are independent. A key feature of the independently scattered condition is that the covariation is both left and right additive, which allows for simulation and estimation of this class of processes. Recently, a new generalization of the independently scattered condition has been introduced, which also preserves the left and right additivity of the covariation. This new generalization allows the characteristic function a wide class of \alpha-stable processes to be determined by a bimeasure. We deal with the problem of simulating from the bimeasure characterization of \alpha-stable processes. In particular, we prove conditions under which the bimeasure leads to a positive definite characteristic function for the case of a two-dimensional skeleton. Based on this result, we then propose a method to construct and simulate n-dimensional skeletons, for arbitrary n > 2.

Advertisements

Data-Driven Market Formation in On-Demand Transport

As on-demand transport providers (e.g., Uber) are adopting increasingly sophisticated mechanisms to allocate and price both passengers and drivers, new issues are arising. In a series of posts (starting here), I have been describing different aspects of these issues including the ways to allocate and price (the mechanism design) and also simulation tools to evaluate performance in realistic environments (capturing both the road network and the behavior of passengers and drivers).

In this post, I want to turn to a different aspect: the market formation problem.

Continue reading

How much does the PHY layer matter?

In wireless communications, a recurring question is whether or not the PHY layer is dead (there was even a paper with this title in 2011). While it is my view that it isn’t (there are still interesting open questions related to, for instance, impulsive noise and also vehicular communications), there are what in all probability are more pressing questions: when and how much does the PHY layer matter?

Continue reading

Analyzing the effect of side information: a perturbative approach

Quite often we need to make decisions. These decisions will typically depend on some information that we have obtained, either through direct observation or because it has been communicated to us by someone (or something) else. This side information is not usually perfect. For example, our measurements will not be without error and information communicated to us will be subject to imperfections in the communication medium.

How can we understand the effect of imperfect side information on our decisions?

Continue reading

ISIT 2016 Paper

In July, the International Symposium on Information Theory will be held in Barcelona, Spain. One of the papers that will be appearing there is some recent work I have done with Mauro de Freitas, Laurent Clavier, Alban Goupil, Gareth Peters, and Nourddine Azzaoui. We have been considering variations on the additive \alpha-stable noise channel Y = X + N, where N is an \alpha-stable random vector.

These kinds of channels appear in various communication systems including wireless and quite recently molecular. As such, it is interesting to try and compute the capacity of these channels. The special case \alpha = 2 with a power constraint has been extensively studied (it is the Gaussian case!), but in general the capacity is not well understood for other values of \alpha with any constraints.

Enter our paper. We considered the case where the noise N is an isotropic \alpha-stable random vector. So, the channel is the additive isotropic \alpha-stable noise (AI\alpha SN) channel. Our results? A quick summary:

  1. The optimal input for the AI\alpha SN channel subject to a constraint \mathbb{E}[|\mathbf{X}|^r] = (\mathbb{E}[|X_1|^r],\mathbb{E}[|X_2|^r])^T \preceq \mathbf{c},~r < \alpha exists and is unique.
  2. The capacity subject to \mathbb{E}[|\mathbf{X}|^r] \preceq \mathbf{c},~r < \alpha, is lower bounded by a function of the form: \frac{1}{\alpha}\log(1 + Kc_{\min}^{\alpha}). (c_{\min} is just the minimum of the elements of \mathbf{c} and K is a constant that depends on the noise parameters)

We also had a brief look at the extension to parallel channels, but for that you will need to read the paper.

For the official summary…
Title: Achievable rates for additive isotropic alpha-stable noise channels
Abstract: Impulsive noise arises in many communication systems—ranging from wireless to molecular—and is often modeled via the \alpha-stable distribution. In this paper, we investigate properties of the capacity of complex isotropic \alpha-stable noise channels, which can arise in the context of wireless cellular communications and are not well understood at present. In particular, we derive a tractable lower bound, as well as prove existence and uniqueness of the optimal input distribution. We then apply our lower bound to study the case of parallel \alpha-stable noise channels and derive a bound that provides insight into the effect of the tail index \alpha on the achievable rate.

 

Mechanism design for on-demand transport

During 2014 – 2015, one of the key research problems I was working on was how to understand and design on-demand transport mechanisms. On-demand transport is about how an individual or group can get from point A to point B at a time of their choosing. Common examples are taxi services and now new services such as Uber.

Working in a computer science department, primarily with collaborators Michal Jakob and Nir Oren, I was concerned with how passenger journeys are allocated to drivers and how each journey was priced, together called a mechanism, from an algorithmic perspective. I.e., how can these allocations and pricing be done in a computationally efficient way so that passengers get to where they want to go on time, each driver can earn a living, and service providers (e.g., Uber) can make a profit.

The problem of choosing a mechanism is known in economics as the mechanism selection problem, and must account for a range of technical, social and financial issues. For example, can the available computing resources compute the allocation and pricing quickly enough? Or, are passengers or drivers prepared to bid for a journey (a key problem for auction-based approaches)?

We have explored the problem of mechanism selection in on-demand transport by first enumerating the possible mechanisms and evaluating their performance. We observed in this working paper that each approach (e.g., hackney carriages, taxi dispatcher models, and Uber-type approaches) can be differentiated by limitations on communication and financial exchanges.

After enumerating the possibilities, we have begun to explore how the different mechanisms perform in terms of metrics such as the proportion of passengers served, costs of journeys and provider profit. In particular, we have published work in:

(1) Malcolm Egan, Martin Schaefer, Michal Jakob, and Nir Oren, “A double auction mechanism for on-demand transport networks”, in the Proc. PRIMA 2015: Principles and Practice of Multi-Agent Systems,  (2015).

(2) Malcolm Egan, and Michal Jakob, “A profit-aware negotiation mechanism for on-demand transport services”, in the Proc. of the European Conference on Artificial Intelligence (ECAI), (2014)

and now

(3) Malcolm Egan and Michal Jakob, “Market mechanism design for profitable on-demand transport services”, accepted for Transportation Research Part B: Methodological.

A key feature of our article (3) is that we provide and justify an agent-based model for on-demand transport services that captures the preferences of passengers. This means that we do not assume that every passenger will accept whatever they are offered, which is commonly assumed in previous work on on-demand transport mechanisms.

The next step is to continue to study the mechanism selection problem by understanding the requirements and performance of other on-demand transport mechanisms. At the end of the day, we hope that this work will aid new providers and municipalities to decide the kinds of mechanisms they want to support to match the unique economic, social and technical features of their cities. We believe this will provide a means to meet the needs of passengers, drivers, and providers in each city in a sustainable way.

To read more, see the next posts in this series:

New paper: Low-High SNR Transition in Multiuser MIMO

Title: Low-High SNR Transition in Multiuser MIMO

Links: [arXiv]

Abstract: Multiuser MIMO (MU-MIMO) plays a key role in the widely adopted 3GPP LTE standard for wireless cellular networks. While exact and asymptotic sum-rate results are well known, the problem of obtaining intuitive analytical results for medium signal-to-noise ratios (SNRs) is still not solved. In this paper, we propose the bend point, which quantifies the transition between low and high SNR; i.e., the beginning of the high SNR region. We derive the bend point for MU-MIMO with zero-forcing precoding and show that it is intimately related to the intercept of the high SNR asymptote with the zero sum-rate line. Using this result, we obtain a new approximation of the sum-rate at the bend point—providing a useful rule of thumb for the effect of increasing the number of antennas at medium SNR.