Abstract

This page is a (online) guide to illustrate the article (available from Arvix), that presents a set of tools for the modeling of a spatial allocation problem in a large geographic market and gives examples of applications. In our settings, the market is described by a network that maps the cost of travel between each pair of adjacent locations. Two types of agents are located at the nodes of this network. The buyers choose the most competitive sellers depending on their prices and the cost to reach them. Their utility is assumed additive in both these quantities. Each seller, taking as given other sellers prices, sets her own price to have a demand equal to the one we observed. We give a linear programming formulation for the equilibrium conditions. After formally introducing our model we apply it on two examples: prices offered by petrol stations and quality of services provided by maternity wards (only the later is described here for privacy issues). These examples illustrate the applicability of our model to aggregate demand, rank prices and estimate cost structure over the network. We insist on the possibility of applications to large scale data sets using modern linear programming solvers such as Gurobi.**Contact** : Arthur Charpentier charpentier.arthur@uqam.ca

We will use some some network packages (mainly to illustrate)

as well as some packages for spatial analysis, and visualization

```
library(geosphere)
library(rgdal)
library(leaflet)
library(scales)
library(lwgeom)
library(shapefiles)
library(sp)
library(rgeos)
library(osmdata)
library(sf)
library(ggmap)
library(maptools)
```

For technical reasons, we need additional packages

```
library(Matrix)
library(tripack)
library(RColorBrewer)
library(units)
library(pals)
library(classInt)
```

In the applications, we will use gurobi. It is a commercial optimization solver for linear programming, quadratic programming (among many other), that is available for free in academia. Installation can be a little bit complicated (see the vignette online),

We will consider three applications in this guide

- the toy example just to explain the four components in our approach : the
*nodes*and the*edges*(a road network for instance), the location of*sellers*and*buyers*. The first part is to match locations of sellers and buyers with nodes. Then we solve the linear programming problem. - the metro example to illustrate the use of a real network (here the metro in Paris), with a single
*buyer*and several*sellers*(hospitals here) - the maternity example to illustrate on read data, with all maternities in France (
*sellers*) and all pregnant women (*buyers*).

The geometry of the geographic market is described by a connected graph \(G=\left(V,E\right)\) where \(V\) is a set of vertices and \(E\) is a set of directed edges. Vertices are the different locations; edges are road segments linking two adjacent locations.

Agents are located at the vertices of our graph (if not, as we will see, we will match them with the closest vertice).We make the following assumptions on their consumption preferences:

**(A1)**Consumers with the same location have the same outside option,**(A2)**Consumers have the same cost of travel along a given edge,**(A3)**There is no capacity constraints on the supply side.

A path \(\pi_{vw}\) between two nodes \(v,w\in V\) is a sequence of connected edges starting in \(v\) and ending in \(w\). We note \(\Pi_{vw}\) the set of paths between \(v\) and \(w\).

For each edge \(e\in E\), we define \(c_{e}\) the cost of travel along this arc. A seller located in \(w\in V\) sells at an endogenous price \(p_{w}\). Therefore a consumer located in \(v\) chooses to buy from the seller located in \(w\) that minimizes his total cost \(p_{v}\) \[ p_{v}=\underset{w\in V\text{, }\pi_{vw}\in\Pi_{vw}}{\min}\left[p_{w}+\underset{e\in\pi_{vw}}{\sum}c_{e}\right] \]

Letâ€™s denote\(u_{v}\) the reservation utility of agents located in \(v\) and \(p_{v}\) the price for these agents (including the cost of transportation). Therefore, if \(p_{v}>u_{v}\) a consumer in \(v\) his outside option, else he buys from the most competitive seller depending on his location in the market.

This outside option can be modeled by a fictitious node \(0\), where the price of the commodity is set to \(p_{0}=0\) and the cost of travel is \(c_{v0}=u_{v}\).

Hence the excess demand \(z_{v}\) at a node \(v\in V\) does not depend on the price. We are solving a matching problem over a network between sellers and consumers.

At equilibrium each consumer chooses the most competitive seller depending on his location; furthermore the demand received by each seller must equal his supply. If we define \(\mu_{e}\) the number of agents traveling along edge \(e\), these equilibrium conditions can be written: \[ \left\{ \begin{array}{l} \forall vw\in E\text{, }p_{w}-p_{v}\leq c_{vw}\\ \forall vw\in E\text{ such that }\mu_{vw}>0\text{, }p_{w}-p_{v}=c_{vw}\\ \forall v\in V\text{, }\underset{w\in V}{\sum}\mu_{vw}-\underset{u\in V}{\sum}\mu_{uv}=z_{v} \end{array}\right. \]

These equations are the complementary slackness conditions for a minimum cost flow problem over network \(G\). Hence, if the graph is connected and if there isnâ€™t any loop of negative cost in \(G\), there exists an equilibrium which is the solution of the min-cost flow problem \[ \begin{array}{cl} \mu=\text{argmin}\underset{e\in E}{\sum}c_{e}\mu_{e}\\ & \mu\text{ s.t. }\forall v\in V\text{, }\underset{w\in V}{\sum}\mu_{vw}-\underset{u\in V}{\sum}\mu_{uv}=z_{v} \end{array} \]

Models used in trade theory usually use **iceberg transport costs**. These costs are linear in distance and paid in the transported good once arrived - hence the metaphor of the iceberg that melts as you transport it.

Our model can incorporate these costs applying a log-transformation to the equilibrium conditions. Letâ€™s define for all \(vw\in E\) iceberg costs \(\tau_{vw}\). An equilibrium \(\left(\mu,p\right)\) should satisfy \[ \left\{ \begin{array}{l} \forall vw\in E\text{, }\left(1-\tau_{vw}\right)p_{w}\leq p_{v}\\ \forall vw\in E\text{ such that }\mu_{vw}>0\text{, }\left(1-\tau_{vw}\right)p_{w}=p_{v}\\ \forall v\in V\text{, }\underset{w\in V}{\sum}\mu_{vw}-\underset{u\in V}{\sum}\mu_{uv}=z_{v} \end{array}\right. \] which becomes \[ \left\{ \begin{array}{l} \forall vw\in E\text{, }\log p_{w}-\log p_{v}\leq-\log\left(1-\tau_{vw}\right)\\ \forall vw\in E\text{ such that }\mu_{vw}>0\text{, }\log p_{w}-\log p_{v}=-\log\left(1-\tau_{vw}\right)\\ \forall v\in V\text{, }\underset{w\in V}{\sum}\mu_{vw}-\underset{u\in V}{\sum}\mu_{uv}=z_{v} \end{array}\right. \]

Therefore this problem is equivalent to the one presented earlier with \(\forall vw\in E\), \(c_{vw}=-\log\left(1-\tau_{vw}\right)\), and replacing \(p\) by its logarithm.

Consider a shapefile of *roads*, or *train lines* : each road is a collection of segments, or connected nodes. Our shapefile is, so fact, only in a dataframe `dd`

Here are the (given) knots and the four roads

```
par(mfrow=c(1,2))
plot(dd$X,dd$Y,col="white",xlab="",ylab="")
for(i in unique(dd[,1])) lines(dd$X[dd$Id==i],dd$Y[dd$Id==i])
points(dd$X,dd$Y,pch=19,col="red")
library(RColorBrewer)
darkcols = brewer.pal(8, "Dark2")
plot(dd$X,dd$Y,xlab="",ylab="")
for(i in unique(dd[,"Id"])) lines(dd$X[dd$Id==i],dd$Y[dd$Id==i],col=darkcols[i],lwd=2)
```

Let us create a *shapefile* from those segments

Intersections of roads are now added, as knots of the network

```
par(mfrow=c(1,2))
plot(dd$X,dd$Y,col="white",xlab="",ylab="")
for(i in unique(dd[,1])) lines(dd$X[dd$Id==i],dd$Y[dd$Id==i])
points(dd2[["knots"]]$X,dd2[["knots"]]$Y,pch=19,col="blue")
points(dd$X,dd$Y,pch=19,col="red")
plot(dd2[["shp"]]$X,dd2[["shp"]]$Y,col="white",xlab="",ylab="",axes=FALSE,xlim=c(2.6,8.4))
text(dd2[["knots"]]$X,dd2[["knots"]]$Y,dd2[["knots"]]$NO)
points(dd2[["knots"]]$X,dd2[["knots"]]$Y,cex=3)
```