Take Action

Home | Faculty & Research Overview | Research

Research Details

Randomness Does Not Break the Curse of Dimensionality Unless the Dynamic Program Is Trivial

Abstract

Rust (1997) developed a randomized algorithm that can solve discrete-choice dynamic programs to any degree of accuracy in polynomial time, under some assumptions. Rust believed these assumptions to be relatively permissive, and thus suggested that randomness can be a powerful remedy against the curse of dimensionality of dynamic programs. However, I show that Rust's assumptions rule out all but a trivial class of dynamic programs. I argue, therefore, that we should not consider randomness as a countermeasure against the curse of dimensionality.

Type

Working Paper

Author(s)

Robert Bray

Date Published

2020

Citations

Bray, Robert. 2020. Randomness Does Not Break the Curse of Dimensionality Unless the Dynamic Program Is Trivial.

KELLOGG INSIGHT

Explore leading research and ideas

Find articles, podcast episodes, and videos that spark ideas in lifelong learners, and inspire those looking to advance in their careers.
learn more

COURSE CATALOG

Review Courses & Schedules

Access information about specific courses and their schedules by viewing the interactive course scheduler tool.
LEARN MORE

DEGREE PROGRAMS

Discover the path to your goals

Whether you choose our Full-Time, Part-Time or Executive MBA program, you’ll enjoy the same unparalleled education, exceptional faculty and distinctive culture.
learn more

Take Action