Academic literature on the topic 'Dominant Strategy Incentive Compatibility (DSIC)'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Dominant Strategy Incentive Compatibility (DSIC).'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Journal articles on the topic "Dominant Strategy Incentive Compatibility (DSIC)"
1
Lerner, Anat, and Rica Gonen. "Efficient Constrained Combinatorial Auctions." International Game Theory Review 18, no. 03 (August 24, 2016): 1650007. http://dx.doi.org/10.1142/s0219198916500079.
Full textAbstract:
The seminal work by Green and Laffont [(1977) characterization of satisfactory mechanisms for the revelation of preferences for public goods, Econometrica 45, 427–438] shows that efficient mechanisms with Vickrey–Clarke–Groves prices satisfy the properties of dominant-strategy incentive compatible (DSIC) and individually rational in the quasilinear utilities model. Nevertheless in many real-world situations some players have a gap between their willingness to pay and their ability to pay, i.e., a budget. We show that once budgets are integrated into the model then Green and Laffont’s theorem ceases to apply. More specifically, we show that even if only a single player has budget constraints then there is no deterministic efficient mechanism that satisfies the individual rationality and DSIC properties. Furthermore, in a quasilinear utilities model with [Formula: see text] nonidentical items and [Formula: see text] players with multidimensional types, we characterize the sufficient and necessary conditions under which Green and Laffont’s theorem holds in the presence of budget-constrained players. Interestingly our characterization is similar in spirit to that of Maskin [(2000) Auctions, development and privatization: Efficient auctions with liquidity-constrained buyers, Eur. Econ. Rev. 44, 667–681] for Bayesian single-item constrained-efficiency auctions.
2
Manelli, Alejandro M., and Daniel R. Vincent. "Dominant-strategy and Bayesian incentive compatibility in multi-object trading environments." Journal of Mathematical Economics 82 (May 2019): 214–26. http://dx.doi.org/10.1016/j.jmateco.2019.03.002.
Full text
3
Gerstgrasser, Matthias, Paul W. Goldberg, Bart De Keijzer, Philip Lazos, and Alexander Skopalik. "Multi-Unit Bilateral Trade." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 1973–80. http://dx.doi.org/10.1609/aaai.v33i01.33011973.
Full textAbstract:
We characterise the set of dominant strategy incentive compatible (DSIC), strongly budget balanced (SBB), and ex-post individually rational (IR) mechanisms for the multi-unit bilateral trade setting. In such a setting there is a single buyer and a single seller who holds a finite number k of identical items. The mechanism has to decide how many units of the item are transferred from the seller to the buyer and how much money is transferred from the buyer to the seller. We consider two classes of valuation functions for the buyer and seller: Valuations that are increasing in the number of units in possession, and the more specific class of valuations that are increasing and submodular.Furthermore, we present some approximation results about the performance of certain such mechanisms, in terms of social welfare: For increasing submodular valuation functions, we show the existence of a deterministic 2-approximation mechanism and a randomised e/(1 − e) approximation mechanism, matching the best known bounds for the single-item setting.
4
Lundy, Taylor, and Hu Fu. "Limitations of Incentive Compatibility on Discrete Type Spaces." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 02 (April 3, 2020): 2136–43. http://dx.doi.org/10.1609/aaai.v34i02.5588.
Full textAbstract:
In the design of incentive compatible mechanisms, a common approach is to enforce incentive compatibility as constraints in programs that optimize over feasible mechanisms. Such constraints are often imposed on sparsified representations of the type spaces, such as their discretizations or samples, in order for the program to be manageable. In this work, we explore limitations of this approach, by studying whether all dominant strategy incentive compatible mechanisms on a set T of discrete types can be extended to the convex hull of T.Dobzinski, Fu and Kleinberg (2015) answered the question affirmatively for all settings where types are single dimensional. It is not difficult to show that the same holds when the set of feasible outcomes is downward closed. In this work we show that the question has a negative answer for certain non-downward-closed settings with multi-dimensional types. This result should call for caution in the use of the said approach to enforcing incentive compatibility beyond single-dimensional preferences and downward closed feasible outcomes.
5
Loertscher, Simon, and Claudio Mezzetti. "A dominant strategy double clock auction with estimation‐based tâtonnement." Theoretical Economics 16, no. 3 (2021): 943–78. http://dx.doi.org/10.3982/te3311.
Full textAbstract:
The price mechanism is fundamental to economics but difficult to reconcile with incentive compatibility and individual rationality. We introduce a double clock auction for a homogeneous good market with multidimensional private information and multiunit traders that is deficit‐free, ex post individually rational, constrained efficient, and makes sincere bidding a dominant strategy equilibrium. Under a weak dependence and an identifiability condition, our double clock auction is also asymptotically efficient. Asymptotic efficiency is achieved by estimating demand and supply using information from the bids of traders that have dropped out and following a tâtonnement process that adjusts the clock prices based on the estimates.
6
Baisa, Brian. "Efficient multiunit auctions for normal goods." Theoretical Economics 15, no. 1 (2020): 361–413. http://dx.doi.org/10.3982/te3430.
Full textAbstract:
I study multiunit auction design when bidders have private values, multiunit demands, and non‐quasilinear preferences. Without quasilinearity, the Vickrey auction loses its desired incentive and efficiency properties. I give conditions under which we can design a mechanism that retains the Vickrey auction's desirable incentive and efficiency properties: (1) individual rationality, (2) dominant strategy incentive compatibility, and (3) Pareto efficiency. I show that there is a mechanism that retains the desired properties of the Vickrey auction if there are two bidders who have single‐dimensional types. I also present an impossibility theorem that shows that there is no mechanism that satisfies Vickrey's desired properties and weak budget balance when bidders have multidimensional types.
7
Gonen, Rica, and Anat Lerner. "The Incompatibility of Pareto Optimality and Dominant-Strategy Incentive Compatibility in Sufficiently-Anonymous Budget-Constrained Quasilinear Settings." Games 4, no. 4 (November 18, 2013): 690–710. http://dx.doi.org/10.3390/g4040690.
Full text
8
Lopomo, Giuseppe, Nicola Persico, and Alessandro T. Villa. "Optimal Procurement with Quality Concerns." American Economic Review 113, no. 6 (June 1, 2023): 1505–29. http://dx.doi.org/10.1257/aer.20211437.
Full textAbstract:
Adverse selection in procurement arises when low-cost bidders are also low-quality suppliers. We propose a mechanism called LoLA (lowball lottery auction) which, under some conditions, maximizes any combination of buyer’s and social surplus, subject to incentive compatibility, in the presence of adverse selection. The LoLA features a floor price, and a reserve price. The LoLA has a dominant strategy equilibrium that, under mild conditions, is unique. In a counterfactual analysis of Italian government auctions, we compute the gain that the government could have made, had it used the optimal procurement mechanism (a LoLA), relative to a first-price auction (the adopted format). (JEL D44, D82, H57, L14)
9
"Book Reviews." Journal of Economic Literature 54, no. 2 (June 1, 2016): 589–91. http://dx.doi.org/10.1257/jel.54.2.589.r1.
Full textAbstract:
Dimitrios Diamantaras of Temple University reviews “An Introduction to the Theory of Mechanism Design,” by Tilman Börgers. The Econlit abstract of this book begins: “Presents explanations of classic results in the theory of mechanism design and examines the frontiers of research in mechanism design in a text written for advanced undergraduate and graduate students of economics who have a good understanding of game theory. Discusses screening; examples of Bayesian mechanism design; examples of dominant strategy mechanisms; incentive compatibility; Bayesian mechanism design; dominant strategy mechanisms; nontransferable utility; informational interdependence; robust mechanism design; and dynamic mechanism design. Börgers is Samuel Zell Professor of the Economics of Risk at the University of Michigan.”
10
Witkowski, Jens, Rupert Freeman, Jennifer Wortman Vaughan, David M. Pennock, and Andreas Krause. "Incentive-Compatible Forecasting Competitions." Management Science, May 17, 2022. http://dx.doi.org/10.1287/mnsc.2022.4410.
Full textAbstract:
We initiate the study of incentive-compatible forecasting competitions in which multiple forecasters make predictions about one or more events and compete for a single prize. We have two objectives: (1) to incentivize forecasters to report truthfully and (2) to award the prize to the most accurate forecaster. Proper scoring rules incentivize truthful reporting if all forecasters are paid according to their scores. However, incentives become distorted if only the best-scoring forecaster wins a prize, since forecasters can often increase their probability of having the highest score by reporting more extreme beliefs. In this paper, we introduce two novel forecasting competition mechanisms. Our first mechanism is incentive compatible and guaranteed to select the most accurate forecaster with probability higher than any other forecaster. Moreover, we show that in the standard single-event, two-forecaster setting and under mild technical conditions, no other incentive-compatible mechanism selects the most accurate forecaster with higher probability. Our second mechanism is incentive compatible when forecasters’ beliefs are such that information about one event does not lead to belief updates on other events, and it selects the best forecaster with probability approaching one as the number of events grows. Our notion of incentive compatibility is more general than previous definitions of dominant strategy incentive compatibility in that it allows for reports to be correlated with the event outcomes. Moreover, our mechanisms are easy to implement and can be generalized to the related problems of outputting a ranking over forecasters and hiring a forecaster with high accuracy on future events. This paper was accepted by Yan Chen, behavioral economics and decision analysis.
Dissertations / Theses on the topic "Dominant Strategy Incentive Compatibility (DSIC)"
1
Schlake, Farimehr. "Optimal Consumer-Centric Delay-Efficient Security Management in Multi-Agent Networks: A Game and Mechanism Design Theoretic Approach." Diss., Virginia Tech, 2012. http://hdl.handle.net/10919/77362.
Full textAbstract:
The main aspiration behind the contributions of this research work is the achievement of simultaneuos delay-efficiency, autonomy, and security through innovative protocol design to address complex real-life problems. To achieve this, we take a holistic approach. We apply theoretical mathematical modeling implementing implications of social-economic behavioral characteristics to propose a cross-layer network security protocol. We further complement this approach by a layer-specific focus with implementations at two lower OSI layers.
For the cross-layer design, we suggest the use of game and mechanism design theories. We design a network-wide consumer-centric and delay-efficient security protocol, DSIC-S. It induces a Dominant Strategy Incentive Compatible equilibrium among all rational and selfish nodes. We prove it is network-wide socially desirable and Pareto optimal. We address resource management and delay-efficiency through synergy of several design aspects. We propose a scenario-based security model with different levels. Furthermore, we design a valuation system to integrate the caused delay in selection of security algorithms at each node without consumer's knowledge of the actual delays. We achieve this by incorporating the consumer's valuation system, in the calculation of the credit transfers through the Vickrey-Clarke-Groves (VCG) payments with Clarke's pivotal rule. As the utmost significant contribution of this work, we solve the revelation theorem's problem of misrepresentation of agents' private information in mechanism design theory through the proposed design. We design an incentive model and incorporate the valuations in the incentives. The simulations validate the theoretical results. They prove the significance of this model and among others show the correlation of the credit transfers to actual delays and security valuations.
In the layer-specific approach for the network-layer, we implement the DSIC-S protocol to extend current IPsec and IKEv2 protocols. IPsec-O and IKEv2-O inherit the strong properties of DSIC-S through the proposed extensions.
Furthermore, we propose yet another layer-specific protocol, the SME_Q, for the datalink layer based on ATM. We develop an extensive simulation software, SMEQSIM, to simulate ATM security negotiations. We simulate the proposed protocol in a comprehensive real-life ATM network and prove the significance of this research work.Ph. D.
2
Udaya, Lakshmi L. "Design Of Truthful Allocation Mechanisms For Carbon Footprint Reduction." Thesis, 2012. https://etd.iisc.ac.in/handle/2005/2322.
Full textAbstract:
Global warming is currently a major challenge faced by the world. Reduction of carbon emissions is of paramount importance in the context of global warming. There are widespread ongoing efforts to find satisfactory ways of surmounting this challenge. The basic objective of all such efforts can be summarized as conception and formation of protocols to reduce the pace of global carbon levels. Countries and global companies are now engaged in understanding systematic ways of achieving
well defined emission targets. In this dissertation, we explore the specific problem faced by a global industry or global company in allocating carbon emission reduction units to its different divisions and supply chain partners in achieving a required target of reductions in its carbon reduction program. The problem becomes a challenging one since the divisions and supply chain partners are often autonomous and could exhibit strategic behavior. Game theory and mechanism design provide a natural modeling tool for capturing the strategic dynamics involved in this problem.
DSIC (Dominant Strategy Incentive Compatibility), AE (Allocative Efficiency), and SBB (Strict Budget Balance) are the key desirable properties for carbon reduction allocation mechanisms.
But due to an impossibility result in mechanism design, DSIC, AE, and SBB can never be simultaneously achieved. Hence in this dissertation, we offer as contributions, two elegant solutions to this carbon emission reduction allocation problem. The first contribution is a mechanism which is DSIC and AE. We first propose a straightforward Vickrey-Clarke-Groves (VCG) mechanism based solution to the problem, leading to a DSIC and AE reverse auction protocol for allocating carbon reductions among the divisions. This solution, however, leads to a high level of budget imbalance. To reduce budget imbalance, we use redistribution mechanisms, without affecting the key properties of DSIC and AE. The Cavallo-Bailey redistribution mechanism, when applied to the above reverse auction protocol leads to reduced budget imbalance. To reduce the imbalance further, we propose an innovative forward auction protocol which achieves less imbalance when combined with the Cavallo-Bailey redistribution mechanism. The forward auction protocol also has the appealing feature of handsomely rewarding divisions that reduce emissions and levying appropriate penalties on divisions that do not participate in emission reductions.
The second contribution is a DSIC and SBB mechanism. Even though the first mechanism tries to reduce the budget imbalance, there is always a surplus which cannot be distributed among divisions and is wasted. So, in this part, by slightly compromising on efficiency, we propose a mechanism which is DSIC and SBB. The SBB property guarantees that there is no need for any monetary support from an external agency for implementing the mechanism and there is no leakage of revenue.
3
Udaya, Lakshmi L. "Design Of Truthful Allocation Mechanisms For Carbon Footprint Reduction." Thesis, 2012. http://etd.iisc.ernet.in/handle/2005/2322.
Full textAbstract:
Global warming is currently a major challenge faced by the world. Reduction of carbon emissions is of paramount importance in the context of global warming. There are widespread ongoing efforts to find satisfactory ways of surmounting this challenge. The basic objective of all such efforts can be summarized as conception and formation of protocols to reduce the pace of global carbon levels. Countries and global companies are now engaged in understanding systematic ways of achieving
well defined emission targets. In this dissertation, we explore the specific problem faced by a global industry or global company in allocating carbon emission reduction units to its different divisions and supply chain partners in achieving a required target of reductions in its carbon reduction program. The problem becomes a challenging one since the divisions and supply chain partners are often autonomous and could exhibit strategic behavior. Game theory and mechanism design provide a natural modeling tool for capturing the strategic dynamics involved in this problem.
DSIC (Dominant Strategy Incentive Compatibility), AE (Allocative Efficiency), and SBB (Strict Budget Balance) are the key desirable properties for carbon reduction allocation mechanisms.
But due to an impossibility result in mechanism design, DSIC, AE, and SBB can never be simultaneously achieved. Hence in this dissertation, we offer as contributions, two elegant solutions to this carbon emission reduction allocation problem. The first contribution is a mechanism which is DSIC and AE. We first propose a straightforward Vickrey-Clarke-Groves (VCG) mechanism based solution to the problem, leading to a DSIC and AE reverse auction protocol for allocating carbon reductions among the divisions. This solution, however, leads to a high level of budget imbalance. To reduce budget imbalance, we use redistribution mechanisms, without affecting the key properties of DSIC and AE. The Cavallo-Bailey redistribution mechanism, when applied to the above reverse auction protocol leads to reduced budget imbalance. To reduce the imbalance further, we propose an innovative forward auction protocol which achieves less imbalance when combined with the Cavallo-Bailey redistribution mechanism. The forward auction protocol also has the appealing feature of handsomely rewarding divisions that reduce emissions and levying appropriate penalties on divisions that do not participate in emission reductions.
The second contribution is a DSIC and SBB mechanism. Even though the first mechanism tries to reduce the budget imbalance, there is always a surplus which cannot be distributed among divisions and is wasted. So, in this part, by slightly compromising on efficiency, we propose a mechanism which is DSIC and SBB. The SBB property guarantees that there is no need for any monetary support from an external agency for implementing the mechanism and there is no leakage of revenue.
4
Narayanam, Ramasuri. "Design Of Incentive Compatible Broadcast Protocols For Ad hoc Wireless Networks : A Game Theoretic Approach." Thesis, 2006. https://etd.iisc.ac.in/handle/2005/343.
Full textAbstract:
An ad hoc wireless network is an infrastructure-less, autonomous system of nodes connected through wireless links. In many current applications of ad hoc wireless networks, individual wireless nodes are autonomous, rational, and intelligent and are often referred to as selfish nodes, following game theoretic terminology. In an ad hoc wireless network, a typical node may be an intermediate node of a route from a source node to a destination node and therefore is often required to forward packets so as to enable communication to be established. Selfish nodes may not always forward the packets since the forwarding activity consumes the node’s own resources. Such behavior by individual nodes may lead to suboptimal situations where nodes, through their actions, lead to a state that is undesirable from an overall network viewpoint. To counter this, there is a need to stimulate cooperation through methods such as providing appropriate incentives. In this thesis, our interest is in designing rigorous incentive based methods for stimulating cooperation among wireless nodes, in the specific context of broadcast. In particular, we address the Incentive Compatible Broadcast problem: how do we design broadcast protocols that induce truth revelation by the individual wireless nodes? We do this using a game theory and mechanism design framework.
Incentive compatibility of broadcast protocols could manifest in two forms: (1) Dominant Strategy Incentive Compatibility (DSIC) (also called strategy-proofness) and (2) Bayesian incentive compatibility (BIC). A DSIC broadcast protocol is one which makes it a best response for every wireless node to reveal its true type, regardless of what the other nodes reveal. A BIC broadcast protocol is one which makes truth revelation a best response for a node, given that the other nodes are truthful. The DSIC property is stronger and more desirable but more difficult to achieve. On the other hand, the BIC property is much weaker and easier to achieve.
In this thesis, we first design a DSIC broadcast protocol for ad hoc networks using the well known VCG (Vickrey-Clarke-Groves) mechanisms and investigate its properties and performance. Next, we design a BIC broadcast protocol, investigate its properties, and compare its performance with that of the DSIC broadcast protocol. Both the protocols developed in this thesis provide an elegant solution to the incentive compatible broadcast problem in ad hoc networks with selfish nodes and help stimulate cooperation among the selfish wireless nodes.
5
Narayanam, Ramasuri. "Design Of Incentive Compatible Broadcast Protocols For Ad hoc Wireless Networks : A Game Theoretic Approach." Thesis, 2006. http://hdl.handle.net/2005/343.
Full textAbstract:
An ad hoc wireless network is an infrastructure-less, autonomous system of nodes connected through wireless links. In many current applications of ad hoc wireless networks, individual wireless nodes are autonomous, rational, and intelligent and are often referred to as selfish nodes, following game theoretic terminology. In an ad hoc wireless network, a typical node may be an intermediate node of a route from a source node to a destination node and therefore is often required to forward packets so as to enable communication to be established. Selfish nodes may not always forward the packets since the forwarding activity consumes the node’s own resources. Such behavior by individual nodes may lead to suboptimal situations where nodes, through their actions, lead to a state that is undesirable from an overall network viewpoint. To counter this, there is a need to stimulate cooperation through methods such as providing appropriate incentives. In this thesis, our interest is in designing rigorous incentive based methods for stimulating cooperation among wireless nodes, in the specific context of broadcast. In particular, we address the Incentive Compatible Broadcast problem: how do we design broadcast protocols that induce truth revelation by the individual wireless nodes? We do this using a game theory and mechanism design framework.
Incentive compatibility of broadcast protocols could manifest in two forms: (1) Dominant Strategy Incentive Compatibility (DSIC) (also called strategy-proofness) and (2) Bayesian incentive compatibility (BIC). A DSIC broadcast protocol is one which makes it a best response for every wireless node to reveal its true type, regardless of what the other nodes reveal. A BIC broadcast protocol is one which makes truth revelation a best response for a node, given that the other nodes are truthful. The DSIC property is stronger and more desirable but more difficult to achieve. On the other hand, the BIC property is much weaker and easier to achieve.
In this thesis, we first design a DSIC broadcast protocol for ad hoc networks using the well known VCG (Vickrey-Clarke-Groves) mechanisms and investigate its properties and performance. Next, we design a BIC broadcast protocol, investigate its properties, and compare its performance with that of the DSIC broadcast protocol. Both the protocols developed in this thesis provide an elegant solution to the incentive compatible broadcast problem in ad hoc networks with selfish nodes and help stimulate cooperation among the selfish wireless nodes.
6
Prakash, Hastagiri. "A Mechanism Design Approach To Resource Procurement In Computational Grids With Rational Resource Providers." Thesis, 2006. https://etd.iisc.ac.in/handle/2005/553.
Full textAbstract:
A computational grid is a hardware and software infrastructure that provides dependable, consistent, pervasive, and inexpensive access to high-end computational capabilities. In the presence of grid users who are autonomous, rational, and intelligent, there is an overall degradation of the total efficiency of the computational grid in comparison to what can be achieved when the participating users are centrally coordinated . This loss in efficiency might arise due to an unwillingness on the part of some of the grid resource providers to either not perform completely or not perform to the fullest capability, the computational jobs of other users in the grid.
In this thesis, our attention is focused on designing grid resource procurement mechanisms which a grid user can use for procuring resources in a computational grid based on bids submitted by autonomous, rational, and intelligent resource providers. Specifically, we follow a game theoretic and mechanism design approach to design three elegant, different incentive compatible procurement mechanisms for this purpose:
G-DSIC (Grid-Dominant Strategy Incentive Compatible) mechanism which guarantees
that truthful bidding is a best response for each resource provider, irrespective of what the other resource providers bid
G-BIC (Grid-Bayesian Nash Incentive Compatible) mechanism which only guarantees that truthful bidding is a best response for each resource provider whenever all other resource providers also bid truthfully
G-OPT (Grid-Optimal) mechanism which minimizes the cost to the grid user, satisfying at the same time, (1) Bayesian Incentive Compatibility (which guarantees that truthful bidding is a best response for each resource provider whenever all other resource providers also bid truthfully) and (2) Individual Rationality (which guarantees that the resource providers have non-negative payoffs if they participate in the bidding process).
We evaluate the relative merits and demerits of the above three mechanisms using game theoretical analysis and numerical experiments. The mechanisms developed in this thesis are in the context of parameter sweep type of jobs, which consist of multiple homogeneous and independent tasks. We believe the use of the mechanisms proposed transcends beyond parameter sweep type of jobs and in general, the proposed mechanisms could be extended to provide a robust way of procuring resources in a computational grid where the resource providers exhibit rational and strategic behavior.
7
Prakash, Hastagiri. "A Mechanism Design Approach To Resource Procurement In Computational Grids With Rational Resource Providers." Thesis, 2006. http://hdl.handle.net/2005/553.
Full textAbstract:
A computational grid is a hardware and software infrastructure that provides dependable, consistent, pervasive, and inexpensive access to high-end computational capabilities. In the presence of grid users who are autonomous, rational, and intelligent, there is an overall degradation of the total efficiency of the computational grid in comparison to what can be achieved when the participating users are centrally coordinated . This loss in efficiency might arise due to an unwillingness on the part of some of the grid resource providers to either not perform completely or not perform to the fullest capability, the computational jobs of other users in the grid.
In this thesis, our attention is focused on designing grid resource procurement mechanisms which a grid user can use for procuring resources in a computational grid based on bids submitted by autonomous, rational, and intelligent resource providers. Specifically, we follow a game theoretic and mechanism design approach to design three elegant, different incentive compatible procurement mechanisms for this purpose:
G-DSIC (Grid-Dominant Strategy Incentive Compatible) mechanism which guarantees
that truthful bidding is a best response for each resource provider, irrespective of what the other resource providers bid
G-BIC (Grid-Bayesian Nash Incentive Compatible) mechanism which only guarantees that truthful bidding is a best response for each resource provider whenever all other resource providers also bid truthfully
G-OPT (Grid-Optimal) mechanism which minimizes the cost to the grid user, satisfying at the same time, (1) Bayesian Incentive Compatibility (which guarantees that truthful bidding is a best response for each resource provider whenever all other resource providers also bid truthfully) and (2) Individual Rationality (which guarantees that the resource providers have non-negative payoffs if they participate in the bidding process).
We evaluate the relative merits and demerits of the above three mechanisms using game theoretical analysis and numerical experiments. The mechanisms developed in this thesis are in the context of parameter sweep type of jobs, which consist of multiple homogeneous and independent tasks. We believe the use of the mechanisms proposed transcends beyond parameter sweep type of jobs and in general, the proposed mechanisms could be extended to provide a robust way of procuring resources in a computational grid where the resource providers exhibit rational and strategic behavior.
Conference papers on the topic "Dominant Strategy Incentive Compatibility (DSIC)"
1
Li, Bin, Dong Hao, and Dengji Zhao. "Incentive-Compatible Diffusion Auctions." In Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}. California: International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/ijcai.2020/33.
Full textAbstract:
Diffusion auction is a new model in auction design. It can incentivize the buyers who have already joined in the auction to further diffuse the sale information to others via social relations, whereby both the seller's revenue and the social welfare can be improved. Diffusion auctions are essentially non-typical multidimensional mechanism design problems and agents' social relations are complicatedly involved with their bids. In such auctions, incentive-compatibility (IC) means it is best for every agent to honestly report her valuation and fully diffuse the sale information to all her neighbors. Existing work identified some specific mechanisms for diffusion auctions, while a general theory characterizing all incentive-compatible diffusion auctions is still missing. In this work, we identify a sufficient and necessary condition for all dominant-strategy incentive-compatible (DSIC) diffusion auctions. We formulate the monotonic allocation policies in such multidimensional problems and show that any monotonic allocation policy can be implemented in a DSIC diffusion auction mechanism. Moreover, given any monotonic allocation policy, we obtain the optimal payment policy to maximize the seller's revenue.
2
Chen, Jing, Bo Li, Yingkai Li, and Pinyan Lu. "Bayesian Auctions with Efficient Queries (Extended Abstract)." In Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}. California: International Joint Conferences on Artificial Intelligence Organization, 2022. http://dx.doi.org/10.24963/ijcai.2022/795.
Full textAbstract:
Designing dominant-strategy incentive compatible (DSIC) mechanisms for a seller to generate (approximately) optimal revenue by selling items to players is a fundamental problem in Bayesian mechanism design. However, most existing studies assume that the seller knows the entire distribution from which the players’ values are drawn. Unfortunately, this assumption may not hold in reality: for example, when the distributions have exponentially large supports or do not have succinct representations. In this work we consider, for the first time, the query complexityof Bayesian mechanisms. The seller only has limited oracle accesses to the players’ distributions, via quantile queriesand value queries. For single-item auctions, we design mechanisms with logarithmicnumber of value or quantile queries which achieve almost optimal revenue. We then prove logarithmic lower-bounds, i.e., logarithmic number of queries are necessary for any constant approximation DSIC mechanisms, even when randomized and adaptive queries are allowed. Thus our mechanisms are almost optimal regarding query complexity. Our lower-bounds can be extended to multi-item auctions with monotone subadditive valuations, and we complement this part with constant approximation mechanisms for unit-demand or additive valuation functions. Our results are robust even if the answers to the queries contain noises.
3
Chen, Jing, Bo Li, and Yingkai Li. "Approximately Maximizing the Broker's Profit in a Two-sided Market." In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. California: International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/22.
Full textAbstract:
We study how to maximize the broker's (expected) profit in a two-sided market, where she buys items from a set of sellers and resells them to a set of buyers. Each seller has a single item to sell and holds a private value on her item, and each buyer has a valuation function over the bundles of the sellers' items. We consider the Bayesian setting where the agents' values/valuations are independently drawn from prior distributions, and aim at designing dominant-strategy incentive-compatible (DSIC) mechanisms that are approximately optimal. Production-cost markets, where each item has a publicly-known cost to be produced, provide a platform for us to study two-sided markets. Briefly, we show how to covert a mechanism for production-cost markets into a mechanism for the broker, whenever the former satisfies cost-monotonicity. This reduction holds even when buyers have general combinatorial valuation functions. When the buyers' valuations are additive, we generalize an existing mechanism to production-cost markets in an approximation-preserving way. We then show that the resulting mechanism is cost-monotone and thus can be converted into an 8-approximation mechanism for two-sided markets.
4
Archbold, Thomas, Bart de Keijzer, and Carmine Ventre. "Non-Obvious Manipulability in Extensive-Form Mechanisms: The Revelation Principle for Single-Parameter Agents." In Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}. California: International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/278.
Full textAbstract:
Recent work in algorithmic mechanism design focuses on designing mechanisms for agents with bounded rationality, modifying the constraints that must be satisfied in order to achieve incentive compatibility. Starting with Li's strengthening of strategyproofness, obvious strategyproofness (OSP) requires truthtelling to be "obvious" over dishonesty, roughly meaning that the worst outcome from truthful actions must be no worse than the best outcome for dishonest ones. A celebrated result for dominant-strategy incentive-compatible mechanisms that allows us to restrict attention to direct mechanisms, known as the revelation principle, does not hold for OSP: the implementation details matter for the obvious incentive properties of the mechanism. Studying agent strategies in real-life mechanisms, Troyan and Morrill introduce a relaxation of strategyproofness known as non-obvious manipulability, which only requires comparing certain extrema of the agents' utility functions in order for a mechanism to be incentive-compatible. Specifically a mechanism is not obviously manipulable (NOM) if the best and worst outcomes when acting truthfully are no worse than the best and worst outcomes when acting dishonestly. In this work we first extend the cycle monotonicity framework for direct-revelation NOM mechanism design to indirect mechanisms. We then apply this to two settings, single-parameter agents and mechanisms for two agents in which one has a two-value domain, and show that under these models the revelation principle holds: direct mechanisms are just as powerful as indirect ones.