NDLI: Altruism, selfishness, and spite in traffic routing

Please wait, while we are loading the content...

Natural language generation for sponsored-search advertisements

Truthful germs are contagious: a local to global characterization of truthfulness

Posted prices vs. negotiations: an asymptotic analysis

Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions

A sufficient condition for voting rules to be frequently manipulable

Altruism, selfishness, and spite in traffic routing

Self-financed wagering mechanisms for forecasting

Better redistribution with inefficient allocation in multi-unit auctions with unit demand

Uncoordinated two-sided matching markets

Strategic network formation with structural holes

Optimizing query rewrites for keyword-based advertising

Mechanism design over discrete domains

Item pricing for revenue maximization

On the communication requirements of verifying the VCG outcome

Generalized scoring rules and the frequency of coalitional manipulability

Behavioral experiments in networked trade

Permutation betting markets: singleton betting with extra information

Efficiency and redistribution in dynamic mechanism design

Fast convergence to nearly optimal solutions in potential games

On the windfall of friendship: inoculation strategies on social networks

Optimal bidding in stochastic budget constrained slot auctions

On characterizations of truthful mechanisms for combinatorial auctions and scheduling

Optimal envy-free pricing with metric substitutability

Informational overhead of incentive compatibility

Incentives for expressing opinions in online polls

Security and insurance management in networks with heterogeneous agents

Complexity of combinatorial market makers

A visual interface for critiquing-based recommender systems

Fault tolerance in large games

Strong regularities in online peer production

Monotonicity and implementability: extended abstract

Information revelation and random entry in sequential ascending auctions

Eliciting properties of probability distributions

Non-myopic strategies in prediction markets

Popularity, novelty and attention

Predicting trusts among users of online communities: an epinions case study

The complexity of forecast testing: abstract

Crowdsourcing and knowledge sharing: strategic user behavior on taskcn

Altruism, selfishness, and spite in traffic routing

Content Provider	ACM Digital Library
Author	Kempe, David Chen, Po-An
Abstract	In this paper, we study the price of anarchy of traffic routing, under the assumption that users are partially altruistic or spiteful. We model such behavior by positing that the "cost" perceived by a user is a linear combination of the actual latency of the route chosen (selfish component), and the increase in latency the user causes for others (altruistic component). We show that if all users have a coefficient of at least β > 0 for the altruistic component, then the price of anarchy is bounded by 1/β, for all network topologies, arbitrary commodities, and arbitrary semi-convex latency functions. We extend this result to give more precise bounds on the price of anarchy for specific classes of latency functions, even for β < 0 modeling spiteful behavior. In particular, we show that if all latency functions are linear, the price of anarchy is bounded by $4/(3+2β--β^{2}).$ We next study non-uniform altruism distributions, where different users may have different coefficients β. We prove that all such games, even with infinitely many types of players, have a Nash Equilibrium. We show that if the average of the coefficients for the altruistic components of all users is β, then the price of anarchy is bounded by 1/β, for single commodity parallel link networks, and arbitrary convex latency functions. In particular, this result generalizes, albeit non-constructively, the Stackelberg routing results of Roughgarden and of Swamy. More generally, we bound the price of anarchy based on the class of allowable latency functions, and as a corollary obtain tighter bounds for Stackelberg routing than a recent result of Swamy.
Starting Page	140
Ending Page	149
Page Count	10
File Format	PDF
ISBN	9781605581699
DOI	10.1145/1386790.1386816
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-07-08
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Anarchy Selfishness Routing Altruism Spite
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Better vaccination strategies for better people

Altruism, selfishness, and spite in traffic routing. In: Fortnow (2008)

Altruism, selfishness, and spite in traffic routing (2008)

Altruism and Its Impact on the Price of Anarchy

Comparative statics of altruism and spite (2008).

Altruism and selfishness in traffic routing (2007)

Selfishness, Altruism and Message Spreading in Mobile Social Networks

Comparative statics of altruism and spite (2006).

Healthy Selfishness and Pathological Altruism: Measuring Two Paradoxical Forms of Selfishness

Altruism, selfishness, and spite in traffic routing

Similar Documents

Better vaccination strategies for better people

Altruism, selfishness, and spite in traffic routing. In: Fortnow (2008)

Altruism, selfishness, and spite in traffic routing (2008)

Altruism and Its Impact on the Price of Anarchy

Comparative statics of altruism and spite (2008).

Altruism and selfishness in traffic routing (2007)

Selfishness, Altruism and Message Spreading in Mobile Social Networks

Comparative statics of altruism and spite (2006).

Healthy Selfishness and Pathological Altruism: Measuring Two Paradoxical Forms of Selfishness

Altruism, selfishness, and spite in traffic routing