{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "44f12d9d",
   "metadata": {},
   "source": [
    "\n# PA1 — Normal‑Form Games: Utilities, Best Responses, and Equilibria\n## CSCE 631 — Summer 2026\n*CSCE 631 — Summer 2026 — Programming Assignment 1*\n\n**Goals**\n- Represent 2‑player normal‑form games\n- Compute expected utilities for mixed strategies\n- Check best responses and Nash equilibrium (strict/weak)\n- Detect strictly dominated strategies\n- **Core**: Verify correlated equilibrium (CE) constraints for a given distribution\n- **Extra Credit**: Compute a CE via a small LP (SciPy)\n\n**What to submit:** your completed `.ipynb` on Canvas. Before submitting, do **Runtime → Restart and run all**.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e621f92b",
   "metadata": {},
   "source": [
    "\n",
    "## Setup\n",
    "Run this cell first. You may use only standard Python/NumPy. For the extra‑credit CE solver you may import SciPy if needed.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4b4b1d7f",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "import numpy as np\n",
    "\n",
    "# Helper: pretty print small arrays\n",
    "def show(arr, name=None):\n",
    "    if name: print(name, \"=\", end=\" \")\n",
    "    print(np.array(arr))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "204c3c5c",
   "metadata": {},
   "source": [
    "\n",
    "## Game Representation\n",
    "We represent a 2‑player game with two payoff matrices `U1` and `U2` of shape `(m, n)` where `m` is the number of player‑1 actions and `n` the number of player‑2 actions.\n",
    "A mixed strategy is a probability vector of length `m` (or `n`).\n",
    "\n",
    "You will implement utility calculations assuming row‑player is Player 1 and column‑player is Player 2.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1286ab67",
   "metadata": {},
   "source": [
    "\n",
    "### Task 1 — Expected Utility\n",
    "Implement `expected_utility(U, p, q)` that returns the expected utility to the owner of payoff matrix `U` when Player 1 plays `p` and Player 2 plays `q`.\n",
    "\n",
    "**Requirements**\n",
    "- Validate shapes and probabilities (nonnegative, sum to 1 within a tolerance)\n",
    "- Work for pure or mixed strategies\n",
    "- Return a scalar `float`\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d18738c0",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# === TODO: implement expected_utility ===\n",
    "def expected_utility(U, p, q, tol=1e-9):\n",
    "    \"\"\"Return E[u] for payoff matrix U (shape m x n) under mixed p (len m) vs q (len n).\n",
    "    Validate that p, q are probability vectors within tolerance tol.\n",
    "    \"\"\"\n",
    "    # TODO: replace with your implementation\n",
    "    raise NotImplementedError\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "11a3236c",
   "metadata": {},
   "source": [
    "\n",
    "### Public Tests: Task 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e65c537a",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# Simple 2x2 test (Matching Pennies payoff for Player 1)\n",
    "U1 = np.array([[1, -1],\n",
    "               [-1, 1]], dtype=float)\n",
    "\n",
    "p = np.array([0.5, 0.5])\n",
    "q = np.array([0.5, 0.5])\n",
    "\n",
    "# Expected utility should be 0 at uniform strategies\n",
    "eu = expected_utility(U1, p, q)\n",
    "assert abs(eu - 0.0) < 1e-9\n",
    "\n",
    "# Pure vs pure\n",
    "assert expected_utility(U1, np.array([1,0]), np.array([1,0])) == 1.0  # (row0, col0)\n",
    "assert expected_utility(U1, np.array([1,0]), np.array([0,1])) == -1.0 # (row0, col1)\n",
    "print(\"✅ Task 1 public tests passed\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6bfe65c0",
   "metadata": {},
   "source": [
    "\n",
    "### Task 2 — Best Response (pure BR to a mixed opponent)\n",
    "Implement `is_best_response_pure(U1, U2, s_index, opp_mix, player)` that returns `True/False` indicating whether `s_index` (a *pure* action index) is a best response to the opponent’s mixed strategy `opp_mix` for the specified `player ∈ {1,2}`.\n",
    "\n",
    "**Notes**\n",
    "- Use `expected_utility` from Task 1.\n",
    "- Ties count as best responses (weak BR). Later we’ll extend strictness options.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5eae874f",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# === TODO: implement is_best_response_pure ===\n",
    "def is_best_response_pure(U1, U2, s_index, opp_mix, player, tol=1e-9):\n",
    "    \"\"\"Return True if pure action s_index is a (weak) best response for 'player' against opp_mix.\n",
    "    player = 1 or 2. Use U1 for player 1 utilities, U2 for player 2.\n",
    "    \"\"\"\n",
    "    # TODO\n",
    "    raise NotImplementedError\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a71b79c3",
   "metadata": {},
   "source": [
    "\n",
    "### Public Tests: Task 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "005c917c",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# Prisoner's Dilemma\n",
    "# Actions: 0 = Cooperate (C), 1 = Defect (D)\n",
    "U1_PD = np.array([[-1, -3],\n",
    "                  [ 0, -2]], dtype=float)\n",
    "U2_PD = np.array([[-1,  0],\n",
    "                  [-3, -2]], dtype=float)\n",
    "\n",
    "# Against opponent mix leaning to C, best response is D for either player\n",
    "opp = np.array([0.8, 0.2])\n",
    "assert is_best_response_pure(U1_PD, U2_PD, s_index=1, opp_mix=opp, player=1)\n",
    "assert is_best_response_pure(U1_PD, U2_PD, s_index=1, opp_mix=opp, player=2)\n",
    "print(\"✅ Task 2 public tests passed\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "88d1df43",
   "metadata": {},
   "source": [
    "\n",
    "### Task 3 — Nash Equilibrium Check (strict/weak)\n",
    "Implement `is_nash_equilibrium(U1, U2, p, q, strict=False)` that returns `True/False` for whether `(p,q)` is a Nash equilibrium.\n",
    "\n",
    "**Details**\n",
    "- For **weak** NE (`strict=False`): every action in the support must be a best response (allowing ties).\n",
    "- For **strict** NE (`strict=True`): support actions must be *strictly* better than any deviation.\n",
    "- You may reuse `is_best_response_pure` and `expected_utility`.\n",
    "- Assume finite action sets and that `p`, `q` have small supports (students can enumerate pure deviations).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0e7fad7f",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# === TODO: implement is_nash_equilibrium ===\n",
    "def is_nash_equilibrium(U1, U2, p, q, strict=False, tol=1e-9):\n",
    "    \"\"\"Return True iff (p,q) is a (weak or strict) Nash equilibrium in a 2-player normal-form game.\"\"\"\n",
    "    # TODO\n",
    "    raise NotImplementedError\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "02936d8c",
   "metadata": {},
   "source": [
    "\n",
    "### Public Tests: Task 3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3d6807d2",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# Matching Pennies: (uniform, uniform) is a (weak) NE\n",
    "U1 = np.array([[1, -1],\n",
    "               [-1, 1]], dtype=float)\n",
    "U2 = -U1.copy()\n",
    "p = np.array([0.5, 0.5])\n",
    "q = np.array([0.5, 0.5])\n",
    "assert is_nash_equilibrium(U1, U2, p, q, strict=False)\n",
    "print(\"✅ Task 3 public tests passed\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ae641250",
   "metadata": {},
   "source": [
    "\n",
    "### Task 4 — Strictly Dominated Strategies\n",
    "Implement `strictly_dominated(U, player)` that returns a list (or boolean mask) of which pure strategies for `player` are **strictly dominated** (by possibly mixed opponents). For PA1 we’ll use a simple **pairwise strict dominance** check: a strategy `a` is strictly dominated if there exists another **pure** strategy `b` such that `u_i(b, a_{-i}) > u_i(a, a_{-i})` for **all** opponent pure actions.\n",
    "\n",
    "*(This simplified definition ignores domination by mixed strategies to keep PA1 tractable.)*\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "34c23572",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# === TODO: implement strictly_dominated ===\n",
    "def strictly_dominated(U, player):\n",
    "    \"\"\"Return indices (or mask) of strictly dominated pure strategies for `player` \n",
    "    using pairwise strict dominance by another pure strategy.\n",
    "    U is U1 if player==1 else U2.\n",
    "    \"\"\"\n",
    "    # TODO\n",
    "    raise NotImplementedError\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5840504",
   "metadata": {},
   "source": [
    "\n",
    "### Public Tests: Task 4\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "193e6936",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# Simple dominance example:\n",
    "# For player 1, action 0 is worse than action 1 in every column.\n",
    "U1_dom = np.array([[0, 0, 0],\n",
    "                   [1, 1, 1]], dtype=float)\n",
    "dom = strictly_dominated(U1_dom, player=1)\n",
    "# Expect that action 0 is dominated\n",
    "assert (0 in dom) or (hasattr(dom, \"__len__\") and bool(dom[0]) and not bool(dom[1]))\n",
    "print(\"✅ Task 4 public tests passed\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a17a8c9c",
   "metadata": {},
   "source": [
    "\n",
    "## Correlated Equilibrium (CE)\n",
    "A joint distribution \\(\\sigma(a_1,a_2)\\) is a **correlated equilibrium** if no player gains by deviating from the recommendation they receive.\n",
    "\n",
    "### Task 5 (Core) — CE Verifier\n",
    "Implement `is_correlated_equilibrium(U1, U2, sigma)` that returns `True/False` by checking the linear incentive constraints for both players:\n",
    "\n",
    "\\[\n",
    "\\sum_{a_{-i}} \\sigma(a_i,a_{-i})\\big(u_i(a_i,a_{-i}) - u_i(a_i',a_{-i})\\big) \\ge 0\n",
    "\\quad \\text{for all } i, a_i, a_i'.\n",
    "\\]\n",
    "\n",
    "Also verify \\(\\sigma\\ge 0\\) and \\(\\sum \\sigma = 1\\) within tolerance.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6666edeb",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# === TODO: implement is_correlated_equilibrium (verifier) ===\n",
    "def is_correlated_equilibrium(U1, U2, sigma, tol=1e-9):\n",
    "    \"\"\"Return True iff sigma (m x n) is a correlated equilibrium for (U1,U2).\"\"\"\n",
    "    # TODO\n",
    "    raise NotImplementedError\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ce0520fd",
   "metadata": {},
   "source": [
    "\n",
    "### Public Tests: Task 5\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0704c8fe",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# Coordination game: (2,2) for (0,0); (1,1) for (1,1)\n",
    "U1_c = np.array([[2, 0],\n",
    "                 [0, 1]], dtype=float)\n",
    "U2_c = np.array([[2, 0],\n",
    "                 [0, 1]], dtype=float)\n",
    "\n",
    "# A trivial CE: recommend (0,0) with prob 1\n",
    "sigma_trivial = np.array([[1.0, 0.0],\n",
    "                          [0.0, 0.0]])\n",
    "assert is_correlated_equilibrium(U1_c, U2_c, sigma_trivial)\n",
    "\n",
    "# Uniform over the two coordinated outcomes is also a CE\n",
    "sigma_two = np.array([[0.5, 0.0],\n",
    "                      [0.0, 0.5]])\n",
    "assert is_correlated_equilibrium(U1_c, U2_c, sigma_two)\n",
    "print(\"✅ Task 5 public tests passed\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5b205666",
   "metadata": {},
   "source": [
    "\n",
    "### Extra Credit — CE via LP (feasibility)\n",
    "**Optional**: Implement `find_correlated_equilibrium(U1, U2)` that returns a feasible \\(\\sigma\\) by solving a small LP (e.g., with SciPy `linprog`). Return `None` if no CE is found (should not occur for finite 2‑player games).\n",
    "\n",
    "> If you implement this, include a small demo that verifies your \\(\\sigma\\) with `is_correlated_equilibrium`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b642f742",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# === OPTIONAL: implement find_correlated_equilibrium via LP ===\n",
    "# from scipy.optimize import linprog  # if you choose to use SciPy\n",
    "def find_correlated_equilibrium(U1, U2):\n",
    "    \"\"\"Optional: return a feasible sigma (m x n) that satisfies CE constraints, or None.\"\"\"\n",
    "    # TODO (extra credit)\n",
    "    return None\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e8014e70",
   "metadata": {},
   "source": [
    "\n",
    "## Methods Note (≈200–300 words)\n",
    "Briefly discuss:\n",
    "- How you validated probability vectors and handled tolerances\n",
    "- How you handled strict vs. weak best responses/NE\n",
    "- One limitation of pairwise strict dominance detection\n",
    "- (If EC attempted) How you set up the LP and mapped constraints to matrices\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dd3f8f79",
   "metadata": {},
   "source": [
    "\n",
    "*Write your methods note here…*\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0238a066",
   "metadata": {},
   "source": [
    "\n",
    "## Final Checklist\n",
    "- All **public tests** show ✅\n",
    "- `Runtime → Restart and run all` completes without errors\n",
    "- Notebook saved and submitted on Canvas as `.ipynb`\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 5
}