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

problemreductions/models/algebraic/
equilibrium_point.rs
