Loading...
墨滴

张春成

2021/07/17  阅读:40  主题:默认主题

行路难

行路难

过分追求全局最优会降低局部效率。 那么这种情况有多严重呢?本文是基于图分析对该问题进行量化。 通过分析,我们可以看到以下现象,

  1. 全局最优解往往会陷于路径依赖困境;
  2. 可以通过极少的“捷径”开销,提升总体效率;
  3. 但全局最优往往已然促成“天然垄断”;
  4. 总体效率的提升会造成“垄断”权益的稀释,从而受到阻碍。

虽然修建捷径是利国利民的好事,但会损害天然垄断的利益。 不难想见,垄断权益受到损害的体量,就是修建捷径的成本。 其值甚至与社会总收益相当,甚至可能产生“投鼠忌器”级别的阻力。 所谓“行路难”是也。


路径依赖与天然垄断的形成

在图论体系下,我们可以使用“全局最短”的连接图,对全部节点进行连接

Shortest Path
Shortest Path

在该图体系下,我们可以从任意节点, 经过特定的路径,可以得到其他节点。

我们假定这些节点是一个一个的收费站。 如果它对所有经过它的车辆进行收费,那么它的收益如下图所示

Raw Profits
Raw Profits

图中可以看到,

  • 越靠近“中心”的节点,其收益越高;
  • 越边缘的节点,其收益越少。

其中,收益高的“重要”节点,就形成了“天然垄断”。 但是这种垄断地位是建立在全局效率低下的条件下的。

然而,火车修到哪里,文明就走到哪里。 人们必然会想办法提升通行效率。 前文已经论述,一个可行的方法那是修建“捷径”。

要想富先修路

我们可以根据《改出路径依赖》一文提出的方法,找到一些关键“捷径”, 从而改出“路径依赖”困境。

Short Cuts
Short Cuts

上图表示我们加入了3条捷径。

加入捷径后,整体通行环境出现了改变,我们用直方图的方式进行展示

Gain on Histogram
Gain on Histogram

如图所示,我们通过添加3找捷径,提升了19.63%的总体通行效率。 也就是说,在新图的条件下,整个社会可以节省约1/5的通行成本。 这本是利国利民的好事。 但有一些“副作用”。

大而不能倒

此时各个节点的收益分布改变为下图所示

Short Cut Profits
Short Cut Profits

与全局最优图相比,垄断地位节点的收益从6000降低到了3500

为了对各个节点的“过路费”变化进行量化,我们对两个情况下的收益相减, 得到下图

Deficits
Deficits

可以看到,节点的收益有增有减,总体上,减多而增少。 问题就出会产生损失(红色节点)的这些节点上。 用网络流行的话说,这些节点就是所谓“大而不能倒”的节点。 捷径会损害它们的垄断收益。

我们从成本的角度上来看这个问题,损益表如下所示

BalanceSheet
BalanceSheet
  • 修建捷径会降低全社会的成本,总收益为+28646
  • 它同样会降低所有节点收益,总损失为-28971
  • 如果你觉得收益和损失相抵,可能就错了;
    • 因为损失利益的垄断节点会联合起来抵抗新兴集团;
    • 而新兴集团天生分散,且在变革发生前尚不占有资源;
  • 那么,天然垄断集团的损失有多大呢? 我们只需要考虑有损失的节点就可以了,其值为-44024
Sorted Deficits
Sorted Deficits

也就是说,为了推动捷径建设,除去建设成本之外。 推动者需要额外付出-44024 + 28646的变革成本,才能对抗垄断集团造成的阻碍。 其值甚至与社会总收益相当,甚至可能产生“投鼠忌器”级别的阻力。

所谓“行路难”正在于此。

代码实现

为了完成以上分析,我写了个工程TrafficAnalysis[1],欢迎大家访问。

  • 我们需要这些包
# %%
from utils.deploy import *
from utils.viz import plot_layout
from utils.graph_methods import compute_dist, mask_dist, spectral_clustering, PathSeacher
from utils.layout_methods import layout_random
from utils.routing_methods import route_least_length, route_between_labels
  • 随机生成一堆点
# %%
nodes = layout_random()
  • 计算全局最优解
# %%
dist = compute_dist(nodes)
links_shortest = route_least_length(dist)
mdist = mask_dist(dist, links_shortest)
labels = spectral_clustering(mdist)
labels = [str(e) for e in labels]
plot_layout(nodes, color=labels, links=links_shortest, title='Shortest Path')
  • 计算最优捷径
# %%
ps = PathSeacher()
_dist = mask_dist(dist, links_shortest, mode='mask_unlink', mask_value=np.inf)
m = ps.trace_all(_dist)

_dist = dist - (m + m.transpose())
links_between = route_between_labels(nodes, _dist, labels)
plot_layout(nodes, color=labels, links=links_between, title='Short Cuts')
  • 绘制新连接图
# %%
plot_layout(nodes, color=labels, links=links_shortest +
            links_between, title='New Path')
  • 全局效率的提升
# %%
_dist = mask_dist(dist, links=links_shortest+links_between,
                  mode='mask_unlink', mask_value=np.inf)

ps1 = PathSeacher()
m1 = ps1.trace_all(_dist)

# %%
df_a = pd.DataFrame(m[m != 0], columns=['count'])
df_a['name'] = 'Raw'

df_b = pd.DataFrame(m1[m1 != 0], columns=['count'])
df_b['name'] = 'ShortCuts'

df = pd.concat([df_a, df_b], axis=0, ignore_index=True)
df

x = np.sum(m - m1)
px.histogram(df, color='name', opacity=0.5,
             barmode='overlay', title='Gain on Histogram (Gain = {} | {:.2f}%)'.format(x * 2100 * x / np.sum(m)))
  • 全局最优图的“收益”分布
# %%
mem = ps.memory
mem1 = ps1.memory

count = np.zeros(len(nodes))
for k, v in tqdm(mem.items()):
    for e in v:
        count[e] += 1

count

count1 = np.zeros(len(nodes))
for k, v in tqdm(mem1.items()):
    for e in v:
        count1[e] += 1

count1

sum(count), sum(count1)

plot_layout(nodes, color=count, links=links_shortest,
            link_color='gray', title='Profits of Nodes (Raw)')
  • 新图的“收益”分布
# %%
plot_layout(nodes, color=count1, links=links_shortest +
            links_between, link_color='gray', title='Profits on Nodes (ShortCut)')
  • 捷径带来的“个体损失”
# %%
plot_layout(nodes, color=count1-count, links=links_shortest,
            link_color='gray', title='Deficits')
  • 捷径带来的“损益”表
# %%

balance_sheet = dict(
    global_grain=(np.sum(m) - np.sum(m1)) * 2,
    individual_lost=np.sum(count1 - count),
    individual_lost_neg=np.sum((count1 - count)[count1 - count < 0])
)

pd.DataFrame([balance_sheet]).transpose()
  • 捷径带来的“损失”直方图
# %%
px.bar(sorted(count1 - count), title='Sorted Deficits')

参考资料

[1]

TrafficAnalysis: https://github.com/listenzcc/TrafficAnalysis

张春成

2021/07/17  阅读:40  主题:默认主题

作者介绍

张春成