Fixed-point computation¶

A represented search task asks for a point fixed by a declared self-map, or for a point meeting a stated residual or distance criterion, under an explicit input model and solution promise.

Version: v1 · 2026-10-17 · History
Domain-specific #: 14154
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Computational Complexity, Fixed Point Search → Computer Science & Software Engineering

Core Idea¶

Fixed-point computation is the search task of producing a point that meets a declared fixed-point criterion for an admissible represented self-map \(F:D\to D\). For an exact task, the answer \(x\in D\) satisfies \(F(x)=x\). An approximate task must say whether it accepts a small residual \(\lVert F(x)-x\rVert\), or instead requires \(x\) to lie close to some actual fixed point. Etessami and Yannakakis define these as different computational questions in their fixed-point framework.^[1]

The map, its carrier, the input representation, the acceptable-output test and the status of any existence promise define the problem before a solver is chosen. Brouwer's theorem guarantees a fixed point for a continuous self-map of a compact convex domain; that conditional existence theorem does not itself provide a procedure for finding one.^[1] An iteration, a triangulation method or a game-specific algorithm can address the task, but none is built into its identity.

Structural Signature¶

Represented self-map and carrier. An input instance determines a domain \(D\) and a map \(F:D\to D\). Without both, the expression \(F(x)=x\) has no typed search target. The game and economy constructions below use different simplex carriers.^[1]
Declared instance and promise class. The task states which represented maps are admissible and whether a solution is promised. Continuity on a compact convex carrier supplies a Brouwer promise in the cited families; it is not a universal requirement for every fixed-point search formulation.^[1]
Acceptable output and precision. Exact equality, weak residual and strong proximity to an actual fixed point are distinct acceptance relations. For an approximation, the norm and tolerance must be specified; the cited framework uses the infinity norm and a positive rational tolerance.^[1]
Effective input and access model. The problem states how the instance and map are supplied. The paper's payoff tables and algebraic circuits or formulas are concrete representations; a differently supplied oracle map cannot inherit their complexity results merely because it has the same equation.^[1]

These roles specify a computational search relation, not four required implementation steps. In particular, the promise role can declare that no general existence guarantee is supplied, and the access-model role does not require an algebraic circuit in every possible instance.

What It Is Not¶

A fixed point is a mathematical point satisfying \(F(x)=x\). Fixed-point computation adds a represented input family and an acceptable-output question. An existence theorem gives conditions under which such points occur; it is distinct from the task and from an algorithm that returns a point.^[1]

Nor is the task synonymous with repeated application \(x_{n+1}=F(x_n)\), Nash best-response improvement, or Scarf's triangulation algorithm. Etessami and Yannakakis discuss Scarf as one algorithmic approach and distinguish its weak almost-fixed-point target from closeness to an actual solution.^[1] A small game-regret value, a small map residual and distance to an actual Nash equilibrium must not be silently exchanged.

Scope of Application¶

The paper supplies two complete and unlike formal settings. For finite games, a payoff table induces Nash's continuous map on a product of mixed-strategy simplices; its exact fixed points are Nash equilibria. The paper constructs an algebraic representation and proves a FIXP-completeness result for the three-or-more-player Nash problem, not for every arbitrary map or every two-player formulation.^[1]

For an exchange economy, aggregate excess-demand functions induce a map on normalized commodity prices. Under the paper's continuity, degree-zero homogeneity and Walras-law assumptions, exact fixed prices satisfy its equilibrium condition. Proposition 19 concerns the narrower input family in which the excess-demand functions are given by algebraic circuits or formulas.^[1]

The same search vocabulary also distinguishes exact answers, weak residual approximations and strong proximity approximations for a declared map family. These are formal task variants with their own input and acceptance conditions, rather than additional empirical case studies. Other continuous, contractive, oracle or black-box families require their own promises and access model before a solver or complexity claim can be transferred.

Clarity¶

Ask first what is given, what counts as an answer, and what guarantees an answer exists? A point can be an exact mathematical fixed point even when no encoded search task has been stated. A continuous compact-convex self-map can have an existence guarantee even when no efficient construction is known.^[1]

For approximation, use two separate tests. A weak \(\varepsilon\)-fixed point has \(\lVert F(x)-x\rVert_\infty<\varepsilon\); a strong \(\varepsilon\)-approximation lies within \(\varepsilon\) in the infinity norm of some \(x^*\) with \(F(x^*)=x^*\). Etessami and Yannakakis state that the weak notion depends on the chosen fixed-point map, while strong proximity belongs to the underlying solution set; a weak answer can remain far from every actual fixed point.^[1]

Manages Complexity¶

A game and a market appear to ask unrelated questions: one seeks mutually stable mixed strategies, the other normalized prices meeting commodity-demand conditions. Writing each as a typed map plus an answer relation exposes a common search structure without erasing its different inputs. The game map uses nonnegative unilateral payoff gains; the market map uses nonnegative aggregate excess demands.^[1]

The compression has a limit. It does not turn payoff tables into demand functions, identify their economic interpretations, or allow the market result to be read off the game result without the paper's reductions. It also keeps representation and precision visible: the same abstract equality \(F(x)=x\) does not settle whether the map is given by a formula, circuit or another access model, nor whether a requested approximation is weak or strong.

Abstract Reasoning¶

To analyze a proposed fixed-point computation task, specify \(D\), \(F:D\to D\), the represented instance family and its input model. Then state whether exact equality, a residual bound or distance to an actual fixed point counts as success. If the task is called total, identify the premise that supplies existence. Only after those declarations can one ask which algorithm applies or what resources it needs.

The source allows an additional distinction between a task and one chosen encoding of it. A target search problem's solution set need not literally equal the fixed-point set of its constructed map: the paper permits a reduction that recovers original answers by projection and separable rational scaling or translation.^[1] That latitude does not erase the need to state the reduction and its answer correspondence.

Knowledge Transfer¶

Nash search and exchange-equilibrium search each fill the same four slots: a represented map and carrier, a conditional existence promise, an exact or specified approximate answer test, and an effective input form. Their substantive mappings differ. The first outputs a mixed-strategy profile from encoded game payoffs; the second outputs a normalized price vector from represented excess demands.^[1]

The transfer is literal because the original authors construct both fixed-point formulations. It does not license calling an unencoded stable state, a generic organizational equilibrium or a numerical iteration a fixed-point computation problem. A new setting must supply the map, input model and output relation again; a resemblance in the word Equilibrium is insufficient.

Examples¶

Finite-game Nash search¶

For a mixed-strategy profile \(x\), Nash's map increases a strategy coordinate by the positive part of that player's unilateral expected-payoff gain and renormalizes the player's strategy block. Etessami and Yannakakis give the formula in §2.3 and show that its exact fixed points are precisely Nash equilibria.^[1] Their Theorem 18 places the represented three-or-more-player problem in the FIXP-complete family; the theorem is about that declared input and answer problem, not a universal runtime for all games.^[1]

Mapped back: The product of strategy simplices and Nash map fill the carrier/self-map role; its compactness and continuity supply the existence promise; a Nash equilibrium is the exact acceptable output; rational payoff-table input and the constructed algebraic formula or circuit fill the representation role. If an approximation is requested, its weak or strong criterion must be separately stated.^[1]

Exchange-economy price search¶

Let \(g_i(p)\) be aggregate excess demand for commodity \(i\) at a normalized price vector \(p\). The paper's map on the price simplex is

[ F_i(p)=\frac{p_i+\max(0,g_i(p))}{1+\sum_k\max(0,g_k(p))}. ] ^[1]

Under the stated demand assumptions, its fixed points are the source's price equilibria: \(g_i(p)\leq 0\) for every commodity, with equality for each one whose price is positive.^[1] Proposition 19 establishes FIXP completeness when the excess-demand functions have the specified algebraic circuit or formula representation.^[1]

Mapped back: The normalized commodity-price simplex and displayed map fill the carrier/self-map role; continuity, degree-zero homogeneity and Walras' law bound this family's existence claim; the price-equilibrium condition is the exact output relation; supplied algebraic excess-demand functions fill the representation role for Proposition 19. These are source-authored formal constructions, not measured market outcomes.^[1]

Structural Tensions¶

The source establishes distinctions that affect which problem is being asked, but it does not establish one recurring two-sided design tradeoff for the general identity. Weak residual and strong distance are different output criteria; one is not automatically a cheap or acceptable substitute for the other. Existence and construction also belong to different logical layers.^[1]

The diagnostic is therefore which relation does this proposed answer satisfy, under which represented map and error convention? Treating these as a fabricated optimization tension would hide the central difference between tasks.

Structural–Framed Character¶

On the structural–framed spectrum, this is a formal search relation framed by computational representation and precision choices. Its structure is an encoded instance, a self-map, a promise status and an acceptable fixed-point output. Game payoffs and market excess demand supply different carriers and interpretations, while the answer relation stays formally comparable.^[1]

Evaluative weight: Choosing an error criterion and resource measure serves an analytical aim; the problem is not a moral ranking of solutions. Human practice: researchers choose encodings and tolerances, but an accepted instance's map and output test are formal. Institutional origin: the cited complexity paper articulates a studied family; no journal or institution makes \(F(x)=x\) true. Vocabulary travel: literal transfer requires another represented self-map search, not merely a phrase such as stable outcome. Import versus recognition: the test recognizes a computational problem when its full roles can be stated and imports a metaphor when they cannot.

Its character: a repeatable formal computation task whose applications remain bounded by the exact map, promise, representation and answer criterion supplied in each setting.

Structural Core vs. Domain Accent¶

The core is represented instance → typed self-map → declared promise status → exact or specified approximate fixed-point output. The map's carrier, input access and error convention remain load-bearing even when two applications share the equation \(F(x)=x\). Nash's payoff-gain formula and the exchange economy's excess-demand formula are different ways to fill that core, not a single universal solver.^[1]

The live Fixed Point concept names a point satisfying a relation, whereas this entry names a search task over encoded instances. A Computational Problem supplies input instances and acceptable outputs; this identity further specifies a represented self-map, promise status, and an exact or stated approximation relation. The two applications here do not by themselves establish a substrate-independent new Prime. Broader reach would require complete, unlike represented-search settings that retain these roles when game, market, and preferred algorithm vocabulary is removed. A shared equation or metaphor alone would not carry the task.

This entry is part of Function (Mapping).

The mathematical fixed point is the sought output, and an algorithm can be a method for finding it. Neither is automatically the whole computational problem. A function mapping supplies a map relation, but the represented search task additionally declares inputs, promise status and acceptable answers. Nash-equilibrium computation is one game-specific realization; the exchange-economy construction shows the identity is not exhausted by that one application.^[1]

Computational Problem is related through encoded instances and acceptable outputs. Fixed Point identifies the output object. The declared self-map is a strict internal Function Mapping: its domain, codomain and single-valued rule are needed to state every exact or approximate answer criterion. The whole search task can accept multiple answers even though the map assigns one value to each point. The map is therefore a constituent of the task, not a classification of the task itself.

Relationships to Other Abstractions¶

Current abstraction Fixed-point computation Domain-specific

Parents (1) — more general patterns this builds on

Fixed-point computation is part of Function (Mapping) Prime

The represented self-map is an identity-bearing Function Mapping within every fixed-point computation task.

Hierarchy path (1) — routes to 1 parentless root

Fixed-point computation → Function (Mapping)

Neighborhood in Abstraction Space¶

Fixed-point computation sits in a sparse region of the domain-specific corpus (77^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2721 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-17

Not to Be Confused With¶

A fixed-point theorem: a conditional existence result does not supply the represented search input or an algorithm.^[1]
A fixed point itself: \(F(x)=x\) classifies a point; a computation problem asks for an acceptable answer from an encoded instance.
One solver or iteration: an algorithm may attempt the task but does not define all valid tasks.
Weak versus strong approximation: small \(\lVert F(x)-x\rVert_\infty\) need not place \(x\) close to an actual fixed point.^[1]
A generic FIXP label: the cited completeness theorems concern the stated algebraic representation classes, not arbitrary continuous or oracle-supplied maps.^[1]
An empirical equilibrium claim: the two examples here are source-authored formal reductions, not observed game play or measured market clearing.

References¶

[1] Kousha Etessami and Mihalis Yannakakis (2010), On the Complexity of Nash Equilibria and Other Fixed Points, SIAM Journal on Computing 39(6), 2531–2597. Full original author manuscript directly inspected; manuscript §2.1 p.7 defines encoded search problems, §2.3 pp.11–12 gives Nash and exchange maps and the reduction boundary, p.15 distinguishes strong and weak approximations, Theorem 18 pp.40–41 bounds the Nash result, and Proposition 19 pp.45–46 bounds the exchange result. Manuscript printed pages and PDF page indexes differ by one. The publisher article record confirms journal metadata; its abstract alone is not the basis for the detailed claims. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x ↩y ↩z ↩27 ↩28 ↩29