Informs Annual Meeting Phoenix 2018

INFORMS Phoenix – 2018

TB19

characterization (here we give structural properties, but it is not closed-form). 2 - Optimal Mechanism Design with Risk-loving Agents Emmanouil Pountourakis, University of Texas at Austin, Austin, TX, United States, Evdokia Velinova Nikolova, Ger Yang One of the most celebrated results in mechanism design is Myerson’s characterization of the revenue optimal auction. However, this result relies heavily on the assumption that buyers are indifferent to risk. In this paper we study the case where the buyers are risk-loving, i.e. they prefer gambling to deterministic rewards We characterize the optimal auction and show that randomization can be used to extract more revenue than when buyers are risk- neutral. Most importantly, we show that the optimal auction is simple: the optimal revenue can be extracted using a randomized take-it-or-leave-it price for a single buyer and using a loser-pay auction, a variant of the all-pay auction, for multiple buyers. 3 - Algorithmic Delegation Ali Khodabakhsh, University of Texas at Austin, Austin, TX, United States, Emmanouil Pountourakis, Sam Taggart We initiate the study of delegation from an algorithmic perspective. An uninformed principal must consult an informed agent to make a decision over which both agent and principal have preferences that depend on the state of the world. The principal may commit to a mechanism, mapping agent’s reports to actions. We derive measures of alignment and conflict between the principal and agent for each action in each state, and show that when alignment is insensitive to the state, it is optimal for the principal to select an action without consulting the agent. When conflict is insensitive to the state, it becomes approximately optimal for the principal to adopt a form of threshold policy. 4 - On Low-rank (quasi-convex) Minimization for a Wide Class of Combinatorial Problems Orestis Papadigenopoulos, University of Texas at Austin, Austin, TX, 78705, United States, Swati Gupta, Evdokia Velinova Nikolova The problem of non-linear, low-rank discrete minimization has been studied under the following similar assumptions: (a) the optimal solution lies on the Pareto-optimal front of a corresponding multi-objective optimization problem, or (b) the objective function is quasi-concave. In our attempt to relax these assumptions, we study minimization of quasi-convex objectives over combinatorial sets and propose efficient approximation schemes. Note that our problem is already NP-hard, even for the case where the rank of the quasi-convex objective is one, using a simple reduction from the exact spanning tree problem. n TB21 North Bldg 129B Topics in Revenue Management and Assortment Optimization Sponsored: Revenue Management & Pricing Sponsored Session Chair: Pelin Pekgun, University of South Carolina, Columbia, SC, 29205, United States Co-Chair: Ovunc Yilmaz, University of Notre Dame, South Bend, IN, 46617, United States 1 - Multi-location Assortment Optimization under Capacity Constraints Alper Sen, Bilkent University, Department of Industrial Engineering, Bilkent, Ankara, 06800, Turkey, Basak Bebitoglu, Philip Kaminsky We study the assortment optimization problem of a retailer which uses multiple DCs to fulfill orders. Each DC can carry up to a pre-specified number of products and is responsible for a region whose customers’ choice is governed by an MNL model. A DC can fulfill demand from another region, but at an additional cost. The retailer’s problem is to determine the products carried in each DC and the assortment in each region so as to maximize its expected profit. We show that the problem is NP-complete and develop a conic MIP formulation. Numerical experiments show that large instances can be solved optimally using this approach. Finally, we study the effect of various factors on profits and assortment structure. 2 - Finite-horizon Approximate Linear Programs for an Infinite-horizon Revenue Management Problem Fan You, University of Colorado-Boulder, 995 Regent Drive, Boulder, CO, 80302, United States, Thomas Vossen, Dan Zhang We consider a rolling-horizon revenue management problem that is formulated as an infinite-horizon discounted cost Markov decision process. We propose a solution strategy based on approximate linear programming. Under affine and finite-horizon approximations, we show that the approximate linear programming formulations admit compact representations and therefore can be solved efficiently. The solutions provide revenue bounds and can be used to construct heuristic control policies. We conduct numerical study to evaluate bound and policy performance.

n TB19 North Bldg 128B New Directions in Pricing and Revenue Management Sponsored: Revenue Management & Pricing Sponsored Session Chair: Georgia Perakis, Massachusetts Institute of Technology, Cambridge, MA, 02142-1347, United States 1 - Estimating Customer Trends to Target Promotions Lennart Baardman, Massachusetts Institute of Technology, Cambridge, MA, 02139, United States, Setareh Borjian Boroujeni, Tamar Cohen, Kiran V. Panchamgam, Georgia Perakis Detecting trends in fashion can help retailers determine effective personalized promotion plans more easily. Social media data is valuable in understanding these trends, but it is often unavailable. We introduce a personalized demand model that captures customer trends from transaction data instead. We base our efficient estimation method on instrumental variables, which allows us to draw causal inference on the effects that targeted promotions have. The promotion targeting problem is NP-hard to solve, so we develop an efficient and provably-good greedy approach. Finally, with real fashion retail data, we estimate our customer trend model and test the promotion targeting algorithm. 2 - Dynamic Pricing for Unknown Latent Class Models Divya Singhvi, MIT, 235 Albany Street, 5010 A, Cambridge, MA, 02139, United States, Pavithra Harsha, Georgia Perakis We consider the problem of dynamic pricing when customers belong to unknown latent classes. Specifically, we consider a demand model in which a customer’s demand response depends on her class. Neither the class, nor the demand functions of the customer class is known. We construct a dynamic pricing policy that is asymptotically optimal and show that it performs considerably better than other benchmark policies for the latent class case. 3 - Dynamic Learning and Optimization for Online Advertising Portfolios Under Periodic Budgets Elaheh Fata, Massachusetts Institute of Technology, Cambridge, MA, 02139, United States, Lennart Baardman, Georgia Perakis, Abhishek Pani The tremendous growth in online personalized data and ad channels enables publishers to auction off targeted advertising slots to advertisers. Everyday, advertisers bid on a portfolio of targets to maximize advertising revenue within their budget constraint. As the advertiser needs to learn the value of targets, we use an exploration-exploitation framework to model this online advertising portfolio optimization problem. We solve this problem using an optimistic-robust learning (ORL) algorithm based on UCB algorithms and robust optimization. Theoretically, we prove its expected regret is bounded, and computationally, we show its powerful performance on real-world data. 4 - Markdown Policies for Demand Learning and Strategic Customer Behavior N. Bora Keskin, Duke University, Fuqua School of Business, 100 Fuqua Drive, Durham, NC, 27708-0120, United States, Hongfan Chen We consider a firm selling a product to a finite population of myopic and strategic customers with heterogeneous valuations. The firm faces uncertainty about the market size and how strategic customers are. We develop guidelines for designing asymptotically optimal markdown policies for demand learning in the presence of strategic customers. n TB20 North Bldg 129A Revenue Maximization Beyond Traditional Models Sponsored: Revenue Management & Pricing Sponsored Session Chair: Emmanouil Pountourakis, University of Texas at Austin, Austin, TX, United States 1 - Selling Partially-ordered Items: Exploring the Space Between Single- and Multi-dimensional Mechanism Design Kira Goldner, University of Washington, Box 352350, Seattle, WA, 98195, United States With respect to optimal seller revenue, the single-dimensional (i.e. one item) setting and multi-dimensional (i.e. heterogeneous items) setting sit at extreme ends of a spectrum: from simple and fully characterized (single-dimensional) to complex and nebulous (multi-dimensional). In this paper, we study where various bundles of items are for sale, and a buyer is single-minded for some bundle (i.e. is satisfied if and only if he receives a superset of said bundle). We prove that this setting’s optimal mechanism sits between the above extremes, both in menu size (here it is unbounded, but always finite) and in the known

282