Networked public goods games model scenarios in which self-interested agents decide whether or how much to invest in an action that benefits not only themselves, but also their network neighbors. Examples include vaccination, security investment, and crime reporting. While every agent's utility is increasing in their neighbors' joint investment, the specific form can vary widely depending on the scenario. A principal, such as a policymaker, may wish to induce large investment from the agents. Besides direct incentives, an important lever here is the network structure itself: by adding and removing edges, for example, through community meetings, the principal can change the nature of the utility functions, resulting in different, and perhaps socially preferable, equilibrium outcomes. We initiate an algorithmic study of targeted network modifications with the goal of inducing equilibria of a particular form. We study this question for a variety of equilibrium forms (induce all agents to invest, at least a given set $S$, exactly a given set $S$, at least $k$ agents), and for a variety of utility functions. While we show that the problem is NP-complete for a number of these scenarios, we exhibit a broad array of scenarios in which the problem can be solved in polynomial time by non-trivial reductions to (minimum-cost) matching problems.
翻译:公共产品网络游戏模型假设,由自我利益代理人决定对一项不仅有利于自身而且有利于其网络邻居的行动投资是否或投资多少,例子包括疫苗接种、安全投资和犯罪报告。每个代理人的效用在邻国的共同投资中正在增加,但具体的形式可能因情景的不同而大不相同。一个主要代理人,如决策者,可能希望吸引代理人的大量投资。除了直接激励外,一个重要的杠杆是网络结构本身:例如通过社区会议,主要可以改变公用事业功能的性质,导致不同,或许社会上更可取的平衡结果。我们发起对有针对性的网络修改的算法研究,目的是引导某种特定形式的平衡。我们研究这一问题的均衡形式(至少吸引所有代理人投资一定的定额美元,确切的定额美元,至少是美元代理商),以及各种公用事业功能。我们表明,这些问题对于一些非情景来说是NP的完成的,但我们展示了一种广泛的模型性模型,在一定的时间上可以解决问题。