Informs Annual Meeting Phoenix 2018

INFORMS Phoenix – 2018

SB72

4 - The CCP Selector: Best Subset Selection for Sparse Ridge Regression from Chance-Constrained Programming Weijun Xie, Virginia Tech, Blacksburg, VA, 24060, United States, Xinwei Deng This paper studies sparse ridge regression problem. This paper first derives a novel mixed integer conic (MISOC) reformulation and proves that its continuous relaxation is equivalent to the convex integer formulation proposed by literature. Based upon these two formulations, we study two approximation algorithms- greedy and randomized rounding. We develop efficient implementable procedures for both algorithms and prove that under mild conditions, these two approaches yield near-optimal solutions. We numerically compare these two algorithms with the others proposed from literature and show that greedy approach consistently outperforms the other by correctly identifying more features. Nicholson Student Paper Competition I Emerging Topic: Nicholson Student Paper Prize Emerging Topic Session Chair: John Hasenbein, University of Texas-Austin, 1 University Station Stop C2200, Department of Mechanical Engineering, Austin, TX, 78712-0292, United States 1 - Learning Optimal Online Advertising Portfolios with Periodic Budgets Lennart Baardman, MIT, Operations Research Center, 77 Mass Ave, Bldg E40-130, Cambridge, MA, 02139-4307, United States, Elaheh Fata, Abhishek Pani, Georgia Perakis We study a novel multi-armed bandit (MAB) problem with periodic budgets and intermittent feedback on rewards and costs. At the beginning of each time period an agent needs to determine which set of arms to pull to maximize the expected total reward, while maintaining a total cost that is within the budget. As the expected revenues and costs of arms are unknown, the agent has to use each period’s budget to both explore the values of arms as well as exploit the most e cient set of arms. This model captures the practical setting where advertisers, in each period, have a periodic advertising budget that is used to bid on a portfolio of targets (e.g., search ads or social ads) to maximize the advertising revenue over that period of time. Over time, the e ciency of the picked targets is revealed and the advertiser revises the portfolio accordingly. This is in contrast to deciding which target to bid on one at a time, which is considered in the budget-limited MAB literature. In this paper, we formulate the MAB problem with periodic budgets, that is a hard to solve problem; therefore, we relax the oracle policy to be able to consider a greedy approximation algorithm for it. We propose an optimistic-robust learning (ORL) algorithm that achieves a bounded total expected regret with respect to this oracle, and show its computational performance. 2 - Sustaining Rainforests and Smallholders by Eliminating Payment- delay in a Commodity Supply Chain – It Takes a Village Joann de Zegher, Stanford University, Via Ortega 473, Suite 226, Stanford, CA, 94305, United States Millions of poor smallholder farmers produce global commodities, often through illegal de forestation. Multinational commodity buyers have committed to halt illegal deforestation and improve farmers’ livelihoods in their supply chains. We propose a profitable way to do so, mo tivated by field research in Indonesia’s palm oil industry. Currently, farmers su er from delay in payment by processors, and buyers expensively attempt to avoid sourcing from illegally deforested land by monitoring individual farmers. Instead, we propose that buyers reward all farmers in a village by eliminating payment-delay if no production occurs on illegally- deforested land in the village. Using field data, dynamic programming and game theory, we show how eliminating payment-delay improves productivity and profitability for farmers, processors and buyers, and how village-level incentives best halt illegal deforestation. 3 - Hidden Integrality of SDP Relaxation for Sub-Gaussian Mixture Models Yingjie Fei, Cornell University, Ithaca, NY, United States, Yudong Chen We consider the problem of estimating the discrete clustering structures under Sub-Gaussian Mixture Models. Our main results establish a hidden integrality property of a semidefinite programming (SDP) relaxation for this problem: while the optimal solutions to the SDP are not integer-valued in general, their estimation error can be upper bounded in terms of the error of an idealized integer program. The error of the integer program, and hence that of the SDP, are further shown to decay exponentially in the signal-to-noise ratio. To the best of our knowledge, this is the first exponentially decaying error bound for convex relaxations of mixture models, and our results reveal the “global-to-local n SB72 West Bldg 211A

mechanism that drives the performance of the SDP. A corollary of our results shows that in certain regimes the SDP solutions are in fact integral and exact, improving on existing exact recovery results for convex relaxations. More generally, our results establish sufficient conditions for the SDP to correctly recover the cluster memberships of (1-$\delta$) fraction of the points for any $\delta\in(0,1)$. As a special case, we show that under the $d$-dimensional Stochastic Ball Model, SDP achieves non-trivial (sometimes exact) recovery when the center separation is as small as $\sqrt{1/d}$, which complements previous exact recovery results that require constant separation. 4- Implementing the Lexicographic Maxmin Bargaining Solution Anilesh Krishnaswamy, Stanford University, Stanford, CA, 94305, United States, Ashish Goel There has been much work on exhibiting mechanisms that implement various bargaining solutions, in particular the Kalai-Smorodinsky solution [Moulin, 1984] and the Nash Bargain ing solution. Another well-known and axiomatically well- studied solution is the lexicographic maxmin solution. However, there is no mechanism known for its implementation. To fill this gap, we construct a mechanism that implements the lexicographic maxmin solution as the unique subgame perfect equilibrium outcome in the n-player setting. As is standard in the literature on implementation of bargaining solutions, we use the assumption that any player can grab the entire surplus. Our mechanism consists of a binary game tree, with each node corresponding to a subgame where the players are allowed to choose between two outcomes. We characterize novel combinatorial properties of the lexicographic maxmin solution which are crucial to the design of our mechanism. JFIG Paper Competition I Sponsored: Junior Faculty JFIG Sponsored Session Chair: Oleg Prokopyev, University of Pittsburgh, 1031 Benedum Hall, Pittsburgh, PA, 15261, United States Co-Chair: Fatma Kilinc Karzan, Carnegie Mellon University, Pittsburgh, PA, 15217, United States 1- JFIG Paper Competition Oleg Prokopyev, University of Pittsburgh, Pittsburgh, PA, United States The 2018 JFIG paper competition features paper submissions from a diverse array of talented junior faculty members. The prize committee evaluated submissions based on the importance of the topic, appropriateness of the approach, and significance of the contribution. After careful review, the prize committee selected a group of finalists to present their research in one of the two JFIG sessions. For information on the finalists and their papers, please refer to the online program.. n SB74 West Bldg 212A MCDM Junior Researcher Best Paper Award Finalists Sponsored: Multiple Criteria Decision Making Sponsored Session Chair: Margaret M. Wiecek, Clemson University, Clemson, SC, 29634-1907, United States 1 - From Stakeholder Analysis to Cognitive Mapping and Multi- Attribute Value Theory: An Integrated Approach for Policy Support Valentina Ferretti, London School of Economics and Political Science, Houghton Street| London | WC2A 2AE, London, United Kingdom This study proposes and tests a decision support process that integrates three different tools to structure and solve complex decision problems. First, stakeholders’ analysis is deployed to identify the key perspectives involved in the decision process. Second, cognitive mapping is used to facilitate participation of the key stakeholders and define a shared set of objectives for the analysis. Finally, Multi Criteria Analysis is employed to identify the best performing alternative among a set of competing projects. Synergies among the three tools and the operability of the proposed framework are discussed. n SB73 West Bldg 211B

58