On a Class of Optimization Problems with No “Effectively Computable” Solution

Misha Gavrilovich () and Victoriya Kreps ()
Additional contact information
Misha Gavrilovich: National Research University Higher School of Economics
Victoriya Kreps: National Research University Higher School of Economics

HSE Working papers from National Research University Higher School of Economics

Abstract: It is well-known that large random structures may have non-random macroscopic properties. We give an example of non-random properties for a class of large optimization problems related to the computational problem MAXFLS^= of calculating the maximal number of consistent equations in a given overdetermined system of linear equations. A problem of this kind is faced by a decision maker (an Agent) choosing the means to protect a house from natural disasters. For this class we establish the following. There is no “efficiently computable” optimal strategy for the Agent. When the size of a random instance of the optimization problem goes to infinity the probability that the uniform mixed strategy of the Agent is ? optimal goes to one. Moreover, there is no “efficiently computable” strategy for the Agent which is substantially better for each instance of the optimization problem

Keywords: optimization; concentration of measure; probabilistically checkable proofs (search for similar items in EconPapers)
JEL-codes: C61 (search for similar items in EconPapers)
Pages: 13 pages
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations:

Published in WP BRP Series: Economics / EC, November 2015, pages 1-13

Downloads: (external link)
http://www.hse.ru/data/2015/11/20/1081927635/112EC2015.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hig:wpaper:112/ec/2015

Access Statistics for this paper

More papers in HSE Working papers from National Research University Higher School of Economics
Bibliographic data for series maintained by Shamil Abdulaev () and Shamil Abdulaev ().