The n-Category Café

Let me set the scene again. We are considering transporting goods from suppliers $S_1,\dots, S_s$ to receivers $R_1,\dots, R_r$. Each supplier $S_i$ has a quantity $\sigma_i$ of goods it can supply; each receiver $R_j$ has a quantity $\rho_j$ of goods that it demands; and each pair $(S_i,R_j)$ of supplier and receiver has an associated cost $k_{i j}$ of transport per unit of goods. The goal is to figure out what quantity of goods to send from each supplier to each receiver so that the total transport cost is minimized.

Last time I showed that there is a dual transport problem which involves an external company taking over the transportation by assigning to each supplier $S_i$ a price $v_i$ that the company will buy a unit of goods for and to each receiver $R_j$ a price $u_j$ that they’ll sell a unit of goods for, so that, for the the consortium of suppliers and receivers, selling one unit of goods at a supplier and buying it back at a receiver costs less than the own original transport cost, ie. $u_j-v_i\le k_{i j}$ for all $i,j$. The goal is to assign the prices so that the external company doing the transportation maximizes their total revenue $\sum_{j=1}^r u_j \rho_j- \sum_{i=1}^s v_i\sigma_i$.

Strong optimal transport duality is the fact that the minimum cost for the original (‘primal’) transport problem is equal to the maximum revenue for the dual transport problem.

What I want to show you is a duality within the dual problem. It turns out that the optimal prices at the suppliers will be dual, in a specific sense, to the optimal prices at the receivers.

Within the dual problem we’ll have a vector of prices $v=(v_1,\dots, v_s)$ at the suppliers and a vector of prices $u=(u_1,\dots, u_r)$ at the receivers. Call a pair of price vectors $(v;u)$ that satisfy the contraints – $u_j-v_i\le k_{i j}$ for all $i,j$ – a pricing plan.

Example. Our example was of transporting bread from three bakeries – Fletcher’s Bakery, Depot Bakery and Gerry’s Bakery – to three cafés – Cawa, Tamper and The Rude Shipyard. This had the following transport costs.

	Cawa	Tamper	Rude Shipyard
Fletcher's	39	44	47
Depot	22	22	30
Gerry's	14	25	29

The supply and demand, in loaves, was as follows.

	Cawa	Tamper	Rude Shipyard	Supply
Fletcher's				350
Depot				200
Gerry's				100
Demand	200	250	200

We are thinking of an external transport company that is buying all the goods from the suppliers and selling them back at the receivers, where the prices they can impose are subject to the constraint above.

Suppose they fix the price vector of price per unit of goods at the suppliers to be $(v_1, \dots,v_s)$. Then we can ask what is the highest price, $\hat{v}_j$, that they can charge the consortium per unit of goods at receiver $R_j$ so that they are at least as cheap as the consortium’s own transportation means. So they need $\hat{v}_j - v_i \le k_{i j}$ for all $j$ and they should take

$$\hat{v}_j := \min_i (k_{i j}+v_i).$$

Then $\hat v\coloneqq (\hat{v}_1,\dots, \hat{v}_r)$ is called the $k$-conjugate price vector at the receivers. This will give the external company the maximum revenue for the given prices at the suppliers.

Example. In our example we could arbitrarily fix the price the external company pays per loaf at the bakeries as follows: $v=(20,25,20)$.

You can calculate the conjugate prices at the cafés and you will find that they come out as follows: $\hat{v}=(34,45,49)$

This gives a total revenue of

$(34\cdot 200 + 45\cdot 250 +49\cdot 200) - (20\cdot 350+ 25\cdot 200 + 20\cdot 100 ) = 13,850$.

But now they can do the same again, and say for fixed prices at the receivers $u=(u_1,\dots,u_r)$, what is the minimum price $\tilde{u}_i$ that the external company can get away with paying for each unit of goods at supplier $S_i$ to keep to the constraint. They need $u_j - \tilde{u}_i \le k_{i j}$ for all $i$ so they should take

$$\tilde{u}_i \ge \max_i(u_j-k_{i j}).$$

The only other requirement is that prices are non-negative, so they should take

$$\tilde{u}_i \coloneqq \max(\max_i(u_j-k_{i j}),0).$$

Example. Using the café prices computed above, $u=\hat{v}=(34,45,49)$, you can compute the following bakery prices: $\tilde{u}=(2,23,20)$.

This would give a revenue of

$(34\cdot 200 + 45\cdot 250 +49\cdot 200) - (2\cdot 350+ 23\cdot 200 + 20\cdot 100 ) =20,550.$

This is certainly an improvement on the revenue that we saw above.

So we started with supplier price vector $v$, computed the conjugate receiver price vector $\hat{v}$ and obtained a pricing plan $(v;\hat{v})$. But then we took the conjugate prices of our new receiver price vector to get a new supplier price vector and a pricing plan $(\tilde{\hat{v}}; \hat{v})$ which gives better revenue. The natural thing here is to keep on going: take the conjugates of the new supplier price vector to get a new price plan $(\tilde{\hat{v}} ;\hat{\tilde{\hat{v}}})$ with even better revenue, and keep on taking conjugates, getting better and better price plans.

Exercise Try this! Calculate the conjugate of the bakery prices, $\tilde{\hat{v}}=(2,23,20)$.

Spoiler alert! You should find that you get back the café prices you previously computed: $\hat{\tilde{\hat{v}}}=(34,45,49)= \hat{v}$ and you don’t get improvement in revenue.

Conjugation is idempotent in the sense that doing it three times is the same as doing it once: $\hat{\tilde{\hat{v}}}= \hat{v}$ . Thus starting from a supplier price vector $v$ the best one can do using this approach is the pricing plan $(\tilde{\hat{v}}; \hat{v})$ which might or might not be optimal.

However, what this does tell us is that if we seeking an optimal pricing plan $(v; u)$ then it can be assumed that the supplier price vector is conjugate to the receiver price vector, and vice versa: $u=\hat v$ and $v=\tilde u$. This is because the pricing plan $(\hat{\hat{v}}; \hat{v})$ satisfies this conjugacy condition and has at least as much revenue as the plan $(v;u)$.

Say that a pricing plan $(v;u)$ is tight if $u=\hat v$ and $v=\tilde u$. So I’ve shown that to find an optimal pricing plan it suffices to consider tight pricing plans.

Looking at this from a step back, what we have is a pair of maps

and the tight pricing plans are those pairs of price vectors which are ‘fixed’ by these maps.

If you’re well-attuned to enriched category theory you might be unsurprised to learn that I will show that this pair of maps form an enriched adjunction, and this adjunction is of a standard type coming from the transport cost matrix $k$, thought of as an enriched profunctor. The tight pricing plans then form the centre of this adjunction.

Modelling with enriched categories

As I’d said previously I want to model this with enriched categories, because it ties in with other things. The enriching category is going to be a sort of ‘ground ring’ and will be thing in which the prices live. I want to be able to add (and ‘subtract’) prices to (and from) each other and to compare prices to each other (as well as, relatedly, take suprema and infima); I will never want to multiply prices by each other.

From my perspective, at this point, there are four ‘obvious’ candidates for the place that prices will live.

• The extended real numbers: $\{-\infty\}\cup\mathbb{R}\cup\{ \infty\}= \{a\mid -\infty\le a \le \infty\}$. I’ve stuck $\pm \infty$ on to the real numbers so that we have infima and suprema of all sets.
• The extended non-negative real numbers $\mathbb{R}_{\ge 0}\cup \infty= \{a\mid 0\le a \le \infty\}$. It’s often a reasonable assumption that prices are non-negative.
• The extended integers $\{-\infty, \dots, -1, 0, 1, 2, \dots, \infty\}$. I might want to consider discrete prices.
• The extended natural numbers $\{0,1,2,\dots ,\infty\}$. I might want non-negative, discrete prices.

I am going to work with the extended non-negative reals here. I hope to show in the next post why sometimes allowing negative prices allows comparison between different approaches. There’s already been some responses in the comments about working over the integers

Let’s define $\bar{\mathbb{R}}_{+}$ to be the category whose object set is the extended non-negative real numbers, $\mathbb{R}_{\ge 0}\cup \infty$, with a unique morphism from $a$ to $b$ precisely when $a\ge b$. The categorical product of two numbers is their maximum and the categorical coproduct is their minimum. Equip this category with a monoidal product which is simply addition. Clearly the unit object is $0$. This is a closed monoidal category, with the internal hom $[a,b]$ given by trunctated subtraction $$a+b\ge c \qquad \iff \qquad a\ge c \,\dot{-}\, b,$$ where $c \,\dot{-}\, b \coloneqq \max(c-b, 0)$.

Categories enriched over $\bar{\mathbb{R}}_+$ are then generalized metric spaces or Lawvere metric spaces, so these are sets with a distance between each pair of points, which is possibly infinite, satisfies the triangle inequality and points have zero self-distance. The distance is not necessarily symmetric. In our case distance is measured in units of cost, so should be thought of as cost.

I will model the suppliers as the discrete $\bar{\mathbb{R}}_+$-category $\mathcal{S}$ with the set of suppliers $\{S_1,\dots,S_s\}$ as its set of objects. Saying that this is a discrete $\bar{\mathbb{R}}_+$-category is saying that there is infinite cost to go from one supplier (or bakery) to another, or, to put it another way, we don’t allow transportation between suppliers. Similarly I will model the receivers by the discrete $\bar{\mathbb{R}}_+$-category $\mathcal{R}$ which has the receivers as its objects.

Then the price vectors are modelled as presheaves, or enriched functors to the ground category $\bar{\mathbb{R}}_+$. Here an enriched functor means a cost-non-increasing function. As both $\mathcal{S}$ and $\mathcal{R}$ are discrete, the cost-non-increasing condition is vacuous.

Thus the sets of vectors get modelled as enriched functor categories:

$$\begin{aligned} \{\text{supplier price vectors}\}\quad&\leftrightarrow\quad \bar{\mathbb{R}}_+^\mathcal{S}\,;\qquad& \{\text{receiver price vectors}\}\quad&\leftrightarrow\quad \bar{\mathbb{R}}_+^{\mathcal{R}}\,. \end{aligned}$$

The transportation cost is modelled as a profunctor $k\colon \mathcal{S}\rightsquigarrow \mathcal{R}$ from suppliers to receivers, this means it’s an $\bar{\mathbb{R}}_+$-functor

$$k\colon \mathcal{S}^\mathrm{op}\otimes \mathcal{R}\to \bar{\mathbb{R}}_+.$$

A functor $\mathcal{S}\to \bar{\mathbb{R}}_+$ can be thought of as a profunctor ${\star}\rightsquigarrow \mathcal{S}$ where $\star$ is the monoidal unit for $\bar{\mathbb{R}}_+$-categories, ie. the one-object $\bar{\mathbb{R}}_+$-category. Similarly a profunctor $\star\rightsquigarrow \mathcal{R}$ can be thought of as a functor $\mathcal{R}\to \bar{\mathbb{R}}_+$.

Thus profunctor composition with $k\colon \mathcal{S}\rightsquigarrow \mathcal{R}$ gives us a functor $k\circ {-} \colon\bar{\mathbb{R}}_+^\mathcal{S}\to \bar{\mathbb{R}}_+^\mathcal{R}$. In general terms this composition is given by a coend expression, which in our case can be written as a certain minimum as follows: $$\begin{aligned} (k\circ v)(R_j)&\coloneqq \int^{S_i\in \mathcal{S}} k(S_i, R_j)\otimes v(S_i)\\ &=\min_{S_i\in \mathcal{S}}\bigl(k(S_i, R_j) + v(S_i)\bigr). \end{aligned}$$ Apart from the notational change of $k$ and $v$ from indexed matrix and vector to profunctor and functor respectively, this is exactly the expression for the $k$-conjugate $\hat{v}$ of $v$ given above.

In the case of nice ground category, enriched profunctors form a closed bicategory, what this means is that the functor $(k\circ {-})$ of post-composing with a fixed profunctor has a right adjoint $(k\triangleright {-})$. This is analogous to (and can be thought of as being a generalization of) the tensor-hom adjunction.

Shen and Zhang (see for example Categories enriched over a quantaloid: Isbell adjunctions and Kan adjunctions) call this adjunction the Kan adjunction coming from a profunctor to distinguish it from what they call the Isbell adjuntion coming from a profunctor; the Isbell adjunction is the adjunction I’ve described here at the café before as it’s the one that appears in the profunctor nucleus, and I’m hoping to revisit it in the next post. I’m not a fan of naming things after people, but in the absence of more descriptive terms, I’ll stick to these terms here.

So from our profunctor $k\colon \mathcal{S}\rightsquigarrow \mathcal{R}$ we get a right adjoint functor $k\triangleright{-}\colon \bar{\mathbb{R}}_+^\mathcal{R}\to \bar{\mathbb{R}}_+^\mathcal{S}$, given in general by an end, which in our case becomes a minimum as follows: $$\begin{aligned} (k\triangleright u)(S_i)&\coloneqq \int_{R_j\in \mathcal{R}}[ k(S_i, R_j), u(R_j)]\\ &=\max_{R_j\in \mathcal{R}}\bigl(u(R_j)\,{\dot{-}}\, k(S_i, R_j) \bigr). \end{aligned}$$ And again, up to changes in notation, this is exactly the expression for the conjugate, $\tilde{u}$, of $u$ as given above.

This means that the pair of $k$-conjugation maps

should be thought of as the Kan adjunction of the cost profunctor $k$,

with the tight pricing plans forming the centre of this adjunction.

What do we gain from this?

A standard question to be asked at this juncture is “What’s the point?” Well, there’s several answers to the question. Firstly, it confirms that this is a natural mathematical construction in the sense that it is an example of something that crops up in many places. Secondly, it means that we have the tools and intuition of adjunctions to apply here; for instance, the fact that we have idempotency is a standard fact about adjunctions when you’re enriched over a poset. Thirdly, it attunes us to the possibility that category theory might pervade deeper in related areas. Hopefully I’ll be able to show you a bit more of that.

Next time I want to show you how this relates to the profunctor nucleus construction that I’ve described before, in particular how a Kan adjunction can be related to an Isbell adjunction when you are enriching over a compact closed category such as the extended real numbers, but not the extended non-negative real numbers which we’ve been using here.

I’ll leave a little exercise for the algebraically minded amongst you, which involves the Kan adjunction in the context of algebra bimodules.

Digression/Exercise. Consider categories enriched in $Vect$, the category of finite dimensional vector spaces over the complex numbers $\mathbb{C}$. Let $A$ and $B$ be finite-dimensional algebras over $\mathbb{C}$ which we consider as one-object $Vect$-categories. A profunctor $M\colon A\rightsquigarrow B$ is then precisely a $B$-$A$-bimodule. What is the Kan adjunction in this case?

If $f\colon B\to A$ is an algebra map then we get an $B$-$A$-bimodule ${}_f A$ which is the underlying vector space of $A$ equipped with the action $b\cdot a\cdot a'= f(b) a a'$. What is the Kan adjunction for ${}_f A\colon A\rightsquigarrow B$?