4期

最新文章

• Tight Lower Bounds on the Sizes of Symmetric Extensions of Permutahedra and Similar Results AI翻译
  作者：Pashkovich, Kanstantsin
  作者单位：Universite Libre de Bruxelles
  摘要：It is well known that the permutahedron IIn has 2(n) - 2 facets. The Birkhoff polytope provides a symmetric extended formulation of IIn of size Theta(n(2)). Recently, Goemans described a non-symmetric extended formulation of IIn of size Theta(n log n). In this paper, we prove that Omega(n(2)) is a lower bound for the size of symmetric extended formulations of IIn. Moreover, we prove that the cardinality indicating polytope has the same tight lower bounds for the sizes of symmetric and nonsymme...
• Optimal Design for Multi-Item Auctions: A Robust Optimization Approach AI翻译
  作者：Bandi, Chaithanya; Bertsimas, Dimitris
  作者单位：Northwestern University; Massachusetts Institute of Technology (MIT)
  摘要：In this paper, we revisit the auction design problem for multi-item auctions with budget constrained buyers by introducing a robust optimization approach to model (a) concepts such as incentive compatibility and individual rationality that are naturally expressed in the language of robust optimization and (b) the auctioneer's beliefs on the buyers' valuations of the items. Rather than using probability distributions (the classical probabilistic approach) or an adversarial model to model valuat...
• The Hirsch Conjecture Holds for Normal Flag Complexes AI翻译
  作者：Adiprasito, Karim A.; Benedetti, Bruno
  作者单位：Universite Paris Saclay
  摘要：Using an intuition from metric geometry, we prove that any flag normal simplicial complex satisfies the nonrevisiting path conjecture. As a consequence, the diameter of its facet-ridge graph is smaller than the number of vertices minus the dimension, as in the Hirsch conjecture. This proves the Hirsch conjecture for all flag polytopes and, more generally, for all (connected) flag homology manifolds.
• A Note on Appointment Scheduling with Piecewise Linear Cost Functions AI翻译
  作者：Ge, Dongdong; Wan, Guohua; Wang, Zizhuo; Zhang, Jiawei
  作者单位：Shanghai University of Finance & Economics; Shanghai Jiao Tong University; University of Minnesota System; University of Minnesota Twin Cities; New York University
  摘要：We consider the problem of determining the optimal schedules for a given sequence of jobs on a single processor. The objective is to minimize the expected total cost incurred by job waiting and processor idling, where the job processing times are random variables. It is known in the prior literature that if the processing times are integers and the costs are linear functions satisfying a mild condition, then the problem can be solved in a polynomial number of expected cost evaluations. In this...
• Opportunistic Approachability and Generalized No-Regret Problems AI翻译
  作者：Bernstein, Andrey; Mannor, Shie; Shimkin, Nahum
  作者单位：Technion Israel Institute of Technology
  摘要：Blackwell's theory of approachability, introduced in 1956, has since proved a useful tool in the study of a range of repeated multiagent decision problems. Given a repeated matrix game with vector payoffs, a target set S is approachable by a certain player if he can ensure that the average payoff vector converges to that set, for any strategy of the opponent. In this paper we consider the case where a set need not be approachable in general, but may be approached if the opponent played favorab...
• Robust Portfolio Choice and Indifference Valuation AI翻译
  作者：Laeven, Roger J. A.; Stadje, Mitja
  作者单位：University of Amsterdam; Tilburg University
  摘要：We solve, theoretically and numerically, the problems of optimal portfolio choice and indifference valuation in a general continuous-time setting. The setting features (i) ambiguity and time-consistent ambiguity-averse preferences, (ii) discontinuities in the asset price processes, with a general and possibly infinite activity jump part next to a continuous diffusion part, and (iii) general and possibly nonconvex trading constraints. We characterize our solutions as solutions to backward stoch...
• Potential Games Are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games AI翻译
  作者：Gopalakrishnan, Ragavendran; Marden, Jason R.; Wierman, Adam
  作者单位：University of Colorado System; University of Colorado Boulder; California Institute of Technology
  摘要：We consider the problem of designing distribution rules to share welfare (cost or revenue) among individually strategic agents. There are many known distribution rules that guarantee the existence of a (pure) Nash equilibrium in this setting, e.g., the Shapley value and its weighted variants; however, a characterization of the space of distribution rules that guarantees the existence of a Nash equilibrium is unknown. Our work provides an exact characterization of this space for a specific clas...
• Partial Monitoring-Classification, Regret Bounds, and Algorithms AI翻译
  作者：Bartok, Gabor; Foster, Dean P.; Pal, David; Rakhlin, Alexander; Szepesvari, Csaba
  作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Yahoo! Inc; Alphabet Inc.; Google Incorporated; University of Pennsylvania; University of Alberta
  摘要：In a partial monitoring game, the learner repeatedly chooses an action, the environment responds with an outcome, and then the learner suffers a loss and receives a feedback signal, both of which are fixed functions of the action and the outcome. The goal of the learner is to minimize his regret, which is the difference between his total cumulative loss and the total loss of the best fixed action in hindsight. In this paper we characterize the minimax regret of any partial monitoring game with...