-
作者：Balkanski, Eric; Rubinstein, Aviad; Singer, Yaron
作者单位：Columbia University; Stanford University; Harvard University
摘要：In this paper, we study submodular maximization under a matroid constraint in the adaptive complexity model. This model was recently introduced in the context of submodular optimization to quantify the information theoretic complexity of black-box optimization in a parallel computation model. Despite the burst in work on submodular maximization in the adaptive complexity model, the fundamental problem of maximizing a monotone submodular function under a matroid constraint has remained elusive....
-
作者：Chen, Xin; Li, Menglong
作者单位：University of Illinois System; University of Illinois Urbana-Champaign
摘要：Ma-convexity, one of the main concepts in discrete convex analysis, possesses many salient structural properties and allows for the design of efficient algorithms. In this paper, we establish several new fundamental properties of Ma-convexity and its variant SSQMa-convexity (semistrictly quasi Ma-convexity). We show that in a parametric maximization model, the optimal solution is nonincreasing in the parameters when the objective function is SSQMa-concave and the constraint is a box and illust...
-
作者：Aravena, Ignacio; Lete, Quentin; Papavasiliou, Anthony; Smeers, Yves
作者单位：United States Department of Energy (DOE); Lawrence Livermore National Laboratory; Universite Catholique Louvain
摘要：We propose a novel framework for modeling zonal electricity markets, based on projecting the constraints of the nodal network onto the space of the zonal aggregation of the network. The framework avoids circular definitions and discretionary parameters, which are recurrent in the implementation and study of zonal markets. Using this framework, we model and analyze two zonal market designs currently present in Europe: flow-based market coupling (FBMC) and available-transfer-capacity market coup...
-
作者：Kanoria, Yash; Nazerzadeh, Hamid
作者单位：Columbia University; University of Southern California
摘要：Large fractions of online advertisements are sold via repeated second-price auctions. In these auctions, the reserve price is the main tool for the auctioneer to boost revenues. In this work, we investigate the following question: how can the auctioneer optimize reserve prices by learning from the previous bids while accounting for the long-term incentives and strategic behavior of the bidders? To this end, we consider a seller who repeatedly sells ex ante identical items via a second-price au...
-
作者：Zhou, Zhengyuan; Mertikopoulos, Panayotis; Moustakas, Aris L.; Bambos, Nicholas; Glynn, Peter
作者单位：New York University; Inria; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); CNRS - Institute of Physics (INP); National & Kapodistrian University of Athens; Stanford University
摘要：We consider the target-rate power management problem for wireless networks; and we propose two simple, distributed power management schemes that regulate power in a provably robust manner by efficiently leveraging past information. Both schemes are obtained via a combined approach of learning and game design where we (1) design a game with suitable payoff functions such that the optimal joint power profile in the original power management problem is the unique Nash equilibrium of the designed ...
-
作者：Ahn, Hyun-Soo; Wang, Derek D.; Wu, Owen Q.
作者单位：University of Michigan System; University of Michigan; Capital University of Economics & Business; McGill University; Indiana University System; Indiana University Bloomington; IU Kelley School of Business
摘要：We extend the classical asset-selling problem to include debt repayment obligation, selling capacity constraint, and Markov price evolution. Specifically, we consider the problem of selling a divisible asset that is acquired through debt financing. The amount of asset that can be sold per period may be limited by physical constraints. The seller uses part of the sales revenue to repay the debt. If unable to pay off the debt, the seller must go bankrupt and liquidate the remaining asset. Our an...
-
作者：Johari, Ramesh; Kamble, Vijay; Kanoria, Yash
作者单位：Stanford University; University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital; Columbia University
摘要：We consider the problem faced by a service platform that needs to match limited supply with demand while learning the attributes of new users to match them better in the future. We introduce a benchmark model with heterogeneous workers (demand) and a limited supply of jobs that arrive over time. Job types are known to the platform, but worker types are unknown and must be learned by observing match outcomes. Workers depart after performing a certain number of jobs. The expected payoff from a m...
-
作者：Candogan, Ozan; Epitropou, Markos; Vohra, Rakesh V.
作者单位：University of Chicago; University of Pennsylvania; University of Pennsylvania
摘要：Under full substitutability of preferences, it is known that a competitive equilibrium exists in trading networks and is equivalent to (chain) stable outcomes. In this paper, we formulate the problem of finding an efficient set of trades as a generalized submodular flow problem in a suitable network. Existence of a competitive equilibrium and its equivalence with the seemingly weaker notion of stability follow directly from the optimality conditions of the flow problem. Our formulation enables...
-
作者：Poursoltani, Mehran; Delage, Erick
作者单位：Universite de Montreal; HEC Montreal; Universite de Montreal; HEC Montreal
摘要：This paper explores the idea that two-stage worst-case regret minimization problems with either objective or right-hand side uncertainty can be reformulated as two-stage robust optimization problems and can therefore benefit from the solution schemes and theoretical knowledge that have been developed in the last decade for this class of problems. In particular, we identify conditions under which a first-stage decision can be obtained either exactly using popular adjustable robust optimization ...
-
作者：Zhang, Wen; Chen, Qi (George); Katok, Elena
作者单位：Baylor University; University of London; London Business School; University of Texas System; University of Texas Dallas
摘要：This paper considers a resourcing setting in which a qualified supplier (the incumbent) and multiple suppliers that have not yet been qualified (the entrants) compete in an open-bid descending auction for a single-supplier contract. Because of the risk of supplier nonperformance, the buyer only awards the contract to a qualified supplier; meanwhile, the buyer can conduct supplier qualification screening at a cost to verify whether the entrant suppliers can perform the contract. Conventionally,...
