Teorie her pro inteligentní sítě

Teorie her je disciplína aplikované matematiky, která analyzuje široké spektrum konfliktních rozhodovacích situací, které mohou nastat kdekoliv, kde dochází ke střetu zájmů. Herně-teoretické modely se pak snaží tyto konfliktní situace nejen analyzovat, ale sestavením matematického modelu daného konfliktu a pomocí výpočtů se snaží nalézt co nejlepší strategie pro konkrétní účastníky takových konfliktů. Teorie her se uplatňuje v mnoha oblastech lidské činnosti od ekonomie, přes politologii až například po sociologii a biologii. V tomto předmětu budeme studovat možnosti aplikací teorie her v inteligentních sítích.

Inteligentní sítě (anglicky Smart grid) jsou silové elektrické a komunikační sítě, které umožňují regulovat výrobu a spotřebu elektrické energie v reálném čase, jak v místním, tak v globálním měřítku. Jejím principem je interaktivní obousměrná komunikace mezi výrobními zdroji a spotřebiči nebo spotřebiteli o aktuálních možnostech výroby a spotřeby energie.

Jedním ze základních problémů v oblasti Smart grids je balancování výroby a spotřeby elektrické energie. Ve dvacátém století byla výroba elektřiny koncentrovaná v síti velkých elektráren (zejména uhelných, jaderných či vodních) a tyto zdroje byly navrženy tak, aby byly schopny regulovat svoji produkci podle aktuální spotřeby. V poslední době nastal prudký rozvoj obnovitelných zdrojů (především slunečních a větrných), které nejenže nejsou schopny regulovat svoji výrobu podle potřeby, ale navíc množství vyrobené elektrické energie je značně proměnlivé v čase a dopředu se velmi špatně odhaduje. Proto dochází k vývoji elektrických baterií a spotřebičů, které jsou schopny plánovat svoji spotřebu energie podle možností sítě. Efektivní využití těchto zařízení vyžaduje pokročilé algoritmy, které jsou schopny dopředu odhadnout množství vyrobené a spotřebované energie, naplánovat jednotlivá zařízení podle jejich možností a pružně reagovat na změny v reálném čase.

Typickým přístupem ke zlepšení využívání energií ve vědeckých publikacích je sestavení globální optimalizační úlohy popisující všechny možné stavy všech zařízení. Tyto metody sice na simulacích či praktických testech dávají lepší výsledky, ale často neplňují některé z následující vlastností.

  • Škálovatelnost: Vyřešení globální optimalizační úlohy často vyžaduje značný výpočetní výkon a tyto nároky na hardware rychle rostou se zvětšujícím se počtem zařízení. Proto bychom preferovali metody, které nejsou výpočetně příliš náročné.
  • Ochrana osobních dat: Globální optimalizační úlohy vyžadují velmi podrobné informace o využívání jednotlivých zařízení. Obyvatelům domácností zapojených do Smart grid projektů se nemusí líbit odesílaní příliš mnoha informací distributorům energií k optimálnímu plánování.
  • Spravedlnost a individuální preference: Jedním ze základních cílů je rovnoměrné rozložení spotřeby energie v čase, čehož se dosahuje spouštěním některých zařízení v méně preferovaných časech. Řešení globalních optimalizačních úloh sice rovnoměrně rozloží spotřebu v čase, ale většinou se nesnaží být spravedlivý k jednotlivým domácnostem nebo neuvažuje induviduální preference jednotlivých domácností.
  • Pravdivost: Obyvatelé by neměli mít možnost získat (pro ně) preferovanější časy spouštění jednotlivých zařízení tím, že do optimalizační úlohy zadají nepravdivé informace.
  • Otevřenost: Optimalizační postupy i komunikační protokoly by měli být veřejné.

Základní informace

  • Název: Teorie her pro inteligentní sítě
  • Vyučující: Martin Loebl a Jiří Fink
  • Kód: NOPT057
  • Rozsah, examinace: 0/2 Z
  • Předmět bude vyučován v českém nebo anglickém jazyce podle zájmu studentů.
  • Výuka bude probíhat v letním semestru 2015/16.
  • Rozvrh bude domluven na úmluvě KAM
  • Seznam článků
  • Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)

Cíle předmětu

Cílem předmětu je studovat možnosti aplikací teorie her v Inteligentních sítích. Studenti mohou v průběhu semestru pracovat na projektech, které bude možné rozšířit na bakalářské a diplomové práce.

Předpoklady

  • znalost lineárního programování (například Optimalizační metody)
  • předmět je primárně určen pro studenty magisterských programů teoretická informatika, umělá inteligence a diskrétní modely a algoritmy, ale po předchozí konzultaci s vyučujícím může být vhodný i pro ostatní studenty MFF UK

Zápočet

Zápočet je možné získat některými z následujících možností.
  • prezentace článků
  • vlastní teoretický výsledek
  • experimentální simulace
Podrobnosti musí být předem konzultovány s vyučujícím. Náročnější projekt nebo vědecká publikace může pokračovat k ročníkovému projektu, softwarovému projektu, bakalářské nebo diplomové práci.

Plánovaný obsah

  • Úvod do Smart Grids a souvislost s teorií her
  • Základní pojmy teorie her a přehled "game design": maticové hry, Nash equilibria, market equilibria, kooperativní vs. kompetitivní strategie, kombinatorické aukce, Fisher a Arrow–Debreu modely, Vickrey-Clark-Groves mechanismus, social choice (dle znalostí studentů)
  • Přehled dosavadních aplikací teorie her ve Smart Grids
  • PowerMatcher and Profile steering
  • Prezentace jednotlivých článků

Literatura

  • K. Kok: The PowerMatcher: Smart Coordination for the Smart Electricity Grid, PhD thesis, Free University of Amsterdam. On-line
  • Robert J. Aumann, Sergiu Hart: Handbook of game theory with economic applications, volume 4, Elseview, 2015. On-line
  • Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani: Algorithmic game theory. Cambridge University Press Cambridge, 2007. On-line

Game Theory in Smart Grids

Game theory is "the study of mathematical models of conflict and cooperation between intelligent rational decision-makers." Game theory is mainly used in economics, political science, and psychology, as well as logic, computer science, biology and Poker (Texas No Limit Hold'em). Originally, it addressed zero-sum games, in which one person's gains result in losses for the other participants. Today, game theory applies to a wide range of behavioral relations, and is now an umbrella term for the science of logical decision making in humans, animals, and computers. In this course, we will study applications of Game Theory in Smart Grids.

A smart grid is a modernized electrical grid that uses analog or digital information and communications technology to gather and act on information in an automated fashion to improve the efficiency, reliability, economics, and sustainability of the production and distribution of electricity.

One the main problems in Smart Grids is balancing energy production and consumption. In 20th century, the production of electricity was concentrated in a group of large power stations (mainly coal, nuclear or water) and these sources were designed to be able to control their output according to demands. However in recent years, the production from renewable energy sources (especially solar and wind) have been significantly increasing. These sources cannot be easily controlled and furthermore, their future output is hard to estimate. Therefore, devices and batteries are being developed to be able to plan their consumption according to the availability of the electricity network. Efficient usage of these devices requires advanced algorithms that can estimate production and consumption of energy, schedule each devices according to their possibilities and dynamically react on every event in real time.

A typical approach to improve the usage of energy in scientific publications is creating a global optimization problem describing all feasible states of all devices. Although these methods gives interesting results in simulations of field tests, they often fail some of the following criteria.

  • Scalability:Solving global optimization problem often requires enormous computational power. Therefore, we prefer methods fast to compute even on embedded systems.
  • Privacy protection: Global optimization problems requires detailed information about the usage of each device. However, inhabitants participating in smart grid project may not appreciate sending such personal data to energy provides for optimal scheduling.
  • Social fairness: One of the main goals is uniform distribution of energy consumption in time which is reached by scheduling some devices in less preferred times. Although solutions of these global optimization problems uniformly schedule demands in time, the scheduling does not try to be fair to individual households or individual preferences are not considered.
  • Truthfulness: Inhabitants should not be able to obtain more preferable scheduling by providing incorrect information.
  • Openness: Optimization methods and communication protocols should be public.

Basic information

  • Name: Game Theory in Smart Grids
  • Teacher: Martin Loebl a Jiří Fink
  • Code: NOPT057
  • Hours per week, examination: 0/2 Z
  • The course will be in Czech or English
  • The course will in summer semester 2015/16.
  • If you are interested, write me e-mail to discuss the schedule.
  • List of articles

Aim of the course

In this course, we will study applications of Game Theory in Smart Grids. Student projects are offered during this course.

Preliminary syllabus

  • Introduction to smart grids and relations to the game theory
  • Basic term of the game theory: game design, matrix games, Nash equilibria, market equilibria, cooperative vs competitive strategies, combinatorial auctions, Fisher and Arrow–Debreu models, Vickrey-Clark-Groves mechanism, social choice (depending of student knowledge)
  • Overview of the current applications of game theory in smart grids
  • PowerMatcher and profile steering
  • Article presentations

Literature

  • K. Kok: The PowerMatcher: Smart Coordination for the Smart Electricity Grid, PhD thesis, Free University of Amsterdam. On-line
  • Robert J. Aumann, Sergiu Hart: Handbook of game theory with economic applications, volume 4, Elseview, 2015. On-line
  • Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani: Algorithmic game theory. Cambridge University Press Cambridge, 2007. On-line