Strategic Analysis of Coloring, Network Formation, and Information Gathering Games
Coloring Game
Best Response in Polynomial Time
Definition of Best Response:
BR(s−i) = {ai ∈ Ai | ui(s−i , ai) = max (a’i∈Ai) (ui(s−i , a’i )} where:
- Ai is the set of actions for player i.
- ui(s−i , ai) is the utility for player i if all players except i play s−i and i plays ai.
In this game, the utility of a player p is equal to the number of neighbors of p that have the same color as p. A strategy profile s−p fixes the strategies of all other players. This means that their colors are fixed.
Read MoreEssential Bash Commands and C++ Fundamentals
Essential Bash Commands
- Use which -a to find the path to the Bash shell.
- Use echo -n to avoid trailing newlines.
- ls -l lists the content in long format.
- ls -a lists all content, including hidden files.
- ls -la combines both.
- pwd prints the current directory.
- Use man x to view the manual of command x.
- Use ~ to navigate to the home directory.
- mkdir creates directories.
- Multiple directories can be created at once by typing them in the same line.
- rmdir deletes an empty directory.
- rm -rf deletes a non-empty directory.
Networking Fundamentals: TCP/IP, Topologies, and Protocols
Understanding Connectionless Packet-Switched Networks
A connectionless packet-switched network transmits data as independent packets without establishing a dedicated connection. Each packet may take a different path, optimizing network resources and routing flexibility.
Operation:
- Packet Creation: Data is divided into packets, each with a header (addressing information) and payload (data).
- Routing: Routers determine paths for each packet based on destination addresses and network conditions.
- Transmission:
Internet Routing and Data Link Layer Protocols: Core Concepts
Goal of Routing
Each router finds a path or route to every destination and produces a forwarding table. Outcome: Packets follow computed paths if each router forwards according to its table.
Network State
Represents the set of functioning links and routers at a given time. Routing adapts to dynamic changes (e.g., link or router failures) by recomputing routes based on the current network state.
Local vs. Global Views
- Global View: The network state represents an overall view used to compute paths.
- Local
Networking Fundamentals: From Basics to Advanced Concepts
Chapter 2: Elements of Network Communication
- Elements of Communication
- Segmentation and Multiplexing
- Network Components: Devices (end and intermediary), facilities, and services
- LAN, WAN, and Internet
- Protocol Suite: Collection of protocols
- Models Based on Protocol Layers: Advantages
- Difference Between Model and Reference Model Protocol
- OSI Model and TCP/IP: Layers, encapsulation, differences
- PDU: Protocol Data Unit names for each layer
- Routing Mechanisms: How messages are routed in each layer
Chapter 3: Application
Read MoreGraph Algorithms: Depth-First Search, Bellman-Ford, and Euler
Depth-First Search (DFS)
Code:
def _dfs(G, node, verts):
# Add node to visitedverts.add(node)# For each neighborfor neigh in G[node]:# If neighbor not visitedif neigh not in verts:# Start exploration from neighborverts = _dfs(G, neigh, verts)return verts
Connected Components
Code:
def cnx(G):
components = []visited = set()# For every node (so we guarantee that every node is visited even if not connected)for node in G:if node in visited: continue # If already visited, next# Explore (e.g. with DFS) from