在门认可匹配的扭曲
Mohamad Latifian1, Alexandros A Voudouris2
1School of Informatics, University of Edinburgh, Scotland, UK.
概括
本研究分析了资源分配的匹配算法,重点是利用有限的代理实用信息最大限度地提高社会福利. 它在单边匹配场景中为决定性和随机方法建立了扭曲界限.
科学领域:
- 计算机科学 计算机科学
- 算法游戏理论 算法游戏理论
- 离散的数学 离散的数学
背景情况:
- 代理商拥有对物品的私人公用事业.
- 代理商报告项目划分为实用值.
- 目标是最大限度地提高社会福利在枢纽制约条件下.
研究的目的:
- 在与私人代理实用程序的设置中分析匹配算法.
- 计算项目分配,以近似最大社会福利.
- 为确定性和随机算法建立扭曲界限.
主要方法:
- 调查了一面匹配,每个代理一个项目.
- 分析了具有't'值效用级别的算法.
- 扩展分析到具有多个项目副本和代理能力的设置.
主要成果:
- 确定确定性匹配算法的扭曲极限: [公式:参见文本].
- 随机匹配算法的确定的扭曲界限: [公式:参见文本].
- 证明了扭曲界限对更复杂的匹配场景具有普遍性.
结论:
- 该研究为匹配算法的效率提供了理论界限.
- 有限的实用信息需要近似算法.
- 这些发现适用于各种资源分配问题.
相关概念视频
The Anchoring-and-Adjustment Heuristic
7.7K
In order to make good decisions, we use our knowledge and our reasoning. Often, this knowledge and reasoning is sound and solid. However, sometimes, we are swayed by biases or by others manipulating a situation. For example, let’s say you and three friends wanted to rent a house and had a combined target budget of $1,600. The realtor shows you only very run-down houses for $1,600 and then shows you a very nice house for $2,000. Might you ask each person to pay more in rent to get the...
7.7K
Confirmation Biases
7.6K
The confirmation bias is the tendency to focus on information that confirms our existing beliefs and ignore information that is inconsistent with our expectations. For example, if you think that your professor is not very nice, you notice all of the instances of rude behavior exhibited by the professor while ignoring the countless pleasant interactions he is involved in on a daily basis. Have you ever fallen prey to the confirmation bias, either as the source or target of such bias?
7.6K
Hypothesis: Accept or Fail to Reject?
29.3K
The outcome of any hypothesis testing leads to rejecting or not rejecting the null hypothesis. This decision is taken based on the analysis of the data, an appropriate test statistic, an appropriate confidence level, the critical values, and P-values. However, when the evidence suggests that the null hypothesis cannot be rejected, is it right to say, 'Accept' the null hypothesis?
There are two ways to indicate that the null hypothesis is not rejected. 'Accept' the null...
There are two ways to indicate that the null hypothesis is not rejected. 'Accept' the null...
29.3K
Testing a Claim about Standard Deviation
2.9K
A complete procedure to test a claim about population standard deviation or population variance is explained here.
The hypothesis testing for the claim of population standard deviation (or variance) requires the data and samples to be random and unbiased. The population distribution also must be normal. There is no specific requirement on the sample size as the estimation is based on the chi-square distribution.
As a first step, the hypothesis (null and alternative) concerning the claim about...
The hypothesis testing for the claim of population standard deviation (or variance) requires the data and samples to be random and unbiased. The population distribution also must be normal. There is no specific requirement on the sample size as the estimation is based on the chi-square distribution.
As a first step, the hypothesis (null and alternative) concerning the claim about...
2.9K
Mismatch Repair
6.3K
Organisms are capable of detecting and fixing nucleotide mismatches that occur during DNA replication. This sophisticated process requires identifying the new strand and replacing the erroneous bases with correct nucleotides. Mismatch repair is coordinated by many proteins in both prokaryotes and eukaryotes.
The Mutator Protein Family Plays a Key Role in DNA Mismatch Repair
The human genome has more than 3 billion base pairs of DNA per cell. Prior to cell division, that vast amount of genetic...
The Mutator Protein Family Plays a Key Role in DNA Mismatch Repair
The human genome has more than 3 billion base pairs of DNA per cell. Prior to cell division, that vast amount of genetic...
6.3K
¹³C NMR: Distortionless Enhancement by Polarization Transfer (DEPT)
1.6K
When proton-coupled carbon-13 spectra are simplified by a broadband proton decoupling technique, structural information about the coupled protons is lost. Distortionless enhancement by polarization transfer (DEPT) is a technique that provides information on the number of hydrogens attached to each carbon in a molecule. While the DEPT experiment utilizes complex pulse sequences, the pulse delay and flip angle are specifically manipulated. The resulting signals have different phases depending on...
1.6K


