Examples of VCG Mechanism and The Clarke Pivot Rule – Mini Post 3

Abstract: In this post we look at the Clarke Pivot Rule, and how it applies and then two examples of how this mechanism can be used. As mentioned in the previous post we use a function which we call . Because this function depends only on the other valuations of the bidders, we can changeContinue reading “Examples of VCG Mechanism and The Clarke Pivot Rule – Mini Post 3”

Vickrey–Clarke–Groves auction/mechanism – Mini Post 2

Abstract: In this post, we look at the Vickery-Clarke-Groves auction and discuss its implications. We also look at the generalized VCG-mechanism. In our last post, we looked at how one would run a sealed bid auction with one item if one would want to maximize social utility. However what if we have more than oneContinue reading “Vickrey–Clarke–Groves auction/mechanism – Mini Post 2”

The Vickrey Auction – Mini Post 1

Abstract: In this mini-blog post, we look at the Vickrey auction and its properties, using mathematical analysis. For the sake of connecting this to tabletop games, let us assume that, for one reason or another, you came into the extremely rare first edition printing of Cosmic Encounter, pictured to the right. And, being the good-naturedContinue reading “The Vickrey Auction – Mini Post 1”

Strategic Considerations for the Gale-Shapley algorithm Part 1

Abstract: In post we look at the Gale-Shapley algorithm from a strategic prospective. We start by introducing the algorithm and give an proof for that individual men can not misrepresent there intent to end up with a more desirable outcome. Then, we look at two ways to “game” the algorithm, one in which a groupContinue reading “Strategic Considerations for the Gale-Shapley algorithm Part 1”

Impartial Games and How to Solve Them Part 3

Abstract: In this short post we apply the techniques learned in the previous two posts on impartial games and present solutions for a a few variations on the previously discussed subtraction games, mainly the addition of a take and break mechanic. We also present the more complicated impartial game, Kayles and its solution. In theContinue reading “Impartial Games and How to Solve Them Part 3”

Impartial Games and how to Solve Them Part 2

Abstract: In this post we introduce two more fundamental ideas to to the study of impartial games. The Sprague-Grundy function, and the Sprague-Grundy Theorem. With these new tools, we are able begin to solve more complicated impartial games, specifically games that are the disjoint sum of other games. Finally, we introduce the game of NimContinue reading “Impartial Games and how to Solve Them Part 2”

Impartial Games and How to Solve Them

Abstract: In this post, we introduce the concept of impartial games and give a few examples. Following that discussion, we look at the process of solving an impartial game with a relatively simply example. During this example, we introduce critical concepts to impartial game theory, those being P and N Positions In a previous post,Continue reading “Impartial Games and How to Solve Them”

Propositional Logic and Social Deduction Games

Abstract: In this post, we introduce how propositional logic can be used in social deduction games. In the first part of this post, a brief overview of propositional logic is given, along with some more advanced ideas that are useful. In the second part an overview of The Resistance is given, followed by how propositionalContinue reading “Propositional Logic and Social Deduction Games”

Proving The NP-Completeness of The Crew: The Quest for Planet Nine

Abstract: In this post I prove the NP-Completeness of The Crew: The Quest for Planet Nine. First we define the unbounded version of the problem statement along with what a brief review on NP as a complexity group. Next, I show a reduction from the Hamilton Path Problem. Finally, a proof is given on theContinue reading “Proving The NP-Completeness of The Crew: The Quest for Planet Nine”

Ticket to Ride the Traveling Salesperson Problem.

Abstract: In this post, we look at how to find the shortest path through a subset of nodes. We reduce the problem to the Traveling Salesperson Problem, and show how our solution is optimal. There is also a discussion on what NP-hard problems are, and why finding a solution to our problem is hard. TicketContinue reading “Ticket to Ride the Traveling Salesperson Problem.”