Search for notes by fellow students, in your own course and all over the country.
Browse our notes for titles which look like what you need, you can preview any of the notes via a sample of the contents. After you're happy these are the notes you're after simply pop them into your shopping cart.
Title: Mathematics of Operational Research - 2016 Notes
Description: University of Cambridge - Part III Mathematics/Certificate of Advanced Study in Mathematics/Masters of Mathematics Mathematics of Operational Research: notes, based on lectures notes by Richard Weber, the book Introduction to Linear Optimization and the book Games, Theory and Applications, by L.C. Thomas. Covering optimization (including primal simplex, dual simplex and integer linear programming), algorithms on graphs, a very short section on complexity theory, game theory (zero-sum games, non-zero-sum games, cooperative games, bargaining, market games and evolutionary games) and regret minimization. An example of using Gomory's Cutting Plane method to solve an integer linear program.
Description: University of Cambridge - Part III Mathematics/Certificate of Advanced Study in Mathematics/Masters of Mathematics Mathematics of Operational Research: notes, based on lectures notes by Richard Weber, the book Introduction to Linear Optimization and the book Games, Theory and Applications, by L.C. Thomas. Covering optimization (including primal simplex, dual simplex and integer linear programming), algorithms on graphs, a very short section on complexity theory, game theory (zero-sum games, non-zero-sum games, cooperative games, bargaining, market games and evolutionary games) and regret minimization. An example of using Gomory's Cutting Plane method to solve an integer linear program.
Document Preview
Extracts from the notes are below, to see the PDF you'll receive please use the links above
Mathematics of Operational Research
Contents
Table of Contents
i
Schedules
v
1 Lagrangian Methods
1
...
1
...
1
...
1
1
3
3
2 Convex and Linear Optimization
2
...
2
...
2
...
2
...
2
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
6
6
7
8
9
9
Simplex Algorithm
Basic solutions
...
The simplex method in tableau form
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
1 The two-phase simplex method
...
2 The dual simplex method
...
3 Gomory’s cutting plane method
...
1 Theory of algorithmic complexity
...
2 P, NP, and polynomial-time reductions
...
3 Some NP-complete problems
...
1 A lower bound for the simplex method
...
2 The idea for a new method
...
1 Ellipsoid method
...
1
3
...
3
3
...
5
...
...
...
...
...
7
...
3
Proof of correctness
...
8 Optimization in Networks
8
...
8
...
8
...
8
...
8
...
6 Longest path problem
...
...
...
...
1 Transportation problem
...
2 Network simplex method in tableau form
...
3 Assignment problem
...
1 Maximum flow problem
...
2 Max-flow min-cut theorem
...
3 The Ford-Fulkerson algorithm
...
4 Applications of the max-flow min-cut theorem
...
5 A polynomial-time algorithm for the assignment problem
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
44
44
44
45
46
48
11 Shortest Paths and Minimum Spanning
11
...
11
...
11
...
11
...
Trees
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
50
50
51
51
53
12 Semidefinite Programming
12
...
2 Semidefinite programming problem
12
...
12
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
1 Knapsack problem
...
2 Branch and bound technique
...
3 Dakin’s method
...
1 The travelling salesman problem
14
...
14
...
14
...
63
63
64
64
65
...
...
...
...
...
...
...
...
ii
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
14
...
67
15 Non-cooperative Games
15
...
15
...
15
...
68
68
70
71
16 Solution of Two-person Games
16
...
16
...
16
...
16
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
1 Linear complementarity problem
...
2 Quadratic programming as a LCP
17
...
17
...
17
...
17
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
78
78
78
79
79
80
82
18 Cooperative Games
18
...
18
...
18
...
18
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
1 The Shapley value
...
2 Shapley value in terms of objections
19
...
19
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
87
87
87
88
88
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
objections
...
...
...
1 Social welfare functions
...
2 Social choice functions
...
3 Strategic manipulation
...
4 Alternative proof of Gibbard-Satterthwaithe
21 Auctions
99
21
...
99
21
...
100
21
...
102
22 Optimal Auctions
104
iii
22
...
2
22
...
4
Revelation principle
...
Heterogenous bidders
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
1 Paying for a club good
...
2 Ex-post budget balance
...
3 Refining a mechanism design
...
iv
Mathematics of Operational Research
In these notes I attempt a ‘Goldilocks path’ by being neither too detailed or too brief
...
• Each lecture has a title and focuses upon just one or two ideas
...
Schedules
• Lagrangian sufficiency theorem
...
Supporting hyperplane theorem
...
Lagrangian necessity
...
Linear program duality
...
Complementary slackness
...
Two-phase method
...
Gomory’s cutting
plane method
...
NP-completeness
...
Polynomial time algorithms for linear programming
...
Network simplex algorithm
...
Shortest paths and
minimum spanning trees
...
Hungarian
algorithm
...
Max-cut problem
...
[5]
• Branch and bound
...
Exact, approximate, and heuristic methods for
the travelling salesman problem
...
[2]
• Cooperative and non-cooperative games
...
Two-player zerosum games
...
Lemke-Howson algorithm
...
Complementary pivoting
...
[3]
• Cooperative and coalitional games, core, nucleolus, Shapley value
...
Social choice
...
Gibbard-Satterthwaite theorem
...
Mechanism design
...
Incentive compatibility
...
Mechanisms with
payments
...
(1
...
1
...
It consists of a vector x ∈ Rn of decision variables, an objective function f :
Rn → R, a functional constraint h(x) = b where h : Rn → Rm and b ∈ Rm , and a
regional constraint x ∈ X where X ⊆ Rn
...
A vector x∗ is called optimal if it is in the
feasible set and minimizes f among all vectors in the feasible set
...
1
...
The idea is to reduce constrained optimization to unconstrained optimization, and to take the (functional) constraints into account by augmenting the objective function with a weighted sum of them
...
1) as
L(x, λ) = f (x) − λT (h(x) − b),
where λ ∈ R
m
(1
...
The following result provides a condition under which minimizing the Lagrangian, subject only to the regional constraints, yields a solution to the original constrained problem
...
Theorem 1
...
Suppose x ∈ X and λ ∈ Rm such
that L(x, λ) = inf x0 ∈X L(x0 , λ) and h(x) = b
...
1)
...
We have that
min f (x0 ) = 0min [f (x0 ) − λT (h(x0 ) − b)]
x0 ∈X(b)
x ∈X(b)
≥ min
[f (x0 ) − λT (h(x0 ) − b)]
0
x ∈X
= f (x) − λT (h(x) − b) = f (x)
...
The inequality
on the second line holds because the minimum is taken over a larger set
...
Two remarks are in order
...
Second, if we wish to find an optimal solution our general strategy is to minimize L(x, λ)
for all values of λ, in order to obtain a minimizer x∗ (λ) that depends on λ, and then
find λ∗ such that x∗ (λ∗ ) satisfies the constraints
...
Example 1
...
Consider minimizing x21 + x22 subject to a1 x1 + a2 x2 = b and x1 , x2 ≥ 0
for some a1 , a2 , b ≥ 0
...
Taking partial derivaties reveals that it has a unique stationary point at (x1 , x2 ) =
(λa1 /2, λa2 /2)
...
Since since ∂ 2 L/∂ 2 x21 > 0, ∂ 2 L/∂ 2 x22 > 0,
and ∂ 2 L/(∂x1 ∂x2 ) = 0 for this value of λ, we have found a minimum, having value
b2 /(a21 + a22 ) at (x1 , x2 ) = (a1 b, a2 b)/(a21 + a22 )
...
3)
we proceed as follows:
1
...
2
...
3
...
4
...
e
...
(1
...
Find λ∗ ∈ Y so that (x∗ (λ∗ ), z ∗ (λ∗ )) is feasible, i
...
so x∗ (λ∗ ) ∈ X, z ∗ (λ∗ ) ≥ 0,
and h(x∗ (λ∗ )) + z ∗ (λ∗ ) = b
...
2, x∗ (λ∗ ) is optimal for (1
...
2
1
...
Denote by φ(b) = inf x∈X(b) f (x) the solution of (1
...
e
...
x∈X
Then, for all λ ∈ Rm ,
inf f (x) =
x∈X(b)
inf L(x, λ) ≥ inf L(x, λ) = g(λ),
x∈X
x∈X(b)
(1
...
e
...
1)
...
This motivates the dual problem, defined as
maximize
g(λ)
subject to λ ∈ Y,
where Y = {λ ∈ Rm : g(λ) > −∞}
...
1) is called the primal problem
...
5) is a proof of the weak duality theorem, which states that
inf f (x) ≥ max g(λ)
...
1) is said to satisfy strong duality if this holds with equality,
i
...
if there exists λ such that
φ(b) = g(λ)
...
1) can be solved using the method of Lagrangian multipliers
...
1
...
1
...
Theorem 1
...
The following are equivalent:
1
...
the problem satisfies strong duality
...
Suppose there exists a supporting hyperplane to φ at b
...
Now suppose that the problem satisfies strong duality
...
This describes a supporting hyperplane to φ at b
...
Consider the hyperplane given by α : Rm → R with
α(c) = β − λT (b − c)
...
We now try to find φ(b) as follows:
1
...
2
...
This is the dual problem, since
g(λ) = inf L(x, λ)
x∈X
f (x) − λT (h(x) − b)
c∈R x∈X(c)
= infm φ(c) − λT (c − b)
c∈R
= sup β : β − λT (b − c) ≤ φ(c) for all c ∈ Rm
= infm inf
= βλ
We again see the weak duality result as maxλ βλ ≤ φ(b), and that equality holds if
there is a supporting hyperplane to φ at b
...
4
φ(c)
φ(c)
α(c) = βλ − λT (c − b)
α(c) = βλ − λT (c − b)
βλ
βλ
b
c
c
b
Figure 1: Geometric interpretation of the dual with optimal value g(λ) = βλ
...
In the situation on the right,
strong duality does not hold, and βλ < φ(b)
...
Consider Pb when f (x) = −x, and in two cases
√
(a) h(x) = x, b = 2;
(b) h(x) = x2 , b = 16
...
2
...
, an > 0,
minimize
−
Pn
i=1
log(ai + xi )
subject to x1 ,
...
The optimal x corresponds to one that can be found by a so-called ‘water filling
algorithm’
...
Draw a
picture to illustrate this idea
...
1
Convex and Linear Optimization
Convexity and strong duality
A set S ⊆ Rn is convex set if for all δ ∈ [0, 1], x, y ∈ S implies that δx + (1 − δ)y ∈ S
...
A point x ∈ S is called an extreme point of S
if for all y, z ∈ S and δ ∈ (0, 1), x = δy + (1 − δ)z implies that x = y = z
...
The set of all interior points of S is called the interior of S
...
The following result gives a sufficient condition for this
...
1 (Supporting Hyperplane Theorem)
...
Then there exists a (nonvertical) supporting hyperplane to φ at b
...
The following identifies a condition that guarantees convexity of φ
...
2
...
Suppose X, f and h are convex
...
Proof
...
Further consider x1 ∈ X(b1 ), x2 ∈ X(b2 ), and let x = δx1 +(1−δ)x2
...
Thus x ∈ X(b), and by convexity of f ,
φ(b) ≤ f (x) = f (δx1 + (1 − δ)x2 ) ≤ δf (x1 ) + (1 − δ)f (x2 )
...
Observe that an equality constraint h(x) = b is equivalent to constraints h(x) ≤ b and
−h(x) ≤ −b
...
6
2
...
It has the form
minimize
cT x
subject to aTi x ≥ bi ,
aTi x
aTi x
i ∈ M1
≤ bi ,
i ∈ M2
= bi ,
i ∈ M3
xj ≥ 0,
j ∈ N1
xj ≤ 0,
j ∈ N2
where c ∈ Rn is a cost vector, x ∈ Rn is a vector of decision variables, and constraints
are given by ai ∈ Rn and bi ∈ R for i ∈ {1,
...
Index sets M1 , M2 , M3 ⊆ {1,
...
, n} are used to distinguish between different types of constraints
...
−
Each occurrence of an unconstrained variable xj can be replaced by x+
j + xj , where
+
−
+
−
xj and xj are two new variables with xj ≥ 0 and xj ≤ 0
...
1)
where x, c ∈ Rn , b ∈ Rm , and A ∈ Rm×n
...
A linear program of the form
min {cT x : Ax = b, x ≥ 0}
(2
...
The standard form is of course a special case of the
general form
...
The general form is typically used to discuss the theory of linear programming, while the
standard form is more convenient when designing algorithms for linear programming
...
3
...
The feasible set is shaded
...
The
optimal value over the feasible set is attained at point C
...
3
2
...
1) and introduce slack variables z to turn it into
min {cT x : Ax − z = b, x, z ≥ 0}
...
The Lagrangian is given by
L((x, z), λ) = cT x − λT (Ax − z − b) = (cT − λT A)x + λT z + λT b
and has a finite minimum over X if and only if
λ ∈ Y = {µ ∈ Rm : cT − µT A ≥ 0, µ ≥ 0}
...
(x,z)∈X
We obtain the dual
max {bT λ : AT λ ≤ c, λ ≥ 0}
...
3)
T
T
The dual of (2
...
This differs
from (2
...
8
2
...
Complementary slackness requires that slack
does not occur simultaneously in a variable, of the primal or dual, and the corresponding
constraint, of the dual or primal
...
It is not hard to see that complementary slackness is a necessary condition
for optimality
...
Recall that the
variables of the dual correspond to the Lagrange multipliers
...
Theorem 2
...
Let x and λ be feasible solutions for the primal (2
...
3),
respectively
...
e
...
(2
...
Since x and λ are feasible, (2
...
But this is equivalent to cT x = λT b, which holds if and only if x and λ are optimal
...
5
Shadow prices
A more intuitive understanding of Lagrange multipliers can be obtained by again
viewing (1
...
As before, let
φ(b) = inf{f (x) : h(x) ≤ b, x ∈ Rn }
...
Theorem 2
...
Suppose that f and h are continuously differentiable on Rn , and that
there exist unique functions x∗ : Rm → Rn and λ∗ : Rm → Rm such that for each
b ∈ Rm , h(x∗ (b)) = b and f (x∗ (b)) = φ(b) = inf{f (x) − λ∗ (b)T (h(x) − b) : x ∈ Rn }
...
∂bi
Proof
...
9
Taking partial derivatives
n
∂φ(b) X
=
∂bi
j=1
∂h ∗
∂f ∗
(x (b)) − λ∗ (b)T
(x (b))
∂xj
∂xj
−
∂x∗j
(b)
∂bi
∂λ∗ (b)T
∂b
(h(x∗ (b)) − b) + λ∗ (b)T
...
The second term is zero as well, because x∗ (b) is feasible and
thus (h(x∗ (b)) − b) = 0
...
This result continues to hold when the functional constraints are inequalities: h(x) ≤ b
...
Also, λ∗ (b) ≤ 0
...
5, Lagrange multipliers are also known as shadow prices, due
to an economic interpretation of the problem to
maximize f (x)
subject to h(x) ≤ b
x ∈ X
...
Vector
b ∈ Rm describes the amount of each raw material available to the firm, vector x ∈ Rn
the quantity produced of each good
...
The goal in the above problem thus
is to maximize the profit of the firm for given amounts of raw materials available to
it
...
e
...
In this context, complementary
slackness corresponds to the basic economic principle that a particular raw material has
a non-zero price if and only if it is scarce, in the sense that increasing its availability
would increase profit
...
1
The Simplex Algorithm
Basic solutions
In the LP of Example 2
...
This was not a coincidence
...
(3
...
e
...
Each level set of the objective function cT x, i
...
each set Lα = {x ∈ Rn : cT x = α} of
points for which the value of the objective function is equal to some constant α ∈ R, is
a k-dimensional flat for some k ≤ n
...
If such a value exists, the intersection contains
either a single point or an infinite number of points, and it is guaranteed to contain an
extreme point of the feasible set
...
f (x) = α∗
f (x) = α
f (x) = α∗
f (x) = α
Figure 3: Illustration of linear programs with one optimal solution (left) and an infinite
number of optimal solutions (right)
The geometric characterization of extreme points, as points that cannot be written as a
convex combination of two different points, is somewhat hard to work with
...
To this end, consider the following
LP in standard form, which can be obtained from (3
...
2)
where A ∈ Rm×n and b ∈ Rm
...
A solution x ∈ Rn
of the equation Ax = b is called basic if the size of its support is no more than m, i
...
if there exists a set B ⊆ {1,
...
The set B
is then called basis, and variable xi is called basic if i ∈ B and non-basic if i ∈
/ B
...
2)
...
From now on, we make the following assumptions, which are without loss of generality
...
(ii) Every set of m columns of A are linearly independent
...
3
...
Theorem 3
...
A vector is a basic feasible solution of Ax = b if and only if it is an
extreme point of the set X(b) = {x : Ax = b, x ≥ 0}
...
Suppose x is not a BFS
...
But then x is the midpoint of x + y and x − y, both of which lie in X(b)
for small enough non-zero
...
Suppose x is not an extreme point, so that x = δy+(1−δ)z for some distinct y, z ∈ X(b)
...
So A(y − z) = 0, with S (y − z) ⊆ S (x)
...
When looking for an optimum, we can restrict our attention basic feasible solutions
...
2
...
2) is feasible and bounded, then it has an
optimal solution that is a basic feasible solution
...
Suppose x is an optimal solution of (3
...
Suppose
x = δy + (1 − δ)z for some distinct y, z ∈ X(b)
...
Consider x0 = δ 0 y + (1 − δ 0 )z = z + δ 0 (y − z)
...
Now by thinking
about increasing δ 0 from 0 until some component of x0 hits 0, we see that for some δ 0 ,
S (x0 ) ⊂ S (x)
...
We can
continue this way until we obtain an optimal solution that is an extreme point
...
However, this
would not be efficient, as the number of basic solutions may grow exponentially in the
number of variables
...
12
3
...
Let A ∈ Rm×n , b ∈ Rm , and x ∈ Rn such that Ax = b
...
e
...
, n} with |B| = m, corresponding to a choice of m non-zero variables
...
Moreover, if x is a basic solution,
then there is a basis B such that xN = 0 and AB xB = b, and if x is a basic feasible
solution, there is a basis B such that xN = 0, AB xB = b, and xB ≥ 0
...
Suppose that we want to maximize cT x and find that
cTN − cTB A−1
B AN ≤ 0
and A−1
B b ≥ 0
...
3)
Then, for any feasible x ∈ Rn , it holds that xN ≥ 0 and therefore f (x) ≤ cTB A−1
B b
...
It must therefore be optimal
...
Either this can be done indefinitely, which means that
the maximum is unbounded, or the constraints force some of the variables in the basis
to become smaller and we have to stop when the first such variable reaches zero
...
Assuming that the LP is feasible and has a bounded optimal solution, there exists
a basis B ∗ for which (3
...
The basic idea behind the simplex method
is to start from an initial BFS and then move from basis to basis until B ∗ is found
...
For a given basis B, it takes the following form:1
1 The columns of the tableau have been permuted such that those corresponding to the basis appear
on the left
...
13
n−m
m
z
m
1
}|
B
{z
}|
N
1
{z
}|
A−1
B AB = I
A−1
B AN
A−1
B b
cTB − cTB A−1
B AB = 0
cTN − cTB A−1
B AN
−cTB A−1
B b
{
The first m rows consist of the matrix A and the column vector b, multiplied by the
−1
inverse of AB
...
The first n columns of the last row are
equal to cT − λT A for λT = cTB A−1
B
...
In the last column of the last row we finally
have the value −f (x), where x is the BFS with xB = A−1
B b and xN = 0
...
As a consequence it also maintains complementary slackness for x and λT = cTB A−1
B :
since we work with an LP in standard form, λT (Ax − b) = 0 follows automatically from
the feasibility condition, Ax = b; the condition (cT − λT A)x = 0 holds because xN = 0
and cTB −λT AB = cTB −cTB A−1
B AB = 0
...
3) to become satisfied
is that cT − λT A ≤ 0, i
...
that λ is a feasible solution for the dual
...
4
...
4
The simplex method in tableau form
Consider a tableau of the following form, where the basis can be identified by the
identity matrix embedded in (aij ):
(aij )
ai0
a0j
a00
The simplex method then proceeds as follows:
1
...
2
...
If yes, the current solution is optimal, so stop
...
Choose j such that a0j > 0, and choose i ∈ {i0 : ai0 j > 0} to minimize ai0 /aij
...
If multiple rows
minimize ai0 /aij , the problem has a degenerate BFS
...
Update the tableau by multiplying row i by 1/aij and adding a −(akj /aij ) multiple of row i to each row k 6= i
...
14
We will now describe the different steps of the simplex method in more detail and
illustrate them using the LP of Example 2
...
Finding an initial BFS
Finding an initial BFS is very easy when the constraints are of the form Ax ≤ b for b ≥ 0
...
Alternatively
one may think of extending x to (x, z) and setting (xB , xN ) = (z, x) = (b, 0)
...
For
the LP of Example 2
...
We will discuss this case in the next lecture
...
Otherwise we can choose a
column j such that a0j > 0 as the pivot column and let the corresponding variable
enter the basis
...
The candidate variables in our example are x1
and x2 , so let us choose x1
...
Choosing the pivot row
If aij ≤ 0 for all i, then the problem is unbounded and the objective can be increased
by an arbitrary amount
...
This row is called the pivot row, and aij is called the pivot
...
In our example there is a unique
choice, namely variable z2
...
Pivoting
The purpose of the pivoting step is to get the tableau into the appropriate form for the
new BFS
...
Our choice of the pivot row as a row that
minimizes ai0 /aij turns out to be crucial, as it guarantees that the solution remains
feasible after pivoting
...
We are now ready to choose a new pivot column
...
All entries in the last row are non-positive, so this solution is optimal
...
5
Degeneracies and cycling
In the absence of degeneracies, the value of the objective function increases in every
iteration of the simplex method, and an optimal solution or a certificate for unboundedness is found after a finite number of steps
...
This would obviously cause the value of the objective function to remain the same
as well, and the simplex method may in fact cycle indefinitely through a number of
bases that all represent the same BFS
...
Bland’s rule achieves this by fixing some ordering of the variables and then
choosing, among all variables that could enter and leave in a given iteration, those that
are minimal according to the ordering
...
1
The two-phase simplex method
The LP we solved in the previous lecture allowed us to find an initial BFS very easily
...
In phase II we then proceed as in the previous lecture
...
Unfortunately, the basic solution with x1 = x2 = 0, z1 = z2 = −1, and z3 = 2 is
not feasible
...
E
...
,
minimize y1 + y2
subject to x1 + x2 − z1 + y1
2x1 − x2 − z2 + y2
3x2 + z3
x1 , x2 , z1 , z2 , z3 , y1 , y2
=1
=1
=2
≥ 0,
and the goal of phase I is to solve this LP starting from the BFS where x1 = x2 = z1 =
z2 = 0, y1 = y2 = 1, and z3 = 2
...
This automatically gives us an initial BFS for the
original problem
...
Bring the constraints into equality form
...
2
...
3
...
4
...
17
While the original objective is not needed for phase I, it is useful to carry it along as
an extra row in the tableau, because it will then be in the appropriate form at the
beginning of phase II
...
This can be obtained by first writing it in terms of y1 and y2 , such that
we have −1 in the columns for y1 and y2 and 0 in all other columns because we are
maximizing −y1 − y2 , and then adding the first and second row to make the entries
for all variables in the basis equal to zero
...
This ends phase I as y1 = y2 = 0, and we have found a BFS for the original problem
with x1 = z2 = 1, z3 = 2, and x2 = z1 = 0
...
3, which we solved in the previous lecture, augmented by the constraint
3x2 ≤ 2
...
This makes sense because the additional
constraint is not tight in the optimal solution, as we can see from the fact that z3 6= 0
...
2
The dual simplex method
The (primal) simplex method maintains feasibility of the primal solution along with
complementary slackness and seeks feasibility of the dual solution
...
This is known as the dual simplex method
...
Consider the following
LP, to which we have already added slack variables z1 and z2 :
minimize 2x1 + 3x2 + 4x3
subject to x1 + 2x2 + x3 − z1 = 3
2x1 − x2 − 3x3 − z2 = 4
x1 , x2 , x3 , z1 , z2
≥ 0
...
On the other hand, c ≥ 0, so the dual solution
with λ1 = λ2 = 0 satisfies cT − λT A ≥ 0 and is therefore feasible
...
Pivoting then works just
like in the primal algorithm
...
It is worth pointing out that for problems in which all constraints are inequality constraints, the optimal dual solution can also be read off from the final tableau
...
For the same reason, the last m columns of the vector cT are 0
...
In our example, we have λ1 = 8/5 and λ2 = 1/5
...
3
Gomory’s cutting plane method
Another situation where the dual simplex method can be useful is when we need to
add constraints to an already solved LP
...
We can therefore
simply add the constraint and continue running the dual LP algorithm from the current
solution until the primal solution again becomes feasible
...
An IP is a linear program with the additional requirement that
variables should be integral
...
e
...
If x is not integral, there has to be a row i such that ai0 is not
integral, and for every feasible solution x,
X
X
xi +
baij cxj ≤ xi +
aij xj = ai0
...
e
...
If x is integral, the left-hand side is integral as well, and
the inequality must still hold if the right-hand side is rounded down
...
j∈N
This inequality is satisfied by every (integral) feasible solution, but not by the current
solution x∗ , for which x∗i = ai0
...
The idea behind the
cutting plane method is to iteratively add cutting planes and solve the resulting linear
programs using the dual simplex algorithm
...
Consider again the final tableau on Page 20, and assume we now want an integral
solution
...
We turn this into an equality constraint using a new slack variable, add it to the tableau,
and bring it into the right form by subtracting the first constraint from it, obtaining
0
1
1
− 25
− 15
− 35
8
5
1
0
−1
0
0
0
0
0
3
1
5
− 52
− 51
1
5
0
0
1
0
2
5
11
5
− 52
− 28
5
After one more round of the dual simplex algorithm we reach the optimal integral
solution with x1 = 3 and x2 = x3 = 0:
0
1
1
−1
0
1
0
1
0
−1
1
0
−2
3
0
0
0
3
1
−5
2
0
0
3
1
0
1
−6
21
5
Complexity of Algorithms
We have seen that the simplex algorithm inspects basic feasible solutions and is guaranteed to find an optimal solution after a finite number of steps
...
It is therefore an interesting question
whether there exist cases where the simplex algorithm has to look at a significant fraction of the set of all basic feasible solutions
...
Before we pursue this question in the next lecture, we prepare with some theory
of algorithmic complexity
...
1
Theory of algorithmic complexity
Formally, an instance of an optimization problem is given by its input
...
If each real value is represented using at most k bits, the whole instance
can be described by a string of (mn + m + n)k bits
...
A sensible way to define the complexity of a problem is via the complexity of the fastest
algorithm that can solve it
...
The following notation is useful in
this context: given two functions f : N → N and g : N → N, write
• f (n) = O(g(n)) if there exist constants c and n0 such that for every n ≥ n0 ,
f (n) ≤ cg(n),
• f (n) = Ω(g(n)) if there exist constants c and n0 such that for every n ≥ n0 ,
f (n) ≥ cg(n), and
• f (n) = Θ(g(n)) if f (n) = O(g(n)) and f (n) = Ω(g(n))
...
Gaussian elimination, for example, shows that solving a linear system Ax = b with
A ∈ Rn×n has arithmetic complexity O(n3 )
...
5
...
In many
situations of interest, and also in this course, it suffices to study complexity-theoretic
22
questions for decision problems, i
...
problems where the answer is just a single bit
...
One might expect the answer to the question whether a particular problem can be solved
efficiently to depend a lot on the details of the computational model one is using
...
A Turing machine has a
finite number of states, finite control, and a readable and writable tape that can store
intermediary results as strings of bits
...
It then runs for a certain number of steps, and when it halts the
output is inferred from the state or the contents of some designated part of the tape
...
The most important open problem in complexity theory concerns the relationship between the complexity classes P and NP
...
Formally, a function f : {0, 1}∗ → {0, 1}∗ is computable
in polynomial time if there exists a Turing machine M and k ∈ N with the following
property: for every x ∈ {0, 1}∗ , if M is started with input x, then after O(|x|k ) steps it
halts with output f (x)
...
Formally, L ⊆ {0, 1}∗ is in NP if there exists a
Turing machine M and k ∈ N with the following property: for every x ∈ {0, 1}∗ , x ∈ L
if and only if there exists a certificate y ∈ {0, 1}∗ with |y| = O(|x|k ) such that M
accepts (x, y) after O(|x|k ) steps
...
A nondeterministic Turing
machine is a Turing machine that can make a non-deterministic choice at each step of
its computation and is required to accept x ∈ L only for some sequence of these choices
...
Most people believe that it must be strictly harder, i
...
that P 6= NP
...
Intuitively, a reduction from one problem to another transforms every
instance of the former into an equivalent instance of the latter, where equivalence
means that both of them yield the same decision
...
In our case it makes sense to use
reductions that can be computed in polynomial time
...
A problem K is called
NP-hard if for every problem L in NP, L ≤p K
...
The relation ≤p is transitive
...
The existence of NP-complete problems is less
obvious, but holds nonetheless
...
NP-hard
NP-complete
NP
P
Figure 4: Relationship between P, NP, and the sets of NP-hard and NP-complete
problems
...
If it is not, then P = NP
...
We do, however, have to
be a bit careful in interpreting results that use these notions
...
In fact, it does not even have to be the case that an algorithm with a polynomial worstcase running time is better in practice than an algorithm whose worst-case running time
is exponential
...
On the other hand, NP-hardness of
a problem does not mean that it can never be solved in practice, and we will consider
approaches for solving NP-hard optimization problems in a later lecture
...
5
...
A
Boolean formula consists of a set of clauses Ci ⊆ X for i = 1,
...
, xn , x
¯1 ,
...
It is called satisfiable if there exists a set S ⊆ X such that |S ∩ {xj , x
¯j }| ≤ 1 for all j = 1,
...
, m
...
NP-hardness can be shown by encoding the operation of an arbitrary
nondeterministic Turing machine as a Boolean formula
...
1 (Cook, 1971; Levin, 1973)
...
An instance of the 0−1 integer programming problem consists of a matrix A ∈
Zm×n and a vector b ∈ Zm , and asks whether there exists a vector x ∈ {0, 1}n such that
Ax ≥ b
...
Theorem 5
...
0−1 integer programming is NP complete
...
Membership in NP is again easy to see
...
Consider a Boolean formula with literals X = {x1 ,
...
, x
¯n }
and clauses Ci , i = 1,
...
, m and j = 1,
...
Now let A ∈ Zm×n and b ∈ Zm be given by
1 if xj ∈ Ci
for i = 1,
...
, n,
aij = −1 if x
¯ j ∈ Ci
0 otherwise
bi = 1 − |{ j : x
¯j ∈ Ci }|
for i = 1,
...
Intuitively, this integer program represents each Boolean variable by a binary variable,
and each clause by a constraint that requires its literals to sum up to at least 1
...
The above form is then obtained by moving all constants to the right hand side
...
The last problem we consider is the travelling salesman problem (TSP)
...
If the
entries of the matrix A are interpreted as pairwise distances among a set of locations,
we are looking for a tour σ(1) → σ(2) → · · · → σ(n) → σ(1) with length ≤ k that visits
every location exactly once and returns to the starting point
...
e
...
Theorem 5
...
TSP is NP-complete, even if A ∈ {0, 1}n×n symmetric
and k = 0
...
1
Computational Complexity of LP
A lower bound for the simplex method
The complexity of the simplex method depends on two factors, the number of steps in
each round and the number of iterations
...
We will now describe an instance
of the linear programming problem, and a specific pivot rule, such that the simplex
method requires an exponential number of iterations to find the optimal solution
...
This shows
that the simplex method requires an exponential number of iterations in the worst case,
for the specific pivoting rule that follows the spanning path
...
, n
...
Further consider a spanning path of the unit
cube constructed inductively as follows
...
In dimension k, the path starts with xk = 0 and traverses the spanning path
for dimensions x1 to xk−1 , which exists by the induction hypothesis
...
This construction is illustrated of the left of Figure 5
...
This can easily be fixed
...
, n
(6
...
It is easily verified that xn now increases
strictly along the path described above
...
Theorem 6
...
Consider the linear programming problem of maximizing xn subject
to (6
...
Then there exists a pivoting rule and an initial basic feasible solution such
that the simplex method requires 2n − 1 iterations before it terminates
...
Interestingly, the first and last vertices of the spanning paths constructed above are
adjacent, which means that a different pivoting rule could reach the optimal solution in a
single step
...
The diameter of a polytope, i
...
the maximum number of steps necessary to get
from any vertex to any other vertex, provides a lower bound of the number of iterations
of the simplex method that is independent of the pivoting rule
...
Whether the diameter is bounded by a
polynomial function of n and d remains open
...
However, it is not clear how the intuition of a good
average-case performance could be formalized, because this would require a natural
probability distribution over instances of the linear programing problem
...
6
...
2) and its corresponding dual:
min {cT x : Ax = b, x ≥ 0}
max {bT λ : AT λ ≤ c}
...
We can thus concentrate on the following decision problem: given a matrix A ∈ Rm×n
and a vector b ∈ Rm , is the set {x ∈ Rn : Ax ≥ b} non-empty? We will now consider a
method for solving this problem, known as the ellipsoid method
...
A symmetric matrix D ∈ Rn×n is called positive definite
if xT Dx > 0 for all non-zero x ∈ Rn
...
If D ∈ Rn×n is non-singular and b ∈ Rn , then the
mapping S : Rn → Rn given by S(x) = Dx + b is called an affine transformation
...
e
...
The volume of a set L ⊆ Rn is finally defined as
Vol(L) = x∈L dx
...
To decide whether
P is non-empty, the ellipsoid method generates a sequence {Et } of ellipsoids Et with
centers xt
...
If xt ∈
/ P , then
one of the constraints is violated, i
...
there exists a row j of A such that aTj xt < bj
...
The following is the key result underlying the ellipsoid method
...
This situation is illustrated in Figure 6
...
The polytope P
and the half-ellipsoid that contains it are shaded
...
2
...
Consider
the half-space H = {x ∈ Rn : aT x ≥ aT z}, and let
Da
1
√
,
n + 1 aT Da
2 DaaT D
n2
D−
...
Moreover, E ∩ H ⊆ E 0 and Vol(E 0 ) < e−1/(2(n+1)) Vol(E)
...
In the next lecture, this procedure will be turned into
28
an algorithm by observing that the volume of P must either be zero or larger than a
certain threshold that depends on the size of the description of P
...
2
...
Lemma 6
...
Let S : Rn → Rn be an affine transformation given by S(x) = Dx + b
and let L ⊆ Rn
...
Proof sketch of Theorem 6
...
We prove the theorem for E = {x ∈ Rn : xT x ≤ 1} and
H = {x ∈ Rn : x1 ≥ 0}
...
3, relative volume of sets
...
, 0)T
...
n2 i=1 i
n
n2
Consider an arbitrary x ∈ E ∩ H, and observe that 0 ≤ x1 ≤ 1 and
easily verified that x ∈ E 0 and thus E ∩ H ⊆ E 0
...
It is
Now consider the affine transformation F : Rn → Rn given by
e1
+
F (x) =
n+1
n2
2
n −1
I−
2
e1 eT1
n+1
21
x
...
Therefore, by Lemma 6
...
A more detailed description of the ellipsoid method and an overview of the proof of
correctness will be given in the next lecture
...
1
Ellipsoid method
Consider a polytope P = {x ∈ Rn : Ax ≥ b}, given by a matrix A ∈ Zm×n and a vector
b ∈ Zm
...
Here,
P is called full-dimensional if Vol(P ) > 0
...
Let U be the largest absolute value among the entries of A and b, and define
x0 = 0, D0 = n(nU )2n I, E0 = E(x0 , D0 ),
√
2
2
V = (2 n)n (nU )n , v = n−n (nU )−n (n+1) ,
t∗ = d2(n + 1) log(V /v)e
...
For t = 0,
...
If t = t∗ then stop; P is empty
...
If xt ∈ P then stop; P is non-empty
...
Find a violated constraint, i
...
a row j such that aTj xt < bj
...
Let Et+1 = E(xt+1 , Dt+1 ) with
xt+1 = xt +
1
Da
q t j ,
n + 1 aT D a
j
Dt+1
n2
= 2
n −1
t j
2 Dt aj aTj Dt
Dt −
n + 1 aTj Dt aj
!
...
7
...
Given Theorem 6
...
We now show that the above assumptions hold, starting with the inclusion of P in E0
and the volume of E0
...
Lemma 7
...
Suppose A ∈ Zm×n , b ∈ Rm and m ≥ n
...
Then every extreme point x of the polytope P =
{x0 ∈ Rn : Ax0 ≥ b} satisfies −(nU )n ≤ xi ≤ (nU )n for all i = 1,
...
30
Proof
...
By Cramer’s rule,
xi =
det Aˆi
,
det Aˆ
where Aˆi is the matrix obtained by replacing the ith column of Aˆ by ˆb
...
, n,
n
n
X
Y
X Y
i
|σ|
i
ˆ
|ˆ
aij,σ(j) | ≤ n!U n ≤ (nU )n ,
(−1)
a
ˆj,σ(j) ≤
det A =
σ∈Sn
j=1
σ∈Sn i=1
where |σ| is the number of inversions of permutation σ ∈ Sn , i
...
the number of pairs
ˆ 6= 0 since Aˆ is invertible,
i, j such that i < j and σ(i) > σ(j)
...
Therefore, |xi | ≤ (nU )n for all
i = 1,
...
P
If P is bounded and x ∈ P , then i x2i ≤ n(nU )2n and so x ∈ E0
...
We now turn to the lower bound on the volume of P in the case when it is non-empty
...
2
...
Then
2
Vol(P ) > n−n (nU )−n (n+1)
...
If P is full-dimensional and bounded and has at least one extreme point,
it has n + 1 extreme points v 0 ,
...
Let Q
be the convex hull of these extreme points, defined as
(
)
n
n
X
X
n
k
Q= x∈R :x=
λk v ,
λk = 1, λk ≥ 0
...
It can be shown that
1
1 ··· 1
...
1, |qik | ≤ (nU )n
...
n
n
i=1
k=0 (nU )
31
So far we have assumed that the polytope P is bounded and full-dimensional
...
Polytopes that are unbouned By Lemma 7
...
, n}
...
We can therefore test for non-emptiness of PB instead
of P , and PB is a bounded polytope
...
The following result shows, however, that we can slightly perturb P
to obtain a polytope that is either empty or full-dimensional
...
3
...
Let
P = { x ∈ Rn : Ax ≥ b − e}
where
=
1
−(n+1)
((n + 1)U )
2(n + 1)
and eT = (1,
...
Then, P = ∅ if and only if P = ∅, and either P = ∅ or
Vol(P ) > 0
...
We first show that emptiness of P implies emptiness of P
...
Therefore its dual, which is
max{λT b : λT A = 0T , λ ≥ 0}, must be infeasible or unbounded; since it is feasible it
must be unbounded
...
1, λi ≤ ((n + 1)U )
for all i
...
Then λT (b − e) = λT b − i=1 λi ≥ λT b − 21 > 0
...
It remains to be shown that P is full-dimensional if P is non-empty
...
, n
...
Thus P must be
full-dimensional
...
32
7
...
It can further be shown that O(n6 log(nU ))
iterations suffice even when P might be unbounded or not full-dimensional
...
A potential problem is that the computation of the new ellipsoid involves taking
a square root
...
It turns out that the algorithm can be made to work, with the same
asymptotic number of iterations as above, when only O(n3 log U ) bits are used for each
intermediate value
...
The ellipsoid method has high theoretical significance, because it provided the first
polynomial-time algorithm for linear programming and can also be applied to larger
classes of convex optimization problems
...
The latter also has a better worst-case performance than the ellipsoid method
...
1
Optimization in Networks
Graph terminology
A directed graph, or network, G = (V, E) consists of a set V of vertices and a set
E ⊆ V × V of edges
...
The degree
of vertex i ∈ V in graph G is the number |{j ∈ V : (i, j) ∈ E or (j, i) ∈ E}| of other
vertices connected to it by an edge
...
, vk ∈ V such that v1 = u, vk = w, and (vi , vi+1 ) ∈ E for i = 1,
...
In a directed graph, we can also consider an undirected walk where (vi , vi+1 ) ∈ E or
(vi+1 , vi ) ∈ E for i = 1,
...
A walk is a path if v1 ,
...
A graph that does not contain any cycles is called
acyclic
...
A tree is a graph that is connected and acyclic
...
In the special
case where G0 is a tree and V 0 = V , it is called a spanning tree of G
...
2
Minimum cost flow problem
Consider a network G = (V, E) with |V | = n, and let b ∈ Rn
...
If bi > 0, we say
that i is a source supplying bi units of flow
...
Further let C, M , M ∈ Rn×n , where cij denotes the cost
per unit of flow on edge (i, j) ∈ E, and mij and mij respectively denote lower and
upper bounds on the flow across this edge
...
Formally, x ∈ Rn×n is a minimum cost flow
of G if it is an optimal solution of the following optimization problem:
minimize
X
cij xij
(i,j)∈E
subject to bi +
X
xji =
j:(j,i)∈E
X
xij
for all i ∈ V ,
j:(i,j)∈E
mij ≤ xij ≤ mij
for all (i, j) ∈ E
...
We further assume without loss of generality that the network G is connected
...
An important special case is that of uncapacitated flows, where mij = 0 and mij = ∞ for all (i, j) ∈ E
...
Given this rather simple structure, we may hope that minimum cost flow problems are
easier to solve than general linear programs
...
8
...
A solution
x is called a spanning tree solution if the edges of G can be partitioned into three
disjoint sets T, L, U , such that (V, T ) is a spanning tree, and xij = mij if (i, j) ∈ L
and xij = mij if (i, j) ∈ U
...
An example is in Figure 7
...
This network is uncapacitated so L = E \ T and U = ∅,
and flows are zero for edges not in T
...
In this example, the spanning tree corresponds to
a degenerate BFS, because edge (6, 7) carries flow zero
...
Theorem 8
...
A flow vector is a basic solution of a minimum cost flow problem if
and only if it is a spanning tree solution
...
4
The network simplex method
We now derive a variant of the simplex method, the network simplex method, that
works directly with spanning tree solutions
...
Rather, it
uses a separate condition to either establish both dual feasibility and complementary
slackness, and thus optimality, or identify a new spanning tree solution
...
1)
λi bi
i∈V
(i,j)∈E
Let c¯ij = cij − λi + λj be the reduced cost of edge (i, j) ∈ E
...
Minimizing L(x, λ) subject to the regional constraints
mij ≤ xij ≤ mij for (i, j) ∈ E further yields the following complementary slackness
conditions:
c¯ij > 0
implies
xij = mij ,
c¯ij < 0
implies
xij = mij , and
mij < xij < mij
implies
c¯ij = 0
...
Then the
system of equations
λ|V | = 0,
λi − λj = cij
for all (i, j) ∈ T
has a unique solution, which in turn allows us to compute c¯ij for all edges (i, j) ∈ E
...
Pivoting
If c¯ij ≥ 0 for all (i, j) ∈ L and c¯ij ≤ 0 for all (i, j) ∈ U , dual feasibility and the first two
complementary slackness are satisfied as well, meaning that the solution is optimal (by
36
appeal to the Lagrangian sufficiency theorem)
...
Since (i, j) is the only edge in C with non-zero reduced cost, we can decrease
the objective by pushing flow along C to increase xij if c¯ij is negative and decrease xij
if c¯ij is positive
...
Let B, B ⊆ C respectively denote the sets of edges whose flow is to decrease or increase,
and let
(
)
δ = min
min {xk` − mk` }, min {mk` − xk` }
...
If δ = ∞, the problem
is unbounded
...
Otherwise, pushing δ units of flow along C yields a unique edge
(k, `) ∈ C whose flow is either mk` or mk`
...
If instead (k, `) = (i, j), we obtain a new BFS
where (i, j) has moved from U to L, or vice versa
...
6
1
(1, 1, 3)
1
5
3
2
6
1
(2, 0, 3)
2
2
4
1
(3, 3, 7)
(1, 1, 3)
2
0
(3, 3, 7)
4
3
(2, 0, 3)
2
4
Figure 8: Flow network before and after a pivoting step
...
In the situation shown on the left, we have λ3 = 0, λ2 = c23 + λ3 = 2,
and λ1 = c12 + λ2 = 5, and thus c¯13 = c13 − λ1 + λ3 = −4
...
The new situation is
shown on the right
...
Since this is positive and x23 = m23 , we have found an
optimal solution
...
If a degenerate solution is
encountered it will still be possible to identify a new spanning tree or even a new BFS,
but extra care may be required to ensure convergence
...
If this is not the case, we can instead
consider the problem obtained by setting mij to zero, mij to mij − mij , and modifying
bi to bi − mij and bj to bj + mij
...
We now modify the problem such that the set of optimal solutions remains the same,
assuming that the problem was feasible, but an initial feasible spanning tree solution is
easy to find
...
It is easy to see that a dummy edge has positive flow in some optimal solution of the
new problem if and only if the original problem is infeasible
...
8
...
Theorem 8
...
Consider a minimum cost flow problem that is feasible and bounded
...
If cij is integral for all (i, j) ∈ E, then there exists
an integral optimal solution to the dual
...
Later, we investigate linear programming problems subject to the additional constraint
that the solution be in integers
...
However, for network flow problems we get
integer solutions for free
...
6
Longest path problem
The critical path method is an operational research technique dating from the late
1950s
...
It concerns a project consisting
of activities, or jobs
...
Job i has a
duration τi
...
Introduce two additional jobs, s and s0 , each of zero duration, to indicate
38
the start and finish of the project, and introduce edges (s, i) and (i, s0 ) for every job i
...
Suppose we start job i at time ti
...
j
i
start
end
s
s′
Let fij be a Lagrange multiplier for constraint tj − ti ≥ τi
...
This is a minimum cost flow problem with cij = −τi
...
It is the longest path from s to s0 when edges (s, i) and
(i, s0 ) have lengths 0 and each other edge (i, j) has length τi
...
1
Transportation and Assignment Problems
Transportation problem
In the transportation problem we are given a set of suppliers S = {1,
...
, m}, with
n
m
consumer j demanding dj of the good, such that
i=1 si =
j=1 dj
...
This can be
formulated as an uncapacitated minimum cost flow problem on a bipartite network,
i
...
a network G = (S ∪ C, E) with E ⊆ S × C
...
, m
xij = si
for all i = 1,
...
It turns out that transportation problems already capture the full expressiveness of
minimum cost flow problems
...
Theorem 9
...
Every minimum cost flow problem with finite capacities or non-negative
costs has an equivalent transportation problem
...
Consider a minimum cost flow problem on a network G = (V, E) with supplies
or demands bi , capacities mij and mij , and costs cij
...
We can further assume that all capacities are
finite: if some edge has infinite capacity but costs are non-negative
then setting the
P
capacity of this edge to a large enough number, for example i∈V |bi |, does not affect
the optimal solution of the problem
...
For every vertex i ∈ V , we add
P
a sink vertex with demand k mik − bi
...
The situation is shown in Figure 9
...
To see this, suppose {xij } is
40
0
mij
i, j
i
P
mik − bi
j
P
mjk − bj
k:(i,k)∈E
cij
k:(j,k)∈E
Figure 9: Representation of flow conservation constraints by a transportation problem
a feasible flow in the minimum cost flow problem
...
The total flow into vertex i then is
P
P
P
k:(i,k)∈E (mik − xik ) +
k:(k,i)∈E xki , which must be equal to
k:(i,k)∈E mik − bi
...
9
...
, n
and µj for j = 1,
...
...
...
...
...
...
...
...
...
Since
s
=
i
i
j dj , this process is guaranteed to find a
feasible solution, and the corresponding spanning tree consists of the pairs (i, j) that
have been visited
...
In the example, we can start by
setting x11 = min{s1 , d1 } = 6, moving to customer 2 and setting x12 = 2, moving to
supplier 2 and setting x22 = 3, and so forth
...
To determine the values of the dual variables λi for i = 1,
...
, 4,
observe that λi − µj = cij must be satisfied for all (i, j) ∈ T
...
It
will finally be convenient to write down λi − µj for (i, j) ∈
/ T , which we do in the upper
right corner of the respective cells
...
In our example
this condition is violated, for example, for i = 2 and j = 1
...
Due to the special structure of the network, doing so will alternately
42
increase and decrease the flow for edges along the cycle
...
The is shown on the
right of Figure 10
...
Now, c24 < λ2 − µ4 , and we can increase x24 by 7 to obtain the right hand tableau
below, which satisfies cij ≥ λi − µj for all (i, j) ∈
/ T and therefore is optimal
...
3
5
2
0
5
−3
5
3
0
7
−2
6
−7
7
4
7
1
4
2
−5
−9
9
6
6
1
8
0
3
−3
3
0
4
5
2
5
5
−3
5
3
0
7
3
6
−2
2
4
−1
4
8
2
−4
4
6
7
1
1
4
Assignment problem
An instance of the assignment problem is given by n agents and n jobs, and costs cij
for assigning job j to agent i
...
, n
n
X
xij = 1 for all i = 1,
...
1)
j=1
n
X
xij = 1
for all j = 1,
...
All basic solutions of the LP relaxation of this problem, which
is obtained by replacing the integrality constraint xij ∈ {0, 1} by 0 ≤ xij ≤ 1, are
spanning tree solutions and therefore integral
...
This is not necessarily the case, for example, for the
ellipsoid method
...
In the
next lecture we will look at a polynomial time algorithm for solving this problem
...
Lemma 9
...
A feasible solution {xij } to (9
...
43
10
10
...
We will also assume for convenience that mij = 0 for
all (i, j) ∈ E
...
e
...
X
(10
...
Since the new edge (n, 1) has infinite capacity, any feasible flow of the original network
is also feasible for the new network
...
This is called a circulation problem,
because there are no sources or sinks but flow merely circulates in the network
...
2
Max-flow min-cut theorem
Consider a flow network G = (V, E) with capacities Cij for all (i, j) ∈ E
...
Formally, for S ⊆ V , the capacity of the
cut (S, V \ S) is
X
C(S) =
Cij
...
2)
(i,j)∈E∩(S×(V \S))
Assume that x is a feasible flow vector that sends δ units of flow from vertex 1 to
vertex n
...
Indeed, for X, Y ⊆ V , let
X
f (X, Y ) =
xij
...
3)
δ = f (S, V ) − f (V, S)
= f (S, S) + f (S, V \ S) − f (V \ S, S) − f (S, S)
(10
...
The following result states that this upper bound is tight, i
...
there exists a flow of size
equal to the minimum capacity of a cut that separates vertex 1 from vertex n
...
1 (Max-flow min-cut theorem)
...
1)
for a network (V, E) with capacities Cij for all (i, j) ∈ E
...
Proof
...
Consider a feasible flow vector x
...
, vk is called an augmenting path for x if xvi−1 vi < Cvi−1 vi or xvi vi−1 > 0
for every i = 1,
...
If there exists an augmenting path from vertex 1 to vertex n,
then we can push flow along the path, by increasing the flow on every forward edge and
decreasing the flow on every backward edge along the path by the same amount, such
that all constraints remain satisfied and the amount of flow from 1 to n increases
...
By optimality of x, n ∈ V \ S
...
The first equality holds by (10
...
The second equality holds because xji = 0 for
every (j, i) ∈ E ∩ ((V \ S) × S)
...
10
...
Start with a feasible flow vector x
...
If there is no augmenting path from 1 to n, then stop
...
Otherwise pick some augmenting path from 1 to n, and push a maximum amount
of flow along this path without violating any constraints
...
Assume that all capacities are integral and that we start with an integral flow vector,
e
...
, the flow vector x such that xij = 0 for all (i, j) ∈ E
...
The algorithm is therefore guaranteed to find a maximum flow after
finitely many iterations
...
If all capacities are bounded by the integer
U then the running time is O(|E| · |V | · U )
...
4/2
2
4
10/10
s
10/8
2
1
8/8
6/6
10/7
t
6
t
10/9
3
9/7
4/4
2
5
4
10/10
s
6
10/10
2
1
8/6
6/6
10/9
10/9
3
9/9
5
Figure 11: In the first picture the flow is suboptimal, at 17
...
After increasing flow along this path by 2, we reach the optimal
flow assignment
...
The maximum flow is
19, and S = {1, 3}
...
10
...
Here are two
...
Suppose |L| = |R| = n
...
The bipartite graph is said to have a
perfect matching if the size of the maximum matching is n, i
...
every i ∈ L can be
matched with some j ∈ R
...
define N (i) = {j : (i, j) ∈ E} and for X ⊆ L,
N (X) = ∪i∈X N (i)
...
2 (Hall’s theorem)
...
It has a perfect matching if and only if |N (X)| ≥ |X| for every X ⊆ L
...
If a perfect matching exists then clearly |N (X)| ≥ |X| for any X ⊆ L
...
We give the original edges in E capacity ∞ and
the new edges capacity 1
...
By considering
how S is constructed we see that N (L ∩ S) ⊆ R ∩ S
...
The total number of these edges is C(S)
...
Theorem 10
...
In a bipartite graph G = (L ∪ R, E), the maximum
size of a matching is equal to the minimum size of a vertex cover
...
We use the same graph as in the proof of Hall’s theorem
...
When it terminates there will be paths from
s to t, each carrying unit flow and sharing no vertices in E
...
So it remains to show ‘min cut capacity’ ≥ ‘min size vertex cover’
...
This consists
of the unmatched vertices in L and all other vertices that can be reached from these
along augmenting paths
...
Note that C(S) = |W |
...
An edge whose left endpoint is not matched must have its right endpoint in R ∩ S
...
L
s
R
1
10
2
11
3
12
4
13
5
14
6
15
7
16
8
17
9
18
t
Figure 12: The graph used in proof of K¨
onig’s theorem
...
Edges in L × R have capacity ∞
...
The vertices in S (shown black) are those reachable from
s by augmenting paths
...
The six vertices: {1, 2, 3} = L ∩ (V \ S) and {13, 14, 15} = R ∩ S provide a
vertex cover of the edges
...
5
A polynomial-time algorithm for the assignment problem
Recall that in the assignment problem we are to find minimum cost matching in a
weighted complete bipartite graph
...
The weight
on edge (i, j) is cij
...
Let Gλ be the subgraph of G consisting of edges where λi − λj = cij
and their endpoints, named the equality graph
...
5
Step 1
...
Similarly if any j ∈ R is not in the equality graph we can decrease λj until
it becomes so
...
Look for an augmenting path in the equality graph by applying the Ford-Fulkerson
algorithm to the same graph used in the proof of Hall’s and K¨onig’s theorems
...
Having found a path, augment flow by 1, thereby finding a matching of
size one greater
...
If this matching is of size n we are done (by Lemma 9
...
If not, proceed to step 2
...
The Ford-Fulkerson algorithm has stopped with a set S, of vertices that can be
reached from s along augmenting paths
...
Let
us now increase by θ the label of each vertex in S, while keeping labels of vertices in
V \ S constant
...
We increase θ gradually from 0 until for some i ∈ L ∩ S, and j ∈ R ∩ (V \ S)
the value of λi − λj moves from < cij to = cij
...
Some edges may have been lost from the equality
graph, but not so as remove any vertices from S (since all vertices in S can be reached
along augmenting paths from s and the labels of vertices along augmenting paths have
all increased by θ)
...
The later can happen at
most n times, so eventually we must find an augmenting path to t
...
The total number times we find an
augmenting path is no more than n (since the cardinality of the matching can increase
at most n times)
...
Each computation of new labels takes time O(n2 ) (since we have to check which
of the λi − λj first increases to cij )
...
There is an improved version of the Hungarian algorithm that runs in time O(n3 )
...
Edges
(s, i) and (j, t) have capacity 1
...
At a step 2 the
equality graph contains the solid edges between L and R
...
All other edges between L and R exist but are not in the equality tree
and are not shown
...
, 6–15), each of which carries flow 1
...
The vertices in S are black and the vertices in V \ S are white
...
As we increase the node numbers on S new edges will join the equality set, such
as those shown dotted
...
Otherwise,
as in case of 4–11 the number of vertices in R ∩ S increases by 1 (with the addition of
11)
...
49
11
Shortest Paths and Minimum Spanning Trees
11
...
It is
equivalent to the minimum cost flow problem on the same network where one unit of
flow is to be routed from each vertex i ∈ V \ {t} to t, i
...
the one with supply bi = 1
at every vertex i ∈ V \ {t} and demand bt = −(|V | − 1) at vertex t
...
By setting λt = 0 and adding these equalities along a path from i to t, we see that
λi is equal to the length of a shortest path from i to t
...
i∈V \{t}
In an optimal solution, λi will thus be as large as possible subject to the constraints,
i
...
it will satisfy the so-called Bellman equations
λi = min {cij + λj }
for all i ∈ V \ {t},
j:(i,j)∈E
with λt = 0
...
This situation
is illustrated in Figure 14
...
2
Bellman-Ford algorithm
Let λi (k) be the length of a shortest path from i to t that uses at most k edges
...
The algorithm that successively computes λi (k) for all i and larger and larger values
of k is known as the Bellman-Ford algorithm
...
Note that λi (|V |) < λi (|V | − 1) for some i ∈ V if and only if there exists a cycle of
negative length
...
Otherwise λi = λi (|V |−1)
...
Each iteration requires O(|E|)
steps, for an overall running time of O(|E| · |V |)
...
11
...
If all
edges have non-negative lengths then the running time can sometimes be decreased
...
Assume E = V × V , and set cij = ∞ if necessary
...
Lemma 11
...
Consider a graph with vertices V and edge lengths cij ≥ 0 for all
i, j ∈ V
...
Let
j ∈ V \ {t} such that cjt = mini∈V \{t} cit
...
Proof
...
Then, λi ≥ λ` ≥ c`t ≥ cjt
...
Thus λj = cjt ≤ λi
...
Find a vertex j with cjt = mini∈V \{t} cit
...
2
...
3
...
If |V | > 1, return to Step 1
...
In the graph on the left,
c2t = mini∈V \{t} cit and therefore, by Lemma 11
...
The graph on the
right is then obtained by removing vertex 2 and updating c14 to min{c14 , c12 + c24 } =
min{∞, 5 + 1} = 6 and c34 to min{c34 , c32 + c24 } = min{6, 4 + 1} = 5
...
The overall running time is thus
O(|V |2 )
...
One might wonder if there exists a way to transform the edge lengths to make them
non-negative without affecting the structure of the shortest paths, so that Dijkstra’s
algorithm could be used in the presence of negative lengths as well
...
Let c¯ij = cij + λj − λi
...
, vk ,
k−1
X
i=1
c¯vi vi+1 =
k−1
X
k−1
X
i=1
i=1
(cvi vi+1 + λvi+1 − λvi ) = λvk − λv1 +
cvi vi+1
...
This observation is not very useful in the context of single-pair or single-destination
shortest path problems: we do not know the values λi , and computing them is at least as
hard as the problem we are trying to solve
...
The straightforward solution to this problem is to run the
Bellman-Ford algorithm |V | times, once for every possible destination vertex
...
Using the above observation, we can instead invoke the Bellman-Ford algorithm for one
destination vertex t to obtain the shortest path lengths λi for all i ∈ V , and compute
shortest paths for the remaining destination vertices by running Dijkstra’s algorithm
on the graph with edge lengths c¯ij
...
52
11
...
This problem arises, for example, if one
wishes to design a communication network that connects a given set of locations
...
Theorem 11
...
Let (V, E) be a graph with edge costs cij for all (i, j) ∈ E
...
Then there exists a
spanning tree of minimum cost that contains (u, v)
...
Let T ⊆ E be a spanning tree of minimum cost
...
Otherwise, T ∪ {(u, v)} contains a cycle, and there must be another edge (u0 , v 0 ) ∈ T
such that (u0 , v 0 ) ∈ U × (V \ U )
...
Prim’s algorithm uses this property to inductively construct a minimum spanning
tree
...
Set U = {1} and T = ∅
...
If U = V , return T
...
3
...
It is called a greedy algorithm, because it always chooses an edge of minimum cost
...
In this example, Prim’s algorithm adds edges in the sequence {1, 3}, {3, 6},
{6, 4}, {3, 2}, {2, 5}
...
This only needs comparison between the previously stored edge and the
edge to the vertex newly added to U
...
So each iteration needs time O(|V |)
...
53
12
12
...
We illustrate the primal-dual path following method for the LP and dual LP
minimize c> x s
...
Ax = b, x ≥ 0,
maximize λ> b s
...
λT A + sT = cT , s ≥ 0
...
We
drop those, and consider new primal and dual objective functions, for µ > 0,
P
P
c> x − µ i log xi and λ> b + µ j log sj
...
Its influence decreases as µ tends to 0
...
1)
xi si = µ for all i = 1,
...
Suppose that we have feasible solutions that satisfy (12
...
Then cT x − λT b = nµ
...
1)
...
1)
...
It is possible to prove√that such an algorithm decreases
the duality gap µk from 0 to in a time that is O( n log(0 /))
...
2
Semidefinite programming problem
The set {(x, s) : x ≥ 0, s ≥ 0} is a convex cone
...
Let Sn = {A ∈ Rn×n : AT = A} be the set of all symmetric n × n matrices
...
e
...
We write A 0
...
e
...
A linear function of X ∈ Sn can be expressed in terms of the inner product
tr(CX) =
n X
n
X
i=1 j=1
54
cij xij
for some C ∈ Sn
...
, m
(12
...
, Am ∈ Sn and b ∈ Rm
...
2) is a special case of semidefinite programming:
minimize hdiag(c), diag(x)i
subject to hdiag(ai ), diag(x)i = bi
diag(x) 0,
for all i = 1,
...
, ain )T , for i = 1,
...
This problem can be brought into the form of (12
...
Semidefinite programming has been called linear programming for the 21st century
...
As a consequence, there are optimization problems that can
be written as an SDP, but not as an LP
...
While no algorithm is known for solving SDPs in a finite number of steps, they can
be solved approximately in polynomial time, by a variant of the ellipsoid method, or a
barrier method of the type described above
...
This works because X 0 if and only if κi ≥ 0 for
all i = 1,
...
The Lagrangian dual of SDP is
DSDP : maximize min tr(CX) +
y
X0
X
yi (bi − tr(Ai X))
i
= maximize y > b s
...
C −
y
X
yi Ai 0
...
The
complementary slackness condition is tr(ZX) = 0
...
1)
...
55
12
...
The max-cut problem is NP-complete and thus cannot be solved
exactly in polynomial time unless P = NP
...
A 0
...
Theorem 12
...
There exists a 0
...
Proof sketch
...
3)
for all i ∈ V
...
Since the max-cut problem is NP-complete, an optimal solution of (12
...
Note, however, that
X 1 − xi xj
{i,j}∈E
2
=
|E| 1 T
|E| 1
− x Cx =
− tr(CxxT ),
2
4
2
4
where C is the graph’s adjacency matrix with Cij = 1 if {i, j} ∈ E and Cij = 0 otherwise
...
So we can relax the constraints
and obtain an upper bound on the optimal solution of (12
...
We arrive at the
following optimization problem, which is an SDP:
|E| 1
− tr(CX)
2
4
subject to Xii = 1 for all i ∈ V
maximize
X 0
...
3)
...
87856
...
87856 of the true max-cut value
...
4
Symmetric rendezvous search game
Suppose that two players are placed in two rooms
...
On the
stroke of each hour, 1, 2,
...
They wish to minimize the expected number of
attempts required until this occurs
...
I
II
Imagine that for each player the telephones are arranged around a circle, and players
have a common notion of clockwise
...
He labels the two phones that are one and two positions clockwise from a
as ‘b’ and ‘c’, respectively
...
Suppose he adopts these with probabilities x = (x1 , x2 , x3 )
...
The
probability that the players fail to pick up connected telephones at the next attempt
(i
...
fail to rendezvous) is
1
1
2
x> C 1 x = x>
1
2
1
2
1
1
2
1
2
1
2
1
x
...
Similarly, thinking about both times 2 and 3, there are 9 pure strategies: aa, ab, ac, ba,
bb, bc, ca, cb, cc
...
, x9 )
...
1
2
1
2
1
2
1
1
0
1
2
1
2
1
2
1
1
2
0
0
1
2
1
1
2
1
2
1
2
1
2
1
2
0
1
2
1
2
1
2
1
2
1
1
2
1
2
1
2
1
2
1
2
0
0
1
2
0
1
2
1
2
1
2
0
1
2
1
2
0
1
2
1
2
0
1
2
1
2
1
2
0
1
2
1
2
C2 is not positive definite
...
) This means
that the quadratic form x> C2 x has local minima
...
But better is
x> = (1/3)(1, 0, 0, 0, 0, 1, 0, 1, 0), which gives x> C2 x = 1/3
...
Note that for x to be a vector of probabilities, we must
have x> Jx = 9
...
t
...
One can numerically compute that the optimal value of this SDP
...
This
provides a lower bound on the probability that the players do not rendezvous by the
end of the 3rd attempt
...
These ideas can be extended (Weber, 2008) to show that the expected time to rendezvous is minimized when players adopt a strategy in which they choose their first
telephone at random, and if this does not connect them then on successive pairs of
subsequent attempts they choose aa, bc or cb, each with probability 1/3
...
This is less than 3, i
...
the expected number of steps required if players simply
try telphones at random at each attempt
...
58
13
Branch and Bound
There are three conceptually different approaches for optimization problems that are
computationally hard: (i) an exact method, which finds optimal solutions but has an
exponential worst-case running time, (ii) heuristic methods, which need not offer guarantees regarding running time or solution quality, but often provide a good tradeoff
between the two in practice, and (iii) approximation algorithms, which run in polynomial time and return solutions with a guaranteed bound on the suboptimality
...
We start with another example of (iii)
and then continue with (i) and (ii)
...
1
Knapsack problem
In the 0-1 knapsack problem we are to
Pn
maximize
x i vi
Pi=1
n
subject to
i=1 xi wi ≤ B,
xi ∈ {0, 1}
...
A greedy algorithm is to
place items in the knapsack in order 1, 2,
...
Suppose
the optimal value is OPT
...
(13
...
In fact, we can find a (1 − )-approximation
algorithm for any > 0, as follows
...
Suppose O is a set of optimal
items for the knapsack and |O| > m
...
Consider filling the knapsack with H ∪ G, where G is obtained
by filling the space B − w(H) by using the greedy algorithm on items with values
no more than values in H, i
...
taking such items in decreasing order of vi /wi until
one does not fit; suppose that is j
...
1) we have v(O) ≤ v(H ∪ G) + vj
...
Hence v(H ∪ G) ≥ (1 − 1/m)v(O)
...
We will either find the optimal packing, say O, when |O| ≤ m,
or at some point take K = H and construct H ∪G such that v(H ∪G) ≥ (1−1/m)v(O)
...
The knapsack problem lies in the
PTAS, which is defined as the class of problems which having a polynomial-time
approximation scheme
...
It can be shown that there is strict
inequality unless P=NP
...
2
Branch and bound technique
Suppose we wish to solve the knapsack problem exactly
...
However, there is something we can do
...
} are still available for inclusion, with vi1 /wi1 ≥
vi2 /wi2 ≥ · · · , then the value we can obtain by completing the packing optimally is
bounded above by
X
vi + vi1 + · · · + vik + α(vik+1 /wik+1 ),
i∈A
P
where i∈A wi + wi1 + wi2 + · · · + wik + α = B, and α < wik+1
...
Branch and bound is a general method for solving optimization problems, especially
in the context of non-convex and combinatorial optimization
...
Branch and bound uses divide and conquer, which splits a
problem into smaller and smaller subproblems until they become easy to solve
...
, Xk such
that i=1,
...
This step is called branching, since its recursive application
defines a tree structure, the so-called search tree, whose vertices are the subsets of X
...
, Xk , it is easy to obtain
a solution for X, because minx∈X f (x) = mini=1,
...
Of course, branching as such doesn’t make the problem any easier to solve, and for
an NP-hard problem we may have to explore an exponential number of vertices of the
search tree
...
The procedure that allows us
to do this is known as bounding
...
e
...
Then, if `(Y ) ≥ u(Z) for two sets Y, Z ⊆ X, then Y can be discarded
...
For the upper bound, it suffices to store the value U = f (x) of the best feasible solution
x ∈ X found so far
...
It is easy to see that this indeed provides a lower bound
...
The branch and bound method stores U and a list L of active sets Y ⊆ X for
which no optimal solution has been found so far, corresponding to vertices in the search
tree that still need to be explored, along with their associated lower bounds
...
Initialize: set U = ∞
...
Start with L = {X}
...
Branch: pick a set Y ∈ L, remove it from L, and split it into k ≥ 2 sets Y1 ,
...
3
...
, k, compute `(Yi )
...
If `(Yi ) < U , but no x ∈ X as above is found, then
add Yi to L
...
If L = ∅, then stop
...
Otherwise go to Step 2
...
These decisions are of course critical for the practical performance of the procedure
...
3
Dakin’s method
Dakin (1965) proposed an obvious way of using branch and bound to solved integer
linear programs
...
e
...
Assume that we are branching on a set Y ∈ L, and that the LP relaxation corresponding
to Y has optimal solution y
...
Otherwise, there is some
i such that yi is not integral, and we can split Y into two sets Y 1 = {x ∈ Y : xi ≤ byi c}
and Y 2 = {x ∈ Y : xi ≥ dyi e}
...
Moreover, this
branching rule forces the solution away from its current value y ∈
/ Y
...
It is worth
noting that we do not have to start from scratch when solving the LP relaxation for Yi :
it was obtained by adding a constraint to an LP that is already solved, and the dual
simplex method often finds a solution satisfying the additional constraint very quickly
...
e
...
Example 13
...
Assume that we want to
minimize x1 − 2x2
subject to −4x1 + 6x2 ≤ 9
x1 + x2 ≤ 4
x1 ≥ 0, x2 ≥ 0
x1 , x2 ∈ Z
...
Let f (x) = x1 − 2x2 , and X = Z2 ∩ X
˜ = { x ∈ R2 : −4x1 + 6x2 ≤ 9, x1 + x2 ≤ 4, x1 ≥ 0, x2 ≥ 0 }
...
61
x2
x2 ≥ x02
3
x0
x1 − 2x2 = −2
x1
2
x4
x3
1
1
x1 ≤ x1
x2 ≤ x02
x1 ≥ x11
0
1
2
x1
3
Figure 16: Illustration of Dakin’s method, applied to the IP of Example 13
...
By solving the LP relaxation for X, we find
that `(X) = minx∈X˜ f (x) = f (x0 ) = −7/2 for x0 = (3/2, 5/2)
...
and X
• Bound X 1 and X 2 by solving the corresponding LP relaxations, and obtain
˜ 2 = ∅
...
˜ 3 and X 4 = Z2 ∩ X
˜ 4 , where
• Branch by splitting X 1 into X 3 = Z2 ∩ X
˜ 3 = {x ∈ X
˜ 1 : x1 ≤ 0}
X
˜ 4 = {x ∈ X
˜ 1 : x1 ≥ 1},
and X
• Bound X 3 and X 4 to obtain `(X 3 ) = minx∈X˜ 3 f (x) = f (x3 ) = −3 for x3 =
(0, 3/2) and `(X 4 ) = minx∈X˜ 4 f (x) = f (x4 ) = −3 for x4 = (1, 2)
...
Then, `(X 3 ) ≥ U , so we can discard X 3 and are done
...
1
62
14
14
...
Matrix entry aij can be interpreted as a cost associated with edge (i, j) ∈ E of a graph
G = (V, E), and we are then trying to find a tour, i
...
a cycle in G that visits every
vertex exactly once, of minimum overall cost
...
Consider variables
xij ∈ {0, 1}
for i, j = 1,
...
1)
encoding whether the tour traverses edge (i, j)
...
e
...
, n − 1}
...
e
...
, n,
n
X
i=1
xij = 1
for i = 1,
...
(14
...
The problem with both of these
formulations is of course that they require an exponential number of constraints, one
for each set S ⊆ V
...
, n, an auxiliary
variable ti ∈ {0,
...
If xij = 1, it
holds that tj = ti + 1
...
This can
be written more succinctly as
tj ≥ ti + 1 − n(1 − xij )
for all i ≥ 1, j ≥ 2, i 6= j
...
3)
Since values satisfying (14
...
On the other hand, it suffices to rule
out subtours, i
...
cycles of length less than |V |
...
3), and assume for contradiction that it consists of two or more subtours
...
P
A minimum cost tour can thus be found by minimizing i,j xij aij subject to (14
...
2), and (14
...
This integer program has a polynomial number of variables and
constraints and can be solved using Dakin’s method, which bounds the optimum by
63
relaxing the integrality constraints (14
...
There are, however, other relaxations that
are specific to the TSP and can provide better bounds
...
3) is an instance of the assignment problem (9
...
It can be solved
efficiently in practice using the network simplex method or Hungarian algorithm, which
yields a solution consisting of one or more subtours
...
, ek } ⊆ E of edges of one or more of the subtours
and disallowing each of them in turn splits the feasible set Y into Y1 ,
...
Clearly, the optimal TSP tour cannot contain all
edges of a subtour, so it must be contained in one of the sets Yi
...
Note that none
of the sets Yi contains the optimal solution of the current relaxation, so `(Yi ) ≥ `(Y )
for all i, and `(Yi ) > `(Y ) if the optimal solution of the current relaxation was unique
...
2
Heuristic algorithms
For all we know, a complete exploration of the search tree, either explicitly or implicitly, might be required to guarantee that an optimal solution is found
...
Heuristics sacrifice solution quality in order to gain computational
performance or conceptual simplicity
...
3
Heuristics for the TSP
A straightforward way of constructing a TSP tour is by starting from an arbitrary
vertex, traversing a minimum cost edge to an unvisited vertex until all vertices have been
visited, and returning to the initial vertex to complete the tour
...
Intuitively it will work well most of the
time, but will sometimes have to add an edge with very high cost because all vertices
connected to the current one by an edge with low cost have already been visited
...
This so-called savings heuristic has complexity
O(n2 log n), which is the complexity of sorting a set with n2 elements
...
e
...
The initial
subtour can be a cycle of two or three vertices
...
The farthest insertion heuristic, on
64
the other hand, inserts a vertex whose minimum distance to any vertex in the current
subtour is maximal
...
14
...
Rather,
we could try to make a small modification to the tour in order to reduce its cost,
and repeat this procedure as long as we can find such an improving modification
...
A tour created using the nearest neighbor heuristic, for example, will usually
contain a few edges with very high cost, so we would be interested in local modifications
that eliminate these edges from the tour
...
Local search then proceeds as follows:
1
...
2
...
3
...
The solution returned by this procedure is a local optimum, in that its cost is no
larger than that of any solution in its neighborhood
...
Any of the basic tour construction heuristics can be used to find an initial feasible
solution in Step 1
...
Step 2
...
Natural options include the first such solution to be found, or the
solution providing the largest decrease
...
A natural neighborhood for the TSP is the k-OPT
neighborhood
...
Viewing tours as permutations, k-OPT cuts a permutation into k segments
and reverses and swaps these segments in a arbitrary way
...
65
6
1
5
6
2
4
1
5
3
6
2
4
3
1
5
2
4
3
Figure 18: A TSP tour (left) and neighboring tours under the 2-OPT (middle) and
3-OPT neighborhoods (right)
...
The choice of k provides a tradeoff between solution quality and speed: the k-OPT
neighborhood of a solution contains its `-OPT neighborhood if k ≥ `, so the quality of
the solution increases with k; the same is also true for the complexity of the method,
because the k-OPT neighborhood of a tour of length n has size O(nk ) and computing
the change in cost between two neighboring tours requires O(k) operations
...
Note that the simplex method for linear programming can also be viewed as a local
search algorithm, where two basic feasible solutions are neighbors if their bases differ
by exactly one element
...
In general, however, local search might get stuck in a local optimum and fail to find a
global one
...
0 4 4 0 1
1 0 4 4 0
There are 4! = 24 TSP tours, and
c(12345) = 5,
c(12354) = 6,
c(12435) = 6,
c(12453) = 10,
c(12534) = 10,
c(12543) = 17,
c(13245) = 6,
c(13254) = 12,
c(13425) = 10,
c(13452) = 6,
c(13524) = 0,
c(13542) = 12,
c(14235) = 10,
c(14253) = 20,
c(14325) = 17,
c(14352) = 9,
c(14523) = 10,
c(14532) = 17,
c(15234) = 6,
c(15243) = 12,
c(15324) = 12,
c(15342) = 17,
c(15423) = 17,
c(15432) = 20
...
66
14
...
Simulated annealing implements this idea
using an analogy to the process of annealing in metallurgy, in which a metal is heated
and then cooled gradually in order to bring it to a low-energy state that comes with
better physical properties
...
With the
remaining probability the solution stays the same
...
As T approaches zero, so
does the probability of moving to a solution with larger cost
...
To motivate this claim, consider the
special case where every solution has k neighbors and a neighbor of the current solution
is chosen uniformly at random
...
This Markov chain has a unique stationary
distribution π, i
...
a distribution over
P
X such that for all x ∈ X, πx = y∈X πy Pyx
...
In fact, detailedP
balance is not only
P necessary but also
P sufficient for
stationary, because it implies that x∈X πx Pxy = x∈X πy Pyx = πy x∈X Pyx = πy
...
Letting Y ⊆ X be the set of solutions with minimum cost
and πY = x∈Y πx , we conclude that πY /(1 − πY ) → ∞ as T → 0
...
A common cooling schedule is to set T = c/ log t in iteration
t, for some constant c
...
Game theory provides mathematical
models, so-called games, for studying such situations
...
Later, we consider cooperative games and focus
upon conditions under which cooperation among subsets of agents can be sustained
...
1
Games and solutions
The central object of study in non-cooperative game theory is the normal-form game
...
e
...
Unless noted otherwise, the results we consider
are invariant under positive affine transformations of payoffs, and payoffs will not be
comparable across players
...
However,
this generally leads to a large increase in the number of actions
...
Two-player games are
therefore sometimes referred to as bimatrix games, and players 1 and 2 as the row
and column player, respectively
...
Assume players can choose their actions randomly and denote the set of possible
Pm strategies of the two players by X and Y , respectively, i
...
X = {x ∈ Rm
:
≥0
i=1 xi = 1}
Pn
and Y = {y ∈ Rn≥0 : i=1 yi = 1}
...
A profile (x, y) ∈ X × Y of strategies induces a lottery over
outcomes, and we write p(x, y) = xT P y and q(x, y) = xT Qy for the expected payoff of
the two players in this lottery
...
If both remain silent, they
walk free after spending a few weeks in detention
...
If both testify, each of them receives a five-year sentence
...
68
S
T
S
(2, 2)
(0, 3)
T
(3, 0)
(1, 1)
Figure 19: Representation of the prisoner’s dilemma as a normal-form game
...
Action S corresponds to
remaining silent, action T to testifying
...
More generally, for two strategies x, x0 ∈ X of the row player, x is said to strictly dominate
x0 if for every strategy y ∈ Y of the column player, p(x, y) > p(x0 , y)
...
Strategy profile (T, T ) in the prisoner’s
dilemma is what is called a dominant strategy equilibrium, a profile of strategies
that dominate every other strategy of the respective player
...
More generally, an outcome that is weakly preferred to another
outcome by all players, and strictly preferred by at least one player is said to Pareto
dominate that outcome
...
In the absence of dominant strategies, it is less obvious how players should proceed
...
It models a situation
in which two cars drive towards each other on a collision course
...
If one of them yields while the other goes straight,
however, the former will be called a “chicken”, or coward
...
C
D
C
(2, 2)
(1, 3)
D
(3, 1)
(0, 0)
Figure 20: The game of chicken, where players can chicken out or dare
The most cautious choice in a situation like this would be to ignore that the other
player is self-interested and choose a strategy that maximizes the payoff in the worst
case, taken over all of the other player’s strategies
...
It
is easy to see that it suffices to maximize the minimum payoff
all pure strategies
Pover
m
of the other player, i
...
to choose x such that minj∈{1,
...
Thus the maximin strategy and the security level for the row player can be found from
69
the following linear program with variables v ∈ R and x ∈ Rm :
maximize
subject to
v
m
X
xi pij ≥ v
for j = 1,
...
(15
...
This also illustrates that a maximin strategy need not be optimal: assuming that
the other player yields, the best response is in fact to go straight
...
The concept of a best response for the column player
is defined analogously
...
It is easily verified that both (C, D) and
(D, C) are equilibria of the game of chicken
...
15
...
A two-player game is a zero-sum game
if qij = −pij for all i = 1,
...
, n
...
Assuming invariance of utilities under positive affine transformations,
results for zero-sum games in fact apply to the larger class of constant-sum games,
in which the payoffs of the two players always sum up to the same constant
...
Pm
Theorem 15
...
Let P ∈ Rm×n , X = {x ∈ Rm
≥0 :
i=1 xi = 1},
P
n
Y = {y ∈ Rn≥0 : i=1 yi = 1}
...
x∈X y∈Y
y∈Y x∈X
Proof
...
1), and recall that the optimal solution
of this linear program is equal to maxx∈X miny∈Y p(x, y)
...
The
a finite maximum for v ∈ R and x ∈ Rm
Pn Lagrangian
Phas
n
with x ≥ 0 if and only if j=1 yj = 1, j=1 pij yj ≤ w for i = 1,
...
The dual of (15
...
, m,
j=1
n
X
yj = 1,
y ≥ 0
...
The number maxx∈X miny∈Y p(x, y) = miny∈Y maxx∈X p(x, y) is called the value of
the matrix game with payoff matrix P
...
1)
...
This does not change the equilibrium of the game, but ensures that
P at the
solution we must have v > 0
...
1) as
minimize
m
X
x0i
subject to
i=1
m
X
x0i pij ≥ 1 for j = 1,
...
i=1
Alternatively, we might apply a similar transformation to the dual and solve
maximize
n
X
yi0
subject to
pij yi0 ≤ 1 for j = 1,
...
i=1
i=1
15
...
Theorem 15
...
A pair of strategies (x, y) ∈ X × Y is an equilibrium of the matrix
game with payoff matrix P if and only if it is a minimax point, i
...
min p(x, y 0 ) = max
min
p(x0 , y 0 )
0
0
y 0 ∈Y
x ∈X y ∈Y
and
(15
...
0
0
0
x ∈X
y ∈Y x ∈X
Proof
...
1
...
This
means that the first and last inequality have to hold with equality as well, and (15
...
On the other hand, if (15
...
This means that the second and third inequality have to hold with equality
as well, so (x, y) is an equilibrium
...
These are that all equilibria yield the same payoffs and that any pair of strategies
of the two players, such that each of them is played in some equilibrium, is itself an
equilibrium
...
3
...
Then p(x, y) = p(x0 , y 0 ), and (x, y 0 ) and (x0 , y) are equilibria as well
...
Since equilibrium strategies are best responses to each other, we have that
p(x, y) ≤ p(x, y 0 ) ≤ p(x0 , y 0 ) ≤ p(x0 , y) ≤ p(x, y)
...
Then,
p(x, y 0 ) = p(x0 , y 0 ) ≥ p(z, y 0 )
p(x, y 0 ) = p(x, y) ≤ p(x, z)
for all z ∈ X,
for all z ∈ Y ,
p(x0 , y) = p(x, y) ≥ p(z, y)
for all z ∈ X, and
p(x0 , y) = p(x0 , y 0 ) ≥ p(x0 , z)
for all z ∈ X,
where the inequalities hold because (x, y) and (x0 , y 0 ) are equilibria
...
Theorems 15
...
2, and 15
...
72
16
16
...
Theorem 16
...
Every bimatrix game has an equilibrium
...
Theorem 16
...
Let f : S → S be a continuous function, where S ⊆ Rn is closed, bounded, and convex
...
Proof of Theorem 16
...
Define X and Y as before, and observe that X × Y is closed,
bounded, and convex
...
e
...
, m and
− q(x, y)}
for j = 1,
...
Further define f : (X × Y ) → (X × Y ) by
letting f (x, y) = (x0 , y 0 ) with
x0i =
xi + si (x, y)
Pm
1 + k=1 sk (x, y)
yj0 =
and
yj + tj (x, y)
Pn
1 + k=1 tk (x, y)
for i = 1,
...
, n
...
2 is must
have a fixed point, i
...
a pair of strategies (x, y) ∈ X × Y such that f (x, y) = (x, y)
...
, m} such that xi > 0 and si (x, y) = 0,
since otherwise
p(x, y) =
m
X
xk p(em
k , y) >
k=1
m
X
xk p(x, y) = p(x, y)
...
k=1
73
This means that for k = 1,
...
It follows that
p(x, y) ≥ p(x0 , y)
for all x0 ∈ X
...
Our requirement that a bimatrix game has a finite number of actions is crucial for this
result
...
16
...
1 relies on fixed points of a continuous function and does not
give rise to a finite method for finding an equilibrium
...
Define the support of strategy x ∈ X as S(x) = {i ∈ {1,
...
, m} : yj > 0}
...
In other words, randomization over the
support of an equilibrium does not happen for the player’s own sake, but to allow the
other player to respond in a way that sustains the equilibrium
...
Once the supports are known, the precise strategies can be computed
by solving a set of equations, which in the two-player case are linear
...
Solving these k + ` equations in k + ` variables yields k values for player 1 and ` values for player 2
...
An equilibrium
with supports of size two in the game of chicken would have to satisfy x1 + x2 = 1,
y1 + y2 = 1, 2x1 + 1x2 = 3x1 + 0x2 , and 2y1 + 1y2 = 3y1 + 0y2
...
No equilibrium with full supports exists in the prisoner’s dilemma,
because the corresponding system of equalities does not have a solution
...
The running time of this method is finite, but clearly exponential in
general
...
While the equilibrium condition can easily be
verified for a given pair of strategies, which implies membership in NP, the notion of
NP-hardness seems inappropriate: equilibria always exist and the decision problem is
therefore trivial
...
Theorem 16
...
Given a bimatrix game, it is NP-complete to decide whether it has
at least two equilibria; an equilibrium in which the expected payoff of the row player is
at least a given amount; an equilibrium in which the expected sum of payoff of the two
players is a least a given amount; an equilibrium with supports of a given minimum
size; an equilibrium whose support includes a given pure strategy; or an equilibrium
whose support does not include a given pure strategy
...
1 is an existence statement, but its proof does not identify an equilibrium
...
It provides an alternative, combinatorial, proof of the existence of an equilibrium
...
3
Symmetric games
A symmetric game is one in which Q = P T
...
Lemma 16
...
Consider the symmetric game with payoff matrix P
...
(16
...
Proof
...
For any strategy x
˜∈X
1
p(˜
x, x
¯) = x
˜T P x
¯ = Pm
i=1
So p(˜
x, x
¯) ≤ 1/
16
...
xi , with equality if x
˜=x
¯
...
1), we now describe an algorithm for finding an equilibrium of a
symmetric game
...
1 except for 1> x > 0
...
It is twice-represented if xi = zi = 0
...
Let S = {(x, z) : P x + z = 1, x ≥ 0, z ≥ 0}
...
Fix a strategy, say i = 1, and consider
the set V , consisting of all vertices of S in which every strategy is represented or twicerepresented, except possibly strategy 1 (which may be missing)
...
Note that v0 ∈ V since in v0 every strategy is represented
...
This is the vertex
reached by increasing x1 from 0
...
(This
can be done in a tableau, similarly to the simplex algorithm)
...
1)
...
Continue in this manner
...
Either
xj or zj has just become 0
...
If this is x1 or z1 we now have a solution to
(16
...
Otherwise we continue
...
The reasoning is cute
...
Second, there is only one
way to leave v0 and remain in V ; similarly, having reached vi there is only one way
to leave vi and remain in V without returning to the vertex from which the path just
arrived
...
Thirdly, there are a finite number of
vertices in V , so eventually the algorithm can go no further
...
Since
this is not v0 it must be one for which 1> x > 0
...
5
...
2
We start at v0 = (x, z) = (0, 0, 0, 1, 1, 1)
...
In moving from v0 to v1 , the variable z1 has decreased
to 0 and strategy 1 is now twice-represented
...
Now z3 has been decreased to 0 and strategy 3 is twicerepresented, so we increase x3 to reach v3 = (0, 31 , 16 , 0, 12 , 0)
...
Now z2 is decreased to 0, all strategies are represented, and xT z = 0
...
As we move amongst vertices in V we are at each step increasing some variable xi
76
(or zi ) associated with an twice-represented strategy i, which is complementary to the
variable zi or (or xi ) that was decreased to 0 at the previous step
...
If we had started with i = 1 we would
have reached v4 along a different path
...
Starting with different i to be dropped we might reach the same
equilibrium or a different equilibrium
...
There is an interesting corollary of this analysis
...
6
...
Proof
...
e
...
Every equilibrium of P × Q is a member of V
(since equilibriums are vertices for which all strategies are represented)
...
So this graph consists of disjoint
paths and cycles
...
There are an even number of endpoints, so the number of Nash
equilibria must be odd
...
1
Linear complimentarity problem
Linear complementarity problem
The linear complementarity problem (LCP) unifies linear programing, quadratic
programing and two-person non-zero sum games (bimatrix games)
...
The LCP is to find z, w ∈ Rn , such that
w − M z = q,
z, w ≥ 0
and z > w = 0
...
1)
Note that nothing is to be maximized or minimized in this problem
...
2
Quadratic programming as a LCP
Let D be a positive definite symmetric matrix and consider
QP :
minimize c> x + 21 x> Dx
subject to Ax ≥ b,
x ≥ 0
...
From the Lagrangian sufficiency theorem we see that (¯
x, v¯) minimizes L if
A¯
x − b = v¯,
y¯> v¯ = 0,
∂
L = c + D¯
x − A> y¯ = u
¯,
∂x
x
¯> u
¯ = 0,
x
¯, v¯, y¯, u
¯ ≥ 0
...
v¯
y¯
v¯
y¯
This defines a LCP, whose solution is an optimal solution to QP
...
78
17
...
, an } and wishes to find a subset which exactly
fill a knapsack of size B
...
, n
...
2)
The constraint xi ∈ {0, 1} can be written as wi = 1 − xi and xi wi = 0
...
2) equivalent to the LCP of finding x, w ≥ 0 such that xT w = 0 and
−1 · · ·
0
0
0
w1
x1
1
...
...
...
0
0
...
=
wn − 0 · · · −1
0
0 xn
1
wn+1
aT
−α
0 xn+1 −B
wn+2
B
xn+2
−aT
0 −β
where α and β are any positive numbers
...
17
...
If q > 0
then a solution to the LCP is w = q and z = 0
...
Let d = (1, 1,
...
For λ > 0 large enough, we have the solution w = q + λd ≥ 0, and z = 0
...
At this point
(where λ = − mini qi = −qk ) we have wk = zk = 0, and complementary slackness, i
...
wi zi = 0 for all i
...
Our next step is to move to a neighbouring basic feasible solution by increasing zk (i
...
we perform a pivot step that puts zk into the basis)
...
(If this does not happen then the algorithm fails
...
)
• If the departing basic variable is λ then we now have a solution to the LCP
...
We continue in this fashion, moving amongst solutions that are always complementary
slack, i
...
wi zi = 0 for all i, and such that λ > 0 and w` = z` = 0 for some `
...
At that point we have a solution to the LCP
...
Each
BFS that we can reach has exactly two neighbouring BFS, one of which precedes it and
one of which follows it
...
17
...
(17
...
4 may be reformulated as follows
...
1
...
3)
...
Then s/1> s is a symmetric equilibrium for this symmetric game, and x
¯ = x/1> x and
>
y¯ = y/1 y are an equilibrium pair for the original nonsymmetric game
...
Adding slack variables z ∈ Rm and w ∈ Rn turns the best
response conditions into QT x+w = 1, P y +z = 1, xT z = y T w = 0, where x, y, z, w ≥ 0
...
1):
0
−P
z
x
1n
−
=
,
w
y
1m
−Q>
0
>
x
z
x
z
≥ 0,
≥ 0,
= 0, x 6= 0, y 6= 0
...
We might start with x = y = 0
...
When xi is increased as much as possible,
a different constraint starts to hold with equality, for example, wj = 0; we say j is
picked up
...
So the next step is
to increase yj from 0
...
From this point we increase wk or xk , respectively
...
This procedure can be carried out through alternatively pivoting in two
tableaus, similarly to pivoting in the simplex method
...
, m} and N = {m + 1,
...
By pivoting we obtain the
following tableau:
7
3
1
3
0
1
8
3
1
6
1
0
− 31
1
6
2
3
1
6
The second row now corresponds to variable x2 that has entered the basis
...
We thus want to turn to the constraint
P y + z = 1 and drop the duplicate label 5
...
The final tableaus are the final two above
...
81
17
...
They can be connected via Sperner’s lemma
...
Consider
the triangulation shown in Figure 17
...
The colour of each vertex x depends on whether
f (x) lies to the northeast, northwest, or south of x
...
Each small triangle has either 0, 1 or 2 such edges
...
That is a triangle whose vertices have all three colours (a rainbow triangle)
...
Sperner’s lemmas says that
there must always be a rainbow triangle
...
In the limit, rainbow triangles
become fixed points
...
Along each side of the large triangle there is an odd
number of edges whose two endpoints are differently coloured
...
Notice
that this also proves that the number of rainbow triangles is odd
...
Only one is found by a following a path entering at the base
...
1
Cooperative Games
Coalitional games
A coalitional game is given by a set N = {1,
...
The payoff can
be distributed arbitrarily among its members due to their having transferable utility
(or payoff)
...
n
For a given game
P (N, v), a vector of payoffs x ∈ R is said to satisfy (economic)
efficiency if
i∈N xi = v(N ) and individual rationality if xi ≥ v({i}) for i =
1,
...
The first condition intuitively ensures that no payoff is wasted, while the
second condition ensures that each player obtains at least the same payoff it would be
able to obtain on its own
...
The set of imputations might be empty
...
e
...
18
...
For any two imputations x and y, i∈N xi = i∈N yi = v(N ), so yi > xi for some
i ∈ N implies that yj < xj for some other j ∈ N
...
If in addition i∈S yi ≤ v(S), the
members of S could increase their respective payoffs by exiting from the grand coalition,
forming the coalition S, and distributing the payoff thus obtained according to y
...
Formally,
imputation x is in the core of game (N, v) if i∈S xi ≥ v(S) for all S ⊆ N
...
This situation
can be modeled by a coalitional game (N, v) where N = {1,
...
The core then contains all imputations
if n = 2, the single imputation (1/2,
...
The latter can be shown using the following characterization of games with a
non-empty core
...
e
...
A
P
game (N, v) is called balanced if for every balanced function λ, S⊆N λ(S)v(S) ≤
v(N )
...
Balancedness of a collection of weights imposes a feasibility condition on
players’ allocations of time, and a game is balanced if there is no feasible allocation
that yields more than v(N )
...
1 (Bondareva 1963, Shapley 1967)
...
Proof
...
This linear program has the following dual:
X
maximize
λ(S)v(S)
S⊆N
subject to
X
λ(S) = 1
for all i ∈ N
S⊆N,i∈S
λ(S) ≥ 0
for all S ⊆ N ,
where λ : 2N → [0, 1]
...
Both primal and dual are feasible, so by strong duality their optimal
objective
values are the same
...
S⊆N
To see that the core of our example game is empty if n is odd, define λ : 2N → [0, 1]
such
P that λ(S) = 1/(n − 1) if |S| = 2 and λ(S) = 0 otherwise
...
Moreover, S⊆N λ(S)v(S) = n(n − 1)/2 · 1/(n − 1) = n/2, which is greater than
v(N ) if n is odd
...
3
The nucleolus
If the core is empty then one might consider weakening the requirement that no coalition
should be able to gain, and instead look for an efficient payoff vector that minimizes
the possible gain over all coalitions
...
To this end, define the excess e(S, x) of coalition S ⊆P
N for payoff vector x as its gain
from leaving the grand coalition, i
...
e(S, x) = v(S) − i∈S xi
...
For a given vector x, let
E(x) = (e(S1x , x), e(S2x , x),
...
, S2xn −1 is an ordering of the coalitions in decreasing order of excess, so
components of E(x) are nonincreasing
...
(No coalition
in positively dissatisified
...
Note that x does not need to be an imputation since we do
not require xi ≥ v({i})
...
Step 1
...
minimize
subject to ≥ v(S) −
P
0 = v(N ) −
i∈S
P
xi
i∈N
for all S ⊂ N
(P1 )
xi
...
Let ∆1 be the set of coalitions for which equality holds
in (P1 ) in every optimal solution
...
, |∆1 |
...
This is because
if each coalition S involved
P
in the inequality constraint satisfied 1 > v(S) − i∈S xi for some optimal solution,
x, then we could take the average of all optimal solutions, say x
¯, and deduce that for
this feasible x
¯ all the inequality constraints would be strict, contradicting 1 being the
optimal value
...
Otherwise stop
...
minimize
= v(S) −
P
xi
for all S ∈ ∆1
k−1
= v(S) −
P
xi
for all S ∈ ∆k−1
≥ v(S) −
P
xi
for all S ⊂ N , S 6∈ ∆1 ∪ · · · ∪ ∆k−1
subject to 1
...
0
i∈S
i∈S
= v(N ) −
i∈S
P
i∈N
(Pk )
xi
...
Let ∆k be the set of all coalitions in which equality
newly holds in (Pk ) in every optimal solution
...
If |∆1 ∪ · · · ∪ ∆k | < 2n − 2 then go to step k + 1
...
The algorithm terminates by the end of step 2n − 2
...
85
Theorem 18
...
The nucleolus of any coalitional game is a singleton
...
If x and y are both in the nucleolus then both P
are optimal solutions atPstep 1
...
The same reasoning holds at each step k
...
Example 18
...
Consider a game with N = {1, 2, 3} and characteristic function values
v({1}) = 1 v({2}) = 2
v({3}) = 1
v({1, 2}) = 2 v({1, 3}) = 3 v({2, 3}) = 5 v({1, 2, 3}) = 4
...
1)
To find the nucleolus of this game, we first
minimize
subject to x1 ≥ 1 − ,
x2 ≥ 2 − ,
x3 ≥ 1 −
x1 + x2 ≥ 2 − ,
x1 + x3 ≥ 3 −
x2 + x3 ≥ 5 − ,
x1 + x2 + x3 = 4
...
By adding the
constraints for {1} and {2, 3} and subtracting the constraint for {1, 2, 3} we see that
≥ 1, so the solution must be optimal
...
Thus x1 = 0, x2 ≥ 1, x3 ≥ 2, and x2 + x3 = 4
...
18
...
e
...
However, a different coalition T might counter-object on the grounds that
e(T, y) > e(T, x)
and e(T, y) ≥ e(S, x)
...
” It can shown that the nucleolus is the unique payoff such that every
objection has a counter-objection
...
1
Bargaining problems
The Shapley value
A different notion of fairness in distributing the joint payoff of a coalition among its
members was proposed by Shapley, starting from a set of axioms
...
e
...
Call two players i, j ∈ N interchangeable if they
contribute the same to every coalition, i
...
if v(S∪{i}) = v(S∪{j}) for all S ⊆ N \{i, j}
...
Solution φ is said to satisfy
• dummies if φi (v) = v({i}) whenever i is a dummy;
• symmetry if φi (v) = φj (v) whenever i and j are interchangeable; and
• additivity if φ(v + w) = φ(v) + φ(w)
...
Theorem 19
...
The Shapley value, given by
φi (v) =
X |S|!(|N | − |S| − 1)!
S⊆N \{i}
|N |!
v(S ∪ {i}) − v(S) ,
is the unique solution that satisfies dummies, symmetry, and additivity
...
For the three-player
game with characteristic function given in (18
...
3
6
6
3
3
19
...
If φj (N ) > φj (N − {i}), then player i might threaten player j, “Give me more or I will
leave the coalition and you will lose
...
” Player i has a valid counterobjection if he can point out that if he gets the others to exclude j then i will be better
off by at least as much
...
The only solution to this is the Shapley value
...
3
Bargaining theory
Bargaining theory investigates how agents should cooperate when non-cooperation may
result in outcomes that are Pareto dominated
...
Here, convexity corresponds to the assumption that any lottery over feasible outcomes
is again feasible
...
An example of a bargaining problem is the so-called ultimatum game given by F =
{(v1 , v2 ) ∈ R2 : v1 + v2 ≤ 1} and d = (0, 0), in which two players receive a fixed amount
of payoff if they can agree on a way to divide this amount among themselves
...
Players’ preferences regarding these equilibria differ,
and bargaining theory tries to answer the question which equilibrium should be chosen
...
, m, j =
1,
...
Here, conv(S) denotes the convex hull of set S
...
We will
focus on the axiomatic approach in this lecture
...
4
Nash’s bargaining solution
For a given bargaining problem (F, d), Nash proposed to
maximize
(v1 − d1 )(v2 − d2 )
subject to v ∈ F
v ≥ d
...
1)
Optimization problem (19
...
Consider for example the two-player game with payoff matrices
!
!
0 5
2 2
P =
and
Q=
...
The column player can guarantee a payoff of 2 by playing
the left column
...
The set F is
the convex hull of the four payoff vectors (0, 2), (5, 2), (3, 4), and (1, 0), and it contains
the feasible set B = {v ∈ F : v ≥ d} of (19
...
The disagreement point is d = (15/7, 2)
...
The Nash bargaining solution v ∗ is the unique point
in the intersection of F with the optimal level set
...
The
objective function becomes
(v1 − d1 )(v2 − d2 ) = (v1 −
15
7 )(5
− v1 ) =
50
7 v1
− v12 −
75
7 ,
and has a stationary point if 50/7 − 2v1 = 0
...
While it is not obvious that maximizing the product of the excess of the two players is
a good idea, it turns out that the Nash bargaining solution can be characterized using
a set of simple axioms
...
Pareto efficient if f (F, d) is not Pareto dominated in F for any bargaining
problem (F, d);
2
...
invariant under positive affine transformations if f (F 0 , d0 ) = α ◦ f (F, d) + β
for any α, β ∈ R2 with α > 0 and any two bargaining problems (F, d) and (F 0 , d0 )
such that F 0 = {α ◦ x + β : x ∈ F } and d0 = α ◦ d + β; and
4
...
Here, ◦ denotes component-wise multiplication of vectors, i
...
(s ◦ t)T = (s1 t1 , s2 t2 ) for
all s, t ∈ R2
...
Invariance under positive affine transformations should hold because payoffs are just a representation of the underlying ordinal
preferences
...
Theorem 19
...
Nash’s bargaining solution is the unique bargaining solution that is
Pareto efficient, symmetric, invariant under positive affine transformations, and independent of irrelevant alternatives
...
It remains to prove that the axioms force the solution to be Nash’s bargaining solution
...
Touch set F with v1 v2 = constant; use axiom 3 to move the
point of touching to (1/2, 1/2); add the set obtained by reflecting F in the line from the
origin through (1/2, 1/2); use axiom 2 to argue (1/2, 1/2) must be the solution; then
use axiom 4 to remove the extra set that was just added
...
We denote the Nash bargaining solution by f N and begin by showing that it
satisfies the axioms
...
For symmetry, assume that d1 = d2
90
and let v ∗ = (v1∗ , v2∗ ) = f N (F, d)
...
For invariance under positive affine transformations, define F 0 and d0 as
above, and observe that f N (F 0 , d0 ) is an optimal solution of the problem to maximize
(v1 − α1 d1 − β1 )(v2 − α2 d2 − β2 ) subject to v ∈ F 0 , v1 ≥ d1 , and v2 ≥ d2
...
For independence of
irrelevant alternatives, let v ∗ = f N (F, d) and F 0 ⊆ F
...
Now consider a bargaining solution f that satisfies the axioms, and fix F and d
...
e
...
Since both f and f N are invariant under positive affine transformations, f (F, d) =
f N (F, d) if and only if f (F 0 , 0) = f N (F 0 , 0)
...
We begin by showing that for all v ∈ F 0 , v1 + v2 ≤ 1
...
By
convexity of F 0 , tδ ∈ F 0 for δ ∈ (0, 1)
...
Now let F 00 be the closure of F 0 under symmetry, and observe that for all v ∈ F 00 ,
v1 +v2 ≤ 1
...
Since f is independent of irrelevant alternatives, f (F 0 , 0) = (1/2, 1/2)T as required
...
1
Social Choice
Social welfare functions
Social choice theory asks how the possibly conflicting preferences of a set of agents can
be aggregated into a collective decision, and in particular which properties the aggregate
choice should satisfy and which properties can be satisfied simultaneously
...
Let N = {1,
...
, m} a set of alternatives
...
This is achieved by means of a social welfare function (SWF) f : L(A)n → L(A)
...
A SWF f : L(A)n → L(A) is
• anonymous if the labelling of the voters is irrelevant;
• neutral if the labelling of the alternatives is irrelevant;
• monotone if an alternative cannot become less preferred socially when it becomes
more preferred by individuals
...
1
...
Then f is the majority rule if and only if it is anonymous, neutral, and monotone
...
Let A = {a, b}
...
By neutrality, the social preference has to
change between a preference profile where bn/2c voters prefer a to b and one where
dn/2e voters prefer a to b
...
In light of this result, it might seem promising to base the decision on pairwise comparisons of alternatives even when m > 2
...
In Figure 23 each column lists the prefa
b
c
b
c
a
c
a
b
Figure 23: Marquis de Condorcet’s paradox, 1786
...
It is easily verified that a majority of the voters prefers a
over b, a majority prefers b over c, and a majority prefers c over a
...
It turns out that dictatorships are the only SWFs for three or more alternatives that
are Pareto optimal and IIA
...
2 (Arrow, 1951)
...
If f is Pareto optimal and IIA, then f is dictatorial
...
So IIA
must be abandoned
...
This maximization problem is NP-hard, but can be written as an integer program
...
2
Social choice functions
It is often sufficient to identify a single best alternative rather than giving a complete
ranking
...
Two
familiar SCFs are plurality, which chooses an alternative ranked first by the largest
number of voters, and single transferable vote (STV), which successively eliminates
alternatives ranked first by the fewest voters until only one alternative remains
...
In this situation, plurality selects alternative a
because it is ranked first by 4 voters, compared to 3 for c and 2 for b
...
Restricting attention to
the remaining alternatives, a is ranked first by 4 voters and c by 5 voters
...
The graph of the majority relations shown in Figure 24 illustrates that alternative b is a
so-called Condorcet winner, i
...
it is preferred to any other alternative by a majority
of the voters, while alternative a is a Condorcet loser, i
...
a majority of voters prefer
any other alternative to a
...
An SCF satisfying
the former property is called Condorcet consistent, and the example of Figure 24 shows
that that neither plurality nor STV are Condorcet consistent
...
At the top of each column of the table is the number of voters having
the preference order below
...
20
...
This ignores, however,
that voters of the third type have an incentive to misrepresent their preferences and
claim that they prefer c to b: assuming that ties are broken in favor of c, only a single
voter of the third type would have to change its reported preferences in this way to
ensure that c is selected instead of a, an outcome this voter prefers
...
More generally, we say that SCF f is manipulable
if there exist situations in which by misrepresenting his true preferences agent i can
cause f to select an outcome which he prefers to the one which would be selected if
he were to give his true preferences
...
SCF f is called
strategyproof if it is not manipulable
...
So when there are more than two alternatives there are two obvious ways to
achieve strategyproofness: choose an alternative based on the preferences of a single
voter, or ignore all but two alternatives and using majority rule to choose between them
...
It turns out that these trivial cases are in fact the only SCFs that are
strategyproof
...
3 (Gibbard, 1973; Satterthwaite, 1975)
...
If f is unanimous and strategyproof, then it is dictatorial
...
4
...
Then i is decisive for a in the
sense that f ( ) = a whenever i ranks a top
...
Suppose i = 1
...
Similarly, a must remain selected however 3 is subsequently changed, and so on
...
, n , alternative a must still remain selected however 1 is
subsequently changed, provided 1 ranks a top, since otherwise 1 can manipulate f
...
5
...
Proof
...
If the only alternative for which each is not-decisive is the same
alternative, say a, then both are decisive for every other alternative, including b and c
...
Hence there must
exist distinct a and b for which 1 and 2 are not-decisive respectively
...
But the selection cannot be a, for then
agent 2 does better by demoting a to the bottom position, where since 1 is not decisive
for a, we know a is not selected and so b is selected (some c cannot be selected since
then 1 could manipulate by swapping preferences of a and b)
...
Proof of GS
...
Choose an arbitrary ∗n and consider a SCF for the first n − 1 agents defined as
h( 1 , 2 ,
...
, n−1 , ∗n )
...
In case (i) there is some a that is not selected even when all
of 1,
...
In case (ii) the dictator amongst agents 1,
...
In either
case there exists some alternative that some individual can ensure is not chosen, even
if all others rank it top
...
Next consider a SCF for two agents: g( 1 , 2 ) = f ( 1 , 1 ,
...
Then g is
unanimous, obviously
...
, 1 ) to ( 01 , 01 ,
...
, 01 , 1 ,
...
Lemma 20
...
However, agent 1 cannot be a dictator
because agent 2 can ensure that a∗ is not selected
...
95
20
...
e
...
They are easily seen
to be equivalent conditions
...
It is twice as long
...
I believe it is sometimes better to try to express things in English
sentences rather than overload the reader with the task of parsing notation
...
We need two lemmas
...
Lemma 20
...
Let f be a strategyproof SCF, ∈ L(A)n with f ( ) = a
...
Proof
...
Let
b = f ( 01 , −1 )
...
Also
by strategyproofness, b 01 a, and thus a = b
...
The second lemma states that the alternative selected by a surjective and strategyproof
SCF must be Pareto optimal
...
7
...
Then, f ( ) 6= b
...
Assume for contradiction that f ( ) = b
...
Let 00 ∈ L(A)n be a preference profile such that for all i ∈ N
a 00i b 00i x
for all x ∈ A \ {a, b}
...
Thus, by Lemma 20
...
Proof of Theorem 20
...
We first prove the theorem for n = 2 and then perform an
induction on n
...
Then, by Lemma 20
...
Suppose that f ( ) = a, and let 0 ∈ L(A)2 such that
a 01 b 01 x
and
b 02 x 02 a
for all x ∈ A \ {a, b}
...
7 and
f ( 0 ) 6= b by strategyproofness
...
6 now implies that f selects alternative a
for any preference profile in which voter 1 ranks alternative a first
...
Let A3 = A \ (A1 ∪ A2 ),
and observe that |A3 | ≤ 1: otherwise we would have performed the above analysis for
two elements in A3 , which would place one of these elements in A1 or A2 and thus not
in A3
...
Moreover, for x, y ∈ A
with x 6= y, it cannot be the case that x ∈ A1 and y ∈ A2 , because this would lead to
a contradiction when voter 1 ranks x first and voter 2 ranks y first
...
It finally follows that A3 = ∅: otherwise
we could repeat the above analysis for c ∈ A3 and 00 ∈ L(A)2 with
c 001 a 001 x
and
a 002 c 002 x
for all x ∈ A \ {a, c}, and conclude that c ∈ A1 or a ∈ A2 , a contradiction
...
Now we assume that the statement of the theorem holds for n voters and prove that it
also holds for n + 1 voters
...
, 2 )
for all 1 , 2 ∈ L(A)
...
7, g is surjective as well
...
By strategyproofness of f , the
manipulator must be voter 2, so there must exist 1 , 2 , 02 ∈ L(A) and a, b ∈ A
such that g( 1 , 2 ) = a, g( 1 , 02 ) = b, and b 2 a
...
, n, let k =
( 1 , 02 ,
...
, 2 ) ∈ L(A)n+1 be the preference profile where k voters have
preference order 02 and n − k voters have preference order 2 , and let ak = f ( k )
...
It follows that g is strategyproof,
and therefore dictatorial
...
6 voter 1 must also be a dictator for
f
...
, n+1 ) = f ( ∗1 , 2 ,
...
Then, h is strategyproof by strategyproofness of f , and
surjective because voter 2 is a dictator for g
...
Assume without loss of generality that the dictator for h is voter 2, and let e : L(A)2 →
A be given by
e( 1 , 2 ) = f ( 1 , 2 , ∗3 ,
...
, ∗n+1 ∈ L(A)
...
In fact, the dictator for e must be voter 2, because voter 1 is not a dictator
for g and thus cannot be a dictator for e
...
, n + 1 was chosen
arbitrarily, it follows that voter 2 is a dictator for f
...
1
Auctions
Types of auctions
Flowers, wines, art, U
...
treasury bonds, government contracts, and real estate are sold
in auctions (and indeed the Roman empire was auctioned by the Praetorian Guards in
A
...
193)
...
An auction is a type of multi-player game
...
It is a partial information game because
each bidder’s valuation of an item is hidden from the auctioneer and other bidders
...
These rules can affect the revenue
obtained by the seller, as well as how much this varies in successive instants of the
auction
...
An auction design is said to be economically efficient, if it allocates the item to
the bidder who values it most
...
There is no one
auction design that is efficient and can be applied in most situations
...
As bidding takes place, his valuation
does not change, though he gains information from the other players’ bids
...
Think, for example, of a jar
of coins
...
In this case
the winner generally overestimates the value (since he had the highest estimate), and
so he pays more than the jar of coins is worth
...
Auctions can be oral (bidders hear each other’s bids and make counter-offers) or written (bidders submit sealed-bids in writing)
...
Dutch auction: the price decreases continuously until some bidder calls stop
...
English auction (or ascending price auction): bids increase in small increments until only one bidder remains
...
first price sealed-bid: the winner pays his bid
...
second price sealed-bid (or Vickrey auction): the winner pays the second
highest bid
...
all-pay sealed-bid auction: highest bidder wins, but all pay their bid
...
Auctions
2 and 4 are equivalent (the item selling for the second greatest valuation)
...
2
The revenue equivalence theorem
The symmetric independent private values model (SIPV) concerns the auction of
a single item, with risk neutral seller and bidders
...
i
...
random variables
...
Lemma 21
...
In any SIPV auction in which the bidders bid optimally and the item
is awarded to the highest bidder, the bids are ordered the same as the valuations
...
Consider an auction satisfying the terms of the lemma
...
Notice that e(p) must be a convex function of p, i
...
e(αp + (1 − α)p0 ) ≤ αe(p) +
(1 − α)e(p0 )
...
Since e(p) is convex it is differentiable at all but a countable number
of points
...
Assuming that p is chosen optimally, the relation
between p and θ is determined by
∂π
= θ − e0 (p) = 0
...
1)
Since e0 (p) is nondecreasing in p, it follows that p(θ) must be nondecreasing in θ
...
We say that two auctions have the same bidder participation if any bidder who finds
it profitable to participate in one auction also finds it profitable to participate in the
other
...
Theorem 21
...
The expected revenue obtained by the
seller is the same for any two SIPV auctions that (a) award the item to the highest
bidder, and (b) have the same bidder participation
...
Suppose there are n bidders
...
1) we have
d
e(p(θ)) = e0 (p)p0 (θ) = θp0 (θ)
...
By assumption (b) this
is the same for any auction being considered
...
2)
θ∗
∗
∗
θ∗
∗
where e(p(θ )) = θ p(θ ) and so
Z
θi
e(p(θi )) = θi p(θi ) −
p(w) dw
...
We know
from Lemma 21
...
Pn Assume for simplicity that
limx→∞ x(1 − F (x)) = 0
...
This is
#
Z ∞ "
Z θ1
nEθ1 (p(θ1 )) = n
θ1 p(θ1 ) −
p(w)dw f (θ1 )dθ1
θ1 =θ ∗
Z
θ∗
∞
=n
Z
θ1
θ1 p(θ1 )f (θ1 )dθ1 + n(1 − F (θ1 ))
θ1 =θ ∗
θ∗
Z
Z
∞
=n
θ1 =θ ∗
∞
p(w)dw
θ1 =θ ∗
∞
−n
(1 − F (θ1 ))p(θ1 )dθ1
∗
! θ
1 − F (θ1 )
F (θ1 )n−1 f (θ1 )dθ1
θ1 −
f (θ1 )
(21
...
4)
where (21
...
Example 21
...
Assume valuations are i
...
d
...
(a) We might simply offer the item at price p and see if any player values it above p
...
nF (p)n−1 f (p)
p
For the distribution U [0, 1], F (u) = u, and thepoptimal price is p∗ = n 1/(np+ 1), and
n
∗
the resulting (expected) revenue
p is [n/(n + 1)] 1/(n + 1)
...
3849
...
e
...
From (21
...
So in all these
auctions the seller’s expected revenue is 2E[θ2 /2] = 1/3 = 0
...
101
The optimal bids differ in the different auctions
...
In the Dutch or first price sealed-bid auctions,
a bidder’s expected payment is p(θ) times his bid
...
In the second price sealed-bid (Vickrey) auction, the winner
pays the bid of the second highest bidder
...
For every possible value of θ2 , this is maximized by bidding u = θ1
...
However, in (a) he assumes
information about the distribution of the valuations
...
Example 21
...
Consider a 3-person game in which player 0, the government, solicits
tenders from two contractors to do a piece of work
...
If the government could know the low
bidder’s cost and pay just a bit above that then its expected payment would be a bit over
E min(C1 , C2 ) = 1/3, which we call first best
...
By a
similar analysis we find that a contractor with cost Ci will bid (1 + Ci )/2
...
We say that the price of anarchy is (2/3)/(1/3) = 2
...
3 consider risk sensitivity
...
Again, consider (a)
...
In
an all-pay sealed-bid auction each pays half the square of his valuation and revenue is
1 2
1 2
2 θ1 + 2 θ2
...
All these have expectation 1/3, but the variances are 1/72, 2/45 and 1/18 respectively
...
21
...
We are given a set of agents N = {1,
...
Agent
i has private knowledge of his type, say θi ∈ Θi , where Θi is the set of his possible
types
...
The idea is that the agents send messages to the mechanism, providing information
about their types, and as a function of these messages the mechanism selects an alternative f (θ) from a set A
...
e
...
A direct mechanism with payments, (f, p),
receives the agents’ type declarations θ = (θ1 ,
...
It is convenient to write θ = (θi , θ−i ), where θ−i is the vector
of types declared by agents other than i
...
5)
where vi : A × Θi → R is a valuation function over alternatives, agent i has true type
θi , declares θi0 , and pays pi (θi0 , θ−i ) = (p(θi0 , θ−i ))i
...
A direct mechanism is called
incentive compatible, or strategyproof if it is a not manipulable
...
That is,
ui (f (θi , θ−i ), θi ) ≥ ui (f (θi0 , θ−i ), θi ),
for all θi0 ∈ Θi
...
One natural
objective
is to maximize social welfare
...
e
...
For example, in a sealed-bid auction an agent’s type corresponds to his valuation θi
and in a direct mechanism he bids a valuation
...
The equilibrium condition is that Eθ−i ui (f (θi0 , θ−i ), θi ) is maximized by
making the truthful declaration θi0 = θi , where the expectation is taken using a prior
distribution over θ−i , which denotes the vector of the other agents’ types and assumes
they are all declaring truthfully
...
In an auction, maximizing social
welfare means maximizing the expected valuation of the bidder who wins the item
...
1
Optimal Auctions
Revelation principle
One might think that arbitrarily complicated mechanisms would be needed to implement certain desired results
...
These are called direct revelation
mechanisms
...
Theorem 22
...
A direct revelation mechanism can generally be
designed to achieve the same result as any other mechanism
...
Consider some mechanism, f , which implements some result (an equilibrium)
via agents making untruthful revelations about their types
...
Then it is an equilibrium of f 0 for players to truthfully
report to f 0
...
This is important because it means that if we wish to design an optimal mechanism
(e
...
maximizing the seller’s expected revenue), we may restrict attention to mechanism
that incentivize truthtelling
...
22
...
The crucial component is the term j∈N \{i} vj (f (θ), θj ), which is equal to the social
welfare for all agents but i
...
The latter does not depend on θi and therefore has no strategic implications
...
2
...
Proof
...
Then,
ui (θ, θi ) = vi (f (θ), θi ) − pi (θ)
104
=
X
vj (f (θ), θj ) − hi (θ−i )
j∈N
≥
X
vj (f (θi0 , θ−i ), θj ) − hi (θ−i )
j∈N
= ui (f (θi0 , θ−i ), θi ),
where the inequality holds because f (θ) maximizes social welfare with respect to θ
...
Strategyproofness holds for any choice of the functions hi , so it is natural to ask for a
good way to define these functions
...
Formally, mechanism (f, p) makes no positive transfers if pi (θ) ≥ 0 for all i ∈ N and
θ ∈ Θ, and is ex-post individually rational if it always yields non-negative utility
for all agents, i
...
if vi (f (θ), θi ) − pi (θ) ≥ 0 for all i ∈ N and θ ∈ Θ
...
The so-called Clark
pivot rule sets hi (θ−i ) = maxa∈A j∈N \{i} vj (a, θj ), such that the payment of agent
P
P
i becomes pi (θ) = maxa∈A j∈N \{i} vj (a, θj ) − j∈N \{i} vj (f (θ), θj )
...
e
...
The payment
makes the agent internalize this externality
...
The one with highest valuation wins and pays the
second highest valuation
...
This is the second-price, or Vickrey, auction
...
22
...
Each bidder’s valuation is private information, and valuations of the
bidders can be modelled as i
...
d
...
We ask the bidders to declare their valuations, say θ1 ,
...
As a function of these
declarations, θ = (θ1 ,
...
Suppose that we are designing a direct revelation mechanism
such that it is optimal for all bidders to declare their valuations truthfully
...
...
,
θ
,
...
...
...
,
θ
,
...
...
1)
0
θi
where Eθ−i denotes expectation with respect to the other bidders’ valuations, and Vi
and Pi are defined implicitly in (22
...
They are the probability of winning the item,
and the expected payment of agent i, when he declares θi0
...
Supposing his true valuation is θi , that derivatives exist and agent i has
maximum profit at a stationary point, we require
d
(22
...
Suppose there is some θi∗ such that
θi Vi (θi ) − Pi (θi ) ≥ 0 iff θi ≥ θi∗ , and θi∗ Vi (θi∗ ) − Pi (θi∗ ) = 0
...
2) we have
Pi (θi ) = Pi (θi∗ ) +
θi
Z
θi∗
Z
= θi Vi (θi ) −
Z
EPi (θi ) =
∞
θi
∞
=
θi∗
Vi (w) dw
...
θi
θi Vi (θi ) −
θi∗
Z
θi Z
wVi0 (w) dw = Pi (θi∗ ) + wVi (w) ∗ −
(22
...
4)
where (22
...
3)
...
4), which
was derived by supposing a bidder bids optimally; here we find the same thing, but
the derivation is via the incentive compatibility condition (22
...
Let
g(θi ) = θi −
1 − F (θi )
...
The auctioneer’s expected revenue is
"
#
X
XZ ∞
X
EPi (θi ) =
g(θi )Vi (θi )f (θi ) dθi = E
φi (θi )g(θi )vi (θ1 ,
...
Consider, for example, the case that θ1 ,
...
Then
g(θi ) = 2θi − 1, θi∗ = 1/2, Vi (θi ) = θin−1 , and then from (22
...
n i
n2
For instance, if n = 2 we might take pi (θi ) = Pi (θi ) = θi2 /2 + 1/8
...
Thus a player with valuation θi will
declare θi = u so as to maximize
θi u − (u2 /2 + 1/8)
...
The expected
sum of the payments is
Z
1
2EP1 (θ1 ) = 2
1/2
(1/8 + θi2 /2) dθi = 5/12,
which exceeds the 1/3 we have seen in other auctions
...
There are other ways to create an optimal auction (i
...
one that maximizes seller’s
revenue)
...
Bidder
1 in this auction pays p0 if bidder 2 has valuation less than p0 , and otherwise pays
Rθ
Bidder 2’s valuation if θ1 > θ2 > p0
...
The seller’s expected revenue is maximized by p0 = 1/2
...
Now bidder 1 will participate only if θ1 > θ∗ , and
in that case if he bids u then his expected payment is
Z
u
c+
θ2 dθ2 = c + (u − θ∗ )
θ∗
θ∗ + u
...
One can check
that the seller’s expected revenue is maximized by c = 1/4, θ∗ = 1/2
...
, θn are i
...
d
...
107
22
...
For example, (22
...
The auctioneer’s expected revenue is
P
E [ i φi (θi )gi (θi )vi (θ1 ,
...
So the optimal auction mechanism awards the item to the bidder i for whom gi (θi ) is
both maximal and nonnegative
...
To prove that it this
payment scheme works we should do a calculation to check that the expected payment
of bidder i, when she has valuation θi , is indeed Pi (θi ) as given in (22
...
Example 22
...
An interesting property of optimal auctions with heterogeneous bidders is that the winner is not necessarily the highest bidder
...
In this case gi (θi ) = θi − (1 − θi )/1 = 2θi − 1
...
e
...
The winner pays
either 1/2 or the second greatest bid, whichever is greatest
...
This agrees with what we have found above
...
So g1 (θ1 ) = 2θ1 − 1, θ1∗ = 1/2,
and g2 (θ2 ) = 2θ2 − 2, θ2∗ = 1
...
e
...
For example, if θ1 = 0
...
2,
then 1 should be declared the winner and pay 0
...
4)
...
1
Paying for a club good
Suppose we propose to provide a new web service that allows its users to share digital
content in the cloud
...
If we do build it, some persons are told the login password, while others
can be excluded
...
Agent i will obtain utility
θi v(Q), where Q is the size of the facility, which is built at cost c(Q)
...
However, it is public knowledge a priori that θi is distributed
with distribution function Fi
...
Our problem is to design a mechanism in which (i) agents declare values of θi , (ii) as
a function of declared θ1 ,
...
The analysis follows the same lines in Lecture 22
...
Fix a mechanism and suppose
that under this mechanism if agent i declares θi , then the expected value of v(Q) is
Vi (θi ) = Eθ−i [v(Q(θ)) | θi ], and his expected payment is P (θi )
...
If this is to be made maximal (and stationary) by the truthful declaration θi0 = θi then
we need θi Vi0 (θi ) − Pi0 (θi ) = 0
...
As before, let g(θi ) = θi − [1 −
F (θi )]/f (θi )
...
, θn ))f (θ1 ) · · · f (θn ) dθ1
...
, θn ))f (θ1 ) · · · f (θn ) dθ1
...
, θn ))]
109
where φ(θi ) is 1 or 0 as θi ≥ θi∗ or θi < θi∗
...
This threat is part of the incentive for agents not to understate their types
...
, θn )) − c(Q)
E
(23
...
This constraint is difficult
to handle, so let us instead consider a weaker constraint, that the expected payments
cover expected cost, i
...
X
E[φ(θi )g(θi )v(Q(θ1 ,
...
, θn ))]
...
2)
i
This leads us to the Lagrangian, combining (23
...
2),
Z
Z X
L=
···
φ(θi )(θi + λg(θi ))v(Q(θ1 ,
...
, θn )) f (θ1 ) · · · f (θn ) dθ1
...
which is to be maximized pointwise in the integrand with respect to φi s and Q
...
To illustrate ideas, let us suppose that θi ∼ U [0, 1], so g(θi ) = 2θi − 1
...
e
...
Otherwise φi (θi ) = 0
...
For a given λ ≥ 0 we know how to find the φi
...
Q
i
The solution is completed by finding the value of λ such that the expected payments
taken from the agents match expected cost
...
However, as
n becomes large, one can prove that nearly the same welfare can be achieved by a
simple scheme that announces that the facility will be of size Q∗ and charges a fixed
subscription fee p∗ to any agent who then chooses to participate, which will be agents
for whom θi v(Q∗ ) − p∗ ≥ 0
...
110
Example 23
...
Suppose a facility may or may not be built
...
There are two agents, whose utility for the facilty are θ1 , θ2 , which are a priori
distributed independently U [0, 1]
...
The expected social welfare would be E[(θ1 + θ2 − 1)+ ] =
1/6 = 0
...
This solution is called first best
...
25
...
25)+ ] = 9/64 =
0
...
The payments can be
(
1
1 2
θi > 41 ,
2 θi − 32 ,
P (θi ) =
0, otherwise
...
P (θ1 ) + P (θ2 ) 6= 1{θ1 +θ2 ≥1
...
Also, payments are taken even when the facility is not built
...
2
Ex-post budget balance
It is possible, to take the above mechanism, in which there is ex-ante budget balance,
and strengthen it to a mechanism in which is ex-post budget balanced, i
...
where
payments cover cost exactly
...
Pick two agents, say 1 and 2
...
Now there is ex-post budget balance because
P
P
i pi (θ) =
i P (θi ) + x(θ) = c(Q(θ))
...
111
Applying this to Example 23
...
25}
p1 (θ) = 21 1{θ1 +θ2 ≥1
...
25}
and p2 (θ) is symmetrical
...
An even better scheme is
p∗1 (θ) = 31 (θ1 − θ2 ) + 12 1{θ1 +θ2 ≥1
...
This design has the advantages that (i) it is incentive compatible, (ii) p1 (θ) ≥ 0, (iii)
p1 (θ) + p2 (θ) = 1{θ1 +θ2 ≥1
...
However, we
cannot have everything ex-post
...
23
...
We will take a discretized model in which θ takes values t1 , t2 <
· · · < tm with equal probability
...
Start with
a mechanism that is ex-ante budget balanced but not ex-post budget balanced
...
, θn ) for which
p1 (θ) + · · · + pn (θ) > c(Q(θ))
...
Case I
...
Suppose i = 1
...
, θn ) = p1 (θ1 , θ2 ,
...
, φn ) = p1 (θ1 , φ2 ,
...
Increase until there is exact budget balance with either θ, φ (or
both)
...
So incentives
do not change
because when agent 1 has type θ1 his expected payment is E p∗1 (θ) θ1 = E p1 (θ) θ1
...
If θ1 6= φ1 and θ2 6= φ2
...
, θn ) = p1 (θ1 , θ2 , θ3 ,
...
, θn ) = p1 (θ1 , φ2 , θ3 ,
...
, θn ) = p2 (θ1 , φ2 , θ3 ,
...
, φn ) = p2 (φ1 , φ2 , φ3 ,
...
The effect can be appreciated in a table
p1
θ1 , θ2 , θ3 ,
...
, θm
+
φ1 , φ2 , φ3 ,
...
The
three rows of the table are equally likely
...
g
...
One
can repeat this process, always preserving the same incentives, until budget balance is
obtained for every vector of types
...
By a similar adjustment mechanism it is possible to show that there exists a mechanism
design which has ex-post budget balance, and the additional property that
φi (θ) = 0 =⇒ pi (θ) = 0
...
As
with Arrow’s theorem, and the Gibbart-Satterwaite theorem, we find it is impossible
to simultaneously satisfy ex-post versions of budget balance, individual rationality and
incentive compatibility
Title: Mathematics of Operational Research - 2016 Notes
Description: University of Cambridge - Part III Mathematics/Certificate of Advanced Study in Mathematics/Masters of Mathematics Mathematics of Operational Research: notes, based on lectures notes by Richard Weber, the book Introduction to Linear Optimization and the book Games, Theory and Applications, by L.C. Thomas. Covering optimization (including primal simplex, dual simplex and integer linear programming), algorithms on graphs, a very short section on complexity theory, game theory (zero-sum games, non-zero-sum games, cooperative games, bargaining, market games and evolutionary games) and regret minimization. An example of using Gomory's Cutting Plane method to solve an integer linear program.
Description: University of Cambridge - Part III Mathematics/Certificate of Advanced Study in Mathematics/Masters of Mathematics Mathematics of Operational Research: notes, based on lectures notes by Richard Weber, the book Introduction to Linear Optimization and the book Games, Theory and Applications, by L.C. Thomas. Covering optimization (including primal simplex, dual simplex and integer linear programming), algorithms on graphs, a very short section on complexity theory, game theory (zero-sum games, non-zero-sum games, cooperative games, bargaining, market games and evolutionary games) and regret minimization. An example of using Gomory's Cutting Plane method to solve an integer linear program.