Efficient Equilibria in Polymatrix Coordination Games

We consider polymatrix coordination games with individual preferences where every player corresponds to a node in a graph who plays with each neighbor a separate bimatrix game with non-negative symmetric payoffs. In this paper, we study $alpha$-approximate $k$-equilibria of these games, i.e., outcomes where no group of at most $k$ players can deviate such that each member increases his payoff by at least a factor $alpha$. We prove that for $alpha ge 2$ these games have the finite coalitional improvement property (and thus $alpha$-approximate $k$-equilibria exist), while for $alpha < 2$ this property does not hold. Further, we derive an almost tight bound of $2alpha(n-1)/(k-1)$ on the price of anarchy, where $n$ is the number of players; in particular, it scales from unbounded for pure Nash equilibria ($k = 1)$ to $2alpha$ for strong equilibria ($k = n$). We also settle the complexity of several problems related to the verification and existence of these equilibria. Finally, we investigate natural means to reduce the inefficiency of Nash equilibria. Most promisingly, we show that by fixing the strategies of $k$ players the price of anarchy can be reduced to $n/k$ (and this bound is tight).

On the Inefficiency of Standard Multi-Unit Auctions

We study two standard multi-unit auction formats for allocating multiple units of a single good to multi-demand bidders. The first one is the Discriminatory Auction, which charges every winner his winning bids. The second is the Uniform Price Auction, which determines a uniform price to be paid per unit. Variants of both formats find applications ranging from the allocation of state bonds to investors, to online sales over the internet, facilitated by popular online brokers. For these formats, we consider two bidding interfaces: (i) standard bidding, which is most prevalent in the scientific literature, and (ii) uniform bidding, which is more popular in practice. In this work, we evaluate the economic inefficiency of both multi-unit auction formats for both bidding interfaces, by means of upper and lower bounds on the Price of Anarchy for pure Nash equilibria and mixed Bayes-Nash equilibria. Our developments improve significantly upon bounds that have been obtained recently in [Markakis, Telelis, ToCS 2014] and [Syrgkanis, Tardos, STOC 2013] for submodular valuation functions. Moreover, we consider for the first time bidders with subadditive valuation functions for these auction formats. Our results signify that these auctions are nearly efficient, which provides further justification for their use in practice.