Incentive Compatibility and the Bargaining Problem By Roger B. Myerson

Incentive Compatibility and the Bargaining Problem

• By Roger B. Myerson

• Presented by Anshi Liang

• lasnake@eecs

Outline of this presentation

• Introduction

• Bayesian Incentive-Compatibility

• Response-Plan Equilibria

• Incentive-Efficiency

• The Bargaining Solution

• Example

Outline of this presentation

• Introduction

• Bayesian Incentive-Compatibility

• Response-Plan Equilibria

• Incentive-Efficiency

• The Bargaining Solution

• Example

Introduction

• Consider the problem of an arbitrator trying to select a collective choice for a group of individuals when he does not have complete information about their preferences and endowments.

• The goal of this paper is to develop a unique solution to this arbitrator’s problem, based on the concept of incentive-compatibility and bargaining solution.

Introduction

• Describe by a Bayesian collective choice problem:

• (C, A1, A2, …, An, U1, U2, …, Un, P)

• C is the set of choices or strategies available to the group;

• Ai is the set of possible types for player i;

• Ui is the utility function for player i such that Ui(c, a1, a2, …, an) is the payoff which player i would get if cЄC were chosen and if (a1, a2, …, an) were the true vector of player types;

• P is the probability distribution such that P(a1, a2, …, an) is the probability that (a1, a2, …, an) is the true vector of types for all players.

Introduction

• Assumptions:

• a. C and all the Ai sets are nonempty finite sets;

• The response of each player is communicated to the arbitrator confidentially and noncooperatively;

• The arbitrator cannot compel a player to give the truthful response;

• The arbitration is binding.

Introduction

• Choice mechanism is a real-value function π with a domain of the form CX(S1XS2X…XSn)—for some collection of response sets S1, S2,…, Sn—such that

• ∑c,ЄCπ(c’|s1,…,sn)=1, and π(c|s1,…,sn) for all c,for every (s1,…,sn) in S1XS2X…XSn.

• Ai is the standard response set.

Outline of this presentation

• Introduction

• Bayesian Incentive-Compatibility

• Response-Plan Equilibria

• Incentive-Efficiency

• The Bargaining Solution

• Example

Bayesian Incentive-Compatibility

• With a choice mechanism π, we have Zi(π, bi|ai) represents the conditionally-expected utility payoff for player i, here ai is his true type, bi is the type he claims.

• A choice mechanism is Bayesian incentive-compatible if

• Zi(π, ai|ai)≥ Zi(π, bi|ai) for all i, aiЄAi, biЄAi

Bayesian Incentive-Compatibility

• Define Vi(π|ai)=Zi(π, ai|ai) if choice mechanism π is used and if everyone is honest.

• Define V(π)=((Vi(π|ai))a1ЄA1,…,(Vn(π|an)) anЄAn).

• The feasible set of expected allocation vectors:

• F={V(π): π is a choice mechanism}

• The incentive-feasible set of expected allocation vectors:

• F*={V(π): π is a Bayesian incentive-compatible}

Bayesian Incentive-Compatibility

• Theorem 1: F* is a nonempty convex and compact subset of F (proof in the paper).

• If Vi(π|ai)for all i and aiЄAi, we say that π is strictly dominated by π’.

Outline of this presentation

• Introduction

• Bayesian Incentive-Compatibility

• Response-Plan Equilibria

• Incentive-Efficiency

• The Bargaining Solution

• Example

Response-Plan Equilibria

• A response plan for player i is a function σi mapping each type aiЄAi onto a probability distribution over his response set Si. σi(si|ai) is the probability that player i will tell the arbitrator si if his true type is ai

• So we have Wi(π, σ1, …, σn|ai) to represent the player i’s expected utility payoff; similarly to before, we have a vector of conditionally-expected payoffs:

• W(π, σ1, …, σn)=(((Wi(π, σ1, …, σn|ai))aiЄAi)ni=1)

Response-Plan Equilibria

• (σ1, …, σn) is a response-plan equilibrium for the choice mechanism π if, for any player i and type aiЄAi, for every possible alternative response plan σ’i for player i:

• Wi(π, σ1, …, σn|ai)≥ Wi(π, σ1, …, σi-1, σ’i, σi+1,…,σn|ai)

• The equilibrium-feasible set of expected allocation vectors:

• F**={W(π, σ1, …, σn): π is a choice mechanism, and (σ1, …, σn) is a response-plan equilibrium for π}

• Theorem 2: F**=F* (proof in the paper)

Outline of this presentation

• Introduction

• Bayesian Incentive-Compatibility

• Response-Plan Equilibria

• Incentive-Efficiency

• The Bargaining Solution

• Example

Incentive-Efficiency

• π is incentive-efficient if and only if it is a Bayesian incentive-compatible choice mechanism and is not strictly dominated by any other Bayesian incentive-compatible mechanism (remind: If Vi(π|ai)for all i and aiЄAi, we say that π is strictly dominated by π’).

Outline of this presentation

• Introduction

• Bayesian Incentive-Compatibility

• Response-Plan Equilibria

• Incentive-Efficiency

• The Bargaining Solution

• Example

The Bargaining Solution

• Conflict outcome: it represents what would happen by default if the arbitrator failed to lead the players to an agreement. Examples:

• Market

• Politics

• Students

• Conflict payoff vector:

• t=((ta1)a1ЄA1, (ta2)a2ЄA2,…,(tan)anЄAn), where each tai is player i’s conditional expectation, given that ai is his true type, of what his utility payoff would be if the conflict outcome occurred.

The Bargaining Solution

• Given the conflict payoff vector t our collective choice problem becomes a bargaining problem, with a feasible set F*, t is a reference point in F*.

• Let F*+ be the set of all incentive-feasible payoff vectors which are individually rational:

• F*+=F*∩{y:yai≥tai for all i and all aiЄAi}

• Theorem 3: Suppose that c* is not incentive-efficient, then there exist a unique incentive-feasible bargaining solution.

Outline of this presentation

• Introduction

• Bayesian Incentive-Compatibility

• Response-Plan Equilibria

• Incentive-Efficiency

• The Bargaining Solution

• Example

Example

• Two players share the cost of a project which benefit them both.

• The project cost $100, the two players call an arbitrator to divide it.

• Project value:

• Player1: $90 if he is type1.0, $30 if he is type1.1

• Player2: $90

• 4. To the arbitrator and player2, P1(1.0)=.9 and P2(1.1)=.1

Example

• Some observation points:

• No matter what player 1’s type is, the project appears to be worth more than it costs;

• The decisions cannot be made separately.

• Some intuitive solutions:

• 50-50 or 20-80

• 47-53

• 50-50 or 0-0

Example

• Formal solution:

• Let C={c0, c1, c2}, A1={1.0, 1.1}, A2={2}. We have P(1.0, 2)=.9 and P(1.1, 2) =.1.

• c0 means “do not undertake the project”; c1 means “undertake the project and make player1 pay for it”; c2 means “undertake the project and make player2 pay for it”.

Example

• Strategies can be randomized.

• Use the abbreviations π0j=π(cj|1.0, 2) and π1j=π(cj|1.1, 2).

• The incentive-compatible choice mechanisms satisfies the following:

• -10π01+90π02≥-10π11+90π12,

• -70π11+30π12≥-10π01+90π02,

• π00+π01+π02=1, π10+π11+π12=1

• ,

Example

• Expected benefits for all players:

• x1.0=0π00-10π01+π02,

• x1.1=0π10-10π11+π12,

• x2=.9(0π00+90π01-10π02)+.1(0π10+90π11-10π12),

• Then the incentive-feasible bargaining solution is the solution that maximize

• ((x1.0).9(x1.1).1x2), x and π satisfy the restrictions above.

Example

• Result:

• x1.0=39.5, x1.1=13.2, x2=36

• π01=.505, π02=.495, π10=.561 and π12=.439

• Meanings in English

Conclusion

• A great paper overall

• The mathematical derivation is complicated but very clear

• This concept can be possibly extended to our networking study. For example, say that the arbitrator is the network designer; the two players are network users, etc.

Thank you very much!

• Anshi Liang