Algorithm to solve 'user optimum' 'polygamic' stable marriage problem: Optimally assign travellers to shared rides.

Question

I am looking for inspiration to reformulate the classical assignment problem into something behaviourally richer (closer to Nash equilibrium, or a stable marriage problem).

I find it tricky to represent the joint decisions where the 'marriage' can contain more than two, and 'marriage' is feasible only if all parties aggre on this.

I apply this for the shared-rides problem, where travellers may reduce their cost if they travel together (e.g. Uber Pool). For system optimal solutions it yields a simple linear assignment problem, which however seems to get complex and non-analytical if we consider joint actions, their dependencies and gains at individual rather than cumulated level.

---

Let's consider the following:

1. There are $T$ travellers willing to reach their destination at the lowest cost (travel time and cost).
2. They can supply their demand with one of $R$ rides.
3. Each ride is composed of one or more travellers $r = \lbrace t_r:t\in T \rbrace$. Rides of more than one traveller are shared, typically they offer better option for travellers, yet they are feasible if and only if all travellers select it, conversely it is not feasible if at least one of sharing travellers opts for another ride.
4. Each ride has its cost for the system provider $c_r$ and for traveller using this ride $c_{r,i}$
5. Each traveller has to be assigned to exactly one ride, obtained through incidence matrix $I_{t,r}$ being one if traveller $t$ is assigned to a ride $r$.
6. Control variable is binary vector $x = \lbrace x_i , \dots , x_r \rbrace$ being one if ride is assigned and zero otherwise.
7. If ride is selected ($x_i = 1$) all travellers of this ride will use it. Or inversely, $x_i$ only if all travellers decide to use it.

If we are interested in minimal cost solution can be obtained with a simple assignment problem, solved with bi-partite matching:

$min \sum_R x_ic_i$

Where $c_i$ is cost of a ride, with two interesting formulations:

• ride cost for operator (e.g. vehicle hours)
• ride cost for travellers (e.g. sum of travel times)

I can solve it in python for big instances (5000 travellers x 10 000 rides) in short time with reasonable results.

---

Though if we look at individual decisions and their optimality we find interesting relations.

Let's consider:

1. three travellers $T= \lbrace t_1, t_2, t_3 \rbrace$
2. five rides $R= \lbrace (t_1), (t_2), (t_3), (t_1, t_2), (t_1, t_3), (t_1, t_2, t_3) \rbrace $
3. Cost of a single ride for travellers and vehicles is equal to 1: $ c_t=1: t \in \lbrace 1,2,3 \rbrace $
4. Cost of a ride shared by travellers is lower than sum of single rides: $ c_t<2: t \in \lbrace 4,5 \rbrace $, $c_5 <3$

Yeilding for instance the following cost matrix:

$ c_{t,r} = \begin{pmatrix} 1 & {-} & {-} & {0.7} & {0.6} & {0.9} \\ {-} & 1 & {-} & {0.5} & {-} & {0.9} \\ {-} & {-} & 1 & {-} & {0.7} & {0.5} \\ \end{pmatrix}$

If we optimize using global costs formulation we find the optimum easily.

The operator costs are: $c = \begin{pmatrix} 1 & 1 & 1 & 1.2 & 1.4 & 2.4 \\ \end{pmatrix}$ the minimal cost is $2.2$ obtained at solution: $x = \begin{pmatrix} 0 & 0 & 1 & 1 & 0 & 0 \\ \end{pmatrix}$.

With other feasible options being:

single rides: $\begin{pmatrix} 1 & 1 & 1 & 0 & 0 & 0 \\ \end{pmatrix}$,

one ride: $\begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix}$,

two rides: $\begin{pmatrix} 0 & 1 & 0 & 0 & 1 & 0 \\ \end{pmatrix}$.

---

However if we look at the perspective of individuals there is clearly a handful of interesting insights and puzzles:

1. optimal choice for traveller 1 is ride 5, yielding cost of 0.6, though it is only feasible if traveller 3 also opts for it.
2. traveller 3 opts for ride 6 yet he has small chances that this solution will be choose, since this is a second best option for both travellers 1 and 2.
3. In the system optimal solution traveller 3 rides alone at highest cost.
4. System optimal solution is not optimal for neither traveller 1 nor 3.
5. Most equilibrated solution (ride shared by 3 travellers) is not optimal in most of closed form cost formulations.

How can we approach this problems, I am looking for inspirations, algorithms, methods.