// verify-the-price-you-didnt-bid.mjs
// Offline recomputation of every number shown by /strata/the-price-you-didnt-bid/.
//
// The page has three instruments. This script recomputes all of them from scratch,
// with no dependencies, using the same algorithms and the same seeded generator the
// page runs in the browser.
//
//   1. WEAK DOMINANCE in the second-price sealed-bid auction (Vickrey 1961).
//      Exhaustive over a discretised grid: for every own value v, every own bid b,
//      and every highest-rival-bid r, the payoff from bidding v is >= the payoff
//      from bidding b. Zero violations, and the two strict-loss regions located.
//
//   2. REVENUE EQUIVALENCE under independent private values, risk neutrality and
//      a uniform[0,1] value distribution. Closed forms:
//        E[highest of n uniforms]        = n/(n+1)
//        E[second highest of n uniforms] = (n-1)/(n+1)
//        first-price symmetric BNE bid   = ((n-1)/n) * v
//        expected revenue, all 4 formats = (n-1)/(n+1)
//      Checked three ways: closed form, a numerically-maximised best response
//      (confirming the shading factor is an equilibrium, not an assertion), and a
//      seeded Monte Carlo running English and Dutch as literal price clocks.
//
//   3. MYERSON's OPTIMAL RESERVE (Myerson 1981). Virtual value for uniform[0,1] is
//      psi(v) = 2v - 1, zero at v = 1/2, so the revenue-maximising reserve is 1/2
//      for EVERY n. Verified by exact differentiation of the revenue function
//        R_n(r) = n r^n (1-r) + n(n-1) [ (1-r^n)/n - (1-r^{n+1})/(n+1) ]
//      whose derivative is exactly n r^{n-1} (1 - 2r), plus a fine grid search, plus
//      Monte Carlo. The cost of the optimum is also computed: the no-sale ("burned
//      trade") probability r^n and the destroyed surplus n r^{n+1}/(n+1).
//
//   4. The GSP counterexample (Edelman, Ostrovsky & Schwarz 2007): in Google's
//      generalised second-price position auction, truthful bidding is NOT a
//      dominant strategy. The canonical instance is recomputed, and VCG is run on
//      the same instance to show truth-telling restored.
//
//   run:  node research/the-price-you-didnt-bid/verify-the-price-you-didnt-bid.mjs

let fails = 0, checks = 0;
const ok = (name, cond, extra = '') => {
  checks++;
  if (!cond) fails++;
  console.log(`${cond ? '  ok' : 'FAIL'}  ${name}${extra ? '   ' + extra : ''}`);
};
const approx = (a, b, eps) => Math.abs(a - b) <= eps;
const f = (x, d = 6) => Number(x).toFixed(d);

// ───────────────────────────────────────────────────────────────────────────
// 1. Vickrey: truthful bidding is weakly dominant in the second-price auction
// ───────────────────────────────────────────────────────────────────────────
// Payoff to a bidder with value v who bids b against a highest rival bid r,
// under the second-price rule. Tie convention (a FREE CHOICE, named on the page):
// a tie is broken by a fair coin, so the expected payoff on a tie is (v - r)/2.
function payoffSP(v, b, r) {
  if (b > r) return v - r;      // win, pay the rival's bid
  if (b < r) return 0;          // lose, pay nothing
  return (v - r) / 2;           // tie -> fair coin
}

console.log('\n-- 1. second-price: truth-telling is weakly dominant (exhaustive) ==');
{
  const STEP = 0.01, N = 101;              // grid 0.00 .. 1.00 inclusive
  const g = (i) => i / (N - 1);
  let triples = 0, violations = 0, strictWins = 0;
  let worstViolation = 0;
  for (let iv = 0; iv < N; iv++) {
    const v = g(iv);
    for (let ib = 0; ib < N; ib++) {
      const b = g(ib);
      for (let ir = 0; ir < N; ir++) {
        const r = g(ir);
        const uTruth = payoffSP(v, v, r);
        const uAlt = payoffSP(v, b, r);
        triples++;
        if (uAlt > uTruth + 1e-12) { violations++; worstViolation = Math.max(worstViolation, uAlt - uTruth); }
        if (uTruth > uAlt + 1e-12) strictWins++;
      }
    }
  }
  ok(`grid ${N}x${N}x${N} = ${triples.toLocaleString('en-US')} (value, bid, rival) triples examined`,
     triples === 101 * 101 * 101, `${triples}`);
  ok('bids that beat truth-telling in even ONE case: 0', violations === 0,
     `worst improvement found = ${worstViolation}`);
  ok('truth-telling is STRICTLY better in a positive fraction of cases',
     strictWins > 0, `${strictWins.toLocaleString('en-US')} triples (${f(100 * strictWins / triples, 2)}%)`);

  // the two failure modes, located exactly
  // (a) OVERBID and win at a loss: b > r > v  -> payoff v - r < 0
  const overbidLoss = payoffSP(0.40, 0.70, 0.55);
  ok('overbid failure mode: v=0.40, bid 0.70, rival 0.55 -> win at a LOSS',
     approx(overbidLoss, -0.15, 1e-12) && overbidLoss < 0, `payoff = ${f(overbidLoss)}`);
  ok('   ... truth-telling would have paid exactly 0 there',
     approx(payoffSP(0.40, 0.40, 0.55), 0, 1e-12));
  // (b) UNDERBID and lose a bargain: b < r < v -> forgone surplus v - r > 0
  const underbidMiss = payoffSP(0.80, 0.50, 0.65);
  ok('underbid failure mode: v=0.80, bid 0.50, rival 0.65 -> lose a bargain',
     approx(underbidMiss, 0, 1e-12));
  ok('   ... truth-telling would have earned 0.15 there',
     approx(payoffSP(0.80, 0.80, 0.65), 0.15, 1e-12), `${f(payoffSP(0.80, 0.80, 0.65))}`);

  // the worst-case shortfall the page reports, at every value on the grid
  {
    let allMatch = true, sample = '';
    for (let iv = 0; iv < N; iv++) {
      const v = g(iv);
      let worstShort = 0;
      for (let ib = 0; ib < N; ib++) {
        const b = g(ib);
        for (let ir = 0; ir < N; ir++) {
          const r = g(ir);
          const d = payoffSP(v, v, r) - payoffSP(v, b, r);
          if (d > worstShort) worstShort = d;
        }
      }
      // Exact grid bound. The continuum bound is max(v, 1-v): overbid by d and a
      // rival can make you pay d over your value; underbid by d and a rival can
      // take a bargain worth d. On the discrete grid the extreme rival bid is a
      // TIE (halved by the coin), so the reachable worst case is one step short.
      const bound = Math.max(v, 1 - v) - STEP;
      if (!approx(worstShort, bound, 1e-12)) { allMatch = false; sample = `v=${f(v, 2)} got ${f(worstShort)} want ${f(bound)}`; }
    }
    ok('worst-case shortfall from lying = max(v, 1-v) - 1/100 at every one of the 101 values',
       allMatch, sample || 'all 101 values match exactly');
    ok('   ... and the continuum bound it approximates is max(v, 1-v)',
       approx(Math.max(0.6, 0.4), 0.6, 1e-12));
  }

  // the reason, in one line: your bid never sets your price, only whether you win.
  let priceIndependent = true;
  for (let ib = 0; ib < N; ib++) {
    const b = g(ib), r = 0.37;
    if (b > r && !approx(payoffSP(0.9, b, r), 0.9 - r, 1e-12)) priceIndependent = false;
  }
  ok('every winning bid pays the SAME price (the rival bid), so bidding cannot buy a discount',
     priceIndependent);
}

// ───────────────────────────────────────────────────────────────────────────
// 2. Order statistics and the first-price equilibrium
// ───────────────────────────────────────────────────────────────────────────
const NS = [2, 3, 5, 10, 50];
const eHighest = (n) => n / (n + 1);
const eSecond = (n) => (n - 1) / (n + 1);
const shade = (n) => (n - 1) / n;

console.log('\n-- 2a. order statistics of n uniform[0,1] draws ==');
for (const n of NS) {
  // exact integration of the order-statistic densities, done numerically from
  // first principles (Simpson) so the closed forms are checked, not assumed.
  //   f_(1)(x) = n x^{n-1}         f_(2)(x) = n(n-1) x^{n-2} (1-x)
  const simpson = (fn, a, b, m) => {
    if (m % 2) m++;
    const h = (b - a) / m; let s = fn(a) + fn(b);
    for (let i = 1; i < m; i++) s += fn(a + i * h) * (i % 2 ? 4 : 2);
    return s * h / 3;
  };
  const m1 = simpson((x) => x * n * Math.pow(x, n - 1), 0, 1, 40000);
  const m2 = simpson((x) => x * n * (n - 1) * Math.pow(x, n - 2) * (1 - x), 0, 1, 40000);
  ok(`n=${String(n).padStart(2)}  E[max]      = n/(n+1)      = ${f(eHighest(n))}`,
     approx(m1, eHighest(n), 1e-7), `numeric ${f(m1)}`);
  ok(`n=${String(n).padStart(2)}  E[2nd max]  = (n-1)/(n+1)  = ${f(eSecond(n))}`,
     approx(m2, eSecond(n), 1e-7), `numeric ${f(m2)}`);
}

console.log('\n-- 2b. first-price: the shading factor (n-1)/n IS a best response ==');
for (const n of NS) {
  // Bidder with value v faces n-1 rivals who each bid ((n-1)/n)V, V ~ U[0,1].
  // P(win | bid b) = P(V < b*n/(n-1))^{n-1}; expected payoff (v-b)*that.
  const v = 0.8;
  const pay = (b) => {
    const q = Math.min(1, Math.max(0, b * n / (n - 1)));
    return (v - b) * Math.pow(q, n - 1);
  };
  let best = 0, bestU = -Infinity;
  for (let i = 0; i <= 2000000; i++) {           // fine grid over [0, v]
    const b = (i / 2000000) * v;
    const u = pay(b);
    if (u > bestU) { bestU = u; best = b; }
  }
  const closed = shade(n) * v;
  ok(`n=${String(n).padStart(2)}  best response to shaded rivals = ${f(closed, 5)} = ((n-1)/n)*v`,
     approx(best, closed, 1e-5), `numeric argmax ${f(best, 6)}`);
}

// The page's arena runs its own brute-force sweep over shading FACTORS (not bids)
// and prints the argmax next to (n-1)/n. These are the identical routines, so the
// numbers rendered in the browser are the numbers checked here.
console.log('\n-- 2b2. the page\'s in-browser shading sweep, same routines ==');
function fpPayoff(n, s, c) {
  if (s <= 0 || s >= 1) return 0;
  if (s <= c) return (1 - s) * Math.pow(s / c, n - 1) / (n + 1);
  const vs = c / s;
  return (1 - s) * (Math.pow(s / c, n - 1) * Math.pow(vs, n + 1) / (n + 1)
                    + (1 - vs * vs) / 2);
}
const SHADE_GRID = 2000;
function bestShade(n) {
  const c = shade(n);
  let bi = 0, bv = -Infinity;
  for (let i = 0; i <= SHADE_GRID; i++) {
    const s = i / SHADE_GRID, p = fpPayoff(n, s, c);
    if (p > bv) { bv = p; bi = i; }
  }
  let lo = Math.max(0, (bi - 1) / SHADE_GRID), hi = Math.min(1, (bi + 1) / SHADE_GRID);
  const gr = (Math.sqrt(5) - 1) / 2;
  let x1 = hi - gr * (hi - lo), x2 = lo + gr * (hi - lo);
  let f1 = fpPayoff(n, x1, c), f2 = fpPayoff(n, x2, c);
  for (let i = 0; i < 200; i++) {
    if (f1 < f2) { lo = x1; x1 = x2; f1 = f2; x2 = lo + gr * (hi - lo); f2 = fpPayoff(n, x2, c); }
    else { hi = x2; x2 = x1; f2 = f1; x1 = hi - gr * (hi - lo); f1 = fpPayoff(n, x1, c); }
  }
  const sStar = (lo + hi) / 2;
  return { grid: bi / SHADE_GRID, best: sStar, quoted: c,
           err: Math.abs(sStar - c), payoff: fpPayoff(n, sStar, c),
           payoffClosed: 1 / (n * (n + 1)) };
}
// First: the exact payoff formula the sweep scores with, checked against a
// completely independent Simpson integration of  E[(1-s)*v*min(1,s*v/c)^(n-1)].
for (const n of NS) {
  const c = shade(n);
  for (const s of [0.2, c, 0.9, 0.97]) {
    const PAN = 40000;
    let acc = 0;
    const g = (v) => {
      const q = Math.min(1, s * v / c);
      return (1 - s) * v * Math.pow(q, n - 1);
    };
    for (let i = 0; i <= PAN; i++) {
      const v = i / PAN;
      const w = (i === 0 || i === PAN) ? 1 : (i % 2 ? 4 : 2);
      acc += w * g(v);
    }
    acc *= (1 / PAN) / 3;
    ok(`n=${String(n).padStart(2)} s=${f(s, 4)}  payoff formula = ${f(fpPayoff(n, s, c), 7)}`,
       approx(fpPayoff(n, s, c), acc, 1e-6), `Simpson ${f(acc, 7)}`);
  }
}
// Then: the sweep itself must land on (n-1)/n without being told it.
for (const n of NS) {
  const b = bestShade(n);
  ok(`n=${String(n).padStart(2)}  sweep argmax ${b.best.toFixed(9)} = (n-1)/n ${b.quoted.toFixed(9)}`,
     approx(b.best, b.quoted, 1e-7), `gap ${b.err.toExponential(2)}`);
  ok(`n=${String(n).padStart(2)}  payoff at argmax = 1/(n(n+1)) = ${b.payoffClosed.toExponential(6)}`,
     approx(b.payoff, b.payoffClosed, 1e-12), `swept ${b.payoff.toExponential(6)}`);
  // the coarse grid alone must already be within one grid step
  ok(`n=${String(n).padStart(2)}  coarse ${SHADE_GRID}-step grid argmax within one step`,
     Math.abs(b.grid - b.quoted) <= 1 / SHADE_GRID + 1e-12, `grid ${f(b.grid, 6)}`);
}
// And total bidder surplus must close the accounting: E[max] - E[2nd] = n * 1/(n(n+1)).
for (const n of NS) {
  ok(`n=${String(n).padStart(2)}  n * 1/(n(n+1)) = E[max] - E[2nd] = ${f(1 / (n + 1), 9)}`,
     approx(n * (1 / (n * (n + 1))), eHighest(n) - eSecond(n), 1e-12),
     `surplus ${f(eHighest(n) - eSecond(n), 9)}`);
}

console.log('\n-- 2c. revenue equivalence, closed form ==');
for (const n of NS) {
  const spsb = eSecond(n);                       // pay the 2nd-highest value
  const fpsb = shade(n) * eHighest(n);           // pay ((n-1)/n) * highest value
  ok(`n=${String(n).padStart(2)}  first-price revenue = second-price revenue = ${f(eSecond(n))}`,
     approx(spsb, fpsb, 1e-12), `fp ${f(fpsb)}  sp ${f(spsb)}`);
}
ok('revenue rises with n and approaches 1', eSecond(50) > eSecond(10) && eSecond(50) < 1,
   `n=50 -> ${f(eSecond(50))}`);

// ───────────────────────────────────────────────────────────────────────────
// 2d. Monte Carlo: all four formats run as literal mechanisms, one seeded stream
// ───────────────────────────────────────────────────────────────────────────
// mulberry32 == the identical generator the page uses, so the page's default
// readout and this script's numbers agree bit for bit.
function mulberry32(a) {
  return function () {
    a |= 0; a = (a + 0x6D2B79F5) | 0;
    let t = Math.imul(a ^ (a >>> 15), 1 | a);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

const CLOCK_STEP = 1 / 4096;   // price-clock granularity (a named free choice)

function runArena(n, trials, seed) {
  const rng = mulberry32(seed);
  const sh = shade(n);
  let sEng = 0, sDut = 0, sFp = 0, sSp = 0;
  let maxEngGap = 0, maxDutGap = 0;
  const vals = new Array(n);
  for (let t = 0; t < trials; t++) {
    for (let i = 0; i < n; i++) vals[i] = rng();
    // exact order statistics of this draw
    let v1 = -1, v2 = -1;
    for (let i = 0; i < n; i++) {
      const v = vals[i];
      if (v > v1) { v2 = v1; v1 = v; } else if (v > v2) { v2 = v;}
    }
    // SEALED SECOND PRICE: truthful bids, winner pays the second-highest bid.
    const spPrice = v2;
    // ENGLISH (ascending price clock): each bidder stays in while clock <= value;
    // the sale price is the clock level at which the second-to-last bidder quits.
    let clock = 0, engPrice = 0;
    for (;;) {
      let active = 0;
      for (let i = 0; i < n; i++) if (vals[i] >= clock) active++;
      if (active <= 1) { engPrice = clock; break; }
      clock += CLOCK_STEP;
      if (clock > 1 + CLOCK_STEP) { engPrice = clock; break; }
    }
    // SEALED FIRST PRICE: symmetric BNE bid ((n-1)/n) * value; pay your own bid.
    const fpPrice = sh * v1;
    // DUTCH (descending price clock): first bidder to accept takes it at the clock
    // level; a bidder accepts when the clock falls to their bid.
    let dclock = 1, dutPrice = 0;
    for (;;) {
      let accepted = false;
      for (let i = 0; i < n; i++) if (sh * vals[i] >= dclock) { accepted = true; break; }
      if (accepted) { dutPrice = dclock; break; }
      dclock -= CLOCK_STEP;
      if (dclock < -CLOCK_STEP) { dutPrice = 0; break; }
    }
    sEng += engPrice; sDut += dutPrice; sFp += fpPrice; sSp += spPrice;
    maxEngGap = Math.max(maxEngGap, Math.abs(engPrice - spPrice));
    maxDutGap = Math.max(maxDutGap, Math.abs(dutPrice - fpPrice));
  }
  return {
    english: sEng / trials, dutch: sDut / trials,
    firstPrice: sFp / trials, secondPrice: sSp / trials,
    maxEngGap, maxDutGap
  };
}

console.log('\n-- 2d. Monte Carlo: four mechanisms, one seeded stream ==');
{
  const SEED = 20260720, TRIALS = 20000;
  for (const n of [2, 3, 5, 10]) {
    const a = runArena(n, TRIALS, SEED);
    const exact = eSecond(n);
    // standard error of the mean of the 2nd order statistic; 4 s.e. is generous
    const varSecond = (2 * n * (n - 1)) / ((n + 2) * (n + 1) * (n + 1)) - 0; // see note
    const se = Math.sqrt(Math.max(varSecond, 1e-12) / TRIALS);
    console.log(`   n=${String(n).padStart(2)}  eng ${f(a.english, 5)}  dut ${f(a.dutch, 5)}  ` +
                `fp ${f(a.firstPrice, 5)}  sp ${f(a.secondPrice, 5)}   exact ${f(exact, 5)}`);
    for (const [nm, val] of [['English', a.english], ['Dutch', a.dutch],
                             ['first-price', a.firstPrice], ['second-price', a.secondPrice]]) {
      ok(`n=${String(n).padStart(2)}  ${nm.padEnd(13)} MC revenue lands on (n-1)/(n+1)`,
         Math.abs(val - exact) < Math.max(6 * se, 2 * CLOCK_STEP),
         `|${f(val, 5)} - ${f(exact, 5)}| = ${f(Math.abs(val - exact), 5)}`);
    }
    ok(`n=${String(n).padStart(2)}  English clock reproduces the second-price outcome on EVERY draw`,
       a.maxEngGap <= CLOCK_STEP + 1e-12, `max gap ${f(a.maxEngGap, 6)} <= clock step ${f(CLOCK_STEP, 6)}`);
    ok(`n=${String(n).padStart(2)}  Dutch clock reproduces the sealed first-price outcome on EVERY draw`,
       a.maxDutGap <= CLOCK_STEP + 1e-12, `max gap ${f(a.maxDutGap, 6)} <= clock step ${f(CLOCK_STEP, 6)}`);
  }
  // PINNED default readout: exactly what the page shows on load (n=5, 20000 trials,
  // seed 20260720). Regression guard == page and verifier run identical code.
  const d = runArena(5, TRIALS, SEED);
  console.log(`   pinned default (n=5, ${TRIALS} trials, seed ${SEED}):`);
  console.log(`     English ${f(d.english, 4)}  Dutch ${f(d.dutch, 4)}  ` +
              `first ${f(d.firstPrice, 4)}  second ${f(d.secondPrice, 4)}  exact ${f(eSecond(5), 4)}`);
  ok('pinned default: English     = 0.6681', approx(+d.english.toFixed(4), 0.6681, 1e-9), f(d.english, 6));
  ok('pinned default: Dutch       = 0.6663', approx(+d.dutch.toFixed(4), 0.6663, 1e-9), f(d.dutch, 6));
  ok('pinned default: first-price = 0.6665', approx(+d.firstPrice.toFixed(4), 0.6665, 1e-9), f(d.firstPrice, 6));
  ok('pinned default: second-price= 0.6680', approx(+d.secondPrice.toFixed(4), 0.6680, 1e-9), f(d.secondPrice, 6));
}

// ───────────────────────────────────────────────────────────────────────────
// 3. Myerson: the optimal reserve is 1/2 for every n
// ───────────────────────────────────────────────────────────────────────────
// Second-price auction with public reserve r, n bidders, values iid U[0,1],
// seller's own value 0.
//   no bidder above r        (prob r^n)              -> revenue 0
//   exactly one above r      (prob n r^{n-1}(1-r))   -> revenue r
//   two or more above r                              -> revenue = 2nd highest value
function revenueWithReserve(n, r) {
  const one = n * Math.pow(r, n - 1) * (1 - r) * r;
  const tail = n * (n - 1) * ((1 - Math.pow(r, n)) / n - (1 - Math.pow(r, n + 1)) / (n + 1));
  return one + tail;
}
// exact derivative, by hand: dR/dr = n r^{n-1} (1 - 2r)
const dRevenue = (n, r) => n * Math.pow(r, n - 1) * (1 - 2 * r);
const burnProb = (n, r) => Math.pow(r, n);
const surplusDestroyed = (n, r) => n * Math.pow(r, n + 1) / (n + 1);
// Myerson virtual value for uniform[0,1]: psi(v) = v - (1-F)/f = v - (1-v) = 2v-1
const virtualValue = (v) => 2 * v - 1;

console.log('\n-- 3a. the virtual value pins the reserve, with no reference to n ==');
ok('psi(v) = 2v - 1 for uniform[0,1]', approx(virtualValue(0.3), -0.4, 1e-12) && approx(virtualValue(0.9), 0.8, 1e-12));
ok('psi(v) = 0 exactly at v = 1/2 -> reserve 1/2, and n never enters the equation',
   approx(virtualValue(0.5), 0, 1e-12));

console.log('\n-- 3b. R_n(r) checked against numerical integration and against MC ==');
for (const n of NS) {
  // numerical: E[revenue] = r*P(exactly one above r) + integral over 2nd-stat above r
  const simpson = (fn, a, b, m) => {
    if (m % 2) m++;
    const h = (b - a) / m; let s = fn(a) + fn(b);
    for (let i = 1; i < m; i++) s += fn(a + i * h) * (i % 2 ? 4 : 2);
    return s * h / 3;
  };
  const r = 0.5;
  const num = n * Math.pow(r, n - 1) * (1 - r) * r +
              simpson((x) => x * n * (n - 1) * Math.pow(x, n - 2) * (1 - x), r, 1, 40000);
  ok(`n=${String(n).padStart(2)}  R_n(0.5) closed form = ${f(revenueWithReserve(n, 0.5))}`,
     approx(num, revenueWithReserve(n, 0.5), 1e-9), `numeric ${f(num)}`);
}
{
  // Monte Carlo the whole institution for n=3, r=0.5
  const n = 3, r = 0.5, T = 400000, rng = mulberry32(777);
  let sum = 0, unsold = 0;
  for (let t = 0; t < T; t++) {
    let v1 = -1, v2 = -1;
    for (let i = 0; i < n; i++) { const v = rng(); if (v > v1) { v2 = v1; v1 = v; } else if (v > v2) v2 = v; }
    if (v1 < r) { unsold++; continue; }            // reserve not met: no sale
    sum += Math.max(v2, r);                        // pay max(2nd bid, reserve)
  }
  const mc = sum / T;
  ok(`n=3, r=0.5: MC revenue ${f(mc, 4)} matches closed form ${f(revenueWithReserve(3, 0.5), 4)}`,
     Math.abs(mc - revenueWithReserve(3, 0.5)) < 0.003, `diff ${f(Math.abs(mc - revenueWithReserve(3, 0.5)), 5)}`);
  ok(`n=3, r=0.5: MC no-sale rate ${f(unsold / T, 4)} matches r^n = ${f(burnProb(3, 0.5), 4)}`,
     Math.abs(unsold / T - burnProb(3, 0.5)) < 0.003);
}

console.log('\n-- 3c. the optimum sits at 0.5 for every n (derivative and grid search) ==');
for (const n of [2, 3, 5, 10, 50, 200]) {
  ok(`n=${String(n).padStart(3)}  dR/dr = n r^{n-1}(1-2r) vanishes at r = 0.5`,
     approx(dRevenue(n, 0.5), 0, 1e-12));
  // and confirm that hand derivative against a central difference
  const h = 1e-6, rr = 0.37;
  const fd = (revenueWithReserve(n, rr + h) - revenueWithReserve(n, rr - h)) / (2 * h);
  ok(`n=${String(n).padStart(3)}  hand derivative matches finite difference at r=0.37`,
     approx(fd, dRevenue(n, rr), 1e-4 * Math.max(1, Math.abs(dRevenue(n, rr)))),
     `hand ${f(dRevenue(n, rr))} fd ${f(fd)}`);
  // fine grid search, the same one the page runs
  let bestR = 0, bestV = -Infinity;
  for (let i = 0; i <= 1000; i++) {
    const r = i / 1000, v = revenueWithReserve(n, r);
    if (v > bestV) { bestV = v; bestR = r; }
  }
  if (n <= 20) {
    ok(`n=${String(n).padStart(3)}  grid search over 1001 reserves picks r* = ${bestR.toFixed(3)}`,
       approx(bestR, 0.5, 1e-9), `R(r*) = ${f(bestV)}`);
  } else {
    // HONEST LIMIT, stated on the page: for large n the revenue curve is flat to
    // double precision across the whole lower half of [0,1] (the reserve almost
    // never binds), so a numeric grid search cannot resolve the peak at all. The
    // ANALYTIC derivative still pins it exactly at 1/2. What we can check is that
    // r=0.5 is within floating-point noise of the numeric maximum.
    ok(`n=${String(n).padStart(3)}  revenue curve is flat to double precision; r=0.5 within 1e-12 of the numeric max`,
       revenueWithReserve(n, 0.5) >= bestV - 1e-12,
       `numeric argmax ${bestR.toFixed(3)} is float noise; R(0.5)=${f(revenueWithReserve(n, 0.5), 12)} R(max)=${f(bestV, 12)}`);
  }
}

console.log('\n-- 3d. the optimum never moves; its prize evaporates ==');
for (const n of NS) {
  const noRes = revenueWithReserve(n, 0), withRes = revenueWithReserve(n, 0.5);
  const gain = withRes - noRes;
  console.log(`   n=${String(n).padStart(2)}  no reserve ${f(noRes, 6)}  r*=0.5 ${f(withRes, 6)}  ` +
              `gain ${gain.toExponential(3)}  burned sales ${f(100 * burnProb(n, 0.5), 4)}%  ` +
              `surplus destroyed ${f(surplusDestroyed(n, 0.5), 6)}`);
  ok(`n=${String(n).padStart(2)}  R_n(0) = (n-1)/(n+1) exactly (reserve 0 is the plain auction)`,
     approx(noRes, eSecond(n), 1e-12));
  if (n <= 20) {
    ok(`n=${String(n).padStart(2)}  the reserve strictly helps the seller`, gain > 0, `+${gain.toExponential(3)}`);
  } else {
    // At n=50 the true gain is about 1e-16 == smaller than the rounding error of the
    // formula itself. The page reports it as "below double precision", not as zero
    // and not as positive, because the arithmetic genuinely cannot tell.
    ok(`n=${String(n).padStart(2)}  the gain has fallen below double precision (|gain| < 1e-12)`,
       Math.abs(gain) < 1e-12, `computed ${gain.toExponential(3)}`);
  }
}
ok('the seller gain collapses as n grows (n=2 gain > 900x the n=10 gain)',
   (revenueWithReserve(2, 0.5) - eSecond(2)) > 900 * (revenueWithReserve(10, 0.5) - eSecond(10)),
   `ratio ${f((revenueWithReserve(2, 0.5) - eSecond(2)) / (revenueWithReserve(10, 0.5) - eSecond(10)), 1)}`);
ok('n=2: gain to seller = 1/12 = 0.083333',
   approx(revenueWithReserve(2, 0.5) - eSecond(2), 1 / 12, 1e-12),
   f(revenueWithReserve(2, 0.5) - eSecond(2)));
ok('n=2: R_2(0.5) = 5/12 = 0.416667', approx(revenueWithReserve(2, 0.5), 5 / 12, 1e-12));
ok('n=2: one sale in four is destroyed on purpose (r^n = 0.25)',
   approx(burnProb(2, 0.5), 0.25, 1e-12));
ok('n=10: still one in ~1024 burned, for a gain of under 0.0001',
   approx(burnProb(10, 0.5), 1 / 1024, 1e-12) &&
   (revenueWithReserve(10, 0.5) - eSecond(10)) < 1e-4,
   `gain ${(revenueWithReserve(10, 0.5) - eSecond(10)).toExponential(3)}`);
// the reserve is NOT efficient: it destroys surplus the auction would have created
ok('n=2: surplus destroyed 0.083333 exceeds nothing the seller could recover elsewhere',
   approx(surplusDestroyed(2, 0.5), 1 / 12, 1e-12), f(surplusDestroyed(2, 0.5)));

// ───────────────────────────────────────────────────────────────────────────
// 4. GSP is not truthful; VCG on the same instance is
// ───────────────────────────────────────────────────────────────────────────
// Position auction, K=2 slots with click-through rates c1 >= c2, third slot c3=0.
// GSP: sort by bid; the advertiser in slot j pays, per click, the bid ranked j+1.
// The canonical instance from Edelman, Ostrovsky & Schwarz (2007): CTRs 200 and
// 199 clicks, per-click values 10, 4, 2.
const CTR = [200, 199, 0];
const VALS = [10, 4, 2];

function gspOutcome(bids, values) {
  const idx = bids.map((b, i) => i).sort((a, b) => bids[b] - bids[a] || a - b);
  const payoff = new Array(bids.length).fill(0);
  const price = new Array(bids.length).fill(0);
  for (let j = 0; j < idx.length; j++) {
    const who = idx[j], c = CTR[j] !== undefined ? CTR[j] : 0;
    const p = j + 1 < idx.length ? bids[idx[j + 1]] : 0;   // next bid down
    price[who] = p;
    payoff[who] = c * (values[who] - p);
  }
  return { order: idx, payoff, price };
}
// VCG for a position auction with values sorted descending v1>=v2>=...:
//   payment of the bidder in slot j = sum_{k>j} v_k (c_{k-1} - c_k)
function vcgPayment(slotIndex, sortedValues) {
  let p = 0;
  for (let k = slotIndex + 1; k < sortedValues.length; k++) {
    p += sortedValues[k] * ((CTR[k - 1] || 0) - (CTR[k] || 0));
  }
  return p;
}

console.log('\n-- 4. GSP: truthful bidding is NOT dominant (Edelman-Ostrovsky-Schwarz 2007) ==');
{
  const truthful = gspOutcome([10, 4, 2], VALS);
  ok('truthful bids 10/4/2: top advertiser takes slot 1 at price 4', truthful.price[0] === 4);
  ok('truthful payoff to the top advertiser = 200*(10-4) = 1200',
     truthful.payoff[0] === 1200, `${truthful.payoff[0]}`);
  const deviate = gspOutcome([3, 4, 2], VALS);
  ok('bidding 3 instead of 10 drops it to slot 2 at price 2', deviate.price[0] === 2);
  ok('the DEVIATION pays 199*(10-2) = 1592, beating the truthful 1200',
     deviate.payoff[0] === 1592 && deviate.payoff[0] > truthful.payoff[0],
     `${deviate.payoff[0]} > ${truthful.payoff[0]} (gain ${deviate.payoff[0] - truthful.payoff[0]})`);
  // exhaustive over a fine bid grid: find the best deviation
  let bestB = 0, bestU = -Infinity;
  for (let i = 0; i <= 2000; i++) {
    const b = i / 100;
    const u = gspOutcome([b, 4, 2], VALS).payoff[0];
    if (u > bestU + 1e-9) { bestU = u; bestB = b; }
  }
  ok('exhaustive search over bids 0..20: the best bid is BELOW the true value 10',
     bestB < 10 - 1e-9, `argmax bid ${bestB.toFixed(2)} -> payoff ${bestU.toFixed(0)}`);

  // VCG on the same instance restores truthfulness
  const vcgSlot1 = vcgPayment(0, VALS);   // 4*(200-199) + 2*(199-0)
  const vcgSlot2 = vcgPayment(1, VALS);   // 2*(199-0)
  ok('VCG price for slot 1 = 4*(200-199) + 2*(199-0) = 402', vcgSlot1 === 402, `${vcgSlot1}`);
  ok('VCG price for slot 2 = 2*(199-0) = 398', vcgSlot2 === 398, `${vcgSlot2}`);
  const vcgTruth = CTR[0] * VALS[0] - vcgSlot1;      // 2000 - 402
  const vcgDev = CTR[1] * VALS[0] - vcgPayment(1, [4, 10, 2].slice().sort((a, b) => b - a));
  // under VCG, if the top advertiser shades into slot 2 the payment is 2*(199-0)=398
  const vcgDevExact = CTR[1] * VALS[0] - 398;
  ok('VCG: truthful payoff 2000-402 = 1598', vcgTruth === 1598, `${vcgTruth}`);
  ok('VCG: the same shading deviation pays 1990-398 = 1592, which is WORSE',
     vcgDevExact === 1592 && vcgTruth > vcgDevExact, `${vcgDevExact} < ${vcgTruth}`);
  ok('   (the sorted-values helper agrees)', vcgDev === vcgDevExact, `${vcgDev}`);
  // and the knife-edge: with c2 far below c1 the GSP deviation stops paying
  const flat = (c2) => {
    const saveC2 = CTR[1]; CTR[1] = c2;
    const t = gspOutcome([10, 4, 2], VALS).payoff[0];
    const d = gspOutcome([3, 4, 2], VALS).payoff[0];
    CTR[1] = saveC2;
    return { t, d };
  };
  const wide = flat(100);
  ok('when slot 2 is much weaker (CTR 100 vs 200), truthful bidding wins again in GSP',
     wide.t > wide.d, `truthful ${wide.t} vs deviation ${wide.d}`);
  ok('   ... which is the point: GSP truthfulness depends on the CTRs, i.e. it is not dominant',
     wide.t > wide.d && deviate.payoff[0] > truthful.payoff[0]);
}

console.log(`\n${fails === 0 ? 'ALL CHECKS PASSED' : fails + ' CHECK(S) FAILED'}  (${checks} checks)\n`);
process.exit(fails === 0 ? 0 : 1);
