Information Technology Reference
In-Depth Information
The mechanism we suggest for the self-interested layered-graph network flow
problem indicates that for some problems we can devise
tractable
allocatively-
ecient, strategy-resistant, and
-budget-balanced solutions. It remains an open
problem to characterize the domains in which such a solution is achievable. Also,
as explained above, this paper considers a domain in which finding a beneficial
manipulation is NP-hard to be a strategy-resistant domain. It also remains an
open problem to find domains in which we can achieve a stronger notion of
strategy-resistance.
4
Self-interested Network Flow
We now present the self-interested layered-graph network flow problem. Consider
a flow network on a layered graph. We have a graph
G
=
<V,E>
,withsource
vertex
s
and target vertex
t
. The vertices of the graph are partitioned into
n
+1
layers,
L
0
=
. The edges only run between consecutive layers.
We have a capacity function
c
:
E
{
s
}
,L
1
, ..., L
n
=
{
t
}
IR which is the maximal flow allowed on
theedges.Wealsohaveaset
I
of agents. Each agent controls a subset
E
i
⊂
→
E
of the graph's edges. No two agents control the same edge:
E
j
=
φ
.
The mechanism chooses a valid flow from
s
to
t
. A valid flow is a function
f
:
∀
i
=
j
E
i
∩
E
→
R
such that the following hold:
∀
(
u,v
)
∈E
f
(
u, v
)
≤
c
(
u, v
),
∀
(
u,v
)
∈E
f
(
u, v
)=
∀
u∈V −{s,t}
v∈V
f
(
u, v
) = 0. We denote the positive flow as fol-
lows: if
f
(
u, v
)
>
0then
f
+
(
u, v
)=
f
(
u, v
), otherwise
f
+
(
u, v
) = 0. We denote
thesizeoftheflow
−
f
(
v, u
), and
=
v∈V
f
(
s, v
). The flow the mechanism chooses may
only go through edges that belong to some agent. The mechanism knows the
capacity constraints of the edges, but must treat edges not reported by an agent
as edges whose capacity is 0. Each agent values the flow chosen by the mecha-
nism according to the total flow going through its edges. Let
f
be the valid flow
chosen by the mechanism, and
E
f
the set of edges in
f
through which there is
a positive flow:
E
f
=
|
f
|
.Wedenotethesetof
A
i
's edges used
in the flow
f
by:
E
f,i
=
E
f
∩ E
i
. The agent's valuation of the flow is
v
i
(
f
)=
e∈E
f,i
{
e
∈
E
|
f
(
e
)
>
0
}
f
(
e
)
.
(4)
A direct revelation implementation for the self-interested network flow prob-
lem would require each agent to state its valuation of all possible flows, which
is not tractable. An alternative tractable implementation is to simply make the
type of an agent the set of its declared edges
E
i
∈
E
i
. Given this information,
the mechanism could compute the agents' valuations of any possible flow. We
will assume agents can only declare edges they actually own.
When the mechanism is given the agents' true types,
θ
=
E
1
,E
2
, ..., E
I
,we
want it to choose the flow that maximizes the total utility of the agents. The
mechanism would be allocatively-ecient if it chooses
f
∗
(
θ
)=
arg
max
f
f
(
e
)
.
(5)
i
e∈E
f,i
