In a Fisher market, the market maker sells m products to n potential agents. The agents submit their utility functions and money endowments to the market maker, who, upon receiving submitted information, derives market equilibrium prices and allocations of the products. Agents are self-interested entities who wish to maximize their utility, and they may misreport their private information for this purpose. The incentive ratio characterizes the extent to which strategic plays can increase an agent's utility. While agents do benefit by misreporting their private information, we show that the ratio of improvement by a unilateral strategic play is no more than two in markets with gross substitute utilities for the agents. Moreover, it can be pinned down to e1/e≈1.445 in Cobb-Douglas markets. For the Leontief markets in which products are complementary, we show that the incentive ratio is at most two as well.

We study the inefficiency of mixed Nash equilibria, expressed as the price of anarchy, of all-pay auctions in three different environments: combinatorial, multi-unit and single-item auctions. First, we consider item-bidding combinatorial auctions where m all-pay auctions run in parallel, one for each good. For fractionally subadditive valuations, we strengthen the upper bound from 2 (Syrgkanis and Tardos in Proceedings of the 45th symposium on theory of computing (STOC ’13), 2013) to 1.82 by proving some structural properties that characterize the mixed Nash equilibria of the game. Next, we design an all-pay mechanism with a randomized allocation rule for the multi-unit auction. We show that, for bidders with submodular valuations, the mechanism admits a unique, $$75\%$$ efficient, pure Nash equilibrium. The efficiency of this mechanism outperforms all the known bounds on the price of anarchy of mixed Nash equilibria in mechanisms used for multi-unit auctions. Finally, we analyze single-item all-pay auctions motivated by their connection to contests and show tight bounds on the price of anarchy with respect to social welfare, revenue and maximum bid.

In a Fisher market game, a market equilibrium is computed in terms of the utility functions and money endowments that agents reported. As a consequence, an individual buyer may misreport his private information to obtain a utility gain. We investigate the extent to which an agent's utility can be increased by unilateral strategic plays and prove that the percentage of this improvement is at most 2 for markets with weak gross substitute utilities. Equivalently, we show that truthfully reporting is a 0.5-approximate Nash equilibrium in this game. To identify sufficient conditions for truthfully reporting being close to Nash equilibrium, we conduct a parameterized study on strategic behaviors and further show that the ratio of utility gain decreases linearly as buyer's initial endowment increases or his maximum share of an item decreases. Finally, we consider collusive behavior of a coalition and prove that the utility gain is bounded by 1/(1 - maximum share of the collusion). Our findings justify the truthful reporting assumption in Fisher markets by a quantitative study on participants incentive, and imply that under large market assumption, the utility gain of a buyer from manipulations diminishes to 0.

We consider the problem of revenue maximization on multi‐unit auctions where items are distinguished by their relative values; any pair of items has the same ratio of values to all buyers. As is common in the study of revenue maximizing problems, we assume that buyers' valuations are drawn from public known distributions and they have additive valuations for multiple items. Our problem is well motivated by sponsored search auctions, which made money for Google and Yahoo! in practice. In this auction, each advertiser bids an amount bi to compete for ad slots on a web page. The value of each ad slot corresponds to its click‐through‐rate, and each buyer has her own per‐click valuations, which is her private information. Obviously, a strategic bidder may bid an amount that is different with her true valuation to improve her utility. Our goal is to design truthful mechanisms avoiding this misreporting. We develop the optimal (with maximum revenue) truthful auction for a relaxed demand model (where each buyer i wants at most di items) and a sharp demand model (where buyer i wants exactly di items). We also find an auction that always guarantees at least half of the revenue of the optimal auction when the buyers are budget constrained. Moreover, all of the auctions we design can be computed efficiently, that is, in polynomial time.

We study the efficiency of the proportional allocation mechanism that is widely used to allocate divisible resources. Each agent submits a bid for each divisible resource and receives a fraction proportional to her bids. We quantify the inefficiency of Nash equilibria by studying the Price of Anarchy (PoA) of the induced game under complete and incomplete information. When agents’ valuations are concave, we show that the Bayesian Nash equilibria can be arbitrarily inefficient, in contrast to the well-known 4/3 bound for pure equilibria Johari and Tsitsiklis (Math. Oper. Res. 29 (3), 407–435 2004 ). Next, we upper bound the PoA over Bayesian equilibria by 2 when agents’ valuations are subadditive, generalizing and strengthening previous bounds on lattice submodular valuations. Furthermore, we show that this bound is tight and cannot be improved by any simple or scale-free mechanism. Then we switch to settings with budget constraints, and we show an improved upper bound on the PoA over coarse-correlated equilibria. Finally, we prove that the PoA is exactly 2 for pure equilibria in the polyhedral environment.