Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Farkas' Lemma: Applications in Game Theory

In course

MATH-261: Discrete optimization

This course is an introduction to linear and discrete optimization. Warning: This is a mathematics course! While much of the course will be algorithmic in nature, you will still need to be able to prove theorems. ...

Description

This lecture covers Farkas' Lemma, which states that for a given matrix A, exactly one of two conditions holds: there exists a vector x > 0 such that Ax = b, or there exists a vector such that ATx > 0 and 1.5 < 0. The lecture then delves into certificates, hyperplane separation, and the application of Farkas' Lemma in combinatorics and game theory. In the context of game theory, the lecture explores how mixed strategies can be used to determine the probability of a goal in a penalty kick scenario, emphasizing the strategic decision-making process between the goalie and the striker.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Instructors (2)

Friedrich Eisenbrand

Friedrich Eisenbrand's main research interests lie in the field of discrete optimization, in particular in algorithms and complexity, integer programming, geometry of numbers, and applied optimization. He is best known for his work on efficient algorithms for integer programming in fixed dimension and the theory of cutting planes, which are an important tool to solve large scale industrial optimization problems in practice. Before joining EPFL in March 2008, Friedrich Eisenbrand was a full professor of mathematics at the University of Paderborn. Friedrich received the Heinz Maier-Leibnitz award of the German Research Foundation (DFG) in 2004 and the Otto Hahn medal of the Max Planck Society in 2001.

Rom Pinchasi

Official source

Related concepts (28)

Hyperplane separation theorem

In geometry, the hyperplane separation theorem is a theorem about disjoint convex sets in n-dimensional Euclidean space. There are several rather similar versions. In one version of the theorem, if both these sets are closed and at least one of them is compact, then there is a hyperplane in between them and even two parallel hyperplanes in between them separated by a gap. In another version, if both disjoint convex sets are open, then there is a hyperplane in between them, but not necessarily any gap.

Convex cone

In linear algebra, a cone—sometimes called a linear cone for distinguishing it from other sorts of cones—is a subset of a vector space that is closed under positive scalar multiplication; that is, C is a cone if implies for every positive scalar s. When the scalars are real numbers, or belong to an ordered field, one generally calls a cone a subset of a vector space that is closed under multiplication by a positive scalar.

Linear combination

In mathematics, a linear combination is an expression constructed from a set of terms by multiplying each term by a constant and adding the results (e.g. a linear combination of x and y would be any expression of the form ax + by, where a and b are constants). The concept of linear combinations is central to linear algebra and related fields of mathematics. Most of this article deals with linear combinations in the context of a vector space over a field, with some generalizations given at the end of the article.

Certificate authority

In cryptography, a certificate authority or certification authority (CA) is an entity that stores, signs, and issues digital certificates. A digital certificate certifies the ownership of a public key by the named subject of the certificate. This allows others (relying parties) to rely upon signatures or on assertions made about the private key that corresponds to the certified public key. A CA acts as a trusted third party—trusted both by the subject (owner) of the certificate and by the party relying upon the certificate.

Linear span

In mathematics, the linear span (also called the linear hull or just span) of a set S of vectors (from a vector space), denoted span(S), is defined as the set of all linear combinations of the vectors in S. For example, two linearly independent vectors span a plane. The linear span can be characterized either as the intersection of all linear subspaces that contain S, or as the smallest subspace containing S. The linear span of a set of vectors is therefore a vector space itself. Spans can be generalized to matroids and modules.

Related lectures (30)

SSL Certificates: Understanding and Python Implementation

Delves into SSL certificates, Python implementation, and root certificate chains.

TLS and Certificate Authorities

Explores the evolution of TLS protocols, the role of certificate authorities, vulnerabilities in outdated encryption, and real-world certificate-related attacks.

SSL Certificates: Understanding and Python Implementation

Explores SSL certificates, their analysis in browsers and Python, and root certificate chain retrieval.

TLS: Understanding Certificates and Python Implementation

Explores TLS certificates in web browsers and Python, covering verification, root and intermediate certificates, and Python code for analysis.

Linear Independence and Basis