TheMathematicalTheoryofMinorityGames 12 This page intentionally left blank The Mathematical Theory of Minority Games Statistical mechanics of interacting agents A.C.C. COOLEN King’sCollegeLondon 1 OXFORD UNIVERSITY PRESS Great Clarendon Street, Oxford OX2 6DP Oxford University press is a department of the University of Oxford. It furthers the University's objective of excellence in research, scholarship, and education by publishing worldwide in Oxford New York Auckland Cape Town Dar es Salaam Hong Kong Karachi Kuala Lumpur Madrid Melbourne Mexico City Nairobi New Delhi Shanghai Taipei Toronto With offices in Argentina Austria Brazil Chile Czech Republic France Greece Guatemala Hungary Italy Japan Poland Portugal Singapore South Korea Switzerland Thailand Turkey Ukraine Vietnam Oxford is a registered trade mark of Oxford University Press in the UK and in certain other countries Published in the United States by Oxford University Press Inc., New York © Oxford University Press 2005 The moral rights of the author have been asserted Database right Oxford University Press (maker) First published 2005 All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, without the prior permission in writing of Oxford University Press, or as expressly permitted by law, or under terms agreed with the appropriate reprographics rights organization. Enquiries concerning reproduction outside the scope of the above should be sent to the Rights Department, Oxford University Press, at the address above You must not circulate this book in any other binding or cover and you must impose this same condition on any acquirer British Library Cataloguing in Publication Data (Data available) Library of Congress Cataloguing in Publication Data (Data available) ISBN 0-19-852080 8 (Hbk) 10 9 8 7 6 54 3 21 Typeset by Kolam Information Services Pvt. Ltd, Pondicherry, India Printed in Great Britain on acid-free paper by Biddies Ltd., King's Lynn. ToKarin,AbelandFinn Preface This book describes Minority Games and explains their mathematical analysis from the viewpoint of a discipline-hopping non-equilibrium statistical mechanicist.There areseveralreasonswhyatextbookonMinorityGamesmightbehelpfulatthispointin time.Firstly,itappearsthatpopularityandscopeofMinorityGamesarestillgrowing. Atextbookmightassistthoseresearchersandstudentsintheoreticalphysics,applied mathematicsoreconomicswhowishtoenterthisscenebyofferinganaccessiblebut detailedandexplicitintroductiontotheirmathematicalanalysis,uniforminstyleand mathematical notation, selective in its choice of topics, and up to date. It might also servethosewhoarealreadyonthescenebyshowinghowdifferentmathematicalap- proachesarerelated,andbyactingasanefficientpointofdeparturefornewresearch. Theauthorhastriedtoexploitthespecificadvantagesofferedbywritingatextbook as opposed to writing research or review papers. The text aims to be self-contained in explaining detailed mathematical derivations, including any hidden or discipline- specificassumptionsandthemathematicalmethodsonwhichthesederivationsrely. Ratherthanintroducingandexplainingmathematicalformalismssuchasreplicathe- ory and generating functional analysis by first turning to spin models (which indeed generated these tools, but which might put off those who are interested in market models only), in the present text an attempt is made to explain such formalisms ‘en passant’, with subtleties discussed in footnotes and with references for further reading. Furthermore, various new derivations have been added with the objective to clarify, connect and supplement the existing analyses and theoretical results in literature. Thebookisorganizedwiththebenefitofhindsight—resultsarepresentedintheor- derexpectedtobemostbeneficialtothereader,ratherthanstrictlychronologically— andtheauthortookthetextbookstyleasajustificationforbeingrelievedoftheobliga- tiontogiveanencyclopedicaccountofthevastnumbersofpaperswrittenonMinority Games, and to concentrate instead on explaining the emerging mathematical theory. Themainreferencesareconcentratedanddiscussedinabibliographysection.Alsothe detailsofnumericalsimulationexperimentsaregiveninanappendix,inordertopre- ventunnecessarydistractioninfigurecaptions.Initschoiceofmathematicalnotation Preface vii the text tries to stay as close as possible to that of the original research papers, in as muchasthisdoesnotconflictwiththedesireforuniformity,whileacceptingthatthe limited combined size of the Roman and Greek alphabets makes a certain degree of symbolrecyclinginevitable. A.C.C.C. August2004 London Acknowledgements Itismygreatpleasuretothankallthosecolleagueswho,viadiscussions,jointresearch or otherwise, have directly or indirectly contributed towards this book. Especially I would like to thank (in alphabetical order) Tobias Galla, Alexander Heimel, Heinz Horner,ReimerKu¨hn,MatteoMarsili,andDavidSherrington. Contents 1 Introduction 1 1.1 Inductivereasoning:theElFarolbarproblem 2 1.2 TheStandardMG 4 1.3 PhenomenologyoftheMG 6 1.3.1 Statisticalpropertiesoftheoverallbid 7 1.3.2 Volatilityandidentificationofcontrolparameters 9 1.3.3 Theconceptof‘frozen’agents 12 1.3.4 Non-ergodicityoftheMG 13 1.3.5 Realversusfakememory 16 1.4 Apreview 20 2 Preparingthestageforstatisticalmechanics 23 2.1 GeneralizeddefinitionoftheMG 23 2.1.1 GeneralizedMGwithoutdecisionnoise 24 2.1.2 S = 2,decisionnoiseandvaluationperturbations 25 2.2 Timescalesandnatureofmicroscopicfluctuations 27 2.2.1 Temporalregularization 28 2.2.2 Kramers–Moyalexpansionandtimescaling 30 2.2.3 TheFokker–Plancktruncation 33 2.3 OverviewofMGversionstobeanalyzed 33 3 Pseudo-equilibriumreplicaanalysis 39 3.1 TheLyapunovfunction 39 3.1.1 Deterministicapproximationoftheprocess 39 3.1.2 Interpretationofminimaandfrozenagents 40 3.1.3 Conversiontoastatisticalmechanicalproblem 42 3.2 Dealingwithdisorder:replicatheory 43 3.2.1 Calculationofthedisorder-averagedfreeenergy 44 3.2.2 Thereplicasymmetricansatz—background 46 3.2.3 TheRSansatz—consequences 49