Budget-feasible mechanism

Last updated December 10, 2024

In mechanism design, a branch of economics, a budget-feasible mechanism is a mechanism in which the total payment made by the auctioneer is upper-bounded by a fixed pre-specified budget. They were first presented by Yaron Singer,^[1] and studied by several others.^[2]^[3]^[4]

Related Research Articles

In graph theory, the metric dimension of a graph G is the minimum cardinality of a subset S of vertices such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP-hard problem; the decision version, determining whether the metric dimension is less than a given value, is NP-complete.

In the mathematical discipline of graph theory, a feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles. Equivalently, each FVS contains at least one vertex of any cycle in the graph. The feedback vertex set number of a graph is the size of a smallest feedback vertex set. The minimum feedback vertex set problem is an NP-complete problem; it was among the first problems shown to be NP-complete. It has wide applications in operating systems, database systems, and VLSI chip design.

A bigraph can be modelled as the superposition of a graph and a set of trees.

Algorithmic Number Theory Symposium (ANTS) is a biennial academic conference, first held in Cornell in 1994, constituting an international forum for the presentation of new research in computational number theory. They are devoted to algorithmic aspects of number theory, including elementary number theory, algebraic number theory, analytic number theory, geometry of numbers, arithmetic geometry, finite fields, and cryptography.

ProVerif is a software tool for automated reasoning about the security properties of cryptographic protocols. The tool has been developed by Bruno Blanchet and others.

The International Semantic Web Conference (ISWC) is a series of academic conferences and the premier international forum for the Semantic Web, Linked Data and Knowledge Graph Community. Here, scientists, industry specialists, and practitioners meet to discuss the future of practical, scalable, user-friendly, and game changing solutions. Its proceedings are published in the Lecture Notes in Computer Science by Springer-Verlag.

The Extended Semantic Web Conference, formerly known as the European Semantic Web Conference, is a yearly international academic conference on the topic of the Semantic Web. The event began in 2004, as the European Semantic Web Symposium. The goal of the event is "to bring together researchers and practitioners dealing with different aspects of semantics on the Web".

Gad Menahem Landau is an Israeli computer scientist noted for his contributions to combinatorial pattern matching and string algorithms and is the founding department chair of the Computer Science Department at the University of Haifa.

Fisher market is an economic model attributed to Irving Fisher. It has the following ingredients:

In the mathematical area of graph theory, a contact graph or tangency graph is a graph whose vertices are represented by geometric objects, and whose edges correspond to two objects touching according to some specified notion. It is similar to the notion of an intersection graph but differs from it in restricting the ways that the underlying objects are allowed to intersect each other.

Envy-free pricing is a kind of fair item allocation. There is a single seller that owns some items, and a set of buyers who are interested in these items. The buyers have different valuations to the items, and they have a quasilinear utility function; this means that the utility an agent gains from a bundle of items equals the agent's value for the bundle minus the total price of items in the bundle. The seller should determine a price for each item, and sell the items to some of the buyers, such that there is no envy. Two kinds of envy are considered:

Runtime predictive analysis is a runtime verification technique in computer science for detecting property violations in program executions inferred from an observed execution. An important class of predictive analysis methods has been developed for detecting concurrency errors in concurrent programs, where a runtime monitor is used to predict errors which did not happen in the observed run, but can happen in an alternative execution of the same program. The predictive capability comes from the fact that the analysis is performed on an abstract model extracted online from the observed execution, which admits a class of executions beyond the observed one.

In economics, a budget-additive valuation is a kind of a utility function. It corresponds to a person that, when given a set of items, evaluates them in the following way:

In mechanism design, a branch of economics, a weakly-budget-balanced (WBB) mechanism is a mechanism in which the total payment made by the participants is at least 0. This means that the mechanism operator does not incur a deficit, i.e., does not have to subsidize the market. Weak budget balance is considered a necessary requirement for the economic feasibility of a mechanism. A strongly-budget-balanced (SBB) mechanism is a mechanism in which the total payment made by the participants is exactly 0. This means that all payments are made among the participants - the mechanism has neither a deficit nor a surplus. The term budget-balanced mechanism is sometimes used as a shorthand for WBB, and sometimes as a shorthand for SBB.

The International Symposium on Experimental Algorithms (SEA), previously known as Workshop on Experimental Algorithms (WEA), is a computer science conference in the area of algorithm engineering.

In algorithmic game theory, a branch of both computer science and economics, a demand oracle is a function that, given a price-vector, returns the demand of an agent. It is used by many algorithms related to pricing and optimization in online market. It is usually contrasted with a value oracle, which is a function that, given a set of items, returns the value assigned to them by an agent.

In computer science, choreographic programming is a programming paradigm where programs are compositions of interactions among multiple concurrent participants.

The LogicBlox system is a commercial, declarative, incremental logic programming language and deductive database inspired by Datalog. The LogiQL programming language extends Datalog with several features, including stratified negation, aggregation, and a module system. LogicBlox has been used to build pointer analyses for Java.

In computer science and mathematical logic, Cooperating Validity Checker (CVC) is a family of satisfiability modulo theories (SMT) solvers. The latest major versions of CVC are CVC4 and CVC5 ; earlier versions include CVC, CVC Lite, and CVC3. Both CVC4 and cvc5 support the SMT-LIB and TPTP input formats for solving SMT problems, and the SyGuS-IF format for program synthesis. Both CVC4 and cvc5 can output proofs that can be independently checked in the LFSC format, cvc5 additionally supports the Alethe and Lean 4 formats. cvc5 has bindings for C++, Python, and Java.

References

↑ Singer, Yaron (2010-10-01). "Budget Feasible Mechanisms". 2010 IEEE 51st Annual Symposium on Foundations of Computer Science. pp. 765–774. doi:10.1109/FOCS.2010.78. ISBN 978-1-4244-8525-3. S2CID 11916656.
↑ Chen, Ning; Gravin, Nick; Lu, Pinyan (2011-01-23), "On the Approximability of Budget Feasible Mechanisms", Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, Society for Industrial and Applied Mathematics, pp. 685–699, arXiv: 1007.3801 , doi: 10.1137/1.9781611973082.54 , ISBN 978-0-89871-993-2, S2CID 14406192
↑ Horel, Thibaut; Ioannidis, Stratis; Muthukrishnan, S. (2014). "Budget Feasible Mechanisms for Experimental Design". In Pardo, Alberto; Viola, Alfredo (eds.). LATIN 2014: Theoretical Informatics. Lecture Notes in Computer Science. Vol. 8392. Berlin, Heidelberg: Springer. pp. 719–730. arXiv: 1302.5724 . doi:10.1007/978-3-642-54423-1_62. ISBN 978-3-642-54423-1. S2CID 145181.
↑ Jalaly Khalilabadi, Pooya; Tardos, Éva (2018). "Simple and Efficient Budget Feasible Mechanisms for Monotone Submodular Valuations". In Christodoulou, George; Harks, Tobias (eds.). Web and Internet Economics. Lecture Notes in Computer Science. Vol. 11316. Cham: Springer International Publishing. pp. 246–263. arXiv: 1703.10681 . doi:10.1007/978-3-030-04612-5_17. ISBN 978-3-030-04612-5. S2CID 15747265.

This economics-related article is a stub. You can help Wikipedia by expanding it.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Singer, Yaron (2010-10-01). "Budget Feasible Mechanisms". 2010 IEEE 51st Annual Symposium on Foundations of Computer Science. pp. 765–774. doi:10.1109/FOCS.2010.78. ISBN 978-1-4244-8525-3. S2CID 11916656.

[2] Chen, Ning; Gravin, Nick; Lu, Pinyan (2011-01-23), "On the Approximability of Budget Feasible Mechanisms", Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, Society for Industrial and Applied Mathematics, pp. 685–699, arXiv: 1007.3801 , doi: 10.1137/1.9781611973082.54 , ISBN 978-0-89871-993-2, S2CID 14406192

[3] Horel, Thibaut; Ioannidis, Stratis; Muthukrishnan, S. (2014). "Budget Feasible Mechanisms for Experimental Design". In Pardo, Alberto; Viola, Alfredo (eds.). LATIN 2014: Theoretical Informatics. Lecture Notes in Computer Science. Vol. 8392. Berlin, Heidelberg: Springer. pp. 719–730. arXiv: 1302.5724 . doi:10.1007/978-3-642-54423-1_62. ISBN 978-3-642-54423-1. S2CID 145181.

[4] Jalaly Khalilabadi, Pooya; Tardos, Éva (2018). "Simple and Efficient Budget Feasible Mechanisms for Monotone Submodular Valuations". In Christodoulou, George; Harks, Tobias (eds.). Web and Internet Economics. Lecture Notes in Computer Science. Vol. 11316. Cham: Springer International Publishing. pp. 246–263. arXiv: 1703.10681 . doi:10.1007/978-3-030-04612-5_17. ISBN 978-3-030-04612-5. S2CID 15747265.

[1]

[2]

[3]

[4]