Séance TB1 - Apprentissage et optimisation dans les jeux et la commande / Learning and Optimization in Games and Controls
Jour mardi, le 05 mai 2009 Salle St-Hubert Président Roland P. Malhamé
Présentations
|
13h30- 13h55 |
Auctions on Networks: Efficiency, Passivity, Consensus, Rate of Convergence |
|
Peng Jia, McGill University, Electrical and Computer Engineering, 3480 University street, Rm 410, Montreal, QC, Canada, h3a2a7 Peter E. Caines, GERAD, McGill University, Electrical and Computer Engineering, 3480 University street, Montreal, QC, Canada, h3a2a7 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. |
|
13h55- 14h20 |
Stochastic Learning of the Optimum Bid in Auction Markets |
|
Shahram Tabandeh, McGill University, Electrical and Computer Engineering Hannah Michalska, McGill University, Electrical and computer Engineering 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. |
|
14h20- 14h45 |
Levy Flight and Simulated Annealing for Learning in Games |
|
Shahram Tabandeh, McGill University, Electrical and Computer Engineering Hannah Michalska, McGill University, Electrical and computer Engineering 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. |
|
14h45- 15h10 |
Global Optimization of Multivariable Systems using Gradient Control |
|
Fargad Esmaeilzadeh Azar, École Polytechnique de Montréal, Génie chimique Michel Perrier, GERAD, École Polytechnique de Montréal, Génie chimique, Montreal, Qc, Canada Bala Srinivasan, GERAD, École Polytechnique de Montréal, Génie Chimique, 2500 Chemin Polytechnique, Montréal, Québec, Canada, H3T 1J4 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. |