>
Using
Contracts to Influence the Outcome of a Game
Robert McGrew
Yoav Shoham
Stanford University
Introduction
Game theoretic
approach to AI
Recognizes
that agents have differing interests.
Agents respond
to their strategic situation.
Usually pursued
through mechanism design
An all-powerful
designer creates a game to force agents to act in a certain way
Auctions
Introduction
Suppose a
pre-existing strategic situation
Exchanging
goods after an online auction
Enforcing
correct behavior in a protocol
Suppose a
limited center
Cannot arbitarily
impose outcomes.
Has cost for
intervening in the protocol.
Related Work
Social Conventions
(Shoham &
Tennenholtz 95)
The center
wishes to influence a given game.
It suggests
a social convention which is improves welfare of players so long
as all players follow it.
The agents
simply obey the social law.
Related Work
k-Implementation
(Tennenholtz
03)
Suppose the
center is an observer to a game.
Center can
provide payments based on outcomes realized, but cannot fine agents.
What can the
center achieve without expenditure in equilibrium?
The center
promises agents payment if specific outcomes occur, but ends up not
having to pay for anything.
Our Problem
The center
wishes to influence the outcome of a given game G.
The center
suggests a contract, the players agree to it, then the center enforces
it.
The center
can reward or fine players in the contract but must be budget-balanced.
The Extended Game
The Extended Game
The center suggests a
contract to the agents.
The Extended Game
The agents send the center
their signatures on the contract.
The Extended Game
If some agent doesn00
sign the contract, the game G is played without the center.
The Extended Game
If all agents sign the
contract, the game G is played and the center observes it.
The Extended Game
The center punishes the
agents based on the contract and the actions taken.
Our Goal
Given a pure-strategy
action profile 00/font> to achieve, we design
a contract:
a set of penalties and rewards for the center to mete out in Punishment
stage
an equilibrium
for the agents to follow
We seek a
subgame-perfect equilibrium (SPE).
Passive Center
An active
center acts on the equilibrium path.
A passive
center acts only when some player deviates from eqm.
00ction00
here involves collecting signatures, observing the game, punishing players.
Because a
passive center threatens to act if players deviate from the equilibrium,
it never has to actually do anything.
Roadmap
What contract
and eqm can the center suggest and the agents follow?
We will require,
progressively:
No punishments
or rewards in equilibrium.
No observation
of the game in equilibrium.
No signature
collection in equilibrium.
At the end,
the protocol will have a completely passive center.
Roadmap
What contract
and eqm can the center suggest and the agents follow?
We will require,
progressively:
No punishments
or rewards in equilibrium.
No observation
of the game in equilibrium.
No signature
collection in equilibrium.
At the end,
the protocol will have a completely passive center.
No Punishments
What contract
and eqm can the center suggest and the agents follow?
Thm: There
exists a contract and an equilibrium for which profile 00/font> is played without rewards or
punishments in equilibrium if and only if for each agent i, there
exists a Nash equilibrium 00/font>i of G with Ui(00/font>)
赂 Ui(00/font>i).
We00l find
that contract and eqm by working backwards.
The Extended Game
Assenting Branch
Suppose all
agents assented to the contract.
We punish
agents by a large amount M for deviating from the specified action
profile.
It is a unique
SPE for the agents to take the correct action.
The Extended Game
Non-Assenting Branch
Suppose some
agent did not sign.
We that agent
to have as low payoffs as possible.
However, in
a subgame-perfect equilibrium, some Nash equilibrium must be played
in this subgame.
Punishment Equilibrium
Let the punishment
equilibrium 00/font>i for a agent i
be the Nash equilibrium of G with the lowest payoff for agent
i.
So if some
agent objects to signing the contract, the remaining agents coordinate
on his punishment equilibrium.
The Extended Game
When will agent i sign
the contract for profile 00/font>?
Payoff: Ui(a)
Payoff: 0
Payoff:
Ui(00/font>i)
Signature Collection
Clearly i
will sign when Ui(00/font>) 赂 Ui(00/font>i).
Thus, there
is a contract and eqm to achieve an action profile 00/font> if 8i, Ui(00/font>)
赂 Ui(00/font>i).
The center
need only punish if some player deviates from the equilibrium.
Roadmap
What contract
and eqm can the center suggest and the agents follow?
We will require,
progressively:
No punishments
or rewards in equilibrium.
No observation
of the game in equilibrium.
No signature
collection in equilibrium.
At the end,
the protocol will have a completely passive center.
The Extended Game
Already passive
Remove observation
Already passive
Remove collection
Removing The Center:
Execution
During the
punishment phase, the agents notify the center if some agent deviated
from the contract.
The punishment
phase is now a strategic game between the players.
We will choose
a game with
action
space 2N
payoffs dependent
on our contract.
Two Cases
How is the
Punishment stage linked to what happened in the Execution stage?
Two cases:
Verfiable:
the center can determine during the punishment phase what action profile
was played.
Unverifiable:
the center cannot determine what profile was played.
Verifiable and Unverifiable
Cases
Thm: In the
verifiable case, there is a contract with a passive center such that
There is a
unique SPE in the assenting branch for each action profile 00/font>.
Thm: In the
unverifiable case, there is a contract with a passive center such that
There is an
SPE in the assenting branch for each action profile 00/font>.
This SPE is
not in general unique.
The Verifiable Case
Passive-center
contract for 00/font>:
If an agent
i correctly notifies the center of a deviation from 00/font>, i is rewarded with m.
If an agent
i notifies the center of a deviation from 00/font>, all deviating agents j 00/font>
i are punished with M (M/n > m).
Equilibrium:
Each agent
plays 00/font>, then notifies the center of
any deviations.
This equilibrium
is dominant-strategy and unique.
The Unverifiable Case
Passive-center
contract for 00/font>:
If i tells
the center that j 00/font> i deviated from 00/font>,
j is punished with M.
Equilibrium:
Each agent
plays 00/font>, then notifies center of any
deviations.
This is an
equilibrium, as each agent is indifferent between telling and not telling.
Thus, there
exists an equilibrium...
The Unverifiable Case
However, any
passive-center contract for which there is a SPE for action profile 00/font>
will in general also have an SPE for many other action profiles.
For example:
Suppose
we have a passive-center contract c specifying action profile 00/font>.
Thm: If 00/font>
is a Nash equilibrium of G, then any c will admit an SPE
where 00/font> is played instead of 00
Spurious Equilibria
There must be an equilibrium 00/font>
of the Punishment stage without punishments or rewards.
Spurious Equilibria
Let 00/font> be an equilibrium of G.
Spurious Equilibria
(00/font>, 00/font>) must be an SPE of the last
two stages.
Spurious Equilibria
(00/font>, 00/font>) must be an SPE of the last
two stages.
(00/font>, 00/font>) must be at least as good for
each player i as 00/font>i, so all players
will sign.
Roadmap
What contract
and eqm can the center suggest and the agents follow?
We will require,
progressively:
No punishments
or rewards in equilibrium.
No observation
of the game in equilibrium.
No signature
collection in equilibrium.
At the end,
the protocol will have a completely passive center.
The Extended Game
Already passive
Already passive
Already passive
Remove collection
Removing the Center:
Signatures
We will make
the players exchange signatures by themselves.
Naive mechanism:
Agents
broadcast their signatures during Signature Collection phase.
In Punishment
phase, an agent must present signatures from all agents when notifying
center of a deviation from the contract.
Naive Broadcast
0,10
10,10
B
0,0
11,1
A
Y
X
m,10-M
10,10
B
0,0
11,1
A
Y
X
The contract
specifies (B, X).
Suppose Column
broadcasts his signature, but Row does not.
Row will choose
to enforce the contract only if it benefits him: if Column deviates
and Row does not.
Naive Broadcast
0,10
10,10
B
0,0
11,1
A
Y
X
m,10-M
10,10
B
0,0
11,1
A
Y
X
The contract
specifies (B, X).
Suppose Column
broadcasts his signature, but Row does not.
Row will choose
to enforce the contract only if it benefits him: if Column deviates
and Row does not.
Naive Broadcast
0,10
10,10
B
0,0
11,1
A
Y
X
m,10-M
10,10
B
0,0
11,1
A
Y
X
The contract
specifies (B, X).
Suppose Column
broadcasts his signature, but Row does not.
Row will choose
to enforce the contract only if it benefits him: if Column deviates
and Row does not.
Pre-contracts
We00l solve
this problem by introducing an additional layer of contracts.
Agents will
first sign a pre-contract pledging them to broadcast their signatures
on the real contract to all other agents.
If agents
fail to broadcast their signatures on the contract, then they are fined.
Extended Signature
Collection
Assent
Objection
Contract
Suggestion
Execution
Execution
Punishment
Pre-Contract
Signing
Contract
Signing
Pre-Contract
Punishment
We break the Signature
Collection stage into three stages.
Extended Signature
Collection
Assent
Objection
Contract
Suggestion
Execution
Execution
Punishment
Pre-Contract
Signing
Contract
Signing
Pre-Contract
Punishment
First, the agents exchange
signatures on the pre-contract.
Extended Signature
Collection
Assent
Objection
Contract
Suggestion
Execution
Execution
Punishment
Pre-Contract
Signing
Pre-Contract
Punishment
Then, if all pre-contract
signatures are received, the agents exchange signatures on the contract.
Contract
Signing
Extended Signature
Collection
Assent
Objection
Contract
Suggestion
Execution
Execution
Punishment
Pre-Contract
Signing
Pre-Contract
Punishment
Finally, if an agent
fails to receive some other player00 signature, he can complain to
the center.
Contract
Signing
Extended Signature
Collection
Pre-contract
Punishment idea:
An agent
must reveal his signature on the contract to the center if he wishes
to complain.
If one player
complains about a deviation, it is a best response for all other players
to complain.
The center
will reveal all signatures he receives to all players.
Thus, if some
player fails to reveal his signature on the contract, all players will
complain in eqm, and all signatures will become known.
Extended Signature
Collection
Thm: There
exists a contract and an equilibrium for which profile 00/font> is played with a completely
passive center if and only if for each agent i, there exists
a Nash equilibrium 00/font>i of G with Ui(00/font>)
赂 Ui(00/font>i).
The center
will take no action in equilibrium.
Thus, we can
achieve as much in a protocol in which the center is passive as we could
with center which is active in the Signature Collection and Execution
phases.
Summary
Contracts
allow agents to achieve outcomes which are otherwise not possible in
eqm.
We can push
the work of making sure the contract is enforced onto the players.
In an unverifiable
setting, pushing this work onto the players results in spurious equilibria
where agents violate the contract in addition to the good equilibrium
where they obey it.
Future Directions
Generalize
to mechanism design setting where players have private information.
Apply idea
of passive center to indirect and distributed mechanism design.
A passive
center is an appealing minimal notion of a center in a distributed setting.
download Using Contracts to Influence the Outcome of a Game
