Southampton是什么意思thampton在线翻译读音

porta是什么意思ta的用法读音典-之路

2023年4月3日发(作者：friendship)

FrugalityRatiosAndImprovedTruthfulMechanismsfor

VertexCover∗

EdithElkind

HebrewUniversityof

Jerusalem,Israel,and

UniversityofSouthampton,

Southampton,SO171BJ,U.K.

LeslieAnnGoldberg

UniversityofLiverpool

LiverpoolL693BX,U.K.

PaulGoldberg

UniversityofLiverpool

LiverpoolL693BX,U.K.

ABSTRACT

Inset-systemauctions,thereareseveraloverlappingteamsofagents,

tioneer’-

plesofthissettingincludeshortest-pathauctionsandvertex-cover

ly,Karlin,KempeandTamirintroducedanewdef-

ally,the“frugality

ratio”istheratioofthetotalpaymentofamechanismtoadesired

iocapturestheextenttowhichthemecha-

nismoverpays,relativetoperceivedfaircostinatruthfulauction.

Inthispaper,weproposeanewtruthfulpolynomial-timeauction

thatthesolutionqualityiswithaconstantfactorofoptimaland

thefrugalityratioiswithinaconstantfactorofthebestpossible

worst-casebound;thisistheﬁrstauctionforthisproblemtohave

er,weshowhowtotransformanytruth-

fulauctionintoafrugalonewhilepreservingtheapproximation

,weconsidertwonaturalmodiﬁcationsofthedeﬁnition

ofKarlinetal.,andweanalysethepropertiesoftheresultingpay-

mentbounds,suchasmonotonicity,computationalhardness,and

ythe

relationshipsbetweenthedifferentpaymentbounds,bothforgen-

eralsetsystemsandforspeciﬁcset-systemauctions,suchaspath

hesenewdeﬁnitions

intheproofofourmainresultforvertex-coverauctionsviaaboot-

strappingtechnique,whichmaybeofindependentinterest.

CategoriesandSubjectDescriptors

F.2[TheoryofComputation]:AnalysisofAlgorithmsandProb-

lemComplexity;J.4[ComputerApplications]:SocialandBehav-

ioralSciences—economics

GeneralTerms

Algorithms,Economics,Theory

=0,c

=aphis2-connectedandthe

thegraphcontainsnoA–DpaththatisdisjointfromABCD,and

hencethefrugalityratioofVCGonthisgraphremainsundeﬁned.

Atthesametime,thereisnomonopoly,thatis,thereisnoven-

ionsforothertypesof

setsystems,therequirementthatthereexistafeasiblesolutiondis-

jointfromtheselectedoneisevenmoresevere:forexample,for

vertex-coverauctions(wherevendorscorrespondtotheverticesof

someunderlyinggraph,andthefeasiblesetsarevertexcovers)the

with

thisproblem,Karlinetal.[16]suggestabetterbenchmark,which

isdeﬁantity,which

theydenoteby,intuitivelycorrespondstothevalueofacheapest

nthisnewdeﬁnition,theauthorscon-

structnewmechanismsfortheshortestpathproblemandshowthat

theoverpaymentofthesemechanismsiswithinaconstantfactorof

optimal.

1.1Ourresults

VertexcoverauctionsWeproposeatruthfulpolynomial-time

auctionforvertexcoverthatoutputsasolutionwhosecostiswithin

afactorof2ofoptimal,andwhosefrugalityratioisatmost2∆,

where∆isthemaximumdegreeofthegraph(Theorem4).We

complementthisresultbyproving(Theorem5)thatforany∆and

n,therearegraphsofmaximumdegree∆andsize(n)forwhich

anytruthfulmechanismhasfrugalityratioatleast∆/ans

thatthesolutionqualityofourauctioniswithafactorof2ofop-

timalandthefrugalityratioiswithinafactorof4ofthebestpos-

estofourknowledge,

thisistheﬁrstauctionforthisproblemthatenjoystheseproper-

er,weshowhowtotransformanytruthfulmechanism

forthevertex-coverproblemintoafrugalonewhilepreservingthe

approximationratio.

FrugalityratiosOurvertexcoverresultsnaturallysuggesttwo

modiﬁcationsofthedeﬁnitionofin[16].Thesemodiﬁcations

canbemadeindependentlyofeachother,resultinginfourdiffer-

entpaymentboundsTUmax,TUmin,NTUmax,andNTUmin,

whereNTUminisequaltotheoriginalpaymentboundofin[16].

AllfourpaymentboundsariseasNashequilibriaofcertaingames

(seethefullversionofthispaper[8]);thedifferencesbetween

themcanbeseenas“thepriceofinitiative”and“thepriceofco-

operation”(seeSection3).Whileourmainresultaboutvertex

coverauctions(Theorem4)iswithrespecttoNTUmin=,we

makeuseofthenewdeﬁnitionsbyﬁrstcomparingthepaymentof

ourmechanismtoaweakerboundNTUmax,andthenbootstrap-

pingfromthisresulttoobtainthedesiredbound.

Inspiredbythisapplication,weembarkonafurtherstudyof

ultshereareasfollows:

rve(Proposition1)thatthefourpaymentboundsal-

waysobeyaparticularorderthatisindependentofthechoiceof

thesetsystemandthecostvector,namely,TUmin≤NTUmin≤

NTUmax≤ideexamples(Proposition5and

Corollaries1and2)showingthatforthevertexcoverproblemany

twoconsecutiveboundscandifferbyafactorofn−2,wherenis

show(Theorem2)thatthissepara-

tionisalmostbestpossibleforgeneralsetsystemsbyprovingthat

foranysetsystemTUmax/TUmin≤rast,wedemon-

strate(Theorem3)thatforpathauctionsTUmax/TUmin≤2.

Weprovideexamples(Propositions2,3and4)showingthatthis

hisasanargumentforthestudyofvertex-

coverauctions,astheyappeartobemorerepresentativeofthegen-

eralteam-selectionproblemthanthewidelystudiedpathauctions.

(Theorem1)thatforanysetsystem,ifthereisacost

vectorforwhichTUminandNTUmindifferbyafactorof,

thereisanothercostvectorthatseparatesNTUminandNTUmax

bythesamefactorandviceversa;thesameistrueforthepairs

(NTUmin,NTUmax)and(NTUmax,TUmax).Thissymme-

tryisquitesurprising,,TUminandNTUmaxareob-

observationsuggeststhatthefourpaymentboundsshouldbestud-

iedinauniﬁedframework;moreover,itleadsustobelievethatthe

bootstrappingtechniqueofTheorem4mayhaveotherapplications.

uatethepaymentboundsintroducedherewithrespect

icular,wenotethatthe

paymentbound=NTUminof[16]exhibitssomecounterintu-

itiveproperties,suchasnonmonotonicitywithrespecttoaddinga

newfeasibleset(Proposition7),andisNP-hardtocompute(Theo-

rem6),whilesomeoftheotherpaymentboundsdonotsufferfrom

nbeseenasanargumentinfavourofusing

weakerbutefﬁcientlycomputableboundsNTUmaxandTUmax.

Relatedwork

Vertex-coverauctionshavebeenstudiedinthepastbyTalwar[21]

andCalinescu[5].Bothofthesepapersarebasedonthedeﬁnition

offrugalityratiousedin[1];asmentionedbefore,thismeansthat

[21]showsthat

thefrugalityratioofVCGisatmost∆.However,sinceﬁnding

thecheapestvertexcoverisanNP-hardproblem,theVCGmech-

ﬁrst(and,tothebestof

ourknowledge,only)papertoinvestigatepolynomial-timetruthful

mechanismsforvertexcoveris[5].Thispaperstudiesanauction

thatisbasedonthegreedyallocationalgorithm,whichhasanap-

hemainfocusof[5]isthemore

generalsetcoverproblem,theresultsof[5]implyafrugalityratio

of2∆ultsimproveonthoseof[21]as

ourmechanismispolynomial-timecomputable,aswellasonthose

of[5],asourmechanismhasabetterapproximationratio,andwe

proveastrongerboundonthefrugalityratio;moreover,thisbound

alsoappliestothemechanismof[5].

INARIES

Inmostofthispaper,wediscussauctionsforsetsystems.A

setsystemisapair(E,F),whereEisthegroundset,|E|=n,

andFisacollectionoffeasiblesets,

particulartypesofsetsystemsareofinteresttous—shortestpath

systems,inwhichthegroundsetconsistsofalledgesofanetwork,

andthefeasiblesetsarepathsbetweentwospeciﬁedverticessand

t,andvertexcoversystems,inwhichtheelementsofthegroundset

aretheverticesofagraph,andthefeasiblesetsarevertexcoversof

thisgraph.

Insetsystemauctions,eachelementeofthegroundsetisowned

byanindependentagentandhasanassociatednon-negativecostc

Thegoalofthecentreistoselect(purchase)

elementeintheselectedsetincursacostofc

.Theelementsthat

arenotselectedincurnocosts.

Theauctionproceedsasfollows:allelementsofthegroundset

maketheirbids,thecentreselectsafeasiblesetbasedonthebids

ly,anauctionisdeﬁned

byanallocationruleA:Rn→FandapaymentruleP:Rn→

ocationruletakesasinputavectorofbidsanddecides

mentrulealso

takesasinputavectorofbidsanddecideshowmuchtopaytoeach

thepaymenttoeachagentshouldbeatleastashighashisincurred

cost(0foragentsnotintheselectedsetandc

foragentsinthe

selectedset)andincentivecompatibility,,each

agent’sdominantstrategyistobidhistruecost.

Anallocationruleismonotoneifanagentcannotincreasehis

ly,foranybid

vectorbandanye∈E,ife∈A(b)thene∈A(b

,...,b′

,...,b

)

foranyb′

.GivenamonotoneallocationruleAandabid

vectorb,thethresholdbidt

ofanagente∈A(b)isthehighest

bidofthisagentthatstillwinstheauction,giventhatthebidsof

ly,t

=sup{b′

∈R|

e∈A(b

,...,b′

,...,b

)}.Itiswellknown([19,13])

thatanyauctionthathasamonotoneallocationruleandpayseach

agenthisthresholdbidistruthful;conversely,anytruthfulauction

hasamonotoneallocationrule.

TheVCGmechanismisatruthfulmechanismthatmaximises

the“socialwelfare”system

auctions,thissimplymeanspickingacheapestfeasibleset,paying

eachagentintheselectedsethisthresholdbid,andpaying0to

,however,thattheVCGmechanismmaybe

difﬁculttoimplement,sinceﬁndingacheapestfeasiblesetmaybe

intractable.

IfUisasetofagents,c(U)denotesPw∈U

.Similarly,b(U)

denotesPw∈U

ITYRATIOS

Westartbyreproducingthedeﬁnitionofthequantityfrom[16,

Deﬁnition4].

Let(E,F)beasetsystemandletSbeacheapestfeasibleset

withrespecttothetruecostsc

.Then(c,S)isthesolutiontothe

followingoptimisationproblem.

MinimiseB=Pe∈S

subjectto

(1)b

≥c

foralle∈E

(2)Pe∈ST

≤Pe∈TS

forallT∈F

(3)foreverye∈S,thereisaT

∈Fsuchthate∈T

andPe

′

∈ST

′=Pe

′

∈T

′

Thebound(c,S)canbeseenasanoutcomeofatwo-stage

process,whereﬁrsteachagente∈Smakesabidb

statinghow

muchitwantstobepaid,andthenthecentredecideswhetherto

aviourofbothpartiesisaffectedbythe

ecentre’spointofview,theset

,itmustbeamong

thecheapestfeasiblesetsunderthenewcostsc′

fore∈S,

c′

fore∈S(condition(2)).Thereasonforthatisthat

if(2)isviolatedforsomesetT,thecentrewouldpreferTtoS.

Ontheotherhand,noagentwouldagreetoapaymentthatdoes

notcoverhiscosts(condition(1)),andmoreover,eachagenttries

tomaximisehisproﬁ,none

oftheagentscanincreasehisbidwithoutviolatingcondition(2)

(condition(3)).Thecentrewantstominimisethetotalpayout,so

(c,S)correspondstothebestpossibleoutcomefromthecentre’s

pointofview.

Thisdeﬁnitioncapturesmanyimportantaspectsofourintuition

about‘fair’r,itcanbemodiﬁedintwoways,

bothofwhicharestillquitenatural,butresultindifferentpayment

bounds.

First,wecanconsidertheworstratherthanthebestpossibleout-

,wecanconsiderthemaximumtotal

paymentthattheagentscanextractbyjointlyselectingtheirbids

subjectto(1),(2),and(3).Suchaboundcorrespondstomaximis-

ingBsubjectto(1),(2),and(3)

istheagentswhomaketheoriginalbids(ratherthanthecentre),

therhand,ina

gameinwhichthecentreproposespaymentstotheagentsinSand

theagentsacceptthemaslongas(1),(2)and(3)aresatisﬁed,we

wouldbelikelytoobserveatotalpaymentof(c,S).Hence,the

differencebetweenthesetwodeﬁnitionscanbeseenas“theprice

ofinitiative”.

Second,theagentsmaybeabletomakepaymentstoeachother.

Inthiscase,iftheycanextractmoremoneyfromthecentreby

condition(1))forsomebidders,theymightbewillingtodoso,as

theagentswhoarepaidbelowtheircostswillbecompensatedby

theyhavetosatisfyb

≥ultingchangeinpaymentscan

beseenas“thepriceofco-operation”andcorrespondstoreplacing

condition(1)withthefollowingweakercondition(1∗):

≥0foralle∈E.(1∗)

Byconsideringallpossiblecombinationsofthesemodiﬁcations,

weobtainfourdifferentpaymentbounds,namely

•TUmin(c,S),whichisthesolutiontotheoptimisationprob-

lem“MinimiseB”subjectto(1∗),(2),and(3).

•TUmax(c,S),whichisthesolutiontotheoptimisationprob-

lem“MaximiseB”subjectto(1∗),(2),and(3).

•NTUmin(c,S),whichisthesolutiontotheoptimisation

problem“MinimiseB”subjectto(1),(2),and(3).

•NTUmax(c,S),whichisthesolutiontotheoptimisation

problem“MaximiseB”subjectto(1),(2),(3).

TheabbreviationsTUandNTUcorrespond,respectively,totrans-

,theagents’abil-

ity/creteness,

wewilltakeTUmin(c)tobeTUmin(c,S)whereSisthelex-

ﬁneTUmax(c),NTUmin(c),NTUmax(c)and(c)similarly,

thoughwewillseeinSection6.3that,infact,NTUmin(c,S)and

NTUmax(c,S)atthe

quantity(c)from[16]isNTUmin(c).

Thesecondmodiﬁcation(transferableutility)ismoreintuitively

appealinginthecontextofthemaximisationproblem,asbothas-

secondmodiﬁcationcanbemadewithouttheﬁrst,theresulting

paymentboundTUmin(c,S)istoostrongtobearealisticbench-

mark,icular,itcanbesmaller

thanthetotalcostofthecheapestfeasiblesetS(seeSection6).

Nevertheless,weprovidethedeﬁnitionaswellassomeresults

aboutTUmin(c,S)inthepaper,bothforcompletenessandbe-

causewebelievethatitmayhelptounderstandwhichproperties

rpos-

sibilitywouldbetointroduceanadditionalconstraintPe∈S

≥Pe∈S

inthedeﬁnitionofTUmin(c,S)(notethatthiscondi-

tionholdsautomaticallyforTUmax(c,S),asTUmax(c,S)≥

NTUmax(c,S));however,suchadeﬁnitionwouldhavenodirect

game-theoreticinterpretation,andsomeofourresults(inparticu-

lar,theonesinSection4)wouldnolongerbetrue.

paymentboundsthatarederivedfrommax-

imisationproblems,(i.e.,TUmax(c,S)andNTUmax(c,S)),con-

straintsoftype(3),

TUmax(c,S)andNTUmax(c,S)aresolutionstolinearpro-

grams,andthereforecanbecomputedinpolynomialtimeaslong

aswehaveaseparationoracleforconstraintsin(2).Incontrast,

NTUmin(c,S)canbeNP-hardtocomputeevenifthesizeofFis

polynomial(seeSection6).

Theﬁrstandthirdinequalitiesinthefollowingobservationfol-

lowfromthefactthatcondition(1∗)isstrictlyweakerthancondi-

tion(1).

PROPOSITION1.

TUmin(c,S)≤NTUmin(c,S)≤

NTUmax(c,S)≤TUmax(c,S).

LetMbeatruthfulmechanismfor(E,F).Letp

(c)denote

lity

ratioofMwithrespecttoapaymentboundistheratiobetween

icular,

TUmin

(M)=sup

(c)/TUmin(c),

TUmax

(M)=sup

(c)/TUmax(c),

NTUmin

(M)=sup

(c)/NTUmin(c),

NTUmax

(M)=sup

(c)/NTUmax(c).

Weconcludethissectionbyshowingthatthereexistsetsystems

andrespectivecostvectorsforwhichallfourpaymentboundsare

extsection,wequantifythisdifference,bothfor

generalsetsystems,andforspeciﬁctypesofsetsystems,suchas

pathauctionsorvertexcoverauctions.

ertheshortest-pathauctiononthegraph

canbeveriﬁed,usingthereasoningofPropositions2and3below,

thatforthecostvectorc

=2,c

=1,c

5,wehave

•TUmax(c)=10(withb

=5,b

=0),

•NTUmax(c)=9(withb

=4,b

=1),

•NTUmin(c)=7(withb

=2,b

=3),

•TUmin(c)=5(withb

=0,b

=5).

INGPAYMENTBOUNDS

4.1Pathauctions

Westartbyshowingthatforpathauctionsanytwoconsecutive

paymentboundscandifferbyatleastafactorof2.

saninstanceoftheshortest-pathprob-

lemforwhichwehaveNTUmax(c)/NTUmin(c)≥2.

nstructionisduetoDavidKempe[17].Con-

siderthegraphofFigure1withtheedgecostsc

=0,c

=hesecosts,ABCDisthe

qualitiesin(2)areb

≤c

=1,

≤c

=ition(3),bothoftheseinequal-

itiesmustbetight(theformeroneistheonlyinequalityinvolv-

ingb

,andthelatteroneistheonly反义词都有什么 inequalityinvolvingb

Theinequalitiesin(1)areb

≥0,b

≥,

ifthegoalistomaximiseb

,thebestchoiceis

=1,b

=0,soNTUmax(c)=ther

hand,ifthegoalistominimiseb

,oneshouldset

=0,b

=1,soNTUmin(c)=1.

saninstanceoftheshortest-pathprob-

lemforwhichwehaveTUmax(c)/NTUmax(c)≥2.

,edge

costsbec

=0,c

=1,c

isthelexicographically-leastcheapestpath,sowecanassumethat

S={AB,BC,CD}.Theinequalitiesin(2)arethesameasin

thepreviousexample,andbythesameargumentbothofthemare,

infact,qualitiesin(1)areb

≥0,b

≥1,

≥listomaximiseb

.Ifwehave

torespecttheinequalitiesin(1),wehavetosetb

=0,

=1,soNTUmax(c)=ise,wecansetb

=1,b

=0,soTUmax(c)≥2.

saninstanceoftheshortest-pathprob-

lemforwhichwehaveNTUmin(c)/TUmin(c)≥2.

nstructionisalsobasedonthegraphofFigure1.

Theedgecostsarec

=1,c

=0,c

thelexicographicallyleastcheapestpath,sowecan

assumethatS={AB,BC,CD}.Again,theinequalitiesin(2)

arethesame,andbothare,infact,qualitiesin(1)

areb

≥1,b

≥0,b

≥listominimiseb

.Ifwehavetorespecttheinequalitiesin(1),wehaveto

setb

=1,b

=0,soNTUmin(c)=ise,

wecansetb

=0,b

=1,soTUmin(c)≤1.

InSection4.4(Theorem3),weshowthattheseparationresults

inPropositions2,3,and4areoptimal.

4.2Connectionsbetweenseparationresults

Theseparationresultsforpathauctionsareobtainedonthesame

soutthatthisisnot

,wecanprovethefollowingtheorem.

setsystem(E,F),andanyfeasiblesetS,

max

TUmax(c,S)

NTUmin(c,S)

max

NTUmax(c,S)

TUmin(c,S)

wherethemaximumisoverallcostvectorscforwhichSisa

cheapestfeasibleset.

Theproofofthetheoremfollowsdirectlyfromthefourlemmas

provedbelow;moreprecisely,theﬁrstequalityinTheorem1is

obtainedbycombiningLemmas1and2,andthesecondequalityis

eLemma1here;

theproofsofLemmas2–4aresimilarandcanbefoundinthefull

versionofthispaper[8].

ethatcisacostvectorfor(E,F)suchthat

SisacheapestfeasiblesetandTUmax(c,S)/NTUmax(c,S)=

.Thenthereisacostvectorc′suchthatSisacheapestfeasible

setandNTUmax(c′,S)/NTUmin(c′,S)≥.

ethatTUmax(c,S)=XandNTUmax(c,S)=

YwhereX/Y=.AssumewithoutlossofgeneralitythatS

consistsofelements1,...,k,andletb1=(b1

,...,b1

)andb2=

(b2

,...,b2

)bethebidvectorsthatcorrespondtoTUmax(c,S)

andNTUmax(c,S),respectively.

Constructthecostvectorc′bysettingc′

fori∈S,

c′

=min{c

,b1

}fori∈y,Sisacheapestsetunderc′.

Moreover,asthecostsofelementsoutsideofSremainedthesame,

theright-handsidesofallconstraintsin(2)didnotchange,soany

bidvectorthatsatisﬁes(2)and(3)withrespecttoc,alsosatisﬁes

themwithrespecttoc′.Wewillconstructtwobidvectorsb3and

b4thatsatisfyconditions(雪人图片 1),(2),and(3)forthecostvectorc′,and

Figure2:Graphthatseparatespaymentboundsforvertex

cover,n=7

havePi∈S

=X,Pi∈S

=ax(c′,S)≥X

andNTUmin(c′,S)≤Y,thisimpliesthelemma.

Wecansetb3

=b1

:thisbidvectorsatisﬁesconditions(2)

and(3)sinceb1does,andwehaveb1

≥min{c

,b1

}=c′

whichmeansthatb3satisﬁescondition(1).Furthermore,wecan

setb4

=b2

.Again,b4satisﬁesconditions(2)and(3)sinceb2

does,andsinceb2satisﬁescondition(1),wehaveb2

≥c

≥c′

whichmeansthatb4satisﬁescondition(1).

ecisacostvectorfor(E,F)suchthatSis

acheapestfeasiblesetandNTUmax(c,S)/NTUmin(c,S)=.

Thenthereisacostvectorc′suchthatSisacheapestfeasibleset

andTUmax(c′,S)/NTUmax(c′,S)≥.

ethatcisacostvectorfor(E,F)suchthat

SisacheapestfeasiblesetandNTUmax(c,S)/红军故事《马背上的小红军》 NTUmin(c,S)=

.Thenthereisacostvectorc′suchthatSisacheapestfeasible

setandNTUmin(c′,S)/TUmin(c′,S)≥.

ethatcisacostvectorfor(E,F)suchthat

SisacheapestfeasiblesetandNTUmin(c,S)/TUmin(c,S)=

.Thenthereisacostvectorc′suchthatSisacheapestfeasible

setandNTUmax(c′,S)/NTUmin(c′,S)≥.

4.3Vertex-coverauctions

Incontrasttothecaseofpathauctions,forvertex-coverauc-

tionsthegapbetweenNTUmin(c)andNTUmax(c)(andhence

betweenNTUmax(c)andTUmax(c),andbetweenTUmin(c)

andNTUmin(c))canbeproportionaltothesizeofthegraph.

n≥3,thereisaann-vertexgraph

andacostvectorcforwhichTUmax(c)/NTUmax(c)≥n−2.

erlyinggraphconsistsofan(n−1)-cliqueon

theverticesX

,...,X

n−1

,andanextravertexX

adjacentto

n−1

.Thecostsarec

==c

n−2

=0,c

n−1

=ssumethatS={X

,...,X

n−2

}(this

isthelexicographicallyﬁrstvertexcoverofcost1).Forthisset

system,theconstraintsin(2)areb

≤c

n−1

=1for

i=1,...,n−y,wecansatisfyconditions(2)and(3)

bysettingb

=1fori=1,...,n−2,b

TUmax(c)≥n−max(c),thereisanadditional

constraintb

≥1,sothebestwecandoistosetb

=0for

i=1,...,n−2,b

=1,whichimpliesNTUmax(c)=1.

CombiningProposition5withLemmas1and3,wederivethe

followingcorollaries.

n≥3,wecanconstructaninstance

ofthevertexcoverproblemonagraphofsizenthatsatisﬁes

NTUmax(c)/NTUmin(c)≥n−2.

n≥3,wecanconstructaninstance

ofthevertexcoverproblemonagraphofsizenthatsatisﬁes

NTUmin(c)/TUmin(c)≥n−2.

j+2

j+1

j+2

j+1

j+2

j+1

Figure3:ProofofTheorem3:constraintsfor

and

j+2

notoverlap

4.4Upperbounds

Itturnsoutthatthelowerboundprovedintheprevioussubsec-

ecisely,thefollowingtheoremshows

thatnotwopaymentboundscandifferbymorethanafactorofn;

moreover,thisisthecasenotjustforthevertexcoverproblem,but

dthegapbetweenTUmax(c)and

TUmin(c).SinceTUmin(c)≤NTUmin(c)≤NTUmax(c)≤

TUmax(c),thisboundappliestoanypairofpaymentbounds.

setsystem(E,F)andanycostvectorc,

wehaveTUmax(c)/TUmin(c)≤n.

wlogthatthewinningsetSconsistsofele-

ments1,...,

,...,c

bethetruecostsofelementsinS,

letb′

,...,b′

betheirbidsthatcorrespondtoTUmin(c),andlet

b′′

,...,b′′

betheirbidsthatcorrespondtoTUmax(c).

Considertheconditions(2)and(3)pickasubset

Lofatmostkinequalitiesin(2)sothatforeachi=1,..关于励志的名言 .,kthere

isatleastoneinequalityinLthatistightforb′

.Supposethatthe

jthinequalityinLisoftheformb

++b

≤c(T

S).For

b′

,allinequalitiesinLare,infact,,byadding

upallofthemweobtainkPi=1,...,k

b′

≥Pj=1,...,k

c(T

S).

Ontheotherhand,alltheseinequalitiesappearincondition(2),so

theymustholdforb′′

,i.e.,Pi=1,...,k

b′′

≤Pj=1,...,k

c(T

S).

Combiningthesetwoinequalities,weobtain

nTUmin(c)≥kTUmin(c)≥TUmax(c).

ﬁnallineoftheproofofTheorem2shows

that,infact,theupperboundonTUmax(c)/TUmin(c)canbe

strengthenedtothesizeofthewinningset,atinProposi-

tion5,aswellasinCorollaries1and2,k=n−1,sotheseresults

donotcontradicteachother.

Forpathauctions,thisupperboundcanbeimprovedto2,match-

ingthelowerboundsofSection4.1.

instanceoftheshortestpathproblem,

TUmax(c)≤2TUmin(c).

network(G,s,t),assumewithoutlossofgen-

eralitythatthelexicographically-leastcheapests–tpath,P,inG

is{e

,...,e

},wheree

=(s,v

),e

=(v

),...,e

k−1

,t).Letc

,...,c

bethetruecostsofe

,...,e

,andlet

b′=(b′

,...,b′

)andb′′=(b′′

,...,b′′

)bebidvectorsthatcor-

respondtoTUmin(c)andTUmax(c),respectively.

Foranyi=1,...,k,thereisaconstraintin(2)thatistightfor

b′

withrespecttothebidvectorb′,i.e.,ans–tpathP

thatavoids

andsatisﬁesb′(PP

)=c(P

P).Wecanassumewithoutloss

ofgeneralitythatP

coincideswithPuptosomevertexx

,then

deviatesfromPtoavoide

,andﬁnallyreturnstoPatavertex

andcoincideswithPfromthenon(clearly,itmighthappen

thats=x

ort=y

).Indeed,ifP

deviatesfromPmorethan

once,oneofthesedeviationsisnotnecessarytoavoide

andcan

bereplacedwiththerespectivesegmentofPwithoutincreasingthe

costofP

.Amongallpathsofthisform,let

betheonewiththe

largestvalueofy

,i.e.,the“rightmost”thcorresponds

toaninequalityI

oftheformb′

++b′

≤c(

P).

AsintheproofofTheorem2,weconstructasetoftightcon-

straintsLsuchthateveryvariableb′

appearsinatleastoneofthese

constraints;however,nowwehavetobemorecarefulaboutthe

tructLinductivelyasfollows.

StartbysettingL={I

}.Atthejthstep,supposethatallvari-

ablesupto(butnotincluding)b′

appearinatleastoneinequality

toL.

Notethatforanyjwehavey

j+1

.Thisisbecausethe

inequalitiesaddedtoLduringtheﬁrstjstepsdidnotcoverb′

j+1

j+2

j+1

,wemustalsohavex

j+2

:otherwise,

j+1

wouldnotbethe“rightmost”constraintfor

b′

j+1

.Therefore,thevariablesinI

j+2

andI

donotoverlap,and

hencenob′

canappearinmorethantwoinequalitiesinL.

NowwefollowtheargumentoftheproofofTheorem2toﬁnish.

Byaddingupallofthe(tight)inequalitiesinLforb′

weobtain

2Pi=1,...,k

b′

≥Pj=1,...,k

P).Ontheotherhand,all

theseinequalitiesappearincondition(2),sotheymustholdfor

b′′

,i.e.,Pi=1,...,k

b′′

≤Pj=1,...,k

P),soTUmax(c)≤

2TUmin(c).

ULMECHANISMSFORVER-

TEXCOVER

Recallthatforavertex-coverauctiononagraphG=(V,E),an

allocationruleisanalgorithmthattakesasinputabidb

foreach

vertexandreturnsavertexcover

ainedinSec-

tion2,wecancombineamonotoneallocationrulewiththreshold

paymentstoobtainatruthfulauction.

TwonaturalexamplesofmonotoneallocationrulesareA

opt

,i.e.,

thealgorithmthatﬁndsanoptimalvertexcover,andthegreedy

algorithmA

.However,A

opt

cannotbeguaranteedtorunin

polynomialtimeunlessP=NPandA

hasapproximation

ratiooflogn.

Anotherapproximationalgorithmforvertexcover,whichhasap-

proximationratio2,isthelocalratioalgorithmA

[2,3].This

nedge

e=(u,v),itcomputes=min{b

}andsetsb

−,

−.Afteralledgeshavebeenprocessed,A

returns

thesetofvertices{v|b

=0}.Itisnothardtocheckthatif

theorderinwhichtheedgesareconsideredisindependentofthe

bids,,wecanuseit

toconstru藏头诗自动生成器 ctatruthfulauctionthatisguaranteedtoselectavertex

coverwhosecostiswithinafactorof2fromtheoptimal.

However,whilethequalityofthesolutionproducedbyA

muchbetterthanthatofA

,westillneedtoshowthatitstotal

extsubsection,weboundthefru-

galityratioofA

(and,moregenerally,allalgorithmsthatsatisfy

theconditionoflocaloptimality,deﬁnedlater)by2∆,where∆is

proveamatchinglowerbound

showingthatforsomegraphsthefrugalityratioofanytruthfulauc-

tionisatleast∆/2.

5.1Upperbound

Wesaythatanallocationruleislocallyoptimalifwheneverb

>Pw∼v

,atforanysuchrule

thethresholdbidofvsatisﬁest

≤Pw∼v

orithmsA

opt

,andA

arelocally

optimal.

texcoverauctionMthathasalocally

optimalandmonotoneallocationruleandpayseachagenthis

thresholdbidhasfrugalityratio

NTUmin

(M)≤2∆.

ToproveTheorem4,weﬁrstshowthatthetotalpaymentof

anylocallyoptimalmechanismdoesnotexceed∆c(V).Wethen

demonstratethatNTUmin(c)≥c(V)/iningthese

tworesults,thetheoremfollows.

eragraphG=(V,E)withmaximumde-

gree∆.LetMbeavertex-coverauctiononGthatsatisﬁesthe

ranycostvectorc,thetotalpay-

mentofMsatisﬁesp

(c)≤∆c(V).

otethatanysuchauctionistruthful,sowecan

assumethateachagent’

Sbethe

localoptimality

(c)=X

v∈

≤X

v∈

w∼v

≤X

w∈V

∆c

=∆c(V).

WenowderivealowerboundonTUmax(c);whilenotessential

fortheproofofTheorem4,ithelpsusbuildtheintuitionnecessary

forthatproof.

rtexcoverinstanceG=(V,E)inwhichS

isaminimumvertexcover,TUmax(c,S)≥c(VS)

rtexwwithatleastoneneighbourinS,let

d(w)er

thebidvectorbinwhich,foreachv∈S,b

=Pw∼v,w∈S

S∩

d(w)

andsincealledgesbetweenTandSgotoS∩T,theright-

hand-sideisequalto

c(TS)+X

w∈T

=c(TS)+c(T)=c(VS)=b(S).

Next,weprovealowerboundonNTUmax(c,S);wewillthen

useittoobtainalowerboundonNTUmin(c).

rtexcoverinstanceG=(V,E)inwhichS

isaminimumvertexcover,NTUmax(c,S)≥c(VS)

(S)≥c(VS),bycondition(1)wearedone.

Therefore,fortherestoftheproofweassumethatc(S)

S).Weshowhowtoconstructabidvector(b

)

e∈S

thatsatisﬁes

conditions(1)and(2)suchthatb(S)≥c(VS);clearly,this

impliesNTUmax(c,S)≥c(VS).

Recallthatanetworkﬂowproblemisdescribedbyadirected

graph=(V

),asourcenodes∈V

,asinknodet∈

,andavectorofcapacityconstraintsa

,e∈E

.Considera

network(V

)suchthatV

=V∪{s,t},E

∪E

whereE

={(s,v)|v∈S},E

={(v,w)|v∈S,w∈

VS,(v,w)∈E},E

={(w,t)|w∈VS}.SinceSis

avertexcoverforG,noedgeofEcanhavebothofitsendpoints

inVS,andbyconstruction,E

containsnoedgeswithboth

ore,thegraph(V,E

)isbipartitewithparts

(S,VS).

Setthecapacityconstraintsfore∈E

asfollows:a

(s,v)

(w,t)

(v,w)

=+∞forallv∈S,w∈VS.

RecallthatacutisapartitionoftheverticesinV

intotwosets

andC

sothats∈C

,t∈C

;wedenotesuchacutby

C=(C

).Abusingnotation,wewritee=(u,v)∈Cif

u∈C

,v∈C

oru∈C

,v∈C

,andsaythatsuchanedge

e=(u,v)acityof白居易的诗300首 acutCiscomputed

ascap(C)=P(v,w)∈C

(v,w)

.Wehavecap(s,V∪{t})=c(S),

cap({s}∪V,t)=c(VS).

LetC

min

=({s}∪S′∪W′,{t}∪S′′∪W′′)beaminimum

cutin,whereS′,S′′⊆S,W′,W′′⊆

cap(C

min

)≤cap(s,V∪{t})=c(S)<+∞,andanyedgein

hasinﬁnitecapacity,noedge(u,v)∈E

crossesC

min

Considerthenetwork′=(V

′,E

′),whereV

′={s}∪

S′∪W′∪{t},E

′={(u,v)∈E

|u,v∈V

′}.Clearly,

C′=({s}∪S′∪W′,{t})isaminimumcutin′(otherwise,

therewouldexistasmallercutfor).Ascap(C′)=c(W′),we

havec(S′)≥c(W′).

Now,considerthenetwork′′=(V

′′,E

′′),whereV

′′=

{s}∪S′′∪W′′∪{t},E

′′={(u,v)∈E

|u,v∈V

′′}.

Similarly,C′′=({s},S′′∪W′′∪{t})isaminimumcutin′′,

cap(C′′)=c(S′′).Asthesizeofamaximumﬂowfromsto

tisequaltothecapacityofaminimumcutseparatingsandt,

thereexistsaﬂowF=(f

)

e∈E

′′

ofsizec(S′′).Thisﬂowhas

tosaturatealledgesbetweensandS′′,i.e.,f

(s,v)

forall

v∈S′′.Now,increasethecapacitiesofalledgesbetweensand

S′′to+∞.Inthemodiﬁednetwork,thecapacityofaminimumcut

(andhencethesizeofamaximumﬂow)isc(W′′),andamaximum

ﬂowF′=(f′

)

e∈E

′′

canbeconstructedbygreedilyaugmenting

Setb

forallv∈S′,b

=f′

(s,v)

forallv∈S′′.AsF′is

constructedbyaugmentingF,wehaveb

≥c

forallv∈,

condition(1)issatisﬁed.

Now,letuscheckthatnovertexcoverT⊆Vcanviolatecon-

dition(2).SetT

=T∩S′,T

=T∩S′′,T

=T∩W′,

=T∩W′′;ourgoalistoshowthatb(S′T

)+b(S′′T

)≤

c(T

)+c(T

).Consideralledges(u,v)∈Esuchthatu∈S′T

If(u,v)∈E

thenv∈T

(noedgeinE

cancrossthecut),andif

u,v∈Sthenv∈T

∪T

.Hence,T

∪T

∪S′′isavertexcoverfor

G,andthereforec(T

)+c(T

)+c(S′′)≥c(S)=c(T

)+c(S′

)+c(S′′).Consequently,c(T

)≥c(S′T

)=b(S′T

Now,considertheverticesinS′′T

.AnyedgeinE

thatstartsin

oneoftheseverticeshastoendinT

(thisedgehastobecoveredby

T,anditcannotgoacrossthecut).Therefore,thetotalﬂowoutof

S′′T

isatmostthetotalﬂowoutofT

,i.e.,b(S′′T

)≤c(T

Hence,b(S′T

)+b(S′′T

)≤c(T

)+c(T

Finally,wederivealowerboundonthepaymentboundthatis

ofinteresttous,namely,NTUmin(c).

rtexcoverinstanceG=(V,E)inwhichS

isaminimumvertexcover,NTUmin(c,S)≥c(VS)

eforcontradictionthatcisacostvectorwith

minimum-costvertexcoverSandNTUmin(c,S)

bbethecorrespondingbidvectorandletc′beanewcostvector

withc′

forv∈Sandc′

forv∈ion(2)

guaranteesthatSisanoptimalsolutiontothecostvectorc′.Now

computeabidvectorb′correspondingtoNTUmax(c′,S).We

S’

W’’

S’’

W’

0000000

1111111

0000

1111

000

111

000000

111111

00000000

11111111

0000000

1111111

0000

1111

111刘禹锡描写黄河的诗句 1

1111

1割席断交告诉我们什么道理 1

000

111

000000

111111

000000

111111

000

111

Figure4:linescorrespondtoedges

inEE

claimthatb′

=c′

foranyv∈,supposethatb′

>c′

forsomev∈S(b′

=c′

forv∈Sbyconstruction).Asbsatisﬁes

conditions(1)–(3),amongtheinequalitiesin(2)thereisonethatis

,b(ST)=c(TS).By

theconstructionofc′,c′(ST)=c′(TS).Nowsinceb′

≥c′

forallw∈S,b′

>c′

impliesb′(ST)>c′(ST)=c′(TS).

Butthisviolates(2).Sowenowknowb′=c′.Hence,wehave

NTUmax(c′,S)=Pv∈S

=NTUmin(c,S)

givingacontradictiontothefactthatNTUmax(c′,S)≥c′(VS)

whichweprovedinLemma7.

AsNTUmin(c,S)satisﬁescondition(1),itfollowsthatwe

haveNTUmin(c,S)≥c(S).TogetherwillLemma8,thisimplies

NTUmin(c,S)≥max{c(VS),c(S)}≥c(V)/ed

withLemma5,thiscompletestheproofofTheorem4.

in(c)≤NTUmax(c)≤TUmax(c),

ourboundof2∆extendstothesmallerfrugalityratiosthatwecon-

NTUmax

(M)and

TUmax

(M).Itisnotclearwhether

itextendstothelargerfrugalityratio

TUmin

(M).However,the

frugalityratio

TUmin

(M)isnotrealisticbecausethepayment

boundTUmin(c)isinappropriatelylow–weshowinSection6

thatTUmin(c)canbesigniﬁcantlysmallerthanthetotalcostofa

cheapestvertexcover.

Extensions

Wecanalsoapplyourresultstomonotonevertex-coveralgorithms

wesimplytakethevertexcoverproducedbyanysuchalgorithm

andtransformitintoalocally-optimalone,consideringthevertices

inlexicographicorderandreplacingavertexvwithitsneighbours

wheneverb

>Pu∼v

.Notethatifavertexuhasbeenaddedto

thevertexcoverduringthisprocess,itmeansthatithasaneighbour

whosebidishigherthanb

,soafteronepassallverticesinthever-

texcoversatisfyb

≤Pu∼v

.Thisprocedureismonotonein

bids,-

fore,usingitontopofamonotoneallocationrulewithapprox-

imationratio,weobtainamonotonelocally-optimalallocation

rulewithapproximationratio.Combiningitwiththresholdpay-

ments,wegetanauctionwith

NTUmin

≤2∆.Sinceanytruthful

auctionhasamonotoneallocationrule,thisproceduretransforms

anytruthfulmechanismforthevertex-coverproblemintoafrugal

onewhilepreservingtheapproximationratio.

5.2Lowerbound

Inthissubsection,weprovethattheupperboundofTheorem4

ofusesthetechniquesof[9],where

theauthorsproveasimilarresultforshortest-pathauctions.

∆>0andanyn,thereexistagraphG

ofmaximumdegree∆andsizeN>nsuchthatforanytruthful

mechanismMonGwehave

NTUmin

(M)≥∆/2.

and∆,setk=⌈n/2∆⌉.LetGbethegraph

thatconsistsofkblocksB

,...,B

ofsize2∆each,whereeach

isacompletebipartitegraphwithpartsL

andR

,|L

|=∆.

costvectorx∈X,eachblockB

hasonevertexofcost1;all

costvectory∈Y,thereisoneblock

thathastwoverticesofcost1,oneineachpart,allotherblocks

haveonevertexofcost1,y,

|X|=(2∆)k,|Y|=k(2∆)k−1∆nowconstructa

bipartitegraphWwiththevertexsetX∪Yasfollows.

Consideracostvectory∈Ythathastwoverticesofcost1in

;lettheseverticesbev

∈L

andv

∈R

.Bychangingthe

costofeitheroftheseverticesto0,weobtainacostvectorinX.

Letx

andx

bethecostvectorsobtainedbychangingthecostof

andv

,texcoverchosenbyM(y)must

eithercontainallverticesinL

oritmustcontainallverticesinR

Intheformercase,weputinWanedgefromytox

andinthe

lattercaseweputinWanedgefromytox

(ifthevertexcover

includesallofB

,Wcontainsbothoftheseedges).

ThegraphWhasatleastk(2∆)k−1∆2edges,sotheremust

existanx∈Xofdegreeatleastk∆/

,...,y

k∆/2

theotherendpointsoftheedgesincidenttox,andforeachi=

1,...,k∆/2,letv

bethevertexwhosecostisdifferentunderx

andy

;notethatallv

aredistinct.

ItisnothardtoseethatNTUmin(x)≤k:thecheapestvertex

covercontainstheall-0partofeachblock,andwecansatisfycon-

ditions(1)–(3)bylettingoneoftheverticesintheall-0partofeach

blocktobid1,whileallothertheverticesinthecheapestsetbid0.

Ontheotherhand,bymonotonicityofMwehavev

∈M(x)

fori=1,...,k∆/2(v

isinthewinningsetundery

,andxis

obtainedfromy

bydecreasingthecostofv

),andmoreover,the

thresholdbidofeachv

isatleast1,sothetotalpaymentofMonx

isatleastk∆/,

NTUmin

(M)≥M(x)/NTUmin(x)≥

∆/2.

erboundofTheorem5canbegeneralised

torandomisedmechanisms,wherearandomisedmechanismiscon-

sideredtobetruthfulifitcanberepresentedasaprobabilitydistri-

case,insteadofchoosing

thevertexx∈Xwiththehighestdegree,weputboth(y,x

)

and(y,x

)intoW,labeleachedgewiththeprobabilitythatthe

respectivepartoftheblockischosen,andpickx∈Xwiththe

umentcanbefurtherextendedto

amorepermissivedeﬁnitionoftruthfulnessforrandomisedmech-

anisms,butthisdiscussionisbeyondthescopeofthispaper.

TIESOFPAYMENTBOUNDS

Inthissectionweconsiderseveraldesirablepropertiesofpay-

mentboundsandevaluatethefourpaymentboundsproposedin

ticularpropertiesthatwe

areinterestedinareindependenceofthechoiceofS(Section6.3),

monotonicity(Section6.4.1),computationalhardness(Section6.4.2),

andtherelationshipwithotherreasonablebounds,suchasthetotal

costofthecheapestset(Section6.1),orthetotalVCGpayment

(Section6.2).

6.1Comparisonwithtotalcost

Ourﬁrstrequirementisthatapaymentboundshouldnotbeless

tboundsareusedto

terhaveto

,thepaymenttoeachagentmust

beatleastaslargeashisincurredcosts;itisonlyreasonableto

requirethepaymentboundtosatisfythesamerequirement.

Clearly,NTUmax(c)andNTUmin(c)satisfythisrequirement

duetocondition(1),andsodoesTUmax(c),sinceTUmax(c)≥

NTUmax(c).However,TUmin(c)mple

ofProposition4showsthatforpathauctions,TUmin(c)canbe

er,thereareset

systemsandcostvectorsforwhichTUmin(c)issmallerthanthe

costofthecheapestsetSbyafactorofΩ(n).Consider,forex-

ample,thevertex-coverauctionforthegraphofProposition5with

thecostsc

==c

n−2

n−1

=1,c

ofacheapestvertexcoverisn−2,andthelexicographicallyﬁrst

vertexcoverofcostn−2is{X

,...,X

n−2

}.Theconstraints

in(2)areb

≤c

n−1

=y,wecansatisfycon-

ditions(2)and(3)bysettingb

==b

n−2

=0,b

=1,

whichmeansthatTUmin(c)≤servationsuggeststhat

thepaymentboundTUmin(c)istoostrongtoberealistic,sinceit

canbesubstantiallylowerthanthecostofthecheapestfeasibleset.

Nevertheless,someofthepositiveresultsthatwereprovedin[16]

forNTUmin(c)gothroughforTUmin(c)icular,

onecanshowthatifthefeasiblesetsarethebasesofamonopoly-

freematroid,then

TUmin

(VCG)=that

TUmin

(VCG)

isatmost1,onemustprovethattheVCGpaymentisatmost

TUmin(c).ThisisshownforNTUmin(c)intheﬁrstparagraph

oftheproofofTheorem5in[16].Theirargumentdoesnotusecon-

dition(1)atall,soitalsoappliestoTUmin(c).Ontheotherhand,

TUmin

(VCG)≥1since

TUmin

(VCG)≥

NTUmin

(VCG)

and

NTUmin

(VCG)≥1byProposition7of[16](andalsoby

Proposition6below).

6.2ComparisonwithVCGpayments

Anothermeasureofsuitabilityforpaymentboundsisthatthey

shouldnotresultinfrugalityratiosthatarelessthen1forwell-

isindeedthecase,thepayment

boundmaybetooweak,asitbecomestooeasytodesignmecha-

icular,areasonable

requirementisthatapaymentboundshouldnotexceedthetotal

paymentoftheclassicalVCGmechanism.

ThefollowingpropositionshowsthatNTUmax(c),andthere-

forealsoNTUmin(c)andTUmin(c),donotexceedtheVCG

paymentp

VCG

(c).Theproofessentiallyfollowstheargumentof

Proposition7of[16]andcanbefoundinthefullversionofthis

paper[8].

PROPOSITION6.

NTUmax

(VCG)≥1.

Proposition6showsthatnoneofthepaymentboundsTUmin(c),

NTUmin(c)andNTUmax(c)-

ever,thepaymentboundTUmax(c)canbelargerthatthetotal

icular,fortheinstanceinProposition5,the

VCGpaymentissmallerthanTUmax(c)byafactorofn−

havealreadyseenthatTUmax(c)≥n−therhand,

underVCG,thethresholdbidofanyX

,i=1,...,n−2,is0:

ifanysuchvertexbidsabove0,itisdeletedfromthewinningset

togetherwithX

andreplacedwithX

n−1

.Similarly,thethreshold

bidofX

is1,becauseifX

bidsabove1,itcanbereplacedwith

n−1

.SotheVCGpaymentis1.

Thisresultisnotsurprising:thedeﬁnitionofTUmax(c)im-

plicitlyassumesthereisco-operationbetweentheagents,while

thecomputationofVCGpaymentsdoesnottakeintoaccountany

,co-operationenablestheagents

,VCGisnotgroup-

ggeststhatasapaymentbound,TUmax(c)

maybetooliberal,atleastinacontextwherethereislittleor

sTUmax(c)canbea

goodbenchmarkformeasuringtheperformanceofmechanismsde-

signedforagentsthatcanformcoalitionsormakesidepayments

toeachother,inparticular,group-strategy茄子的拼音 proofmechanisms.

Anothersettinginwhichbounding

TUmax

isstillofsomein-

terestiswhen,fortheunderlyingproblem,theoptimalallocation

case,ﬁnding

apolynomial-timecomputablemechanismwithgoodfrugalityra-

tiowithrespecttoTUmax(c)isanon-trivialtask,whilebounding

thefrugalityratiowithrespecttomorechallengingpaymentbounds

couldbetoodifﬁstratethispoint,comparetheproofs

ofLemma6andLemma7:bothrequiresomeeffort,butthelatter

ismuchmoredifﬁcultthantheformer.

6.3ThechoiceofS

Allpaymentboundsdeﬁnedinthispapercorrespondtothetotal

bidofallelementsinthecheapestfeasibleset,wheretiesarebro-

hisdeﬁnitionensuresthatourpay-

mentboundsarewell-deﬁned,theparticularchoiceofthedraw-

resolutionruleappearsarbitrary,andonemightwonderifourpay-

mentboundsaresufﬁcientlyrobusttobeindependentofthischoice.

ItturnsoutthatisindeedthecaseforNTUmin(c)andNTUmax(c),

seethis,supposethattwofeasiblesetsS

andS

havethesame

omputationofNTUmin(c,S

),allverticesinS

wouldhavetobidtheirtruecost,sinceotherwiseS

wouldbe-

comecheaperthanS

.Hence,anyb山水田园诗句100首 idvectorforS

canonlyhave

fore∈S

∩S

,andhenceconstitutesavalidbidvector

forS

arargumentappliestoNTUmax(c).

However,forTUmin(c)andTUmax(c)thisisnotthecase.

Forexample,considerthesetsystem

E={e

F={S

={e

},S

={e

},S

={e

}}

withthecostsc

=2,c

=1,c

=apest

setsareS

andS

.NowTUmax(c,S

)≤4,asthetotalbidof

theelementsinS

cannotexceedthetotalcostofS

.Ontheother

hand,TUmax(c,S

)≥5,aswecansetb

=3,b

=0,b

=2.

Similarly,TUmin(c,S

)=4,becausetheinequalitiesin(2)are

≤2andb

≤in(c,S

)≤3aswecanset

=1,b

=2,b

=0.

6.4NegativeresultsforNTUmin(c)andTUmin(c)

Theresultsin[16]andourvertexcoverresultsareprovedforthe

frugalityratio

NTUmin

.Indeed,itcanbearguedthat

NTUmin

the“best”deﬁnitionoffrugalityratio,becauseamongallreason-

,onesthatareatleastaslargeasthecost

ofthecheapestfeasibleset),itismostdemandingofthealgorithm.

However,NTUmin(c)isnotalwaystheeasiestorthemostnatural

subsection,wediscussseveral

disadvantagesofNTUmin(c)(andalsoTUmin(c))ascompared

toNTUmax(c)andTUmax(c).

6.4.1Nonmonotonicity

TheﬁrstproblemwithNTUmin(c)isthatitisnotmonotone

,itmayincreasewhenoneaddsafeasible

settoF.(Itis,however,monotoneinthesensethatalosingagent

cannotbecomeawinnerbyraisinghiscost.)Intuitively,agood

paymentboundshouldsatisfythismonotonicityrequirement,as

addingafeasiblesetincreasesthecompetition,soitshoulddrive

atthisindeedthecaseforNTUmax(c)

andTUmax(c)sinceanewfeasiblesetaddsaconstraintin(2),

thuslimitingthesolutionspacefortherespectivelinearprogram.

afeasiblesettoFcanincreasethe

valueofNTUmin(c)byafactorofΩ(n).

={x,xx,y

,...,y

,...,z

}.SetY=

,...,y

},S=Y∪{x},T

=Y{y

}∪{z

},i=1,...,n,

andsupposethatF={S,T

,...,T

}.Thecostsarec

=0,

=0,c

=1fori=1,...,atSis

′=F∪{T

},whereT

=Y∪

{xx}.ForF,thebidvectorb

==b

=0,b

satisﬁes(1),(2),and(3),soNTUmin(c)≤′,Sisstill

imalsolutionhas

=0(byconstraintin(2)withT

).Condition(3)fory

implies

=1,sob

=1andNTUmin(c)=n.

Forpathauctions,ithasbeenshown[18]thatNTUmin(c)is

,withrespectto

addinganewedge(agent)ratherthananewfeasibleset(ateam

ofexistingagents).

lsoshowthatNTUmin(c)isnon-monotone

case,addinganewfeasiblesetcorresponds

soutthatdeletingasingle

edgecanincreaseNTUmin(c)byafactorofn−2;theconstruc-

tionissimilartothatofProposition5.

6.4.2NP-Hardness

AnotherproblemwithNTUmin(c,S)isthatitisNP-hardto

computeevenifthenumberoffeasiblesetsispolynomialinn.

Again,thisputsitatadisadvantagecomparedtoNTUmax(c,S)

andTUmax(c,S)(seeRemark1).

ingNTUmin(c)isNP-hard,evenwhen

thelexicographically-leastfeasiblesetSisgivenintheinput.

ceEXACTCOVERBY3-SETS(X3C)toourprob-

anceofX3CisgivenbyauniverseG={g

,...,g

}

andacollectionofsubsetsC

,...,C

⊂G,|C

|=3,where

thegoalistodecidewhetheronecancoverGbyn/3ofthesesets.

Observethatifthisisindeedthecase,eachelementofGiscon-

tainedinexactlyonesetofthecover.

eraminimisationproblemPofthefollowing

form:MinimisePi=1,...,n

underconditions(1)b

≥0forall

i=1,...,n;(2)foranyj=1,...,kwehavePb

∈S

≤a

whereS

⊆{b

,...,b

};(3)foreachb

,oneoftheconstraints

in(2)suchP,onecanconstructa

setsystemSandavectorofcostscsuchthatNTUmin(c)isthe

optimalsolutiontoP.

structionisstraightforward:thereisanelement

ofcost0foreachb

,anelementofcosta

foreacha

,thefeasible

solutionsare{b

,...,b

},oranysetobtainedfrom{b

,...,b

}

byreplacingtheelementsinS

bya

Bythislemma,allwehavetodotoproveTheorem6istoshow

howtosolveX3Cbyusingthesolutiontoaminimisationproblem

,weintroduce4variablesx

,andb

.Also,foreach

elementg

ofGthereisavariabled

.Weusethefollowingsetof

constraints:

•In(1),wehaveconstraintsx

≥0,x

≥0,a

≥0,b

≥0,

≥0foralli=1,...,m,j=1,...,n.

•In(2),foralli=1,...,m,wehavethefollowing5con-

straints:x

≤1,x

≤1,

≤,forallj=1,...,nwehaveaconstraint

oftheformx

++x

≤1,whereC

,...,C

arethesetsthatcontaing

Thegoalistominimizez=Pi

)+Pj

Observethatforeachj,thereisonlyoneconstraintinvolving

,sobycondition(3)itmustbetight.

Considerthetwoconstraintsinvolvinga

.Oneofthemmustbe

tight,andthereforex

≥x

≥,for

anyfeasiblesolutionto(1)–(3)wehavez≥,supposethat

=0forj=1,...,,ifC

isincludedinthiscover,setx

=1,x

=0,otherwise

setx

=1,x

=y,allinequalitiesin(2)

aresatisﬁed(weusethefactthateachelementiscoveredexactly

once),andforeachvariable,oneoftheconstraintsinvolvingitis

signmentresultsinz=m.

Conversely,supposethereisafeasiblesolutionwithz=m.

Aseachaddendoftheformx

contributesatleast

1,wehavex

=1foralli,d

=0forallj.

Wewillnowshowthatforeachi,eitherx

=1andx

=0,or

=0andx

=sakeofcontradiction,supposethat

=<1,x

=′

mustbetight,wehavea

≥min{1−,1−′}.Similarly,

≥min{1−,1−′}.Hence,x

=1=

+′+2min{1−,1−′}>ﬁnishtheproof,notethatfor

eachj=1,...,mwehavex

++x

=1andd

=0,

sothesubsetsthatcorrespondtox

=1constituteasetcover.

roofsofProposition7andTheorem6all

constraintsin(1)areoftheformb

≥,thesameresults

aretrueforTUmin(c).

rtest-pathauctions,thesizeofFcanbe

r,thereisapolynomial-timeseparation

oracleforconstraintsin(2)(toconstructone,useanyalgorithm

forﬁndingshortestpaths),soonecancomputeNTUmax(c)and

TUmax(c)therhand,recentlyand

independentlyitwasshown[18]thatcomputingNTUmin(c)for

shortest-pathauctionsisNP-hard.

NCES

[1],

Proceedingsofthe13thAnnualACM-SIAMSymposiumon

DiscreteAlgorithms,pages991–999,2002

[2]-Yehuda,,,,Local

ratio:Auniﬁ

Memoriam:.,

36(4):422–463,2004

[3],Alocal-ratiotheoremfor

DiscreteMathematics,25:27–46,1985

[4],Choice,

8:17–33,1971

[5]scu,Boundingthepaymentofapproximatetruthful

eedingsofthe15thInternational

SymposiumonAlgorithmsandComputation,pages221–233,

2004

[6],Ontheexpectedpaymentof

eedingsofthe5th

ACMConferenceonElectronicCommerce(EC’04),2004

[7],Truecostsofcheaplaborarehardtomeasure:edge

eedingsofthe

6thACMConferenceonElectronicCommerce(EC’05),2005

[8],rg,rg,Frugality

ratiosandimprovedtruthfulmechanismsforvertexcover.

Availablefrom

/abs/cs/0606044,2006

[9],,itz,Frugalityinpath

eedingsofthe15thAnnualACM-SIAM

SymposiumonDiscreteAlgorithms,pages694–702,2004

[10]baum,mitriou,,and

r,ABGP-basedmechanismforlowest-costrouting.

InProceedingsofthe21stSymposiumonPrinciplesof

DistributedComputing,pages173–182,2002

[11],rg,ne,,Competitive

eedingsofthe34thAnnualACM

SymposiumonTheoryofComputation,pages72–81,2002

[12],,,Coalitional

gamesongraphs:corestructures,

Proceedingsofthe4thACMConferenceonElectronic

Commerce(EC’03),2005

[13]rg,ne,,Competitive

eedingsofthe12thAnnual

ACM-SIAMSymposiumonDiscreteAlgorithms,pages

735–744,2001

[14],etrica,

41(4):617–631,1973

[15]ica,,va,,

eedingsofthe6thACM

ConferenceonElectronicCommerce(EC’05),2005

[16],,,BeyondVCG:

eedingsofthe46th

AnnualIEEESymposiumonFoundationsofComputer

Science,pages615–626,2005

[17],Personalcommunication,2006

[18],,Cheaplaborcanbeexpensive,In

Proceedingsofthe18thAnnualACM-SIAMSymposiumon

DiscreteAlgorithms,pages735–744,2007

[19],

Proceedingsofthe31stAnnualACMSymposiumonTheoryof

Computation,pages129–140,1999

[20]an,Towardsgenericlowpayment

eedings

ofthe7thInternationalIEEEConferenceonE-Commerce

Technology,2005

[21],Thepriceoftruth:frugalityintruthful

eedingsof20thInternationalSymposium

onTheoreticalAspectsofComputerScience,2003

[22]y,Counterspeculation,auctions,andcompetitive

lofFinance,16:8–37,1961

更多推荐

Southampton是什么意思thampton在线翻译读音

Southampton是什么意思thampton在线翻译读音

porta是什么意思ta的用法读音典-之路

发布评论取消回复

最近发表

热门文章

标签列表

Southampton是什么意思thampton在线翻译读音

porta是什么意思ta的用法读音典-之路

相关文章

发布评论取消回复

最近发表

热门文章

标签列表