The pivotal mechanism of game theory

A few days ago, I accidentally found the electronic version of the book "Game Theory" and just read the first two chapters, which I found very interesting. I especially like the process of formalizing and solving problems. The second chapter mainly discusses the methods used in decision-making, such as the second-price auction: the highest bidder wins the auction but only needs to pay the second highest price, and the pivotal mechanism discussed below translates pivotal as "关键" (~~feels a bit strange~~).

This is my first encounter with game theory, so please point out any inaccuracies. 🥺

Concepts#

Opinion polls are an important tool for organizations to make project decisions, but the reported preferences of participants do not always reflect the true situation. This is because respondents may amplify or diminish their true preferences for various reasons such as price, taxes, and preferences.

For example, if a community wants to raise money to build a soccer field, participant A, who loves soccer, may exaggerate the price they are willing to pay during the survey because they believe that the higher price will be shared among other participants. On the other hand, participant B, who does not like soccer, may report a lower price than their true preference, taking into account the cost of building the soccer field and their own benefits. Everybody lies.

The pivotal mechanism / Clarke mechanism provides a game model that incentivizes respondents to report their true preferences.

The idea of the pivotal mechanism is to make each participant believe that they are the key to determining the outcome, thereby inducing participants to report truthful information for decision-making. The basic process is as follows:

Each participant reports their private information (such as the price they are willing to pay).
Calculate the sum of all information to obtain a decision result.
For each participant, consider whether the decision result would change if their information is excluded.
Only charge participants who have changed the result (e.g., additional taxes).

Example#

Imagine a scenario where the government is considering building a park in a community, and it is estimated to cost $\$C$ . There are a total of $n$ citizens in the community. If the decision is made to build the park, each citizen needs to contribute $\$c_i (c_1+c_2+...+c_n = C)$ . Since the benefits of the park vary for each citizen (e.g., distance from their homes), each citizen's actual contribution will be different.

Assuming each citizen $i$ has an initial wealth of $\$m_i (m_i>0)$ , and if the park is built, they can receive a benefit of $v_i$ (here, the benefit is quantified as wealth, note that the benefit can be negative), then the utility function for citizen $i$ is as follows (this formula is only used in subsequent mathematical proofs):

When making decisions, the government will only decide to build the park if the total benefits exceed the total costs, i.e., $\sum_{i=1}^{n}v_i > C$ . However, the government cannot know the value of $v_i$ for each citizen, so a survey is needed.

Using the pivotal mechanism for opinion polls#

Step 1: Each surveyed citizen reports a benefit $w_i$ they would receive from the park construction process. In an ideal situation of absolute honesty, $w_i$ should be equal to $v_i$ .
Step 2: Calculate the sum of all reported benefits. The decision made through the survey becomes to build the park only if $\sum_{i=1}^{n}w_i > C$ .
Step 3: Divide the participants into pivotal and non-pivotal categories based on the following conditions (removing the reported benefit $w_j$ of a non-pivotal participant does not change the overall decision):

The first row indicates that the sum of benefits for all people, including and excluding $i$ , is greater than the required total cost, so the decision remains unchanged (building the park).
The second row indicates that the sum of benefits for all people, including and excluding $i$ , is less than the required total cost, so the decision remains unchanged (not building the park).

Step 4: Impose a certain tax on pivotal citizens (non-non-pivotal citizens), the amount of which is:

Intuitive Analysis#

Since pivotal citizens have to pay additional taxes, each citizen's relatively rational choice is to make their $w_i = c_i$ so that they are never pivotal:

If the original total $W \ge C$ , adding $c_i$ to both sides still maintains the inequality $W+w_i \ge C+c_i$ .
If the original total $W < C$ , adding $c_i$ to both sides still maintains the inequality $W+w_i < C+c_i$ .

In an environment of absolute honesty and rationality, all participants should have $w_i = v_i$ so that the government can compare $\sum_{i=1}^{n}w_i = \sum_{i=1}^{n}v_i$ with $C$ to make the most accurate decision.

Mathematical Proof#

The mathematical proof mainly calculates the utility function for each participant to prove that $w_i = c_i$ is indeed the optimal choice for each participant (each $i$ wants to maximize their final wealth). This is also referred to as "our hypothesis" in the proof below.

$w_i$ represents the reported benefit (quantified as wealth).
$v_i$ represents the true benefit (quantified as wealth).
$c_i$ represents the true cost under the condition of building the park, and it is $0$ if not built.
$\bar{m}_i$ represents the initial wealth of participant $i$ .
$i's utility$ represents the final wealth of participant $i$ , and $i$ will make decisions to maximize this value.

且听风吟