we-solve (beta)

Econ-486 · economics · Economics

Economic models of costly computation

LLM status Open unverified

Statement

Original subject group: Economic theory, equilibrium and social choice

Audit classification: Published research agenda. Verified computational-constraint directions in the survey’s §7. The cost-and-repertoire identification exercise is editorial; finite maximization is elementary.

Definitions and precise research target

Model and research target. Consider economic decision problems $d$ drawn from a distribution $\mathcal D$. Each problem specifies a finite feasible set $X_d$, payoff function $u_d:X_d\to[0,1]$, and an information representation accessible through queries. A decision algorithm $A$ maps query histories into further queries or a final choice $x$. Let $C(A,d)$ be its expected number of elementary operations, and let $\kappa\geq0$ be an individual's cost per operation. A computational-choice model selects an algorithm from a stated repertoire $\mathcal A$ to maximize \[ V(A,d,\kappa)=E[u_d(A(d))]-\kappa C(A,d). \] The target is to construct and identify a parsimonious repertoire and cost specification that jointly predict choices, response times, and the effects of experimentally varied information complexity. Estimate $\kappa$ and repertoire heterogeneity using randomized changes in representation while holding material payoffs fixed. Determine restrictions under which algorithmic cost can be distinguished from preferences over outcomes and statistical choice noise. Require successful prediction on new problem families and an explicit account of how primitive computational operations map into measured time. A solution may establish failure of portable parameterization and identify the additional primitives required.

Definitions and maintained assumptions (editorial unless a source definition is named). Fix an explicit machine model, query alphabet, encoded problem family $\mathcal D$, and repertoire of algorithms. An algorithm must terminate almost surely; its random output is feasible and its expected operation count is finite. Costs and payoffs are expressed in comparable units, and the map from operation count to response time is part of the model. A representation treatment changes the encoding or query access while preserving outcomes and objective payoffs; this does not by itself prove invariance of utility or algorithm availability. To avoid assuming the decision maker sees the full problem before selecting a procedure, either let a procedure be chosen ex ante to maximize $\mathbb E_{d\sim\mathcal D}V(A,d,\kappa)$, or state the information available at the selection node. The unknown parameters include repertoire membership, $\kappa$, utility curvature if not fixed, and time measurement error. Identification is uniqueness, or a sharp set, among these parameters generating the same action-time law across treatments. With a known finite repertoire, optimizing $V$ by enumeration already solves the purely numerical choice problem.

Variants and assumption changes

  1. Fixed repertoire (editorial). Specify finitely many query procedures with experimentally calibrated time costs. Identify cost heterogeneity from representation changes and test predictions on new distributions of encoded problems.
  2. Uniform complexity (editorial). Let input size grow and restrict the repertoire to programs of bounded description length or operation budget. Study payoff loss as a function of that budget and whether parameters estimated at one size predict choice at another.

References and source audit

  1. §7 pp.53–54 in February 2023 manuscript. Supports the stated research area; exact displayed specification is editorial. DOI publication is2024; full inspected manuscript is February2023. https://geoffroydeclippel.net/Working%20Papers%20PDFs/JEL.pdf
  1. Geoffroy de Clippel; Kareen Rozen. 2024. Bounded Rationality in Choice Theory: A Survey. Published JEL 62(3),995–1039 (2024); inspected February2023 author manuscript §§6.4–7, printed pp.51–54. https://geoffroydeclippel.net/Working%20Papers%20PDFs/JEL.pdf. DOI: https://doi.org/10.1257/jel.20231592.

Common conventions: Source mathematical conventions

These conventions apply to each entry unless explicitly replaced.

Models and identification. A primitive model $m$ specifies all probability laws, feasible choices, information, equilibrium and measurement rules used by its target. The admissible class $\mathcal M$ is fixed independently of outcomes. If $P_O(m)$ is its observable probability law and $\tau(m)$ the target, its identified set at observable law $P$ is \[ \mathcal I_\tau(P)=\{\tau(m):m\in\mathcal M,\ P_O(m)=P\}. \] Point identification means that this set is a singleton. An empty set signals incompatibility of data and assumptions. Coordinate bounds need not describe the joint set. Bounds are sharp only if every retained target is attainable or arbitrarily approachable by compatible models. Finite bounds require explicit restrictions on unobserved quantities; unrestricted confounding, hidden wealth, extrapolation or arbitrary equilibrium selection can yield uninformative sets.

Causal interventions. A potential outcome $Y_i(p)$ is the outcome under a complete policy regime $p$, including timing, financing, information and market spillovers. The target population and units are fixed before treatment. With interference, use the complete assignment vector or a justified exposure mapping; individual no-interference notation alone cannot identify an economy-wide intervention. A difference of mean potential outcomes does not require the cross-world joint distribution. Conditioning on post-treatment migration, survival, enrollment or employment changes the estimand and needs separate justification.

Statistical statements. An estimator, confidence set, forecast or test specifies a sampling law, model class and loss/coverage criterion. Uniform $(1-\alpha)$-coverage means $\inf_{m\in\mathcal M}\Pr_m\{\tau(m)\in C_n\}\geq1-\alpha$, or an explicitly asymptotic version. The whole parameter space trivially has coverage, so informativeness requires a stated width, risk or power objective. A forecasting improvement is relative to a named benchmark, information set and evaluation population.

Equilibrium and optimization. An equilibrium comprises feasible plans, optimality, beliefs where needed, budget constraints and all market/resource clearing. The primitives or a stated benchmark define each correspondence $\mathcal E(p;m)$. Nonemptiness is assumed or proved, never inferred just from compact policy sets. A selected-equilibrium target uses a declared selection rule; a robust target quantifies over all permitted equilibria. Use suprema or infima unless attainment is established. An $\varepsilon$-optimal policy is feasible and within $\varepsilon$ of the finite optimum value. Report an empty feasible set separately.

Welfare and accounting. Normative utility, interpersonal normalization, social weights, numeraire, discounting and the use of public receipts are primitives. Behavioral utility need not coincide with the welfare criterion. Household welfare includes ownership income and rents once; adding profits again to compensating variation generally double-counts them. A monetary equivalent is defined by an explicit transfer and price convention, with monotonicity and range conditions. Average effects, mechanism contributions, transfers and welfare losses are different targets. Infinite sums require convergence and dynamic feasible plans require terminal or no-Ponzi conditions.

Source versions. A working-paper date, revision date and journal publication year are distinguished. A DOI for a journal version is not automatically the DOI of an earlier manuscript. Locators refer to the stated version and printed pages where specified. A metadata-only check does not verify a claim about a full-text conclusion. Every entry's source subsection narrows the provenance claim accordingly.

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Econ-486-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Econ-486

Computational cost and algorithm availability: sharp experimental limits and a scalable query benchmark

Problem ID: D91-482. Status: Unresolved; rigorous restricted results.

Target and information at the selection node

The target is a portable model of algorithm choice, response times, and representation effects, with computation cost distinguished from outcome preferences and repertoire restrictions. De Clippel and Rozen [dr], Section 7 of the February 2023 manuscript, call for further work on procedural and computational constraints. We give sharp identification results for an explicitly calibrated repertoire and solve a growing-input query family. Neither finite enumeration nor the family below constitutes a general theory of bounded rationality.

An algorithm is selected before the hidden input is drawn. Treatment $r$ publicly specifies its encoding, input distribution, reward schedule and available queries. For algorithm $j$, the analyst knows its ex ante payoff $v_{jr}$ and expected elementary operation count $c_{jr}<\infty$. Material utility is linear in reward and measured in the same units as $\kappa c_{jr}$. Programs terminate almost surely and always output a feasible choice. The individual chooses from a repertoire $R$ to maximize $v_{jr}-\kappa c_{jr}$. These informational assumptions prevent the selector from using the solution to a hidden instance to choose its own solution method.

Exact rationalization with a known repertoire

Suppose one individual is observed under several treatments, and calibrated action-time signatures identify the selected algorithm $j_r$. Indifference may be resolved in favor of any maximizer, using a treatment-specific tie selector included in the model.
Proposition (A sharp interval for operation cost): For a known finite repertoire $R$, the sharp set for $\kappa\geq0$ is \[ \mathcal K_R=\left\{\kappa\geq0: \kappa(c_{j_r r}-c_{kr})\leq v_{j_r r}-v_{kr} \quad\text{for all }r,\ k\in R\right\}. \tag{1} \] It is an interval, possibly empty, unbounded, or a singleton. With an unknown repertoire restricted to a specified collection $\mathfrak R$, the sharp set of pairs is \[ \{(R,\kappa):R\in\mathfrak R,\ j_r\in R\ \forall r, \ \kappa\in\mathcal K_R\}. \tag{2} \]
Proof: An observed algorithm is optimal precisely when its net payoff exceeds every available competitor's. Rearranging gives (1), proving necessity. Every inequality is a closed half-line in $\kappa$, or a constant compatibility check when counts are equal. Their intersection with $[0,\infty)$ is an interval of the stated kinds. Conversely, for any retained $\kappa$, each observed algorithm is a maximizer; the permitted tie selector can choose it, reproducing the data. For an unknown repertoire apply this argument to each $R$ containing every observed algorithm. It proves both necessity and attainability in (2). ∎

For clarity, if $c_{j_r r}>c_{kr}$, the corresponding ratio gives an upper bound on $\kappa$; if the inequality of counts is reversed, it gives a lower bound. Negative ratios or equal-count contradictions may empty the set. They must not be discarded by an informal "cost must be positive" argument.

Selected algorithms are not generally observed from choices alone. A sufficient calibration condition is as follows. Let $z$ range over finitely many observed action-time bins and let $H_r(z,j)$ be the known distribution of a bin conditional on selecting program $j$. If $H_r$ has linearly independent columns, program shares $w_r$ are identified from $P_r=H_rw_r$: if two share vectors fit, their difference is in the null space, which is zero. With individual programs deterministically distinguished by disjoint signatures, $j_r$ itself is observed. Full column rank identifies shares, not individual identities in a panel; intertemporal dependence would need its own measurement model.

An availability-cost confound that randomization does not remove

Consider two programs. The cheap program is always available, has payoff $v_0$ and count $c_0$. The expensive program, if available, improves expected payoff by $\Delta v>0$ and count by $\Delta c>0$. Let $t=\Delta v/\Delta c$ be an experimentally varied threshold. Availability and $\kappa$ can be dependent. Define the subprobability measure \[ \nu(B)=\Pr\{\text{expensive program available},\ \kappa\in B\}. \] Break ties in favor of the expensive program. Suppose calibrated action-time observations identify its selection probability $q(t)$.
Theorem (Sharp availability identification): For every tested threshold, $q(t)=\nu([0,t])$. At finitely many nonnegative thresholds $t_1<\cdots<t_m$, compatibility requires and is implied by \[ 0\leq q(t_1)\leq\cdots\leq q(t_m)\leq1. \] The sharp availability-probability set is $[q(t_m),1]$. Every value in this interval is attainable with finite operation costs. If thresholds can increase without bound and $\kappa<\infty$ almost surely among available individuals, availability is identified as $\lim_{t\to\infty}q(t)$.
Proof: The expensive program is chosen precisely when available and $\Delta v-\kappa\Delta c\geq0$, giving the subdistribution formula and monotonicity. Necessity of the availability lower bound follows because all selected individuals must have access.

For sufficiency place available mass $q(t_1)$ at cost zero. For $j\geq2$ place available mass $q(t_j)-q(t_{j-1})$ at any point in $(t_{j-1},t_j]$. For a proposed availability $h\in[q(t_m),1]$, put additional available mass $h-q(t_m)$ at $t_m+1$ and make the remaining mass $1-h$ unavailable. All costs are finite and all probabilities sum to one. This construction matches every observed share and proves sharpness. Finally $[0,t]$ increases to $[0,\infty)$, so continuity from below of measures gives the limiting statement. ∎

Even perfect finite experiments cannot distinguish "cannot use the program" from "can use it but has cost above all tested thresholds." If a representation treatment changes availability, interpreting its entire effect as a change in computation price is therefore unjustified. Similarly, if true utility is $s$ times the recorded reward, choices depend on $\kappa/s$; without a utility normalization the monetary cost parameter is not identified.

Time requires a second normalization. Under $T=t_0+\eta C+\zeta$, with unknown seconds per operation $\eta$, replacing $C$ by $aC$, $\eta$ by $\eta/a$, and $\kappa$ by $\kappa/a$ preserves both objective values and the complete time law for any $a>0$. An explicit machine model and a calibration task are needed to fix this scale.

A growing-input family solved over all adaptive queries

There are $n\geq2$ boxes, exactly one marked, with its position uniformly distributed. A query names one box and returns whether it is marked. Each query costs one elementary operation; terminal selection and bookkeeping are assigned zero additional cost in this explicit oracle model. The decision maker earns one unit for selecting the marked box and zero otherwise. It may select a box without querying it. No algorithm initially knows the marked position. We consider all almost-surely terminating adaptive algorithms, including randomization. Repeated queries, querying after success, or selecting a known unmarked box are weakly dominated and can be removed without decreasing payoff or increasing cost.
Theorem (Optimal computation and its cross-size prediction): For this query model, an optimal algorithm either makes no queries and guesses, or queries distinct boxes until it finds the mark or only one unqueried box remains. Write these programs as $A_0,A_F$. Then \[ v(A_0)=1/n,\quad C(A_0)=0,\qquad v(A_F)=1,\quad C(A_F)=\frac{(n-1)(n+2)}{2n}. \tag{3} \] The full procedure is optimal if and only if \[ \kappa\leq\frac{2}{n+2}, \tag{4} \] with both endpoint programs optimal at equality. Except for ties or zero-cost degeneracies, every optimal nonredundant program has an endpoint query budget.
Proof: Fix an algorithm's random seed. After every failed query, the remaining boxes are equiprobable; a deterministic algorithm consequently has one possible all-failure path, along which it queries a particular sequence of distinct boxes and stops at some count $q\in\{0,\ldots,n-1\}$. Finding the mark earlier stops the search. The final guess among remaining boxes succeeds for one further marked position. Thus its success probability is $(q+1)/n$. Query $k$ is made precisely when the first $k-1$ queried boxes did not contain the mark, an event of probability $(n-k+1)/n$. Hence \[ C_q=\sum_{k=1}^q\frac{n-k+1}{n} =q-\frac{q(q-1)}{2n}. \] Its objective equals \[ V_q=\frac{q+1}{n}-\kappa q+\frac{\kappa q(q-1)}{2n}. \] As a function of real $q$ in $[0,n-1]$, this is convex. A convex function on an interval cannot exceed the larger endpoint value: write an interior point as a convex combination of the endpoints and apply convexity. Therefore a best deterministic seed uses $q=0$ or $q=n-1$. A randomized algorithm is an average over seeds, so it cannot exceed the largest deterministic value. Substituting the endpoints gives (3). The difference is $(n-1)/n-\kappa(n-1)(n+2)/(2n)$, whose sign gives (4). When $\kappa>0$ and an interior integer exists, strict convexity makes its objective strictly lower than the endpoint chord. At $\kappa=0$ success increases strictly with $q$, so full search is optimal. ∎

Under $A_F$, the query count is $k$ with probability $1/n$ for $1\leq k\leq n-2$, and $n-1$ with probability $2/n$. The last probability combines finding the mark in the penultimate queried box and inferring the final unqueried box. Thus a calibrated operation-to-time map predicts a complete response-time distribution, not only its mean. The two programs have disjoint zero versus positive query counts when time measurement is exact.

With a stable population cost distribution and both programs available, the cross-size prediction is $\Pr(A_F\mid n)=F_\kappa(2/(n+2))$. This becomes a portable, falsifiable restriction across arbitrarily large $n$, rather than a separate fitted parameter at each size. If availability changes with $n$, it is replaced by the subdistribution in Theorem 2. Access to a representation that directly reveals the marked index in one query changes the repertoire's cost structure; it need not change rewards. The theorem's oracle operation count must not be equated with bit complexity of reading arbitrary long encodings. The finite input is encoded by a marked $n$-bit vector and an index-query interface; the unit-query assumption is a declared abstraction.

The remaining target is to infer a useful repertoire and time-error model in richer economic tasks, establish their invariance under representation changes, and validate predictions on new problem families. Our sharp confounds show why action and timing data cannot accomplish this without calibration and availability restrictions.

Completion Estimate

55%

This is a post hoc, heuristic estimate for the full catalogue target. The attempt obtains sharp cost-repertoire rationalization, identifies availability confounds, and solves all adaptive algorithms in a growing-size search family. A portable model for richer economic tasks still needs empirically calibrated algorithm signatures, time errors, stable preferences and repertoires, and prediction across new problem families.

References

Go to contribution →