Outline of the Talk

(1)

Mechanism Design with Monetary Transfers

Swaprava Nath

Economics and Planning Unit Indian Statistical Institute, New Delhi

Workshop on Static and Dynamic Mechanism Design Indian Statistical Institute, New Delhi

(2)

Outline of the Talk

1 The Setup

Unrestricted Preferences Restricted Preferences

2 Mechanisms in Quasi-linear Domain Structure of a Mechanism Some Definitions

3 Results

Groves Class of Mechanisms

What Other Mechanisms are Incentive Compatible Revenue Equivalence

Uniqueness of Groves for Efficiency Budget Balance

Bayesian Incentive Compatibility

4 Summary

(3)

Outline of the Talk

1 The Setup

3 Results

(4)

Outline of the Talk

1 The Setup

3 Results

4 Summary

(5)

The Gibbard-Satterthwaite Setting

Voters can have arbitrarystrict ordinalpreferences over the set of alternatives Set of alternativesX ={a, b, c, d}

Voter 1 Voter 2 Voter 3 Voter 4

a d c d

b b b b

c a a c

d c d a

(6)

The Gibbard-Satterthwaite Setting

Goal: elicit the preferences truthfully from the agents Voter 1 Voter 2 Voter 3 Voter 4

a d c d

b b b b

c a a c

d c d a

(7)

The Gibbard-Satterthwaite Setting

Goal: elicit the preferences truthfully from the agents Voter 1 Voter 2 Voter 3 Voter 4

a d c d

b b b b

c a a c

d c d a

Theorem (Gibbard (1973), Satterthwaite (1975))

If|X| ≥3, an ontosocial choice functionis strategyproof if and only if it is

(8)

Outline of the Talk

1 The Setup

3 Results

4 Summary

(9)

Quasi-linear Preferences

An alternativex∈X is a tuple (a, p)

Allocationabelongs to the set of allocationsA

(10)

Quasi-linear Preferences

Allocationabelongs to the set of allocationsA Paymentspbelong toRⁿ

(11)

Quasi-linear Preferences

Each agentihas a valuation functionvi:A→Rbelonging to the setVi

(12)

Quasi-linear Preferences

Each agentihas a valuation functionvi:A→Rbelonging to the setVi

Agents’ utilities are given by

ui(x) =ui(a, p) =vi(a)−pi

(13)

Example: Public Good

Alternatives→

Alice 10 80

Bob 100 30

Carol 40 50

Photo courtesy: wikimedia.org and nimsuniversity.org

(14)

Example: Public Good

Alternatives→

Alice 10 80

Bob 100 30

Carol 40 50

Valuations: vA(F) = 10, vA(L) = 80

Social planner takes the decision of buildingForL Cantax people differently depending on their preferences

Quasi-linear preferences

(15)

Example: Resource Allocation

Commodities

→

Alice 0.2 0.8 0.5

Bob 0.3 0.1 0.2

Carol 0.5 0.1 0.3

Photo courtesy: individual organizations

(16)

Example: Resource Allocation

Commodities

→

Alice 0.2 0.8 0.5

Bob 0.3 0.1 0.2

Carol 0.5 0.1 0.3

Set of allocationsA={x∈[0,1]^n×m:Pm

j=1xi,j= 1}

Items are divisible among the agents

Agents’ valuations reflect their preferences over different allocations They are charged monetary transfers for every allocation

Quasi-linear preferences

(17)

Example: Resource Allocation

Commodities

→

Alice 0.2 0.8 0.5

Bob 0.3 0.1 0.2

Carol 0.5 0.1 0.3

Selfish valuations

(18)

Why Quasi-linearity avoids GS Impossibility

GS theorem is valid for unrestricted preferences

In quasi-linear domain, agents’ preferences are restricted

(19)

Why Quasi-linearity avoids GS Impossibility

In quasi-linear domain, agents’ preferences are restricted Example:

◮ Set of alternativesX=A×Rⁿconsists of(a, p)pairs

◮ Allocationa∈Aand payment vectorp∈Rⁿ

(20)

Why Quasi-linearity avoids GS Impossibility

◮ Consider two alternativesx₁= (a, p₁)andx₂= (a, p₂), wherep₁< p₂

(21)

Why Quasi-linearity avoids GS Impossibility

◮ For all agents,x₁≻x₂ for any valuation profile

(22)

Why Quasi-linearity avoids GS Impossibility

◮ For all agents,x₁≻x₂ for any valuation profile

◮ There is no preference profile wherex₂≻x₁

(23)

An Example of a Truthful Mechanism

Alice 10 80 40

Bob 100 20 50

Carol 0 40 30

(24)

An Example of a Truthful Mechanism

Alice 10 80 40

Bob 100 20 50

Carol 0 40 30

Consider the mechanism:

◮ pick the alternativea^∗that maximizes the sum of the valuations (with arbitrary tie-breaking rule)

◮ pay every agentian amountP

j6=ivj(a^∗)

(25)

An Example of a Truthful Mechanism

Alice 10 80 40

Bob 100 20 50

Carol 0 40 30

Consider the mechanism:

◮ pick the alternativea^∗that maximizes the sum of the valuations (with arbitrary tie-breaking rule)

pay every agentian amountP

v (a^∗)

(26)

Outline of the Talk

1 The Setup

3 Results

4 Summary

(27)

Outline of the Talk

1 The Setup

3 Results

(28)

Structure of a Mechanism

Set of agentsN ={1, . . . , n}

Set of allocationsA, finite (for this tutorial)

Valuation of agenti,vi:A→R, the set of valuations is denoted byVi

(29)

Structure of a Mechanism

A mechanism in quasi-linear (QL) domain is a pair of functions:

◮ allocation function,a:Q

jVj→A

◮ payment function,pi:Q

jVj→R, for alli∈N Agenti’s payoff is given by:

vi(a(v))−pi(v)

(30)

Structure of a Mechanism

A mechanism in quasi-linear (QL) domain is a pair of functions:

◮ allocation function,a:Q

jVj→A

◮ payment function,pi:Q

jVj→R, for alli∈N Agenti’s payoff is given by:

vi(a(v))−pi(v)

Onlydirect revelation mechanisms(DRM)(this talk)

(31)

Outline of the Talk

1 The Setup

3 Results

(32)

Social Choice Function

Definition (Social Choice Function)

Asocial choice function(SCF)f is a mapping from the set of valuation profiles to the set of allocations, i.e.,f :V →A, whereV =Q

jVj.

Note that the outcome is only the allocations

(33)

Social Choice Function

Definition (Social Choice Function)

Asocial choice function(SCF)f is a mapping from the set of valuation profiles to the set of allocations, i.e.,f :V →A, whereV =Q

jVj.

Note that the outcome is only the allocations In QL domain:

A mechanismM = (a, p)implementsa SCFf if:

◮ a(v) =f(v),∀v∈V and,

◮ for every agenti∈N, reportingvi truthfully is anequilibrium

Even though the SCF is concerned with only allocations, payments can also be characterized byrevenue equivalence (defined later)

(34)

Incentive Compatibility

Definition (Dominant Strategy Incentive Compatibility (DSIC))

A mechanism(f, p1, . . . , pn)is dominant strategy incentive compatibleif for all i∈N and for allv−i∈V−i :=Q

j6=iVj,

vi(f(vi, v−i))−pi(vi, v−i)≥vi(f(v^′_i, v−i))−pi(v_i^′, v−i), ∀vi, v_i^′∈Vi. In this case, paymentspi, i∈N implementf in dominant strategies

(35)

Incentive Compatibility (Contd.)

In a Bayesian game, the valuationsv are generated through a priorP Each agentiknows her own realized valuationvi andP

Her belief on the valuations of other agentsv−i is given byP(v−i|vi)derived by Baye’s rule

(36)

Incentive Compatibility (Contd.)

In a Bayesian game, the valuationsv are generated through a priorP Each agentiknows her own realized valuationvi andP

Her belief on the valuations of other agentsv−i is given byP(v−i|vi)derived by Baye’s rule

Definition (Bayesian Incentive Compatibility (BIC))

A mechanism(f, p1, . . . , pn)is Bayesian incentive compatiblefor a priorP if for alli∈N,

E_v

−i|vi[vi(f(vi, v−i))−pi(vi, v−i)]≥E_v

−i|vi[vi(f(v_i^′, v−i))−pi(v^′_i, v−i)]

∀vi, v_i^′ ∈Vi.

In this case, paymentspi, i∈N implementf in a Bayesian Nash equilibrium

(37)

Observations on IC

A DSIC mechanism is always BIC

(38)

Observations on IC

For a DSIC mechanism(f, p1, . . . , pn), let valuations of agents other thaniis fixed atv−i

Ifvi, v^′_i be such thatf(vi, v−i) =f(v^′_i, v−i), thenpi(vi, v−i) =pi(v_i^′, v−i)

(39)

Observations on IC

For a DSIC mechanism(f, p1, . . . , pn), let valuations of agents other thaniis fixed atv−i

Ifvi, v^′_i be such thatf(vi, v−i) =f(v^′_i, v−i), thenpi(vi, v−i) =pi(v_i^′, v−i) Consider another paymentqi(vi, v−i) =pi(vi, v−i) +hi(v−i),

vi(f(vi, v−i))−qi(vi, v−i)≥vi(f(v_i^′, v−i))−qi(v_i^′, v−i), ∀vi, v_i^′∈Vi.

(40)

Efficiency

Definition (Efficiency)

An SCFf isefficientif for allv∈V, f(v)∈argmax

a∈A

X

i∈N

vi(a).

An efficient SCF ensures that the ‘social welfare’ is maximized

(41)

Revenue Equivalence

This property characterizes the payment functions

Definition (Revenue Equivalence)

An SCFf satisfiesrevenue equivalenceif for any two payment rulespandp^′ that implementf, there exist functionsαi:V−i→R, such that,

pi(vi, v−i) =p^′_i(vi, v−i) +αi(v−i), ∀vi∈Vi,∀v−i∈V−i,∀i∈N.

(42)

Revenue Equivalence

This property characterizes the payment functions

Definition (Revenue Equivalence)

An SCFf satisfiesrevenue equivalenceif for any two payment rulespandp^′ that implementf, there exist functionsαi:V−i→R, such that,

pi(vi, v−i) =p^′_i(vi, v−i) +αi(v−i), ∀vi∈Vi,∀v−i∈V−i,∀i∈N.

Saw an example of a payment of agentibeing different by a factor not dependent oni’s valuation

This property says more: pickanytwo payments that implementf - they must be different by a similar factor

(43)

Budget Balance

Definition (Budget Balance)

A set of paymentspi:V →R, i∈N is budget balanced if, X

i∈N

pi(v) = 0,∀v∈V.

This property ensures that the mechanism does not produce any monetary surplus

Hard to satisfy with incentive compatibility

(44)

Outline of the Talk

1 The Setup

3 Results

4 Summary

(45)

Outline of the Talk

1 The Setup

3 Results

(46)

Single Indivisible Item Auction

Buyer 1 Buyer 2

Metropolitan Museum of Arts Louvre

(47)

Second Price Auction

(48)

Groves Class of Mechanisms

Allocation rule is efficient:

a^∗(v)∈argmax

a∈A

X

i∈N

vi(a)

Payment rule is given by:

p^∗_i(vi, v−i) =hi(v−i)− X

j∈N\{i}

vj(a^∗(v)),

wherehi:V−i→Ris any arbitrary function that does not depend onvi

(49)

Groves Class of Mechanisms

Allocation rule is efficient:

a^∗(v)∈argmax

a∈A

X

i∈N

vi(a)

Payment rule is given by:

p^∗_i(vi, v−i) =hi(v−i)− X

j∈N\{i}

vj(a^∗(v)),

wherehi:V−i→Ris any arbitrary function that does not depend onvi

Claim

Groves class of mechanisms are DSIC

(50)

Incentive Compatibility of Groves

Utility of agenti according to Groves class of mechanisms:

u^(a_i ^∗^,p^∗⁾(vi, v−i)

=vi(a^∗(vi, v−i))−p^∗_i(vi, v−i)

(51)

Incentive Compatibility of Groves

u^(a_i ^∗^,p^∗⁾(vi, v−i)

=vi(a^∗(vi, v−i))−hi(v−i) + X

j∈N\{i}

vj(a^∗(vi, v−i))

(52)

Incentive Compatibility of Groves

u^(a_i ^∗^,p^∗⁾(vi, v−i)

j∈N\{i}

=X

j∈N

vj(a^∗(vi, v−i))−hi(v−i)

(53)

Incentive Compatibility of Groves

u^(a_i ^∗^,p^∗⁾(vi, v−i)

j∈N\{i}

=X

j∈N

≥X

j∈N

vj(a^∗(v_i^′, v−i))−hi(v−i)(by definition ofa^∗)

(54)

Incentive Compatibility of Groves

u^(a_i ^∗^,p^∗⁾(vi, v−i)

j∈N\{i}

=X

j∈N

≥X

j∈N

=vi(a^∗(v_i^′, v−i))−hi(v−i) + X

j∈N\{i}

vj(a^∗(v^′_i, v−i))

(55)

Incentive Compatibility of Groves

u^(a_i ^∗^,p^∗⁾(vi, v−i)

j∈N\{i}

=X

j∈N

≥X

j∈N

=vi(a^∗(v_i^′, v−i))−hi(v−i) + X

j∈N\{i}

vj(a^∗(v^′_i, v−i))

=vi(a^∗(v^′, v−i))−p^∗(v^′, v−i)

(56)

Incentive Compatibility of Groves

u^(a_i ^∗^,p^∗⁾(vi, v−i)

j∈N\{i}

=X

j∈N

≥X

j∈N

=vi(a^∗(v_i^′, v−i))−hi(v−i) + X

j∈N\{i}

vj(a^∗(v^′_i, v−i))

=vi(a^∗(v_i^′, v−i))−p^∗_i(v^′_i, v−i)

=u^(a^∗^,p^∗⁾(v^′, v )

(57)

Pivot Mechanism

A special case of Groves class when the payment is given by:

hi(v−i) = X

j∈N\{i}

vj(a^∗_−i(v−i)),

where the allocationa^∗_−i(v−i)is given by:

a^∗_−i(v−i)∈argmax

a∈A

X

j∈N\{i}

vj(a)

The allocationa^∗_−imaximizes the sum of valuations in the absence of agenti The functionhi is the maximum value of this sum

The payment is therefore:

(58)

Interpretations of the Pivot Mechanism

pi(vi, v−i) = max

a∈A

X

j∈N\{i}

vj(a)− X

j∈N\{i}

vj(a^∗(v)) Two Interpretations:

1. Externality:

◮ maxa∈AP

j∈N\{i}vj(a)is what the agentsN\ {i}can achieve

◮ P

j∈N\{i}vj(a^∗(v))is what they achieve under the efficient rule

◮ The mechanism asks agentito pay the difference

(59)

Interpretations of the Pivot Mechanism

pi(vi, v−i) = max

a∈A

X

j∈N\{i}

vj(a)− X

j∈N\{i}

vj(a^∗(v)) Two Interpretations:

1. Externality:

◮ maxa∈AP

j∈N\{i}vj(a)is what the agentsN\ {i}can achieve

◮ P

j∈N\{i}vj(a^∗(v))is what they achieve under the efficient rule

◮ The mechanism asks agentito pay the difference 2. Marginal contribution:

◮ Net utility of agentiin pivot mechanism:

ui(vi, v_−i) =X

j∈N

vj(a^∗(vi, v_−i))−max

a∈A

X

j∈N\{i}

vj(a)

i.e., the difference in sum valuation in presence of agentiand in her absence Net utility is agenti’s

(60)

What is Pivotal about it?

Alternatives→

Alice 10 70

Bob 100 10

Carol 10 50

(61)

What is Pivotal about it?

Alternatives→

Alice 10 70

Bob 100 10

Carol 10 50

Outcome: L

(62)

What is Pivotal about it?

Alternatives→

Alice 10 70

Bob 100 10

Carol 10 50

Outcome: L

Alice pays(100 + 10)−(10 + 50) = 50

(63)

What is Pivotal about it?

Alternatives→

Alice 10 70

Bob 100 10

Carol 10 50

Outcome: L

Alice pays(100 + 10)−(10 + 50) = 50

(64)

What is Pivotal about it?

Alternatives→

Alice 10 70

Bob 100 10

Carol 10 50

Outcome: L

Alice pays(100 + 10)−(10 + 50) = 50 Bob pays(70 + 50)−(70 + 50) = 0 Carol pays(10 + 100)−(70 + 10) = 30

(65)

What is Pivotal about it?

Alternatives→

Alice 10 70

Bob 100 10

Carol 10 50

Outcome: L

Alice pays(100 + 10)−(10 + 50) = 50 Bob pays(70 + 50)−(70 + 50) = 0

(66)

Outline of the Talk

1 The Setup

3 Results

4 Summary

(67)

Affine Maximizers

An important class of SCFs is that of affine maximizers

Definition (Affine Maximizer)

An SCFf :V →Ais anaffine maximizerif there existswi≥0, i∈N, not all zero, and a functionκ:A→Rsuch that,

f(v)∈argmax

a∈A

X

i∈N

wivi(a) +κ(a)

! .

(68)

Affine Maximizers

Definition (Affine Maximizer)

f(v)∈argmax

a∈A

X

i∈N

wivi(a) +κ(a)

! .

Special cases:

wi= 1,∀iandκ≡0: efficientSCF

(69)

Affine Maximizers

Definition (Affine Maximizer)

f(v)∈argmax

a∈A

X

i∈N

wivi(a) +κ(a)

! .

Special cases:

wi= 1,∀iandκ≡0: efficientSCF

wd= 1, for somed,wi= 0,∀i6=dandκ≡0: dictatorialSCF

(70)

Affine Maximizers (Contd.)

An affine maximizerf satisfiesindependence of irrelevant agents (IIA) if for everyiwithwi= 0and for every v−i∈V−i,

f(vi, v−i) =f(v_i^′, v−i),∀vi, v_i^′∈Vi

This is a consistency condition for tie-breaking

(71)

Affine Maximizers (Contd.)

This is a consistency condition for tie-breaking Every affine maximizer satisfying IIA is implementable

(72)

Affine Maximizers (Contd.)

This is a consistency condition for tie-breaking Every affine maximizer satisfying IIA is implementable

In particular, payments are of the following form: for alli∈N pi(vi, v−i) =

( 1 wi

P

j6=iwjvj(f(v)) +κ(f(v)) +hi(v−i)

, wi>0

0 wi= 0

f is an affine maximizer

(73)

Roberts’ Theorem

Theorem (Roberts 1979)

Let the allocation spaceAbe finite with|A| ≥3. If the space of valuationsV is unrestricted, then an onto and dominant strategy implementable SCFf :V →A is an affine maximizer.

(74)

Roberts’ Theorem

Theorem (Roberts 1979)

Understanding Roberts’ Theorem:

Groves’ or pivotal mechanisms are implementable, but this result is giving a necessary condition for implementability

(75)

Roberts’ Theorem

Theorem (Roberts 1979)

Moreover, it provides a functional form characterization of the DSIC mechanisms (as opposed to Myerson’s monotonicity characterization)

(76)

Roberts’ Theorem

Theorem (Roberts 1979)

Moreover, it provides a functional form characterization of the DSIC mechanisms (as opposed to Myerson’s monotonicity characterization) If payments are enforced to be zero for every valuation profilev, then the only implementable mechanism is dictatorial - GS theorem is a corollary of this result

(77)

Some Observations and Implications

If an SCFf is implementable in a valuation spaceV, it is implementable in every valuation spaceV^′⊆V - same payments implement them and the number of incentive compatibility constraints reduce

(78)

Some Observations and Implications

Efficient SCF is implementable in any valuation space

(79)

Some Observations and Implications

Unrestricted valuation space is crucial for Roberts’ theorem - some recent results show that the affine maximizer characterization is true even for certain restricted valuation spaces

(80)

Some Observations and Implications

Unrestricted valuation space is crucial for Roberts’ theorem - some recent results show that the affine maximizer characterization is true even for certain restricted valuation spaces

Characterization of implementability in restricted domains is an active research area

[A proof by pictures]

(81)

Outline of the Talk

1 The Setup

3 Results

(82)

Revenue Equivalence

Ifpandp^′ implementf in dominant strategies, then pi(v) =p^′_i(v) +αi(v−i),∀v∈V

(83)

Revenue Equivalence

Theorem (Rockafeller 1997; Krishna and Maenner (2001))

If the type space is convex and the valuations are linear in type, then an SCF, implementable in dominant strategies, satisfies revenue equivalence.

(84)

Revenue Equivalence

Theorem (Rockafeller 1997; Krishna and Maenner (2001))

If the type space is convex and the valuations are linear in type, then an SCF, implementable in dominant strategies, satisfies revenue equivalence.

Theorem (Chung and Olszewski (2007))

Suppose the type spaceT ⊆Rⁿ is a connected set,A is finite and the valuations are continuous in type. If an SCF is implementable in dominant strategies, then it satisfies revenue equivalence.

(85)

Outline of the Talk

1 The Setup

3 Results

(86)

Green-Laffont-Holmstr¨om Characterization

An efficient SCFf chooses an alternative in argmax_a∈AP

j∈Nvj(a)

(87)

Green-Laffont-Holmstr¨om Characterization

An efficient SCFf chooses an alternative in argmax_a∈AP

j∈Nvj(a)

Theorem (Green and Laffont (1979), Holmstr¨om (1979))

If the valuation space is convex and smoothly connected, every efficient and DSIC mechanism is a Groves mechanism.

Shows uniqueness of Groves class in the space of efficient, DSIC mechanisms

[A proof outline]

(88)

Outline of the Talk

1 The Setup

3 Results

4 Summary

(89)

Green-Laffont Impossibility

Theorem (Green and Laffont (1979))

No Groves mechanism isbudget balanced(BB), i.e.,

∄p^Groves_i s.t.P

i∈Np^Groves_i (v) = 0,∀v∈V.

This leads to the following corollary

Corollary

If the valuation space is convex and smoothly connected, noefficientmechanism can be both DSIC and BB.

(90)

Outline of the Talk

1 The Setup

3 Results

4 Summary

(91)

AGV Mechanism

If the equilibrium condition is relaxed to BIC, we have a positive result Payment is defined via a functionδi, i∈N:

δi(vi) =E_v

−i|vi



 X

j∈N\{i}

vj(a^∗(v))



,

wherea^∗ is an efficient allocation Payment is:

p^AGV_i (v) = X

j∈N\{i}

δj(vj)−δi(vi)

Theorem (d’Aspremont and Gerard-Varet (1979), Arrow (1979))

The AGV mechanism is BIC, efficient, and budget-balanced

(92)

Outline of the Talk

1 The Setup

3 Results

4 Summary

(93)

Summary

DSIC mechanisms

(94)

Summary

DSIC mechanisms U

Valuation / Type Space Mechanism Space

(95)

Summary

DSIC mechanisms U

Dict

(96)

Summary

DSIC mechanisms U

QL

Dict

(97)

Summary

DSIC mechanisms U

QL

AM

Dict

(98)

Summary

DSIC mechanisms U

QL +EFF

AM

Dict

(99)

Summary

DSIC mechanisms U

QL +EFF

AM

Dict Gr

(100)

Summary

DSIC mechanisms U

QL +EFF

AM

Dict Gr

Piv

(101)

Summary

DSIC mechanisms U

QL +EFF

+BB

AM

Dict Gr

Piv

(102)

Summary

DSIC mechanisms U

QL +EFF

+BB

∅

AM

Dict Gr

Piv

(103)

Thank you!

swaprava@gmail.com

http://www.isid.ac.in/∼swaprava

(104)

Value Difference Set

Q:What does affine maximizer mean?

(105)

Value Difference Set

A:Iff(v) =y then

w^⊤v(y) +κ(y)≥w^⊤v(z) +κ(z),∀z∈A\ {y}

⇒w^⊤(v(y)−v(z))≥κ(z)−κ(y),∀z∈A\ {y}

(106)

Value Difference Set

A:Iff(v) =y then

w^⊤v(y) +κ(y)≥w^⊤v(z) +κ(z),∀z∈A\ {y}

⇒w^⊤(v(y)−v(z))≥κ(z)−κ(y),∀z∈A\ {y}

w^⊤α≥β half-space

(107)

Value Difference Set

A:Iff(v) =y then

w^⊤v(y) +κ(y)≥w^⊤v(z) +κ(z),∀z∈A\ {y}

⇒w^⊤(v(y)−v(z))≥κ(z)−κ(y),∀z∈A\ {y}

Define thevalue difference setfor any pair of distinctalternativesy, z ∈A.

P(y, z) ={α∈Rⁿ:∃v∈V s.t. v(y)−v(z) =αandf(v) =y}.

(108)

Value Difference Set

A:Iff(v) =y then

w^⊤v(y) +κ(y)≥w^⊤v(z) +κ(z),∀z∈A\ {y}

⇒w^⊤(v(y)−v(z))≥κ(z)−κ(y),∀z∈A\ {y}

Define thevalue difference setfor any pair of distinctalternativesy, z ∈A.

P(y, z) ={α∈Rⁿ:∃v∈V s.t. v(y)−v(z) =αandf(v) =y}.

Claim

Ifα∈P(y, z), andδ >0∈Rⁿ, thenα+δ∈P(y, z), for all distincty, z∈A.

(109)

Graphical Illustration for Two Players

−4 −3 −2 −1 1 2 3 4 5 6 7

−2

−1 1 2 3 4 5 6

0

P(y, z), y, z∈A

v1(y)−v1(z) v2(y)−v2(z)

(110)

Complementary Structures of P (y, z) and P (z, y)

Claim

For everyα, ǫ∈Rⁿ, ǫ >0, and for ally, z∈A, (a) α−ǫ∈P(y, z) ⇒ −α /∈P(z, y).

(b) α /∈P(y, z) ⇒ −α∈P(z, y).

(111)

−6 −4 −2 2 4 6 8

6

−4

−2 2 4 6

0

P(y, z), y, z∈A

v1(y)−v1(z) v2(y)−v2(z)

P(z, y), y, z∈A

(112)

−6 −4 −2 2 4 6 8

−6

−4

−2 2 4 6

0

P(y, z), y, z∈A

v1(y)−v1(z) v2(y)−v2(z)

P(z, y), y, z∈A γ(y, z)

γ(z, y)

(113)

−6 −4 −2 2 4 6 8

6

−4

−2 2 4 6

0

P(y, z), y, z∈A

v1(y)−v1(z) v2(y)−v2(z)

P(z, y), y, z∈A γ(y, z)

γ(z, y) =−γ(y, z)

(114)

Independence of C ˚ from the Alternatives in A

Define the translated setC(y, z) =P(y, z)−γ(y, z)1 Denote the ‘interior’ ofC(y, z)byC(y, z)˚

(115)

Independence of C ˚ from the Alternatives in A

Claim

C(y, z˚ ) = ˚C(w, l), for anyy, z, w, l∈A,y6=z andw6=l.

(116)

Independence of C ˚ from the Alternatives in A

Claim

C(y, z˚ ) = ˚C(w, l), for anyy, z, w, l∈A,y6=z andw6=l.

Remark: Note that this result, in particular, includes the cases,

C(y, z˚ ) = ˚C(l, z) = ˚C(l, y) = ˚C(z, y). Therefore, the claim holds even without y, z, w, lbeing all distinct.

(117)

−4 −3 −2 −1 1 2 3 4 5

−3

−2

−1 1 2 3

0

C(y, z) = ˚˚ C(z, y) =C

v1(y)−v1(z) v2(y)−v2(z)

(118)

−4 −3 −2 −1 1 2 3 4 5

−3

−2

−1 1 2 3

0

C

(119)

Convexity of C

Claim

The setC is convex.

(120)

−4 −3 −2 −1 1 2 3 4 5

−4

−3

−2

−1 1 2 3

0

C

(121)

Holmstr¨om Characterization

Set of allocationsA={a, b}

Social welfares at these two allocations areP

j∈Nvj(a)andP

j∈Nvj(b)

(122)

Holmstr¨om Characterization

j∈Nvj(a)andP

j∈Nvj(b) Efficiency requires that ifais chosen, thenP

j∈Nvj(a)≥P

j∈Nvj(b)

(123)

Holmstr¨om Characterization

j∈Nvj(a)andP

j∈Nvj(a)≥P

j∈Nvj(b) Fix valuations of agents other thaniatv−i

Fix valuations of agentiexcept allocationa, i.e., atbatvi(b)

(124)

Holmstr¨om Characterization

j∈Nvj(a)andP

j∈Nvj(a)≥P

Fix valuations of agentiexcept allocationa, i.e., atbatvi(b) There exists some thresholdv_i^∗(a)such that

◮ for allvi(a)≥v_i^∗(a),ais the outcome

◮ for allvi(a)< v_i^∗(a),bis the outcome

(125)

Holmstr¨om Characterization

j∈Nvj(a)andP

j∈Nvj(a)≥P

Fix valuations of agentiexcept allocationa, i.e., atbatvi(b) There exists some thresholdv_i^∗(a)such that

◮ for allvi(a)≥v_i^∗(a),ais the outcome

◮ for allvi(a)< v_i^∗(a),bis the outcome

Considervi(a) =v_i^∗(a) +ǫ, ǫ >0, and write the DSIC constraint:

v^∗_i(a) +ǫ−pi,a≥vi(b)−pi,b (1) outcome does not change⇒payment does not change

(126)

Holmstr¨om Characterization

Considervi(a) =v_i^∗(a)−δ,δ >0, and similarly:

vi(b)−pi,b≥v_i^∗(a)−δ−pi,a (2) Combining Equations (1) and (2) and taking limitsǫ, δ→0, we get,

vi(b)−pi,b=v^∗_i(a)−pi,a

(127)

Holmstr¨om Characterization

Sincev^∗_i(a)is a threshold of change ofefficientoutcome, v_i^∗(a) + X

j∈N\{i}

vj(a) =vi(b) + X

j∈N\{i}

vj(b)

(128)

Holmstr¨om Characterization

Sincev^∗_i(a)is a threshold of change ofefficientoutcome, v_i^∗(a) + X

j∈N\{i}

vj(a) =vi(b) + X

j∈N\{i}

vj(b)

Substituting:

pi,a−pi,b=−



 X

j∈N\{i}

vj(b)− X

j∈N\{i}

vj(a)



