Monte Carlo Search

Monte Carlo Equilibrium Search Module

This module provides tools for searching and analyzing equilibria in adaptive game environments using grid search and Monte Carlo methods. It includes functionality for detecting convergence, identifying limit cycles, classifying equilibrium types, and visualizing the distribution of equilibria across the strategy space.

The module is designed to work with the AdaptiveEnv class and provides comprehensive analysis of equilibrium structures in multi-agent influencer games.

Dependencies:

• InflGame.adaptive.grad_func_env

• InflGame.utils

• NumPy

• PyTorch

• Matplotlib

• pandas

Usage:

The search_env class can be used to search for equilibria across the strategy space using either grid-based or Monte Carlo sampling. It supports parallel processing for computational efficiency and provides detailed classification of equilibrium types.

Example:

from InflGame.adaptive.monte_search import search_env
import torch
import numpy as np

# Initialize the search environment
searcher = search_env(
    num_agents=3,
    agents_pos=np.array([0.2, 0.5, 0.8]),
    parameters=torch.tensor([0.1, 0.1, 0.1]),
    resource_distribution=torch.tensor([10.0, 20.0, 30.0]),
    bin_points=np.linspace(0, 1, 100),
    infl_configs={'infl_type': 'gaussian'},
    learning_rate_type='cosine_annealing',
    learning_rate=[0.0001, 0.01, 15],
    time_steps=10000,
    domain_type='1d',
    domain_bounds=[0, 1]
)

# Set up the adaptive environment
searcher.setup_adaptive_env()

# Perform grid search for equilibria
results = searcher.search_Eq(
    resolution=10,
    time_steps=10000,
    use_parallel=True
)

# Analyze results
stats = searcher.analyze_grid_search_results()

# Print summary
searcher.print_results_summary()

# Visualize equilibrium distribution
fig = searcher.plot_equilibrium_analysis()
fig.show()

Classes

InflGame.adaptive.monte_search.analyze_unique_equilibria(result_tensor, tolerance=0.0001)

Analyze Monte Carlo results to find unique equilibria and their frequencies.

Parameters:

• result_tensor (torch.Tensor) – Tensor of final positions from Monte Carlo runs

• tolerance (float) – Tolerance for considering positions as “near-unique”

Returns:

Dictionary with unique equilibria, frequencies, and statistics

Return type:

dict

InflGame.adaptive.monte_search.print_equilibrium_analysis(analysis_results)

Print a detailed analysis of the equilibrium results.

Parameters:

analysis_results (dict) – Results from analyze_unique_equilibria

class InflGame.adaptive.monte_search.search_env(num_agents, agents_pos, parameters, resource_distribution, bin_points, infl_configs={'infl_type': 'gaussian'}, learning_rate_type='cosine_annealing', learning_rate=[0.0001, 0.01, 15], time_steps=100, fp=0, infl_cshift=False, cshift=None, infl_fshift=False, Q=None, domain_type='1d', domain_bounds=[0, 1], resource_type='na', domain_refinement=10, tolerance=1e-05, tolerated_agents=None, ignore_zero_infl=False)

The search_env class provides a framework for searching and analyzing equilibria in adaptive game environments. It supports grid-based and Monte Carlo sampling methods to explore the strategy space, detect convergence patterns, identify limit cycles, and classify equilibrium types based on agent positions and clustering.

This class is particularly useful for understanding the multiplicity and stability of equilibria in multi-agent influencer games across various domains (1D, 2D, and simplex).

Key Features:

• Grid search and Monte Carlo sampling for equilibrium discovery

• Parallel processing support for computational efficiency

• Automatic detection of convergence and limit cycles

• Classification of equilibrium types based on agent clustering

• Comprehensive visualization of equilibrium distributions

Methods

analyze_grid_search_results([results_dict, ...])	Analyze equilibrium search results to classify equilibrium types and compute statistics.
classify_equilibrium_type(positions[, tolerance])	Classify equilibrium type based on agent clustering and spatial arrangement.
detect_approximate_cycles(sequence[, ...])	Detect approximate periodic cycles in gradient ascent trajectories.
gradient_ascent_monte_carlo(number_samples, seed)	Run gradient ascent using Monte Carlo generated starting positions with parallelization.
monte_carlo_unit_hypercube(number_samples, seed)	Generate random samples in the unit hypercube for Monte Carlo equilibrium search.
plot_equilibrium_analysis([results_dict, ...])	Create comprehensive visualizations of equilibrium analysis results.
print_results_summary()	Print a formatted summary of equilibrium search analysis results.
search_Eq([resolution, number_samples, ...])	Search for equilibrium positions from multiple starting points across the strategy space.
setup_adaptive_env()	Set up the adaptive environment for equilibrium search.
unit_cube_3d([resolution])	Generate a 3D grid of points in the unit cube for systematic equilibrium search.

analyze_grid_search_results(results_dict=None, position_tolerance=0.001)

Analyze equilibrium search results to classify equilibrium types and compute statistics.

This method processes the results from search_Eq() to categorize convergence behavior, classify equilibrium types based on agent clustering, and compute comprehensive statistics about the equilibrium landscape.

Classification Categories:

• Converged: Gradient ascent reached a stable equilibrium

• Cycling: Limit cycle detected in the dynamics

• No Result: Failed to converge within time limit

Example:

results = searcher.search_Eq(resolution=10)
stats = searcher.analyze_grid_search_results(
    results_dict=results,
    position_tolerance=1e-3
)

print(f"Convergence rate: {stats['converged_percentage']:.1f}%")
print(f"Equilibrium types: {stats['equilibrium_types']}")

Parameters:

• results_dict (Optional[Dict]) – Results dictionary from search_Eq(). Uses self.results_dict if None.

• position_tolerance (float) – Tolerance for grouping agents at similar positions.

Returns:

Dictionary containing: - total_points (int): Total starting points analyzed - converged (int): Number of converged points - cycles (int): Number of cycling trajectories - converged_percentage (float): Percentage that converged - equilibrium_types (Dict): Counts of each equilibrium type - equilibrium_type_percentages (Dict): Percentages of each type

Return type:

Dict

classify_equilibrium_type(positions, tolerance=0.001)

Classify equilibrium type based on agent clustering and spatial arrangement.

This method analyzes the final positions of agents to determine the equilibrium structure, grouping agents that are within tolerance of each other and providing a descriptive classification that captures both the clustering pattern and spatial ordering.

Classification Notation:

• (n): All n agents clustered together

• (n-1,1): n-1 agents at lower position, 1 isolated higher

• (1,n-1): 1 agent at lower position, n-1 grouped higher

• c(1,n-2,1): Symmetric arrangement with middle group centered at 0.5

• l(1,n-2,1): Asymmetric with middle group below 0.5

• u(1,n-2,1): Asymmetric with middle group above 0.5

Example:

positions = np.array([0.2, 0.5, 0.5, 0.8])
eq_type = searcher.classify_equilibrium_type(positions)
# Returns: '(1,2,1)' for symmetric 4-player equilibrium

Parameters:

• positions (np.ndarray) – Array of agent positions at equilibrium.

• tolerance (float) – Maximum distance to consider positions as equal.

Returns:

String describing the equilibrium type and spatial arrangement.

Return type:

str

detect_approximate_cycles(sequence, tolerance=0.05, min_period=10, max_period=None)

Detect approximate periodic cycles in gradient ascent trajectories.

This method identifies limit cycles in the dynamics by searching for repeating patterns in the position sequence, allowing for some numerical tolerance to handle cases where cycles aren’t perfectly identical.

Algorithm:

Uses autocorrelation to detect periodicity, computing correlation between the sequence and shifted versions of itself to find the best matching period.

Parameters:

• sequence (np.ndarray) – Time series of positions or values to analyze.

• tolerance (float) – Tolerance for considering patterns as similar.

• min_period (int) – Minimum period length to consider.

• max_period (Optional[int]) – Maximum period length to consider. Defaults to half sequence length.

Returns:

Dictionary containing cycle detection results with keys: - has_approximate_cycle (bool): Whether a cycle was detected - period (int): Detected period length (None if no cycle) - correlation_score (float): Quality of the detected cycle - confidence (float): Confidence in cycle detection (0-1)

Return type:

Dict

gradient_ascent_monte_carlo(number_samples, seed, tolerance=1e-05, tolerated_agents=None, parallel=True, max_workers=None, batch_size=None, time_steps=None)

Run gradient ascent using Monte Carlo generated starting positions with parallelization.

This function generates random starting positions using the monte_carlo_unit_hypercube method and then runs gradient ascent for each position in parallel, similar to final_pos_over_reach but using random initial positions instead of varying parameters.

Parameters:

• number_samples (int) – Number of Monte Carlo samples to generate

• seed (int) – Random seed for reproducibility

• tolerance (float) – Tolerance for convergence

• tolerated_agents (Optional[int]) – Number of agents allowed to tolerate deviations

• parallel (bool) – Whether to use parallel processing

• max_workers (Optional[int]) – Maximum number of parallel workers (defaults to CPU count)

• batch_size (Optional[int]) – Batch size for processing (auto-calculated if None)

• time_steps (Optional[int]) – Maximum time steps for gradient ascent

Returns:

The final positions of agents for each Monte Carlo sample

Return type:

torch.Tensor

Raises:

• ValueError – If input parameters are invalid

• RuntimeError – If computation fails

monte_carlo_unit_hypercube(number_samples, seed)

Generate random samples in the unit hypercube for Monte Carlo equilibrium search.

This method generates uniformly distributed random starting positions in the n-dimensional unit hypercube [0,1]^n, where n is the number of agents.

Parameters:

• number_samples (int) – Number of random samples to generate.

• seed (int) – Random seed for reproducibility.

Returns:

Tensor of random positions with shape (number_samples, num_agents).

Return type:

torch.Tensor

plot_equilibrium_analysis(results_dict=None, plot_types=['convergence', 'distribution', 'percentage'], save=False, name_ads=[], save_types=['.png', '.svg'], paper_figure={'figure_id': 'equilibrium_analysis', 'paper': False, 'section': 'equilibrium_analysis'}, font={'default_size': 12, 'font_family': 'sans-serif', 'label_size': 11, 'tick_size': 10, 'title_size': 14}, colors={'bar_distribution': '#3498DB', 'bar_percentage': '#E74C3C', 'converged': '#2E8B57', 'cycling': '#FF6B6B', 'no_result': '#95A5A6'}, text_configs={'convergence_title': 'Convergence Behavior Distribution', 'distribution_title': 'Equilibrium Types Distribution', 'percentage_title': 'Equilibrium Types (% of Converged)', 'xlabel_distribution': 'Equilibrium Type', 'xlabel_percentage': 'Equilibrium Type', 'ylabel_distribution': 'Count', 'ylabel_percentage': 'Percentage (%)'}, figsize=None)

Create comprehensive visualizations of equilibrium analysis results.

Parameters:

statsDict

Statistics dictionary containing convergence results and equilibrium types.

plot_typesList[str], optional

List of plot types to include: ‘convergence’, ‘distribution’, ‘percentage’. Default is all three.

savebool, optional

Whether to save the figure. Default is False.

name_adsList[str], optional

List of additional name components for file naming. Default is [].

save_typesList[str], optional

File extensions for saving. Default is [‘.png’, ‘.svg’].

paper_figureDict, optional

Dictionary with keys ‘paper’ (bool), ‘section’ (str), ‘figure_id’ (str). Controls paper-style naming and organization. Default is {‘paper’: False, ‘section’: ‘equilibrium_analysis’, ‘figure_id’: ‘equilibrium_analysis’}.

fontDict, optional

Font configuration dictionary with keys: ‘default_size’, ‘title_size’, ‘label_size’, ‘tick_size’, ‘font_family’.

colorsDict, optional

Color configuration for different plot elements.

text_configsDict, optional

Text configuration for titles and labels.

figsizeOptional[tuple], optional

Figure size. If None, automatically determined based on number of plots.

Returns:

matplotlib.figure.Figure

The generated matplotlib figure.

Examples

>>> # Show only convergence pie chart
>>> fig = plot_equilibrium_analysis(stats, plot_types=['convergence'])
>>> 
>>> # Show distribution and percentage, save with custom naming
>>> fig = plot_equilibrium_analysis(
...     stats,
...     plot_types=['distribution', 'percentage'],
...     save=True,
...     name_ads=['gaussian', 'n3'],
...     paper_figure={'paper': True, 'section': 'results', 'figure_id': 'eq_analysis'}
... )

print_results_summary()

Print a formatted summary of equilibrium search analysis results.

This method displays a comprehensive, human-readable summary of the equilibrium search results, including convergence statistics, equilibrium type distributions, and detailed breakdowns of each equilibrium category.

Must be called after analyze_grid_search_results().

Example:

results = searcher.search_Eq(resolution=10)
searcher.analyze_grid_search_results(results)
searcher.print_results_summary()

Raises:

AttributeError – If analyze_grid_search_results() hasn’t been called yet.

search_Eq(resolution=None, number_samples=None, time_steps=10000, use_parallel=True, num_workers=None, use_monte_carlo=False, seed=42)

Search for equilibrium positions from multiple starting points across the strategy space.

This method performs a comprehensive search for equilibria using either grid-based sampling or Monte Carlo random sampling. It analyzes convergence behavior from each starting point, detecting both stable equilibria and limit cycles.

Search Methods:

• Grid Search (use_monte_carlo=False): Systematic sampling on a uniform grid

• Monte Carlo (use_monte_carlo=True): Random sampling from uniform distribution

Example:

# Grid search with 10 points per dimension
results = searcher.search_Eq(
    resolution=10,
    time_steps=10000,
    use_parallel=True
)

# Monte Carlo search with 1000 random samples
results = searcher.search_Eq(
    number_samples=1000,
    time_steps=10000,
    use_monte_carlo=True,
    seed=42
)

Parameters:

• resolution (Optional[int]) – Grid resolution (points per dimension). Required for grid search.

• number_samples (Optional[int]) – Number of random samples. Required for Monte Carlo search.

• time_steps (int) – Maximum gradient ascent iterations per starting point.

• use_parallel (bool) – Whether to use parallel processing for efficiency.

• num_workers (Optional[int]) – Number of parallel workers. Defaults to CPU count.

• use_monte_carlo (bool) – Use Monte Carlo sampling instead of grid.

• seed (int) – Random seed for reproducibility (Monte Carlo only).

Returns:

Dictionary mapping starting points to convergence results.

Return type:

Dict

setup_adaptive_env()

Set up the adaptive environment for equilibrium search.

This method initializes the gradient function environment with the provided parameters, enabling gradient ascent dynamics for equilibrium discovery. Must be called before performing any equilibrium search operations.

Example:

searcher = search_env(...)
searcher.setup_adaptive_env()
results = searcher.search_Eq(resolution=10)

unit_cube_3d(resolution=10)

Generate a 3D grid of points in the unit cube for systematic equilibrium search.

This method creates a uniform grid of points in [0,1]^3 space, excluding boundary points to focus on interior equilibria.

Parameters:

resolution (int) – Number of points per dimension (excluding boundaries).

Returns:

Tensor of grid points with shape (n_points, 3).

Return type:

torch.Tensor

InflGame.adaptive.monte_search.visualize_equilibrium_clustering(analysis_results, original_results)

Create visualizations for the equilibrium clustering analysis.

Parameters:

• analysis_results – Results from analyze_unique_equilibria

• original_results – Original Monte Carlo results tensor