Geodesic
On a class of optimization problems with no “effectively computable” solution
Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial methods. Part XXV, Tome 436 (2015), pp. 122-135 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

It is well known that large random structures may have nonrandom macroscopic properties. We give an example of nonrandom properties for a class of large optimization problems related to the computational problem $MAX\,FLS^=$ of calculating the maximum number of consistent equations in a given overdetermined system of linear equations. For this class we establish the following. There is no “efficiently computable” optimal strategy. When the size of a random instance of the optimization problem goes to infinity, the probability that the uniform mixed strategy is $\varepsilon$-optimal goes to one. Moreover, there is no “efficiently computable” strategy that is substantially better for each instance of the optimization problem. 
@article{ZNSL_2015_436_a6,
     author = {M. R. Gavrilovich and V. L. Kreps},
     title = {On a class of optimization problems with no {\textquotedblleft}effectively computable{\textquotedblright} solution},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {122--135},
     year = {2015},
     volume = {436},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2015_436_a6/}
}
TY  - JOUR
AU  - M. R. Gavrilovich
AU  - V. L. Kreps
TI  - On a class of optimization problems with no “effectively computable” solution
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2015
SP  - 122
EP  - 135
VL  - 436
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2015_436_a6/
LA  - ru
ID  - ZNSL_2015_436_a6
ER  - 
%0 Journal Article
%A M. R. Gavrilovich
%A V. L. Kreps
%T On a class of optimization problems with no “effectively computable” solution
%J Zapiski Nauchnykh Seminarov POMI
%D 2015
%P 122-135
%V 436
%U http://geodesic.mathdoc.fr/item/ZNSL_2015_436_a6/
%G ru
%F ZNSL_2015_436_a6
M. R. Gavrilovich; V. L. Kreps. On a class of optimization problems with no “effectively computable” solution. Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial methods. Part XXV, Tome 436 (2015), pp. 122-135. http://geodesic.mathdoc.fr/item/ZNSL_2015_436_a6/

[1] D. G. Kabe, “Laws of large numbers for random payoff games”, Indust. Math., 33 (1983), 73–86 | MR | Zbl

[2] J. Jonasson, “On the optimal strategy in a random game”, Electron. Comm. Probab., 9 (2004), 132–139 | DOI | MR | Zbl

[3] A. McLennan, J. Berg, “Asymptotic expected number of Nash equilibria of two-player normal form games”, Games Econom. Behav., 51:2 (2005), 264–295 | DOI | MR | Zbl

[4] A. Tanikawa, “On stability of the values of random zero-sum games”, Internat. J. Innov. Comput. Inform. Control, 7:1 (2011), 133–140 | MR

[5] F. Sandomirskiy, “On typical properties of large zero-sum games”, International Conference SING-GTM 2015, Abstracts, eds. L. Petrosjan, N. Zenkevich, St. Petersburg, 2015

[6] E. Amaldi, V. Kann, “The complexity and approximability of finding maximum feasible subsystems of linear relations”, Theoret. Comput. Sci., 147 (1995), 181–210 | DOI | MR | Zbl

[7] J. Hastad, “Some optimal inapproximability results”, Proceedings of 29th Annual Symposium on Theory of Computation, El Paso, 1997, 1–10 | MR

[8] Y. Luke, Mathematical Functions and Their Approximations, Academic Press, 1975 | MR | Zbl

[9] B. D. McKay, “On Littlewood's estimate for the binomial distribution”, Adv. in Appl. Probab., 21 (1989), 475–478 | DOI | MR | Zbl

[10] J. E. Littlewood, “On the probability in the tail of a binomial distribution”, Adv. in Appl. Probab., 1 (1969), 43–72 | DOI | MR | Zbl

[11] B. Bollobas, Random Graphs, 2nd edition, Cambridge Univ. Press, Cambridge, 2001 | MR | Zbl

[12] S. Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge Univ. Press, Cambridge, 2009 | MR | Zbl

[13] I. Dinur, The PCP theorem by gap amplification, Technical Report TR05-046, Revision 1, available from , ECCC, 2005, http://eccc.uni-trier.de/eccc-reports/2005/TR05-046/