Broadcast in Ad hoc Wireless Networks with Selfish Nodes: A Bayesian Incentive Compatibility Approach

We consider the incentive compatible broadcast (ICB) problem in ad hoc wireless networks with selfish nodes. We design a Bayesian incentive compatible Broadcast (BIC-B) protocol to address this problem. VCG mechanism based schemes have been popularly used in the literature to design dominant strategy incentive compatible (DSIC) protocols for ad hoe wireless networks. VCG based mechanisms have two critical limitations: (i) the network is required to he bi-connected, (ii) the resulting protocol is not budget balanced. Our proposed BIC-B protocol overcomes these difficulties. We also prove the optimality of the proposed scheme.

Broadcast in Adhoc Wireless Networks with Selfish Nodes: A Bayesian Incentive Compatibility Approach

We consider the incentive compatible broadcast (ICB) problem in ad hoc wireless networks with selfish nodes. We design a Bayesian incentive compatible broadcast (BIC-B) protocol to address this problem. VCG mechanism based schemes have been popularly used in the literature to design dominant strategy incentive compatible (DSIC) protocols for ad hoc wireless networks. VCG based mechanisms have two critical limitations: (i) the network is required to be bi-connected, (ii) the resulting protocol is not budget balanced. Our proposed BIC-B protocol overcomes these difficulties. We also prove the optimality of the proposed scheme.

Continuity and Incentive Compatibility in Cardinal Voting Mechanisms

We show that every cardinal incentive compatible voting mechanism satisfying a continuity condition, must be ordinal. Our results apply to many standard models in mechanism design without transfers, including the standard voting models with any domain restrictions.

Contract enforcement and incentive compatibility in large economies with differential information: the role of exact feasibility

We consider exchange economies with a continuum of agents and differential information about finitely many states of nature. It was proved in Einy, Moreno and Shitovitz (2001) that if we allow for free disposal in the market clearing (feasibility) constraints then an irreducible economy has a competitive (or Walrasian expectations) equilibrium, and moreover, the set of competitive equilibrium allocations coincides with the private core. However when feasibility is defined with free disposal, competitive equilibrium allocations may not be incentive compatible and contracts may not be enforceable (see e.g. Glycopantis, Muir and Yannelis (2002)). This is the main motivation for considering equilibrium solutions with exact feasibility. We first prove that the results in Einy et al. (2001) are still valid without free-disposal. Then we define an incentive compatibility property motivated by the issue of contracts’ execution and we prove that every Pareto optimal exact feasible allocation is incentive compatible, implying that contracts of a competitive or core allocations are enforceable.

A Bayesian incentive compatible mechanism for decentralized supply chain formation

In this paper we consider a decentralized supply chain formation problem for linear multi-echelon supply chains when the managers of the individual echelons are autonomous, rational, and intelligent. At each echelon, there is a choice of service providers and the specific problem we solve is that of determining a cost-optimal mix of service providers so as to achieve a desired level of end-to-end delivery performance. The problem can be broken up into two sub-problems following a mechanism design approach: (1) Design of an incentive compatible mechanism to elicit the true cost functions from the echelon managers; (2) Formulation and solution of an appropriate optimization problem using the true cost information. In this paper we propose a novel Bayesian incentive compatible mechanism for eliciting the true cost functions. This improves upon existing solutions in the literature which are all based on the classical Vickrey-Clarke-Groves mechanisms, requiring significant incentives to be paid to the echelon managers for achieving dominant strategy incentive compatibility. The proposed solution, which we call SCF-BIC (Supply Chain Formation with Bayesian Incentive Compatibility), significantly reduces the cost of supply chain formation. We illustrate the efficacy of the proposed methodology using the example of a three echelon manufacturing supply chain.

Incentive Compatible Mechanisms for Resource Procurement in Computational Grids with Rational resource Providers

In a computational grid, the presence of grid resource providers who are rational and intelligent could lead to an overall degradation in the efficiency of the grid. In this paper, we design incentive compatible grid resource procurement mechanisms which ensure that the efficiency of the grid is not affected by the rational behavior of resource providers.In particular, we offer three elegant incentive compatible mechanisms for this purpose: (1) G-DSIC (Grid-Dominant Strategy Incentive Compatible) mechanism (2) G-BIC (Grid-Bayesian Nash Incentive Compatible) mechanism (3) G-OPT(Grid-Optimal) mechanism which minimizes the cost to the grid user, satisfying at the same time, (a) Bayesian incentive compatibility and (b) individual rationality. We evaluate the relative merits and demerits of the above three mechanisms using game theoretical analysis and numerical experiments.

Incentive Compatible Influence Maximization in Social Networks with Application to Viral Marketing

Information diffusion and influence maximization are important and extensively studied problems in social networks. Various models and algorithms have been proposed in the literature in the context of the influence maximization problem. A crucial assumption in all these studies is that the influence probabilities are known to the social planner. This assumption is unrealistic since the influence probabilities are usually private information of the individual agents and strategic agents may not reveal them truthfully. Moreover, the influence probabilities could vary significantly with the type of the information flowing in the network and the time at which the information is propagating in the network. In this paper, we use a mechanism design approach to elicit influence probabilities truthfully from the agents. Our main contribution is to design a scoring rule based mechanism in the context of the influencer-influencee model. In particular, we show the incentive compatibility of the mechanisms and propose a reverse weighted scoring rule based mechanism as an appropriate mechanism to use.

Sharing the Cost of a Public Good: an Incentive-Constrained Axiomatic Approach

We study the problem of provision and cost-sharing of a public good in large economies where exclusion, complete or partial, is possible. We search for incentive-constrained efficient allocation rules that display fairness properties. Population monotonicity says that an increase in population should not be detrimental to anyone. Demand monotonicity states that an increase in the demand for the public good (in the sense of a first-order stochastic dominance shift in the distribution of preferences) should not be detrimental to any agent whose preferences remain unchanged. Under suitable domain restrictions, there exists a unique incentive-constrained efficient and demand-monotonic allocation rule: the so-called serial rule. In the binary public good case, the serial rule is also the only incentive-constrained efficient and population-monotonic rule.

(Minimally) 'epsilon'-incentive compatible competitive equilibria in economies with indivisibilities

We consider competitive and budget-balanced allocation rules for problems where a number of indivisible objects and a fixed amount of money is allocated among a group of agents. In 'small' economies, we identify under classical preferences each agent's maximal gain from manipulation. Using this result we find the competitive and budget-balanced allocation rules which are minimally manipulable for each preference profile in terms of any agent's maximal gain. If preferences are quasi-linear, then we can find a competitive and budget-balanced allocation rule such that for any problem, the maximal utility gain from manipulation is equalized among all agents.

An Optimal Mechanism for Sponsored Search Auctions on the Web and Comparison With Other Mechanisms

In this paper, we first describe a framework to model the sponsored search auction on the web as a mechanism design problem. Using this framework, we describe two well-known mechanisms for sponsored search auction-Generalized Second Price (GSP) and Vickrey-Clarke-Groves (VCG). We then derive a new mechanism for sponsored search auction which we call optimal (OPT) mechanism. The OPT mechanism maximizes the search engine's expected revenue, while achieving Bayesian incentive compatibility and individual rationality of the advertisers. We then undertake a detailed comparative study of the mechanisms GSP, VCG, and OPT. We compute and compare the expected revenue earned by the search engine under the three mechanisms when the advertisers are symmetric and some special conditions are satisfied. We also compare the three mechanisms in terms of incentive compatibility, individual rationality, and computational complexity. Note to Practitioners-The advertiser-supported web site is one of the successful business models in the emerging web landscape. When an Internet user enters a keyword (i.e., a search phrase) into a search engine, the user gets back a page with results, containing the links most relevant to the query and also sponsored links, (also called paid advertisement links). When a sponsored link is clicked, the user is directed to the corresponding advertiser's web page. The advertiser pays the search engine in some appropriate manner for sending the user to its web page. Against every search performed by any user on any keyword, the search engine faces the problem of matching a set of advertisers to the sponsored slots. In addition, the search engine also needs to decide on a price to be charged to each advertiser. Due to increasing demands for Internet advertising space, most search engines currently use auction mechanisms for this purpose. These are called sponsored search auctions. A significant percentage of the revenue of Internet giants such as Google, Yahoo!, MSN, etc., comes from sponsored search auctions. In this paper, we study two auction mechanisms, GSP and VCG, which are quite popular in the sponsored auction context, and pursue the objective of designing a mechanism that is superior to these two mechanisms. In particular, we propose a new mechanism which we call the OPT mechanism. This mechanism maximizes the search engine's expected revenue subject to achieving Bayesian incentive compatibility and individual rationality. Bayesian incentive compatibility guarantees that it is optimal for each advertiser to bid his/her true value provided that all other agents also bid their respective true values. Individual rationality ensures that the agents participate voluntarily in the auction since they are assured of gaining a non-negative payoff by doing so.

Design of an optimal auction for sponsored search auctions

In this paper we first describe a framework to model the sponsored search auction on the web as a mechanism design problem. Using this framework, we design a novel auction which we call the OPT (optimal) auction. The OPT mechanism maximizes the search engine's expected revenue while achieving Bayesian incentive compatibility and individual rationality of the advertisers. We show that the OPT mechanism is superior to two of the most commonly used mechanisms for sponsored search namely (1) GSP (Generalized Second Price) and (2) VCG (Vickrey-Clarke-Groves). We then show an important revenue equivalence result that the expected revenue earned by the search engine is the same for all the three mechanisms provided the advertisers are symmetric and the number of sponsored slots is strictly less than the number of advertisers.

Optimal auctions for multi-unit procurement with volume discount bids

Our attention, is focused on designing an optimal procurement mechanism which a buyer can use for procuring multiple units of a homogeneous item based on bids submitted by autonomous, rational, and intelligent suppliers. We design elegant optimal procurement mechanisms for two different situations. In the first situation, each supplier specifies the maximum quantity that can be supplied together with a per unit price. For this situation, we design an optimal mechanism S-OPT (Optimal with Simple bids). In the more generalized case, each supplier specifies discounts based on the volume of supply. In this case, we design an optimal mechanism VD-OPT (Optimal with Volume Discount, bids). The VD-OPT mechanism uses the S-OPT mechanism as a building block. The proposed mechanisms minimize the cost to the buyer, satisfying at the same time, (a) Bayesian, incentive compatibility and (b) interim individual rationality.