Vai al contenuto principale
Coronavirus: aggiornamenti per la comunità universitaria / Coronavirus: updates for UniTo Community
Oggetto:
Oggetto:

Modelli Matematici per le Applicazioni

Oggetto:

Mathematical Models for the Applications

Oggetto:

Anno accademico 2022/2023

Codice attività didattica
MFN0363
Docente
Prof. Paolo Cermelli (Titolare del corso)
Corso di studio
Laurea in Matematica
Anno
3° anno
Periodo
Secondo semestre
Tipologia
D.M. 270 TAF B - Caratterizzante
Crediti/Valenza
6
SSD attività didattica
MAT/07 - fisica matematica
Erogazione
A distanza
Lingua
Italiano
Frequenza
Facoltativa
Tipologia esame
Orale
Oggetto:

Sommario insegnamento

Oggetto:

Obiettivi formativi

Lo scopo del corso è fornire un'introduzione alle tecniche di base per la modellizzazione dei fenomeni sociali e di teoria delle reti.

In particolare, esamineremo prima di tutto le basi della teoria delle decisioni interattive, la cosidetta teoria dei giochi, che è lo strumento fondamentale per formulare e testare modelli di interazione tra individui, ad esempio in competizione per una risorsa. Estenderemo poi i concetti di base al caso in cui il gioco, e quindi l'interazione, sia ripetuta nel tempo, studiando due famiglie di modelli: quelli che fanno capo alla cosiddetta teoria dei giochi evolutivi, che permette di analizzare sotto quali condizioni gli equuilibri di Nash vengono effettivamente raggiunti da giocatori 'miopi', e la teoria degli automi decisionali, ad esempio Tit for Tat, win-stay/lose shift, e così via.

La seconda parte del corso tratta degli elementi di teoria delle reti: introdurremo le basi di teoria dei grafi direzionati, e studieremo le relazioni tra le proprietà topologiche dei grafi e le proprietà algebriche della matrice di adiacenza. Questo permette di introdurre la nozione di camminatore casuale su un grafo, e di descriverlo come una catena di Markov a stati finiti. Come applicazione studieremo l'algoritmo di Brin e Page per il Page Rank di Google. Come seconda applicazione, studieremo successioni di grafi casuali, e descriveremo i principali modelli generativi per il grafo Web, mostrando come la note distribuzione a legge di potenza delle pagine web implichi una legge di attaccamento preferenziale: il web si aggrega in modo che pagine più popolari attirano più link delle altre. Discuteremo inoltre l'importanza relativa di alcune misure di clustering e connessione di grafi, con applicazioni alle reti sociali. Infine, presenterò il modello base di gestione del traffico su reti, il cosiddetto selfish routing, in cui si vede bene l'interazione tra la topologia della rete e la logica del conflitto tra gli utenti pr l'utilizzo della stessa.

The course aims at providing  an introduction to the basic techniques for the modelization of social phenomena and network theory. First of all, we will examine the basics of interactive decision theory,  a.k.a. Game Theory, which is the fundamental tool to formulate and  test models of interactions among individuals.  Then, we will extend the basic concepts to situations in which the interaction, i.e., the game, is iterated, and study two families of mathematical models: evolutionary game theory,  for which concepts from the theory of dynamical systems are needed, and the iterated prisoner's dilemma, in which the interactions occur at discrete times and the strategies can be described as machines, i.e., decisional automata, such as  Tit for Tat, win-stay/lose shift, and so on.

The second part of the course is devoted to network theory: we will first introduce basic results on directed graphs, highlighting the relations between the topological properties of the graph and the algebraic properties of the adjacency matrix. This will allow to define random walks on graphs,  and show that this is a finite-states Markov chain. As an application, we will discuss the Page Rank (Google) algorithm and Salsa, two well known ranking algorithms for web pages. Then, we will study large-scale properties of the Web, namely the power law distribution of the indegrees. We will present the preferential attachment (Albert-Barabasi) and the random attachment models, and show that they lead to substantially different indegree distributions.

Finally, we will briefly discuss some clustering and centrality coefficients for social networks, and study an exactly solvable analogy of the Watts-Strogatz model for small-world networks. A final section will be devoted to selfish-routing models.

Oggetto:

Risultati dell'apprendimento attesi

In uscita lo studente dovrebbe avere le basi su cui fondare lo studio ulteriore dei sistemi complessi formati da agenti in mutua interazione, con i metodi più sofisticati forniti in corsi successivi, ad esempio basati su tecniche di meccanica statistica (non trattata in questo corso).

At the end of the course, the student will have the basis on which he/she will build the study of complex networks with more sophisticated theoretical and numerical tools, for instance using concepts of statistical mechanics. 

 

Oggetto:

Programma

Teoria dei giochi. Forma strategica e forma estesa. Equilibri di Nash, equilibri perfetti e subgame perfect.

Teoria evolutiva dei giochi: dinamica del replicatore e dinamiche di apprendimento.

Il dilemma del prigioniero iterato: automi e teoremi folk di Nash.

Teoria delle reti, cenni su teoria dei grafi casuali e catene di Markov. L'algoritmo Page Rank.  I principali modelli generativi per il web, e applicazioni alla autoorganizzazione di reti sociali e web. Misure di clustering e connessione. Il modello di Watts Strogatz. Anaòlisi di reti sociali.

Selfish routing: il paradosso di Braess

 

 



Game theory: strategic and extended form. Nash Equilibria, perfect  and subgame perfect equilibria.

Evolutionary game theory: replicator dynamics and learning dynamics.

The Iterated Prisoner's Dilemma: automata and Nash folk theorems.

Network theory: some notions of random graphs. The Page Rank  algorithm. Generative models for random networks, with applications to the web and social networks. The Watts-Strogatz model.

Selfish Routing: the Braess paradox.

 

 

 

 

Oggetto:

Modalità di insegnamento

L'insegnamento, di 48 ore, e' costituito principalmente da lezioni frontali, in cui verranno presentati i risultati teorici e le loro dimostrazioni, e da ampie  discussioni di esempi ed esercizi.

Per l’AA 22-23, le lezioni saranno svolte in presenza. Modalità didattiche alternative (streaming) potranno essere introdotte a seguito di nuove raccomandazioni di Ateneo in relazione allo stato della pandemia Covid-19.

 

 The course, of 48 hours, will be provided as frontal lessons, in which both theory and examples will be discussed. For the academic year 22-23, the lessons will be held in person. Alternative teaching methods (streaming) may be introduced following new University recommendations in relation to the state of the Covid-19 pandemic.

 

Oggetto:

Modalità di verifica dell'apprendimento

L'esame e' costituito da una prova orale di durata non inferiore a 30 minuti che comprende quesiti teorici e risoluzione di esercizi.  In alternativa, verranno proposti test scritti intermedi il cui risultato contribuirà al voto finale.

Per l’AA 22-23, gli esami si svolgeranno in presenza, con la sola eccezione per gli studenti e le studentesse che autodichiarano, in relazione al Covid-19, fragilità personale o positività. Modalità alternative (online) potranno essere introdotte a seguito di nuove raccomandazioni di Ateneo in relazione allo stato della pandemia Covid-19.

The examination consists of an oral colloquium including the discussion of an exercise. Alternatively, the students will have the chance to sit at intermediate written tests (typically 2/3) whose marks will be taken into account in the final grade.

For AY 22-23, exams will be held in person, with the sole exception of students who self-report, in relation to Covid-19, personal fragility or positivity. Alternative (online) methods may be introduced following new University recommendations in relation to the state of the Covid-19 pandemic.

Testi consigliati e bibliografia

Oggetto:

 

- Dispense del corso disponibili sul sito

- M. Osborne and A. Rubinstein. A course in Game Theory. MIT Press

- R. B. Myerson. Game theory: analysis of conflict. Harvard University Press

- H. Gintis. Game theory evolving. Princeton University Press

- D. Easley and J. Kleinberg.  Metworks, crowds and markets. Cambridge University Press

 - A. Bonato. A course on the Web graph. American Mathematical Society.

- M. Van Steen. Graph theory and complex networks: an Introduction.

 

 

- Lecture notes available on the web site.

- M. Osborne and A. Rubinstein. A course in Game Theory. MIT Press

- R. B. Myerson. Game theory: analysis of conflict. Harvard University Press

- H. Gintis. Game theory evolving. Princeton University Press

- D. Easley and J. Kleinberg.  Metworks, crowds and markets. Cambridge University Press

 - A. Bonato. A course on the Web graph. American Mathematical Society.

- M. Van Steen. Graph theory and complex networks: an Introduction.

 



Oggetto:

Insegnamenti che mutuano questo insegnamento

Oggetto:

Orario lezioniV

Registrazione
  • Aperta
    Oggetto:
    Ultimo aggiornamento: 12/09/2022 19:08

    Non cliccare qui!