editor
178
edits
Changes
From Theory
Created page with "== Title == The power of stochastic modeling, beating theoretically proven lower bounds of optimization problems == Speaker == Saeidreza Seddighin == Abstract == Several op..."
== Title ==
The power of stochastic modeling, beating theoretically proven lower bounds of optimization problems
== Speaker ==
Saeidreza Seddighin
== Abstract ==
Several optimization problems have been studied in the
literature of game theory, online algorithms, mechanism design, and
economics, most of which are motivated by their vast applications in real
world or their applicability to other theoretical problems. In all of these
problems, the goal is to design either an algorithm or a mechanism that
guarantees the highest performance in the worst case scenarios. In many
cases, this is achieved by taking a significant hit on the average outcome
of the algorithm. In real world, however, adversarial scenarios are not
always the case. Therefore, a new line of research is necessary to study
these optimization problems with a more realistic setting. An effective and
fruitful means to rule out unlikely scenarios is limiting the uncertain
parameters of the problem by adding stochastic assumptions. This has been
applied to many problems in different areas with names such as ``Bayesian
setting", ``Prophet inequality", etc.
In this work we revisit well-known and classical problems in game theory,
mechanism design, social networks, economics, and online algorithms in
stochastic settings. Some of these problems have been posed in previous
works and were left as open questions. For all of these problems we propose
mechanisms/algorithms that are almost optimal with respect to the stochastic
inputs, i.e., no other mechanism/algorithm can achieve a relatively higher
performance unless either a constraint of the problem is violated or a
widely believed conjecture fails. We show that we can beat the theoretically
proved lower bounds for general problems by considering the stochastic
inputs. As an example, the currently known lower bound on the competitive
ratio of the the $k$-server problem is $k$, whereas we prove logarithmically
small (and even constant in some cases) upper bounds on the approximation
ratio of our algorithm for the stochastic version of the problem.
The power of stochastic modeling, beating theoretically proven lower bounds of optimization problems
== Speaker ==
Saeidreza Seddighin
== Abstract ==
Several optimization problems have been studied in the
literature of game theory, online algorithms, mechanism design, and
economics, most of which are motivated by their vast applications in real
world or their applicability to other theoretical problems. In all of these
problems, the goal is to design either an algorithm or a mechanism that
guarantees the highest performance in the worst case scenarios. In many
cases, this is achieved by taking a significant hit on the average outcome
of the algorithm. In real world, however, adversarial scenarios are not
always the case. Therefore, a new line of research is necessary to study
these optimization problems with a more realistic setting. An effective and
fruitful means to rule out unlikely scenarios is limiting the uncertain
parameters of the problem by adding stochastic assumptions. This has been
applied to many problems in different areas with names such as ``Bayesian
setting", ``Prophet inequality", etc.
In this work we revisit well-known and classical problems in game theory,
mechanism design, social networks, economics, and online algorithms in
stochastic settings. Some of these problems have been posed in previous
works and were left as open questions. For all of these problems we propose
mechanisms/algorithms that are almost optimal with respect to the stochastic
inputs, i.e., no other mechanism/algorithm can achieve a relatively higher
performance unless either a constraint of the problem is violated or a
widely believed conjecture fails. We show that we can beat the theoretically
proved lower bounds for general problems by considering the stochastic
inputs. As an example, the currently known lower bound on the competitive
ratio of the the $k$-server problem is $k$, whereas we prove logarithmically
small (and even constant in some cases) upper bounds on the approximation
ratio of our algorithm for the stochastic version of the problem.
