Allocation problem for the platform of platforms

Another joint work with Ruijie Li, built on our previous research of ridesharing, including A-PASS and Pricing carpool.

In this study, we consider a general problem called the Allocation Problem for the Platform of Platforms – dubbed AP3.  Such a problem might arise  in a two-sided service market, where a third-party integrator tries to allocate customers to workers separately controlled by a set of online platforms in a manner that satisfies all stakeholders.   The integrator, as a leader, influences the outcome of the game by pricing the service, whereas the platforms (followers) are given the freedom to accept or reject customers to maximize their own profit, given the prices set by the integrator (see the plot below for an illustration).  A set of nonlinear constraints are imposed on the leader’s problem to eliminate artificial scarcity, orignated from the integrator’s monopoly power.  We formulate AP3 as a Stackelberg bipartite matching problem, which is known to be NP-hard in general.  Our main result concerns the proof that AP3 can be reduced to a polynomially solvable problem by taking advantage of, somewhat paradoxically, the hard requirement of ruling out artificial scarcity.

A preprint can be downloaded here.


Abstract: We study the Allocation Problem for the Platform of Platforms (abbreviated as AP3) in a two-sided service market, where a third-party integrator tries to allocate customers to workers separately controlled by a set of online platforms in a manner that satisfies all stakeholders. AP3 is a natural Stackelberg game. The integrator, as a leader, influences the outcome of the game by pricing the service, whereas the platforms (followers) are given the freedom to accept or reject customers to maximize their own profit, given the prices set by the integrator. A set of nonlinear constraints are imposed on the leader’s problem to eliminate artificial scarcity, derived from the integrator’s monopoly power. We formulate AP3 as a Stackelberg bipartite matching problem, which is known to be NP-hard in general. Our main result concerns the proof that AP3 can be reduced to a polynomially solvable problem by taking advantage of, somewhat paradoxically, the “hard” requirement of ruling out artificial scarcity. Numerical experiments are conducted using the ride-hail service market as a case study. We find artificial scarcity negatively affects the number of customers served, although the magnitude of the effect varies with market conditions. In most cases, the integrator takes the lion’s share of the profit, but the need to eliminate artificial scarcity sometimes forces them to concede the benefits of collaboration to the platforms. The tighter the supply relative to the demand, the more the platforms benefit from removing artificial scarcity. In an over-supplied market, however, the integrator has a consistent and overwhelming advantage bestowed by its monopoly position.

Differentiable bilevel programming

A Stackelberg congestion game (SCG) is a bilevel program in which a leader aims to maximize their own gain by anticipating and manipulating the equilibrium state at which followers settle by playing a congestion game. Large-scale SCGs are well known for their intractability and complexity.   In this study,  we attempt to marry the latest developments in machine learning with traditional methodologies — notably bilevel optimization and game theory — to forge an integrative approach based on differentiable programming.  Among other advantages,  the approach enables us to treat the equilibration of a congestion game as a deep neural network (see below), so that a suite of computational tools, notably automatic differentiation, can be easily applied.  You may download a preprint here.


Abstract: A Stackelberg congestion game (SCG) is a bilevel program in which a leader aims to maximize their own gain by anticipating and manipulating the equilibrium state at which followers settle by playing a congestion game. Large-scale SCGs are well known for their intractability and complexity. This study approaches SCGs through differentiable programming, which marries the latest developments in machine learning with conventional methodologies. The core idea centers on representing the lower-level equilibrium problem using an evolution path formed by the imitative logit dynamics. It enables the use of automatic differentiation over the evolution path towards equilibrium, leading to a double-loop gradient descent algorithm. We further show the fixation on the lower-level equilibrium may be a self-imposed computational obstacle. Instead, the leader may only look ahead along the followers’ evolution path for a few steps, while updating their decisions in sync with the followers through a co-evolution process. The revelation gives rise to a single-loop algorithm that is more efficient in terms of both memory consumption and computation time. Through numerical experiments that cover a wide range of benchmark problems, we find the single-loop algorithm consistently strikes a good balance between solution quality and efficiency, outperforming not only the standard double-loop implementation but also other methods from the literature. Importantly, our results highlight both the wastefulness of “full anticipation” and the peril of “zero anticipation”. If a quick-and-dirty heuristic is needed for solving a really large SCG, the proposed single-loop algorithm with a one-step look-ahead makes an ideal candidate.

国史大纲+万古江河

钱穆的《国史大纲》和许倬云的《万古江河》都是架构宏大的中国通史,两本书覆盖范围差不多,均为上古至民国:国史大纲止于抗战时期,而万古江河以49年作结;风格也类似,都从重构历史出发,探究中华文明特质及精神,解释兴衰变迁,在当今世界中为其定位。就像钱穆说的,“治国史之第一任务,在能于国家民族之内部自身,求得其独特精神之所在。”

两位史家秉持的中华史观相差不可道里计。钱穆是传统视角,以中原地理坐标为枢轴,以中国传统文化为经纬来编制历史,尚未脱天下四方的二元理念。比如他解释中国文化演进的独特性时写道,“中国政制常偏重于中央之凝合,而不重于四围之吞并。其精神亦常偏于和平,而不重于富强;常偏于已有之完整,而略于未有之侵获;对外则曰’昭文德以来之’,对内则曰’不患寡而患不均’”。字里行间充满了对天朝文化感召力的自信,虽然没写圣人出而天下归心,四海定而万国宾服,但意思差相仿佛。 大概因为成书在抗战时期,《国史大纲》民族情结强烈,夷夏之防溢于言表,这一点从他扬明抑清的倾向中表露无疑。比如他说,“明清之际的转变,大部分是明代内部自身的政治问题,说不上民族的衰老”;又说,“中国则因有二百年来满洲部族政权之横梗作病,使之虽欲急起直追而不可得”,恨不得要把中国近代落后的总账一股脑都算在满清这个异族征服者的头上。相比之下,许倬云学贯中西,视野要开阔许多,坚持把中国放在世界地理坐标中来定位,把中国作为东亚文明圈农耕文明的翘楚,但也把北方草原文明—从秦汉的匈奴,到南北朝的五胡,再到辽金元满,乃至西夏吐蕃—放在跟它平等的地位上来描述。《万古江河》从上古中华文明圈的形成发展,到中古时代东亚文明圈内部的重整融合,再到近古时代东亚文明圈跟其他文明圈的交流冲突,最后落到全球化的愿景,鼓吹“真正天下为公的大同境界”,虽然略嫌一厢情愿 (尤其放到出版后十六年的今天,更似乎与浩浩汤汤的反全球化浪潮格格不入),但脉络清晰,逻辑自然,跟我从小读的历史教课书比,至少是一个更客观真实的角度,如果说以史为镜,那《万古江河》应该是想要反躬自省的人更需要的那面镜子。

思想上,许倬云是比较典型的进步派(progressives),他认为中华文明源远流长,胜在兼容并蓄的普世胸怀,以仁为本的儒家理念,和推己及人的人文精神。他号召全体人类自觉合作,以市场经济和“国族范围的民主政治”为基础,纳入中国儒家理念,印度众生平等思想,以及伊斯兰对自然的尊重, 完成“人类文明另一次的重大突破”。愿景虽然鼓舞人心,但未免有理想主义过头的危险。 而钱穆无疑是保守派(conservatives)。他支持中学为体、西学为用的大方向,认为中国近代落后,除了“满洲部族横梗做病”之外,更受鸦片战争以来无间断革命之害,以至于社会动荡,民不聊生,”欧洲之科学舆机械,遂终无在中国社会保养,徐徐生长成熟之机会。”,而中国社会之所以落后,“只在科学机械方面之落后。” 钱老在民族存亡之秋撰史,又处于新旧文化交战的时代,其局限性所在难免,有“咱们无非是差在科学机械”这种本末倒置的观点,无可厚非。但到了五代之下的今天如果还抱着它不放,则非因循守旧、抱残守缺八字可以解释了。

从阅读体验来说,我觉得两本书都比较枯燥,《国史大纲》因为半文半白,更兼体例关系,正文精炼扼要而辅以大量正史原文,对我这种半吊子文言文水平的人更是煎熬。《万古江河》颇多新鲜史料(尤以在商业、工业、科学、普通人生活方面),角度也新颖有趣(比如论南北宋在东亚格局中的地位,评满清对中国现代幅员做出的巨大贡献),可惜文字平实严谨有余,而风韵魅力稍逊,也算美中不足吧。

A failure of capitalism

Richard Posner is said to be the most cited legal scholar of the twentieth century.  A Failure of Capitalism, a book published toward the end of his distinguished career, is not among the most cited of his scholarly works – not even close – but probably the most read, judged by the number of ratings on Goodreads.  “The failure” of capitalism concerned herein is the financial crisis of 2008, which triggered the Great Recession, the worst recession the world had ever seen since the legendary depression of 1929.  The book attempts to explain the causes of that crisis, who should bear the blames and what lessons we may collectively draw from the event.

Posner believes the main cause of Great Recession is the confluence of lower interest rates in 2000s and the over-deregulation of financial industry that began much earlier.  On the one hand, cheap credit encouraged the expansion of homeownership, which pushed up home price because the supply in real estate market is usually slow to catch up with demand.  Rising price convinced people that houses are good investment, thereby inducing more to dive in with money borrowed beyond their means to pay back unless home price continued to rise.  On the other hand, deregulation made it harder for traditional commercial banks to raise equity capital from demand deposit accounts, owing to the competition from investment banks and hedge funds alike. To stay in the game, therefore, banks had to rely more on borrowed short-term credit, increase their leverage (the ratio of debt to equity) and make longer term (hence riskier) loans. With the huge demand for credit fueled by the low interests of 2000s, this business model was pushed to the limit, exposing the entire industry to the risk of default in the housing market should the price begin to fall.  To mitigate these risks, banks invented complex debt securitization devices, including the infamous credit-default swaps.   In hindsight, however, these tools were not so much about reducing the risks as hiding them, unconsciously or otherwise.

Given this analysis, it is hardly surprising Posner argues the leaders at Federal Reserve and other economic agencies – Alan Greenspan and, to lesser extent, Ben Bernanke, among others – are culpable for a misconceived monetary policy and the lack of foresight for the impending crisis.  He also points fingers at the US government for its deregulation of the financial industry – driven largely by market fundamentalism – and the failure to prepare a contingence plan that would have avoided the “bumbling improvisations” in the initial response.   Posner is also dismayed at the “failure of the economics profession to have grasped the dangers”.  Many, including Robert Lucas – the most distinguished macroeconomist at the time – seemed to have been completely blindsided by the disaster.    Lucas had gone so far as to downplay the imminence of a recession as late as September 19, 2008, four days after the collapse of Lehman Brothers.     However, Posner argues his fellow academics deserve lenience for missing the warning signs that they were supposedly best poised to spot.  For one thing, they were not well equipped to “empirically test rival theories of depression” and were increasingly isolated in their own silos by ever-greater specialization. More importantly, doomsaying is a tricky and unpopular craft. As Posner points out, “Cassandras rarely receive a fair hearing”, because “it is very difficult to receive praise, and indeed to avoid criticism, for preventing a bad thing from happening unless the probability of its happening is known”.

Posner pushes back forcefully against the claim that the crisis had much to do with the stupidity or greed of bank executives and hedge fund managers.  Nor does he believe they should be held responsible for not heeding the warning signs of a gigantic bubble while taking seemingly undue risks to “ride it”.     “Riding a bubble can be rational”, Posner explains, especially when money is cheap.  More importantly, nobody really knows when a bubble, unattainably large as it might seem, will burst, and until it does one could still be making much money riding it than climbing off.   Indeed, being rational could be a losing proposition when the majority is irrational, as summarized in Keynes’ famous aphorism,

“the market can stay irrational longer than you can stay solvent”.

Posner believes the duty of mitigating systematic risks resides elsewhere (i.e., government), because

“it would make no more sense for an individual businessman to worry that because of the instability of the banking industry his decisions and those of his competitors might trigger a depression than for a lion to spare a zebra out of concern that lions are eating zebras faster than the zebras can reproduce.”

Posner writes beautifully, with a combination of clarity, precision, and elegance that few authors could match.  If one wants to learn how to explain complex concepts to a layman in an accessible but still sophisticated manner, the book will make a great tutorial. I don’t know enough about macroeconomics or finance to comment on many an opinion expressed in the book.   Truth told, the book taught me a lot about those subjects – the difference between equity and security being a memorable example. However, I do question the wisdom of writing a book about an event that had not even run its course at the writing (early 2009).   If Posner had waited a few more years, perhaps he would not insist to label the crisis as a “depression”.  He might also reconsider his derision of Feds’ low-interest policy because that policy, in a much more aggressive form, had not only survived Great Recession, but also thrived for more than a decade since.

How many are too many?

If you had visited  big Chinese cities between 2016 and 2019, you might have noticed many sidewalks  rendered completely unwalkable by a myriad of shared bikes.  Thrown out there by well-meaning entrepreneurs and ambitious investors who funded their operations, the sight of these bikes clogging public space epitomizes the feverish quest for growth that has become the hallmark of the Chinese Model.  My sense was that most shared bike operators had no idea — or did not care —  how many bikes they need to serve a given city well and at what price they should charge the users in order to cover the operating cost, including the cost of routinely moving the bikes around to meet the demand.    However, as a transportation modeler and analyst, I  found these questions fascinating, and this paper was precisely the result of my attempt to answer them.

You can read the abstract below and a preprint can be downloaded here.


How Many Are Too Many? Analyzing Dockless Bikesharing Systems with a Parsimonious Model

Using a parsimonious model, this paper analyzes a dockless bikesharing (DLB) service that competes with walking and a generic motorized mode. The DLB operator chooses a fleet size and a fare schedule that dictate the level of service (LOS), as measured by the access time, or the walking time taken to reach the nearest bike location. The market equilibrium is formulated as a solution to a nonlinear equation system, over which three counterfactual design problems are defined to maximize (i) profit; (ii) ridership; or (iii) social welfare. The model is calibrated with empirical data collected in Chengdu, China and all three counterfactual designs are tested against the status quo. We show the LOS of a DLB system is subject to rapidly diminishing returns to the investment on the fleet. Thus, under the monopoly setting considered herein, the current fleet cap set by Chengdu can be cut by up to three quarters, even when the DLB operator aims to maximize social welfare. This indicates the city’s fleet cap decision might have been misguided by the prevailing conditions of a competitive yet highly inefficient market. For a regulator seeking to influence the DLB operator for social good, the choice of policy instruments depends on the operator’s objective. When the operator focuses on profit, limiting fare is much more effective than limiting fleet size. If, instead, they aim to grow their market share, then setting a limit on fleet size becomes a dominant strategy. We also show, both analytically and numerically, the ability to achieve a stable LOS with a low rebalancing frequency is critical to profitability. A lower rebalancing frequency always rewards users with cheaper fares and better LOS, even for a profit-maximizing operator.