Quantitative Fairness Games

Details Quantitative Fairness Games Quantitative Fairness Games

2010-06-26

arxiv.org/abs/1006.5097v1

EPTCS 28, 2010, pp. 48-63

Computer Science

Computer Science and Game Theory

Scientific paper

10.4204/EPTCS.28.4

We consider two-player games played on finite colored graphs where the goal is the construction of an infinite path with one of the following frequency-related properties: (i) all colors occur with the same asymptotic frequency, (ii) there is a constant that bounds the difference between the occurrences of any two colors for all prefixes of the path, or (iii) all colors occur with a fixed asymptotic frequency. These properties can be viewed as quantitative refinements of the classical notion of fair path in a concurrent system, whose simplest form checks whether all colors occur infinitely often. In particular, the first two properties enforce equal treatment of all the jobs involved in the system, while the third one represents a way to assign a given priority to each job. For all the above goals, we show that the problem of checking whether there exists a winning strategy is CoNP-complete.

Affiliated with

Also associated with

No associations

Rating

Quantitative Fairness Games 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 Quantitative Fairness Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantitative Fairness Games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-525565