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.
Core Idea¶
Fixed-point computation asks for an acceptable point for a represented self-map \(F:D\to D\), with an exact answer obeying \(F(x)=x\).[^ref-f78d1c518983] An approximate task must say whether it accepts a small residual \(\lVert F(x)-x\rVert\) or a point near an actual fixed point; these tests differ.[^ref-f78d1c518983] The input representation, carrier, answer test and existence promise define the task before a solver is chosen; a continuous self-map on a compact convex carrier has a Brouwer existence guarantee, but that theorem alone does not supply a solver.[^ref-f78d1c518983]
Scope of Application¶
Two source constructions in unlike formal settings support exact tasks and the indicated derived approximation variants:
- Finite-game exact search: Nash's payoff-derived map on mixed-strategy profiles has equilibria as fixed points, with FIXP completeness scoped to three or more players.[^ref-f78d1c518983]
- Finite-game weak approximation: The same map permits a specified small residual without guaranteeing closeness to an equilibrium.[^ref-f78d1c518983]
- Exchange-economy exact search: The excess-demand price map has equilibrium fixed points under the paper's stated assumptions.[^ref-f78d1c518983]
- Exchange-economy strong approximation: Distance to an actual fixed price gives a derived task under Proposition 19's circuit/formula input limits.[^ref-f78d1c518983]
Clarity¶
A fixed point is a possible answer object, while computation is the represented task of producing an answer. State \(D\), \(F\), the input model, the answer test and any existence promise. A weak residual can be small while the point remains far from every actual fixed point; a strong approximation is defined by distance to one.[^ref-f78d1c518983] An iteration or triangulation algorithm may solve a declared task but is not part of its identity.
Manages Complexity¶
The same task format organizes a payoff-derived game map and an excess-demand price map without identifying their inputs or economic meanings. It also keeps approximation and representation visible: an exact equality does not tell us whether \(F\) is given by a payoff table, algebraic circuit, formula or a differently declared oracle, and a complexity result for one represented family does not automatically cover another.[^ref-f78d1c518983]
Abstract Reasoning¶
First determine whether the proposed instance actually supplies a self-map on a declared carrier. Then specify which outputs count: exact equality, weak residual or strong proximity. Finally identify the input/access model and the premise for any asserted existence guarantee. If the map, norm, tolerance or promise changes, the resulting search question may change even when the phrase fixed point remains the same.[^ref-f78d1c518983]
Knowledge Transfer¶
The necessary internal Function Mapping assigns one \(F(x)\) to each admissible \(x\); the whole search task may admit several acceptable points. The map is therefore a strict constituent, not the whole task's type. Nash search uses a mixed-strategy map, while the exchange case uses a price-simplex map.[^ref-f78d1c518983] Fixed Point names a possible output, and an algorithm names a way to seek it. Neither replaces the declared representation and success condition.
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 (77th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (2721 abstractions)
Nearest neighbors
- Ahlswede–Daykin inequality — 0.83
- Complete lattice — 0.83
- Join and meet — 0.83
- Semilinear map — 0.83
- Mazur's lemma — 0.82
Computed from structural-signature embeddings · 2026-10-17
References¶
[^ref-f78d1c518983]: 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.