enter search term and/or author name
∃R-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria
Jugal Garg, Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod
Article No.: 1
As a result of a series of important works [7--9, 15, 23], the complexity of two-player Nash equilibrium is by now well understood, even when equilibria with special properties are desired and when the game is symmetric. However, for multi-player...
We study pricing equilibria for graphical valuations, whichare a class of valuations that admit a compact representation. These valuations are associated with a value graph, whose nodes correspond to items, and edges encode (pairwise)...
The Random Assignment Problem with Submodular Constraints on Goods
Satoru Fujishige, Yoshio Sano, Ping Zhan
Article No.: 3
Problems of allocating indivisible goods to agents in an efficient and fair manner without money have long been investigated in literature. The random assignment problem is one of them, where we are given a fixed feasible (available) set of...
Competitive Packet Routing with Priority Lists
Tobias Harks, Britta Peis, Daniel Schmand, Bjoern Tauer, Laura Vargas Koch
Article No.: 4
In competitive packet routing games, the packets are routed selfishly through a network and scheduling policies at edges determine which packets are forwarded first if there is not enough capacity on an edge to forward all packets at once. We...