EF45 – Multi-Agent Social Systems

Project

EF5-6

Evolution Models for Historical Networks

Project Heads

Benjamin Ducke (DAI), Max Klimm (TU), Guillaume Sagnol (TU)

Project Members

Maximilian Stahlberg (TU)

Project Duration

01.04.2021 − 31.03.2024

Located at

TU Berlin

Description

Our knowledge of prehistoric and ancient road networks is fragmentary: Contemporary maps are rarely available and far from modern standards of precision. Some roads may be textually referenced and some are found to be still in use today while the remains of others can only be spotted from the air or sparsely sampled via ground-penetrating radar or excavation. Modern maps of ancient networks thus emerge as a conglomeration of data from many sources.

To predict missing links in incomplete networks and to better understand the principles that drive the evolution of ancient road networks, we develop and study domain-specific mathematical models.

A sequential model of network formation

We propose a novel model based on three simplifying assumptions concerning the growth of ancient road networks:

Modeling assumptions

  1. Roads are added in sequence as their construction is fast compared to the lifespan of a network.
  2. Traveling through the wilderness is prohibitively difficult, so the road network will eventually contain adequate connections between all pairs of significant settlements.
  3. The course of connections optimizes a trade-off between road construction and travel costs.

Our model assumes a maximal network G = (V, E) of possible road segments equipped with a terrain cost c, and a set of connections K to establish, normally given as all unordered pairs over a set of settlements S ⊆ V. If these connections are brought into an order π ∈ S(K), then a subgraph of G emerges from the following procedure, parameterized by α ∈ [0, 1]:

Network formation

  1. Initialize the set of roads R = Ø.
  2. For every connection {u, v} = πᵢ in order of π:
    1. Find a least-cost u-v-path P ⊆ E in G according to edge costs c.
    2. For every edge e ∈ P with e ∉ R:
      1. Reduce the edge’s cost to c(e) = α⋅c(e).
      2. Update R = R ∪ {e}.
  3. Return the road network G[R].

Project Webpages

Selected Publications

  1. M. J. Stahlberg, G. Sagnol, B. Ducke, and M. Klimm.
    Spatiotemporal reconstruction of ancient road networks through sequential cost–benefit analysis.

    PNAS Nexus
    2(2), 2023.
  2. M. Klimm and M. J. Stahlberg.
    Complexity of equilibria in binary public goods games on undirected graphs.
    Proceedings of the 24th ACM Conference on Economics and Computation (EC), 2023.
  3. J. Cembrano, S. M. Griesbach, and M. J. Stahlberg.
    Deterministic impartial selection with weights.
    ACM Transactions on Economics and Computation, to appear.

Outreach Activity

Selected Pictures

Evidence based reconstruction of the Roman road network on Sardinia

A model-based reconstruction (black) in comparison with a scholarly interpretation (yellow) of the Roman road network on Sardinia. The model was trained using a digital elevation model, a collection of ancient sites (blue circles) and additional points of evidence: way stations (red diamonds) and milestones (yellow triangles).