Achieving Allocatively-Efficient and Strongly Budget-Balanced Mechanisms in the
Network Flow Domain for Bounded-Rational Agents
Yoram Bachrach and Jeffrey S.Ronschein
{yori,jeff }@cs.huji.ac.il
School of Engineering and Computer Science
董卿经典语录
Hebrew University Jerusalem,Israel
Abstract
Vickrey-Clarke-Groves (VCG)mechanisms are a framework for finding a solution to a distributed optimization problem in systems of lf-interested agents.VCG mechanisms have received wide at-tention in the AI community becau they are ef-ficient and strategy-proof;a special ca of the Groves family of mechanisms,VCG mechanisms are the only direct-revelation mechanisms that are allocatively efficient and strategy-proof.Unfortu-nately,they are only weakly budget-balanced.
We consider lf-interested agents in a network flow domain,and show that in this domain,it is possible to design a mechanism that is both allocatively-efficient and almost completely budget-balanced.This is done by choosing a mech-anism that is not strategy-proof but rather strategy-resistant .Instead of using the VCG mechanism,we propo a mechanism in which finding a beneficial manipulation is an NP-complete problem,and the payments from the agents to the mechanism may be minimized as much as desired.
1Mechanisms for Network Flow世界最富的国家排名
Mechanisms face the problem of finding a system-wide so-lution to an optimization problem bad on private informa-tion given by lf-interested agents.A well-known solution to such problems in the ca of quasi-linear preferences is that of Groves mechanisms.A special ca of the Groves fam-ily of mechanisms are VCG mechanisms,which are budget-balanced,allocatively-efficient,and strategy-proof.
A significant disadvantage of VCG mechanisms is that they are only weakly budget-balanced.We would in principle pre-fer a strongly budget-balanced mechanism,where the total sum of payments to the mechanism is zero: i t i (θ)=0.Impossibility results ([Green and Laffont,1977]and [Hur-wicz,1975])
show that in a quasi-linear environment,it is impossible to achieve a mechanism that is strategy-proof,allocatively-efficient,and strongly budget-balanced.
We address this by slightly relaxing the strategy-proof re-quirement,replacing it with strategy-resistance .A mecha-nism is strategy-proof if the dominant strategy of each agent is to reveal its true type to the mechanism.Strategy-resistance
only requires that even if an agent is given the reported types of the other agents,it has a computationally intractable prob-lem to solve if it wishes to find a beneficial manipulation (i.e.,report a fal type to the mechanism to gain higher utility).In this work,we consider the domain of network flows.In that domain,the edges of a network flow belong to v-eral lf-interested agents.Each agent reports its edges to the mechanism.The mechanism is then required to choo a flow from the source vertex to the target vertex.Agents gain utility from flow units on their edges.Agents can lie,and declare a subt of the edges they really own.This manipulation may change the flow that the mechanism choos,and agents may try to take advantage of this.However,we show that it is possible to u the fact that agents have computational lim-itations and are not unboundedly rational,so as to construct mechanisms with beneficial properties.
1.1Self-Interested Network Flows
正能量早安语录
We explore the problem of designing a mechanism for bounded-rational agents in a distributed flow problem.We demonstrate that for this domain,we can find a mechanism that is allocatively-efficient, -budget-balanced,and strategy-resistant.This means that if we assume the agents are bounded-rational and would not try to manipulate the mech-anism if such manipulation is an NP-complete problem,they would all truthfully report their preferences.Once the mech-anism gets their true preferences,it choos the outcome that maximizes total utility of the agents.To achieve this truth-fulness,the mechanism requires payments;however,the total sum of the payments can be minimized as much as required.We now prent the lf-interested layered-graph network flow problem.Consider a flow network on a layered graph.We have a graph G =<V,E >,with source vertex s and target vertex t .The vertices of the graph are partitioned into n +1layers,L 0={s },L 1,...,L n ={t }.The edges only run between concutive layers.We have a capacity function c :E →R which is the maximal flow allowed on the edges.We also have a t I of agents.Each agent controls a subt E i ⊂E of the graph’s edges.No two agents control the same edge:∀i =j E i ∩E j =φ.
The mechanism choos a valid flow from s to t .A valid flow is a function f :E →R such that ∀(u,v )∈E f (u,v )≤c (u,v ),∀(u,v )∈E f (u,v )=−f (v,u ),and ∀u ∈V −{s,t }
v ∈V f (u,v )=0.
Each agent values the flow according to the total flow go-ing through its edges.Let f be the valid flow chon by the mechanism,and E f the t of edges in f through which there is a positive flow:E f ={e ∈E |f (e )>0}.We denote the t of A i ’s edges ud 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
f (e ).
When the mechanism is given the agents’true types,θ=E 1,E 2,...,E I ,we want it to choo the flow that maximizes the total utility of the agents.The mecha-nism would be allocatively-efficient if it choos f ∗(θ)=arg max f i爬英文>怎样治近视
e ∈E f,i
f (e ).In a layered graph the flow that maximizes the sum of agents’utilities is the maximal flow (proof of this is given in the full paper).Thus,if each agent truthfully declares its subt of edges,the mechanism can eas-ily compute f ∗(θ)by runnin
g a maximal flow algorithm,suc
h as the Edmonds-Karp algorithm.
As shown in the full version of this paper,a naive mecha-nism for the lf-interested flow problem,with no payments to the mechanism,is not strategy-proof.An agent may de-clare a subt of the edges it controls,to change the flow that the mechanism choos to a flow that the agent values more.
1.2Self-Interested Network Flow Mechanism
工作效率是什么意思
We assume quasi-linear utility.Each agent pays the mech-anism 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 rule we u is simple:each agent pays the mech-anism a constant of c for each edge it declares it owns.Let E i ⊂E i be the subt of edges an agent declares it owns.
Then p i (E i )=c |E
i |.We also give a minor correction to make sure the mechanism is individual-rational.The payment p i gives the agent a utility of 0when the agent’s valuation of the chon flow is less than the payment to the mechanism.
Assume that A i knows E
j for all j =i .It can easily calcu-late the utility it would get by truthfully declaring all its edges.How hard is it for i to find a subt of edges it could declare to the mechanism so as to gain a higher utility?We define the problem of finding a uful manipulation in the lf-interested network flow domain as follows.
FLOW-EDGE-SUBSET:We are given a layered graph flow network,with the capacity function c :E →R ,E −i the declared edges of the other agents,and E i ,the t of our edges.We are also given the constant c of the payment,and we know that if we declare that we have k edges,our pay-ment to the mechanism would be p i =ck .We assume the mechanism prefers a maximal flow that maximizes our util-ity of all the possible maximal flows.We are also given a constant k ,the target utility for A i .We are asked if there is
a subt of A i ’s edges E
i ⊂E i ,such that the maximal flow
叶金强chon by the mechanism,f ∗(E 1,...,E i −1,E
论语诠解
i ,E i +1,...,E I )
gives A i a utility of at least k :u i (f ∗
,p i )=v i (f ∗)−p i = e ∈E f ∗,i f (e )−c |E
i |≥k .
A reduction,given in the full version of this paper,indi-cates that FLOW-EDGE-SUBSET is an NP-complete prob-lem.The reduction given is from a general VERTEX-COVER instance to a FLOW-EDGE-SUBSET problem.Although we do not include the full details of the reduc-
tion here,we do give some intuition about how it was con-structed.Given the original VERTEX-COVER instance,we build a layer graph,where one of the agents,A 1,controls all the edges between two concutive layers.Each edge A 1owns corresponds to a vertex in the original VERTEX-COVER graph.The network flow graph is constructed so that in order for A 1to maximize its valuation,it must declare a subt of edges that is a vertex cover of G .However,in order to minimize its payment to the mechanism,A 1must choo as few edges as possible.If the payment constant c is small enough,A 1’s top priority is to make its chon vertices a vertex-cover,and only then choosing as few edges as possi-ble.This makes its preferred choice the minimal vertex cover of the original graph.
2Conclusions and Future Directions
We have suggested a mechanism for the distributed network flow problem with lf-interested agents.With a proper choice of the payment constant c ,finding a beneficial manip-ulation is an NP-complete problem.Since finding a beneficial manipulation is intractable,we encourage agents to truthfully report their preferences.In this ca,the mechanism would choo the result maximizing the sum of agents’utilities,and we have an allocatively-efficient mechanism.
Given some >0,we can make the mechanism -budget-balanced,by choosing a small enough payment con-stant c < n (|E |+|V |),where n is the number of agents.This way,all of the agents together pay less than .The mechanism we have described is also individual-rational.Therefore,in the domain of network flows,this achieves an individual-rational,allocatively-efficient, -budget-balanced,and strategy-resistant mechanism.The standard VCG solu-tion in this domain would be only weakly budget-balanced,but strategy-proof.
Impossibility results ([Green and Laffont,1977]and [Hur-wicz,1975])indicate that no direct-revelation mechanism can achieve strong budget-balance without sacrificing either allocative-efficiency or strategy-proofness.We believe that in many cas,trading strategy-proofness for strategy-resistance
is a fair price to pay for achieving strong budget-balance.Our strategy-resistance rested on the worst ca assump-tions of NP-hardness,which only indicates that a certain problem has some hard instances.A stronger notion of strategy-resistance could also require the manipulation prob-lem to have no approximation methods,that it be in some harder complexity class,or that it be hard to find any (not just the optimal)beneficial manipulation.This work constitutes a first step in establishing the notion of strategy-resistance.
References
[Green and Laffont,1977]Jerry Green and Jean-Jacques Laffont.Characterization of satisfactory mechanisms for the revelation of preferences for public goods.Economet-rica ,45(2):427–38,March 1977.
[Hurwicz,1975]Leonid Hurwicz.On the existence of al-location systems who manipulative Nash equilibria are pareto-optimal.In 3rd World Congress of the Econometric Society (Unpublished),1975.
