Information Technology Reference
In-Depth Information
4.1
Layered Graphs and Mechanisms for Network Flow
Consider a self-interested network flow problem in a
layered
graph. If each agent
truthfully declares its subset of edges, the mechanism can easily compute
f
∗
(
θ
)
by running a maximal flow algorithm, such as the Edmonds-Karp algorithm.
Proof.
Suppose the mechanism chooses a flow
f
. The total flow exiting
s
ends
up in vertices in
L
1
.Alltheflowfrom
L
1
ends up in vertices in
L
2
,andsoon.
Since flow may only go through edges owned by some agent, the total utility
obtained by the flow
f
is
f
+
(
e
)=
f
+
(
u, v
)+
...
+
f
+
(
u, v
)=
|
f
|
+
...
+
|
f
|
=(
n
−
1)
|
f
e∈E
u∈L
1
,v∈L
2
u∈L
n−
1
,v∈L
n
(6)
A naive mechanism for the self-interested flow problem, with no payments to
the mechanism, is not strategy-proof. An agent may declare only a subset of the
edges it controls, to change the flow that the mechanism chooses to a flow that
the agent values more. Figure 1 shows two agents on a certain network flow (
A
1
and
A
2
).
A
1
's edges are marked with dashed lines, and
A
2
's edges are marked
with full lines.
A
2
truthfully declares all its edges. Assuming the mechanism
favors
A
1
and chooses the specific maximal that maximizes
A
1
's utility among
all maximal flows,
A
1
can do better by not declaring its topmost edge (
v
1
,v
4
),
gaining a utility of 2 instead of 1.
Fig. 1.
Manipulations in self-interested flow problems
5
A Mechanism for the Self-interested Network Flow
Problem
We assume quasi-linear utility. Each agent pays the mechanism a payment
p
i
,
and its utility is
u
i
(
f
)=
v
i
(
f
)
p
i
. We now show that by using a straightforward
payment rule, we make finding a beneficial manipulation NP-hard. The payment
−
