Competitive mediator games and urban CAV routing markets

Competitive mediator games and urban CAV routing markets

Grzegorz Jamróz

Abstract

Inspired by possible future markets of autonomous routing and driving (ARAD), we introduce competitive mediator games and their equilibria which generalize the (coarse) correlated equilibria, which have become a popular research area recently as they not only can be more socially efficient than Nash equilibria but also are limits of algorithmic no-regret multiagent learning dynamics. We discuss the basic properties of competitive mediator games and prove that in the generic setting of anonymous congestion(routing) games with market-share maximizing mediators all competitive mediator equilibria are monopolies whenever one of the mediators is weakly preferred to other mediators by all users. We apply and interpret these results in the context of new markets of competing ARAD service providers. We also provide a comprehensive overview of these markets and discuss the future mechanism design thereof.

Keywords: competitive mediator game, competitive mediated equilibrium, non-atomic games, autonomous driving, CAV-human interaction, collective routing

Summary

This paper introduces a general game-theoretical framework for mediated markets with several service providers whose objective is more complex than pure pricing and shows, on the example of mediated future markets of competing ARAD providers, how it can be used to derive informative conclusions.

The paper is motivated by the future markets of autonomous routing and driving (ARAD), where multiple service providers compete for customers offering ARAD services while leveraging collective routing to improve operations. The paper discusses various forms CAV routing markets could assume in the future, differing with respect to vehicle ownership and freedom of routing decisions. The authors choose Mature market II as the default option, characterized by familiar traffic driving patterns which results from AVs behaving and looking similarly to human driven vehicles in traffic (yet not necessarily in route choice).

The paper formalizes the notion of competitive mediator games in both the finite-user and continuum of users setting. In both cases the notions of user equilibrium and competitive mediator equilibrium are discussed. The paper proves that under mild assumptions the user equilibria exist. The competitive mediator equilibria, on the other hand, may not exist unless the user equilibrium is unique.

Specializing to discounted share-maximizing routing games, the paper proves that the competitive mediator equilibria are monopolies, whenever one of the mediators is weakly preferred by all the users, and strongly preferred by some of the users. The main result is Theorem 7.17, which states:

"Consider a discounted share-maximizing independent routing game (N = [0, 1], F = 1, 2, Ai, ufi, U f) with mediator 1 strictly dominant. Suppose that there are two alternatives, i.e. action sets are Ai = 1, 2 and that ufi = γif t(qai) for a strictly increasing continuous delay function t. Then, there exists a dominant strategy (routing) R1 such that, for every routing R2 of mediator 2, the induced user equlibrium consists in all users selecting mediator 1, i.e. χ = µF ⊗ δ1, where µF represents the distribution of discount factors (γ 1, γ 2). Consequently ((R1, R2)), µF ⊗ δ1) is a competitive mediator equilibrium (CME) for any R2, and there is no R2 such that ((R1, R2), χ) is a CME, when χ ̸= µF ⊗ δ1."

The paper concludes that if the market were to equilibrate, the equilibrium would take the form of a monopoly. Nevertheless, this monopoly seems not to be particularly detrimental as the competing mediators are incentivised to raise the quality of their service, which would break the monopoly.

The main conclusion is: "In the possible future CAV routing markets designed such that competitive mediators are incentivised to maximize market share, a slight advantage of one of the mediators in terms of quality may bring about monopoly if no further regulations are introduced."

The paper also discusses the relation of the setting to the future markets of collective routing of CAVs and argues for the viability of this form of the market. It advocates for a fee-free market, where revenue for mediators is proportional to market share, not claiming however that this mechanism design is optimal. Partial regulation of this market via augmentation of the objective of mediators with social-welfare term, in order to avoid monopolies, was proposed in [28], however in realistic designs it would need to be revisited and tested in real traffic situtions.

The paper leaves open several directions for future research, including:

• Further research on which autonomous routing and driving market form would be the most beneficial to society and which mechanism design should be put in place in order to avoid the errors from other markets.

• Discussion of the Competitive Mediator Equilibria/Market Dynamics in settings when the preferences of users are more diverse and not strongly skewed towards one mediator.

• Extension of the monopoly results to settings with viable independent driving (HDV).

• Extension of the results to settings with more complex road networks and delay functions, perhaps from microscopic simulation.

• Discussion of the competition in out of equilibrium settings, e.g. varying in time strategies of mediators, based e.g. on multiagent reinforcement learning (MARL).

• Inclusion of elastic discount factors or more complex functional form of utility of users.

• Behavioural modelling of human choices in the introduced setting, including action/mediator choices and the evolution of discount factors or generalization thereof. Experimental validation of the models.

• Convergence of the dynamics of the competition to monopoly equilibria in practical settings under application of the developed model of human behaviour.

• Considering setting with recommendation patterns which are not independent but mediators either partially collude or condition their recommendations on the predicted behaviour of other mediators.

• Considering settings without complete information, i.e. on the one hand of users being supplied e.g. only the expected travel times a mediator can hope to provide, compare [28] and not the full details of the offered routing (incomplete user information) and limited information on the mediator preferences of users (incomplete mediator information).

Based on the paper, here are specific improvements to AI systems and what the improved systems can do:

1. Multi-agent routing coordination with mediator-aware equilibrium prediction

• Improvement: Integrate the competitive mediator game framework into AI routing systems (e.g., fleet management or ride-hailing algorithms) to model multiple service providers simultaneously optimizing for market share, not just user cost.

• What it can do: Predict when a slight quality advantage leads to monopoly (per Theorem 7.17) and proactively adjust routing strategies to avoid market collapse, or simulate regulatory interventions (e.g., adding social-welfare terms) to test their impact before deployment.

2. No-regret learning for mediated markets

• Improvement: Extend existing no-regret multiagent learning algorithms to incorporate mediator-level objectives (market share) and user equilibrium constraints, using the paper’s definition of competitive mediator equilibria as a convergence target.

• What it can do: Train AI agents (mediators) to learn stable routing policies in dynamic urban environments, even when user preferences are heterogeneous, and detect when learning dynamics fail to converge to a unique equilibrium—enabling early warnings for market instability.

3. Mechanism design for CAV routing markets

• Improvement: Use the paper’s framework to build AI-based mechanism design tools that simulate fee-free, market-share-driven markets and test alternative reward structures (e.g., adding social welfare terms) to prevent monopolies.

• What it can do: Automatically generate and evaluate regulatory policies for future autonomous vehicle markets, balancing efficiency, equity, and competition, before real-world implementation.

4. User behavior modeling with discount factors

• Improvement: Incorporate the paper’s model of user preferences (discount factors γ) into AI systems that predict human choices between competing routing services, including evolution of preferences over time.

• What it can do: Build more accurate demand forecasting for mobility-as-a-service platforms, enabling personalized routing recommendations that account for heterogeneous user sensitivity to quality differences, and simulate long-term market dynamics under changing user preferences.

5. Robust equilibrium computation under non-uniqueness

• Improvement: Develop algorithms that handle cases where competitive mediator equilibria may not exist (as noted when user equilibrium is non-unique), using the paper’s existence conditions to guide solver design.

• What it can do: Provide AI systems with fallback strategies (e.g., approximate equilibria or bounded rationality) when deployed in real-world traffic where multiple user equilibria are possible, ensuring stable operation despite theoretical non-existence.

6. Simulation of out-of-equilibrium competition

• Improvement: Extend the static equilibrium analysis to dynamic, time-varying mediator strategies using multiagent reinforcement learning, as suggested in the paper’s future work.

• What it can do: Enable AI systems to simulate and optimize competitive routing markets over time, capturing transient behaviors (e.g., price wars or quality races) that static equilibria miss, and inform real-time strategic decisions for service providers.

7. Incomplete information handling

• Improvement: Adapt the framework to settings where users only see expected travel times (not full routing details) and mediators have limited information on user preferences, as the paper lists as open directions.

• What it can do: Build AI systems that operate under realistic information asymmetry—e.g., a routing service that only publishes aggregate performance metrics—and still make robust decisions using Bayesian or robust optimization techniques, improving trust and adoption in opaque market conditions.

Inspired by possible future markets of autonomous routing and driving (ARAD), we introduce competitive mediator games and their equilibria which generalize the (coarse) correlated equilibria, which have become a popular research area recently as they not only can be more socially efficient than Nash equilibria but also are limits of algorithmic no-regret multi-agent learning dynamics. We discuss the basic properties of competitive mediator games and prove that in the generic setting of anonymous congestion(routing) games with market-share maximizing mediators all competitive mediator equilibria are monopolies whenever one of the mediators is weakly preferred to other mediators by all users. We apply and interpret these results in the context of new markets of competing ARAD service providers. We also provide a comprehensive overview of these markets and discuss the future mechanism design thereof.