We must check that allowing introduces no false feasible solution. If , then . The recession cone of the nonempty linear polyhedron is . Indeed for , for every . Boundedness of therefore forces , contradicting . Thus every transformed feasible point has .
Conversely set . The constraints give and , with the same objective value. The assumed original optimizer with positive denominator supplies a transformed feasible point. Every transformed point corresponds to an original point and has objective at most that optimizer's value. Hence the transformed linear program attains the original optimum, and its optimizer recovers . Positivity on every point of is not needed here; the given positive-denominator optimum suffices.
The feasible triangle has verticesThese come from the three pairs of active boundary lines and satisfy the remaining inequalities. Its denominator is positive at each vertex, with minimum , so is positive throughout the triangle because it is an affine function.
For a direct linear programming optimality certificate, add twice the second inequality to the third to get . Thus , equivalently . Division by the positive denominator gives an objective at most . Both inequalities used in the bound are equalities at , where the first inequality is also satisfied. ThereforeEquality requires the two bounding inequalities to be tight, so this optimizer is unique.
The feasible point makes the second and third constraints tight; the first has left side two. Its objective is .
To prove optimality from first principles, multiply each of the second and third inequalities by and add. For every nonnegative feasible ,This is an explicit weak duality bound, proved here simply by adding inequalities. The displayed point attains it, soEquality forces and both contributing constraints tight, proving uniqueness as well.
The same weak duality certificate gives the upper bound for every feasible point. Keep and solve the tight second and third constraints:These are nonnegative precisely when their numerators are nonnegative. The remaining first-constraint slack is . All three are positive for sufficiently small perturbations, so the point is feasible and attains the bound. This illustrates linear programming sensitivity within a fixed optimal basis:More generally this expression is valid throughout the region specified by those three feasibility inequalities.
With , the conditions reduce toThe endpoints are included. Outside this interval the bound cannot be attained: its equality conditions require exactly the point above, which then has a negative or violates the first constraint. Whenever feasible, the problem attains a maximum because the first constraint and nonnegativity bound all coordinates, so its value is strictly smaller outside the interval. For it is infeasible. Thus the range is exact, not just a sufficient neighborhood.
Use safety for failure counts within the available components, equivalently tolerance of up to that many failures. An exact-count condition with more failures than components would otherwise be vacuous. Assume the client is not itself a server; that exceptional case needs no network connection.
Create a flow network by replacing each undirected link by two oppositely directed arcs of capacity one. Add a new sink and arcs from every server to , each of capacity . Find a maximum flow from to with the Edmonds–Karp algorithm. By the max-flow min-cut theorem, its value is the minimum cut capacity. A cut using a server-to-sink arc costs at least , whereas cutting all original links costs at most , so a minimum cut uses none of the added arcs.
A source-side cut therefore contains no server. Each original undirected edge crossing it contributes exactly one of its two arcs, so its capacity is the number of original links separating the client from every server. Conversely, if a set of failed links disconnects all servers, the vertices still reachable from define a cut contained in that failed set. Thus is exactly the minimum number of links whose failure can disconnect the client from all servers. This is server connectivity under component failures.
Deleting fewer than links leaves some connection, while deleting a minimum cut destroys every connection. ThereforeIf , the network is already disconnected and has no nonnegative safe failure count. The transformed graph has vertices and arcs. The Edmonds–Karp algorithm runs in steps, so both the construction and computation are polynomial in the original graph size.
Use vertex splitting to encode node failures as well as link failures. Replace each vertex by and an internal arc . Give that arc capacity one for an intermediary node, and capacity for the client and servers. Replace an undirected link by arcs and , each of capacity one. Connect server outputs to a common sink with capacity and take as source.
A minimum cut avoids capacity- arcs because failure of all original links provides a cheaper separating set. We can normalize its source side so that being on that side implies is also there: moving to that side cannot increase the cut capacity, since its sole outgoing arc leads to . In such a cut, at most one direction of any original link crosses. Every unit internal arc crossing corresponds to failing its intermediary node; every unit link arc corresponds to failing that link. Their failures disconnect all servers, so the cut capacity is the cost of a real failure set.
Conversely remove the internal arcs of failed nodes and both arcs of failed links. The reachable-side cut contains only arcs corresponding to those failures, with at most one crossing orientation per failed link; its capacity is at most their number. The max-flow min-cut theorem thus identifies the minimum mixed failure count exactly. HenceThe split graph has vertices and arcs, so the same Edmonds–Karp algorithm gives a polynomial-time decision procedure.
Name the outer pentagon vertices, in order from the client clockwise, . Name the upper inner vertex , the left inner vertex , and the lower-right inner vertex . The two remaining inner vertices are the labelled servers .
Four edge-disjoint server paths areEach uses different links, although some intermediary vertices are shared. Any three failed links therefore leave at least one path intact. The client has exactly four incident links; failing those four disconnects it. Thus the minimum link cut has size four, givingFor mixed failures use the three paths , and . Their internal vertices are disjoint, as are their links. One failed link or intermediary node can destroy at most one of these paths, so any two failures leave a path intact. Failing the three intermediary nodes disconnects both servers: has neighbors , and has neighbors . ThereforeThe two certificates distinguish edge-disjoint paths from internally vertex-disjoint paths, exactly the distinction needed between the two failure models.
Use net monetary gain as payoff and order each player's pure strategies as . The payoff matrix for the first player isThe second player's matrix is . Equal choices return both stakes, so the diagonal is zero; when the first player wins, their net gain is the other's stake, and when they lose it is minus their own stake. This is a matrix game, hence a zero-sum game and a normal-form game.
The game is degenerate in the nondegeneracy of a bimatrix game sense. Against the first player's pure strategy , the second player's choices and are both best responses, with payoff four. A mixed strategy of support size one therefore has two pure best responses. The usual Lemke-Howson algorithm path needs additional tie handling or perturbation in such a game; the zero-sum game structure gives a simpler direct linear program.
Add five to every entry of the first player's matrix, obtainingThis does not change either player's best responses or Nash equilibria; it raises the game value by five. Since all entries are positive, its value is positive. If is a row mixed strategy guaranteeing , put . Then and .
Conversely any feasible has , and guarantees payoff in the shifted game. Maximizing that guaranteed payoff is therefore equivalent to minimizing under , . These are precisely the displayed constraints. The dual program maximizes subject to , ; normalizing an optimal gives the column strategy. This is positive-payoff linear programming for a matrix game.
Introduce nonnegative surplus variablesAt the proposed starting basic feasible solution, the basic variables are and the nonbasic variables are . Its simplex dictionary, with objective , isIncrease to decrease . The simplex ratio test gives limits from , from , and from . The smallest is , so enters and leaves. After this single pivot the dictionary isAll objective coefficients of nonbasic variables are strictly positive. Thus the simplex method has reached its unique optimum:The feasible dual vector has the same objective, providing an independent weak duality certificate. Normalization givesThese are all the equilibria: the dual's strict slack in row two forces , and the primal's strict slack in column two forces . Equality of the two active row and column payoffs then fixes the displayed probabilities. The value is the first player's expected net loss; the second gains .
For a fixed number choice, increasing one's own stake changes only the amount lost when one loses. It does not change the amount won, which is the opponent's stake, or the zero payoff of a tie. Thus doubling is either weakly dominated by retaining the original stake or payoff-equivalent to it. This establishes that there is no strategic advantage in doubling, but does not imply strict harm in every equilibrium.
For the first player, each of the two equilibrium choices loses with positive probability: choice one loses against the second player's four, and choice four loses against their one. Doubling either therefore gives a strictly smaller expected payoff than . By contrast, against the first player's support , the second player's choices one and four either win or tie. Their own stake is never lost, so doubling it does not change their payoff.
More precisely, retain the first player's original-stake probabilities . The second player may split their total probability on choice one, and on choice four, arbitrarily between original and double stakes. The first player's unused choice two has payoff at most , even when the second player doubles their one stake. The doubled first-player choices are also worse. The second player's choice two, with either stake, is worse against the displayed first-player strategy. Hence these splits remain Nash equilibria of the enlarged zero-sum game.
The first player should not double; the second player is indifferent between doubling and retaining the original stakes on their equilibrium choices. This distinction is an example of weak domination does not exclude equilibrium strategies.
Give each permanent member weight seven, each nonpermanent member weight one, and use the strict threshold . If a coalition omits a permanent member, its weight is at most , so it loses. If it includes all five permanent members and others, its weight is , which exceeds 38 exactly when . These are precisely the required winning coalitions. Thus a weighted voting game representation isThe strict-threshold convention is important: in the alternative convention requiring weight at least the quota, the quota is 39.
For a simple cooperative game, the Shapley value is the probability that a player is pivotal in a uniformly random ordering. Symmetry gives one value for permanent members and another for nonpermanent members.
A particular nonpermanent member is pivotal exactly when all five permanent members and exactly three of the other nine nonpermanent members precede them. The predecessor set then has size eight. There are such sets, each giving orderings. Their Shapley value is thereforeEvery ordering has exactly one pivotal member, since the empty coalition loses and the full coalition wins. This proves efficiency directly: , where is the value of each permanent member. HenceThe vector has five entries and ten entries . As a check, a permanent member is pivotal when they are last among the permanent members and occupy a position from nine to fifteen; counting those orderings gives the same .
False. Take three players of weight one and strict threshold one, so a coalition wins exactly when it contains at least two players. Set and . ThenThe convex cooperative game inequality would require . Thus even this elementary majority weighted voting game is not convex.
True, with the usual normalization . For a convex cooperative game, the supermodular inequality implies increasing marginal contributions: if and , apply it to and to obtainFix an ordering and let be the set of players before . Its marginal contribution vector is . Summing in order telescopes to . For any coalition , , so increasing marginals giveThese are exactly the efficiency and coalition constraints of the core of a cooperative game. Thus every marginal contribution vector is in the core. The core is a convex set, being an intersection of linear half-spaces and an efficiency hyperplane. The Shapley value is the average of the marginal contribution vectors over all orderings, so it too lies in the core. This proves Shapley value belongs to the core of a convex game, without needing a separate existence theorem for the core.
Let be the number of true values among . Count the ten clause occurrences for the two choices of . With , the three positive singletons contribute , the three negated-pair clauses contribute , and the last three clauses all hold. With , the four singleton clauses contribute , the negated pairs again contribute , and the last three contribute . ThereforeThe original three-literal clause is satisfied exactly when , and then a value of satisfies exactly seven gadget clauses. If , no choice reaches seven. Thus the required equivalence holds, and seven is also an upper bound for every assignment to the gadget. This is the seven-clause gadget for MAX-2SAT.
The decision problem is in NP: an assignment is a certificate, and counting its satisfied clause occurrences is polynomial in the input size.
Reduce 3-SAT to it. For each of the original clauses, use the seven-clause gadget for MAX-2SAT with its three literals in place of and with a fresh auxiliary variable. Keep all ten clause occurrences per gadget, including any repeated occurrences across gadgets. Set the target to .
If the original formula is satisfiable, choose each auxiliary value as in part (a), giving seven satisfied clauses per gadget. Conversely, no gadget can exceed seven. If an assignment satisfies at least clauses in total, every gadget must reach seven, so every original clause is satisfied by the original-variable assignment. The construction has clauses and auxiliary variables, so is polynomial. Consequently the decision version of MAX-2SAT is NP-complete.
Use the usual nonempty-clause convention and normalize repeated literals within a clause; tautologies are always satisfied. If empty clauses are admitted, discard them first: they contribute nothing to any assignment or to the optimum. Let be the resulting number of clause occurrences.
Assign independent fair truth values. A singleton clause is satisfied with probability , a proper two-variable clause with probability , and a tautology with probability one. By linearity of expectation, the expected number satisfied is at least , hence at least .
To derandomize, use the method of conditional probabilities. After some variables have been fixed, let be the conditional expected number of satisfied clauses. For the next variable the two conditional expectations satisfy . Fix the value with the larger expectation. This never decreases . When all variables have been fixed, is the actual integer number of satisfied clauses, soCompute each conditional expectation by summing the probabilities of the clauses. Each has at most two variables, so its contribution is computed in constant time; scanning all clauses for each variable gives arithmetic operations. This is a polynomial-time approximation algorithm with approximation ratio .
Apply the condition after the usual clause normalization, so each variable has at most one singleton clause. For a variable with such a clause, make its favored literal true with probability ; for other variables use a fair value. Make these choices independently. Then every singleton is satisfied with probability .
Each literal of a proper two-variable clause is true with probability at least . Independence bounds the probability that both are false by , so the clause is satisfied with probability at least . Tautologies have probability one. Thus the expected fraction satisfied is at least . One term increases and the other decreases, so their intersection maximizes this bound:The method of conditional probabilities also works with these biased probabilities: before fixing a variable, the current expectation is the weighted average of its two conditional expectations, so choosing the larger cannot decrease it. Each clause contributes a constant-degree expression in ; since , these expectations can be compared exactly in the fixed quadratic field with polynomial bit complexity. The final deterministic assignment therefore hasThis is the golden ratio approximation for MAX-2SAT, under the stated restriction on normalized singleton clauses. Arbitrary conflicting singleton clauses do not admit the same independent-bias guarantee.
Articles by others on the same topic
There are currently no matching articles.