-
作者：Basu, Amitabh; Conforti, Michele; Di Summa, Marco; Zambelli, Giacomo
作者单位：Johns Hopkins University; University of Padua; University of London; London School Economics & Political Science
摘要：We study quantitative criteria for evaluating the strength of valid inequalities for Gomory and Johnson's finite and infinite group models, and we describe valid inequalities that are optimal for these criteria. We justify and focus on the criterion of maximizing the volume of the nonnegative orthant cut off by a valid inequality. For the finite group model of prime order, we show that the unique maximizer is an automorphism of the Gomory mixed-integer (GMI) cut for a possibly different finite...
-
作者：Xu, Zhen; Zhang, Jiheng; Zhang, Rachel Q.
作者单位：Hong Kong University of Science & Technology
摘要：Consider a storage system where the content is driven by a Brownian motion in the absence of control. At any time, one may increase or decrease the content at a cost proportional to the amount of adjustment. A decrease of the content takes effect immediately, while an increase is realized after a fixed lead time l. Holding costs are incurred continuously over time and are a convex function of the content. The objective is to find a control policy that minimizes the expected present value of th...
-
作者：Marinacci, Massimo; Montrucchio, Luigi
作者单位：Bocconi University; Bocconi University; Collegio Carlo Alberto; University of Turin
摘要：We establish sufficient conditions that ensure the uniqueness of Tarski-type fixed points of monotone operators. A first set of results relies on order concavity, whereas a second one uses subhomogeneity. A few applications that illustrate our results are presented.
-
作者：Lianeas, Thanasis; Nikolova, Evdokia; Stier-Moses, Nicolas E.
作者单位：University of Texas System; University of Texas Austin; Facebook Inc
摘要：We consider a nonatomic selfish routing model with independent stochastic travel times for each edge, represented by mean and variance latency functions that depend on edge flows. This model can apply to traffic in the Internet or in a road network. Variability negatively impacts packets or drivers by introducing jitter in transmission delays, which lowers quality of streaming audio or video, or by making it more difficult to predict the arrival time at destination. At equilibrium, agents may ...
-
作者：Fokkink, Robbert J.; Lidbetter, Thomas; Vegh, Laszlo A.
作者单位：Delft University of Technology; Rutgers University System; Rutgers University Newark; Rutgers University New Brunswick; University of London; London School Economics & Political Science
摘要：Suppose that some objects are hidden in a finite set S of hiding places that must be examined one by one. The cost of searching subsets of S is given by a submodular function, and the probability that all objects are contained in a subset is given by a supermodular function. We seek an ordering of S that finds all the objects with minimal expected cost. This problem is NP-hard, and we give an efficient combinatorial 2-approximation algorithm, generalizing analogous results in scheduling theory...
-
作者：Kunimoto, Takashi; Serrano, Roberto
作者单位：Singapore Management University; Brown University
摘要：A new condition, which we call uniform monotonicity, is shown to be necessary and almost sufficient for rationalizable implementation of correspondences. Uniform monotonicity is much weaker than Maskin monotonicity and reduces to it in the case of functions. Maskin monotonicity, the key condition for Nash implementation, had also been shown to be necessary for rationalizable implementation of social choice functions. Our conclusion is that the conditions for rationalizable implementation are n...
-
作者：Gairing, Martin; Savani, Rahul
作者单位：University of Liverpool
摘要：We study the computational complexity of finding stable outcomes in hedonic games, which are a class of coalition formation games. We restrict our attention to symmetric additively separable hedonic games, which are a nontrivial subclass of such games that are guaranteed to possess stable outcomes. These games are specified by undirected edge-weighted graphs: nodes are players, an outcome of the game is a partition of the nodes into coalitions, and the utility of a node is the sum of incident ...
-
作者：Syrgkanis, Vasilis; Kempe, David; Tardos, Eva
作者单位：Microsoft; University of Southern California; Cornell University
摘要：We consider common-value hybrid auctions among two asymmetrically informed bidders, in which the winning bidder pays his bid with some positive probability kappa and the losing bid otherwise. Under the assumption of discrete and affiliated signals, we give an explicit characterization of the (unique) equilibrium based on a simple recurrence relation, which gives rise to a linear-time algorithm for explicitly computing the equilibrium. By analyzing the execution of the algorithm, we derive seve...
-
作者：Pittel, Boris
作者单位：University System of Ohio; Ohio State University
摘要：Following up a recent work by Ashlagi, Kanoria, and Leshno, we study a stable matching problem with unequal side sizes, n men and N > n women, whose preferences for a partner are uniformly random and independent. An asymptotic formula for the expected number of stable matchings is obtained. In particular, for N = n +1 this number is close to n/(e log n), in notable contrast with (n log n)/e, the formula for the balanced case N = n that we obtained in 1988. We associate with each stable matchin...
-
作者：Lewis, Mark E.; Paul, Anand
