67

　　布雷斯悖论
　　Braess的悖论是观察到在道路网络中添加一条或多条道路会减慢通过它的整体交通流量。这个悖论是由德国数学家迪特里希·布雷斯在1968年发现的。
　　这个悖论可能在电网和生物系统中有类比。有人建议，理论上，可以通过移除故障网络的某些部分来改善故障网络。这个悖论已被用来解释当现有主要道路关闭时交通流量得到改善的例子。
　　发现和定义
　　德国鲁尔大学的数学家迪特里希·布雷斯(DietrichBraess)在进行交通建模时注意到，添加一条新道路可能会阻碍道路网络中的流动。他的想法是，如果每个司机都在为最快的路线做出最佳的自利决策，那麽司机可能会过于频繁地选择捷径，从而使司机的旅行时间尽可能短。更正式地说，布雷斯发现背后的想法是，纳什均衡可能不等同于通过网络的最佳整体流量。
　　悖论表述如下：
　　“对于路网的每个点，给定从它开始的汽车数量和汽车的目的地。在这种情况下，人们希望估计交通流量的分佈。一条街道是否优于另一条街道取决于不不仅取决于道路的质量，而且还取决于流量的密度。如果每个驾驶员都选择对他们最有利的路径，那麽由此产生的运行时间不必是最小的。此外，通过一个示例表明，扩展路网的减少可能会导致交通的重新分配，从而导致更长的个人运行时间。”
　　当移动实体自私地选择其路线时，向网络添加额外容量在某些情况下会降低整体性能。这是因为这样一个系统的纳什均衡不一定是最优的。网络变化引发了一种新的博弈结构，导致了（多人）囚徒困境。在纳什均衡中，司机没有动力改变他们的路线。虽然系统不处于纳什均衡，但个别司机可以通过改变他们所走的路线来改善他们各自的旅行时间。在Braess悖论的情况下，儘管整体性能下降，司机仍将继续转换，直到达到纳什均衡。
　　如果延迟函数是线性的，那麽添加一条边永远不会使平衡时的总行程时间变差超过4/3。
　　悖论的可能实例
　　患病率
　　1983年，Steinberg和Zangwill在合理的假设下，提供了当增加一条新路线时，在一般交通网络中出现Braess悖论的充要条件。（请注意，他们的结果适用于添加任何新路由，而不仅仅是添加单个链接的情况。）作为推论，他们得出，当随机的新路由被添加时，Braess悖论发生的可能性和不发生的可能性一样大。添加。
　　交通
　　Braess悖论在道路网络减少（可能导致个人通勤时间减少）的情况下具有对应关係。
　　在韩国首尔，由于清溪川修復工程的一部分高速公路被拆除，城市周围的交通加速了。在德国斯图加特，1969年对公路网进行投资后，交通状况一直没有好转，直到一段新建的道路再次封闭通行。1990年，纽约市第42街因地球日临时关闭，减少了该地区的拥堵程度。2008年，Youn、Gastner和Jeong在波士顿、纽约市和伦敦展示了可能实际发生这种情况的具体路线，并指出了可能关闭的道路以减少预计的旅行时间。2009年，纽约尝试关闭时代广场和先驱广场的百老汇，从而改善交通流量和永久性步行广场。
　　2012年，法兰西岛规划与发展研究所的PaulLecroart写道：“儘管最初存在担忧，但主要道路的拆除不会导致交通状况恶化，超出起步调整。交通转移是有限的。并低于预期”。他还指出，一些私家车旅行（和相关的经济活动）并未转移到公共交通工具上，而是直接消失（“蒸发”）。
　　当道路封闭不是城市项目的一部分而是事故的后果时，也会观察到同样的现象。2012年在鲁昂，一座桥被大火烧毁。在接下来的两年裡，其他桥樑的使用量增加了，但过桥的汽车总数减少了。
　　电
　　2012年，马克斯普朗克动力学和自组织研究所的科学家通过计算建模证明了这种现像在发电分散的输电网络中发生的可能性。
　　2012年，来自InstitutNéel(CNRS,France)、INP(France)、IEMN(CNRS,France)和UCL(Belgium)的国际研究团队在PhysicalReviewLetters上发表了一篇论文，表明Braess悖论可能发生在介观电子系统。特别是，他们表明，在纳米级网络中添加电子路径反而会降低其电导率。模拟以及使用扫描门显微镜在低温下的实验都证明了这一点。
　　生物学
　　AdilsonE.Motter和合作者证明，Braess的悖论结果可能经常发生在生物和生态系统中。Motter建议移除部分受干扰的网络可以挽救它。对于濒危物种食物网的资源管理，其中许多物种可能相继灭绝，从网络中选择性地清除注定要灭绝的物种原则上可以带来防止一系列进一步灭绝的积极结果。
　　团队运动策略
　　有人提出，在篮球运动中，一支球队可以被视为一个得分路径的可能性网络，每条路径的效率不同，而明星球员可能会降低球队的整体效率，类似于过度使用的捷径会增加通过道路网络的总时间。一个建议的最大效率得分解决方案是让明星球员投篮次数与队友的投篮次数大致相同。然而，正如原始论文中所指出的，这种方法没有得到确凿的统计证据的支持。
　　数学方法
　　例子
　　考虑如下图所示的道路网络，4000名驾驶员希望在该道路网络上从起点行驶到终点。Start-A道路上的行驶时间（以分钟为单位）是旅客人数(T)除以100，Start-B上的行驶时间是恆定的45分钟（与他们对面的道路一样）。如果虚线道路不存在（因此交通网络共有4条道路），则行驶Start-A-End路线所需的时间为a司机将是一个100+45.驾驶Start-B-End路线所需的时间b司机将是b100+45.由于有4000名司机，事实上a+b=4000可以用来推导出这样一个事实a=b=2000当系统处于平衡状态时。因此，每条路线採取2000100+45=65分钟。如果任一路线花费的时间更少，这将不是纳什均衡：理性的司机会从较长的路线切换到较短的路线。
　　现在假设虚线A-B是一条行驶时间极短的道路，大约为0分钟。假设道路是开放的，一位司机尝试开始-A-B-结束。令他惊讶的是，他发现他的时间是2000100+2001年100=40.01分钟，节省了将近25分钟。很快，4000名司机中的更多人正在尝试这条新路线。所用时间从40.01上升并不断攀升。当尝试新路线的司机人数达到2500人时，仍有1500人在Start-B-End路线上，他们的时间将是2500100+4000100=65分钟，这与原始路线相比没有任何改进。与此同时，这1500名司机已被放慢45+4000100=85分钟，增加了20分钟。他们也必须通过A切换到新路线，所以现在需要4000100+4000100=80分钟。没有人有动力去A-End或Start-B，因为任何尝试它们的司机都需要85分钟。因此，交叉路的开通引发了每个人对它的不可逆转的改变，每个人都花费了80分钟，而不是原来的65分钟。如果每个司机都同意不使用A-B路径，或者如果这条路关闭，每个司机将受益于旅行时间减少15分钟。
　　平衡的存在
　　如果假设每个人在边缘行驶的旅行时间相等，那麽平衡将始终存在。
　　让大号e(X)是每个人沿边缘旅行的旅行时间的公式e什麽时候X人们佔据了优势。假设有一个流量图Xe沿边缘行驶的人e.让能量e,E(e)，是
　　∑i=1XeLe(i)=Le(1)+Le(2)+⋯+Le(Xe)
　　（如果Xe=0让B(e)=0）。让交通图的总能量为图中每条边的能量之和。
　　选择使总能量最小化的路线。这样的选择必须存在，因为路线的选择是有限的。那将是一个平衡。
　　假设，由于矛盾，情况并非如此。然后，至少有一名司机可以切换路线，提高行程时间。假设原来的路线是e0,e1,…,en而新路线是e0',e1',…,em'.让E是交通图的总能量，并考虑路线时会发生什麽e0,e1,...en已移除。每条边的能量ei将减少Lei(Xei)所以E将减少∑i=0nLei(Xei).这只是採取原始路线所需的总行程时间。如果随后添加了新路线，e0',e1',…,em',总能量E将增加走新路线所需的总行程时间。因为新路线比原路线短，E必须相对于原始配置减少，这与原始路线集最小化总能量的假设相矛盾。
　　因此，最小化总能量的路线的选择是一种平衡。
　　寻找平衡
　　上述证明概述了一个称为最佳响应动态的过程，该过程为线**通图找到平衡并在有限数量的步骤中终止。该算法被称为“最佳响应”，因为在算法的每一步，如果图形不处于平衡状态，则某些驱动程序对所有其他驱动程序的策略具有最佳响应并切换到该响应。
　　最佳响应动态的伪代码：
　　让P是一些流量模式。
　　当P不平衡时：计算P中每个驱动程序d的P
　　的势能e：
　　对于d可用的每个备用路径p：
　　如果n<e，则计算d走路径p时模式
　　的势能n：
　　修改P使d走路径p
　　继续最上面，而
　　在每一步，如果某个特定的驱动程序可以通过採用替代路径（“最佳响应”）做得更好，那麽这样做会严格降低图的能量。如果没有驱动程序具有最佳响应，则图表处于平衡状态。由于图的能量随着每一步而严格减少，因此最佳响应动力学算法最终必须停止。
　　交通平衡离最优还有多远？
　　如果旅行时间函数是线性的，即Le(X)=AeX+be对于一些一个e,be≥0，那麽在最坏的情况下，能量最小化均衡中的交通是社会最优的两倍。
　　证明：让Z是一些流量配置，具有相关的能量B(Z)和总旅行时间T(Z).对于每条边，能量是等差数列的总和，使用等差数列总和的公式可以证明B(Z)≤T(Z)≤2B(Z).如果Zo是社会最优交通流Ze是能量最小化的交通流，不等式意味着T(Ze)≤2B(Ze)≤2B(Zo)≤2T(Zo).
　　因此，能量最小化平衡的总行程时间最多是最佳流动的两倍。
　　Braess悖论的动力学分析
　　2013年，DalForno和Merlone将Braess悖论解释为动态三元选择问题。分析显示新路径如何改变问题。在新路径可用之前，动态与具有外部性的二元选择相同，但新路径将其转换为三元选择问题。添加额外资源丰富了动态的複杂性。事实上，循环甚至可以并存，悖论对动力学的影响可以从几何和分析的角度来看。
　　棋盘悖论
　　棋盘悖论或Loyd和Schlömilch的悖论是基于视错觉的虚假悖论。将一个边长为8个单位的棋盘或正方形切成四块。这四块用于形成一个边长为13和5个单位的矩形。因此，所有四块的总面积是正方形中的64个区域单位，而矩形中的65个区域单位，这看似矛盾是由于视觉错觉，因为四块不完全适合矩形，但留下了一个几乎看不到的小块矩形对角线周围的间隙。这个悖论有时归因于美国拼图发明家山姆·洛伊德（SamLoyd，1841-1911）和德国数学家奥斯卡·施洛米尔奇(1832–1901)
　　分析
　　仔细观察后，可以看到这四个部分并不完全吻合，但在矩形的对角线周围留下了一个几乎看不到的小间隙。这个差距DEBF具有平行四边形的形状，可以通过显示对角大小相等来检查。
　　∠FDB=90∘−∠FDG−∠EDI=90∘−arctan⁡(|EI||DI|)−arctan⁡(|FG||DG|)=90∘−arctan⁡(52)−arctan⁡(38)=90∘−arctan⁡(|FJ||BJ|)−arctan⁡(|EH||BH|)=90∘−∠FBJ−∠EBH=∠FBE≈1.24536∘
　　∠DEB=360∘−∠DEI−∠IEH−∠EBH=360∘−arctan⁡(|DI||EI|)−90∘−arctan⁡(|DG||FG|)=360∘−arctan⁡(25)−90∘−arctan⁡(83)=360∘−arctan⁡(|BJ||FJ|)−90∘−arctan⁡(|BH||EH|)=360∘−∠BFJ−∠JFG−∠GFD=∠DFB≈178.75464∘
　　沿着矩形的四个部分的精确拟合需要平行四边形折叠成线段，这意味着它需要具有以下尺寸：
　　∠FBE=∠FDE=0∘
　　∠DFB=∠DEB=180∘
　　由于实际角度仅与这些值稍有偏差，因此会产生平行四边形只是一条线段的视觉错觉，并且各部分完全吻合。或者，可以通过将反应角放置在坐标系中并比较边的斜率或矢量表示来验证平行度。
　　平行四边形的边长和对角线分别为：
　　|DE|=|FB|=22+52=29
　　|DF|=|EB|=32+82=73
　　|BF|=12+32=10
　　|DB|=52+132=194
　　使用赫伦公式可以计算出平行四边形一半的面积（△DFG）。减半的周长是
　　s=|BF|+|DB|+|DF|2=10+29+732
　　得到整个平行四边形的面积：
　　F=2⋅s⋅(s−|EF|)⋅(s−|DE|)⋅(s−|DF|)=2⋅14⋅(10+29+73)⋅(−10+29+73)⋅(10−29+73)⋅(10+29−73)=2⋅14⋅2=1
　　所以间隙的面积正好佔矩形的附加面积。
　　概括
　　最后几章的绘图中出现的线段的长度为2、3、5、8和13。这些都是连续的斐波那契数，暗示了基于斐波那契数的解剖方案的推广。斐波那契数的属性也提供了一些更深入的见解，为什麽视错觉如此有效。边长为斐波那契数的正方形Fn可以使用长度的线段进行剖析Fn,Fn-1,Fn-2以同样的方式使用长度为8、5、3的线段剖析棋盘（见图）。
　　卡西尼号的身份：
　　Fn+1⋅Fn-1-Fn2=(-1)n
　　从中可以立即清楚地看出，正方形和矩形之间的面积差必须始终为1个面积单位，特别是对于原始的棋盘悖论：
　　13⋅5-82=F7⋅F5-F62=(-1)6=1
　　注意比不均匀的索引n正方形的面积不是小一个面积单位而是更大。在这种情况下，四个部分在组装成矩形时不会产生小间隙，而是稍微重叠。由于面积的差异始终为1个面积单位，因此可以使用较大的斐波那契数来改善视错觉，从而使矩形区域的间隙百分比变得任意小，因此实际上是不可见的。
　　由于相邻斐波那契数的比率相对于黄金比率收敛得相当快φ，以下比率也快速收敛：
　　FnFn-2=FnFn-1⋅Fn-1Fn-2→φ2,Fn-2Fn=Fn-2Fn-1⋅Fn-1Fn→φ-2
　　为了使正方形的四个切口精确地组合在一起形成一个矩形，小平行四边形DEBF需要折叠成一条线段，作为矩形的对角线。在这种情况下，由于是对应的平行角，以下适用于矩形中的角度：
　　∠IDB=∠HEB,∠D乙我=∠EBH,∠FDG=∠BFJ,∠GFD=∠JBF
　　因此，以下直角三角形△IED,△HBE,△DFG和△FBJ必须相似，并且它们的腿的比例必须相同。
　　由于上述快速收敛，组装矩形中斐波那契数的相应比率几乎相同：
　　FnFn-2≈Fn-1Fn-3,Fn-2Fn≈Fn-3Fn-1
　　因此它们几乎完全吻合，这会产生视错觉。
　　还可以像在原始棋盘分析中一样查看平行四边形的角度。对于这些角度，可以得出以下公式：
　　n≥4:∠FBE=∠FDE=arctan⁡(1f2n−3+2fn−3fn−2)→0∘
　　n≥4：∠DFB=∠DEB=180∘-反正切⁡(1F2n-3+2Fn-3Fn-2)→180∘
　　因此，角度快速收敛到精确拟合所需的值。
　　然而，可以在不产生面积不匹配的情况下使用解剖方案，即四个切口将完全组装成一个与正方形面积相同的矩形。不是使用斐波那契数，而是直接根据黄金比例本身进行剖析（见图）。对于边长的正方形a这产生了矩形的面积
　　(φ-1)a⋅(φa)=(φ2-φ)a2=a2,
　　自从φ2-φ=1是黄金比例的属性。
　　历史
　　胡珀悖论可以看作是国际象棋悖论的先驱。在其中，您将相同的四块图形组装成一个矩形，但是四块起源的剖切形状不是正方形，也不是基于斐波那契数的所涉及的线段。胡珀在他的着作RationalRecreations中以几何货币的名义发表了现在以他的名字命名的悖论。然而，我不是他的发明，因为他的书本质上是EdméGillesGuyot（1706-1786年）于1769年在法国出版的Nouvellesrécréationsphysiquesetmathétiques的翻译。
　　实际国际象棋悖论的第一个已知出版物归功于德国数学家奥斯卡·施洛米尔奇。他于1868年在德国科学杂誌ZeitschriftfürMathematikundPhysik上以EingeometrischesParadoxon（“几何悖论”）为题发表了该论文。在同一期刊上，VictorSchlegel于1879年发表了文章VerallgemeinerungeinesgeometrischenParadoxons（“几何悖论的概括”），其中他概括了构造并指出了与斐波那契数的联繫。棋盘悖论也是英国数学家和作家刘易斯卡罗尔的最爱，他也致力于泛化，但没有发表。这后来在他死后的笔记中被发现。美国拼图发明家山姆·洛伊德声称在1858年的世界国际象棋大会上提出了棋盘悖论，后来它被包含在山姆·洛伊德的5,000个拼图、技巧和难题的百科全书（1914年）中，由他的儿子死后出版。姓名。儿子说，将这四个部分组合成一个63个区域单位的图形（见上图）是他的想法。然而，它已于1901年发表在沃尔特·德克斯特(WalterDexter)的文章一些明信片谜题中。
　　系统U
　　在数学逻辑中，SystemU和SystemU-是纯类型系统，即具有任意数量的排序、公理和规则（或排序之间的依赖关係）的类型化lambda演算的特殊形式。Jean-YvesGirard在1972年证明了它们都不一致。这一结果导致人们认识到Martin-Löf最初的1971年类型理论是不一致的，因为它允许Girard悖论利用的相同“类型中的类型”行为。
　　正式定义
　　SystemU被定义为作为纯类型系统
　　三种_{*,◻,△};
　　两个公理{*：◻,◻：△};和
　　五个规则{(*,*),(◻,*),(◻,◻),(△,*),(△,◻)}.
　　SystemU-定义相同，除了(△,*)规则。
　　种类*和◻通常分别称为“类型”和“种类”；排序△没有特定的名称。这两个公理描述了种类中类型的包含（*：◻)和种类△(◻：△）。直观地说，这些类别描述了术语性质的层次结构。
　　所有值都有一个类型，例如基本类型（例如b：Bool读作“b是布尔值”）或（依赖）函数类型（例如F：ñAT→Bool读作“f是从自然数到布尔值的函数”）。
　　*是所有此类类型中的一种（T：*读作“t是一种类型”）。从*我们可以构建更多的术语，例如*→*这是一种一元类型级别的运算符（例如LisT：*→*读作“List是从类型到类型的函数”，即多态类型）。这些规则限制了我们如何形成新的种类。
　　◻是所有这些类型中的那种（ķ：◻读作“k是一种”）。同样，我们可以根据规则允许构建相关术语。
　　△是所有此类术语的类型。
　　规则管理排序之间的依赖关係：(*,*)表示值可能取决于值（函数），(◻,*)允许值依赖于类型（多态性），(◻,◻)允许类型依赖于类型（类型运算符）等等。
　　吉拉德悖论
　　SystemU和U-的定义允许将多态类型分配给泛型构造函数，类似于经典多态lambda演算中术语的多态类型，例如SystemF。这种泛型构造函数的示例可能是（其中k表示种类变量）
　　λķ◻λαķ→ķλβķ.α(αβ)：Πķ：◻((ķ→ķ)→ķ→ķ).
　　这种机制足以构造一个类型为(∀p：*,p)（相当于类型⊥)，这意味着每种类型都有人居住。通过Curry-Howard对应，这相当于所有逻辑命题都是可证明的，这使得系统不一致。
　　吉拉德悖论是集合论中罗素悖论的类型论类似物。