Journées de l'optimisation 2009 Optimizations days

First, a quantized progressive second price auction called UQ-PSP is developed to allocate a resource among arbitrary populations of agents. Second, distributed auctions on networks are analyzed where agents employ UQ-PSP schemes by observing their neighbors’ bids. The equilibria and convergence properties of the distributed auctions are established and are shown to depend on the network topology.

Evolutionary algorithms based on stochastic programming are proposed for learning of the optimum bid in auction markets. Sellers and buyers are attempting to learn their optimum bids that maximize their individual utility functions in the next round of the game. Examples of a second-price sealed-bid auction and double auction markets are considered and good performance of this type of algorithms is confirmed by extensive simulations. The proposed algorithms need no assumptions about the stationary behaviour of players, contrary to the needs of competitive algorithms in the class of fictitious play.

A novel algorithm for learning in non-cooperative games is proposed. The algorithm employs the idea of the Metropolis Monte-Carlo algorithm in which the generated Markov chain is non-homogeneous. The algorithm can be viewed as a type of simulated annealing algorithm in which the proposal is the Levy skew alpha-stable distribution. The parameter scale factor which represents the measure of the width of the distribution is made to decrease monotonically along with the parameter implementing the cooling process. The simulated annealing algorithm has been originally conceived to provide solutions to global optimization problems, but is adapted here to find Nash equilibria. An additional advantage of the algorithm is that it can handle discontinuous utility functions.

Real-time unconstrained optimization is realized by controlling the gradient, that is estimated using finite difference between two units operating with an offset. Scalar global optimization is achieved by reducing this offset to zero. For two-input systems, the above technique is performed on the circumference of a circle of reducing radius.