Showing posts with label Budish. Show all posts
Showing posts with label Budish. Show all posts

Monday, May 29, 2023

Further progress on course allocation, by Budish, Gao, Othman, Rubinstein and Zhang

 Here are some new developments in the course allocation mechanism used initially in Wharton and now elsewhere.  It turns out that strategy-proofness in the (very) large doesn't imply strategyproofness in samples of realistic size, but this seems to be fixable (and profitable manipulations were not easy to find). The paper concludes with some far ranging thoughts on the econ-cs interface.

Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI)   by ERIC BUDISH, RUIQUAN GAO, ABRAHAM OTHMAN  AVIAD RUBINSTEIN, and QIANFAN ZHANG

Abstract: "Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is an equilibrium-based solution concept for fair division of discrete items to agents with combinatorial demands. In theory, it is known that in asymptotically large markets:

•For incentives, the A-CEEI mechanism is Envy-Free-but-for-Tie-Breaking (EF-TB), which implies that it is Strategyproof-in-the-Large (SP-L).

•From a computational perspective, computing the equilibrium solution is unfortunately a computationally intractable problem (in the worst-case, assuming PPAD≠FP).

We develop a new heuristic algorithm that outperforms the previous state-of-the-art by multiple orders of magnitude. This new, faster algorithm lets us perform experiments on real-world inputs for the first time. We discover that with real-world preferences, even in a realistic implementation that satisfies the EF-TB and SP-L properties, agents may have surprisingly simple and plausible deviations from truthful reporting of preferences. To this end, we propose a novel strengthening of EF-TB, which dramatically reduces the potential for strategic deviations from truthful reporting in our experiments. A (variant of ) our algorithm is now in production: on real course allocation problems it is much faster, has zero clearing error, and has stronger incentive properties than the prior state-of-the-art implementation"

Here's an intriguing passage:

"In Section 6 we use our manipulation-finding algorithm in combination with our fast A-CEEI finding algorithm to explore the plausibility of effective manipulations for students bidding in ACEEI. Originally, we had expected that since our mechanism satisfies the EF-TB and SP-L properties, it would at least be practically strategyproof — if even we don’t really understand the way our algorithm chooses among the many possible equilibria, how can a student with limited information learn to strategically bid in such a complex environment? 

"Indeed, in 2 out of 3 schools that we tested, our manipulation-finding algorithms finds very few or no statistically significant manipulations at all. However, when analyzing the 3rd school, we stumbled upon a simple and effective manipulation for (the first iteration of) our mechanism. We emphasize that although the manipulation is simple in hindsight, in over a year of working on this project we failed to predict it by analyzing the algorithm — the manipulation was discovered by the algorithm

"Inspired by this manipulation, we propose a natural strengthening of envy-free (discussed below), which we call contested-envy free. We encode the analogous contested EF-TB as a new constraint in our algorithm (specifically, the integer program for finding optimal budget perturbations). Fortunately, our algorithm is still very fast even with this more elaborate constraint. And, when we re-run our manipulation-finding experiments, we observe that contested EF-TB significantly reduces the potential for manipulations in practice."

...

"Conclusion:  In this work, we give a significantly faster algorithm for computing A-CEEI. Kamal Jain’s famous formulation “if your laptop cannot find it then neither can the market” [Papadimitriou 2007] was originally intended as a negative result, casting doubt on the practical implications of many famous economic concepts because of their worst-case computational complexity results. Even for course allocation, where a heuristic algorithm existed and worked in practice, Jain’s formulation seemed to still bind, as solving A-CEEI involved an intense day-long process with a fleet of high-powered cloud servers operating in parallel. The work detailed in this paper has significantly progressed what laptops can find: even the largest and most challenging real course allocation problems we have access to can now be solved in under an hour on a commodity laptop. 

"This significant practical improvement suggests that the relationship between prices and demand for the course allocation problem—and potentially other problems of economic interest with complex agent preferences and heterogeneous goods—may be much simpler than has been previously believed and may be far more tractable in practice than the worst-case theoretical bounds. Recalling Jain’s dictum, perhaps many more market equilibria can be found by laptops—or, perhaps, Walras’s original and seemingly naive description of how prices iterate in the real world may in fact typically produce approximate equilibria. 

"Our fast algorithm also opens the door for empirical research on A-CEEI, because we can now solve many instances and see how the solution changes for different inputs. We took it in one direction: empirically investigating the incentives properties of A-CEEI for the first time. For course allocation specifically, this faster algorithm opens up new avenues for improving student outcomes through experimentation. For instance, university administrators often want to subsidize some 6 group of students (e.g., second-year MBA students over first-year MBA students), but are unsure how large of a budget subsidy to grant those students to balance equity against their expectations. Being able to run more assignments with different subsidies can help to resolve this issue."

*************

Earlier related posts:

Thursday, April 23, 2009

Sunday, October 4, 2009

Thursday, May 30, 2013

Monday, August 3, 2015

Tuesday, June 9, 2020

Tuesday, November 15, 2022

Eric Budish on the economics of cryptocurrencies (video of his Harris Lecture at Harvard)

 If you haven't heard Eric Budish talk about crypto, this is your chance:  here's the video of his Harris Lecture at Harvard: The Economics of Cryptocurrencies by Eric Budish

(It was delivered before the recent collapse of the FTX exchange.)

Friday, May 18, 2018

Eric Budish on (expensive) blockchain technology


The Economic Limits of the Blockchain
by Eric Budish
May 3, 2018

Abstract: The amount of computational power devoted to blockchains such as Bitcoin’s must simultaneously satisfy two conditions in equilibrium: (1) a zero-profit condition among miners,who engage in a rent-seeking competition for the prize associated with adding the next block to the chain; and (2) an incentive compatibility condition on the system’s vulnerability to a“majority attack”, namely that the computational costs of such an attack must exceed the benefits. Together, these two equations imply that (3) the recurring, “flow”, payments to miners for running the blockchain must be large relative to the one-off, “stock”, benefits of attacking it. The constraint is softer (i.e., stock versus stock) if both (i) the mining technology used to run the blockchain is both scarce and non-repurposable, and (ii) any majority attack is a “sabotage” in that it causes a collapse in the economic value of the blockchain; however, reliance on non-repurposable technology for security and vulnerability to sabotage each raise their own concerns, and point to specific collapse scenarios. Overall the results place potentially serious economic constraints on the applicability of the Nakamoto (2008) blockchain innovation. The anonymous, decentralized trust enabled by the blockchain, while ingenious, is expensive.

Saturday, April 14, 2018

Are financial markets too fast? A discussion of high speed trading (with Eric Budish)




"On this episode of The Big Question, Chicago Booth Review's Hal Weitzman talks with Chicago Booth professor of economics Eric Budish, Chicago Trading Company's Steve Crutchfield, and former Commodity Futures Trading Commission commissioner Sharon Bowen about how speed affects financial markets and what, if anything, we should do about it."

Eric points out that competition among exchanges has worked well in driving down trading fees, and poorly in selling access--"co-location"--since each exchange has a monopoly on selling speedy access to its data.

Friday, March 21, 2014

Insider trading 2.0? New York State Attorney General talks about high frequency trading and market design

New York State Attorney General Eric Schneiderman has been talking market design, in a lawman sort of way. Interestingly, he's interested in the proposal by Budish, Cramton and Shim for frequent batch auctions. (See previous posts here and here.)


Schneiderman: "We Will Continue to Shine a Light on Unseemly Practices That Cater to High-Frequency Traders at the Expense of Other Investors, and Other Forms of Insider Trading 2.0"
****************

"As your Attorney General, I am the top law enforcement officer for the State of 
New York, which gives me a unique role to play in the oversight of Wall Street. 
And I take that very, very seriously. I spent most of my career in private practice 
before becoming Attorney General, which is really a distinction among 
Attorneys General in New York State. And I represented big financial firms; I 
represented stock and commodities markets. 

"And I am a believer in our market system, and I am a believer that our market 
can only function with strong, clear regulations, and uniform and equitable 
enforcement of those regulations. 

"We have to ensure that our markets work for the entire investing public, not 
just for a small number. And the Martin Act, which I hope you’ve heard of, 
empowers my office, and our Investor Protection Bureau in particular, to  investigate pretty much any fraudulent or deceptive practice in financial 
dealings. 

"One of the fundamental principles that drives every part of our office is a very 
simple, very American notion of equal justice under law. There has to be one 
set of rules for everyone. 
...
"But, as I mentioned, our capital markets can only succeed if investors view them 
as fair and as fairly regulated. 

"So that’s why we’ve been focusing on cracking down on fundamentally unfair – 
and potentially illegal – situations that fall outside the parameters of traditional 
insider trading but give elite groups of traders access to market-moving 
information at the expense of the rest of the market. 

"This is what we call Insider Trading 2.0, and it’s one of the greatest threats to 
public confidence in the markets. 
...
"Currently, on our exchanges, securities are traded continuously, which means 
that orders are constantly accepted and matched with ties broken based on 
which orders arrived first. This system rewards high-frequency traders who 
continuously flood the market with orders – emphasizing speed over price. 

"The University of Chicago proposal – which I endorse – would, in effect, put a speed bump in place. Orders would be processed in batches after short 
intervals – potentially a second or less than a second in length – but that would ensure that the price would be the deciding factor in who obtains a trade, not who has the fastest supercomputer and early access to market-moving information. 

"This structural reform – sometimes called “frequent batch auctions” -- would help catch and cap the supercomputer arms race now underway. This is 
tremendously important, because even advocates of high-frequency trading 
have always recognized that the potential for destabilization of the markets 
from volatility is a problem. 

"If you had frequent batch auctions, there’s no point in trying to get faster than 
whatever the interval is. It would discourage the risk taking that can cause flash 
crashes because, in the quest for greater and greater speed, there is, in and of 
itself, a threat to market stability. It rewards those who are taking chances. It 
rewards those who try risky new ways to gain a few milliseconds of speed. And that’s something we could put an end to if this proposal were successfully 
carried out. "
 ***************

"Attorney General Eric Schneiderman said today that he’s examining the sale of products and services that offer faster access to data and richer information on trades than what’s typically available to the public. Wall Street banks and rapid-fire trading firms pay thousands of dollars a month for these services from firms including Nasdaq OMX Group Inc. and IntercontinentalExchange Group Inc.’s New York Stock Exchange."
**********************

..."frequent batch auctions, something that came out of the University of Chicago, not some enemy of free markets..."