Como dividir o custo numa viagem partilhada?

Um exemplo de aplicação dos valores de shapley

Na definição de uma rede de transportes públicos, quer no seu desenho geográfico, quer na definição dos níveis de serviço, emerge uma questão fundamental: como imputar o custo? Este dilema é especialmente relevante em sistemas de transporte coletivo, onde múltiplos passageiros utilizam o mesmo serviço para chegar a destinos diferentes a horas diferentes. Para abordar esta questão, podemos recorrer aos valores de Shapley, uma ferramenta da teoria dos jogos que oferece uma solução equitativa para a divisão de custos em situações de cooperação.

Neste artigo, iremos explorar um exemplo prático de como os valores de Shapley podem ser aplicados para dividir o custo de uma viagem partilhada entre um grupo de amigos que decidem utilizar um serviço de táxi para se deslocarem juntos. Através deste exemplo, vamos entender como esta abordagem pode garantir o benefício do grupo e que cada amigo paga uma parte justa do custo total da viagem, levando em consideração as diferentes contribuições de cada um para a viagem.

Dividir o custo de forma justa é importante?

Dividir o custo de uma viagem partilhada de forma justa é crucial para manter a harmonia e a satisfação entre os participantes. Quando um grupo de amigos decide partilhar uma viagem, cada um contribui de maneira diferente para a definição da viagem, seja em termos de distância percorrida, tempo gasto ou recursos utilizados. Se o custo não for dividido de forma justa, o interesse individual de cada um, pode deixar de estar alinhado com o interesse coletivo. Uma divisão justa do custo não apenas promove a cooperação e a solidariedade entre os amigos, mas também incentiva o uso de uma solução comum.

Extendendo ao domínio dos transportes públicos, a cooperação permite otimizar os recursos disponíveis, reduzir o impacto ambiental e melhorar a eficiência do sistema de transporte como um todo. Esta dinâmica de ciclo virtuoso permite que o sistema de transporte colectivo público se torna verdadeiramente sustentável, eficiente e atractivo com impacto direto não só na população (utilizadores e não utilizadores), mas também na economia e no ambiente.

O objectivo desta cooperação é o de garantir que o grupo como um todo retire benefícios da cooperação, mas também que cada um dos amigos sinta que a sua contribuição é valorizada e que o custo que paga é proporcional ao benefício que recebe.

Photo by Sarah Noltner on Unsplash

Exemplo prático: Dividindo o custo de uma viagem partilhada

Custos isolados

Vamos imaginar um grupo de três amigos, Ana, Bruno e Carolina, foram jantar fora juntos. No final do jantar decidem partilhar uma viagem de táxi para voltarem a casa. Cada um dos amigos tem um destino diferente. Para entender como dividir este custo de forma justa, precisamos primeiro calcular os custos isolados de cada amigo, ou seja, quanto cada um pagaria se fosse viajar sozinho. - Ana: 4 euros - Bruno: 6 euros - Carolina: 20 euros

import plotly.graph_objects as go

# Node positions
nodes = {
    'O': (-1, -1.3),
    'A': (0, 0),
    'B': (0, -1.8),
    'C': (0.5, -4),
}

# Undirected edges with weights (duplicates removed)
edges = [
    ('O', 'A', 4),
    ('O', 'B', 6),
    ('O', 'C', 20),
    ('A', 'B', 3),
    ('A', 'C', 17),
    ('B', 'C', 15),
]

fig = go.Figure()

# Draw edges
for src, dst, weight in edges:
    x0, y0 = nodes[src]
    x1, y1 = nodes[dst]

    fig.add_trace(go.Scatter(
        x=[x0, x1], y=[y0, y1],
        mode='lines',
        line=dict(width=2, color='#636efa'),
        hoverinfo='none',
        showlegend=False
    ))

    # Weight label at midpoint
    fig.add_annotation(
        x=(x0 + x1) / 2, y=(y0 + y1) / 2,
        text=f"<b>{weight}</b>",
        showarrow=False,
        font=dict(size=12, color='#ff7f0e'),
        bgcolor='white',
        bordercolor='#ff7f0e',
        borderwidth=1,
        borderpad=3,
    )

# Draw nodes
fig.add_trace(go.Scatter(
    x=[pos[0] for pos in nodes.values()],
    y=[pos[1] for pos in nodes.values()],
    mode='markers+text',
    marker=dict(size=40, color='#1f77b4', line=dict(width=2, color='white')),
    text=list(nodes.keys()),
    textfont=dict(size=16, color='white', family='Arial Black'),
    textposition='middle center',
    hoverinfo='text',
    hovertext=list(nodes.keys()),
    showlegend=False
))

fig.update_layout(
    title=dict(text='Gráfico esquemático (Valores em euros)', font=dict(size=20)),
    xaxis=dict(showgrid=False, zeroline=False, showticklabels=False),
    yaxis=dict(showgrid=False, zeroline=False, showticklabels=False),
    plot_bgcolor='#f9f9f9',
    paper_bgcolor='white',
    margin=dict(l=40, r=40, t=60, b=40),
    width=750,
    height=550,
)

fig.show()

Avaliação dos diferentes trajetos possíveis

Custo dos diferentes trajetos possíveis

Ordem do percurso	custo total da viagem
O-A-B-C	4 + 3 + 15 = 22
O-A-C-B	4 + 15 + 17 = 36
O-B-A-C	6 + 3 + 17 = 26
O-B-C-A	6 + 15 + 17 = 38
O-C-A-B	20 + 17 + 3 = 40
O-C-B-A	20 + 15 + 6 = 41

Após avaliarem os custos dos diferentes trajetos possíveis, os três amigos percebem que o trajeto mais barato é o O-A-B-C, ou seja, o táxi passa primeiro pela casa da Ana, depois do Bruno e por fim da Carolina. O custo total da viagem é de 22 euros. Caso cada um dos amigos pagasse o custo isolado, o custo total seria de 30 euros, ou seja, a partilha da viagem permite uma poupança de 8 euros para o grupo como um todo. Mas como dividir estes 22 euros de forma justa?

Mas esta não é a única conclusão a que chegam. Percebem também que há várias coligações possíveis.

Custo das diferentes coligações possíveis

Coligação	Custo da viagem
A	4
B	6
C	20
A,B	7
A,C	21
B,C	21
A,B,C	22

Modelo mais simples, dividir o custo total por 3

A forma mais simples de dividir o custo total da viagem seria dividir os 22 euros por 3, ou seja, cada amigo pagaria aproximadamente 7.33 euros. No entanto, esta abordagem não leva em consideração as diferentes contribuições de cada amigo para a viagem, nem o facto de que cada um tem um destino diferente. Por exemplo, a Carolina tem um custo isolado muito mais alto do que os outros dois amigos, e a Ana tem um custo isolado mais baixo. Dividir o custo total por igual, distribui de forma desigual o benefício da cooperação. A Carolina beneficia mais da cooperação, pois paga muito menos do que o seu custo isolado, enquanto que tanto a Ana como o Bruno são prejudicados.

Nestas condições, a Ana e o Bruno decidem partilhar um táxi entre eles, e a Carolina acaba por viajar sozinha. O custo total da viagem do Bruno e da Ana é de 7 euros, ou seja, cada um paga 3.5 euros, beneficiando ambos, mas a Carolina paga o seu custo isolado de 20 euros, ou seja, no total o grupo escolhe uma solução com um custo total de 27 euros.

Modelo proporcional ao custo isolado

Outra forma em que se poderia dividir o custo total da viagem seria dividir os 22 euros de forma proporcional ao custo isolado de cada amigo. Neste caso, a Ana pagaria aproximadamente 2.93 euros, o Bruno pagaria aproximadamente 4.40 euros e a Carolina pagaria aproximadamente 14.67 euros. Esta abordagem é mais justa do que dividir o custo total por igual, pois leva em consideração as diferentes contribuições de cada amigo para a viagem e garante que cada um paga uma parte proporcional ao benefício que recebe. No entanto, ainda assim, esta abordagem não é perfeita, pois não leva em consideração as diferentes trajetórias possíveis e como cada amigo contribui para reduzir o custo total da viagem.

Nestas condições, a Ana e o Bruno decidem partilhar um táxi entre eles, e a Carolina acaba por viajar sozinha. O custo total da viagem do Bruno e da Ana é de 7 euros, aplicando as regras de proporcionalidade, a Ana paga 2.80 euros e o Bruno 4.20 euros, beneficiando ambos, mas a Carolina paga o seu custo isolado de 20 euros, ou seja, no total o grupo escolhe uma solução com um custo total de 27 euros.

Modelo de Shapley

O modelo de Shapley é uma abordagem mais sofisticada para dividir o custo de uma viagem partilhada de forma justa. Ele leva em consideração as diferentes contribuições de cada amigo para a viagem, bem como o facto de que cada um tem um destino diferente. O valor de Shapley para cada amigo é calculado com base na sua contribuição marginal para a viagem, ou seja, quanto cada amigo contribui para reduzir o custo total da viagem em comparação com o custo isolado.

Para calcular a contribuição marginal, agora que já sabemos o custo total da viagem optimizado, precisamos avaliar os diferentes trajetos possíveis.

Ordem do percurso	A	B	C	custo total da viagem
O-A-B-C	4	3	22-4-3=15	22
O-A-C-B	4	22-17-4=1	17	22
O-B-A-C	1	6	22-1-6=15	22
O-B-C-A	22-6-15=1	6	15	22
O-C-A-B	1	22-20-1=1	20	22
O-C-B-A	22-20-1=1	1	20	22
Média	2	3	17	22

from itertools import permutations

# from the article, change it as you wish
coalition_values = {
    frozenset(): 0,
    frozenset("A"): 4,
    frozenset("B"): 6,
    frozenset("C"): 20,
    frozenset(("A", "B")): 7,
    frozenset(("A", "C")): 21,
    frozenset(("B", "C")): 21,
    frozenset(("A", "B", "C")): 22,
}

def compute_shapley_values(coalition_values, player):
    players = max(coalition_values, key=lambda x: len(x))
    contributions = []

    for permutation in permutations(players):
        player_index = permutation.index(player)
        coalition_before = frozenset(permutation[:player_index])  # excluding player
        coalition_after = frozenset(permutation[: player_index + 1])  # player joined coalition
        contributions.append(coalition_values[coalition_after] - coalition_values[coalition_before])

    return sum(contributions) / len(contributions)  # average, results in Shapley values

for player in ("A", "B", "C"):
    print(player, compute_shapley_values(coalition_values, player))

A 2.0
B 3.0
C 17.0

Calculando a média de todos os trajetos possíveis, obtemos qual deve ser a contribuição de cada amigo para a viagem: - Ana: 2 euros - Bruno: 3 euros - Carolina: 17 euros

Neste caso, todos os amigos beneficiam da cooperação, a Carolina poupa 3 euros, o Bruno poupa 3 euros e a Ana poupa 2 euros. O custo total da viagem é de 22 euros, ou seja, o grupo poupa 8 euros em comparação com os custos isolados. Esta abordagem é mais justa do que dividir o custo total por igual, pois leva em consideração as diferentes contribuições de cada amigo para a viagem e garante que cada um paga uma parte proporcional ao benefício que recebe.

Reflexão

Analisando os benefícios da cooperação, é contra-intuitivo que a Carolina tenha uma poupança igual à do Bruno quando o seu custo isolado é muito mais alto do que o do Bruno. Este resultado é explicado pelo facto de a casa do Bruno estar “a caminho” da casa da Carolina, ou seja, o valor de shapley captura o custo marginal de fazer o desvio para deixar o Bruno. Caso a Carolina e Ana tivessem decidido partilhar um táxi entre elas, o custo total da viagem seria de 21 euros, enquanto que nesta solução as duas amigas suportam entre elas um custo total de 19 euros.

Aplicação dos valores de Shapley na definição de redes de transporte público

Este exemplo prático de como os valores de Shapley podem ser aplicados para dividir o custo de uma viagem partilhada entre um grupo de amigos, pode ser estendido para a definição de redes de transporte público. Em vez de amigos, temos passageiros ou territórios, e em vez de uma viagem de táxi, temos um sistema de transporte coletivo. Os valores de Shapley podem ser utilizados para determinar como dividir o custo do sistema de transporte coletivo, levando em consideração as diferentes contribuições de cada passageiro para o sistema e garantindo que cada um suporta uma parte justa do custo total do sistema.

Em transportes, a única aplicação prática de valores de Shapley que conheço, está relacionada com infraestruturas como aeroportos quando se pretende, por razões económicas juntar numa só infraestrutura diferentes projetos que possuem requisitos comuns e requisitos específicos. Nesses casos é habitual recorrer a valores de Shapley para determinar a imputação da componente comum de forma justa a cada projeto.

Pausa Técnica