Abstract

Lower bounds for cost sharing and

group-strategyproof mechanisms

Nicole Immorlica Mohammad Mahdian Vahab S.Mirrokni

Abstract

A cost-sharing scheme is a set of rules de?ning how to share the cost of a service(often computed by solving a combinatorial optimization problem)amongst serviced customers.A cost-sharing scheme is cross-monotonic if it satis?es the property that everyone is better off when the set of people who receive the service expands. In this paper,we develop a novel technique for proving lower bounds on the budget-balance factor of cross-monotonic cost-sharing schemes.We apply this tech-nique to games de?ned based on the problems of edge cover,vertex cover,set cover,metric facility location, maximum?ow,arborescence packing,and maximum matching,and in each case derive tight or nearly-tight lower bounds.In particular,we show that for the fa-cility location game,there is no cross-monotonic cost sharing scheme that recovers more than a third of the to-tal cost.This result together with a recent-budget-balanced cross-monotonic cost-sharing scheme of Pal and Tardos[15]closes the gap for the facility loca-tion game.For the vertex cover and set cover games, we show that no cross-monotonic cost sharing scheme can recover more than a and

Computer Science and Arti?cial Intelligence Lab,MIT,Cambridge, MA02139.Email:nickle,mahdian,mirrokni@https://www.wendangku.net/doc/6e10283998.html,.tivity to a network.The total cost of this service is a function of the group of customers that are serviced:a group of customers in distant towns might incur a larger cost than a group of customers in the same town.The service provider must develop a pricing policy,or cost-sharing scheme,that,given any group of customers, divides the cost of the service amongst them.For ex-ample,one plausible cost-sharing scheme divides the cost of the service evenly amongst the customers.How-ever,in the case of network connectivity,this scheme seems to undercharge distant customers with high con-nection costs and overcharge other customers.De-veloping a fair and economically viable cost-sharing scheme is a central problem in cooperative game the-ory.One commonly explored condition is that of cross-monotonicity[13,14].Intuitively,cross-monotonicity requires that the price charged to any individual in a group decreases as the group expands.Thus customers have an economic incentive to promote the service.

For the important class of services with submodular cost functions,various cross-monotonic cost-sharing schemes were studied by Moulin and Shenker[13]and further by Jain and Vazirani[10].For submodular cost functions,there are cross-monotonic cost-sharing schemes that are budget-balanced,i.e.,the sum of prices charged to the agents covers the full cost of serving them.There are many other interesting classes of cost functions that arise from NP-hard optimization problems.For example,the cost of providing the service for a set of agents could be expressed as the cost of building the cheapest Steiner tree that covers the elements of,or the minimum cost of opening

facilities and connecting each member of to an open facility.In such cases,it is usually impossible for a cross-monotonic cost sharing scheme to be budget-balanced.Moreover,even if a budget-balanced cross-monotonic cost sharing scheme exists,it might be

hard to compute.Therefore,it is natural to consider

cost sharing schemes that are approximately budget

balanced,i.e.,they recover only a fraction of the cost of

the service.Such schemes have been studied by Kent

and Skorin-Kapov[11],Feigenbaum et al.[4],Jain and

Vazirani[8],and Pal and Tardos[15].

The cross-monotonicity of a cost sharing scheme

implies that for every set of agents the cost shares form

an allocation in the core of the game(see Section2for

de?nitions).Therefore,the best budget-balance factor

achievable by a cross-monotonic cost sharing scheme

cannot be better than that of a cost sharing in the core.

This,together with the folklore theorem that the best

budget-balance factor for a cost sharing in the core of

integer covering games is equal to the integrality gap

of the“natural”LP-relaxation of the problem,gives us

lower bounds for the best cross-monotonic cost sharing

scheme for various combinatorial optimization prob-

lems.For example,this argument implies that cross-

monotonic cost sharing schemes for metric facility lo-

cation,vertex cover,and set cover games cannot re-

cover more than a,and

fraction of the total cost,respectively.1Previously,Devanur et

al.[3]give a strategyproof-budget bal-anced cost-sharing mechanism in the core for the set

cover game,but their underlying cost-sharing scheme

is not cross-monotonic.We also apply this technique to

the total cost of servicing.A cost-sharing scheme is a collection of cost allocations for every. More formally,a cost sharing scheme is a function

,such that for every

and every,.Intuitively,we think of as the share of of the total cost if is the set of agents receiving the service.

Ideally,we want cost sharing schemes(and cost allocations)to be budget-balanced,i.e.,for every ,.However,it is not always possible to achieve budget balance in combination with other properties,or even if it is possible,it might be computationally hard to compute the cost shares. Therefore,we relax this notion to the notion of-budget balance(for some),which means that for every,.

In addition to budget balance,we usually require cost allocation and cost sharing schemes to satisfy additional properties.One property that is extensively studied in the cooperative game theory literature is the property of being in the core(see,for example, Bondareva[1]and Shapley[17]),which intuitively says that no subset of users should be overcharged for the service.

D EFINITION1.A cost allocation for a set is in the-core if and only if it is-budget balanced and for every,.A cost sharing scheme is in the-core if and only if for every, is in the-core.

Another property,which was studied by Moulin[14]and Moulin and Shenker[13]in or-der to design group-strategyproof mechanisms(see the de?nition below),and has recently received consider-able attention in the computer science literature(see, for example,[11,10,8,15]),is cross-monotonicity. This property captures the notion that users should not be penalized as the serviced set https://www.wendangku.net/doc/6e10283998.html,ly,

D EFINITION2.A cost sharing scheme is cross-monotone if for all and,

It is a simple exercise to show that every-budget-balanced cross-monotonic cost sharing scheme is in the -core,but the converse need not hold.Therefore, cross-monotonicity is a strictly stronger requirement than being in the core.

The main application of cross-monotonic cost shar-

ing schemes is in the design of cost sharing mecha-

nisms,de?ned in the following setting:Each user

has a willingness to pay for the ser-vice,i.e.,she is willing to pay up to dollars to get

the service.We further assume that the utility(or hap-

piness)of user is given by,where is an

indicator variable which indicates whether she has re-

ceived the service or not,and is the amount she has

to pay2.A cost sharing mechanism(also known as a

social choice function)is an algorithm that elicits a bid

from each agent,and based on these bids,decides which agents should receive the service and how much each of them has to pay.More formally, a cost sharing mechanism is a function that associates to each vector of non-negative bids a set of agents to be serviced,and a vector of non-negative payments.When there is no ambiguity,we write and instead of and,respectively. Throughout this paper,we assume that a mechanism does not charge an agent who does not receive the ser-vice(i.e.,for),does not charge an agent who receives the service more than her bid(i.e., for),and for each agent,there is some bid such that if bids,she will get the service,no mat-ter what others bid3.Furthermore,we would like the mechanisms to be approximately budget balanced.We call a mechanism-budget balanced if the total amount the mechanism charges the agents is between

and(i.e.,).

The main property that we want a mechanism to

satisfy is incentive compatibility.We want our mecha-

nism to encourage participants to submit their true will-

ingness to pay as their bid.Agents should not be able

to bene?t from lying about the prices they are willing

to pay.Ideally,not even a group of users should be

able to bene?t by cooperatively lying,thus discourag-

ing complicated bidding strategies.More precisely,we

look for mechanisms,called group strategyproof mech-

anisms which satisfy the following additional property.

Let be a coalition of users,and be two vectors of non-negative bids satisfying for ev-ery(we think of as the true willingness to pay

of users,and as a vector of strategically chosen bids).

Let and denote the outputs of the mech-anism when the bids are and,respectively.We say that the mechanism is group strategyproof if for every such,if the inequality

holds for all,then it holds with equality for every .In other words,there should not be any coali-tion and vector of bids such that if members of announce instead of(their true willingness to pay) as their bids,then every member of the coalition is at least as happy as in the truthful scenario,and at least one person is happier.

3Lower bounds for cross-monotonic cost sharing schemes

In this section we present the main idea behind our lower bound technique and prove several lower bounds for the games de?ned based on edge cover,vertex cover,and facility location.In Section3.1we explain the technique with a simple example of the edge cover game.Sections3.2and3.3contain the proofs of the lower bounds for the vertex cover and facility location games.Finally,in Section3.4we state(without proof) several other lower bounds that can be proved using our technique.

3.1A simple example:the edge cover game In this section,we explain our technique using the edge cover game as a guiding example.The edge cover cost function is de?ned as follows.

D EFINITION3.Let be a graph with no isolated vertices.The set of agents in the edge cover game on is the set of vertices of.Given a subset of vertices,the cost of is the minimum size of a set of edges such that for every,at least one of the edges incident to is in.Such a set is called an edge cover for.

It is easy to see that for every set,one can obtain a minimum edge cover of by taking a maximum matching on and adding one edge for every vertex that is not covered by the maximum matching(see[2]). Using this fact,we can give a cost-sharing scheme that is in the

,and other vertices

times the edge cover for .Therefore,there is a cost-sharing scheme satisfying the core property with a budget-balance factor of

-core.However,in the following,we show that no cross-monotonic cost-sharing scheme can achieve a budget-balance factor better than

-budget balanced cross-monotonic cost sharing scheme for the edge cover problem.

Here’s the high-level idea of the proof:We assume, for contradiction,that there is a cross-monotonic cost sharing scheme that always recovers at least a

times the size of the minimum edge-cover for.This is done by picking a subset at random from a certain distribution and showing that in expectation,the ratio of the recovered cost to the cost of is low.Therefore, there is a manifestation of for which this ratio is low. In the edge-cover example,we pick one vertex of uniformly at random and let be the union of and the set of vertices adjacent to.We now need to bound the expected value of the sum of cost shares of the elements of.We do this by using cross-monotonicity and bounding the cost share of each vertex by the cost share of in a substructure of.Bounding the expected cost share of in is done by showing that for every substructure,every has the same probability of occurring in a structure in which .This implies that the expected cost share of in(where the expectation is over the choice of)is at most the cost of divided by the number of agents in.Summing up these values for all gives us the desired contradiction.

Proof of Proof of Theorem3.1.Assume that there is a

scheme.Let be the complete bipartite graph,

where will be?xed later,and consider on.For every,we let be the union of and the set of vertices adjacent to(i.e.,vertices of the other part).We pick a set of agents by picking uniformly at random from and letting.By the de?nition of the edge cover problem,

for every(3.1) On the other hand,

(3.2)

where the last inequality follows from the facts that for every vertex and every set,,and that for every and,

.Both of these facts are consequences of the cross-monotonicity of.By the de?nition of expected values,we have

(3.3) where the second expectation is over the choice of from and in.However,choosing a vertex and then a neighbor of at random is equivalent to choosing a random edge in at random, and letting be a random endpoint of and be the other one.By the budget-balance condition,the sum of the cost shares of the endpoints of is at most one. Therefore,for every,if is a random endpoint of and is the other endpoint,

. Therefore,by Equations3.1and3.2,we have

for.Therefore,there is a set satisfying

,which is a contradiction with the assumption that is

for every is cross-monotonic and

fraction of the cost.Similar argument shows that for the general case of the set cover game,no cross-monotonic cost-sharing scheme can recover more than a

B

C

Figure1:The structure in the vertex cover game

Let be a permutation of the vertices.Let be the set of the?rst vertices,be the set of the next vertices,and be the set of the remaining vertices. We denote the’th vertices of and(based on the ordering given by)by and.Let denote the set of all edges between and,union the set of edges for.We pick by picking the permutation uniformly at random and letting. See Figure1for an example.

If we denote the set of edges between and by ,we have

(3.4)

where the?rst inequality follows from the cross-monotonicity of and the second inequality is implied by the budget balance assumption and the fact that the cost of the minimum vertex cover in is.We also let be the set of all edges in that have as an endpoint(see Figure1).Equation3.4and the cross-monotonicity of imply the following.

(3.5)

We now need to analyze the expectation of

over the random choice of.Notice that the only elements of that are important in

are the?rst elements and the’th and

’th elements(and).There-fore,the expectation of over the choice of is equal to the expectation of,

over the random choice of an ordered list of different vertices of.However,in this ex-periment it is clear by symmetry that the expected cost

share of is the same for, and therefore by the budget balance condition each of

these expected cost shares is at most

(3.6)

On the other hand,the size of the minimum vertex cover in is always.Therefore,the expected value of the ratio of to is at most. Thus,there is a set for which this ratio is at most .Taking

-budget-balanced.This matches the budget-balance factor of the scheme given by Pal and Tardos[15].

We start by giving an example on which the scheme of Pal and Tardos[15]recovers only a third of the cost4.

This example will be used as the randomly chosen structure in our proof.The proof of the following lemma is simple and is omitted here.

L EMMA3.1.Let be an instance of the facility lo-

cation problem consisting of cities, and facilities each of opening cost3.For every and,the connection costs between and and between and are all1,and other connection costs are obtained by the triangle inequal-ity.See Figure2(a).Then if and tends to in?nity,the optimal solution for has cost. T HEOREM3.4.Any cross-monotonic cost-sharing scheme for the facility location game is at most -budget balanced.

Proof.Consider the following instance of the facility location problem.There are sets of cities each,where and.For every subset of cities containing exactly one city from each (for all),there is a facility with connection cost to each city in.The remaining connection costs are de?ned by extending the metric, i.e.,the cost of connecting city to facility for

is.The facility opening costs are all3.

We pick a random set of cities in the above instance as follows:Pick a random from, and for every,pick a city uniformly at random from.Let and.See Figure2(b)for an example.It is easy to see that the set induces an instance of the facility location problem almost identical to the instance in Lemma3.1(the only difference is that here we have more facilities,but it is easy to see that the only relevant facilities are the ones that are present in).Therefore,the cost of the optimal solution on is.

We show that for any cross-monotonic cost-sharing scheme,the average recovered cost over the choice of is at most and thus conclude that there is some whose recovered cost is.As in the previous proofs,we start bounding the expected total cost share by using the linearity of expectations and cross-monotonicity:Notice the set has a facility location solution of cost and thus by the budget balance condition the second term in the above expression is at most. The?rst term in the above expression can be written as where the expectation is over the random choice of and the random choice of from.However,it can be seen easily that this is equivalent to the following random experiment:From each,pick a city uniformly at random.Then pick from uniformly at random and let and.From this description it is clear that the expected value of

is equal to

. Therefore,

f 1

f

m

1k

(a)(b) Figure2:Lower bound for facility location game

T HEOREM3.5.There is no-budget balanced pro?t sharing scheme for the maximum?ow game where is the number of agents.

The second problem is the problem of packing the maximum number of arborescences in a digraph.An -arborescence is a spanning tree rooted at in which all edges are directed away from.In the maximum -arborescence game,we are given a directed graph with a root.Agents are directed edges of.Given a subset of edges,,the value of is the maximum number of edge-disjoint-arborescences on the subgraph induced by.One can think of the pro?t of as the maximum bandwidth for broadcasting messages from to all vertices of the graph.It is known that the core of this game is nonempty[2].

T HEOREM3.6.There is no-budget balanced pro?t sharing scheme for maximum-arborescence game.

Finally,we consider the maximum matching game, in which the agents are vertices of a graph,and the pro?t of a subset of vertices is the size of maximum matching in.One can show that there is a-budget balance pro?t allocation in the core of this game. T HEOREM3.7.There is no-budget balanced pro?t sharing scheme for the maximum matching game. 4Group-strategyproof mechanisms

A main motivation behind cross-monotonic cost-sharing schemes is that they can be used to de?ne group-strategyproof mechanisms[13].In the previous section,we proved that for certain games every cross-monotonic cost sharing scheme for certain games is poorly budget balanced.A natural question to ask is whether all group-strategyproof mechanisms for these games are so poorly budget balanced.Towards this aim, one might hope to show that every group-strategyproof mechanism corresponds to a cross-monotonic cost shar-ing scheme.In fact,given a group-strategyproof mech-anism,it is possible to de?ne a corresponding cost-sharing scheme by having the agents in a set bid a suf?ciently large value and others zero,and letting

be the payment charged by the mechanism to the agent in this scenario.Unfortunately,this scheme is not necessarily budget-balanced or cross-monotonic. In fact,the following simple examples show that for ev-ery cost function,there is a group-strategyproof mech-anism recovering all the cost.

E XAMPLE1.Single Payment Mechanism:Arbitrarily order the agents from to.Then,?nd the?rst agent in this order whose bid is at least.The set that will receive the service is,and the total cost of servicing this set is paid by the agent. Other agents pay nothing.

A less unfair mechanism that still recovers all the cost and works for every subadditive function is the following.

E XAMPLE2.Arbitrarily order the users from to. Initialize the set of serviced users to the empty set and

the amount of money that is already charged to the agents to0.For from to,do the following:if the bid of is at least, then include in,and charge him

(therefore,will be increased by this quantity).

Intuitively,the mechanisms in Examples1and2 are neither fair nor ef?cient.They always place the bur-den of the entire service cost on a small subset of agents while servicing others for free.Agents who receive the service for free,called free riders,increase the cost of the solution but do not contribute any payment.We consider constraining our mechanism to rule out free riders.With this added constraint,we can prove that there is no budget-balanced group strategyproof mech-anism for vertex cover.To prove this statement and sev-eral others,we prove a useful structural lemma(Lemma 4.1)on the cost sharing schemes derived from a group-strategyproof mechanism.We need the following de?-nition to state this lemma.

D EFINITION4.Let be a cost-sharing scheme,,and.We say is good for set if for every,

and for at least one a strict inequality holds;is bad for if for every,

and for at least one a strict inequality holds.If for all,,we say is neutral for.

L EMMA4.1.Let be a cost-sharing scheme derived from a group-strategyproof mechanism.Then for every player and set,,is either good,bad, or neutral for.

Using Lemma4.1,we prove the following:

T HEOREM4.1.There is no budget-balanced group strategyproof mechanism without free riders for the ver-tex cover game.

Proofs of Lemma4.1and Theorem4.1can be found in Appendix C.Although there is no budget-balanced group strategyproof mechanism for the vertex cover game,the following theorem shows that for every,there are-budget balance group strategyproof mechanisms without free riders for any non-decreasing cost function.T HEOREM4.2.For any non-decreasing cost function and,there is an-budget-balanced group-strategyproof mechanism for with no free-riders. Proof Sketch.The idea is to charge every agent a small participation fee that depends on.Let be the

subset of bidders who bid strictly greater than.Other bidders will not be considered by the mechanism.Now, we run a variant of the single payment mechanism for bidders in:Arbitrarily order the agents,and?nd the?rst agent in this order whose bid is at least

.The set receives the service,pays,and everybody else in pays.

In the mechanism given in the above proof,there are scenarios in which an agent does not receive the service,but would receive service if she increased her bid by any positive amount,however small.In fact,we can show that a cross-monotonic cost sharing scheme can be derived from any mechanism with no free riders for which such situations do not occur.More precisely, we call a mechanism upper continuous if for every player,if gets the service for every bid value greater than holding other bids?xed,then gets the service if she bids.Upper continuity by itself is not dif?cult to satisfy.In fact,both mechanisms in Examples1and2 are upper continuous.However,the following theorem shows that mechanisms satisfying upper continuity and no-free-rider conditions are as hard as cross-monotonic cost sharing schemes.The proof of this theorem can be found in the appendix.

T HEOREM4.3.The cost function has an upper-continuous-budget-balanced group-strategyproof mechanism with no free riders if and only if it has an-budget-balanced cross-monotonic cost-sharing scheme.

In the proof of Theorem4.3we do not use coali-tions of size greater than2.Thus,with the assumptions of no-free-rider and upper-continuity,coalitions of size 2are as strong as coalitions of arbitrary size.We do not know if this equivalence holds without these assump-tions.Theorem4.2shows that the no-free-rider prop-erty is not strong enough to guarantee that the mech-anism is fair,since there are almost budget-balanced group-strategyproof mechanisms satisfying this prop-

erty in which a few users pay a large portion of the to-tal cost.A stronger fairness property is the subsidy-freeness property considered by Moulin5[12].This condition says that the total charge of the mechanism to all users in a set is at most the cost of the set .In the following theorem,we show that group-

strategyproof mechanisms with this property are equiv-alent to cross-monotonic cost sharing schemes.

T HEOREM4.4.There exists a budget-balanced group-strategyproof mechanism satisfying the subsidy-freeness property for a cost function if and only if this cost function has a budget-balanced cross-monotonic cost-sharing scheme.

The proof of this theorem is based on Lemma4.1 and is left to Appendix C.We do not know if this theorem holds for budget-balance factors other than1. 5Conclusion

In this paper,we studied lower bounds for the budget-balance factor of cross-monotonic cost-sharing schemes for a variety of combinatorial optimization games.Our techniques are quite general and may prove applicable to variety of other interesting games.For ex-ample,the facility location game restricted to a tree al-ways has a budget-balanced cost sharing in the core[6], but we do not have a tight lower and upper bound for the budget-balance factor of a cross-monotonic cost sharing scheme.For the facility location on the line, we have the lower bound of

5See Devanur et al.[3]for a discussion of strategyproof(but not group-strategyproof)mechanisms satisfying subsidy-freeness for set cover and facility location problems.open question in this area is to extend the result of Theorem4.4and show that-budget-balanced group-strategy mechanisms with subsidy-freeness are equiva-lent to-budget-balanced cross-monotone cost-sharing schemes.

It is a standard economic result that a strategyproof mechanism can not be both ef?cient(i.e.,return a solution that maximizes social welfare)and budget-balanced[7,16].It would be interesting to explore the possible budget-balance factor of group-strategyproof mechanisms that are in some sense close to ef?cient. Acknowledgments.We would like to thank Michel Goemans for helpful discussions.Also,we would like to thank Martin P′a l for introducing the problem and for helpful discussions.

References

[1]O.N.Bondareva.Some applications of linear program-

ming to cooperative games.Problemy Kibernetiki, 1963.

[2]X.Deng,T.Ibaraki,and H.Nagamochi.Algorithms

and complexity in combinatorial optimization games.

In SODA,1997.

[3]N.Devanur,M.Mihail,and V.Vazirani.Strategyproof

cost sharing mechanisms for set cover and facility location problems.Proceedings of ACM Conference on Electronic Commerce,2003.

[4]J.Feigenbaum, C.Papadimitriou,and S.Shenker.

Sharing the cost of multicast transmission.Proceed-ings of STOC,2000.

[5]M.Goemans.Personal communication.

[6]M.X.Goemans and M.Skutella.Cooperative facility

location games.Proceedings of SODA,2000.

[7]J.Green,E.Kohlberg,and https://www.wendangku.net/doc/6e10283998.html,ffont.Partial equi-

librium approach to the free rider problem.Journal of Public Economics,6:375–394,1976.

[8]K.Jain and V.V.Vazirani.Applications of approxi-

mation algorithms to cooperative games.Proceedings STOC,2001.

[9]K.Jain and V.V.Vazirani.Approximation algorithms

for metric facility location and k-median problems us-ing the primal-dual schema and lagrangian relaxation.

Journal of the ACM,48:274–296,2001.

[10]K.Jain and V.V.Vazirani.Equitable cost alloca-

tions via primal-dual-type algorithms.Proceedings of STOC,2002.

[11]K.Kent and D.Skorin-Kapov.Population monotonic

cost allocation on MST’s.In Operational Reearch Proceedings KOI,pages43–48,1996.

[12]H.Moulin.Axioms of cooperative decision making,

volume1,chapter Cost sharing games and the core.

Cambridge University Press,1988.

[13]H.Moulin and S.Shenker.Strategyproof sharing of

submodular costs:budget balance versus ef?ciency.to appear in Economic Theory,1997.

[14]Herv′e Moulin.Incremental cost sharing:Characteri-

zation by coalition strategy-proofness.Social Choice and Welfare,16:279–320,1999.

[15]M.Pal and E.Tardos.Strategy proof mechanisms via

primal-dual algorithms.FOCS’03,2003.

[16]K.Roberts.The characterization of implementable

choice rules.In https://www.wendangku.net/doc/6e10283998.html,ffont,editor,Aggregation

and Revelation of Preferences.Studies in Public Eco-nomics,Amsterdam,North Holland,1979.

[17]Lloyd S.Shapley.On balanced sets and cores.Naval

Research Logistics Quarterly,14:453–460,1967.

A Set cover and vertex cover games

T HEOREM A.1.There is no cross-monotonic cost-sharing scheme for the set cover game such that for every set,recovers more than a

in an experiment that con-sists of choosing an agent from each uniformly

at random.By the budget-balance property,we always

have

.Therefore,the?rst term in the left-hand side of the

inequality(1.8)is at most one.This means that the ex-

pected total cost share recovered from the set is at most two.Therefore,the ratio of recovered cost to total

cost of is at most.

Proof of Theorem3.3.It is clear that this scheme is

cross-monotone.We only need to verify the budget-

balance factor.Consider a set of agents(i.e.,

edges),and the graph induced on this set of edges. We prove that the total cost share of the agents in is at least times the cost of a vertex cover for.

Divide the set of vertices into two subsets and ,where is the set vertices of degree less than

,the sum of the cost shares of the edges adjacent to is at least.Each edge is included in at most two such summations,and thus the sum of the cost shares of edges adjacent to vertices in is at least a fraction of the cost of.Therefore, the sum of the cost shares of the agents in is at least times the cost of the optimal vertex cover for.

Figure3:The graph for the maximum?ow game

B Proofs for theorems in Section3.4

Proof of Theorem3.5.Let be a graph consisting of three nodes:,,and.There are edges from to,and edges from to.Let and

denote the set of edges from to and from to, respectively.See Figure3.We pick a random set of agents as follows:With probability,pick a random edge from to,and let. With probability,pick a random edge from to ,and let.For example the set could contain the thick edges in Figure3.

Assume is an-budget balanced cross-monotonic pro?t-sharing scheme for.We have that

is

On the the hand,the pro?t of every set picked using the above procedure is one.Therefore,the expected ratio of the total pro?t shares to the pro?t of is at least.

The same construction as the one used in the above proof gives us a proof for Theorem3.6.Proof of Theorem3.7.We use the same construction that was used in the proof of Theorem3.1.Let be a complete bipartite graph with vertices in each part(here we use instead of so that the size of becomes),and pick by picking a random

vertex in and all vertices in the other https://www.wendangku.net/doc/6e10283998.html,ing an argument essentially the same as the one used in the proof of Theorem3.1,the expected total pro?t share of the elements of is at least.On the other hand,the pro?t of is always one.Thus,there is an on which the ratio between the total pro?t-share and the pro?t of is at least.

C Proofs of results in Section4

Proof of Lemma4.1.For a player,let be a large enough number such that if player bids,he will get the service,independent of other players’bids. Let.Consider the following3bid vectors:

1.

2.

3.

It is clear that in the?rst scenario set is served and in the third scenario is served.Consider two cases:

Case1:If is served in scenario2,’s payment is equal to(otherwise would lie in scenario1by announcing as his bid and consequently pay less).We claim that for every ,.Assume for contradiction that.

Then can convince to bid0in scenario2.

Player’s happiness remains the same(zero)and

pays less,and so they can form a coalition, contradicting with group strategyproofness.Here we used coalitions of size at most2in the proof. Case2:If is not served in scenario2,we claim that for every,

.Assume for contradiction that

.Now,can convince to bid in scenario2.Player’s happiness remains the same and pays less,so we again have a

coalition(of size at most2),contradicting group strategyproofness.

In case1,is good or neutral for by de?nition and in case2,is bad or neutral by de?nition.

C OROLLARY C.1.In a group-strategyproof mecha-nism,a good player will(and a bad player will not) receive service if she bids her cost share in the serviced set,other players in bid,and others bid zero.

L EMMA C.1.Let be a group-strategyproof mecha-nism.Consider a bid vector such that for and for.If play-ers bid according to this vector,then set is serviced at their cost shares.

Proof.Order the bidders such that.We will prove by induction that if the?rst bidders in bid and the rest bid,then the set is served at their cost shares.First notice that,by de?nition,if

for all,gets the service at their cost shares. Consider the following scenarios:

1.

2.

By induction hypothesis,gets serviced at his cost share in the scenario1.If he gets serviced at less than his cost share in scenario2,then when the true utilities are as in scenario1,will lie and bid.Similarly,if he gets serviced at more than his cost share in scenario2 or does not get the service,then when the true utilities are as in scenario2,will lie and bid.Therefore, gets serviced at his cost share in scenario2and is thus indifferent between scenario1and2.Therefore,no one’s happiness can change between the two scenarios or else they could form a coalition with bidder.Since all non-zero bidders have positive happiness in scenario 1,they must have positive happiness in scenario2and must receive the service at their cost shares.

We use the above lemma to prove the following:

L EMMA C.2.Let be a group-strategyproof mech-anism.For any bid vector,if the serviced set is,then payment of is equal to .Proof.Let.It is clear that all members of do not pay more than.We prove that they do not pay less either.Thus for,

and pays.Let

and.Let be a scenario at which all members of bid,all members of bid(their bid in)and all members of bid zero.From Lemma C.1,in scenario,set will get the service at the cost

.If a player in pays less in than in, then can convince to make a coalition

in and pretend.As a result will pay less and no member of coalition pay more contradicting with group-strategyproofness.Now consider player. If he pays more than in,he would make the coalition and pretend instead and pay less.Thus,all members of also pay the same as .Also if any player in pays less in than in,then can convince to make a coalition

in and pretend instead and pay less.

Proof of Theorem4.1.Let be a budget-balanced group-strategyproof mechanism for the vertex cover problem.Now consider the complete graph on3 vertices.The cost of servicing3players is2,the cost of any two players is1and the cost of individuals is1. For ease of notation we will use as a number strictly greater than.

It is not hard to see that for any.Assume for contradiction,

.From the budget-balanced property,

.Choose

.Consider the scenario

and compare it to the scenario

.By the budget-balance property,it is not possible that both and or either of them individually get the service in.If does not get the service(and so the serviced set is empty),then the three players can form a coalition and report bids.Thus receives the service at cost at most.By Lemmas C.1and C.2,3has to pay in scenario and thus has incentive to lie and bid.

From this we can show that no player is good and at most one player is neutral for set.For contra-diction,assume is good.Then

Thus

.This contradicts our bound on the cost shares.By similar arguments,if is neutral for,then,so by budget-balanced and no-free-riders,no one else can be neutral. Thus,there exists at least one bad player.

Consider the scenario

. As there is one bad player,at least one player will not receive the service in this scenario,say player3.If one or no player gets the service,then have incentive to lie and bid. If both and get the service,then we prove that

.But this implies which contradicts the no-free-rider assumption.

If2is neutral for,we know

.Otherwise both and are bad.Now consider the scenario

. Since is bad,2will not get the service,since 1’s and3’s bids are strictly greater than their cost share in,the served set is. Thus,and

,because oth-erwise can lie in and pretend and get the service at lower costs.From these two equalities and the fact that the sum of cost shares for3players is2, we see that.Similar to this we can show that no matter whether is neutral or bad.This contradicts with not having free riders because it implies that.

Proof of Theorem 4.3.Given an-budget-balanced cross-monotonic cost-sharing scheme,the Moulin-Shenker mechanism gives an-budget-balanced group-strategyproof mechanism[13]with upper-continuity and without free riders.Given an-budget-balanced group-strategyproof mechanism, Corollary C.1shows that the upper continuity condi-tion implies all players are good or neutral.This proves that given a group-strategyproof mechanism,is cross monotone.The budget-balance factor is the same because when bids suf?ciently large and other play-ers bid zero,the served set is exactly since there are no free riders.Proof of Theorem4.4.The“if”part is obvious from

the Moulin-Shenker mechanism[13].Given a budget-

balanced group-strategyproof mechanism with the corresponding cost share in the core,we prove that

there is no bad player.Consider player who is bad for the set.Then for any player,

and a strict inequality holds at least for one.Thus,

,It contradicting the core property.Therefore,all players are good or neutral, and so the cost sharing derived from is cross monotone.

如何写英文Abstract

How to Write an Abstract 一、什么是摘要Abstract? an abstract comprises one paragraph which describes the main content of a paper and appears at the very beginning of the paper. 摘要是叙述文章主要内容的一个段落，并且位于文章的开头部分。 摘要是以梗概形式呈现的一篇文章要点的总结，它强调了一篇文章所包含的重要的信息。它也可以帮助读者快速的了解到是否这篇文章是他们感兴趣的，是否他们需要来阅读整篇文章。而且，国家或国际出版社的编辑通常通过浏览投稿文章的摘要来决定是否投稿人的文章是可以被录用的。因此，对于学者和研究人员来说，写一份好的摘要至关重要。 二、写作Abstract的目的 对于科技论文的摘要，Abstract的目的有以下几点： 1.Introduce journal articles. https://www.wendangku.net/doc/6e10283998.html,rm readers about article`s content. 3.Help readers decide whether or not to read article. 4.Overview conference programs,abstract collections,and book chapters. 三、学习写作Abstract的必要性 1.Helps you present complex information in a clear,concise manner. 2.Helps you read abstracts more effectively. 3.Helps you conduct research. 4.Helps you write abstracts for future publications. 5.Helps you condense report information into a short format for database searches. 四、Abstract的写作要求 https://www.wendangku.net/doc/6e10283998.html,e one or more well-developed paragraphs,which are unified,coherent,concise,and able to stand alone（200-300 words). https://www.wendangku.net/doc/6e10283998.html,e an introduction-body conclusion structure in which the parts of the parts of the report are discussed in order:purpose,researcquestions,method,findings,conclusions,recommendations.

国外写作APA详细模板

[Title of Paper] [Student Name] [School] [Course/Number] April 13, 2013 [Instructor Name]

Abstract (if needed)[replace] [According to the Publication Manual of the American Psychological Association (APA), “An abstract is a brief, comprehensive summary of the contents of the article; it allows readers to survey the contents of an article quickly and, like a title, it enables persons interested in the document to retrieve it from abstracting and indexing databases” (2010, p. 25). The first line of the abstract is not indented. An abstract may range from 150 to 250 words (APA, 2010). Because an abstract is not always required for student papers, adhere to your instructor’s requirements. ]

abstract 的语步分析

Research article abstract 1.Introducing purpose This move gives a precise indication of the author’s intention, thesis or hypothesis which forms the basis of the research being reported. It may also include the goals or objectives of research or the problem that the author wishes to tackle. 2.Describing methodology In this move the author gives a good indication of the experimental design, including information on the data, procedures or method(s) used and, if necessary, the scope of the research being reported. 3.Summarizing results This is an important aspect of abstracts where the author mentions his observations and findings and also suggests solutions to the problem, if any, posed in the first move. 4.Presenting conclusions This move is meant to interpret results and draw inferences. It typically includes some indication of the implications and applications of the present findings.

UPPAAL建模工具教程

Uppaal4.0:Small Tutorial? 16November2009 1Introduction This document is intended to be used by newcomers to Uppaal and veri?cation.Students or engineers with little background in formal methods should be able to use Uppaal for practical purposes after this tutorial. Section2describes Uppaal and Section3is the tutorial itself. 2Uppaal Uppaal is a tool box for validation(via graphical simulation)and veri?cation(via automatic model-checking)of real-time systems.It consists of two main parts:a graphical user interface and a model-checker engine.The user interface is implemented in Java and is executed on the users work station.Version4.0of Uppaal requires that the Java Runtime Environment5or higher is installed on the computer.The engine part is by default executed on the same computer as the user interface,but can also run on a more powerful server. The idea is to model a system using timed automata,simulate it and then verify properties on it.Timed automata are?nite state machines with time(clocks).A system consists of a network of processes that are composed of locations.Transitions between these locations de?ne how the system behaves.The simulation step consists of running the system interactively to check that it works as intended.Then we can ask the veri?er to check reachability properties,i.e.,if a certain state is reachable or not.This is called model-checking and it is basically an exhaustive search that covers all possible dynamic behaviours of the system. More precisely,the engine uses on-the-?y veri?cation combined with a symbolic technique re-ducing the veri?cation problem to that of solving simple constraint systems[YPD94,LPY95].The veri?er checks for simple invariants and reachability properties for e?ciency reasons.Other prop-erties may be checked by using testing automata[JLS96]or the decorated system with debugging information[LPY97]. 3Learning Uppaal Uppaal is based on timed automata,that is?nite state machine with clocks.The clocks are the way to handle time in Uppaal.Time is continuous and the clocks measure time progress.It is allowed to test the value of a clock or to reset it.Time will progress globally at the same pace for the whole system. A system in Uppaal is composed of concurrent processes,each of them modeled as an automa-ton.The automaton has a set of locations.Transitions are used to change location.To control when to take a transition(to“?re”it),it is possible to have a guard and a synchronization.A guard is a condition on the variables and the clocks saying when the transition is enabled.The synchronization mechanism in Uppaal is a hand-shaking synchronization:two processes take a ?This description covers version4.0.7

Java中的abstract方法和abstract类的问题

Java中的abstract方法和abstract类的问题 当知道一个类的子类将不同的实现某个方法时，把该类声明为抽象类很有用，可以共用相同的父类方法，不必再定义。 抽象类和抽象方法的关系:含有抽象方法的类一定是抽象类，抽象类里不一定含有抽象方法。抽象类存在的意义是用来被继承的。一个类继承了一个抽象类，必须实现抽象类里面所有的抽象方法，否则，此类也是抽象类。 abstract修饰符用来修饰类和成员方法 1：用abstract修饰的类表示抽象类，抽象类位于继承树的抽象层，抽象类不能被实例化。2：用abstract修饰的方法表示抽象方法,抽象方法没有方法体。抽象方法用来描述系统具有什么功能，但不提供具体的实现。 abstract 规则： 1：抽象类可以没有抽象方法，但是有抽象方法的类必须定义为抽象类，如果一个子类继承一个抽象类，子类没有实现父类的所有抽象方法，那么子类也要定义为抽象类，否则的话编译会出错的。 2：抽象类没有构造方法，也没有抽象静态方法。但是可以有非抽象的构造方法 3：抽象类不能被实例化，但是可以创建一个引用变量，类型是一个抽象类，并让它引用非抽象类的子类的一个实例 4：不能用final 修饰符修饰 Q:java里面有抽象类么？和接口的区别是什么？ A:java中有抽象类,用关键字abstract修饰。 以下是我对这个问题的看法。 首先，从语法上讲，抽象类是一个类，根据java的单继承体系。如果它有子类，那么它的

子类只能继承它。 java允许实现多个接口。所以一个类可以实现多个接口 抽象类里面可以定义各种类型和访问权限的变量(就像普通类一样)，也可以定义各种访问权限的方法(就像普通类一样)。 但是接口不可以。在接口里面定义的方法默认就是public abstract的，变量默认就是public static final的。(不管你有没有加权限控制符，不加，默认就是这些权限；加错了，权限缩小了，那么就会报错) 其次，从意义上讲，如果继承一个抽象类，那么抽象类和它的子类就有父子关系，即有类的层次关系(这关系到类的设计问题)。 接口，在我看来，是一种契约或者协议，是一层提供给另一层的接口(可以想象成OSI各层之间的关系) 在某一层中有多个类协作实现这个层的功能，通过接口暴露出去。但这些类之间会有层次关系(is a,has a) Q:一个方法加abstract和不加abstract有什么区别？就是说不加有什么关系？加了又会怎样？ A:一方法要是加abstract，那么这个方法就是抽象的，须由子类去实现 抽象方法必须在抽象类当中，也就是说，一个类只要有一个方法是抽象的，那么这个类就必须是抽象类 抽象类里面的方法不一定要抽象的，也可以全都不是抽象的 抽象类不能实例化！ 所以可以想到，当你不想让你的类被别人实例化，只想这个类的子类可以实例化，那么只要将这个类声明为abstract的就可以了

abstract结构分析

1.Urology is perceived as a competitivespecialty choice. Declining undergraduate exposure and thepreference for ‘‘lifestyle specialties’’ may jeopardize urology’s popularity. Our objective was to assess trends inapplication and matching rates to urology compared withother surgical specialties. 2. We reviewed data collected by CanadianResidency Matching Service (CaRMS) and the CanadianPost-MD Education Registry since expansion in Canadianmedical school enrollment began (2002-2011). The following were examined: applicant preference, number ofpositions, gender patterns, and match results. ‘‘Surgery’’included general surgery, orthopedics, plastics, ENT, and urology. 3.From 2002 to 2011 CaRMS applicantsincreased from 1117 to 2528 (126%). The number ofapplicants selecting surgery first increased from 178 to338(90%). The number of surgery positions increased from138 to 275 (100%). Urology positions increased from 15to 31 (113%). Applicants to urology increased only 40%(30-42). The proportion of all CARMs applicants selectingurology as their first choice decreased from 2.7% (30) to1.7% (42). The ratio of first choice urology applicants topositions decreased from 2 to 1.35. The probability ofmatching urology as first choice increased from 50% to76%. Female medical graduates increased from 51% to58%. The female applicants selecting surgery first increasedfrom 21% (49) to 41% (173). In contrast, females selectingurology first rose from 13% (4) to 17% (7). 4.Urology in Canada is becoming lesscompetitive. Residency positions have doubled since 2002whereas the number of applicants remains static. This trendwas not reflected in other surgical specialities. Factorsaccounting for this may include poor undergraduateexposure, demand for specialties with controllable lifestyles,gender shifts in undergraduate medicine, and lack of rolemodels. The need for undergraduate exposure to urologyand vetting numbers of residency positions remains a matterof paramount importance. ( JSurg 70:537-543. JC2013Association of Program Directors in Surgery. Published byElsevier Inc. All rights reserved.) BACKGROUND1: METHODS2: RESULTS3: CONCLUSION4:

英文论文模板

A4 Paper Size Format for RFIT (Title in 18-point Times font) 1st Author1,2, 2nd Author2, 3rd Author1,2 (List authors on this line using 12 point Times font) 1Name of first affiliation, City, State/Region, Mail/Zip Code, Country 2Name of second affiliation, City, State/Region, Mail/Zip Code, Country (authors' affiliation(s) listed here in 12 point Times font) Email: contact.author@https://www.wendangku.net/doc/6e10283998.html, Abstract — Use 9 point Times New Roman Bold font for the abstract. Set your line spacing to be 10 points rather than single space. Indent the first line by 0.125 inches and type the word "Abstract" in 9 point Times New Roman Bold Italic. This should be followed by two spaces, a long dash (option / shift / minus), two spaces, and then the first word of your abstract (as shown above). Please try to keep the length of your abstract to 100 words or less. Times font is an acceptable substitute for Times New Roman font. After the abstract, you should list a few key words from the IEEE approved “Index Terms” LIST that describe your paper. The index terms are used by automated IEEE search engines to quickly locate your paper. Typically, you should list about 5 to 7 key words, in alphabetical order, using 9 point Times New Roman Bold font. An example is shown next. Index Terms — Ceramics, coaxial resonators, delay filters, delay-lines, power amplifiers. I. I NTRODUCTION Please read through this entire template before you start using it to create your paper! This will save you and the RFIT Committee considerable time, and improve your chances for acceptance. The following information is provided to help you prepare the Initial Submission as well as the Final Paper for submission to RFIT. (Many authors submit the same paper for the initial as well as the final submission. This is a common practice. See item #4 below.) A contributor should remember that: 1) Deadlines are absolute, don't even ask! 2) Summaries may not exceed four pages, including all figures, tables, references, etc. Additionally, there is a size limit on the electronic version of all Summaries. In Adobe Portable Document Format (PDF), submissions may not exceed 1 Megabyte. 3) Acceptance rates have historically run at approx-imately 50%. There is not sufficient room within the Technical Program to accept all submissions. 4) Many submitters with previous experience realize that, if their submission is accepted, they will be required to submit a version of their Final Paper to be published in the Symposium Digest. As the Digest paper will be similar in length to the Summary, many contributors opt to prepare their Summary in the format required for the Digest. This template contains the instructions for the proper preparation of such a document. 5) Although not required, you are encouraged to employ this format. This document is being made available as a template for your convenience. If you elect not to use this template, please remember that you must still adhere to the general guidelines embodied in this document concerning, but not limited to, font size, margin size, page limits, file size, etc. (Note: Starting in 2004, Index Terms are required.) II. O VERVIEW OF THE D IGEST F ORMAT We are requesting that you follow these guidelines as closely as possible so that the Digest has a professional look and resembles the MTT Transactions. All paragraphs of text, including the abstract, figure captions, and refer-ences, should be justified at the left and the right edges. For the Title use 18-point Times (Roman) font. Its paragraph description should be set so that the line spacing is single with 6-point spacing before and 6-point spacing after (Format --> Paragraph --> Indents and Spacing). The font description for the Author List and Authors' Affiliation(s) should be 12-point Times. The paragraph descriptions should be set so that the line spacing is single with 6-point spacings before and after. Use an additional line spacing of 12 points before the beginning of the double column section, as shown above. III. D ETAILED T EXT F ORMATTING Using 210 x 297-mm (8.27 x 11.69-inch) A4 paper, the top and bottom margins are 31.75-mm (1.25 inches), and the left and right margins are 19-mm (0.75 inches). Except for Title, Authors and Affiliations, use a double column format. The column width is 83-mm (3.27 inches) and the column spacing is 5.8-mm (0.23 inch). Each major section begins with a Heading in 10 point Times font centered within the column and numbered using Roman numerals (except for A CKNOWLEDGEMENT and R EFERENCES), followed by a period, a single space, and the title using an initial capital letter for each word. The remaining letters are in SMALL CAPITALS. The paragraph description of the section heading line should be set for 18 points before, 6 points after, and the line spacing should be set to exactly 12 points.

期刊论文的分析技巧与程序总结

（1）Abstract： 说明这篇论文的主要贡献、方法特色与主要内容。只看Abstract 和Introduction便可以判 断出这篇论文的重点和你的研究有没有直接关连，从而决定要不要把它给读完。 （2）Introduction： Introduction 的功能是介绍问题的背景和起源，交代前人在这个题目上已经有过的主要贡献，说清楚前人留下来的未解问题，以及在这个背景下这篇论文的想解决的问题和它的重要性。对初学的学生而言，从这里可以了解以前研究的概况。通常我会建议初学的学生，对你的题目不熟时，先把跟你题目可能相关的论文收集个30～40篇，每篇都只读Abstract 和Introduction，而不要读Main Body（本文），只在必要时稍微参考一下后面的Illustrative examples和Conclusions，直到你能回答下面这三个问题： （2A）在这领域内最常被引述的方法有哪些？ （2B）这些方法可以分成哪些主要派别？ （2C）每个派别的主要特色（含优点和缺点）是什么？ 问题是，你怎么去找到这最初的30～40篇论文？有一种期刊论文叫做「review paper」，专门在一个题目下面整理出所有相关的论文，并且做简单的回顾。你可以在搜寻Compendex时在keywords 中加一个「review」而筛选出这类论文。然后从相关的数篇review paper 开始，从中根据title 与Abstract 找出你认为跟你研究题目较相关的30～40篇论文。 通常只要你反复读过该领域内30～40篇论文的Abstract 和Introduction，你就应该可以从Introduction的评论中回答（2A）和（2B）这两个问题。尤其要记得，当你阅读的目的是要回答（2A）和（2B）这两个问题时，你一定要先挑那些Introduction写得比较有观念的论文念（很多论文的Introduction 写得像流水帐，没有观念，这种论文刚开始时不要去读它）。假如你读过假如30～40篇论文的Abstract

语言学中的研究方法

第34卷第6期 唐山师范学院学报 2012年11月 Vol.34 No.6 Journal of Tangshan Teachers College Nov. 2012 ────────── 收稿日期：2012-03-25 作者简介：申丽红（1975-），女，河北邯郸人，博士研究生，讲师，研究方向为理论语言学及语言教学。 -24- 语言学中的研究方法 申丽红1,2 （1. 中国传媒大学 文学院，北京 100021；2. 河北联合大学 外国语学院，河北 唐山 063000） 摘 要：语言学作为社会科学和自然科学的交叉学科，近年来有了长足的发展。各家学者秉承不同的语言学理论，采用不同的研究方法对语言进行了多方位的研究。本文从语言学理论的不同发展阶段对语言学研究方法做一梳理。 关键词：语言学；定量研究；定性研究 中图分类号： H 0-05 文献标识码： A 文章编号：1009-9115(2012)06-0024-03 Some Research Methods of Linguistics SHEN Li-hong 1,2 (1. College of Liberal Arts, The Communication University of China, Beijing 100021, China; 2. College of Foreign Languages, Hebei United University, Tangshan 063000, China) Abstract: Linguistics, as a cross-discipline between natural and social science, has developed well in recent years. Different scholars did some researches on language with different theories and from different angles. A summary about the research methods of linguistics is made. Key Words: linguistics; quantitative research; qualitative research 语言是人类特有的宝贵财产，是人类社会生活的重要组成部分。随着社会发展，文明进步，人们开始从不同角度探索语言的奥秘，以揭示形形色色的言语背后所隐藏的规律，从而形成了林林总总的语言学流派和语言学理论。 任何一门学科的研究方法对于一门学科的发展都是至关重要的。在语言学发展的不同阶段，不同的语言学流派以不同的哲学基础建立起自己的理论框架后，因其学科发展的不同时期以及不同的研究目的而选用不同的研究方法来进行语言学相关研究。 一、语言学发展简史 西方的语言学研究自古希腊始，希腊著名的哲学家苏格拉底（Socrates, BC 470-BC 399），柏拉图（ Plato, BC 429-BC 347）和亚里士多德（Aristotle, BC 384- BC322）等通过对语言的辩论奠定了语言研究的哲学基础。此后语言学在西方历经中世纪、文艺复兴以及19世纪历史比较语言学的发展，随着一些人类学家、哲学家等相继加入语言学研究，语言学学科迅速发展。他们详细研究了语言的分类， 语言中的音变等，为现代语言学的诞生奠定了坚实的基础。 20世纪初，瑞士语言学家索绪尔提出的普通语言学理论使语言学真正成为了一门科学的学科。此后的布拉格学派、哥本哈根学派以及美国的结构主义学派基本上秉承了结构主义的衣钵，对语言的结构、音位等进行了详细的描写和切分。 20世纪50年代，乔姆斯基（Noam Chomsky ）提出了转换生成语法（Transformational-Generative Grammar ）。转换生成语法彻底颠覆了传统的结构主义语法，推动语言学研究进入当代语言学时期。乔姆斯基认为人类获得语言的过程无论采用“白板说”还是“刺激-反应”论都不足以说明问题，以此提出了“先天性假设”（innateness hypothesis ）。他认为人类的大脑先天被内置了一套“普遍语法”（universal grammar ）或“语言普遍现象”（linguistic universals ）。这种普遍语法在后天经验的触发下而形成各种各样的“个别语法”（particular grammar ）。语言学家的任务就是运用数学的运算原理，运用各种规则逐步推导以

TOPSIS方法研究讲解

TOPSIS分析方法研究 摘要 本文主要介绍了TOPSIS分析方法理论及其主要思想，运用数学理论，对其算法进行了详细的分析，并指出原始方法存在的优缺点；在此基础上提出了一种改进的TOPSIS分析方法，给出具体求权重的方法，突出其客观公正性.本文还分析了TOPSIS方法逆序产生的原因及其改进的方法，突出其实用性，推广其应用范围. 关键词TOPSIS法; 改进的TOPSIS; 权重；逆序

TOPSIS ANALYSIS METHOD ABSTRACT This paper describes a method of theory—TOPSIS, and its main idea. Using mathematical theory, its algorithm for a detailed analysis and noted the advantages and disadvantages of the original methods. On this base ,an improved TOPSIS method is given, and specific for weight, in order to highlight its objective impartiality. The paper also analyzes the causes of TOPSIS Reverse and its improved methods, highlight its practicality and the promotion of its use. Keywords TOPSIS method; Improved TOPSIS; weight; Reverse

论文写作abstract

How to Write an Abstract for a Research Paper WANG Yan School of International Studies UIBE Issues to address: 1What is an abstract? 2Functions of an abstract 3Structure of an abstract 4Principles of abstract writing 1. What is an abstract? ?An abstract is a condensed version of a longer piece of writing that highlights the major points covered, concisely describes the purpose and scope of the writing, and reviews the writing's contents in abbreviated form. ?It is a concise and clear summary of a complete research paper. ?It tells the reader What you set out to do, and Why you did it,How you did it, What you found (recommendations).

2. Functions of an abstract ?An abstract is used to communicate specific information from the article.?It is aimed at introducing the subject to readers, who may then read the article to find out the author's results, conclusions, or recommendations. 2. Functions of an abstract ?The practice of using key words in an abstract is vital because of today's electronic information retrieval systems. ?Titles and abstracts are filed electronically, and key words are put in electronic storage. ?When people search for information, they enter key words related to the subject, and the computer prints out the titles of all the articles containing those key words. ?An abstract must contain key words about what is essential in an article so that someone else can retrieve information from it. 3. Structure of an abstract ?The components of an abstract ①Background Information ②Subject Matter/Problem Statement ③Purpose ④Method (and Data) ⑤Results / Findings ⑥Conclusion / Implications