A periodic isoperimetric problem related to the unique games conjecture

We prove the endpoint case of a conjecture of Khot and Moshkovitz related to the unique games conjecture, less a small error. Let n ≥ 2. Suppose a subset Ω of n‐dimensional Euclidean space satisfies ?Ω = Ω^c and Ω + v = Ω^c (up to measure zero sets) for every standard basis vector . For any and for any q ≥ 1, let and let . For any x ∈ ?Ω, let N(x) denote the exterior normal vector at x such that ‖N(x)‖₂ = 1. Let . Our main result shows that B has the smallest Gaussian surface area among all such subsets Ω, less a small error: In particular, Standard arguments extend these results to a corresponding weak inequality for noise stability. Removing the factor 6 × 10^?9 would prove the endpoint case of the Khot‐Moshkovitz conjecture. Lastly, we prove a Euclidean analogue of the Khot and Moshkovitz conjecture. The full conjecture of Khot and Moshkovitz provides strong evidence for the truth of the unique games conjecture, a central conjecture in theoretical computer science that is closely related to the P versus NP problem. So, our results also provide evidence for the truth of the unique games conjecture. Nevertheless, this paper does not prove any case of the unique games conjecture.     

Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games

We consider the problem of computing the set of initial states of a dynamical system such that there exists a control strategy to ensure that the trajectories satisfy a temporal logic specification with probability 1 (almost-surely). We focus on discrete-time, stochastic linear dynamics and specifications given as formulas of the Generalized Reactivity(1) fragment of Linear Temporal Logic over linear predicates in the states of the system. We propose a solution based on iterative abstraction-refinement, and turn-based 2-player probabilistic games. While the theoretical guarantee of our algorithm after any finite number of iterations is only a partial solution, we show that if our algorithm terminates, then the result is the set of all satisfying initial states. Moreover, for any (partial) solution our algorithm synthesizes witness control strategies to ensure almost-sure satisfaction of the temporal logic specification. While the proposed algorithm guarantees progress and soundness in every iteration, it is computationally demanding. We offer an alternative, more efficient solution for the reachability properties that decomposes the problem into a series of smaller problems of the same type. All algorithms are demonstrated on an illustrative case study.     

The impact of loops on the game of cops and robbers on graphs

In the game of cops and robbers on graphs, the cops and the robber are allowed to pass their turn if they are located on a looped vertex. This paper explores the effect of loops on the cop number and the capture time. We provide examples of graphs where the cop number almost doubles when the loops are removed, graphs where the cop number decreases when the loops are removed, graphs where the capture time is quadratic in the number of vertices and copwin graphs where the cop needs to move away from the robber in optimal play.     

Demand commitments in majority bargaining or how formateurs get their way

We consider a demand bargaining model where the formateur (proposal maker) is appointed before the players state their demands. In a general continuous framework, we show that if the decision has a distributive dimension, then the formateur gets his way. I thank Friedel Bolle, Jonathan Tan, the editor, and an anonymous referee for very helpful comments. In addition, I gratefully acknowledge the support of the DFG (project no. BO 747/10-1).     

On the existence of oscillating solutions in non-monotone Mean-Field Games

For non-monotone single and two-populations time-dependent Mean-Field Game systems we obtain the existence of an infinite number of branches of non-trivial solutions. These non-trivial solutions are in particular shown to exhibit an oscillatory behaviour when they are close to the trivial (constant) one. The existence of such branches is derived using local and global bifurcation methods, that rely on the analysis of eigenfunction expansions of solutions to the associated linearized problem. Numerical analysis is performed on two different models to observe the oscillatory behaviour of solutions predicted by bifurcation theory, and to study further properties of branches far away from bifurcation points.     

Monotonicity properties of wholesale price contracts

This paper contributes to the supply chain contracts literature in economics and operations by performing qualitative sensitivity analysis of a wholesale price contract in a two-echelon supply chain setting. Order-theory tools are used to derive sufficient conditions for monotonicity of contract parameters.The upstream supplier is modeled as a Stackelberg leader. The supplier is assumed to have complete information about the costs and revenue function of the downstream retailer. It is shown that an equilibrium wholesale price weakly increases with an increase in the supplier production cost rate, but it may increase or decrease with an increase in the retailer cost rate. As either the supplier production cost or the retailer cost increases, the supplier profit decreases weakly. Additional sensitivity analysis is performed assuming certain properties of the retailer revenue function.Several well-known results in the supply chain contracting literature can be considered as special cases of the more general theorems developed here. In particular, this paper reexamines the analysis of a newsvendor supply chain problem by Lariviere and Porteus [Lariviere, M.A., Porteus, E.L., 2001. Selling to the newsvendor: An analysis of price-only contracts. Manufacturing & Service Operations Management 3, 293–305]. This paper generalizes and extends their work, by establishing properties of the newsvendor demand distribution that guarantee monotonicity of the contract parameters, without requiring a unique contract solution.     

Pricing Behaviors on Networks: Some General Results for Two-way Networks

In this paper, we study monopolistic pricing behaviors within a two-way network. In this symbiotic production system, independent decision centers carry out an activity which concurs to the production of different system goods. The players are assumed to know the whole network. Due to this rationality, they try to capture a share of the profit of the firms who sell the system goods to the consumers. These double marginalization behaviors are studied within very general networks. Conditions with ensure existence and uniqueness are discussed. We even provided a complete characterization of an equilibrium. Potential applications are also discussed     

Asymmetric flow networks

This paper provides a new model of network formation that bridges the gap between the two benchmark game-theoretic models by Bala and Goyal (2000a) – the one-way flow model, and the two-way flow model – and includes both as limiting cases. As in both the said models, a link can be initiated unilaterally by any player with any other in what we call an “asymmetric flow” network, and the flow through a link towards the player who supports it is perfect. Unlike those models, there is friction or decay in the opposite direction. When this decay is complete there is no flow and this corresponds to the one-way flow model. The limit case when the decay in the opposite direction (and asymmetry) disappears corresponds to the two-way flow model. We characterize stable and strictly stable architectures for the whole range of parameters of this “intermediate” and more general model. A study of the efficiency of these architectures shows that in general stability and efficiency do not go together. We also prove the convergence of Bala and Goyal’s dynamic model in this context.     

Three-level warranty service contract among manufacturer,agent and customer: A game-theoretical approach

A warranty is a service contract between a manufacturer and a customer which plays a vital role in many businesses and legal transactions. In this paper, various three-level service contracts will be presented among the following three participants; a manufacturer, an agent, and a customer. In order to obtain a better result, the interaction between the aforementioned participants will be modeled using the game theory approach. Under non-cooperative and semi-cooperative games, the optimal sale price, warranty period and warranty price for the manufacturer and the optimal maintenance cost or repair cost for the agent are obtained by maximizing their profits. The satisfaction of the customer is also maximized by being able to choose one of the suggested options from the manufacturer and the agent, based on the risk parameter. Several numerical examples and managerial insights are presented and used to illustrate the models presented in this paper.