Algorithmic Game Theory: Strategies and Equilibrium

Algorithmic Game Theory Overview

• Game theory is used to mathematically model strategic interactions among rational agents, who are participants with preferences.
• Key elements to defining a game are players, possible moves/strategies, and utilities/payoffs for each outcome.
• Algorithmic game theory combines game theory and computer science to address the limitations of perfect rationality assumptions in real-world scenarios.

Core Game Theory Concepts

Strategies

• Pure Strategy: A deterministic approach for an agent to select an action.
• Mixed Strategy: A probability distribution over pure strategies for an agent's actions.

Dominance

• Strictly Dominant Strategy: Guarantees a higher payoff, regardless of other players' choices.
• Weakly Dominant Strategy: Provides at least as high a payoff as any other strategy, with the potential for a higher payoff in some situations.

Equilibrium and Optimality

• Nash Equilibrium: A stable set of strategies where no player benefits from changing their strategy unilaterally.
• Pareto Optimality: An outcome where no player can be made better off without making another player worse off.
• Social Welfare: The sum of all players' utilities in a game outcome.

Key Algorithmic Game Theory Topics

• Efficient Computation: Focuses on efficiently finding game-theoretic solution concepts like Nash equilibrium.
• Mechanism Design: Focuses on designing games or protocol's to achieve desired outcomes, even when players are working in self-interest.
• Price of Anarchy: Measures the inefficiency of equilibria by comparing them to optimal outcomes.

Data Structures and Algorithms

• A data structure is an organized method for storing and managing data.
• An algorithm is a step-by-step instruction set to solve a certain problem.
• Together they enable efficient data processing and problem-solving.

Programming Languages

• Programming languages comprise formal languages for formulating data structures and algorithms that a computer can execute.
• These languages consist of syntactical text patterns and semantics, which allows a computer to follow human direction.

Formal Languages

• Formal languages consist of symbols, rules, and structures used to describe and analyze syntax and semantics in computer science.
• Syntax refers to a rule system for the composition of natural and formal languages.
• Semantics is the study of the meaning of symbols.

Compilers, Binary Code and Source Code

• Compilers change source-code into machine or another compiler language
• Binary code represents a system, coding machine data using 0's and 1's in computers
• Source code is is code in a programming language

Imperative and Object-Oriented Programming

• Imperative languages consist are instructions that a computer should execute, examples include ALGOL, BASIC, Fortran, Pascal, Ada
• Object oriented languages use basic structures of a software in way that reflects the real world examples include: Java, Python, C++, ActionScript, AppleScript, Kotlin, Ruby and PHP

Concepts of Object Oriented Programming

• Object: An element that has a state, behaviors, and an identify
• Class: An abstract model that defines attributed and behaviors for objects, these classes can be inherited
• Method: It is a function that changes the status of an object

Machine, Assmbler, and Higher Level Languages

• Machine language allows communication with the computer at a hardware level, although is error-prone
• Assembler is a version of machine language that builds on codes
• Higher Level languages need a computer or compiler to be translated into machine language, and can be adapted to human habits

Data Structures Overview

• Store values in memory
• Basic data-types like int can be stored
• Index always starts with 0 in Informatics

Data Structure Types

• Tuple: data structures that store several values such as ("a,b,c")
• Array (Field): data structure that stores multiple variables of the same data type
• List: Data structures that store data types next to each other, can be concatenated such as: [1,2,3,4,5], ['green', 'rot', 'gold', 'lila']

Price of Anarchy in Selfish Routing

Model Setup

• Involves $n$ players controlling small traffic amounts across a network between source and destination.
• Each player aims to minimize their route travel duration through the system.
• Edge latency varies with traffic volume.

Wardrop Equilibrium

• Characterized by stable traffic flow, where no player can cut travel time through route changes alone.
• In this state, all paths used have equal latency, while unused paths exhibit greater latency.

Social and Economic Impact

• Social Cost measures average travel time, reflecting players’ total latency.
• Price of Anarchy quantifies equilibrium inefficiency versus optimal flow.
• Braess's Paradox illustrates that adding network edges can degrade equilibrium social cost.

Future Directions

• Research efforts include limiting anarchy costs for various latency profiles, designing mechanisms for better traffic management.

Explore algorithmic game theory, combining game theory and computer science to model strategic interactions. Learn about pure and mixed strategies, dominance, and Nash equilibrium. Understand key concepts in multi-agent systems.