Worst-Case Nash Equilibria in Restricted Routing

We study the network routing problem with restricted and related links.There are parallel links with possibly different speeds,between a source and a sink.Also there are users,and each user has a traffic of some weight to assign to one of the links from a subset of all the links,named his/her allowable set.The users choosing the same link suffer the same delay,which is equal to the total weight assigned to that link over its speed.A state of the system is called a Nash equilibrium if no user can decrease his/her delay by unilaterally changing his/her link.To measure the performance degradation of the system due to the selfish behavior of all the users,Koutsoupias and Papadimitriou proposed the notion Price of Anarchy (denoted by PoA),which is the ratio of the maximum delay in the worst-case Nash equilibrium and in an optimal solution.The PoA for this restricted related model has been studied,and a linear lower bound was obtained.However in their bad instance,some users can only use extremely slow links.This is a little artificial and unlikely to appear in a real world.So in order to better understand this model,we introduce a parameter for the system,and prove a better Price of Anarchy in terms of the parameter.We also show an important application of our result in coordination mechanism design for task scheduling game.We propose a new coordination mechanism,Group-Makespan,for unrelated selfish task scheduling game with improved price of anarchy.     

Envy-Free Pricing with General Supply Constraints for Unit Demand Consumers

The envy-free pricing problem can be stated as finding a pricing and allocation scheme in which each consumer is allocated a set of items that maximize his/her utility under the pricing.The goal is to maximize seller revenue.We study the problem with general supply constraints which are given as an independence system defined over the items.The constraints,for example,can be a number of linear constraints or matroids.This captures the situation where items do not pre-exist,but are produced in reflection of consumer valuation of the items under the limit of resources.This paper focuses on the case of unit-demand consumers.In the setting,there are n consumers and m items;each item may be produced in multiple copies.Each consumer i ∈ [n] has a valuation vij on item j in the set Si in which he/she is interested.He/she must be allocated (if any) an item which gives the maximum (non-negative) utility.Suppose we are given an α-approximation oracle for finding the maximum weight independent set for the given independence system (or a slightly stronger oracle);for a large number of natural and interesting supply constraints,constant approximation algorithms are available.We obtain the following results.1) O(α log n)-approximation for the general case.2) O(αk)-approximation when each consumer is interested in at most k distinct types of items.3) O(αf)-approximation when each type of item is interesting to at most f consumers.Note that the final two results were previously unknown even without the independence system constraint.