Truthful Mechanisms for Competing Submodular Processes

Details Truthful Mechanisms for Competing Submodular Processes Truthful Mechanisms for Competing Submodular Processes

2012-02-09

arxiv.org/abs/1202.2097v1

Computer Science

Computer Science and Game Theory

Scientific paper

Motivated by models of competitive influence spread in networks, we study mechanisms for allocating nodes to selfish agents. For example, a social network provider may wish to let advertisers provide offers to influential individuals. The advertisers benefit in that product adoption may spread through the network. However, a competing product may adversely impact the rate of adoption for any given advertiser. In general, there is a set U and rational agents vying for elements of this set. A valid allocation is a collection of subsets of U, one for each agent. In our applications, an agent's utility is non-decreasing in her own allocation and non-increasing in her opponents' allocation, and the social welfare is monotone submodular. This framework captures many models of influence spread, and in general, (set)monotone processes with negative externalities in which only the total welfare is submodular. We consider a mechanism that receives the agents' demands, and returns sets respecting those demands with the goal of maximizing social welfare. Introducing competition raises strategic issues, where agents may underreport their demands. The complication is that while the social welfare function is submodular, the utilities may undergo complex interactions due to externalities. In a such scenarios, the social welfare can be c-approximated by iteratively selecting an (arbitrary) agent in each iteration and greedily allocating her an item. Under two natural assumptions about the social welfare and the utilities, we show that using this algorithm with a randomized ordering is strategyproof for the case of k>2 agents. Interestingly, this approach fails to be strategyproof when there are only two agents. Instead, we recursively construct a strategyproof mechanism that maintains the social welfare approximation of the greedy algorithm. This method works when lifting the extra assumptions.

Affiliated with

Also associated with

No associations

Rating

Truthful Mechanisms for Competing Submodular Processes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Truthful Mechanisms for Competing Submodular Processes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Truthful Mechanisms for Competing Submodular Processes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-273529