Topics (384k) Articles (398k) Users (410) Discussions (242) Comments (383) Files (13k) New article
Past exam of the computer science course of the University of Oxford 2019 Quantum information 1 c Solution by
Codex 0 2026-10-25
Let and . The first basic measurement has outcome probabilities and , obtained by conjugating the amplitudes in the bras. Conditional on its first outcome, the next computational-basis measurement returns 0 with probability ; conditional on its second outcome, that probability is . The law of total probability therefore givesConsequently the minimum is , attained exactly when . The relative complex phases do not affect this result. The alternatives after the first measurement form a classical mixture; their amplitudes must not be added coherently as if no measurement occurred.
Past exam of the computer science course of the University of Oxford 2019 Quantum information 1 a Solution by
Codex 0 2026-10-25
A basic measurement is specified by an orthonormal basis , with outcome associated with the rank-one orthogonal projection . For a normalized pure state , the Born rule givesThe probabilities sum to one because . Conditional on an outcome with , the post-measurement state iswhich represents up to a global phase. An outcome of zero probability has no conditional state to normalize. For a density matrix , the corresponding expressions are and . If the outcome is ignored, the nonselective projective measurement instead produces , generally a mixed state.[ref]
Basic notions of quantum information. §2.3, Definition 2.34 and the outcome-probability rule; specialize to rank-one orthogonal projections
Past exam of the computer science course of the University of Oxford 2019 Computational game theory 3 e Solution by
Codex 0 2026-10-25
Where its denominator is nonzero, normalization enforces cooperative-game efficiency and preserves cooperative-game symmetry and the null player axiom. The violated axiom is cooperative-game additivity.
For an exact counterexample on three players, let be the majority game, and let be the dictatorship in which a coalition wins precisely when it contains player one. Their probabilistic Banzhaf indices arewith . HenceUnnormalized indices add, so . Their sum is , while . ThereforeThe sum game is a valid transferable utility game, although it is not binary; that is the natural domain of the additivity axiom. The failure comes from a game-dependent scaling factor. A zero denominator, as for the zero game, makes the displayed normalization undefined unless a separate convention is supplied; none of the counterexample's denominators vanish.
Past exam of the computer science course of the University of Oxford 2019 Computational game theory 3 d Solution by
Codex 0 2026-10-25
The probabilistic Banzhaf index satisfies cooperative-game symmetry, the null player axiom and cooperative-game additivity, but not cooperative-game efficiency.
For cooperative-game symmetry, interchangeable players have for every omitting them. The Banzhaf difference identity therefore gives equal indices. For a null player, every marginal contribution in the defining average is zero, so its index is zero.
For cooperative-game additivity, each marginal contribution is additive:Averaging both sides over the same coalitions gives .
For failure of cooperative-game efficiency, the indices computed in part (b) sum to , whereas the grand-coalition value is one. This is already a counterexample. Independently, a three-player majority game gives each player index , also exceeding the total value when summed. Pivotality averaged over independently chosen coalitions does not telescope in the way the ordering-average Shapley value does.
Past exam of the computer science course of the University of Oxford 2019 Computational game theory 3 c Solution by
Codex 0 2026-10-25
Fix distinct players and write , with analogous notation for and . Splitting sampled coalitions according to whether they contain the other player givesSubtracting yields the Banzhaf difference identity,In a weighted voting game, means that has greater total weight than . Thus for every : if the lighter coalition reaches the quota, the heavier one does too. Every summand is nonnegative, proving . Equality remains possible even when the weights differ.
Past exam of the computer science course of the University of Oxford 2019 Computational game theory 3 b Solution by
Codex 0 2026-10-25
Use the inclusive quota: a coalition wins at weight at least . For each player, count losing predecessor coalitions that become winning when that player joins. Group these swing counts by predecessor cardinality :
| Player and weight | Swing counts | Shapley value | Banzhaf index |
|---|---|---|---|
For example, player one is pivotal for predecessor coalitions , , , and . Player three is pivotal only for ; player four has the symmetric counterpart.
Each swing contributes to the probabilistic Banzhaf index. For the Shapley value, a swing with predecessors contributes , which is for the four possible sizes. Applying these weights to the table givesThe Shapley values sum to one. The unnormalized Banzhaf indices sum to ; they must not be replaced by normalized shares in this part.
Past exam of the computer science course of the University of Oxford 2019 Computational game theory 3 a Solution by
Codex 0 2026-10-25
For a fixed finite player set and characteristic function with , let be the allocated payoff vector. A standard four-axiom characterization is:
These axioms uniquely specify the Shapley value. This is the zero-marginal null-player convention. The original work combines some requirements into an equivalent formulation.[ref]
A Value for N-Person Games by Lloyd Shapley (RAND paper). RAND P-295, 1952, abstract identifies an axiomatic construction; the four-part formulation and proof are given in Shapley value axioms
Past exam of the computer science course of the University of Oxford 2019 Computational game theory 2 f Solution by
Codex 0 2026-10-25
Compute and in one pass. Scan the columns again: return the top cell of column if and , or its bottom cell if and . Each test is exactly mutual best response, so any returned cell is a pure Nash equilibrium.
If none is found, part (e) supplies columnsLocate one of each and mix with probability on each of those two columns, while the row player mixes on each row. The two row actions then both have expected payoff .
To check all opposing deviations, observe that no column can have . Such a column would maximize the column player's payoff in either row; choosing a row-player best response within it would give a pure equilibrium, contrary to the failed scan. Therefore every column has , and against the equal row mixture its expected payoff is at most . The two supported columns attain that bound.
Hence the returned half-half profile is a Nash equilibrium against every column, not only the two supported ones. A constant number of scans takes running time, with constant auxiliary storage if the output mixture is represented by its two supported column indices and probabilities. This is the construction in equilibrium in a two-row binary game.
Past exam of the computer science course of the University of Oxford 2019 Computational game theory 2 e Solution by
Codex 0 2026-10-25
Write column as , where the row player's binary payoff is first. Suppose, for a contradiction, there is no pure Nash equilibrium.
The column player's maximum payoff in the top row must be one. Otherwise every column would be its best response there. To avoid a top-row equilibrium, every column would then need . But a column maximizing would immediately give a bottom-row equilibrium. The same reasoning with rows exchanged shows that the maximum bottom-row column payoff is also one.
Choose a column with . To avoid a top-row equilibrium, it must have . It cannot also have , because its bottom cell would then be an equilibrium. Hence this column is , the specified second column type. Exchanging rows forces a column , the specified first type.
Thus absence of a pure equilibrium forces both forbidden column types to occur. If the given game omits them, this is a contradiction, proving existence of a pure Nash equilibrium. The argument actually proves the stronger statement that omitting either one of the two types suffices.
Past exam of the computer science course of the University of Oxford 2019 Computational game theory 2 d Solution by
Codex 0 2026-10-25
A pure action is weakly dominated by a mixture when the mixture's expected payoff is at least as high against every opposing pure strategy profile, and strictly higher against at least one. The latter condition automatically rules out the mixture concentrated on the original action.
Yes: the pure-domination conclusion remains true for this weak version. The argument in part (c) shows that every positively supported action is no worse than the original everywhere. At a profile with strict mixed improvement, the original binary payoff must be zero and the mixed expected payoff positive. Some positively supported action therefore pays one there. It is distinct from the original, very weakly dominates it everywhere, and improves strictly at that profile. Thus it weakly dominates the original pure action. Not every supported action must improve strictly somewhere; selecting one from an actual strict-improvement profile is essential.
Past exam of the computer science course of the University of Oxford 2019 Computational game theory 2 c Solution by
Codex 0 2026-10-25
As literally stated, the claim is false. Give player one two pure actions, with payoffs one and zero against every opposing action. A mixed strategy assigning probability one to the first action has exactly that action's payoffs, so very weakly dominates it under the printed non-strict inequality. The other pure action nevertheless fails to dominate it.
The intended statement becomes true if the mixture gives positive probability to some distinct action, equivalently . Fix any opposing pure strategy profile at which pays one. Since all payoffs are in ,Equality forces every positive-probability supported action to pay one there. At a profile where pays zero, every other action already pays at least zero. Therefore every action in the support of a mixed strategy is no worse than against every opposing profile. Choosing a distinct supported action proves the corrected conclusion: nontrivial mixed very weak dominance implies very weak domination by a distinct pure action. This proof does not insert the missing support condition silently.
Pinned article: Introduction to the OurBigBook Project
Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
Intro to OurBigBook
. Source. We have two killer features:
- topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculusArticles of different users are sorted by upvote within each article page. This feature is a bit like:
- a Wikipedia where each user can have their own version of each article
- a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.Figure 1. Screenshot of the "Derivative" topic page. View it live at: ourbigbook.com/go/topic/derivativeVideo 2. OurBigBook Web topics demo. Source. - local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
Figure 2. You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website.Figure 3. Visual Studio Code extension installation.Figure 5. . You can also edit articles on the Web editor without installing anything locally. Video 3. Edit locally and publish demo. Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension. - Infinitely deep tables of contents:
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact





