Repository logo
  • Log In
    Log in via Symplectic to deposit your publication(s).
Repository logo
  • Communities & Collections
  • Research Outputs
  • Statistics
  • Log In
    Log in via Symplectic to deposit your publication(s).
  1. Home
  2. Faculty of Engineering
  3. Faculty of Engineering
  4. Games with congestion-averse utilities
 
  • Details
Games with congestion-averse utilities
OA Location
http://eprints.soton.ac.uk/267679/
Author(s)
Byde, Andrew
Polukarov, Mariya
Jennings, Nick
Type
Conference Paper
Abstract
Congestion games–in which players strategically choose from a set of ?resources? and derive utilities that depend on the congestion on each resource– are important in a wide range of applications. However, to date, such games have been constrained to use utility functions that are linear sums with respect to resources. To remove this restriction, this paper provides a significant generalisation to the case where a player?s payoff can be given by any real-valued function over the set of possible congestion vectors. Under reasonable assumptions on the structure of player strategy spaces, we constructively prove the existence of a pure strategy equilibrium for the very wide class of these generalised games in which player utility functions are congestion-averse–i.e., monotonic, submodular and independent of irrelevant alternatives. Although, as we show, these games do not admit a generalised ordinal potential function (and hence–the finite improvement property), any such game does possess a Nash equilibrium in pure strategies. A polynomial time algorithm for computing such an equilibrium is presented.
Date Issued
2009
Citation
2009, pp.220-232
URI
http://hdl.handle.net/10044/1/37013
URL
http://eprints.soton.ac.uk/267679/
Start Page
220
End Page
232
Identifier
http://eprints.soton.ac.uk/267679/
Source
Proc. 2nd Int. Sym. on Algorithmic Game Theory
Subjects
Artificial Intelligence & Image Processing
08 Information And Computing Sciences
Publication Status
Unpublished
About
Spiral Depositing with Spiral Publishing with Spiral Symplectic
Contact us
Open access team Report an issue
Other Services
Scholarly Communications Library Services
logo

Imperial College London

South Kensington Campus

London SW7 2AZ, UK

tel: +44 (0)20 7589 5111

Accessibility Modern slavery statement Cookie Policy

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science

  • Cookie settings
  • Privacy policy
  • End User Agreement
  • Send Feedback