On participation games with complete information

We analyze a class of two-candidate voter participation games under complete information that encompasses as special cases certain public good provision games. We characterize the Nash equilibria of these games as stationary points of a non-linear programming problem, the objective function of which is a Morse function (onethat does not admit degenerate critical points) for almost all costs of participation. We use this fact to establish that, outside a closed set of measure zero of participation costs, all equilibria of these games are regular (an alternative to the result of De Sinopoli and Iannantuoni in Econ Theory 25(2):477–486, 2005). One consequence of regularity is that the equilibria of these games are robust to the introduction of (mild) incomplete information. Finally, we establish the existence of monotone Nash equilibria, such that players with higher participation cost abstain with (weakly) higher probability.      

Robust optimization with applications to game theory

In this article, we investigate robust optimization equilibria with two players, in which each player can neither evaluate his opponent's strategy nor his own cost matrix accurately while may estimate a bounded set of the strategy or cost matrix. We obtain a result that solving this equilibria can be formulated as solving a second-order cone complementarity problem under an ellipsoid uncertainty set or a mixed complementarity problem under a box uncertainty set. We present some numerical results to illustrate the behaviour of robust optimization equilibria.     

Stationary perfect equilibria of an n-person noncooperative bargaining game and cooperative solution concepts

This paper characterizes the stationary (subgame) perfect equilibria of an n-person noncooperative bargaining model with characteristic functions, and provides strategic foundations of some cooperative solution concepts such as the core, the bargaining set and the kernel. The contribution of this paper is twofold. First, we show that a linear programming formulation successfully characterizes the stationary (subgame) perfect equilibria of our bargaining game. We suggest a linear programming formulation as an algorithm for the stationary (subgame) perfect equilibria of a class of n-person noncooperative games. Second, utilizing the linear programming formulation, we show that stationary (subgame) perfect equilibria of n-person noncooperative games provide strategic foundations for the bargaining set and the kernel.     

On the Semismoothness of Projection Mappings and Maximum Eigenvalue Functions

This paper analyses the properties of the projection mapping over a set defined by a constraint function whose image is possibly a nonpolyhedral convex set. Under some nondegeneracy assumptions, we prove the (strong) semismoothness of the projection mapping. In particular, we derive the strong semismoothness of the projection mapping when the nonpolyhedral convex set under consideration is taken to be the second-order cone or the semidefinite cone. We also derive the semismoothness of the solution to the Moreau–Yosida regularization of the maximum eigenvalue function.     

Basis Function Adaptation in Temporal Difference Reinforcement Learning

Reinforcement Learning (RL) is an approach for solving complex multi-stage decision problems that fall under the general framework of Markov Decision Problems (MDPs), with possibly unknown parameters. Function approximation is essential for problems with a large state space, as it facilitates compact representation and enables generalization. Linear approximation architectures (where the adjustable parameters are the weights of pre-fixed basis functions) have recently gained prominence due to efficient algorithms and convergence guarantees. Nonetheless, an appropriate choice of basis function is important for the success of the algorithm. In the present paper we examine methods for adapting the basis function during the learning process in the context of evaluating the value function under a fixed control policy. Using the Bellman approximation error as an optimization criterion, we optimize the weights of the basis function while simultaneously adapting the (non-linear) basis function parameters. We present two algorithms for this problem. The first uses a gradient-based approach and the second applies the Cross Entropy method. The performance of the proposed algorithms is evaluated and compared in simulations. This research was partially supported by the Fund for Promotion of Research at the Technion. The work of S.M. was partially supported by the National Science Foundation under grant ECS-0312921.     

Riesz-Nágy singular functions revisited

In 1952 F. Riesz and Sz.-Nágy published an example of a monotonic continuous function whose derivative is zero almost everywhere, that is to say, a singular function. Besides, the function was strictly increasing. Their example was built as the limit of a sequence of deformations of the identity function. As an easy consequence of the definition, the derivative, when it existed and was finite, was found to be zero. In this paper we revisit the Riesz-Nágy family of functions and we relate it to a system for real number representation which we call (τ,τ−1)-expansions. With the help of these real number expansions we generalize the family. The singularity of the functions is proved through some metrical properties of the expansions used in their definition which also allows us to give a more precise way of determining when the derivative is 0 or infinity.     

Supply Function Equilibrium in Electricity Spot Markets with Contracts and Price Caps

In electricity wholesale markets, generators often sign long term contracts with purchasers of power in order to hedge risks. In this paper, we consider a market where demand is uncertain, but can be represented as a function of price together with a random shock. Each generator offers a smooth supply function into the market and wishes to maximize his expected profit, allowing for his contract position. We investigate supply function equilibria in this setting, using a model introduced by Anderson and Philpott. We study first the existence of a unique monotonically increasing supply curve that maximizes the objective function under the constraint of limited generation capacity and a price cap, and discuss the influence of the generators contract on the optimal supply curve. We then investigate the existence of a symmetric Nash supply function equilibrium, where we do not have to assume that the demand is a concave function of price. Finally, we identify the Nash supply function equilibrium which gives rise to the generators maximal expected profit. This work was supported by the Australian Research Council Grant RMG1965The authors would like to thank three anonymous referees for their helpful comments     

Modified Newton methods for solving a semismooth reformulation of monotone complementarity problems

In this paper, we propose a Newton-type method for solving a semismooth reformulation of monotone complementarity problems. In this method, a direction-finding subproblem, which is a system of linear equations, is uniquely solvable at each iteration. Moreover, the obtained search direction always affords a direction of sufficient decrease for the merit function defined as the squared residual for the semismooth equation equivalent to the complementarity problem. We show that the algorithm is globally convergent under some mild assumptions. Next, by slightly modifying the direction-finding problem, we propose another Newton-type method, which may be considered a restricted version of the first algorithm. We show that this algorithm has a superlinear, or possibly quadratic, rate of convergence under suitable assumptions. Finally, some numerical results are presented. Supported by Research Fellowships of the Japan Society for the Promotion of Science for Young Scientists. Supported in part by the Scientific Research Grant-in-Aid from the Ministry of Education, Science and Culture, Japan.     

Characterizations of Optimal Trajectories for Nonconvex Control Systems under State Constraints

We consider an optimal control problem for a nonconvex control system under state constraints and the associated value function, which in general is not differentiable. We provide some characterizations of optimal trajectories using contingent derivatives. For this aim, we derive a costate satisfying the adjoint equation, the maximum principle, and a transversality condition linked to the superdifferential of the value function.Communicated by F. ZirilliThis paper is dedicated by the author to her children.     

A semismooth Newton method for traffic equilibrium problem with a general nonadditive route cost

Computing traffic equilibria with a general nonadditive route cost disutility function is considered in this paper. Following the user equilibrium (UE) condition, that is, no driver can unilaterally change route to achieve less travel costs, the traffic equilibrium problem (TEP) can be formulated as a nonlinear complementary problem (NCP). In this paper, we propose a semismooth Newton method with a penalized Fischer–Burmeister (PFB) NCP function to solve the NCP formulation of the TEP, and also, we investigate the properties of the proposed method. Numerical results are provided and compared with the classical TEP with additive route cost functions. The results show the algorithm can achieved substantially better performance than the existing approaches. A sensitivity analysis is also conducted to examine the parameter of the proposed nonadditive route cost function.     

On the rate of convergence of infinite horizon discounted optimal value functions

In this paper we investigate the rate of convergence of the optimal value function of an infinite horizon discounted optimal control problem as the discount rate tends to zero. Using the Integration Theorem for Laplace transformations we provide conditions on averaged functionals along suitable trajectories yielding quadratic pointwise convergence. From this we derive under appropriate controllability conditions criteria for linear uniform convergence of the value functions on control sets. Applications of these results are given and an example is discussed in which both linear and slower rates of convergence occur depending on the cost functional.     

Optimal paths in bi-attribute networks with fractional cost functions

An important routing problem is to determine an optimal path through a multi-attribute network which minimizes a cost function of path attributes. In this paper, we study an optimal path problem in a bi-attribute network where the cost function for path evaluation is fractional. The problem can be equivalently formulated as the “bi-attribute rational path problem” which is known to be NP-complete. We develop an exact approach to find an optimal simple path through the network when arc attributes are non-negative. The approach uses some path preference structures and elimination techniques to discard, from further consideration, those (partial) paths that cannot be parts of an optimal path. Our extensive computational results demonstrate that the proposed method can find optimal paths for large networks in very attractive times.     

New optimality principles for economic efficiency and equilibrium

This paper develops several optimization principles relating the fundamental concepts of Pareto efficiency and competitive equilibria. The beginning point for this development is the introduction of a new function describing individual preferences, closely related to willingness-to-pay, termed the benefit function. An important property of the benefit function is that it can be summed across individuals to obtain a meaningful measure of total benefit relative to a given set of utility levels; and the optimization principles presented in the paper are based on maximization of this total benefit.Specifically, it is shown that, under appropriate technical assumptions, a Pareto-efficient allocationX maximizes the total benefit relative to the utility levels it yields. Conversely, if an allocationX yields zero benefit and maximizes the total benefit function, then that allocation is Pareto efficient. The Lagrange multipliersp of the benefit maximization problem serve as prices; and the (X,p) pair satisfies a generalized saddle-point property termed a Lagrange equilibrium. This in turn is equivalent, under appropriate assumptions, to a competitive equilibrium.There are natural duals to all of the results stated above. The dual optimization principle is based on a surplus function which is a function of prices. The surplus is the total income generated at pricesp, minus the total income required to obtain given utility levels. The dual optimization principle states that prices that are dual (or indirect) Pareto efficient minimize total surplus and render it zero. Conversely, a set of prices that minimizes total surplus and renders it zero is a dual Pareto efficient set of prices.The results of the paper can be viewed as augmenting the first and second theorems of welfare economics (and their duals) to provide a family of results that relate the important economic concepts of Pareto efficiency, equilibrium, dual (or indirect) Pareto efficiency, total benefit, Lagrange equilibrium, and total surplus.The author wishes to thank Charles R. Bowman and Andrew J. Yates for several valuable suggestions and corrections.     

Semidefinite complementarity reformulation for robust Nash equilibrium problems with Euclidean uncertainty sets

Consider the N-person non-cooperative game in which each player’s cost function and the opponents’ strategies are uncertain. For such an incomplete information game, the new solution concept called a robust Nash equilibrium has attracted much attention over the past several years. The robust Nash equilibrium results from each player’s decision-making based on the robust optimization policy. In this paper, we focus on the robust Nash equilibrium problem in which each player’s cost function is quadratic, and the uncertainty sets for the opponents’ strategies and the cost matrices are represented by means of Euclidean and Frobenius norms, respectively. Then, we show that the robust Nash equilibrium problem can be reformulated as a semidefinite complementarity problem (SDCP), by utilizing the semidefinite programming (SDP) reformulation technique in robust optimization. We also give some numerical example to illustrate the behavior of robust Nash equilibria.     

On the Characterization of Preinvex Functions

In Refs. [J. Math. Anal. Appl. 258:287–308, [2001]; J. Math. Anal. Appl. 256:229–241, [2001]], Yang and Li presented a characterization of preinvex functions and semistrictly preinvex functions under a certain set of conditions. In this note, we show that the same results or even more general ones can be obtained under weaker assumptions; we also give a characterization of strictly preinvex functions under mild conditions. This research was supported by the National Natural Science Foundation of China under Grants 70671064 and 60673177, and the Education Department Foundation of Zhejiang Province Grant 20070306. The authors thank Professor F. Giannessi for valuable comments on the original version of this paper.     

Robust Equilibria in Indefinite Linear-Quadratic Differential Games

Equilibria in dynamic games are formulated often under the assumption that the players have full knowledge of the dynamics to which they are subject. Here, we formulate equilibria in which players are looking for robustness and take model uncertainty explicitly into account in their decisions. Specifically, we consider feedback Nash equilibria in indefinite linear-quadratic differential games on an infinite time horizon. Model uncertainty is represented by a malevolent input which is subject to a cost penalty or to a direct bound. We derive conditions for the existence of robust equilibria in terms of solutions of sets of algebraic Riccati equations.     

阿罗不可能性定理的几个等价形式

在这篇短中。给出了关于社会福利函数F的防止策略性操纵的概念,并且证明了如果备选对象至少有三个。则下面结论是相互等价的：(1)F满足Pareto与IIA性质;(2)F满足Pareto与RID性质;(3)F是独裁的;(4)F是满的、正向响应的;(5)F是防止策略操纵的且F是满的。     

Effective Search Problems

The task of computing a function F with the help of an oracle X can be viewed as a search problem where the cost measure is the number of queries to X. We ask for the minimal number that can be achieved by a suitable choice of X and call this quantity the query complexity of F. This concept is suggested by earlier work of Beigel, Gasarch, Gill, and Owings on “Bounded query classes”. We introduce a fault tolerant version and relate it with Ulam's game. For many natural classes of functions F we obtain tight upper and lower bounds on the query complexity of F. Previous results like the Nonspeedup Theorem and the Cardinality Theorem appear in a wider perspective. Mathematics Subject Classification: 03D20, 68Q15, 68R05.     

Nash Equilibria,Variational Inequalities,and Dynamical Systems

In this paper, we introduce some relationships between Nash equilibria, variational equilibria, and dynamical equilibria for noncooperative games.     

Green's functions for elliptic and parabolic systems with Robin-type boundary conditions

The aim of this paper is to investigate Green's function for parabolic and elliptic systems satisfying a possibly nonlocal Robin-type boundary condition. We construct Green's function for parabolic systems with time-dependent coefficients satisfying a possibly nonlocal Robin-type boundary condition assuming that weak solutions of the system are locally Hölder continuous in the interior of the domain, and as a corollary we construct Green's function for elliptic system with a Robin-type condition. Also, we obtain Gaussian bound for Robin Green's function under an additional assumption that weak solutions of Robin problem are locally bounded up to the boundary. We provide some examples satisfying such a local boundedness property, and thus have Gaussian bounds for their Green's functions.