Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userContingent Payment Mechanisms for Resource Utilization
127
0
0.0
(
0
)
Added by
Hongyao Ma
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We introduce the problem of assigning resources to improve their utilization. The motivation comes from settings where agents have uncertainty about their own values for using a resource, and where it is in the interest of a group that resources be used and not wasted. Done in the right way, improved utilization maximizes social welfare--- balancing the utility of a high value but unreliable agent with the groups preference that resources be used. We introduce the family of contingent payment mechanisms (CP), which may charge an agent contingent on use (a penalty). A CP mechanism is parameterized by a maximum penalty, and has a dominant-strategy equilibrium. Under a set of axiomatic properties, we establish welfare-optimality for the special case CP(W), with CP instantiated for a maximum penalty equal to societal value W for utilization. CP(W) is not dominated for expected welfare by any other mechanism, and second, amongst mechanisms that always allocate the resource and have a simple indirect structure, CP(W) strictly dominates every other mechanism. The special case with no upper bound on penalty, the contingent second-price mechanism, maximizes utilization. We extend the mechanisms to assign multiple, heterogeneous resources, and present a simulation study of the welfare properties of these mechanisms.
rate research
Read More
In this paper, we design gross product maximization mechanisms which incentivize users to upload high-quality contents on user-generated-content (UGC) websites. We show that, the proportional division mechanism, which is widely used in practice, can perform arbitrarily bad in the worst case. The problem can be formulated using a linear program with bounded and increasing variables. We then present an $O(nlog n)$ algorithm to find the optimal mechanism, where n is the number of players.
Mechanism design is addressed in the context of fair allocations of indivisible goods with monetary compensation. Motivated by a real-world social choice problem, mechanisms with verification are considered in a setting where (i) agents declarations on allocated goods can be fully verified before payments are performed, and where (ii) verification is not used to punish agents whose declarations resulted in incorrect ones. Within this setting, a mechanism is designed that is shown to be truthful, efficient, and budget-balanced, and where agents utilities are fairly determined by the Shapley value of suitable coalitional games. The proposed mechanism is however shown to be #P-complete. Thus, to deal with applications with many agents involved, two polynomial-time randomized variants are also proposed: one that is still truthful and efficient, and which is approximately budget-balanced with high probability, and another one that is truthful in expectation, while still budget-balanced and efficient.
We formulate and study the algorithmic mechanism design problem for a general class of resource allocation settings, where the center redistributes the private resources brought by individuals. Money transfer is forbidden. Distinct from the standard literature, which assumes the amount of resources brought by an individual to be public information, we consider this amount as an agents private, possibly multi-dimensional type. Our goal is to design truthful mechanisms that achieve two objectives: max-min and Pareto efficiency. For each objective, we provide a reduction that converts any optimal algorithm into a strategy-proof mechanism that achieves the same objective. Our reductions do not inspect the input algorithms but only query these algorithms as oracles. Applying the reductions, we produce strategy-proof mechanisms in a non-trivial application: network route allocation. Our models and result in the application are valuable on their own rights.
Payment networks were introduced to address the limitation on the transaction throughput of popular blockchains. To open a payment channel one has to publish a transaction on-chain and pay the appropriate transaction fee. A transaction can be routed in the network, as long as there is a path of channels with the necessary capital. The intermediate nodes on this path can ask for a fee to forward the transaction. Hence, opening channels, although costly, can benefit a party, both by reducing the cost of the party for sending a transaction and by collecting the fees from forwarding transactions of other parties. This trade-off spawns a network creation game between the channel parties. In this work, we introduce the first game theoretic model for analyzing the network creation game on blockchain payment channels. Further, we examine various network structures (path, star, complete bipartite graph and clique) and determine for each one of them the constraints (fee value) under which they constitute a Nash equilibrium, given a fixed fee policy. Last, we show that the star is a Nash equilibrium when each channel party can freely decide the channel fee. On the other hand, we prove the complete bipartite graph can never be a Nash equilibrium, given a free fee policy.
Let $(f,P)$ be an incentive compatible mechanism where $f$ is the social choice function and $P$ is the payment function. In many important settings, $f$ uniquely determines $P$ (up to a constant) and therefore a common approach is to focus on the design of $f$ and neglect the role of the payment function. Fadel and Segal [JET, 2009] question this approach by taking the lenses of communication complexity: can it be that the communication complexity of an incentive compatible mechanism that implements $f$ (that is, computes both the output and the payments) is much larger than the communication complexity of computing the output? I.e., can it be that $cc_{IC}(f)>>cc(f)$? Fadel and Segal show that for every $f$, $cc_{IC}(f)leq exp(cc(f))$. They also show that fully computing the incentive compatible mechanism is strictly harder than computing only the output: there exists a social choice function $f$ such that $cc_{IC}(f)=cc(f)+1$. In a follow-up work, Babaioff, Blumrosen, Naor, and Schapira [EC08] provide a social choice function $f$ such that $cc_{IC}(f)=Theta(ncdot cc(f))$, where $n$ is the number of players. The question of whether the exponential upper bound of Fadel and Segal is tight remained wide open. In this paper we solve this question by explicitly providing an $f$ such that $cc_{IC}(f)= exp(cc(f))$. In fact, we establish this via two very different proofs. In contrast, we show that if the players are risk-neutral and we can compromise on a randomized truthful-in-expectation implementation (and not on deterministic ex-post implementation) gives that $cc_{TIE}(f)=poly(n,cc(f))$ for every function $f$, as long as the domain of $f$ is single parameter or a convex multi-parameter domain. We also provide efficient algorithms for deterministic computation of payments in several important domains.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
