A decisionmaker faces n alternatives, each of which represents a potential reward. After investing costly resources into investigating the alternatives, the decisionmaker selects one (or more generally a feasible subset), and receives the associated reward(s). We model each alternative as a Markov Search Process (MSP), a type of undiscounted Markov Decision Process on a finite acyclic graph, and call this problem Combinatorial Markov Search (CMS). CMS broadly generalizes recent NP-hard problems of interest such as Pandora’s Box with nonobligatory inspection. Despite the seemingly adaptive and interactive nature of the problem, we construct online algorithms for CMS that explore each alternative sequentially, either selecting or discarding it before moving to the next. We first show that any ex-ante prophet inequality can be converted into an (inefficient) online algorithm for CMS with the same approximation guarantee. Then, for any matroid feasibility constraint, we construct a polynomial-time (1/2−є)-approximation algorithm for CMS. Our construction also implies incentive-compatible mechanisms with constant Price of Anarchy for a strategic version of the problem that generalizes auctions with inspection costs.

This paper derives polynomial-time approximation schemes for several NP-hard stochastic optimization problems from the algorithmic mechanism design and operations research literatures. The problems we consider involve a principal or seller optimizing with respect to a subsequent choice by an agent or buyer. These include posted pricing for a unit-demand buyer with independent values (Chawla et al. [19], Cai and Daskalakis [16]), assortment optimization with independent utilities (Talluri and van Ryzin [53]), and delegated choice (Khodabakhsh et al. [36]). Our results advance the state of the art for each of these problems. For unit-demand pricing with discrete distributions, our multiplicative PTAS improves on the additive PTAS of Cai and Daskalakis [16], and we additionally give a PTAS for the unbounded regular case, improving on the latter paper’s QPTAS. For assortment optimization, no constant approximation was previously known. For delegated choice, we improve on both the 3 -approximation for the case with no outside option and the super-constant-approximation with an outside option.A key technical insight driving our results is an economically meaningful property we term utility alignment. Informally, a problem is utility aligned if, at optimality, the principal derives most of their utility from realizations where the agent’s utility is also high. Utility alignment allows the algorithm designer to focus on maximizing performance on realizations with high agent utility, which is often an algorithmically simpler task. We prove utility alignment results for all the problems mentioned above, including strong results for unit-demand pricing and delegation, as well as a weaker but very broad guarantee that holds for many other problems under very mild conditions.

We present the Loom Pedals, an open-source hardware/software interface for enhancing a weaver’s ability to create on-the-fly, improvised designs in Jacquard weaving. Learning from traditional handweaving and our own weaving experiences, we describe our process of designing, implementing, and using the prototype Loom Pedals system with a TC2 Digital Jacquard loom. The Loom Pedals include a set of modular, reconfigurable foot pedals which can be mapped to parametric Operations that generate and transform digital woven designs. Our novel interface integrates design and loom control, providing a customizable workflow for playful, improvisational Jacquard weaving. We conducted a formative evaluation of the prototype through autobiographical methods and collaboratively developed future Loom Pedals features. We contribute our prototype, design process, and conceptual reflections on weaving as a human-machine dialog between a weaver, the loom, and many other agents.