problemreductions/models/algebraic/
equilibrium_point.rs

1//! Equilibrium Point problem implementation.
2//!
3//! Given n players, polynomial payoff functions F_i, and finite strategy sets M_i,
4//! determine whether there exists a pure-strategy Nash equilibrium: an assignment
5//! y = (y_1, ..., y_n) with y_i ∈ M_i such that for every player i,
6//! F_i(y) ≥ F_i(y with y_i replaced by any y' ∈ M_i).
7
8use crate::registry::{FieldInfo, ProblemSchemaEntry};
9use crate::traits::Problem;
10use crate::types::Or;
11use serde::de::Error as _;
12use serde::{Deserialize, Deserializer, Serialize};
13
14inventory::submit! {
15    ProblemSchemaEntry {
16        name: "EquilibriumPoint",
17        display_name: "Equilibrium Point",
18        aliases: &[],
19        dimensions: &[],
20        category: crate::registry::ProblemCategory::Algebraic,
21        module_path: module_path!(),
22        description: "Decide whether a pure-strategy Nash equilibrium exists for a multi-player game with polynomial payoff functions",
23        fields: &[
24            FieldInfo {
25                name: "polynomials",
26                type_name: "Vec<Vec<Vec<i64>>>",
27                description: "polynomials[i] is a list of affine factors for F_i; each factor [a0,a1,...,an] represents a0 + a1*x1 + ... + an*xn",
28            },
29            FieldInfo {
30                name: "range_sets",
31                type_name: "Vec<Vec<i64>>",
32                description: "range_sets[i] is the finite strategy set M_i for player i",
33            },
34        ],
35    }
36}
37
38/// Equilibrium Point problem.
39///
40/// Given n players, each with a finite strategy set M_i and a polynomial payoff
41/// function F_i, decide whether there exists a pure-strategy Nash equilibrium:
42/// an assignment y = (y_1, ..., y_n) with y_i ∈ M_i such that no player can
43/// improve their payoff by unilaterally deviating.
44///
45/// F_i is expressed as a product of affine factors. Each factor is represented
46/// as a coefficient vector `[a0, a1, ..., an]` evaluating to
47/// `a0 + a1*y_1 + ... + an*y_n`.
48///
49/// # Configuration
50///
51/// `config[i]` is an index into `range_sets[i]`; the assignment is
52/// `y_i = range_sets[i][config[i]]`.
53///
54/// # Example
55///
56/// ```
57/// use problemreductions::models::algebraic::EquilibriumPoint;
58/// use problemreductions::{Problem, BruteForce};
59///
60/// // 3 players, M_i = {0, 1} for all i.
61/// // F1 = x1*x2*x3, F2 = (1-x1)*x2, F3 = x1*(1-x3)
62/// let polynomials = vec![
63///     vec![vec![0,1,0,0], vec![0,0,1,0], vec![0,0,0,1]],
64///     vec![vec![1,-1,0,0], vec![0,0,1,0]],
65///     vec![vec![0,1,0,0], vec![1,0,0,-1]],
66/// ];
67/// let range_sets = vec![vec![0,1], vec![0,1], vec![0,1]];
68/// let problem = EquilibriumPoint::new(polynomials, range_sets).unwrap();
69/// let solver = BruteForce::new();
70/// let witness = solver.solve(&problem).unwrap();
71/// assert!(witness.is_some());
72/// ```
73#[derive(Debug, Clone, Serialize)]
74pub struct EquilibriumPoint {
75    /// polynomials[i] is a list of affine factors for F_i.
76    /// F_i(y) = product over all factors of (a0 + a1*y1 + ... + an*yn).
77    polynomials: Vec<Vec<Vec<i64>>>,
78    /// range_sets[i] is the finite strategy set M_i for player i.
79    range_sets: Vec<Vec<i64>>,
80}
81
82impl EquilibriumPoint {
83    fn validate_inputs(
84        polynomials: &[Vec<Vec<i64>>],
85        range_sets: &[Vec<i64>],
86    ) -> Result<(), crate::registry::ConstructionError> {
87        let n = polynomials.len();
88        if range_sets.len() != n {
89            return Err(format!(
90                "polynomials has {n} entries but range_sets has {} entries; lengths must match",
91                range_sets.len()
92            )
93            .into());
94        }
95        for (i, m) in range_sets.iter().enumerate() {
96            if m.is_empty() {
97                return Err(format!("range_sets[{i}] must be non-empty").into());
98            }
99        }
100        // Each factor must have length n+1 (constant + one coefficient per player).
101        let expected_factor_len = n + 1;
102        for (i, factors) in polynomials.iter().enumerate() {
103            for (j, factor) in factors.iter().enumerate() {
104                if factor.len() != expected_factor_len {
105                    return Err(format!(
106                        "polynomials[{i}][{j}] has {} coefficients but expected {expected_factor_len} (1 + num_players)",
107                        factor.len()
108                    ).into());
109                }
110            }
111        }
112        Ok(())
113    }
114
115    /// Create a new `EquilibriumPoint` instance, returning an error on invalid input.
116    pub fn new(
117        polynomials: Vec<Vec<Vec<i64>>>,
118        range_sets: Vec<Vec<i64>>,
119    ) -> Result<Self, crate::registry::ConstructionError> {
120        Self::validate_inputs(&polynomials, &range_sets)?;
121        Ok(Self {
122            polynomials,
123            range_sets,
124        })
125    }
126
127    /// Get the number of players.
128    pub fn num_players(&self) -> usize {
129        self.polynomials.len()
130    }
131
132    /// Get the polynomial factor lists.
133    pub fn polynomials(&self) -> &[Vec<Vec<i64>>] {
134        &self.polynomials
135    }
136
137    /// Get the strategy sets.
138    pub fn range_sets(&self) -> &[Vec<i64>] {
139        &self.range_sets
140    }
141
142    /// Evaluate F_i at a given assignment y (as i64 slice).
143    ///
144    /// Returns the product of all affine factors for player i.
145    fn eval_payoff(
146        &self,
147        player: usize,
148        assignment: &[i64],
149    ) -> Result<i64, crate::traits::EvaluationError> {
150        let factors = &self.polynomials[player];
151        if factors.is_empty() {
152            return Ok(0);
153        }
154        let mut product = 1_i64;
155        for coeffs in factors {
156            let mut value = coeffs[0];
157            for (&coefficient, &strategy) in coeffs[1..].iter().zip(assignment.iter()) {
158                let term = coefficient.checked_mul(strategy).ok_or_else(|| {
159                    crate::traits::EvaluationError::IntegerOverflow(
160                        "multiplying equilibrium payoff coefficient by strategy".to_string(),
161                    )
162                })?;
163                value = value.checked_add(term).ok_or_else(|| {
164                    crate::traits::EvaluationError::IntegerOverflow(
165                        "summing equilibrium payoff factor".to_string(),
166                    )
167                })?;
168            }
169            product = product.checked_mul(value).ok_or_else(|| {
170                crate::traits::EvaluationError::IntegerOverflow(
171                    "multiplying equilibrium payoff factors".to_string(),
172                )
173            })?;
174        }
175        Ok(product)
176    }
177}
178
179#[derive(Deserialize)]
180struct EquilibriumPointData {
181    polynomials: Vec<Vec<Vec<i64>>>,
182    range_sets: Vec<Vec<i64>>,
183}
184
185impl<'de> Deserialize<'de> for EquilibriumPoint {
186    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
187    where
188        D: Deserializer<'de>,
189    {
190        let data = EquilibriumPointData::deserialize(deserializer)?;
191        Self::new(data.polynomials, data.range_sets).map_err(D::Error::custom)
192    }
193}
194
195impl Problem for EquilibriumPoint {
196    const NAME: &'static str = "EquilibriumPoint";
197    type Solution = Vec<i64>;
198    type Value = Or;
199
200    crate::problem_parameters![("num_players", num_players),];
201
202    fn variant() -> Vec<(&'static str, &'static str)> {
203        crate::variant_params![]
204    }
205
206    fn evaluate(&self, solution: &Self::Solution) -> Result<Or, crate::traits::EvaluationError> {
207        Ok({
208            let n = self.num_players();
209            if solution.len() != n {
210                return Err(crate::traits::EvaluationError::InvalidConfiguration(
211                    format!("expected {n} player choices, got {}", solution.len()),
212                ));
213            }
214            if solution
215                .iter()
216                .zip(&self.range_sets)
217                .any(|(value, range)| !range.contains(value))
218            {
219                return Ok(Or(false));
220            }
221
222            // Check best-response condition for each player.
223            for i in 0..n {
224                let current_payoff = self.eval_payoff(i, solution)?;
225                // Try every y' in M_i for player i.
226                let mut best_response_satisfied = true;
227                for &alt in &self.range_sets[i] {
228                    if alt == solution[i] {
229                        continue;
230                    }
231                    // Build alternative assignment with player i using alt.
232                    let mut alt_assignment = solution.clone();
233                    alt_assignment[i] = alt;
234                    let alt_payoff = self.eval_payoff(i, &alt_assignment)?;
235                    if alt_payoff > current_payoff {
236                        best_response_satisfied = false;
237                        break;
238                    }
239                }
240                if !best_response_satisfied {
241                    return Ok(Or(false));
242                }
243            }
244            Or(true)
245        })
246    }
247}
248
249impl crate::solvers::BruteForceProblem for EquilibriumPoint {
250    fn dimensions(&self) -> Vec<usize> {
251        self.range_sets.iter().map(|m| m.len()).collect()
252    }
253}
254
255crate::declare_variants! {
256    default EquilibriumPoint => "2^num_players",
257}
258
259crate::register_brute_force! {
260    EquilibriumPoint decode |problem: &EquilibriumPoint, indices: Vec<usize>| indices.into_iter().enumerate().map(|(player, choice)| problem.range_sets[player][choice]).collect(),
261}
262
263#[cfg(feature = "example-db")]
264pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
265    // 3 players, M_i = {0, 1} for all i.
266    // F1 = x1*x2*x3:        factors [[0,1,0,0],[0,0,1,0],[0,0,0,1]]
267    // F2 = (1-x1)*x2:       factors [[1,-1,0,0],[0,0,1,0]]
268    // F3 = x1*(1-x3):       factors [[0,1,0,0],[1,0,0,-1]]
269    //
270    // config [0,1,0] → assignment (0,1,0).
271    // F1(0,1,0) = 0*1*0 = 0. Deviations for player 1: y'=1 → F1(1,1,0)=0. No improvement.
272    // F2(0,1,0) = (1-0)*1 = 1. Deviations for player 2: y'=0 → F2(0,0,0)=0. No improvement.
273    // F3(0,1,0) = 0*(1-0) = 0. Deviations for player 3: y'=1 → F3(0,1,1)=0. No improvement.
274    // → (0,1,0) is a Nash equilibrium.
275    let polynomials = vec![
276        vec![vec![0, 1, 0, 0], vec![0, 0, 1, 0], vec![0, 0, 0, 1]],
277        vec![vec![1, -1, 0, 0], vec![0, 0, 1, 0]],
278        vec![vec![0, 1, 0, 0], vec![1, 0, 0, -1]],
279    ];
280    let range_sets = vec![vec![0, 1], vec![0, 1], vec![0, 1]];
281    vec![crate::example_db::specs::ModelExampleSpec {
282        id: "equilibrium_point",
283        instance: Box::new(EquilibriumPoint::new(polynomials, range_sets).unwrap()),
284        optimal_config: serde_json::json!(vec![0, 1, 0]),
285        optimal_value: serde_json::json!(true),
286    }]
287}
288
289#[cfg(test)]
290#[path = "../../unit_tests/models/algebraic/equilibrium_point.rs"]
291mod tests;
problemreductions/models/algebraic/equilibrium_point.rs

problemreductions/models/algebraic/
equilibrium_point.rs
