First-Price vs. Vickrey Auctions

from tys import probe, progress


class Agent:
    """Bidder with regret-matching over a few shading options."""

    def __init__(self, idx: int, rng):
        self.idx = idx
        self.rng = rng

        self.actions = [1.0, 0.8, 0.6]
        self.regret = [0.0] * len(self.actions)

    def _strategy(self):
        """Convert positive regrets into a probability distribution."""
        positives = [max(r, 0.0) for r in self.regret]
        total = sum(positives)
        if total > 0:
            return [r / total for r in positives]
        return [1.0 / len(self.actions)] * len(self.actions)

    def choose_action(self) -> int:
        probs = self._strategy()
        r = self.rng.random()
        cumulative = 0.0
        for i, p in enumerate(probs):
            cumulative += p
            if r <= cumulative:
                return i
        return len(self.actions) - 1

    def update(self, value: float, bids: list[float], winner: int, payment: float, rule: str, chosen: int):
        chosen_payoff = value - payment if winner == self.idx else 0.0
        for i, a in enumerate(self.actions):
            alt_bids = bids[:]
            alt_bids[self.idx] = value * a
            max_bid = max(alt_bids)
            winners = [j for j, b in enumerate(alt_bids) if b == max_bid]
            w = self.rng.choice(winners)
            if rule == "first_price":
                pay = alt_bids[w]
            else:
                sorted_bids = sorted(alt_bids, reverse=True)
                pay = sorted_bids[1] if len(sorted_bids) > 1 else 0.0
            payoff = value - pay if w == self.idx else 0.0
            regret = payoff - chosen_payoff
            if regret > 0:
                self.regret[i] += regret


def simulate(cfg: dict):
    """Run repeated auctions and record summary metrics."""

    import simpy
    import random

    env = simpy.Environment()

    num_agents = int(cfg["num_agents"])
    num_rounds = int(cfg["num_rounds"])
    rule = cfg["auction_rule"]  # ``first_price`` or ``vickrey``
    seed = int(cfg.get("seed", 1))

    rng = random.Random(seed)
    agents = [Agent(i, rng) for i in range(num_agents)]

    revenue_total = 0.0
    efficient_total = 0
    done = env.event()

    def run():
        nonlocal revenue_total, efficient_total
        for t in range(num_rounds):
            vals = [rng.random() for _ in range(num_agents)]
            bids = []
            choices = []
            for ag, val in zip(agents, vals):
                idx = ag.choose_action()
                choices.append(idx)
                bids.append(val * ag.actions[idx])

            max_bid = max(bids)
            winners = [i for i, b in enumerate(bids) if b == max_bid]
            winner = rng.choice(winners)

            if rule == "first_price":
                payment = bids[winner]
            else:  # Vickrey second-price
                sorted_bids = sorted(bids, reverse=True)
                payment = sorted_bids[1] if len(sorted_bids) > 1 else 0.0

            revenue_total += payment
            if vals[winner] == max(vals):
                efficient_total += 1

            truthful = sum(1 for idx in choices if agents[0].actions[idx] == 1.0) / num_agents

            probe("revenue", env.now, payment)
            probe("allocative_efficiency", env.now, efficient_total / (t + 1))
            probe("truthful_bidding", env.now, truthful)

            for i, ag in enumerate(agents):
                ag.update(vals[i], bids, winner, payment, rule, choices[i])

            progress(int(100 * (t + 1) / num_rounds))
            yield env.timeout(1)

        done.succeed({
            "avg_revenue": revenue_total / num_rounds,
            "efficiency": efficient_total / num_rounds,
        })

    env.process(run())
    env.run(until=done)
    return done.value


def requirements():
    return {
        "builtin": ["micropip", "pyyaml"],
        "external": ["simpy==4.1.1"],
    }