Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOptimal Multi-Dimensional Mechanisms are not Local
84
0
0.0
(
0
)
Added by
Zixin Zhou
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Consider the problem of implementing a revenue-optimal, Bayesian Incentive Compatible auction when buyers values are drawn from distributions $times_i D_i$ on a particular instance $vec{v}$. Optimal single-dimensional mechanisms are local: in order to allocate the item correctly on a particular valuation profile $vec{v}$, only $tilde{O}(1)$ bits are needed from each player (specifically, their Myerson virtual value [Mye81]), rather than the entire distribution. We show that optimal multi-dimensional mechanisms are not local: in order to allocate the item correctly on a particular valuation profile $vec{v}$, one still needs to know (essentially) the entire distribution. Specifically, if the distributions have support-size $n$, then $Omega(n)$ bits are necessary from each bidder. We show that this phenomenon already occurs with just two bidders, even when one bidder is single-dimensional, and even when the other bidder is barely multi-dimensional. More specifically, the multi-dimensional bidder is inter-dimensional from the FedEx setting with just two days [FGKK16].
rate research
Read More
Many two-sided matching markets, from labor markets to school choice programs, use a clearinghouse based on the applicant-proposing deferred acceptance algorithm, which is well known to be strategy-proof for the applicants. Nonetheless, a growing amount of empirical evidence reveals that applicants misrepresent their preferences when this mechanism is used. This paper shows that no mechanism that implements a stable matching is obviously strategy-proof for any side of the market, a stronger incentive property than strategy-proofness that was introduced by Li (2017). A stable mechanism that is obviously strategy-proof for applicants is introduced for the case in which agents on the other side have acyclical preferences.
We study revenue maximization by deterministic mechanisms for the simplest case for which Myersons characterization does not hold: a single seller selling two items, with independently distributed values, to a single additive buyer. We prove that optimal mechanisms are submodular and hence monotone. Furthermore, we show that in the IID case, optimal mechanisms are symmetric. Our characterizations are surprisingly non-trivial, and we show that they fail to extend in several natural ways, e.g. for correlated distributions or more than two items. In particular, this shows that the optimality of symmetric mechanisms does not follow from the symmetry of the IID distribution.
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.
We study a family of subvarieties of the flag variety defined by certain linear conditions, called Hessenberg varieties. We compare them to Schubert varieties. We prove that some Schubert varieties can be realized as Hessenberg varieties and vice versa. Our proof explicitly identifies these Schubert varieties by their permutation and computes their dimension. We use this to answer an open question by proving that Hessenberg varieties are not always pure dimensional. We give examples that neither semisimple nor nilpotent Hessenberg varieties need be pure; the latter are connected, non-pure-dimensional Hessenberg varieties. Our methods require us to generalize the definition of Hessenberg varieties.
We study a market of investments on networks, where each agent (vertex) can invest in any enterprise linked to him, and at the same time, raise capital for his firm own enterprise from other agents he is linked to. Failing to raise sufficient capital results with the firm defaulting, being unable to invest in others. Our main objective is to examine the role of collaterals in handling the strategic risk that can propagate to a systemic risk throughout the network in a cascade of defaults. We take a mechanism design approach and solve for the optimal scheme of collateral contracts that capital raisers offer their investors. These contracts aim at sustaining the efficient level of investment as a unique Nash equilibrium, while minimizing the total collateral. Our main results contrast the network environment with its non-network counterpart (where the sets of investors and capital raisers are disjoint). We show that for acyclic investment networks, the network environment does not necessitate any additional collaterals, and systemic risk can be fully handled by optimal bilateral collateral contracts between capital raisers and their investors. This is, unfortunately, not the case for cyclic investment networks. We show that bilateral contracting will not suffice to resolve systemic risk, and the market will need an external entity to design a global collateral scheme for all capital raisers. Furthermore, the minimum total collateral that will sustain the efficient level of investment as a unique equilibrium may be arbitrarily higher, even in simple cyclic investment networks, compared with its corresponding non-network environment. Additionally, we prove computational-complexity results, both for a single enterprise and for networks.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
