且听风吟

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

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

Concepts#

Surveys are an important tool for organizations to make project decisions, but the willingness reported by participants does not always reflect the true situation. This is because respondents may exaggerate or downplay their true willingness 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 A believes that the higher price will be shared among other participants when it comes to the actual bidding. Conversely, participant B, who does not like soccer, will report a willingness that is lower than their true willingness, considering the costs 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 willingness.

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

1. Each participant reports their private information (such as the price they are willing to pay).
2. Calculate the total of all reported information to obtain a decision result.
3. For each participant, consider whether the decision result changes if their information is excluded.
4. Only charge participants whose exclusion changes the result (for example, an additional tax).

Example#

Imagine a scenario where the government is considering building a park in a community, which is expected to cost a total of $\$C$, and there are $n$ citizens in the community. If the decision is made to build the park, each citizen will need to contribute $\$c_i (c_1+c_2+...+c_n = C)$ since the benefits of the park differ for each citizen (for example, the distance from each person's home varies), the actual contribution of each citizen will differ.

Assuming each citizen $i$ has an initial wealth of $\$m_i(m_i>0)$ and the benefit they can gain from the park is $v_i$ (here, benefits are quantified as wealth, noting that benefits can be negative), the benefit function for citizen $i$ is (this formula is only used in subsequent mathematical proofs)

When making decisions, the government will only decide to build the park if the total benefit exceeds the total cost, i.e., $\sum_{i=1}^{n}v_i > C$ . However, the problem is that the government cannot know each citizen's $v_i$, so a survey is needed.

Using the Pivotal Mechanism for Surveys#

1. The first step is for each surveyed citizen to report a benefit $w_i$ they expect to gain from the park's construction. In an absolutely honest scenario, $w_i$ should equal $v_i$.

2. The second step is to calculate the total of all reported benefits. The decision made through the survey will then only lead to the construction of the park if $\sum_{i=1}^{n}w_i > C$.

3. The third step is to categorize participants into pivotal and non-pivotal groups. Those who meet the following condition are considered non-pivotal (excluding this participant's $w_j$ does not change the overall decision).

The first line indicates that the total benefit including $i$ and excluding $i$ is greater than the total required expenditure, so the decision remains unchanged (build the park). The second line indicates that the total benefit including $i$ and excluding $i$ is less than the total required expenditure, so the decision remains unchanged (do not build the park).

4. The fourth step is to levy a certain tax on pivotal citizens (non-non-pivotal citizens), with the amount being

Sensory Analysis#

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

• If the original total $W \ge C$, then adding $c_i$ still maintains the greater relationship $W+w_i \ge C+c_i$.
• If the original total $W < C$, then adding $c_i$ still maintains the lesser relationship $W+w_i < C+c_i$.

In an absolutely honest and rational environment, all participants should have $w_i = v_i$, so the government can compare the statistically obtained $\sum_{i=1}^{n}w_i = \sum_{i=1}^{n}v_i$ with $C$ to arrive at the most accurate decision.

Mathematical Proof#

The mathematical proof mainly demonstrates that $w_i = c_i$ is indeed the optimal choice for each participant (each $i$ wants their final wealth to be maximized) by calculating each participant's benefit function. 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 expenditure in the case of building the park; if not built, this is $0$.
• $\bar{m}_i$ represents the initial wealth of participant $i$.
• $i's utility$ represents $i$'s final wealth, and $i$ will make decisions based on maximizing this value.

Case 1#

Case 2#

Case 3#

Case 4#