Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPandoras Box Problem with Order Constraints
144
0
0.0
(
0
)
Added by
Federico Fusco
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The Pandoras Box Problem, originally formalized by Weitzman in 1979, models selection from set of random, alternative options, when evaluation is costly. This includes, for example, the problem of hiring a skilled worker, where only one hire can be made, but the evaluation of each candidate is an expensive procedure. Weitzman showed that the Pandoras Box Problem admits an elegant, simple solution, where the options are considered in decreasing order of reservation value,i.e., the value that reduces to zero the expected marginal gain for opening the box. We study for the first time this problem when order - or precedence - constraints are imposed between the boxes. We show that, despite the difficulty of defining reservation values for the boxes which take into account both in-depth and in-breath exploration of the various options, greedy optimal strategies exist and can be efficiently computed for tree-like order constraints. We also prove that finding approximately optimal adaptive search strategies is NP-hard when certain matroid constraints are used to further restrict the set of boxes which may be opened, or when the order constraints are given as reachability constraints on a DAG. We complement the above result by giving approximate adaptive search strategies based on a connection between optimal adaptive strategies and non-adaptive strategies with bounded adaptivity gap for a carefully relaxed version of the problem.
rate research
Read More
Martin Weitzmans Pandoras problem furnishes the mathematical basis for optimal search theory in economics. Nearly 40 years later, Laura Doval introduced a version of the problem in which the searcher is not obligated to pay the cost of inspecting an alternatives value before selecting it. Unlike the original Pandoras problem, the version with nonobligatory inspection cannot be solved optimally by any simple ranking-based policy, and it is unknown whether there exists any polynomial-time algorithm to compute the optimal policy. This motivates the study of approximately optimal policies that are simple and computationally efficient. In this work we provide the first non-trivial approximation guarantees for this problem. We introduce a family of committing policies such that it is computationally easy to find and implement the optimal committing policy. We prove that the optimal committing policy is guaranteed to approximate the fully optimal policy within a $1-frac1e = 0.63ldots$ factor, and for the special case of two boxes we improve this factor to 4/5 and show that this approximation is tight for the class of committing policies.
In the secretary problem we are faced with an online sequence of elements with values. Upon seeing an element we have to make an irrevocable take-it-or-leave-it decision. The goal is to maximize the probability of picking the element of maximum value. The most classic version of the problem is that in which the elements arrive in random order and their values are arbitrary. However, by varying the available information, new interesting problems arise. Also the case in which the arrival order is adversarial instead of random leads to interesting variants that have been considered in the literature. In this paper we study both the random order and adversarial order secretary problems with an additional twist. The values are arbitrary, but before starting the online sequence we independently sample each element with a fixed probability $p$. The sampled elements become our information or history set and the game is played over the remaining elements. We call these problems the random order secretary problem with $p$-sampling (ROS$p$ for short) and the adversarial order secretary problem with $p$-sampling (AOS$p$ for short). Our main result is to obtain best possible algorithms for both problems and all values of $p$. As $p$ grows to 1 the obtained guarantees converge to the optimal guarantees in the full information case. In the adversarial order setting, the best possible algorithm turns out to be a simple fixed threshold algorithm in which the optimal threshold is a function of $p$ only. In the random order setting we prove that the best possible algorithm is characterized by a fixed sequence of time thresholds, dictating at which point in time we should start accepting a value that is both a maximum of the online sequence and has a given ranking within the sampled elements.
In this note we study the greedy algorithm for combinatorial auctions with submodular bidders. It is well known that this algorithm provides an approximation ratio of $2$ for every order of the items. We show that if the valuations are vertex cover functions and the order is random then the expected approximation ratio imrpoves to $frac 7 4$.
We propose a truthful-in-expectation, $(1-1/e)$-approximation mechanism for a strategic variant of the generalized assignment problem (GAP). In GAP, a set of items has to be optimally assigned to a set of bins without exceeding the capacity of any singular bin. In the strategic variant of the problem we study, values for assigning items to bins are the private information of bidders and the mechanism should provide bidders with incentives to truthfully report their values. The approximation ratio of the mechanism is a significant improvement over the approximation ratio of the existing truthful mechanism for GAP. The proposed mechanism comprises a novel convex optimization program as the allocation rule as well as an appropriate payment rule. To implement the convex program in polynomial time, we propose a fractional local search algorithm which approximates the optimal solution within an arbitrarily small error leading to an approximately truthful-in-expectation mechanism. The presented algorithm improves upon the existing optimization algorithms for GAP in terms of simplicity and runtime while the approximation ratio closely matches the best approximation ratio given for GAP when all inputs are publicly known.
In many settings, people exhibit behavior that is inconsistent across time --- we allocate a block of time to get work done and then procrastinate, or put effort into a project and then later fail to complete it. An active line of research in behavioral economics and related fields has developed and analyzed models for this type of time-inconsistent behavior. Here we propose a graph-theoretic model of tasks and goals, in which dependencies among actions are represented by a directed graph, and a time-inconsistent agent constructs a path through this graph. We first show how instances of this path-finding problem on different input graphs can reconstruct a wide range of qualitative phenomena observed in the literature on time-inconsistency, including procrastination, abandonment of long-range tasks, and the benefits of reduced sets of choices. We then explore a set of analyses that quantify over the set of all graphs; among other results, we find that in any graph, there can be only polynomially many distinct forms of time-inconsistent behavior; and any graph in which a time-inconsistent agent incurs significantly more cost than an optimal agent must contain a large procrastination structure as a minor. Finally, we use this graph-theoretic model to explore ways in which tasks can be designed to help motivate agents to reach designated goals.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
