GPT 6 Astra Ultra attempt on Econ-22

Proof: The objective is nonnegative on the feasible set. A bounded-below linear objective on a nonempty polyhedron attains its infimum; apply the standard finite-dimensional LP attainment theorem. Among optima choose one, $t$, with minimum support. If its supported columns of $B$ are dependent, choose a nonzero vector $z$ supported there with $Bz=0$. For sufficiently small positive and negative $\epsilon$, $t+\epsilon z$ remains nonnegative and feasible. Optimality forces $q_a\cdot z=0$, since otherwise one sign improves the objective. Choose a sign and increase its magnitude until the first positive coordinate becomes zero. Such a finite endpoint exists in at least one direction because $z\ne0$. This gives another optimum with strictly smaller support, a contradiction. Thus the supported columns are independent. ∎

Proof: For each $a$, the feasible polyhedron lies in the nonnegative orthant and therefore has no lines. A nonempty optimal face has a vertex. At a vertex with $k$ positive coordinates, the active incentive inequalities restricted to these coordinates must have rank $k$; otherwise a small two-sided feasible perturbation contradicts being a vertex. In particular $k\leq n-1$. Enumerate each support of size $k\leq n-1$ and each choice of $k$ incentive rows; solve the resulting square system when nonsingular and check all original inequalities and nonnegativity. Include $t=0$ separately. At least one optimal vertex is encountered for every inducible action. Gaussian elimination on matrices of size at most $n-1$ and all comparisons use a number of operations bounded as stated. Cramer's-rule determinant bounds give polynomial input-bit length for all candidates. Select the action/payment candidate maximizing $q_a\cdot(r-t)$.

To justify the tie rule, every candidate action is a utility maximizer for its contract. If another tied action would give the principal more, principal-favorable tie breaking realizes at least the candidate payoff. Conversely every actual contract/action outcome is feasible in the corresponding LP. Thus maximizing candidate payoffs attains exactly the optimal realizable payoff. ∎

Proof: First take $d\ne0$ and set $x=d\cdot t$. The incentive inequalities for $a$ reduce exactly to \[ (\theta_a-\theta_b)x\geq c_a-c_b\quad\text{for every }b. \] Intersect these half-lines to obtain a closed interval $I_a$, possibly empty or unbounded. A zero coefficient with a positive right side makes it empty. This takes $O(n)$ operations for each $a$. Since $d$ is nonzero and sums to zero, both $\{j:d_j>0\}$ and $\{j:d_j<0\}$ are nonempty. Define \[ \alpha_a^+=\min_{d_j>0}\frac{q_{aj}}{d_j},\qquad \alpha_a^-=\min_{d_j<0}\frac{q_{aj}}{-d_j}. \] Both numbers are nonnegative. For $x\geq0$, every $t\geq0$ with $d\cdot t=x$ satisfies $q_a\cdot t\geq\alpha_a^+x$: for $d_j>0$ this holds termwise; for $d_j\leq0$, $q_{aj}\geq0\geq\alpha_a^+d_j$. Equality is achieved by selecting a minimizing outcome $j$ and setting $t_j=x/d_j$, all other payments zero. For $x\leq0$ the analogous bound and one-outcome construction give minimum payment $\alpha_a^-(-x)$. In particular at $x=0$ the zero contract achieves minimum payment zero. Thus the exact minimum-payment cost as a function of $x$ is \[ C_a(x)=\begin{cases}\alpha_a^+x,&x\geq0,\\ \alpha_a^-(-x),&x\leq0.\end{cases} \] It is nondecreasing away from zero on either half-line. Consequently choose $x_a=0$ if $0\in I_a$, the left endpoint if $I_a\subset(0,\infty)$, or the right endpoint if $I_a\subset(-\infty,0)$. The endpoint is finite whenever needed. This remains optimal if a slope vanishes. Realize $x_a$ by the one-outcome payment described above, calculate $q_a\cdot r-C_a(x_a)$, and maximize over nonempty $I_a$. The preceding proposition's tie argument applies unchanged and proves global optimality. There is at least one nonempty interval because zero payment induces a minimum-cost action.

All intervals require $O(n^2)$ comparisons and divisions; all slope minima, rewards, and output comparisons require $O(nm)$ more. Endpoints are ratios of input costs and $\theta$ differences, and payments are products and ratios of a bounded number of these rational quantities. Sums in rewards have at most $m$ terms. Their encodings are polynomial in total input length.

For recognition, choose $q^0$ as one input row. If every row is equal, there is no variation in expected payment or reward across actions. A minimum-cost action is always chosen, and zero payment maximizes principal payoff. Otherwise choose a nonzero row difference $d=q_b-q^0$, and one coordinate $j_0$ with $d_{j_0}\ne0$. Set $\theta_a=(q_{aj_0}-q^0_{j_0})/d_{j_0}$ and check every coordinate of $q_a=q^0+\theta_a d$. This proves and tests the hypothesis using $O(nm)$ operations, and the same encoding bounds apply. ∎